1 //===-- StackColoring.cpp -------------------------------------------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This pass implements the stack-coloring optimization that looks for 11 // lifetime markers machine instructions (LIFESTART_BEGIN and LIFESTART_END), 12 // which represent the possible lifetime of stack slots. It attempts to 13 // merge disjoint stack slots and reduce the used stack space. 14 // NOTE: This pass is not StackSlotColoring, which optimizes spill slots. 15 // 16 // TODO: In the future we plan to improve stack coloring in the following ways: 17 // 1. Allow merging multiple small slots into a single larger slot at different 18 // offsets. 19 // 2. Merge this pass with StackSlotColoring and allow merging of allocas with 20 // spill slots. 21 // 22 //===----------------------------------------------------------------------===// 23 24 #define DEBUG_TYPE "stackcoloring" 25 #include "MachineTraceMetrics.h" 26 #include "llvm/Function.h" 27 #include "llvm/Module.h" 28 #include "llvm/ADT/BitVector.h" 29 #include "llvm/Analysis/Dominators.h" 30 #include "llvm/Analysis/ValueTracking.h" 31 #include "llvm/ADT/DepthFirstIterator.h" 32 #include "llvm/ADT/PostOrderIterator.h" 33 #include "llvm/ADT/SetVector.h" 34 #include "llvm/ADT/SmallPtrSet.h" 35 #include "llvm/ADT/SparseSet.h" 36 #include "llvm/ADT/Statistic.h" 37 #include "llvm/CodeGen/LiveInterval.h" 38 #include "llvm/CodeGen/MachineLoopInfo.h" 39 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h" 40 #include "llvm/CodeGen/MachineDominators.h" 41 #include "llvm/CodeGen/MachineBasicBlock.h" 42 #include "llvm/CodeGen/MachineFunctionPass.h" 43 #include "llvm/CodeGen/MachineLoopInfo.h" 44 #include "llvm/CodeGen/MachineModuleInfo.h" 45 #include "llvm/CodeGen/MachineRegisterInfo.h" 46 #include "llvm/CodeGen/MachineFrameInfo.h" 47 #include "llvm/CodeGen/MachineMemOperand.h" 48 #include "llvm/CodeGen/Passes.h" 49 #include "llvm/CodeGen/SlotIndexes.h" 50 #include "llvm/DebugInfo.h" 51 #include "llvm/MC/MCInstrItineraries.h" 52 #include "llvm/Target/TargetInstrInfo.h" 53 #include "llvm/Target/TargetRegisterInfo.h" 54 #include "llvm/Support/CommandLine.h" 55 #include "llvm/Support/Debug.h" 56 #include "llvm/Support/raw_ostream.h" 57 58 using namespace llvm; 59 60 static cl::opt<bool> 61 DisableColoring("no-stack-coloring", 62 cl::init(true), cl::Hidden, 63 cl::desc("Suppress stack coloring")); 64 65 STATISTIC(NumMarkerSeen, "Number of life markers found."); 66 STATISTIC(StackSpaceSaved, "Number of bytes saved due to merging slots."); 67 STATISTIC(StackSlotMerged, "Number of stack slot merged."); 68 69 //===----------------------------------------------------------------------===// 70 // StackColoring Pass 71 //===----------------------------------------------------------------------===// 72 73 namespace { 74 /// StackColoring - A machine pass for merging disjoint stack allocations, 75 /// marked by the LIFETIME_START and LIFETIME_END pseudo instructions. 76 class StackColoring : public MachineFunctionPass { 77 MachineFrameInfo *MFI; 78 MachineFunction *MF; 79 80 /// A class representing liveness information for a single basic block. 81 /// Each bit in the BitVector represents the liveness property 82 /// for a different stack slot. 83 struct BlockLifetimeInfo { 84 /// Which slots BEGINs in each basic block. 85 BitVector Begin; 86 /// Which slots ENDs in each basic block. 87 BitVector End; 88 /// Which slots are marked as LIVE_IN, coming into each basic block. 89 BitVector LiveIn; 90 /// Which slots are marked as LIVE_OUT, coming out of each basic block. 91 BitVector LiveOut; 92 }; 93 94 /// Maps active slots (per bit) for each basic block. 95 DenseMap<MachineBasicBlock*, BlockLifetimeInfo> BlockLiveness; 96 97 /// Maps serial numbers to basic blocks. 98 DenseMap<MachineBasicBlock*, int> BasicBlocks; 99 /// Maps basic blocks to a serial number. 100 SmallVector<MachineBasicBlock*, 8> BasicBlockNumbering; 101 102 /// Maps liveness intervals for each slot. 103 SmallVector<LiveInterval*, 16> Intervals; 104 /// VNInfo is used for the construction of LiveIntervals. 105 VNInfo::Allocator VNInfoAllocator; 106 /// SlotIndex analysis object. 107 SlotIndexes* Indexes; 108 109 /// The list of lifetime markers found. These markers are to be removed 110 /// once the coloring is done. 111 SmallVector<MachineInstr*, 8> Markers; 112 113 /// SlotSizeSorter - A Sort utility for arranging stack slots according 114 /// to their size. 115 struct SlotSizeSorter { 116 MachineFrameInfo *MFI; 117 SlotSizeSorter(MachineFrameInfo *mfi) : MFI(mfi) { } 118 bool operator()(int LHS, int RHS) { 119 // We use -1 to denote a uninteresting slot. Place these slots at the end. 120 if (LHS == -1) return false; 121 if (RHS == -1) return true; 122 // Sort according to size. 123 return MFI->getObjectSize(LHS) > MFI->getObjectSize(RHS); 124 } 125 }; 126 127 public: 128 static char ID; 129 StackColoring() : MachineFunctionPass(ID) { 130 initializeStackColoringPass(*PassRegistry::getPassRegistry()); 131 } 132 void getAnalysisUsage(AnalysisUsage &AU) const; 133 bool runOnMachineFunction(MachineFunction &MF); 134 135 private: 136 /// Debug. 137 void dump(); 138 139 /// Removes all of the lifetime marker instructions from the function. 140 /// \returns true if any markers were removed. 141 bool removeAllMarkers(); 142 143 /// Scan the machine function and find all of the lifetime markers. 144 /// Record the findings in the BEGIN and END vectors. 145 /// \returns the number of markers found. 146 unsigned collectMarkers(unsigned NumSlot); 147 148 /// Perform the dataflow calculation and calculate the lifetime for each of 149 /// the slots, based on the BEGIN/END vectors. Set the LifetimeLIVE_IN and 150 /// LifetimeLIVE_OUT maps that represent which stack slots are live coming 151 /// in and out blocks. 152 void calculateLocalLiveness(); 153 154 /// Construct the LiveIntervals for the slots. 155 void calculateLiveIntervals(unsigned NumSlots); 156 157 /// Go over the machine function and change instructions which use stack 158 /// slots to use the joint slots. 159 void remapInstructions(DenseMap<int, int> &SlotRemap); 160 161 /// Map entries which point to other entries to their destination. 162 /// A->B->C becomes A->C. 163 void expungeSlotMap(DenseMap<int, int> &SlotRemap, unsigned NumSlots); 164 }; 165 } // end anonymous namespace 166 167 char StackColoring::ID = 0; 168 char &llvm::StackColoringID = StackColoring::ID; 169 170 INITIALIZE_PASS_BEGIN(StackColoring, 171 "stack-coloring", "Merge disjoint stack slots", false, false) 172 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 173 INITIALIZE_PASS_DEPENDENCY(SlotIndexes) 174 INITIALIZE_PASS_END(StackColoring, 175 "stack-coloring", "Merge disjoint stack slots", false, false) 176 177 void StackColoring::getAnalysisUsage(AnalysisUsage &AU) const { 178 AU.addRequired<MachineDominatorTree>(); 179 AU.addPreserved<MachineDominatorTree>(); 180 AU.addRequired<SlotIndexes>(); 181 MachineFunctionPass::getAnalysisUsage(AU); 182 } 183 184 void StackColoring::dump() { 185 for (df_iterator<MachineFunction*> FI = df_begin(MF), FE = df_end(MF); 186 FI != FE; ++FI) { 187 unsigned Num = BasicBlocks[*FI]; 188 DEBUG(dbgs()<<"Inspecting block #"<<Num<<" ["<<FI->getName()<<"]\n"); 189 Num = 0; 190 DEBUG(dbgs()<<"BEGIN : {"); 191 for (unsigned i=0; i < BlockLiveness[*FI].Begin.size(); ++i) 192 DEBUG(dbgs()<<BlockLiveness[*FI].Begin.test(i)<<" "); 193 DEBUG(dbgs()<<"}\n"); 194 195 DEBUG(dbgs()<<"END : {"); 196 for (unsigned i=0; i < BlockLiveness[*FI].End.size(); ++i) 197 DEBUG(dbgs()<<BlockLiveness[*FI].End.test(i)<<" "); 198 199 DEBUG(dbgs()<<"}\n"); 200 201 DEBUG(dbgs()<<"LIVE_IN: {"); 202 for (unsigned i=0; i < BlockLiveness[*FI].LiveIn.size(); ++i) 203 DEBUG(dbgs()<<BlockLiveness[*FI].LiveIn.test(i)<<" "); 204 205 DEBUG(dbgs()<<"}\n"); 206 DEBUG(dbgs()<<"LIVEOUT: {"); 207 for (unsigned i=0; i < BlockLiveness[*FI].LiveOut.size(); ++i) 208 DEBUG(dbgs()<<BlockLiveness[*FI].LiveOut.test(i)<<" "); 209 DEBUG(dbgs()<<"}\n"); 210 } 211 } 212 213 unsigned StackColoring::collectMarkers(unsigned NumSlot) { 214 unsigned MarkersFound = 0; 215 // Scan the function to find all lifetime markers. 216 // NOTE: We use the a reverse-post-order iteration to ensure that we obtain a 217 // deterministic numbering, and because we'll need a post-order iteration 218 // later for solving the liveness dataflow problem. 219 for (df_iterator<MachineFunction*> FI = df_begin(MF), FE = df_end(MF); 220 FI != FE; ++FI) { 221 222 // Assign a serial number to this basic block. 223 BasicBlocks[*FI] = BasicBlockNumbering.size(); 224 BasicBlockNumbering.push_back(*FI); 225 226 BlockLiveness[*FI].Begin.resize(NumSlot); 227 BlockLiveness[*FI].End.resize(NumSlot); 228 229 for (MachineBasicBlock::iterator BI = (*FI)->begin(), BE = (*FI)->end(); 230 BI != BE; ++BI) { 231 232 if (BI->getOpcode() != TargetOpcode::LIFETIME_START && 233 BI->getOpcode() != TargetOpcode::LIFETIME_END) 234 continue; 235 236 Markers.push_back(BI); 237 238 bool IsStart = BI->getOpcode() == TargetOpcode::LIFETIME_START; 239 MachineOperand &MI = BI->getOperand(0); 240 unsigned Slot = MI.getIndex(); 241 242 MarkersFound++; 243 244 const Value *Allocation = MFI->getObjectAllocation(Slot); 245 if (Allocation) { 246 DEBUG(dbgs()<<"Found lifetime marker for allocation: "<< 247 Allocation->getName()<<"\n"); 248 } 249 250 if (IsStart) { 251 BlockLiveness[*FI].Begin.set(Slot); 252 } else { 253 if (BlockLiveness[*FI].Begin.test(Slot)) { 254 // Allocas that start and end within a single block are handled 255 // specially when computing the LiveIntervals to avoid pessimizing 256 // the liveness propagation. 257 BlockLiveness[*FI].Begin.reset(Slot); 258 } else { 259 BlockLiveness[*FI].End.set(Slot); 260 } 261 } 262 } 263 } 264 265 // Update statistics. 266 NumMarkerSeen += MarkersFound; 267 return MarkersFound; 268 } 269 270 void StackColoring::calculateLocalLiveness() { 271 // Perform a standard reverse dataflow computation to solve for 272 // global liveness. The BEGIN set here is equivalent to KILL in the standard 273 // formulation, and END is equivalent to GEN. The result of this computation 274 // is a map from blocks to bitvectors where the bitvectors represent which 275 // allocas are live in/out of that block. 276 SmallPtrSet<MachineBasicBlock*, 8> BBSet(BasicBlockNumbering.begin(), 277 BasicBlockNumbering.end()); 278 unsigned NumSSMIters = 0; 279 bool changed = true; 280 while (changed) { 281 changed = false; 282 ++NumSSMIters; 283 284 SmallPtrSet<MachineBasicBlock*, 8> NextBBSet; 285 286 for (SmallVector<MachineBasicBlock*, 8>::iterator 287 PI = BasicBlockNumbering.begin(), PE = BasicBlockNumbering.end(); 288 PI != PE; ++PI) { 289 290 MachineBasicBlock *BB = *PI; 291 if (!BBSet.count(BB)) continue; 292 293 BitVector LocalLiveIn; 294 BitVector LocalLiveOut; 295 296 // Forward propagation from begins to ends. 297 for (MachineBasicBlock::pred_iterator PI = BB->pred_begin(), 298 PE = BB->pred_end(); PI != PE; ++PI) 299 LocalLiveIn |= BlockLiveness[*PI].LiveOut; 300 LocalLiveIn |= BlockLiveness[BB].End; 301 LocalLiveIn.reset(BlockLiveness[BB].Begin); 302 303 // Reverse propagation from ends to begins. 304 for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(), 305 SE = BB->succ_end(); SI != SE; ++SI) 306 LocalLiveOut |= BlockLiveness[*SI].LiveIn; 307 LocalLiveOut |= BlockLiveness[BB].Begin; 308 LocalLiveOut.reset(BlockLiveness[BB].End); 309 310 LocalLiveIn |= LocalLiveOut; 311 LocalLiveOut |= LocalLiveIn; 312 313 // After adopting the live bits, we need to turn-off the bits which 314 // are de-activated in this block. 315 LocalLiveOut.reset(BlockLiveness[BB].End); 316 LocalLiveIn.reset(BlockLiveness[BB].Begin); 317 318 // If we have both BEGIN and END markers in the same basic block then 319 // we know that the BEGIN marker comes after the END, because we already 320 // handle the case where the BEGIN comes before the END when collecting 321 // the markers (and building the BEGIN/END vectore). 322 // Want to enable the LIVE_IN and LIVE_OUT of slots that have both 323 // BEGIN and END because it means that the value lives before and after 324 // this basic block. 325 BitVector LocalEndBegin = BlockLiveness[BB].End; 326 LocalEndBegin &= BlockLiveness[BB].Begin; 327 LocalLiveIn |= LocalEndBegin; 328 LocalLiveOut |= LocalEndBegin; 329 330 if (LocalLiveIn.test(BlockLiveness[BB].LiveIn)) { 331 changed = true; 332 BlockLiveness[BB].LiveIn |= LocalLiveIn; 333 334 for (MachineBasicBlock::pred_iterator PI = BB->pred_begin(), 335 PE = BB->pred_end(); PI != PE; ++PI) 336 NextBBSet.insert(*PI); 337 } 338 339 if (LocalLiveOut.test(BlockLiveness[BB].LiveOut)) { 340 changed = true; 341 BlockLiveness[BB].LiveOut |= LocalLiveOut; 342 343 for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(), 344 SE = BB->succ_end(); SI != SE; ++SI) 345 NextBBSet.insert(*SI); 346 } 347 } 348 349 BBSet = NextBBSet; 350 }// while changed. 351 } 352 353 void StackColoring::calculateLiveIntervals(unsigned NumSlots) { 354 SmallVector<SlotIndex, 16> Starts; 355 SmallVector<SlotIndex, 16> Finishes; 356 357 // For each block, find which slots are active within this block 358 // and update the live intervals. 359 for (MachineFunction::iterator MBB = MF->begin(), MBBe = MF->end(); 360 MBB != MBBe; ++MBB) { 361 Starts.clear(); 362 Starts.resize(NumSlots); 363 Finishes.clear(); 364 Finishes.resize(NumSlots); 365 366 // Create the interval for the basic blocks with lifetime markers in them. 367 for (SmallVector<MachineInstr*, 8>::iterator it = Markers.begin(), 368 e = Markers.end(); it != e; ++it) { 369 MachineInstr *MI = *it; 370 if (MI->getParent() != MBB) 371 continue; 372 373 assert((MI->getOpcode() == TargetOpcode::LIFETIME_START || 374 MI->getOpcode() == TargetOpcode::LIFETIME_END) && 375 "Invalid Lifetime marker"); 376 377 bool IsStart = MI->getOpcode() == TargetOpcode::LIFETIME_START; 378 MachineOperand &Mo = MI->getOperand(0); 379 int Slot = Mo.getIndex(); 380 assert(Slot >= 0 && "Invalid slot"); 381 382 SlotIndex ThisIndex = Indexes->getInstructionIndex(MI); 383 384 if (IsStart) { 385 if (!Starts[Slot].isValid() || Starts[Slot] > ThisIndex) 386 Starts[Slot] = ThisIndex; 387 } else { 388 if (!Finishes[Slot].isValid() || Finishes[Slot] < ThisIndex) 389 Finishes[Slot] = ThisIndex; 390 } 391 } 392 393 // Create the interval of the blocks that we previously found to be 'alive'. 394 BitVector Alive = BlockLiveness[MBB].LiveIn; 395 Alive |= BlockLiveness[MBB].LiveOut; 396 397 if (Alive.any()) { 398 for (int pos = Alive.find_first(); pos != -1; 399 pos = Alive.find_next(pos)) { 400 if (!Starts[pos].isValid()) 401 Starts[pos] = Indexes->getMBBStartIdx(MBB); 402 if (!Finishes[pos].isValid()) 403 Finishes[pos] = Indexes->getMBBEndIdx(MBB); 404 } 405 } 406 407 for (unsigned i = 0; i < NumSlots; ++i) { 408 assert(Starts[i].isValid() == Finishes[i].isValid() && "Unmatched range"); 409 if (!Starts[i].isValid()) 410 continue; 411 412 assert(Starts[i] && Finishes[i] && "Invalid interval"); 413 VNInfo *ValNum = Intervals[i]->getValNumInfo(0); 414 SlotIndex S = Starts[i]; 415 SlotIndex F = Finishes[i]; 416 if (S < F) { 417 // We have a single consecutive region. 418 Intervals[i]->addRange(LiveRange(S, F, ValNum)); 419 } else { 420 // We have two non consecutive regions. This happens when 421 // LIFETIME_START appears after the LIFETIME_END marker. 422 SlotIndex NewStart = Indexes->getMBBStartIdx(MBB); 423 SlotIndex NewFin = Indexes->getMBBEndIdx(MBB); 424 Intervals[i]->addRange(LiveRange(NewStart, F, ValNum)); 425 Intervals[i]->addRange(LiveRange(S, NewFin, ValNum)); 426 } 427 } 428 } 429 } 430 431 bool StackColoring::removeAllMarkers() { 432 unsigned Count = 0; 433 for (unsigned i = 0; i < Markers.size(); ++i) { 434 Markers[i]->eraseFromParent(); 435 Count++; 436 } 437 Markers.clear(); 438 439 DEBUG(dbgs()<<"Removed "<<Count<<" markers.\n"); 440 return Count; 441 } 442 443 void StackColoring::remapInstructions(DenseMap<int, int> &SlotRemap) { 444 unsigned FixedInstr = 0; 445 unsigned FixedMemOp = 0; 446 unsigned FixedDbg = 0; 447 MachineModuleInfo *MMI = &MF->getMMI(); 448 449 // Remap debug information that refers to stack slots. 450 MachineModuleInfo::VariableDbgInfoMapTy &VMap = MMI->getVariableDbgInfo(); 451 for (MachineModuleInfo::VariableDbgInfoMapTy::iterator VI = VMap.begin(), 452 VE = VMap.end(); VI != VE; ++VI) { 453 const MDNode *Var = VI->first; 454 if (!Var) continue; 455 std::pair<unsigned, DebugLoc> &VP = VI->second; 456 if (SlotRemap.count(VP.first)) { 457 DEBUG(dbgs()<<"Remapping debug info for ["<<Var->getName()<<"].\n"); 458 VP.first = SlotRemap[VP.first]; 459 FixedDbg++; 460 } 461 } 462 463 // Keep a list of *allocas* which need to be remapped. 464 DenseMap<const Value*, const Value*> Allocas; 465 for (DenseMap<int, int>::iterator it = SlotRemap.begin(), 466 e = SlotRemap.end(); it != e; ++it) { 467 const Value *From = MFI->getObjectAllocation(it->first); 468 const Value *To = MFI->getObjectAllocation(it->second); 469 assert(To && From && "Invalid allocation object"); 470 Allocas[From] = To; 471 } 472 473 // Remap all instructions to the new stack slots. 474 MachineFunction::iterator BB, BBE; 475 MachineBasicBlock::iterator I, IE; 476 for (BB = MF->begin(), BBE = MF->end(); BB != BBE; ++BB) 477 for (I = BB->begin(), IE = BB->end(); I != IE; ++I) { 478 479 // Skip lifetime markers. We'll remove them soon. 480 if (I->getOpcode() == TargetOpcode::LIFETIME_START || 481 I->getOpcode() == TargetOpcode::LIFETIME_END) 482 continue; 483 484 // Update the MachineMemOperand to use the new alloca. 485 for (MachineInstr::mmo_iterator MM = I->memoperands_begin(), 486 E = I->memoperands_end(); MM != E; ++MM) { 487 MachineMemOperand *MMO = *MM; 488 489 const Value *V = MMO->getValue(); 490 491 if (!V) 492 continue; 493 494 // Climb up and find the original alloca. 495 V = GetUnderlyingObject(V); 496 // If we did not find one, or if the one that we found is not in our 497 // map, then move on. 498 if (!V || !Allocas.count(V)) 499 continue; 500 501 MMO->setValue(Allocas[V]); 502 FixedMemOp++; 503 } 504 505 // Update all of the machine instruction operands. 506 for (unsigned i = 0 ; i < I->getNumOperands(); ++i) { 507 MachineOperand &MO = I->getOperand(i); 508 509 if (!MO.isFI()) 510 continue; 511 int FromSlot = MO.getIndex(); 512 513 // Don't touch arguments. 514 if (FromSlot<0) 515 continue; 516 517 // Only look at mapped slots. 518 if (!SlotRemap.count(FromSlot)) 519 continue; 520 521 // In a debug build, check that the instruction that we are modifying is 522 // inside the expected live range. If the instruction is not inside 523 // the calculated range then it means that the alloca usage moved 524 // outside of the lifetime markers. 525 #ifndef NDEBUG 526 SlotIndex Index = Indexes->getInstructionIndex(I); 527 LiveInterval* Interval = Intervals[FromSlot]; 528 assert(Interval->find(Index) != Interval->end() && 529 "Found instruction usage outside of live range."); 530 #endif 531 532 // Fix the machine instructions. 533 int ToSlot = SlotRemap[FromSlot]; 534 MO.setIndex(ToSlot); 535 FixedInstr++; 536 } 537 } 538 539 DEBUG(dbgs()<<"Fixed "<<FixedMemOp<<" machine memory operands.\n"); 540 DEBUG(dbgs()<<"Fixed "<<FixedDbg<<" debug locations.\n"); 541 DEBUG(dbgs()<<"Fixed "<<FixedInstr<<" machine instructions.\n"); 542 } 543 544 void StackColoring::expungeSlotMap(DenseMap<int, int> &SlotRemap, 545 unsigned NumSlots) { 546 // Expunge slot remap map. 547 for (unsigned i=0; i < NumSlots; ++i) { 548 // If we are remapping i 549 if (SlotRemap.count(i)) { 550 int Target = SlotRemap[i]; 551 // As long as our target is mapped to something else, follow it. 552 while (SlotRemap.count(Target)) { 553 Target = SlotRemap[Target]; 554 SlotRemap[i] = Target; 555 } 556 } 557 } 558 } 559 560 bool StackColoring::runOnMachineFunction(MachineFunction &Func) { 561 DEBUG(dbgs() << "********** Stack Coloring **********\n" 562 << "********** Function: " 563 << ((const Value*)Func.getFunction())->getName() << '\n'); 564 MF = &Func; 565 MFI = MF->getFrameInfo(); 566 Indexes = &getAnalysis<SlotIndexes>(); 567 BlockLiveness.clear(); 568 BasicBlocks.clear(); 569 BasicBlockNumbering.clear(); 570 Markers.clear(); 571 Intervals.clear(); 572 VNInfoAllocator.Reset(); 573 574 unsigned NumSlots = MFI->getObjectIndexEnd(); 575 576 // If there are no stack slots then there are no markers to remove. 577 if (!NumSlots) 578 return false; 579 580 SmallVector<int, 8> SortedSlots; 581 582 SortedSlots.reserve(NumSlots); 583 Intervals.reserve(NumSlots); 584 585 unsigned NumMarkers = collectMarkers(NumSlots); 586 587 unsigned TotalSize = 0; 588 DEBUG(dbgs()<<"Found "<<NumMarkers<<" markers and "<<NumSlots<<" slots\n"); 589 DEBUG(dbgs()<<"Slot structure:\n"); 590 591 for (int i=0; i < MFI->getObjectIndexEnd(); ++i) { 592 DEBUG(dbgs()<<"Slot #"<<i<<" - "<<MFI->getObjectSize(i)<<" bytes.\n"); 593 TotalSize += MFI->getObjectSize(i); 594 } 595 596 DEBUG(dbgs()<<"Total Stack size: "<<TotalSize<<" bytes\n\n"); 597 598 // Don't continue because there are not enough lifetime markers, or the 599 // stack or too small, or we are told not to optimize the slots. 600 if (NumMarkers < 2 || TotalSize < 16 || DisableColoring) { 601 DEBUG(dbgs()<<"Will not try to merge slots.\n"); 602 return removeAllMarkers(); 603 } 604 605 for (unsigned i=0; i < NumSlots; ++i) { 606 LiveInterval *LI = new LiveInterval(i, 0); 607 Intervals.push_back(LI); 608 LI->getNextValue(Indexes->getZeroIndex(), VNInfoAllocator); 609 SortedSlots.push_back(i); 610 } 611 612 // Calculate the liveness of each block. 613 calculateLocalLiveness(); 614 615 // Propagate the liveness information. 616 calculateLiveIntervals(NumSlots); 617 618 // Maps old slots to new slots. 619 DenseMap<int, int> SlotRemap; 620 unsigned RemovedSlots = 0; 621 unsigned ReducedSize = 0; 622 623 // Do not bother looking at empty intervals. 624 for (unsigned I = 0; I < NumSlots; ++I) { 625 if (Intervals[SortedSlots[I]]->empty()) 626 SortedSlots[I] = -1; 627 } 628 629 // This is a simple greedy algorithm for merging allocas. First, sort the 630 // slots, placing the largest slots first. Next, perform an n^2 scan and look 631 // for disjoint slots. When you find disjoint slots, merge the samller one 632 // into the bigger one and update the live interval. Remove the small alloca 633 // and continue. 634 635 // Sort the slots according to their size. Place unused slots at the end. 636 std::sort(SortedSlots.begin(), SortedSlots.end(), SlotSizeSorter(MFI)); 637 638 bool Chanded = true; 639 while (Chanded) { 640 Chanded = false; 641 for (unsigned I = 0; I < NumSlots; ++I) { 642 if (SortedSlots[I] == -1) 643 continue; 644 645 for (unsigned J=I+1; J < NumSlots; ++J) { 646 if (SortedSlots[J] == -1) 647 continue; 648 649 int FirstSlot = SortedSlots[I]; 650 int SecondSlot = SortedSlots[J]; 651 LiveInterval *First = Intervals[FirstSlot]; 652 LiveInterval *Second = Intervals[SecondSlot]; 653 assert (!First->empty() && !Second->empty() && "Found an empty range"); 654 655 // Merge disjoint slots. 656 if (!First->overlaps(*Second)) { 657 Chanded = true; 658 First->MergeRangesInAsValue(*Second, First->getValNumInfo(0)); 659 SlotRemap[SecondSlot] = FirstSlot; 660 SortedSlots[J] = -1; 661 DEBUG(dbgs()<<"Merging #"<<FirstSlot<<" and slots #"<< 662 SecondSlot<<" together.\n"); 663 unsigned MaxAlignment = std::max(MFI->getObjectAlignment(FirstSlot), 664 MFI->getObjectAlignment(SecondSlot)); 665 666 assert(MFI->getObjectSize(FirstSlot) >= 667 MFI->getObjectSize(SecondSlot) && 668 "Merging a small object into a larger one"); 669 670 RemovedSlots+=1; 671 ReducedSize += MFI->getObjectSize(SecondSlot); 672 MFI->setObjectAlignment(FirstSlot, MaxAlignment); 673 MFI->RemoveStackObject(SecondSlot); 674 } 675 } 676 } 677 }// While changed. 678 679 // Record statistics. 680 StackSpaceSaved += ReducedSize; 681 StackSlotMerged += RemovedSlots; 682 DEBUG(dbgs()<<"Merge "<<RemovedSlots<<" slots. Saved "<< 683 ReducedSize<<" bytes\n"); 684 685 // Scan the entire function and update all machine operands that use frame 686 // indices to use the remapped frame index. 687 expungeSlotMap(SlotRemap, NumSlots); 688 remapInstructions(SlotRemap); 689 690 // Release the intervals. 691 for (unsigned I = 0; I < NumSlots; ++I) { 692 delete Intervals[I]; 693 } 694 695 return removeAllMarkers(); 696 } 697