StackColoring.cpp revision 79cb162e5d7aeaa3602bf4a7afa253232f461b33
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 58using namespace llvm; 59 60static cl::opt<bool> 61DisableColoring("no-stack-coloring", 62 cl::init(true), cl::Hidden, 63 cl::desc("Suppress stack coloring")); 64 65STATISTIC(NumMarkerSeen, "Number of life markers found."); 66STATISTIC(StackSpaceSaved, "Number of bytes saved due to merging slots."); 67STATISTIC(StackSlotMerged, "Number of stack slot merged."); 68 69//===----------------------------------------------------------------------===// 70// StackColoring Pass 71//===----------------------------------------------------------------------===// 72 73namespace { 74/// StackColoring - A machine pass for merging disjoint stack allocations, 75/// marked by the LIFETIME_START and LIFETIME_END pseudo instructions. 76class 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 127public: 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 135private: 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 167char StackColoring::ID = 0; 168char &llvm::StackColoringID = StackColoring::ID; 169 170INITIALIZE_PASS_BEGIN(StackColoring, 171 "stack-coloring", "Merge disjoint stack slots", false, false) 172INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 173INITIALIZE_PASS_DEPENDENCY(SlotIndexes) 174INITIALIZE_PASS_END(StackColoring, 175 "stack-coloring", "Merge disjoint stack slots", false, false) 176 177void StackColoring::getAnalysisUsage(AnalysisUsage &AU) const { 178 AU.addRequired<MachineDominatorTree>(); 179 AU.addPreserved<MachineDominatorTree>(); 180 AU.addRequired<SlotIndexes>(); 181 MachineFunctionPass::getAnalysisUsage(AU); 182} 183 184void 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 213unsigned 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 270void 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 (LocalLiveIn.test(BlockLiveness[BB].LiveIn)) { 319 changed = true; 320 BlockLiveness[BB].LiveIn |= LocalLiveIn; 321 322 for (MachineBasicBlock::pred_iterator PI = BB->pred_begin(), 323 PE = BB->pred_end(); PI != PE; ++PI) 324 NextBBSet.insert(*PI); 325 } 326 327 if (LocalLiveOut.test(BlockLiveness[BB].LiveOut)) { 328 changed = true; 329 BlockLiveness[BB].LiveOut |= LocalLiveOut; 330 331 for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(), 332 SE = BB->succ_end(); SI != SE; ++SI) 333 NextBBSet.insert(*SI); 334 } 335 } 336 337 BBSet = NextBBSet; 338 }// while changed. 339} 340 341void StackColoring::calculateLiveIntervals(unsigned NumSlots) { 342 SmallVector<SlotIndex, 16> Starts; 343 SmallVector<SlotIndex, 16> Finishes; 344 345 // For each block, find which slots are active within this block 346 // and update the live intervals. 347 for (MachineFunction::iterator MBB = MF->begin(), MBBe = MF->end(); 348 MBB != MBBe; ++MBB) { 349 Starts.clear(); 350 Starts.resize(NumSlots); 351 Finishes.clear(); 352 Finishes.resize(NumSlots); 353 354 BitVector Alive = BlockLiveness[MBB].LiveIn; 355 Alive |= BlockLiveness[MBB].LiveOut; 356 357 if (Alive.any()) { 358 for (int pos = Alive.find_first(); pos != -1; 359 pos = Alive.find_next(pos)) { 360 Starts[pos] = Indexes->getMBBStartIdx(MBB); 361 Finishes[pos] = Indexes->getMBBEndIdx(MBB); 362 } 363 } 364 365 for (SmallVector<MachineInstr*, 8>::iterator it = Markers.begin(), 366 e = Markers.end(); it != e; ++it) { 367 MachineInstr *MI = *it; 368 assert((MI->getOpcode() == TargetOpcode::LIFETIME_START || 369 MI->getOpcode() == TargetOpcode::LIFETIME_END) && 370 "Invalid Lifetime marker"); 371 372 if (MI->getParent() == MBB) { 373 bool IsStart = MI->getOpcode() == TargetOpcode::LIFETIME_START; 374 MachineOperand &Mo = MI->getOperand(0); 375 int Slot = Mo.getIndex(); 376 assert(Slot >= 0 && "Invalid slot"); 377 if (IsStart) { 378 Starts[Slot] = Indexes->getInstructionIndex(MI); 379 } else { 380 Finishes[Slot] = Indexes->getInstructionIndex(MI); 381 } 382 } 383 } 384 385 for (unsigned i = 0; i < NumSlots; ++i) { 386 assert(!!Starts[i] == !!Finishes[i] && "Unmatched range"); 387 if (Starts[i] == Finishes[i]) 388 continue; 389 390 assert(Starts[i] && Finishes[i] && "Invalid interval"); 391 VNInfo *ValNum = Intervals[i]->getValNumInfo(0); 392 SlotIndex S = Starts[i]; 393 SlotIndex F = Finishes[i]; 394 if (S < F) { 395 // We have a single consecutive region. 396 Intervals[i]->addRange(LiveRange(S, F, ValNum)); 397 } else { 398 // We have two non consecutive regions. This happens when 399 // LIFETIME_START appears after the LIFETIME_END marker. 400 SlotIndex NewStart = Indexes->getMBBStartIdx(MBB); 401 SlotIndex NewFin = Indexes->getMBBEndIdx(MBB); 402 Intervals[i]->addRange(LiveRange(NewStart, F, ValNum)); 403 Intervals[i]->addRange(LiveRange(S, NewFin, ValNum)); 404 } 405 } 406 } 407} 408 409bool StackColoring::removeAllMarkers() { 410 unsigned Count = 0; 411 for (unsigned i = 0; i < Markers.size(); ++i) { 412 Markers[i]->eraseFromParent(); 413 Count++; 414 } 415 Markers.clear(); 416 417 DEBUG(dbgs()<<"Removed "<<Count<<" markers.\n"); 418 return Count; 419} 420 421void StackColoring::remapInstructions(DenseMap<int, int> &SlotRemap) { 422 unsigned FixedInstr = 0; 423 unsigned FixedMemOp = 0; 424 unsigned FixedDbg = 0; 425 MachineModuleInfo *MMI = &MF->getMMI(); 426 427 // Remap debug information that refers to stack slots. 428 MachineModuleInfo::VariableDbgInfoMapTy &VMap = MMI->getVariableDbgInfo(); 429 for (MachineModuleInfo::VariableDbgInfoMapTy::iterator VI = VMap.begin(), 430 VE = VMap.end(); VI != VE; ++VI) { 431 const MDNode *Var = VI->first; 432 if (!Var) continue; 433 std::pair<unsigned, DebugLoc> &VP = VI->second; 434 if (SlotRemap.count(VP.first)) { 435 DEBUG(dbgs()<<"Remapping debug info for ["<<Var->getName()<<"].\n"); 436 VP.first = SlotRemap[VP.first]; 437 FixedDbg++; 438 } 439 } 440 441 // Keep a list of *allocas* which need to be remapped. 442 DenseMap<const Value*, const Value*> Allocas; 443 for (DenseMap<int, int>::iterator it = SlotRemap.begin(), 444 e = SlotRemap.end(); it != e; ++it) { 445 const Value* From = MFI->getObjectAllocation(it->first); 446 const Value* To = MFI->getObjectAllocation(it->second); 447 assert(To && From && "Invalid allocation object"); 448 Allocas[From] = To; 449 } 450 451 // Remap all instructions to the new stack slots. 452 MachineFunction::iterator BB, BBE; 453 MachineBasicBlock::iterator I, IE; 454 for (BB = MF->begin(), BBE = MF->end(); BB != BBE; ++BB) 455 for (I = BB->begin(), IE = BB->end(); I != IE; ++I) { 456 457 // Update the MachineMemOperand to use the new alloca. 458 for (MachineInstr::mmo_iterator MM = I->memoperands_begin(), 459 E = I->memoperands_end(); MM != E; ++MM) { 460 MachineMemOperand *MMO = *MM; 461 462 const Value *V = MMO->getValue(); 463 464 if (!V) 465 continue; 466 467 // Climb up and find the original alloca. 468 V = GetUnderlyingObject(V); 469 // If we did not find one, or if the one that we found is not in our 470 // map, then move on. 471 if (!V || !Allocas.count(V)) 472 continue; 473 474 MMO->setValue(Allocas[V]); 475 FixedMemOp++; 476 } 477 478 // Update all of the machine instruction operands. 479 for (unsigned i = 0 ; i < I->getNumOperands(); ++i) { 480 MachineOperand &MO = I->getOperand(i); 481 482 if (!MO.isFI()) 483 continue; 484 int FromSlot = MO.getIndex(); 485 486 // Don't touch arguments. 487 if (FromSlot<0) 488 continue; 489 490 // Only look at mapped slots. 491 if (!SlotRemap.count(FromSlot)) 492 continue; 493 494 // Fix the machine instructions. 495 int ToSlot = SlotRemap[FromSlot]; 496 MO.setIndex(ToSlot); 497 FixedInstr++; 498 } 499 } 500 501 DEBUG(dbgs()<<"Fixed "<<FixedMemOp<<" machine memory operands.\n"); 502 DEBUG(dbgs()<<"Fixed "<<FixedDbg<<" debug locations.\n"); 503 DEBUG(dbgs()<<"Fixed "<<FixedInstr<<" machine instructions.\n"); 504} 505 506void StackColoring::expungeSlotMap(DenseMap<int, int> &SlotRemap, 507 unsigned NumSlots) { 508 // Expunge slot remap map. 509 for (unsigned i=0; i < NumSlots; ++i) { 510 // If we are remapping i 511 if (SlotRemap.count(i)) { 512 int Target = SlotRemap[i]; 513 // As long as our target is mapped to something else, follow it. 514 while (SlotRemap.count(Target)) { 515 Target = SlotRemap[Target]; 516 SlotRemap[i] = Target; 517 } 518 } 519 } 520} 521 522bool StackColoring::runOnMachineFunction(MachineFunction &Func) { 523 DEBUG(dbgs() << "********** Stack Coloring **********\n" 524 << "********** Function: " 525 << ((Value*)Func.getFunction())->getName() << '\n'); 526 MF = &Func; 527 MFI = MF->getFrameInfo(); 528 Indexes = &getAnalysis<SlotIndexes>(); 529 BlockLiveness.clear(); 530 BasicBlocks.clear(); 531 BasicBlockNumbering.clear(); 532 Markers.clear(); 533 Intervals.clear(); 534 VNInfoAllocator.Reset(); 535 536 unsigned NumSlots = MFI->getObjectIndexEnd(); 537 538 // If there are no stack slots then there are no markers to remove. 539 if (!NumSlots) 540 return false; 541 542 SmallVector<int, 8> SortedSlots; 543 544 SortedSlots.reserve(NumSlots); 545 Intervals.reserve(NumSlots); 546 547 unsigned NumMarkers = collectMarkers(NumSlots); 548 549 unsigned TotalSize = 0; 550 DEBUG(dbgs()<<"Found "<<NumMarkers<<" markers and "<<NumSlots<<" slots\n"); 551 DEBUG(dbgs()<<"Slot structure:\n"); 552 553 for (int i=0; i < MFI->getObjectIndexEnd(); ++i) { 554 DEBUG(dbgs()<<"Slot #"<<i<<" - "<<MFI->getObjectSize(i)<<" bytes.\n"); 555 TotalSize += MFI->getObjectSize(i); 556 } 557 558 DEBUG(dbgs()<<"Total Stack size: "<<TotalSize<<" bytes\n\n"); 559 560 // Don't continue because there are not enough lifetime markers, or the 561 // stack or too small, or we are told not to optimize the slots. 562 if (NumMarkers < 2 || TotalSize < 16 || DisableColoring) { 563 DEBUG(dbgs()<<"Will not try to merge slots.\n"); 564 return removeAllMarkers(); 565 } 566 567 for (unsigned i=0; i < NumSlots; ++i) { 568 LiveInterval *LI = new LiveInterval(i, 0); 569 Intervals.push_back(LI); 570 LI->getNextValue(Indexes->getZeroIndex(), VNInfoAllocator); 571 SortedSlots.push_back(i); 572 } 573 574 // Calculate the liveness of each block. 575 calculateLocalLiveness(); 576 577 // Propagate the liveness information. 578 calculateLiveIntervals(NumSlots); 579 580 // Maps old slots to new slots. 581 DenseMap<int, int> SlotRemap; 582 unsigned RemovedSlots = 0; 583 unsigned ReducedSize = 0; 584 585 // Do not bother looking at empty intervals. 586 for (unsigned I = 0; I < NumSlots; ++I) { 587 if (Intervals[SortedSlots[I]]->empty()) 588 SortedSlots[I] = -1; 589 } 590 591 // This is a simple greedy algorithm for merging allocas. First, sort the 592 // slots, placing the largest slots first. Next, perform an n^2 scan and look 593 // for disjoint slots. When you find disjoint slots, merge the samller one 594 // into the bigger one and update the live interval. Remove the small alloca 595 // and continue. 596 597 // Sort the slots according to their size. Place unused slots at the end. 598 std::sort(SortedSlots.begin(), SortedSlots.end(), SlotSizeSorter(MFI)); 599 600 bool Chanded = true; 601 while (Chanded) { 602 Chanded = false; 603 for (unsigned I = 0; I < NumSlots; ++I) { 604 if (SortedSlots[I] == -1) 605 continue; 606 607 for (unsigned J=0; J < NumSlots; ++J) { 608 if (SortedSlots[J] == -1) 609 continue; 610 611 int FirstSlot = SortedSlots[I]; 612 int SecondSlot = SortedSlots[J]; 613 LiveInterval *First = Intervals[FirstSlot]; 614 LiveInterval *Second = Intervals[SecondSlot]; 615 assert (!First->empty() && !Second->empty() && "Found an empty range"); 616 617 // Merge disjoint slots. 618 if (!First->overlaps(*Second)) { 619 Chanded = true; 620 First->MergeRangesInAsValue(*Second, First->getValNumInfo(0)); 621 SlotRemap[SecondSlot] = FirstSlot; 622 SortedSlots[J] = -1; 623 DEBUG(dbgs()<<"Merging #"<<I<<" and slots #"<<J<<" together.\n"); 624 unsigned MaxAlignment = std::max(MFI->getObjectAlignment(FirstSlot), 625 MFI->getObjectAlignment(SecondSlot)); 626 627 assert(MFI->getObjectSize(FirstSlot) >= 628 MFI->getObjectSize(SecondSlot) && 629 "Merging a small object into a larger one"); 630 631 RemovedSlots+=1; 632 ReducedSize += MFI->getObjectSize(SecondSlot); 633 MFI->setObjectAlignment(FirstSlot, MaxAlignment); 634 MFI->RemoveStackObject(SecondSlot); 635 } 636 } 637 } 638 }// While changed. 639 640 // Record statistics. 641 StackSpaceSaved += ReducedSize; 642 StackSlotMerged += RemovedSlots; 643 DEBUG(dbgs()<<"Merge "<<RemovedSlots<<" slots. Saved "<< 644 ReducedSize<<" bytes\n"); 645 646 // Scan the entire function and update all machine operands that use frame 647 // indices to use the remapped frame index. 648 expungeSlotMap(SlotRemap, NumSlots); 649 remapInstructions(SlotRemap); 650 651 // Release the intervals. 652 for (unsigned I = 0; I < NumSlots; ++I) { 653 delete Intervals[I]; 654 } 655 656 return removeAllMarkers(); 657} 658