1 //===- StackColoring.cpp --------------------------------------------------===//
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
9 // This pass implements the stack-coloring optimization that looks for
10 // lifetime markers machine instructions (LIFESTART_BEGIN and LIFESTART_END),
11 // which represent the possible lifetime of stack slots. It attempts to
12 // merge disjoint stack slots and reduce the used stack space.
13 // NOTE: This pass is not StackSlotColoring, which optimizes spill slots.
15 // TODO: In the future we plan to improve stack coloring in the following ways:
16 // 1. Allow merging multiple small slots into a single larger slot at different
18 // 2. Merge this pass with StackSlotColoring and allow merging of allocas with
21 //===----------------------------------------------------------------------===//
23 #include "llvm/ADT/BitVector.h"
24 #include "llvm/ADT/DenseMap.h"
25 #include "llvm/ADT/DepthFirstIterator.h"
26 #include "llvm/ADT/SmallPtrSet.h"
27 #include "llvm/ADT/SmallVector.h"
28 #include "llvm/ADT/Statistic.h"
29 #include "llvm/Analysis/ValueTracking.h"
30 #include "llvm/CodeGen/LiveInterval.h"
31 #include "llvm/CodeGen/MachineBasicBlock.h"
32 #include "llvm/CodeGen/MachineFrameInfo.h"
33 #include "llvm/CodeGen/MachineFunction.h"
34 #include "llvm/CodeGen/MachineFunctionPass.h"
35 #include "llvm/CodeGen/MachineInstr.h"
36 #include "llvm/CodeGen/MachineMemOperand.h"
37 #include "llvm/CodeGen/MachineOperand.h"
38 #include "llvm/CodeGen/Passes.h"
39 #include "llvm/CodeGen/SelectionDAGNodes.h"
40 #include "llvm/CodeGen/SlotIndexes.h"
41 #include "llvm/CodeGen/TargetOpcodes.h"
42 #include "llvm/CodeGen/WinEHFuncInfo.h"
43 #include "llvm/Config/llvm-config.h"
44 #include "llvm/IR/Constants.h"
45 #include "llvm/IR/DebugInfoMetadata.h"
46 #include "llvm/IR/Function.h"
47 #include "llvm/IR/Instructions.h"
48 #include "llvm/IR/Metadata.h"
49 #include "llvm/IR/Use.h"
50 #include "llvm/IR/Value.h"
51 #include "llvm/InitializePasses.h"
52 #include "llvm/Pass.h"
53 #include "llvm/Support/Casting.h"
54 #include "llvm/Support/CommandLine.h"
55 #include "llvm/Support/Compiler.h"
56 #include "llvm/Support/Debug.h"
57 #include "llvm/Support/raw_ostream.h"
66 #define DEBUG_TYPE "stack-coloring"
69 DisableColoring("no-stack-coloring",
70 cl::init(false), cl::Hidden,
71 cl::desc("Disable stack coloring"));
73 /// The user may write code that uses allocas outside of the declared lifetime
74 /// zone. This can happen when the user returns a reference to a local
75 /// data-structure. We can detect these cases and decide not to optimize the
76 /// code. If this flag is enabled, we try to save the user. This option
77 /// is treated as overriding LifetimeStartOnFirstUse below.
79 ProtectFromEscapedAllocas("protect-from-escaped-allocas",
80 cl::init(false), cl::Hidden,
81 cl::desc("Do not optimize lifetime zones that "
84 /// Enable enhanced dataflow scheme for lifetime analysis (treat first
85 /// use of stack slot as start of slot lifetime, as opposed to looking
86 /// for LIFETIME_START marker). See "Implementation notes" below for
89 LifetimeStartOnFirstUse("stackcoloring-lifetime-start-on-first-use",
90 cl::init(true), cl::Hidden,
91 cl::desc("Treat stack lifetimes as starting on first use, not on START marker."));
94 STATISTIC(NumMarkerSeen, "Number of lifetime markers found.");
95 STATISTIC(StackSpaceSaved, "Number of bytes saved due to merging slots.");
96 STATISTIC(StackSlotMerged, "Number of stack slot merged.");
97 STATISTIC(EscapedAllocas, "Number of allocas that escaped the lifetime region");
99 //===----------------------------------------------------------------------===//
100 // StackColoring Pass
101 //===----------------------------------------------------------------------===//
103 // Stack Coloring reduces stack usage by merging stack slots when they
104 // can't be used together. For example, consider the following C program:
106 // void bar(char *, int);
107 // void foo(bool var) {
126 // Naively-compiled, this program would use 12k of stack space. However, the
127 // stack slot corresponding to `z` is always destroyed before either of the
128 // stack slots for `x` or `y` are used, and then `x` is only used if `var`
129 // is true, while `y` is only used if `var` is false. So in no time are 2
130 // of the stack slots used together, and therefore we can merge them,
131 // compiling the function using only a single 4k alloca:
133 // void foo(bool var) { // equivalent
146 // This is an important optimization if we want stack space to be under
147 // control in large functions, both open-coded ones and ones created by
150 // Implementation Notes:
151 // ---------------------
153 // An important part of the above reasoning is that `z` can't be accessed
154 // while the latter 2 calls to `bar` are running. This is justified because
155 // `z`'s lifetime is over after we exit from block `A:`, so any further
156 // accesses to it would be UB. The way we represent this information
157 // in LLVM is by having frontends delimit blocks with `lifetime.start`
158 // and `lifetime.end` intrinsics.
160 // The effect of these intrinsics seems to be as follows (maybe I should
161 // specify this in the reference?):
163 // L1) at start, each stack-slot is marked as *out-of-scope*, unless no
164 // lifetime intrinsic refers to that stack slot, in which case
165 // it is marked as *in-scope*.
166 // L2) on a `lifetime.start`, a stack slot is marked as *in-scope* and
167 // the stack slot is overwritten with `undef`.
168 // L3) on a `lifetime.end`, a stack slot is marked as *out-of-scope*.
169 // L4) on function exit, all stack slots are marked as *out-of-scope*.
170 // L5) `lifetime.end` is a no-op when called on a slot that is already
172 // L6) memory accesses to *out-of-scope* stack slots are UB.
173 // L7) when a stack-slot is marked as *out-of-scope*, all pointers to it
174 // are invalidated, unless the slot is "degenerate". This is used to
175 // justify not marking slots as in-use until the pointer to them is
176 // used, but feels a bit hacky in the presence of things like LICM. See
177 // the "Degenerate Slots" section for more details.
179 // Now, let's ground stack coloring on these rules. We'll define a slot
180 // as *in-use* at a (dynamic) point in execution if it either can be
181 // written to at that point, or if it has a live and non-undef content
184 // Obviously, slots that are never *in-use* together can be merged, and
185 // in our example `foo`, the slots for `x`, `y` and `z` are never
186 // in-use together (of course, sometimes slots that *are* in-use together
187 // might still be mergable, but we don't care about that here).
189 // In this implementation, we successively merge pairs of slots that are
190 // not *in-use* together. We could be smarter - for example, we could merge
191 // a single large slot with 2 small slots, or we could construct the
192 // interference graph and run a "smart" graph coloring algorithm, but with
193 // that aside, how do we find out whether a pair of slots might be *in-use*
196 // From our rules, we see that *out-of-scope* slots are never *in-use*,
197 // and from (L7) we see that "non-degenerate" slots remain non-*in-use*
198 // until their address is taken. Therefore, we can approximate slot activity
201 // A subtle point: naively, we might try to figure out which pairs of
202 // stack-slots interfere by propagating `S in-use` through the CFG for every
203 // stack-slot `S`, and having `S` and `T` interfere if there is a CFG point in
204 // which they are both *in-use*.
206 // That is sound, but overly conservative in some cases: in our (artificial)
207 // example `foo`, either `x` or `y` might be in use at the label `B:`, but
208 // as `x` is only in use if we came in from the `var` edge and `y` only
209 // if we came from the `!var` edge, they still can't be in use together.
210 // See PR32488 for an important real-life case.
212 // If we wanted to find all points of interference precisely, we could
213 // propagate `S in-use` and `S&T in-use` predicates through the CFG. That
214 // would be precise, but requires propagating `O(n^2)` dataflow facts.
216 // However, we aren't interested in the *set* of points of interference
217 // between 2 stack slots, only *whether* there *is* such a point. So we
218 // can rely on a little trick: for `S` and `T` to be in-use together,
219 // one of them needs to become in-use while the other is in-use (or
220 // they might both become in use simultaneously). We can check this
221 // by also keeping track of the points at which a stack slot might *start*
227 // Consider the following motivating example:
230 // char b1[1024], b2[1024];
236 // char b4[1024], b5[1024];
237 // <uses of b2, b4, b5>;
242 // In the code above, "b3" and "b4" are declared in distinct lexical
243 // scopes, meaning that it is easy to prove that they can share the
244 // same stack slot. Variables "b1" and "b2" are declared in the same
245 // scope, meaning that from a lexical point of view, their lifetimes
246 // overlap. From a control flow pointer of view, however, the two
247 // variables are accessed in disjoint regions of the CFG, thus it
248 // should be possible for them to share the same stack slot. An ideal
249 // stack allocation for the function above would look like:
255 // Achieving this allocation is tricky, however, due to the way
256 // lifetime markers are inserted. Here is a simplified view of the
257 // control flow graph for the code above:
259 // +------ block 0 -------+
260 // 0| LIFETIME_START b1, b2 |
261 // 1| <test 'if' condition> |
262 // +-----------------------+
264 // +------ block 1 -------+ +------ block 2 -------+
265 // 2| LIFETIME_START b3 | 5| LIFETIME_START b4, b5 |
266 // 3| <uses of b1, b3> | 6| <uses of b2, b4, b5> |
267 // 4| LIFETIME_END b3 | 7| LIFETIME_END b4, b5 |
268 // +-----------------------+ +-----------------------+
270 // +------ block 3 -------+
271 // 8| <cleanupcode> |
272 // 9| LIFETIME_END b1, b2 |
274 // +-----------------------+
276 // If we create live intervals for the variables above strictly based
277 // on the lifetime markers, we'll get the set of intervals on the
278 // left. If we ignore the lifetime start markers and instead treat a
279 // variable's lifetime as beginning with the first reference to the
280 // var, then we get the intervals on the right.
282 // LIFETIME_START First Use
283 // b1: [0,9] [3,4] [8,9]
289 // For the intervals on the left, the best we can do is overlap two
290 // variables (b3 and b4, for example); this gives us a stack size of
291 // 4*1024 bytes, not ideal. When treating first-use as the start of a
292 // lifetime, we can additionally overlap b1 and b5, giving us a 3*1024
293 // byte stack (better).
298 // Relying entirely on first-use of stack slots is problematic,
299 // however, due to the fact that optimizations can sometimes migrate
300 // uses of a variable outside of its lifetime start/end region. Here
304 // char b1[1024], b2[1024];
317 // Before optimization, the control flow graph for the code above
318 // might look like the following:
320 // +------ block 0 -------+
321 // 0| LIFETIME_START b1, b2 |
322 // 1| <test 'if' condition> |
323 // +-----------------------+
325 // +------ block 1 -------+ +------- block 2 -------+
326 // 2| <uses of b2> | 3| <uses of b1> |
327 // +-----------------------+ +-----------------------+
329 // | +------- block 3 -------+ <-\.
330 // | 4| <while condition> | |
331 // | +-----------------------+ |
333 // | / +------- block 4 -------+
334 // \ / 5| LIFETIME_START b3 | |
335 // \ / 6| <uses of b3> | |
336 // \ / 7| LIFETIME_END b3 | |
337 // \ | +------------------------+ |
339 // +------ block 5 -----+ \---------------
340 // 8| <cleanupcode> |
341 // 9| LIFETIME_END b1, b2 |
343 // +---------------------+
345 // During optimization, however, it can happen that an instruction
346 // computing an address in "b3" (for example, a loop-invariant GEP) is
347 // hoisted up out of the loop from block 4 to block 2. [Note that
348 // this is not an actual load from the stack, only an instruction that
349 // computes the address to be loaded]. If this happens, there is now a
350 // path leading from the first use of b3 to the return instruction
351 // that does not encounter the b3 LIFETIME_END, hence b3's lifetime is
352 // now larger than if we were computing live intervals strictly based
353 // on lifetime markers. In the example above, this lengthened lifetime
354 // would mean that it would appear illegal to overlap b3 with b2.
356 // To deal with this such cases, the code in ::collectMarkers() below
357 // tries to identify "degenerate" slots -- those slots where on a single
358 // forward pass through the CFG we encounter a first reference to slot
359 // K before we hit the slot K lifetime start marker. For such slots,
360 // we fall back on using the lifetime start marker as the beginning of
361 // the variable's lifetime. NB: with this implementation, slots can
362 // appear degenerate in cases where there is unstructured control flow:
367 // memcpy(&b[0], ...);
372 // If in RPO ordering chosen to walk the CFG we happen to visit the b[k]
373 // before visiting the memcpy block (which will contain the lifetime start
374 // for "b" then it will appear that 'b' has a degenerate lifetime.
379 /// StackColoring - A machine pass for merging disjoint stack allocations,
380 /// marked by the LIFETIME_START and LIFETIME_END pseudo instructions.
381 class StackColoring : public MachineFunctionPass {
382 MachineFrameInfo *MFI;
385 /// A class representing liveness information for a single basic block.
386 /// Each bit in the BitVector represents the liveness property
387 /// for a different stack slot.
388 struct BlockLifetimeInfo {
389 /// Which slots BEGINs in each basic block.
392 /// Which slots ENDs in each basic block.
395 /// Which slots are marked as LIVE_IN, coming into each basic block.
398 /// Which slots are marked as LIVE_OUT, coming out of each basic block.
402 /// Maps active slots (per bit) for each basic block.
403 using LivenessMap = DenseMap<const MachineBasicBlock *, BlockLifetimeInfo>;
404 LivenessMap BlockLiveness;
406 /// Maps serial numbers to basic blocks.
407 DenseMap<const MachineBasicBlock *, int> BasicBlocks;
409 /// Maps basic blocks to a serial number.
410 SmallVector<const MachineBasicBlock *, 8> BasicBlockNumbering;
412 /// Maps slots to their use interval. Outside of this interval, slots
413 /// values are either dead or `undef` and they will not be written to.
414 SmallVector<std::unique_ptr<LiveInterval>, 16> Intervals;
416 /// Maps slots to the points where they can become in-use.
417 SmallVector<SmallVector<SlotIndex, 4>, 16> LiveStarts;
419 /// VNInfo is used for the construction of LiveIntervals.
420 VNInfo::Allocator VNInfoAllocator;
422 /// SlotIndex analysis object.
423 SlotIndexes *Indexes;
425 /// The list of lifetime markers found. These markers are to be removed
426 /// once the coloring is done.
427 SmallVector<MachineInstr*, 8> Markers;
429 /// Record the FI slots for which we have seen some sort of
430 /// lifetime marker (either start or end).
431 BitVector InterestingSlots;
433 /// FI slots that need to be handled conservatively (for these
434 /// slots lifetime-start-on-first-use is disabled).
435 BitVector ConservativeSlots;
437 /// Number of iterations taken during data flow analysis.
438 unsigned NumIterations;
443 StackColoring() : MachineFunctionPass(ID) {
444 initializeStackColoringPass(*PassRegistry::getPassRegistry());
447 void getAnalysisUsage(AnalysisUsage &AU) const override;
448 bool runOnMachineFunction(MachineFunction &Func) override;
451 /// Used in collectMarkers
452 using BlockBitVecMap = DenseMap<const MachineBasicBlock *, BitVector>;
456 void dumpIntervals() const;
457 void dumpBB(MachineBasicBlock *MBB) const;
458 void dumpBV(const char *tag, const BitVector &BV) const;
460 /// Removes all of the lifetime marker instructions from the function.
461 /// \returns true if any markers were removed.
462 bool removeAllMarkers();
464 /// Scan the machine function and find all of the lifetime markers.
465 /// Record the findings in the BEGIN and END vectors.
466 /// \returns the number of markers found.
467 unsigned collectMarkers(unsigned NumSlot);
469 /// Perform the dataflow calculation and calculate the lifetime for each of
470 /// the slots, based on the BEGIN/END vectors. Set the LifetimeLIVE_IN and
471 /// LifetimeLIVE_OUT maps that represent which stack slots are live coming
472 /// in and out blocks.
473 void calculateLocalLiveness();
475 /// Returns TRUE if we're using the first-use-begins-lifetime method for
476 /// this slot (if FALSE, then the start marker is treated as start of lifetime).
477 bool applyFirstUse(int Slot) {
478 if (!LifetimeStartOnFirstUse || ProtectFromEscapedAllocas)
480 if (ConservativeSlots.test(Slot))
485 /// Examines the specified instruction and returns TRUE if the instruction
486 /// represents the start or end of an interesting lifetime. The slot or slots
487 /// starting or ending are added to the vector "slots" and "isStart" is set
489 /// \returns True if inst contains a lifetime start or end
490 bool isLifetimeStartOrEnd(const MachineInstr &MI,
491 SmallVector<int, 4> &slots,
494 /// Construct the LiveIntervals for the slots.
495 void calculateLiveIntervals(unsigned NumSlots);
497 /// Go over the machine function and change instructions which use stack
498 /// slots to use the joint slots.
499 void remapInstructions(DenseMap<int, int> &SlotRemap);
501 /// The input program may contain instructions which are not inside lifetime
502 /// markers. This can happen due to a bug in the compiler or due to a bug in
503 /// user code (for example, returning a reference to a local variable).
504 /// This procedure checks all of the instructions in the function and
505 /// invalidates lifetime ranges which do not contain all of the instructions
506 /// which access that frame slot.
507 void removeInvalidSlotRanges();
509 /// Map entries which point to other entries to their destination.
510 /// A->B->C becomes A->C.
511 void expungeSlotMap(DenseMap<int, int> &SlotRemap, unsigned NumSlots);
514 } // end anonymous namespace
516 char StackColoring::ID = 0;
518 char &llvm::StackColoringID = StackColoring::ID;
520 INITIALIZE_PASS_BEGIN(StackColoring, DEBUG_TYPE,
521 "Merge disjoint stack slots", false, false)
522 INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
523 INITIALIZE_PASS_END(StackColoring, DEBUG_TYPE,
524 "Merge disjoint stack slots", false, false)
526 void StackColoring::getAnalysisUsage(AnalysisUsage &AU) const {
527 AU.addRequired<SlotIndexes>();
528 MachineFunctionPass::getAnalysisUsage(AU);
531 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
532 LLVM_DUMP_METHOD void StackColoring::dumpBV(const char *tag,
533 const BitVector &BV) const {
534 dbgs() << tag << " : { ";
535 for (unsigned I = 0, E = BV.size(); I != E; ++I)
536 dbgs() << BV.test(I) << " ";
540 LLVM_DUMP_METHOD void StackColoring::dumpBB(MachineBasicBlock *MBB) const {
541 LivenessMap::const_iterator BI = BlockLiveness.find(MBB);
542 assert(BI != BlockLiveness.end() && "Block not found");
543 const BlockLifetimeInfo &BlockInfo = BI->second;
545 dumpBV("BEGIN", BlockInfo.Begin);
546 dumpBV("END", BlockInfo.End);
547 dumpBV("LIVE_IN", BlockInfo.LiveIn);
548 dumpBV("LIVE_OUT", BlockInfo.LiveOut);
551 LLVM_DUMP_METHOD void StackColoring::dump() const {
552 for (MachineBasicBlock *MBB : depth_first(MF)) {
553 dbgs() << "Inspecting block #" << MBB->getNumber() << " ["
554 << MBB->getName() << "]\n";
559 LLVM_DUMP_METHOD void StackColoring::dumpIntervals() const {
560 for (unsigned I = 0, E = Intervals.size(); I != E; ++I) {
561 dbgs() << "Interval[" << I << "]:\n";
562 Intervals[I]->dump();
567 static inline int getStartOrEndSlot(const MachineInstr &MI)
569 assert((MI.getOpcode() == TargetOpcode::LIFETIME_START ||
570 MI.getOpcode() == TargetOpcode::LIFETIME_END) &&
571 "Expected LIFETIME_START or LIFETIME_END op");
572 const MachineOperand &MO = MI.getOperand(0);
573 int Slot = MO.getIndex();
579 // At the moment the only way to end a variable lifetime is with
580 // a VARIABLE_LIFETIME op (which can't contain a start). If things
581 // change and the IR allows for a single inst that both begins
582 // and ends lifetime(s), this interface will need to be reworked.
583 bool StackColoring::isLifetimeStartOrEnd(const MachineInstr &MI,
584 SmallVector<int, 4> &slots,
586 if (MI.getOpcode() == TargetOpcode::LIFETIME_START ||
587 MI.getOpcode() == TargetOpcode::LIFETIME_END) {
588 int Slot = getStartOrEndSlot(MI);
591 if (!InterestingSlots.test(Slot))
593 slots.push_back(Slot);
594 if (MI.getOpcode() == TargetOpcode::LIFETIME_END) {
598 if (!applyFirstUse(Slot)) {
602 } else if (LifetimeStartOnFirstUse && !ProtectFromEscapedAllocas) {
603 if (!MI.isDebugInstr()) {
605 for (const MachineOperand &MO : MI.operands()) {
608 int Slot = MO.getIndex();
611 if (InterestingSlots.test(Slot) && applyFirstUse(Slot)) {
612 slots.push_back(Slot);
625 unsigned StackColoring::collectMarkers(unsigned NumSlot) {
626 unsigned MarkersFound = 0;
627 BlockBitVecMap SeenStartMap;
628 InterestingSlots.clear();
629 InterestingSlots.resize(NumSlot);
630 ConservativeSlots.clear();
631 ConservativeSlots.resize(NumSlot);
633 // number of start and end lifetime ops for each slot
634 SmallVector<int, 8> NumStartLifetimes(NumSlot, 0);
635 SmallVector<int, 8> NumEndLifetimes(NumSlot, 0);
637 // Step 1: collect markers and populate the "InterestingSlots"
638 // and "ConservativeSlots" sets.
639 for (MachineBasicBlock *MBB : depth_first(MF)) {
640 // Compute the set of slots for which we've seen a START marker but have
641 // not yet seen an END marker at this point in the walk (e.g. on entry
643 BitVector BetweenStartEnd;
644 BetweenStartEnd.resize(NumSlot);
645 for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(),
646 PE = MBB->pred_end(); PI != PE; ++PI) {
647 BlockBitVecMap::const_iterator I = SeenStartMap.find(*PI);
648 if (I != SeenStartMap.end()) {
649 BetweenStartEnd |= I->second;
653 // Walk the instructions in the block to look for start/end ops.
654 for (MachineInstr &MI : *MBB) {
655 if (MI.getOpcode() == TargetOpcode::LIFETIME_START ||
656 MI.getOpcode() == TargetOpcode::LIFETIME_END) {
657 int Slot = getStartOrEndSlot(MI);
660 InterestingSlots.set(Slot);
661 if (MI.getOpcode() == TargetOpcode::LIFETIME_START) {
662 BetweenStartEnd.set(Slot);
663 NumStartLifetimes[Slot] += 1;
665 BetweenStartEnd.reset(Slot);
666 NumEndLifetimes[Slot] += 1;
668 const AllocaInst *Allocation = MFI->getObjectAllocation(Slot);
670 LLVM_DEBUG(dbgs() << "Found a lifetime ");
671 LLVM_DEBUG(dbgs() << (MI.getOpcode() == TargetOpcode::LIFETIME_START
674 LLVM_DEBUG(dbgs() << " marker for slot #" << Slot);
676 << " with allocation: " << Allocation->getName() << "\n");
678 Markers.push_back(&MI);
681 for (const MachineOperand &MO : MI.operands()) {
684 int Slot = MO.getIndex();
687 if (! BetweenStartEnd.test(Slot)) {
688 ConservativeSlots.set(Slot);
693 BitVector &SeenStart = SeenStartMap[MBB];
694 SeenStart |= BetweenStartEnd;
700 // PR27903: slots with multiple start or end lifetime ops are not
701 // safe to enable for "lifetime-start-on-first-use".
702 for (unsigned slot = 0; slot < NumSlot; ++slot)
703 if (NumStartLifetimes[slot] > 1 || NumEndLifetimes[slot] > 1)
704 ConservativeSlots.set(slot);
705 LLVM_DEBUG(dumpBV("Conservative slots", ConservativeSlots));
707 // Step 2: compute begin/end sets for each block
709 // NOTE: We use a depth-first iteration to ensure that we obtain a
710 // deterministic numbering.
711 for (MachineBasicBlock *MBB : depth_first(MF)) {
712 // Assign a serial number to this basic block.
713 BasicBlocks[MBB] = BasicBlockNumbering.size();
714 BasicBlockNumbering.push_back(MBB);
716 // Keep a reference to avoid repeated lookups.
717 BlockLifetimeInfo &BlockInfo = BlockLiveness[MBB];
719 BlockInfo.Begin.resize(NumSlot);
720 BlockInfo.End.resize(NumSlot);
722 SmallVector<int, 4> slots;
723 for (MachineInstr &MI : *MBB) {
724 bool isStart = false;
726 if (isLifetimeStartOrEnd(MI, slots, isStart)) {
728 assert(slots.size() == 1 && "unexpected: MI ends multiple slots");
730 if (BlockInfo.Begin.test(Slot)) {
731 BlockInfo.Begin.reset(Slot);
733 BlockInfo.End.set(Slot);
735 for (auto Slot : slots) {
736 LLVM_DEBUG(dbgs() << "Found a use of slot #" << Slot);
738 << " at " << printMBBReference(*MBB) << " index ");
739 LLVM_DEBUG(Indexes->getInstructionIndex(MI).print(dbgs()));
740 const AllocaInst *Allocation = MFI->getObjectAllocation(Slot);
743 << " with allocation: " << Allocation->getName());
745 LLVM_DEBUG(dbgs() << "\n");
746 if (BlockInfo.End.test(Slot)) {
747 BlockInfo.End.reset(Slot);
749 BlockInfo.Begin.set(Slot);
756 // Update statistics.
757 NumMarkerSeen += MarkersFound;
761 void StackColoring::calculateLocalLiveness() {
762 unsigned NumIters = 0;
768 for (const MachineBasicBlock *BB : BasicBlockNumbering) {
769 // Use an iterator to avoid repeated lookups.
770 LivenessMap::iterator BI = BlockLiveness.find(BB);
771 assert(BI != BlockLiveness.end() && "Block not found");
772 BlockLifetimeInfo &BlockInfo = BI->second;
774 // Compute LiveIn by unioning together the LiveOut sets of all preds.
775 BitVector LocalLiveIn;
776 for (MachineBasicBlock::const_pred_iterator PI = BB->pred_begin(),
777 PE = BB->pred_end(); PI != PE; ++PI) {
778 LivenessMap::const_iterator I = BlockLiveness.find(*PI);
779 // PR37130: transformations prior to stack coloring can
780 // sometimes leave behind statically unreachable blocks; these
781 // can be safely skipped here.
782 if (I != BlockLiveness.end())
783 LocalLiveIn |= I->second.LiveOut;
786 // Compute LiveOut by subtracting out lifetimes that end in this
787 // block, then adding in lifetimes that begin in this block. If
788 // we have both BEGIN and END markers in the same basic block
789 // then we know that the BEGIN marker comes after the END,
790 // because we already handle the case where the BEGIN comes
791 // before the END when collecting the markers (and building the
792 // BEGIN/END vectors).
793 BitVector LocalLiveOut = LocalLiveIn;
794 LocalLiveOut.reset(BlockInfo.End);
795 LocalLiveOut |= BlockInfo.Begin;
797 // Update block LiveIn set, noting whether it has changed.
798 if (LocalLiveIn.test(BlockInfo.LiveIn)) {
800 BlockInfo.LiveIn |= LocalLiveIn;
803 // Update block LiveOut set, noting whether it has changed.
804 if (LocalLiveOut.test(BlockInfo.LiveOut)) {
806 BlockInfo.LiveOut |= LocalLiveOut;
811 NumIterations = NumIters;
814 void StackColoring::calculateLiveIntervals(unsigned NumSlots) {
815 SmallVector<SlotIndex, 16> Starts;
816 SmallVector<bool, 16> DefinitelyInUse;
818 // For each block, find which slots are active within this block
819 // and update the live intervals.
820 for (const MachineBasicBlock &MBB : *MF) {
822 Starts.resize(NumSlots);
823 DefinitelyInUse.clear();
824 DefinitelyInUse.resize(NumSlots);
826 // Start the interval of the slots that we previously found to be 'in-use'.
827 BlockLifetimeInfo &MBBLiveness = BlockLiveness[&MBB];
828 for (int pos = MBBLiveness.LiveIn.find_first(); pos != -1;
829 pos = MBBLiveness.LiveIn.find_next(pos)) {
830 Starts[pos] = Indexes->getMBBStartIdx(&MBB);
833 // Create the interval for the basic blocks containing lifetime begin/end.
834 for (const MachineInstr &MI : MBB) {
835 SmallVector<int, 4> slots;
836 bool IsStart = false;
837 if (!isLifetimeStartOrEnd(MI, slots, IsStart))
839 SlotIndex ThisIndex = Indexes->getInstructionIndex(MI);
840 for (auto Slot : slots) {
842 // If a slot is already definitely in use, we don't have to emit
843 // a new start marker because there is already a pre-existing
845 if (!DefinitelyInUse[Slot]) {
846 LiveStarts[Slot].push_back(ThisIndex);
847 DefinitelyInUse[Slot] = true;
849 if (!Starts[Slot].isValid())
850 Starts[Slot] = ThisIndex;
852 if (Starts[Slot].isValid()) {
853 VNInfo *VNI = Intervals[Slot]->getValNumInfo(0);
854 Intervals[Slot]->addSegment(
855 LiveInterval::Segment(Starts[Slot], ThisIndex, VNI));
856 Starts[Slot] = SlotIndex(); // Invalidate the start index
857 DefinitelyInUse[Slot] = false;
863 // Finish up started segments
864 for (unsigned i = 0; i < NumSlots; ++i) {
865 if (!Starts[i].isValid())
868 SlotIndex EndIdx = Indexes->getMBBEndIdx(&MBB);
869 VNInfo *VNI = Intervals[i]->getValNumInfo(0);
870 Intervals[i]->addSegment(LiveInterval::Segment(Starts[i], EndIdx, VNI));
875 bool StackColoring::removeAllMarkers() {
877 for (MachineInstr *MI : Markers) {
878 MI->eraseFromParent();
883 LLVM_DEBUG(dbgs() << "Removed " << Count << " markers.\n");
887 void StackColoring::remapInstructions(DenseMap<int, int> &SlotRemap) {
888 unsigned FixedInstr = 0;
889 unsigned FixedMemOp = 0;
890 unsigned FixedDbg = 0;
892 // Remap debug information that refers to stack slots.
893 for (auto &VI : MF->getVariableDbgInfo()) {
896 if (SlotRemap.count(VI.Slot)) {
897 LLVM_DEBUG(dbgs() << "Remapping debug info for ["
898 << cast<DILocalVariable>(VI.Var)->getName() << "].\n");
899 VI.Slot = SlotRemap[VI.Slot];
904 // Keep a list of *allocas* which need to be remapped.
905 DenseMap<const AllocaInst*, const AllocaInst*> Allocas;
907 // Keep a list of allocas which has been affected by the remap.
908 SmallPtrSet<const AllocaInst*, 32> MergedAllocas;
910 for (const std::pair<int, int> &SI : SlotRemap) {
911 const AllocaInst *From = MFI->getObjectAllocation(SI.first);
912 const AllocaInst *To = MFI->getObjectAllocation(SI.second);
913 assert(To && From && "Invalid allocation object");
916 // AA might be used later for instruction scheduling, and we need it to be
917 // able to deduce the correct aliasing releationships between pointers
918 // derived from the alloca being remapped and the target of that remapping.
919 // The only safe way, without directly informing AA about the remapping
920 // somehow, is to directly update the IR to reflect the change being made
922 Instruction *Inst = const_cast<AllocaInst *>(To);
923 if (From->getType() != To->getType()) {
924 BitCastInst *Cast = new BitCastInst(Inst, From->getType());
925 Cast->insertAfter(Inst);
929 // We keep both slots to maintain AliasAnalysis metadata later.
930 MergedAllocas.insert(From);
931 MergedAllocas.insert(To);
933 // Transfer the stack protector layout tag, but make sure that SSPLK_AddrOf
934 // does not overwrite SSPLK_SmallArray or SSPLK_LargeArray, and make sure
935 // that SSPLK_SmallArray does not overwrite SSPLK_LargeArray.
936 MachineFrameInfo::SSPLayoutKind FromKind
937 = MFI->getObjectSSPLayout(SI.first);
938 MachineFrameInfo::SSPLayoutKind ToKind = MFI->getObjectSSPLayout(SI.second);
939 if (FromKind != MachineFrameInfo::SSPLK_None &&
940 (ToKind == MachineFrameInfo::SSPLK_None ||
941 (ToKind != MachineFrameInfo::SSPLK_LargeArray &&
942 FromKind != MachineFrameInfo::SSPLK_AddrOf)))
943 MFI->setObjectSSPLayout(SI.second, FromKind);
945 // The new alloca might not be valid in a llvm.dbg.declare for this
946 // variable, so undef out the use to make the verifier happy.
947 AllocaInst *FromAI = const_cast<AllocaInst *>(From);
948 if (FromAI->isUsedByMetadata())
949 ValueAsMetadata::handleRAUW(FromAI, UndefValue::get(FromAI->getType()));
950 for (auto &Use : FromAI->uses()) {
951 if (BitCastInst *BCI = dyn_cast<BitCastInst>(Use.get()))
952 if (BCI->isUsedByMetadata())
953 ValueAsMetadata::handleRAUW(BCI, UndefValue::get(BCI->getType()));
956 // Note that this will not replace uses in MMOs (which we'll update below),
957 // or anywhere else (which is why we won't delete the original
959 FromAI->replaceAllUsesWith(Inst);
962 // Remap all instructions to the new stack slots.
963 std::vector<std::vector<MachineMemOperand *>> SSRefs(MFI->getObjectIndexEnd());
964 for (MachineBasicBlock &BB : *MF)
965 for (MachineInstr &I : BB) {
966 // Skip lifetime markers. We'll remove them soon.
967 if (I.getOpcode() == TargetOpcode::LIFETIME_START ||
968 I.getOpcode() == TargetOpcode::LIFETIME_END)
971 // Update the MachineMemOperand to use the new alloca.
972 for (MachineMemOperand *MMO : I.memoperands()) {
973 // We've replaced IR-level uses of the remapped allocas, so we only
974 // need to replace direct uses here.
975 const AllocaInst *AI = dyn_cast_or_null<AllocaInst>(MMO->getValue());
979 if (!Allocas.count(AI))
982 MMO->setValue(Allocas[AI]);
986 // Update all of the machine instruction operands.
987 for (MachineOperand &MO : I.operands()) {
990 int FromSlot = MO.getIndex();
992 // Don't touch arguments.
996 // Only look at mapped slots.
997 if (!SlotRemap.count(FromSlot))
1000 // In a debug build, check that the instruction that we are modifying is
1001 // inside the expected live range. If the instruction is not inside
1002 // the calculated range then it means that the alloca usage moved
1003 // outside of the lifetime markers, or that the user has a bug.
1004 // NOTE: Alloca address calculations which happen outside the lifetime
1005 // zone are okay, despite the fact that we don't have a good way
1006 // for validating all of the usages of the calculation.
1008 bool TouchesMemory = I.mayLoadOrStore();
1009 // If we *don't* protect the user from escaped allocas, don't bother
1010 // validating the instructions.
1011 if (!I.isDebugInstr() && TouchesMemory && ProtectFromEscapedAllocas) {
1012 SlotIndex Index = Indexes->getInstructionIndex(I);
1013 const LiveInterval *Interval = &*Intervals[FromSlot];
1014 assert(Interval->find(Index) != Interval->end() &&
1015 "Found instruction usage outside of live range.");
1019 // Fix the machine instructions.
1020 int ToSlot = SlotRemap[FromSlot];
1021 MO.setIndex(ToSlot);
1025 // We adjust AliasAnalysis information for merged stack slots.
1026 SmallVector<MachineMemOperand *, 2> NewMMOs;
1027 bool ReplaceMemOps = false;
1028 for (MachineMemOperand *MMO : I.memoperands()) {
1029 // Collect MachineMemOperands which reference
1030 // FixedStackPseudoSourceValues with old frame indices.
1031 if (const auto *FSV = dyn_cast_or_null<FixedStackPseudoSourceValue>(
1032 MMO->getPseudoValue())) {
1033 int FI = FSV->getFrameIndex();
1034 auto To = SlotRemap.find(FI);
1035 if (To != SlotRemap.end())
1036 SSRefs[FI].push_back(MMO);
1039 // If this memory location can be a slot remapped here,
1040 // we remove AA information.
1041 bool MayHaveConflictingAAMD = false;
1042 if (MMO->getAAInfo()) {
1043 if (const Value *MMOV = MMO->getValue()) {
1044 SmallVector<Value *, 4> Objs;
1045 getUnderlyingObjectsForCodeGen(MMOV, Objs, MF->getDataLayout());
1048 MayHaveConflictingAAMD = true;
1050 for (Value *V : Objs) {
1051 // If this memory location comes from a known stack slot
1052 // that is not remapped, we continue checking.
1053 // Otherwise, we need to invalidate AA infomation.
1054 const AllocaInst *AI = dyn_cast_or_null<AllocaInst>(V);
1055 if (AI && MergedAllocas.count(AI)) {
1056 MayHaveConflictingAAMD = true;
1062 if (MayHaveConflictingAAMD) {
1063 NewMMOs.push_back(MF->getMachineMemOperand(MMO, AAMDNodes()));
1064 ReplaceMemOps = true;
1066 NewMMOs.push_back(MMO);
1070 // If any memory operand is updated, set memory references of
1071 // this instruction.
1073 I.setMemRefs(*MF, NewMMOs);
1076 // Rewrite MachineMemOperands that reference old frame indices.
1077 for (auto E : enumerate(SSRefs)) {
1078 const PseudoSourceValue *NewSV =
1079 MF->getPSVManager().getFixedStack(SlotRemap[E.index()]);
1080 for (MachineMemOperand *Ref : E.value())
1081 Ref->setValue(NewSV);
1084 // Update the location of C++ catch objects for the MSVC personality routine.
1085 if (WinEHFuncInfo *EHInfo = MF->getWinEHFuncInfo())
1086 for (WinEHTryBlockMapEntry &TBME : EHInfo->TryBlockMap)
1087 for (WinEHHandlerType &H : TBME.HandlerArray)
1088 if (H.CatchObj.FrameIndex != std::numeric_limits<int>::max() &&
1089 SlotRemap.count(H.CatchObj.FrameIndex))
1090 H.CatchObj.FrameIndex = SlotRemap[H.CatchObj.FrameIndex];
1092 LLVM_DEBUG(dbgs() << "Fixed " << FixedMemOp << " machine memory operands.\n");
1093 LLVM_DEBUG(dbgs() << "Fixed " << FixedDbg << " debug locations.\n");
1094 LLVM_DEBUG(dbgs() << "Fixed " << FixedInstr << " machine instructions.\n");
1097 void StackColoring::removeInvalidSlotRanges() {
1098 for (MachineBasicBlock &BB : *MF)
1099 for (MachineInstr &I : BB) {
1100 if (I.getOpcode() == TargetOpcode::LIFETIME_START ||
1101 I.getOpcode() == TargetOpcode::LIFETIME_END || I.isDebugInstr())
1104 // Some intervals are suspicious! In some cases we find address
1105 // calculations outside of the lifetime zone, but not actual memory
1106 // read or write. Memory accesses outside of the lifetime zone are a clear
1107 // violation, but address calculations are okay. This can happen when
1108 // GEPs are hoisted outside of the lifetime zone.
1109 // So, in here we only check instructions which can read or write memory.
1110 if (!I.mayLoad() && !I.mayStore())
1113 // Check all of the machine operands.
1114 for (const MachineOperand &MO : I.operands()) {
1118 int Slot = MO.getIndex();
1123 if (Intervals[Slot]->empty())
1126 // Check that the used slot is inside the calculated lifetime range.
1127 // If it is not, warn about it and invalidate the range.
1128 LiveInterval *Interval = &*Intervals[Slot];
1129 SlotIndex Index = Indexes->getInstructionIndex(I);
1130 if (Interval->find(Index) == Interval->end()) {
1132 LLVM_DEBUG(dbgs() << "Invalidating range #" << Slot << "\n");
1139 void StackColoring::expungeSlotMap(DenseMap<int, int> &SlotRemap,
1140 unsigned NumSlots) {
1141 // Expunge slot remap map.
1142 for (unsigned i=0; i < NumSlots; ++i) {
1143 // If we are remapping i
1144 if (SlotRemap.count(i)) {
1145 int Target = SlotRemap[i];
1146 // As long as our target is mapped to something else, follow it.
1147 while (SlotRemap.count(Target)) {
1148 Target = SlotRemap[Target];
1149 SlotRemap[i] = Target;
1155 bool StackColoring::runOnMachineFunction(MachineFunction &Func) {
1156 LLVM_DEBUG(dbgs() << "********** Stack Coloring **********\n"
1157 << "********** Function: " << Func.getName() << '\n');
1159 MFI = &MF->getFrameInfo();
1160 Indexes = &getAnalysis<SlotIndexes>();
1161 BlockLiveness.clear();
1162 BasicBlocks.clear();
1163 BasicBlockNumbering.clear();
1167 VNInfoAllocator.Reset();
1169 unsigned NumSlots = MFI->getObjectIndexEnd();
1171 // If there are no stack slots then there are no markers to remove.
1175 SmallVector<int, 8> SortedSlots;
1176 SortedSlots.reserve(NumSlots);
1177 Intervals.reserve(NumSlots);
1178 LiveStarts.resize(NumSlots);
1180 unsigned NumMarkers = collectMarkers(NumSlots);
1182 unsigned TotalSize = 0;
1183 LLVM_DEBUG(dbgs() << "Found " << NumMarkers << " markers and " << NumSlots
1185 LLVM_DEBUG(dbgs() << "Slot structure:\n");
1187 for (int i=0; i < MFI->getObjectIndexEnd(); ++i) {
1188 LLVM_DEBUG(dbgs() << "Slot #" << i << " - " << MFI->getObjectSize(i)
1190 TotalSize += MFI->getObjectSize(i);
1193 LLVM_DEBUG(dbgs() << "Total Stack size: " << TotalSize << " bytes\n\n");
1195 // Don't continue because there are not enough lifetime markers, or the
1196 // stack is too small, or we are told not to optimize the slots.
1197 if (NumMarkers < 2 || TotalSize < 16 || DisableColoring ||
1198 skipFunction(Func.getFunction())) {
1199 LLVM_DEBUG(dbgs() << "Will not try to merge slots.\n");
1200 return removeAllMarkers();
1203 for (unsigned i=0; i < NumSlots; ++i) {
1204 std::unique_ptr<LiveInterval> LI(new LiveInterval(i, 0));
1205 LI->getNextValue(Indexes->getZeroIndex(), VNInfoAllocator);
1206 Intervals.push_back(std::move(LI));
1207 SortedSlots.push_back(i);
1210 // Calculate the liveness of each block.
1211 calculateLocalLiveness();
1212 LLVM_DEBUG(dbgs() << "Dataflow iterations: " << NumIterations << "\n");
1215 // Propagate the liveness information.
1216 calculateLiveIntervals(NumSlots);
1217 LLVM_DEBUG(dumpIntervals());
1219 // Search for allocas which are used outside of the declared lifetime
1221 if (ProtectFromEscapedAllocas)
1222 removeInvalidSlotRanges();
1224 // Maps old slots to new slots.
1225 DenseMap<int, int> SlotRemap;
1226 unsigned RemovedSlots = 0;
1227 unsigned ReducedSize = 0;
1229 // Do not bother looking at empty intervals.
1230 for (unsigned I = 0; I < NumSlots; ++I) {
1231 if (Intervals[SortedSlots[I]]->empty())
1232 SortedSlots[I] = -1;
1235 // This is a simple greedy algorithm for merging allocas. First, sort the
1236 // slots, placing the largest slots first. Next, perform an n^2 scan and look
1237 // for disjoint slots. When you find disjoint slots, merge the samller one
1238 // into the bigger one and update the live interval. Remove the small alloca
1241 // Sort the slots according to their size. Place unused slots at the end.
1242 // Use stable sort to guarantee deterministic code generation.
1243 llvm::stable_sort(SortedSlots, [this](int LHS, int RHS) {
1244 // We use -1 to denote a uninteresting slot. Place these slots at the end.
1249 // Sort according to size.
1250 return MFI->getObjectSize(LHS) > MFI->getObjectSize(RHS);
1253 for (auto &s : LiveStarts)
1256 bool Changed = true;
1259 for (unsigned I = 0; I < NumSlots; ++I) {
1260 if (SortedSlots[I] == -1)
1263 for (unsigned J=I+1; J < NumSlots; ++J) {
1264 if (SortedSlots[J] == -1)
1267 int FirstSlot = SortedSlots[I];
1268 int SecondSlot = SortedSlots[J];
1269 LiveInterval *First = &*Intervals[FirstSlot];
1270 LiveInterval *Second = &*Intervals[SecondSlot];
1271 auto &FirstS = LiveStarts[FirstSlot];
1272 auto &SecondS = LiveStarts[SecondSlot];
1273 assert(!First->empty() && !Second->empty() && "Found an empty range");
1275 // Merge disjoint slots. This is a little bit tricky - see the
1276 // Implementation Notes section for an explanation.
1277 if (!First->isLiveAtIndexes(SecondS) &&
1278 !Second->isLiveAtIndexes(FirstS)) {
1280 First->MergeSegmentsInAsValue(*Second, First->getValNumInfo(0));
1282 int OldSize = FirstS.size();
1283 FirstS.append(SecondS.begin(), SecondS.end());
1284 auto Mid = FirstS.begin() + OldSize;
1285 std::inplace_merge(FirstS.begin(), Mid, FirstS.end());
1287 SlotRemap[SecondSlot] = FirstSlot;
1288 SortedSlots[J] = -1;
1289 LLVM_DEBUG(dbgs() << "Merging #" << FirstSlot << " and slots #"
1290 << SecondSlot << " together.\n");
1291 unsigned MaxAlignment = std::max(MFI->getObjectAlignment(FirstSlot),
1292 MFI->getObjectAlignment(SecondSlot));
1294 assert(MFI->getObjectSize(FirstSlot) >=
1295 MFI->getObjectSize(SecondSlot) &&
1296 "Merging a small object into a larger one");
1299 ReducedSize += MFI->getObjectSize(SecondSlot);
1300 MFI->setObjectAlignment(FirstSlot, MaxAlignment);
1301 MFI->RemoveStackObject(SecondSlot);
1307 // Record statistics.
1308 StackSpaceSaved += ReducedSize;
1309 StackSlotMerged += RemovedSlots;
1310 LLVM_DEBUG(dbgs() << "Merge " << RemovedSlots << " slots. Saved "
1311 << ReducedSize << " bytes\n");
1313 // Scan the entire function and update all machine operands that use frame
1314 // indices to use the remapped frame index.
1315 expungeSlotMap(SlotRemap, NumSlots);
1316 remapInstructions(SlotRemap);
1318 return removeAllMarkers();