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 #include "llvm/CodeGen/Passes.h"
25 #include "llvm/ADT/BitVector.h"
26 #include "llvm/ADT/DepthFirstIterator.h"
27 #include "llvm/ADT/PostOrderIterator.h"
28 #include "llvm/ADT/SetVector.h"
29 #include "llvm/ADT/SmallPtrSet.h"
30 #include "llvm/ADT/SparseSet.h"
31 #include "llvm/ADT/Statistic.h"
32 #include "llvm/Analysis/ValueTracking.h"
33 #include "llvm/CodeGen/LiveInterval.h"
34 #include "llvm/CodeGen/MachineBasicBlock.h"
35 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
36 #include "llvm/CodeGen/MachineDominators.h"
37 #include "llvm/CodeGen/MachineFrameInfo.h"
38 #include "llvm/CodeGen/MachineFunctionPass.h"
39 #include "llvm/CodeGen/MachineLoopInfo.h"
40 #include "llvm/CodeGen/MachineMemOperand.h"
41 #include "llvm/CodeGen/MachineModuleInfo.h"
42 #include "llvm/CodeGen/MachineRegisterInfo.h"
43 #include "llvm/CodeGen/PseudoSourceValue.h"
44 #include "llvm/CodeGen/SlotIndexes.h"
45 #include "llvm/CodeGen/StackProtector.h"
46 #include "llvm/IR/DebugInfo.h"
47 #include "llvm/IR/Dominators.h"
48 #include "llvm/IR/Function.h"
49 #include "llvm/IR/Instructions.h"
50 #include "llvm/IR/Module.h"
51 #include "llvm/MC/MCInstrItineraries.h"
52 #include "llvm/Support/CommandLine.h"
53 #include "llvm/Support/Debug.h"
54 #include "llvm/Support/raw_ostream.h"
55 #include "llvm/Target/TargetInstrInfo.h"
56 #include "llvm/Target/TargetRegisterInfo.h"
60 #define DEBUG_TYPE "stackcoloring"
63 DisableColoring("no-stack-coloring",
64 cl::init(false), cl::Hidden
,
65 cl::desc("Disable stack coloring"));
67 /// The user may write code that uses allocas outside of the declared lifetime
68 /// zone. This can happen when the user returns a reference to a local
69 /// data-structure. We can detect these cases and decide not to optimize the
70 /// code. If this flag is enabled, we try to save the user.
72 ProtectFromEscapedAllocas("protect-from-escaped-allocas",
73 cl::init(false), cl::Hidden
,
74 cl::desc("Do not optimize lifetime zones that "
77 STATISTIC(NumMarkerSeen
, "Number of lifetime markers found.");
78 STATISTIC(StackSpaceSaved
, "Number of bytes saved due to merging slots.");
79 STATISTIC(StackSlotMerged
, "Number of stack slot merged.");
80 STATISTIC(EscapedAllocas
, "Number of allocas that escaped the lifetime region");
82 //===----------------------------------------------------------------------===//
84 //===----------------------------------------------------------------------===//
87 /// StackColoring - A machine pass for merging disjoint stack allocations,
88 /// marked by the LIFETIME_START and LIFETIME_END pseudo instructions.
89 class StackColoring
: public MachineFunctionPass
{
90 MachineFrameInfo
*MFI
;
93 /// A class representing liveness information for a single basic block.
94 /// Each bit in the BitVector represents the liveness property
95 /// for a different stack slot.
96 struct BlockLifetimeInfo
{
97 /// Which slots BEGINs in each basic block.
99 /// Which slots ENDs in each basic block.
101 /// Which slots are marked as LIVE_IN, coming into each basic block.
103 /// Which slots are marked as LIVE_OUT, coming out of each basic block.
107 /// Maps active slots (per bit) for each basic block.
108 typedef DenseMap
<const MachineBasicBlock
*, BlockLifetimeInfo
> LivenessMap
;
109 LivenessMap BlockLiveness
;
111 /// Maps serial numbers to basic blocks.
112 DenseMap
<const MachineBasicBlock
*, int> BasicBlocks
;
113 /// Maps basic blocks to a serial number.
114 SmallVector
<const MachineBasicBlock
*, 8> BasicBlockNumbering
;
116 /// Maps liveness intervals for each slot.
117 SmallVector
<std::unique_ptr
<LiveInterval
>, 16> Intervals
;
118 /// VNInfo is used for the construction of LiveIntervals.
119 VNInfo::Allocator VNInfoAllocator
;
120 /// SlotIndex analysis object.
121 SlotIndexes
*Indexes
;
122 /// The stack protector object.
125 /// The list of lifetime markers found. These markers are to be removed
126 /// once the coloring is done.
127 SmallVector
<MachineInstr
*, 8> Markers
;
131 StackColoring() : MachineFunctionPass(ID
) {
132 initializeStackColoringPass(*PassRegistry::getPassRegistry());
134 void getAnalysisUsage(AnalysisUsage
&AU
) const override
;
135 bool runOnMachineFunction(MachineFunction
&MF
) override
;
141 /// Removes all of the lifetime marker instructions from the function.
142 /// \returns true if any markers were removed.
143 bool removeAllMarkers();
145 /// Scan the machine function and find all of the lifetime markers.
146 /// Record the findings in the BEGIN and END vectors.
147 /// \returns the number of markers found.
148 unsigned collectMarkers(unsigned NumSlot
);
150 /// Perform the dataflow calculation and calculate the lifetime for each of
151 /// the slots, based on the BEGIN/END vectors. Set the LifetimeLIVE_IN and
152 /// LifetimeLIVE_OUT maps that represent which stack slots are live coming
153 /// in and out blocks.
154 void calculateLocalLiveness();
156 /// Construct the LiveIntervals for the slots.
157 void calculateLiveIntervals(unsigned NumSlots
);
159 /// Go over the machine function and change instructions which use stack
160 /// slots to use the joint slots.
161 void remapInstructions(DenseMap
<int, int> &SlotRemap
);
163 /// The input program may contain instructions which are not inside lifetime
164 /// markers. This can happen due to a bug in the compiler or due to a bug in
165 /// user code (for example, returning a reference to a local variable).
166 /// This procedure checks all of the instructions in the function and
167 /// invalidates lifetime ranges which do not contain all of the instructions
168 /// which access that frame slot.
169 void removeInvalidSlotRanges();
171 /// Map entries which point to other entries to their destination.
172 /// A->B->C becomes A->C.
173 void expungeSlotMap(DenseMap
<int, int> &SlotRemap
, unsigned NumSlots
);
175 } // end anonymous namespace
177 char StackColoring::ID
= 0;
178 char &llvm::StackColoringID
= StackColoring::ID
;
180 INITIALIZE_PASS_BEGIN(StackColoring
,
181 "stack-coloring", "Merge disjoint stack slots", false, false)
182 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree
)
183 INITIALIZE_PASS_DEPENDENCY(SlotIndexes
)
184 INITIALIZE_PASS_DEPENDENCY(StackProtector
)
185 INITIALIZE_PASS_END(StackColoring
,
186 "stack-coloring", "Merge disjoint stack slots", false, false)
188 void StackColoring::getAnalysisUsage(AnalysisUsage
&AU
) const {
189 AU
.addRequired
<MachineDominatorTree
>();
190 AU
.addPreserved
<MachineDominatorTree
>();
191 AU
.addRequired
<SlotIndexes
>();
192 AU
.addRequired
<StackProtector
>();
193 MachineFunctionPass::getAnalysisUsage(AU
);
196 void StackColoring::dump() const {
197 for (MachineBasicBlock
*MBB
: depth_first(MF
)) {
198 DEBUG(dbgs() << "Inspecting block #" << BasicBlocks
.lookup(MBB
) << " ["
199 << MBB
->getName() << "]\n");
201 LivenessMap::const_iterator BI
= BlockLiveness
.find(MBB
);
202 assert(BI
!= BlockLiveness
.end() && "Block not found");
203 const BlockLifetimeInfo
&BlockInfo
= BI
->second
;
205 DEBUG(dbgs()<<"BEGIN : {");
206 for (unsigned i
=0; i
< BlockInfo
.Begin
.size(); ++i
)
207 DEBUG(dbgs()<<BlockInfo
.Begin
.test(i
)<<" ");
208 DEBUG(dbgs()<<"}\n");
210 DEBUG(dbgs()<<"END : {");
211 for (unsigned i
=0; i
< BlockInfo
.End
.size(); ++i
)
212 DEBUG(dbgs()<<BlockInfo
.End
.test(i
)<<" ");
214 DEBUG(dbgs()<<"}\n");
216 DEBUG(dbgs()<<"LIVE_IN: {");
217 for (unsigned i
=0; i
< BlockInfo
.LiveIn
.size(); ++i
)
218 DEBUG(dbgs()<<BlockInfo
.LiveIn
.test(i
)<<" ");
220 DEBUG(dbgs()<<"}\n");
221 DEBUG(dbgs()<<"LIVEOUT: {");
222 for (unsigned i
=0; i
< BlockInfo
.LiveOut
.size(); ++i
)
223 DEBUG(dbgs()<<BlockInfo
.LiveOut
.test(i
)<<" ");
224 DEBUG(dbgs()<<"}\n");
228 unsigned StackColoring::collectMarkers(unsigned NumSlot
) {
229 unsigned MarkersFound
= 0;
230 // Scan the function to find all lifetime markers.
231 // NOTE: We use a reverse-post-order iteration to ensure that we obtain a
232 // deterministic numbering, and because we'll need a post-order iteration
233 // later for solving the liveness dataflow problem.
234 for (MachineBasicBlock
*MBB
: depth_first(MF
)) {
236 // Assign a serial number to this basic block.
237 BasicBlocks
[MBB
] = BasicBlockNumbering
.size();
238 BasicBlockNumbering
.push_back(MBB
);
240 // Keep a reference to avoid repeated lookups.
241 BlockLifetimeInfo
&BlockInfo
= BlockLiveness
[MBB
];
243 BlockInfo
.Begin
.resize(NumSlot
);
244 BlockInfo
.End
.resize(NumSlot
);
246 for (MachineInstr
&MI
: *MBB
) {
247 if (MI
.getOpcode() != TargetOpcode::LIFETIME_START
&&
248 MI
.getOpcode() != TargetOpcode::LIFETIME_END
)
251 Markers
.push_back(&MI
);
253 bool IsStart
= MI
.getOpcode() == TargetOpcode::LIFETIME_START
;
254 const MachineOperand
&MO
= MI
.getOperand(0);
255 unsigned Slot
= MO
.getIndex();
259 const AllocaInst
*Allocation
= MFI
->getObjectAllocation(Slot
);
261 DEBUG(dbgs()<<"Found a lifetime marker for slot #"<<Slot
<<
262 " with allocation: "<< Allocation
->getName()<<"\n");
266 BlockInfo
.Begin
.set(Slot
);
268 if (BlockInfo
.Begin
.test(Slot
)) {
269 // Allocas that start and end within a single block are handled
270 // specially when computing the LiveIntervals to avoid pessimizing
271 // the liveness propagation.
272 BlockInfo
.Begin
.reset(Slot
);
274 BlockInfo
.End
.set(Slot
);
280 // Update statistics.
281 NumMarkerSeen
+= MarkersFound
;
285 void StackColoring::calculateLocalLiveness() {
286 // Perform a standard reverse dataflow computation to solve for
287 // global liveness. The BEGIN set here is equivalent to KILL in the standard
288 // formulation, and END is equivalent to GEN. The result of this computation
289 // is a map from blocks to bitvectors where the bitvectors represent which
290 // allocas are live in/out of that block.
291 SmallPtrSet
<const MachineBasicBlock
*, 8> BBSet(BasicBlockNumbering
.begin(),
292 BasicBlockNumbering
.end());
293 unsigned NumSSMIters
= 0;
299 SmallPtrSet
<const MachineBasicBlock
*, 8> NextBBSet
;
301 for (const MachineBasicBlock
*BB
: BasicBlockNumbering
) {
302 if (!BBSet
.count(BB
)) continue;
304 // Use an iterator to avoid repeated lookups.
305 LivenessMap::iterator BI
= BlockLiveness
.find(BB
);
306 assert(BI
!= BlockLiveness
.end() && "Block not found");
307 BlockLifetimeInfo
&BlockInfo
= BI
->second
;
309 BitVector LocalLiveIn
;
310 BitVector LocalLiveOut
;
312 // Forward propagation from begins to ends.
313 for (MachineBasicBlock::const_pred_iterator PI
= BB
->pred_begin(),
314 PE
= BB
->pred_end(); PI
!= PE
; ++PI
) {
315 LivenessMap::const_iterator I
= BlockLiveness
.find(*PI
);
316 assert(I
!= BlockLiveness
.end() && "Predecessor not found");
317 LocalLiveIn
|= I
->second
.LiveOut
;
319 LocalLiveIn
|= BlockInfo
.End
;
320 LocalLiveIn
.reset(BlockInfo
.Begin
);
322 // Reverse propagation from ends to begins.
323 for (MachineBasicBlock::const_succ_iterator SI
= BB
->succ_begin(),
324 SE
= BB
->succ_end(); SI
!= SE
; ++SI
) {
325 LivenessMap::const_iterator I
= BlockLiveness
.find(*SI
);
326 assert(I
!= BlockLiveness
.end() && "Successor not found");
327 LocalLiveOut
|= I
->second
.LiveIn
;
329 LocalLiveOut
|= BlockInfo
.Begin
;
330 LocalLiveOut
.reset(BlockInfo
.End
);
332 LocalLiveIn
|= LocalLiveOut
;
333 LocalLiveOut
|= LocalLiveIn
;
335 // After adopting the live bits, we need to turn-off the bits which
336 // are de-activated in this block.
337 LocalLiveOut
.reset(BlockInfo
.End
);
338 LocalLiveIn
.reset(BlockInfo
.Begin
);
340 // If we have both BEGIN and END markers in the same basic block then
341 // we know that the BEGIN marker comes after the END, because we already
342 // handle the case where the BEGIN comes before the END when collecting
343 // the markers (and building the BEGIN/END vectore).
344 // Want to enable the LIVE_IN and LIVE_OUT of slots that have both
345 // BEGIN and END because it means that the value lives before and after
347 BitVector LocalEndBegin
= BlockInfo
.End
;
348 LocalEndBegin
&= BlockInfo
.Begin
;
349 LocalLiveIn
|= LocalEndBegin
;
350 LocalLiveOut
|= LocalEndBegin
;
352 if (LocalLiveIn
.test(BlockInfo
.LiveIn
)) {
354 BlockInfo
.LiveIn
|= LocalLiveIn
;
356 NextBBSet
.insert(BB
->pred_begin(), BB
->pred_end());
359 if (LocalLiveOut
.test(BlockInfo
.LiveOut
)) {
361 BlockInfo
.LiveOut
|= LocalLiveOut
;
363 NextBBSet
.insert(BB
->succ_begin(), BB
->succ_end());
371 void StackColoring::calculateLiveIntervals(unsigned NumSlots
) {
372 SmallVector
<SlotIndex
, 16> Starts
;
373 SmallVector
<SlotIndex
, 16> Finishes
;
375 // For each block, find which slots are active within this block
376 // and update the live intervals.
377 for (const MachineBasicBlock
&MBB
: *MF
) {
379 Starts
.resize(NumSlots
);
381 Finishes
.resize(NumSlots
);
383 // Create the interval for the basic blocks with lifetime markers in them.
384 for (const MachineInstr
*MI
: Markers
) {
385 if (MI
->getParent() != &MBB
)
388 assert((MI
->getOpcode() == TargetOpcode::LIFETIME_START
||
389 MI
->getOpcode() == TargetOpcode::LIFETIME_END
) &&
390 "Invalid Lifetime marker");
392 bool IsStart
= MI
->getOpcode() == TargetOpcode::LIFETIME_START
;
393 const MachineOperand
&Mo
= MI
->getOperand(0);
394 int Slot
= Mo
.getIndex();
395 assert(Slot
>= 0 && "Invalid slot");
397 SlotIndex ThisIndex
= Indexes
->getInstructionIndex(MI
);
400 if (!Starts
[Slot
].isValid() || Starts
[Slot
] > ThisIndex
)
401 Starts
[Slot
] = ThisIndex
;
403 if (!Finishes
[Slot
].isValid() || Finishes
[Slot
] < ThisIndex
)
404 Finishes
[Slot
] = ThisIndex
;
408 // Create the interval of the blocks that we previously found to be 'alive'.
409 BlockLifetimeInfo
&MBBLiveness
= BlockLiveness
[&MBB
];
410 for (int pos
= MBBLiveness
.LiveIn
.find_first(); pos
!= -1;
411 pos
= MBBLiveness
.LiveIn
.find_next(pos
)) {
412 Starts
[pos
] = Indexes
->getMBBStartIdx(&MBB
);
414 for (int pos
= MBBLiveness
.LiveOut
.find_first(); pos
!= -1;
415 pos
= MBBLiveness
.LiveOut
.find_next(pos
)) {
416 Finishes
[pos
] = Indexes
->getMBBEndIdx(&MBB
);
419 for (unsigned i
= 0; i
< NumSlots
; ++i
) {
420 assert(Starts
[i
].isValid() == Finishes
[i
].isValid() && "Unmatched range");
421 if (!Starts
[i
].isValid())
424 assert(Starts
[i
] && Finishes
[i
] && "Invalid interval");
425 VNInfo
*ValNum
= Intervals
[i
]->getValNumInfo(0);
426 SlotIndex S
= Starts
[i
];
427 SlotIndex F
= Finishes
[i
];
429 // We have a single consecutive region.
430 Intervals
[i
]->addSegment(LiveInterval::Segment(S
, F
, ValNum
));
432 // We have two non-consecutive regions. This happens when
433 // LIFETIME_START appears after the LIFETIME_END marker.
434 SlotIndex NewStart
= Indexes
->getMBBStartIdx(&MBB
);
435 SlotIndex NewFin
= Indexes
->getMBBEndIdx(&MBB
);
436 Intervals
[i
]->addSegment(LiveInterval::Segment(NewStart
, F
, ValNum
));
437 Intervals
[i
]->addSegment(LiveInterval::Segment(S
, NewFin
, ValNum
));
443 bool StackColoring::removeAllMarkers() {
445 for (MachineInstr
*MI
: Markers
) {
446 MI
->eraseFromParent();
451 DEBUG(dbgs()<<"Removed "<<Count
<<" markers.\n");
455 void StackColoring::remapInstructions(DenseMap
<int, int> &SlotRemap
) {
456 unsigned FixedInstr
= 0;
457 unsigned FixedMemOp
= 0;
458 unsigned FixedDbg
= 0;
459 MachineModuleInfo
*MMI
= &MF
->getMMI();
461 // Remap debug information that refers to stack slots.
462 for (auto &VI
: MMI
->getVariableDbgInfo()) {
465 if (SlotRemap
.count(VI
.Slot
)) {
466 DEBUG(dbgs() << "Remapping debug info for ["
467 << DIVariable(VI
.Var
).getName() << "].\n");
468 VI
.Slot
= SlotRemap
[VI
.Slot
];
473 // Keep a list of *allocas* which need to be remapped.
474 DenseMap
<const AllocaInst
*, const AllocaInst
*> Allocas
;
475 for (const std::pair
<int, int> &SI
: SlotRemap
) {
476 const AllocaInst
*From
= MFI
->getObjectAllocation(SI
.first
);
477 const AllocaInst
*To
= MFI
->getObjectAllocation(SI
.second
);
478 assert(To
&& From
&& "Invalid allocation object");
481 // AA might be used later for instruction scheduling, and we need it to be
482 // able to deduce the correct aliasing releationships between pointers
483 // derived from the alloca being remapped and the target of that remapping.
484 // The only safe way, without directly informing AA about the remapping
485 // somehow, is to directly update the IR to reflect the change being made
487 Instruction
*Inst
= const_cast<AllocaInst
*>(To
);
488 if (From
->getType() != To
->getType()) {
489 BitCastInst
*Cast
= new BitCastInst(Inst
, From
->getType());
490 Cast
->insertAfter(Inst
);
494 // Allow the stack protector to adjust its value map to account for the
495 // upcoming replacement.
496 SP
->adjustForColoring(From
, To
);
498 // Note that this will not replace uses in MMOs (which we'll update below),
499 // or anywhere else (which is why we won't delete the original
501 const_cast<AllocaInst
*>(From
)->replaceAllUsesWith(Inst
);
504 // Remap all instructions to the new stack slots.
505 for (MachineBasicBlock
&BB
: *MF
)
506 for (MachineInstr
&I
: BB
) {
507 // Skip lifetime markers. We'll remove them soon.
508 if (I
.getOpcode() == TargetOpcode::LIFETIME_START
||
509 I
.getOpcode() == TargetOpcode::LIFETIME_END
)
512 // Update the MachineMemOperand to use the new alloca.
513 for (MachineMemOperand
*MMO
: I
.memoperands()) {
514 // FIXME: In order to enable the use of TBAA when using AA in CodeGen,
515 // we'll also need to update the TBAA nodes in MMOs with values
516 // derived from the merged allocas. When doing this, we'll need to use
517 // the same variant of GetUnderlyingObjects that is used by the
518 // instruction scheduler (that can look through ptrtoint/inttoptr
521 // We've replaced IR-level uses of the remapped allocas, so we only
522 // need to replace direct uses here.
523 const AllocaInst
*AI
= dyn_cast_or_null
<AllocaInst
>(MMO
->getValue());
527 if (!Allocas
.count(AI
))
530 MMO
->setValue(Allocas
[AI
]);
534 // Update all of the machine instruction operands.
535 for (MachineOperand
&MO
: I
.operands()) {
538 int FromSlot
= MO
.getIndex();
540 // Don't touch arguments.
544 // Only look at mapped slots.
545 if (!SlotRemap
.count(FromSlot
))
548 // In a debug build, check that the instruction that we are modifying is
549 // inside the expected live range. If the instruction is not inside
550 // the calculated range then it means that the alloca usage moved
551 // outside of the lifetime markers, or that the user has a bug.
552 // NOTE: Alloca address calculations which happen outside the lifetime
553 // zone are are okay, despite the fact that we don't have a good way
554 // for validating all of the usages of the calculation.
556 bool TouchesMemory
= I
.mayLoad() || I
.mayStore();
557 // If we *don't* protect the user from escaped allocas, don't bother
558 // validating the instructions.
559 if (!I
.isDebugValue() && TouchesMemory
&& ProtectFromEscapedAllocas
) {
560 SlotIndex Index
= Indexes
->getInstructionIndex(&I
);
561 const LiveInterval
*Interval
= &*Intervals
[FromSlot
];
562 assert(Interval
->find(Index
) != Interval
->end() &&
563 "Found instruction usage outside of live range.");
567 // Fix the machine instructions.
568 int ToSlot
= SlotRemap
[FromSlot
];
574 DEBUG(dbgs()<<"Fixed "<<FixedMemOp
<<" machine memory operands.\n");
575 DEBUG(dbgs()<<"Fixed "<<FixedDbg
<<" debug locations.\n");
576 DEBUG(dbgs()<<"Fixed "<<FixedInstr
<<" machine instructions.\n");
579 void StackColoring::removeInvalidSlotRanges() {
580 for (MachineBasicBlock
&BB
: *MF
)
581 for (MachineInstr
&I
: BB
) {
582 if (I
.getOpcode() == TargetOpcode::LIFETIME_START
||
583 I
.getOpcode() == TargetOpcode::LIFETIME_END
|| I
.isDebugValue())
586 // Some intervals are suspicious! In some cases we find address
587 // calculations outside of the lifetime zone, but not actual memory
588 // read or write. Memory accesses outside of the lifetime zone are a clear
589 // violation, but address calculations are okay. This can happen when
590 // GEPs are hoisted outside of the lifetime zone.
591 // So, in here we only check instructions which can read or write memory.
592 if (!I
.mayLoad() && !I
.mayStore())
595 // Check all of the machine operands.
596 for (const MachineOperand
&MO
: I
.operands()) {
600 int Slot
= MO
.getIndex();
605 if (Intervals
[Slot
]->empty())
608 // Check that the used slot is inside the calculated lifetime range.
609 // If it is not, warn about it and invalidate the range.
610 LiveInterval
*Interval
= &*Intervals
[Slot
];
611 SlotIndex Index
= Indexes
->getInstructionIndex(&I
);
612 if (Interval
->find(Index
) == Interval
->end()) {
614 DEBUG(dbgs()<<"Invalidating range #"<<Slot
<<"\n");
621 void StackColoring::expungeSlotMap(DenseMap
<int, int> &SlotRemap
,
623 // Expunge slot remap map.
624 for (unsigned i
=0; i
< NumSlots
; ++i
) {
625 // If we are remapping i
626 if (SlotRemap
.count(i
)) {
627 int Target
= SlotRemap
[i
];
628 // As long as our target is mapped to something else, follow it.
629 while (SlotRemap
.count(Target
)) {
630 Target
= SlotRemap
[Target
];
631 SlotRemap
[i
] = Target
;
637 bool StackColoring::runOnMachineFunction(MachineFunction
&Func
) {
638 if (skipOptnoneFunction(*Func
.getFunction()))
641 DEBUG(dbgs() << "********** Stack Coloring **********\n"
642 << "********** Function: "
643 << ((const Value
*)Func
.getFunction())->getName() << '\n');
645 MFI
= MF
->getFrameInfo();
646 Indexes
= &getAnalysis
<SlotIndexes
>();
647 SP
= &getAnalysis
<StackProtector
>();
648 BlockLiveness
.clear();
650 BasicBlockNumbering
.clear();
653 VNInfoAllocator
.Reset();
655 unsigned NumSlots
= MFI
->getObjectIndexEnd();
657 // If there are no stack slots then there are no markers to remove.
661 SmallVector
<int, 8> SortedSlots
;
663 SortedSlots
.reserve(NumSlots
);
664 Intervals
.reserve(NumSlots
);
666 unsigned NumMarkers
= collectMarkers(NumSlots
);
668 unsigned TotalSize
= 0;
669 DEBUG(dbgs()<<"Found "<<NumMarkers
<<" markers and "<<NumSlots
<<" slots\n");
670 DEBUG(dbgs()<<"Slot structure:\n");
672 for (int i
=0; i
< MFI
->getObjectIndexEnd(); ++i
) {
673 DEBUG(dbgs()<<"Slot #"<<i
<<" - "<<MFI
->getObjectSize(i
)<<" bytes.\n");
674 TotalSize
+= MFI
->getObjectSize(i
);
677 DEBUG(dbgs()<<"Total Stack size: "<<TotalSize
<<" bytes\n\n");
679 // Don't continue because there are not enough lifetime markers, or the
680 // stack is too small, or we are told not to optimize the slots.
681 if (NumMarkers
< 2 || TotalSize
< 16 || DisableColoring
) {
682 DEBUG(dbgs()<<"Will not try to merge slots.\n");
683 return removeAllMarkers();
686 for (unsigned i
=0; i
< NumSlots
; ++i
) {
687 std::unique_ptr
<LiveInterval
> LI(new LiveInterval(i
, 0));
688 LI
->getNextValue(Indexes
->getZeroIndex(), VNInfoAllocator
);
689 Intervals
.push_back(std::move(LI
));
690 SortedSlots
.push_back(i
);
693 // Calculate the liveness of each block.
694 calculateLocalLiveness();
696 // Propagate the liveness information.
697 calculateLiveIntervals(NumSlots
);
699 // Search for allocas which are used outside of the declared lifetime
701 if (ProtectFromEscapedAllocas
)
702 removeInvalidSlotRanges();
704 // Maps old slots to new slots.
705 DenseMap
<int, int> SlotRemap
;
706 unsigned RemovedSlots
= 0;
707 unsigned ReducedSize
= 0;
709 // Do not bother looking at empty intervals.
710 for (unsigned I
= 0; I
< NumSlots
; ++I
) {
711 if (Intervals
[SortedSlots
[I
]]->empty())
715 // This is a simple greedy algorithm for merging allocas. First, sort the
716 // slots, placing the largest slots first. Next, perform an n^2 scan and look
717 // for disjoint slots. When you find disjoint slots, merge the samller one
718 // into the bigger one and update the live interval. Remove the small alloca
721 // Sort the slots according to their size. Place unused slots at the end.
722 // Use stable sort to guarantee deterministic code generation.
723 std::stable_sort(SortedSlots
.begin(), SortedSlots
.end(),
724 [this](int LHS
, int RHS
) {
725 // We use -1 to denote a uninteresting slot. Place these slots at the end.
726 if (LHS
== -1) return false;
727 if (RHS
== -1) return true;
728 // Sort according to size.
729 return MFI
->getObjectSize(LHS
) > MFI
->getObjectSize(RHS
);
735 for (unsigned I
= 0; I
< NumSlots
; ++I
) {
736 if (SortedSlots
[I
] == -1)
739 for (unsigned J
=I
+1; J
< NumSlots
; ++J
) {
740 if (SortedSlots
[J
] == -1)
743 int FirstSlot
= SortedSlots
[I
];
744 int SecondSlot
= SortedSlots
[J
];
745 LiveInterval
*First
= &*Intervals
[FirstSlot
];
746 LiveInterval
*Second
= &*Intervals
[SecondSlot
];
747 assert (!First
->empty() && !Second
->empty() && "Found an empty range");
749 // Merge disjoint slots.
750 if (!First
->overlaps(*Second
)) {
752 First
->MergeSegmentsInAsValue(*Second
, First
->getValNumInfo(0));
753 SlotRemap
[SecondSlot
] = FirstSlot
;
755 DEBUG(dbgs()<<"Merging #"<<FirstSlot
<<" and slots #"<<
756 SecondSlot
<<" together.\n");
757 unsigned MaxAlignment
= std::max(MFI
->getObjectAlignment(FirstSlot
),
758 MFI
->getObjectAlignment(SecondSlot
));
760 assert(MFI
->getObjectSize(FirstSlot
) >=
761 MFI
->getObjectSize(SecondSlot
) &&
762 "Merging a small object into a larger one");
765 ReducedSize
+= MFI
->getObjectSize(SecondSlot
);
766 MFI
->setObjectAlignment(FirstSlot
, MaxAlignment
);
767 MFI
->RemoveStackObject(SecondSlot
);
773 // Record statistics.
774 StackSpaceSaved
+= ReducedSize
;
775 StackSlotMerged
+= RemovedSlots
;
776 DEBUG(dbgs()<<"Merge "<<RemovedSlots
<<" slots. Saved "<<
777 ReducedSize
<<" bytes\n");
779 // Scan the entire function and update all machine operands that use frame
780 // indices to use the remapped frame index.
781 expungeSlotMap(SlotRemap
, NumSlots
);
782 remapInstructions(SlotRemap
);
784 return removeAllMarkers();