1 //===-- StackColoring.cpp -------------------------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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.
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
19 // 2. Merge this pass with StackSlotColoring and allow merging of allocas with
22 //===----------------------------------------------------------------------===//
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"
61 DisableColoring("no-stack-coloring",
62 cl::init(true), cl::Hidden,
63 cl::desc("Suppress stack coloring"));
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.");
69 //===----------------------------------------------------------------------===//
71 //===----------------------------------------------------------------------===//
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;
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.
86 /// Which slots ENDs in each basic block.
88 /// Which slots are marked as LIVE_IN, coming into each basic block.
90 /// Which slots are marked as LIVE_OUT, coming out of each basic block.
94 /// Maps active slots (per bit) for each basic block.
95 DenseMap<MachineBasicBlock*, BlockLifetimeInfo> BlockLiveness;
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;
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;
109 /// The list of lifetime markers found. These markers are to be removed
110 /// once the coloring is done.
111 SmallVector<MachineInstr*, 8> Markers;
113 /// SlotSizeSorter - A Sort utility for arranging stack slots according
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);
129 StackColoring() : MachineFunctionPass(ID) {
130 initializeStackColoringPass(*PassRegistry::getPassRegistry());
132 void getAnalysisUsage(AnalysisUsage &AU) const;
133 bool runOnMachineFunction(MachineFunction &MF);
139 /// Removes all of the lifetime marker instructions from the function.
140 /// \returns true if any markers were removed.
141 bool removeAllMarkers();
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);
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();
154 /// Construct the LiveIntervals for the slots.
155 void calculateLiveIntervals(unsigned NumSlots);
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);
161 /// The input program may contain intructions which are not inside lifetime
162 /// markers. This can happen due to a bug in the compiler or due to a bug in
163 /// user code (for example, returning a reference to a local variable).
164 /// This procedure checks all of the instructions in the function and
165 /// invalidates lifetime ranges which do not contain all of the instructions
166 /// which access that frame slot.
167 void removeInvalidSlotRanges();
169 /// Map entries which point to other entries to their destination.
170 /// A->B->C becomes A->C.
171 void expungeSlotMap(DenseMap<int, int> &SlotRemap, unsigned NumSlots);
173 } // end anonymous namespace
175 char StackColoring::ID = 0;
176 char &llvm::StackColoringID = StackColoring::ID;
178 INITIALIZE_PASS_BEGIN(StackColoring,
179 "stack-coloring", "Merge disjoint stack slots", false, false)
180 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
181 INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
182 INITIALIZE_PASS_END(StackColoring,
183 "stack-coloring", "Merge disjoint stack slots", false, false)
185 void StackColoring::getAnalysisUsage(AnalysisUsage &AU) const {
186 AU.addRequired<MachineDominatorTree>();
187 AU.addPreserved<MachineDominatorTree>();
188 AU.addRequired<SlotIndexes>();
189 MachineFunctionPass::getAnalysisUsage(AU);
192 void StackColoring::dump() {
193 for (df_iterator<MachineFunction*> FI = df_begin(MF), FE = df_end(MF);
195 unsigned Num = BasicBlocks[*FI];
196 DEBUG(dbgs()<<"Inspecting block #"<<Num<<" ["<<FI->getName()<<"]\n");
198 DEBUG(dbgs()<<"BEGIN : {");
199 for (unsigned i=0; i < BlockLiveness[*FI].Begin.size(); ++i)
200 DEBUG(dbgs()<<BlockLiveness[*FI].Begin.test(i)<<" ");
201 DEBUG(dbgs()<<"}\n");
203 DEBUG(dbgs()<<"END : {");
204 for (unsigned i=0; i < BlockLiveness[*FI].End.size(); ++i)
205 DEBUG(dbgs()<<BlockLiveness[*FI].End.test(i)<<" ");
207 DEBUG(dbgs()<<"}\n");
209 DEBUG(dbgs()<<"LIVE_IN: {");
210 for (unsigned i=0; i < BlockLiveness[*FI].LiveIn.size(); ++i)
211 DEBUG(dbgs()<<BlockLiveness[*FI].LiveIn.test(i)<<" ");
213 DEBUG(dbgs()<<"}\n");
214 DEBUG(dbgs()<<"LIVEOUT: {");
215 for (unsigned i=0; i < BlockLiveness[*FI].LiveOut.size(); ++i)
216 DEBUG(dbgs()<<BlockLiveness[*FI].LiveOut.test(i)<<" ");
217 DEBUG(dbgs()<<"}\n");
221 unsigned StackColoring::collectMarkers(unsigned NumSlot) {
222 unsigned MarkersFound = 0;
223 // Scan the function to find all lifetime markers.
224 // NOTE: We use the a reverse-post-order iteration to ensure that we obtain a
225 // deterministic numbering, and because we'll need a post-order iteration
226 // later for solving the liveness dataflow problem.
227 for (df_iterator<MachineFunction*> FI = df_begin(MF), FE = df_end(MF);
230 // Assign a serial number to this basic block.
231 BasicBlocks[*FI] = BasicBlockNumbering.size();
232 BasicBlockNumbering.push_back(*FI);
234 BlockLiveness[*FI].Begin.resize(NumSlot);
235 BlockLiveness[*FI].End.resize(NumSlot);
237 for (MachineBasicBlock::iterator BI = (*FI)->begin(), BE = (*FI)->end();
240 if (BI->getOpcode() != TargetOpcode::LIFETIME_START &&
241 BI->getOpcode() != TargetOpcode::LIFETIME_END)
244 Markers.push_back(BI);
246 bool IsStart = BI->getOpcode() == TargetOpcode::LIFETIME_START;
247 MachineOperand &MI = BI->getOperand(0);
248 unsigned Slot = MI.getIndex();
252 const Value *Allocation = MFI->getObjectAllocation(Slot);
254 DEBUG(dbgs()<<"Found lifetime marker for allocation: "<<
255 Allocation->getName()<<"\n");
259 BlockLiveness[*FI].Begin.set(Slot);
261 if (BlockLiveness[*FI].Begin.test(Slot)) {
262 // Allocas that start and end within a single block are handled
263 // specially when computing the LiveIntervals to avoid pessimizing
264 // the liveness propagation.
265 BlockLiveness[*FI].Begin.reset(Slot);
267 BlockLiveness[*FI].End.set(Slot);
273 // Update statistics.
274 NumMarkerSeen += MarkersFound;
278 void StackColoring::calculateLocalLiveness() {
279 // Perform a standard reverse dataflow computation to solve for
280 // global liveness. The BEGIN set here is equivalent to KILL in the standard
281 // formulation, and END is equivalent to GEN. The result of this computation
282 // is a map from blocks to bitvectors where the bitvectors represent which
283 // allocas are live in/out of that block.
284 SmallPtrSet<MachineBasicBlock*, 8> BBSet(BasicBlockNumbering.begin(),
285 BasicBlockNumbering.end());
286 unsigned NumSSMIters = 0;
292 SmallPtrSet<MachineBasicBlock*, 8> NextBBSet;
294 for (SmallVector<MachineBasicBlock*, 8>::iterator
295 PI = BasicBlockNumbering.begin(), PE = BasicBlockNumbering.end();
298 MachineBasicBlock *BB = *PI;
299 if (!BBSet.count(BB)) continue;
301 BitVector LocalLiveIn;
302 BitVector LocalLiveOut;
304 // Forward propagation from begins to ends.
305 for (MachineBasicBlock::pred_iterator PI = BB->pred_begin(),
306 PE = BB->pred_end(); PI != PE; ++PI)
307 LocalLiveIn |= BlockLiveness[*PI].LiveOut;
308 LocalLiveIn |= BlockLiveness[BB].End;
309 LocalLiveIn.reset(BlockLiveness[BB].Begin);
311 // Reverse propagation from ends to begins.
312 for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(),
313 SE = BB->succ_end(); SI != SE; ++SI)
314 LocalLiveOut |= BlockLiveness[*SI].LiveIn;
315 LocalLiveOut |= BlockLiveness[BB].Begin;
316 LocalLiveOut.reset(BlockLiveness[BB].End);
318 LocalLiveIn |= LocalLiveOut;
319 LocalLiveOut |= LocalLiveIn;
321 // After adopting the live bits, we need to turn-off the bits which
322 // are de-activated in this block.
323 LocalLiveOut.reset(BlockLiveness[BB].End);
324 LocalLiveIn.reset(BlockLiveness[BB].Begin);
326 // If we have both BEGIN and END markers in the same basic block then
327 // we know that the BEGIN marker comes after the END, because we already
328 // handle the case where the BEGIN comes before the END when collecting
329 // the markers (and building the BEGIN/END vectore).
330 // Want to enable the LIVE_IN and LIVE_OUT of slots that have both
331 // BEGIN and END because it means that the value lives before and after
333 BitVector LocalEndBegin = BlockLiveness[BB].End;
334 LocalEndBegin &= BlockLiveness[BB].Begin;
335 LocalLiveIn |= LocalEndBegin;
336 LocalLiveOut |= LocalEndBegin;
338 if (LocalLiveIn.test(BlockLiveness[BB].LiveIn)) {
340 BlockLiveness[BB].LiveIn |= LocalLiveIn;
342 for (MachineBasicBlock::pred_iterator PI = BB->pred_begin(),
343 PE = BB->pred_end(); PI != PE; ++PI)
344 NextBBSet.insert(*PI);
347 if (LocalLiveOut.test(BlockLiveness[BB].LiveOut)) {
349 BlockLiveness[BB].LiveOut |= LocalLiveOut;
351 for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(),
352 SE = BB->succ_end(); SI != SE; ++SI)
353 NextBBSet.insert(*SI);
361 void StackColoring::calculateLiveIntervals(unsigned NumSlots) {
362 SmallVector<SlotIndex, 16> Starts;
363 SmallVector<SlotIndex, 16> Finishes;
365 // For each block, find which slots are active within this block
366 // and update the live intervals.
367 for (MachineFunction::iterator MBB = MF->begin(), MBBe = MF->end();
368 MBB != MBBe; ++MBB) {
370 Starts.resize(NumSlots);
372 Finishes.resize(NumSlots);
374 // Create the interval for the basic blocks with lifetime markers in them.
375 for (SmallVector<MachineInstr*, 8>::iterator it = Markers.begin(),
376 e = Markers.end(); it != e; ++it) {
377 MachineInstr *MI = *it;
378 if (MI->getParent() != MBB)
381 assert((MI->getOpcode() == TargetOpcode::LIFETIME_START ||
382 MI->getOpcode() == TargetOpcode::LIFETIME_END) &&
383 "Invalid Lifetime marker");
385 bool IsStart = MI->getOpcode() == TargetOpcode::LIFETIME_START;
386 MachineOperand &Mo = MI->getOperand(0);
387 int Slot = Mo.getIndex();
388 assert(Slot >= 0 && "Invalid slot");
390 SlotIndex ThisIndex = Indexes->getInstructionIndex(MI);
393 if (!Starts[Slot].isValid() || Starts[Slot] > ThisIndex)
394 Starts[Slot] = ThisIndex;
396 if (!Finishes[Slot].isValid() || Finishes[Slot] < ThisIndex)
397 Finishes[Slot] = ThisIndex;
401 // Create the interval of the blocks that we previously found to be 'alive'.
402 BitVector Alive = BlockLiveness[MBB].LiveIn;
403 Alive |= BlockLiveness[MBB].LiveOut;
406 for (int pos = Alive.find_first(); pos != -1;
407 pos = Alive.find_next(pos)) {
408 if (!Starts[pos].isValid())
409 Starts[pos] = Indexes->getMBBStartIdx(MBB);
410 if (!Finishes[pos].isValid())
411 Finishes[pos] = Indexes->getMBBEndIdx(MBB);
415 for (unsigned i = 0; i < NumSlots; ++i) {
416 assert(Starts[i].isValid() == Finishes[i].isValid() && "Unmatched range");
417 if (!Starts[i].isValid())
420 assert(Starts[i] && Finishes[i] && "Invalid interval");
421 VNInfo *ValNum = Intervals[i]->getValNumInfo(0);
422 SlotIndex S = Starts[i];
423 SlotIndex F = Finishes[i];
425 // We have a single consecutive region.
426 Intervals[i]->addRange(LiveRange(S, F, ValNum));
428 // We have two non consecutive regions. This happens when
429 // LIFETIME_START appears after the LIFETIME_END marker.
430 SlotIndex NewStart = Indexes->getMBBStartIdx(MBB);
431 SlotIndex NewFin = Indexes->getMBBEndIdx(MBB);
432 Intervals[i]->addRange(LiveRange(NewStart, F, ValNum));
433 Intervals[i]->addRange(LiveRange(S, NewFin, ValNum));
439 bool StackColoring::removeAllMarkers() {
441 for (unsigned i = 0; i < Markers.size(); ++i) {
442 Markers[i]->eraseFromParent();
447 DEBUG(dbgs()<<"Removed "<<Count<<" markers.\n");
451 void StackColoring::remapInstructions(DenseMap<int, int> &SlotRemap) {
452 unsigned FixedInstr = 0;
453 unsigned FixedMemOp = 0;
454 unsigned FixedDbg = 0;
455 MachineModuleInfo *MMI = &MF->getMMI();
457 // Remap debug information that refers to stack slots.
458 MachineModuleInfo::VariableDbgInfoMapTy &VMap = MMI->getVariableDbgInfo();
459 for (MachineModuleInfo::VariableDbgInfoMapTy::iterator VI = VMap.begin(),
460 VE = VMap.end(); VI != VE; ++VI) {
461 const MDNode *Var = VI->first;
463 std::pair<unsigned, DebugLoc> &VP = VI->second;
464 if (SlotRemap.count(VP.first)) {
465 DEBUG(dbgs()<<"Remapping debug info for ["<<Var->getName()<<"].\n");
466 VP.first = SlotRemap[VP.first];
471 // Keep a list of *allocas* which need to be remapped.
472 DenseMap<const Value*, const Value*> Allocas;
473 for (DenseMap<int, int>::iterator it = SlotRemap.begin(),
474 e = SlotRemap.end(); it != e; ++it) {
475 const Value *From = MFI->getObjectAllocation(it->first);
476 const Value *To = MFI->getObjectAllocation(it->second);
477 assert(To && From && "Invalid allocation object");
481 // Remap all instructions to the new stack slots.
482 MachineFunction::iterator BB, BBE;
483 MachineBasicBlock::iterator I, IE;
484 for (BB = MF->begin(), BBE = MF->end(); BB != BBE; ++BB)
485 for (I = BB->begin(), IE = BB->end(); I != IE; ++I) {
487 // Skip lifetime markers. We'll remove them soon.
488 if (I->getOpcode() == TargetOpcode::LIFETIME_START ||
489 I->getOpcode() == TargetOpcode::LIFETIME_END)
492 // Update the MachineMemOperand to use the new alloca.
493 for (MachineInstr::mmo_iterator MM = I->memoperands_begin(),
494 E = I->memoperands_end(); MM != E; ++MM) {
495 MachineMemOperand *MMO = *MM;
497 const Value *V = MMO->getValue();
502 // Climb up and find the original alloca.
503 V = GetUnderlyingObject(V);
504 // If we did not find one, or if the one that we found is not in our
505 // map, then move on.
506 if (!V || !Allocas.count(V))
509 MMO->setValue(Allocas[V]);
513 // Update all of the machine instruction operands.
514 for (unsigned i = 0 ; i < I->getNumOperands(); ++i) {
515 MachineOperand &MO = I->getOperand(i);
519 int FromSlot = MO.getIndex();
521 // Don't touch arguments.
525 // Only look at mapped slots.
526 if (!SlotRemap.count(FromSlot))
529 // In a debug build, check that the instruction that we are modifying is
530 // inside the expected live range. If the instruction is not inside
531 // the calculated range then it means that the alloca usage moved
532 // outside of the lifetime markers.
534 if (!I->isDebugValue()) {
535 SlotIndex Index = Indexes->getInstructionIndex(I);
536 LiveInterval* Interval = Intervals[FromSlot];
537 assert(Interval->find(Index) != Interval->end() &&
538 "Found instruction usage outside of live range.");
542 // Fix the machine instructions.
543 int ToSlot = SlotRemap[FromSlot];
549 DEBUG(dbgs()<<"Fixed "<<FixedMemOp<<" machine memory operands.\n");
550 DEBUG(dbgs()<<"Fixed "<<FixedDbg<<" debug locations.\n");
551 DEBUG(dbgs()<<"Fixed "<<FixedInstr<<" machine instructions.\n");
554 void StackColoring::removeInvalidSlotRanges() {
555 MachineFunction::iterator BB, BBE;
556 MachineBasicBlock::iterator I, IE;
557 for (BB = MF->begin(), BBE = MF->end(); BB != BBE; ++BB)
558 for (I = BB->begin(), IE = BB->end(); I != IE; ++I) {
560 if (I->getOpcode() == TargetOpcode::LIFETIME_START ||
561 I->getOpcode() == TargetOpcode::LIFETIME_END || I->isDebugValue())
564 // Check all of the machine operands.
565 for (unsigned i = 0 ; i < I->getNumOperands(); ++i) {
566 MachineOperand &MO = I->getOperand(i);
571 int Slot = MO.getIndex();
576 if (Intervals[Slot]->empty())
579 // Check that the used slot is inside the calculated lifetime range.
580 // If it is not, warn about it and invalidate the range.
581 LiveInterval *Interval = Intervals[Slot];
582 SlotIndex Index = Indexes->getInstructionIndex(I);
583 if (Interval->find(Index) == Interval->end()) {
584 Intervals[Slot]->clear();
585 DEBUG(dbgs()<<"Invalidating range #"<<Slot<<"\n");
591 void StackColoring::expungeSlotMap(DenseMap<int, int> &SlotRemap,
593 // Expunge slot remap map.
594 for (unsigned i=0; i < NumSlots; ++i) {
595 // If we are remapping i
596 if (SlotRemap.count(i)) {
597 int Target = SlotRemap[i];
598 // As long as our target is mapped to something else, follow it.
599 while (SlotRemap.count(Target)) {
600 Target = SlotRemap[Target];
601 SlotRemap[i] = Target;
607 bool StackColoring::runOnMachineFunction(MachineFunction &Func) {
608 DEBUG(dbgs() << "********** Stack Coloring **********\n"
609 << "********** Function: "
610 << ((const Value*)Func.getFunction())->getName() << '\n');
612 MFI = MF->getFrameInfo();
613 Indexes = &getAnalysis<SlotIndexes>();
614 BlockLiveness.clear();
616 BasicBlockNumbering.clear();
619 VNInfoAllocator.Reset();
621 unsigned NumSlots = MFI->getObjectIndexEnd();
623 // If there are no stack slots then there are no markers to remove.
627 SmallVector<int, 8> SortedSlots;
629 SortedSlots.reserve(NumSlots);
630 Intervals.reserve(NumSlots);
632 unsigned NumMarkers = collectMarkers(NumSlots);
634 unsigned TotalSize = 0;
635 DEBUG(dbgs()<<"Found "<<NumMarkers<<" markers and "<<NumSlots<<" slots\n");
636 DEBUG(dbgs()<<"Slot structure:\n");
638 for (int i=0; i < MFI->getObjectIndexEnd(); ++i) {
639 DEBUG(dbgs()<<"Slot #"<<i<<" - "<<MFI->getObjectSize(i)<<" bytes.\n");
640 TotalSize += MFI->getObjectSize(i);
643 DEBUG(dbgs()<<"Total Stack size: "<<TotalSize<<" bytes\n\n");
645 // Don't continue because there are not enough lifetime markers, or the
646 // stack or too small, or we are told not to optimize the slots.
647 if (NumMarkers < 2 || TotalSize < 16 || DisableColoring) {
648 DEBUG(dbgs()<<"Will not try to merge slots.\n");
649 return removeAllMarkers();
652 for (unsigned i=0; i < NumSlots; ++i) {
653 LiveInterval *LI = new LiveInterval(i, 0);
654 Intervals.push_back(LI);
655 LI->getNextValue(Indexes->getZeroIndex(), VNInfoAllocator);
656 SortedSlots.push_back(i);
659 // Calculate the liveness of each block.
660 calculateLocalLiveness();
662 // Propagate the liveness information.
663 calculateLiveIntervals(NumSlots);
665 removeInvalidSlotRanges();
667 // Maps old slots to new slots.
668 DenseMap<int, int> SlotRemap;
669 unsigned RemovedSlots = 0;
670 unsigned ReducedSize = 0;
672 // Do not bother looking at empty intervals.
673 for (unsigned I = 0; I < NumSlots; ++I) {
674 if (Intervals[SortedSlots[I]]->empty())
678 // This is a simple greedy algorithm for merging allocas. First, sort the
679 // slots, placing the largest slots first. Next, perform an n^2 scan and look
680 // for disjoint slots. When you find disjoint slots, merge the samller one
681 // into the bigger one and update the live interval. Remove the small alloca
684 // Sort the slots according to their size. Place unused slots at the end.
685 std::sort(SortedSlots.begin(), SortedSlots.end(), SlotSizeSorter(MFI));
690 for (unsigned I = 0; I < NumSlots; ++I) {
691 if (SortedSlots[I] == -1)
694 for (unsigned J=I+1; J < NumSlots; ++J) {
695 if (SortedSlots[J] == -1)
698 int FirstSlot = SortedSlots[I];
699 int SecondSlot = SortedSlots[J];
700 LiveInterval *First = Intervals[FirstSlot];
701 LiveInterval *Second = Intervals[SecondSlot];
702 assert (!First->empty() && !Second->empty() && "Found an empty range");
704 // Merge disjoint slots.
705 if (!First->overlaps(*Second)) {
707 First->MergeRangesInAsValue(*Second, First->getValNumInfo(0));
708 SlotRemap[SecondSlot] = FirstSlot;
710 DEBUG(dbgs()<<"Merging #"<<FirstSlot<<" and slots #"<<
711 SecondSlot<<" together.\n");
712 unsigned MaxAlignment = std::max(MFI->getObjectAlignment(FirstSlot),
713 MFI->getObjectAlignment(SecondSlot));
715 assert(MFI->getObjectSize(FirstSlot) >=
716 MFI->getObjectSize(SecondSlot) &&
717 "Merging a small object into a larger one");
720 ReducedSize += MFI->getObjectSize(SecondSlot);
721 MFI->setObjectAlignment(FirstSlot, MaxAlignment);
722 MFI->RemoveStackObject(SecondSlot);
728 // Record statistics.
729 StackSpaceSaved += ReducedSize;
730 StackSlotMerged += RemovedSlots;
731 DEBUG(dbgs()<<"Merge "<<RemovedSlots<<" slots. Saved "<<
732 ReducedSize<<" bytes\n");
734 // Scan the entire function and update all machine operands that use frame
735 // indices to use the remapped frame index.
736 expungeSlotMap(SlotRemap, NumSlots);
737 remapInstructions(SlotRemap);
739 // Release the intervals.
740 for (unsigned I = 0; I < NumSlots; ++I) {
744 return removeAllMarkers();