1//===- StackColoring.cpp --------------------------------------------------===//
2//
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
6//
7//===----------------------------------------------------------------------===//
8//
9// This pass implements the stack-coloring optimization that looks for
10// lifetime markers machine instructions (LIFETIME_START and LIFETIME_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.
14//
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
17// offsets.
18// 2. Merge this pass with StackSlotColoring and allow merging of allocas with
19// spill slots.
20//
21//===----------------------------------------------------------------------===//
22
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/PseudoSourceValueManager.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/Instructions.h"
47#include "llvm/IR/Metadata.h"
48#include "llvm/IR/Use.h"
49#include "llvm/IR/Value.h"
50#include "llvm/InitializePasses.h"
51#include "llvm/Pass.h"
52#include "llvm/Support/Casting.h"
53#include "llvm/Support/CommandLine.h"
54#include "llvm/Support/Compiler.h"
55#include "llvm/Support/Debug.h"
56#include "llvm/Support/raw_ostream.h"
57#include <algorithm>
58#include <cassert>
59#include <limits>
60#include <memory>
61#include <utility>
62
63using namespace llvm;
64
65#define DEBUG_TYPE "stack-coloring"
66
67static cl::opt<bool>
68DisableColoring("no-stack-coloring",
69 cl::init(Val: false), cl::Hidden,
70 cl::desc("Disable stack coloring"));
71
72/// The user may write code that uses allocas outside of the declared lifetime
73/// zone. This can happen when the user returns a reference to a local
74/// data-structure. We can detect these cases and decide not to optimize the
75/// code. If this flag is enabled, we try to save the user. This option
76/// is treated as overriding LifetimeStartOnFirstUse below.
77static cl::opt<bool>
78ProtectFromEscapedAllocas("protect-from-escaped-allocas",
79 cl::init(Val: false), cl::Hidden,
80 cl::desc("Do not optimize lifetime zones that "
81 "are broken"));
82
83/// Enable enhanced dataflow scheme for lifetime analysis (treat first
84/// use of stack slot as start of slot lifetime, as opposed to looking
85/// for LIFETIME_START marker). See "Implementation notes" below for
86/// more info.
87static cl::opt<bool>
88LifetimeStartOnFirstUse("stackcoloring-lifetime-start-on-first-use",
89 cl::init(Val: true), cl::Hidden,
90 cl::desc("Treat stack lifetimes as starting on first use, not on START marker."));
91
92
93STATISTIC(NumMarkerSeen, "Number of lifetime markers found.");
94STATISTIC(StackSpaceSaved, "Number of bytes saved due to merging slots.");
95STATISTIC(StackSlotMerged, "Number of stack slot merged.");
96STATISTIC(EscapedAllocas, "Number of allocas that escaped the lifetime region");
97
98//===----------------------------------------------------------------------===//
99// StackColoring Pass
100//===----------------------------------------------------------------------===//
101//
102// Stack Coloring reduces stack usage by merging stack slots when they
103// can't be used together. For example, consider the following C program:
104//
105// void bar(char *, int);
106// void foo(bool var) {
107// A: {
108// char z[4096];
109// bar(z, 0);
110// }
111//
112// char *p;
113// char x[4096];
114// char y[4096];
115// if (var) {
116// p = x;
117// } else {
118// bar(y, 1);
119// p = y + 1024;
120// }
121// B:
122// bar(p, 2);
123// }
124//
125// Naively-compiled, this program would use 12k of stack space. However, the
126// stack slot corresponding to `z` is always destroyed before either of the
127// stack slots for `x` or `y` are used, and then `x` is only used if `var`
128// is true, while `y` is only used if `var` is false. So in no time are 2
129// of the stack slots used together, and therefore we can merge them,
130// compiling the function using only a single 4k alloca:
131//
132// void foo(bool var) { // equivalent
133// char x[4096];
134// char *p;
135// bar(x, 0);
136// if (var) {
137// p = x;
138// } else {
139// bar(x, 1);
140// p = x + 1024;
141// }
142// bar(p, 2);
143// }
144//
145// This is an important optimization if we want stack space to be under
146// control in large functions, both open-coded ones and ones created by
147// inlining.
148//
149// Implementation Notes:
150// ---------------------
151//
152// An important part of the above reasoning is that `z` can't be accessed
153// while the latter 2 calls to `bar` are running. This is justified because
154// `z`'s lifetime is over after we exit from block `A:`, so any further
155// accesses to it would be UB. The way we represent this information
156// in LLVM is by having frontends delimit blocks with `lifetime.start`
157// and `lifetime.end` intrinsics.
158//
159// The effect of these intrinsics seems to be as follows (maybe I should
160// specify this in the reference?):
161//
162// L1) at start, each stack-slot is marked as *out-of-scope*, unless no
163// lifetime intrinsic refers to that stack slot, in which case
164// it is marked as *in-scope*.
165// L2) on a `lifetime.start`, a stack slot is marked as *in-scope* and
166// the stack slot is overwritten with `undef`.
167// L3) on a `lifetime.end`, a stack slot is marked as *out-of-scope*.
168// L4) on function exit, all stack slots are marked as *out-of-scope*.
169// L5) `lifetime.end` is a no-op when called on a slot that is already
170// *out-of-scope*.
171// L6) memory accesses to *out-of-scope* stack slots are UB.
172// L7) when a stack-slot is marked as *out-of-scope*, all pointers to it
173// are invalidated, unless the slot is "degenerate". This is used to
174// justify not marking slots as in-use until the pointer to them is
175// used, but feels a bit hacky in the presence of things like LICM. See
176// the "Degenerate Slots" section for more details.
177//
178// Now, let's ground stack coloring on these rules. We'll define a slot
179// as *in-use* at a (dynamic) point in execution if it either can be
180// written to at that point, or if it has a live and non-undef content
181// at that point.
182//
183// Obviously, slots that are never *in-use* together can be merged, and
184// in our example `foo`, the slots for `x`, `y` and `z` are never
185// in-use together (of course, sometimes slots that *are* in-use together
186// might still be mergable, but we don't care about that here).
187//
188// In this implementation, we successively merge pairs of slots that are
189// not *in-use* together. We could be smarter - for example, we could merge
190// a single large slot with 2 small slots, or we could construct the
191// interference graph and run a "smart" graph coloring algorithm, but with
192// that aside, how do we find out whether a pair of slots might be *in-use*
193// together?
194//
195// From our rules, we see that *out-of-scope* slots are never *in-use*,
196// and from (L7) we see that "non-degenerate" slots remain non-*in-use*
197// until their address is taken. Therefore, we can approximate slot activity
198// using dataflow.
199//
200// A subtle point: naively, we might try to figure out which pairs of
201// stack-slots interfere by propagating `S in-use` through the CFG for every
202// stack-slot `S`, and having `S` and `T` interfere if there is a CFG point in
203// which they are both *in-use*.
204//
205// That is sound, but overly conservative in some cases: in our (artificial)
206// example `foo`, either `x` or `y` might be in use at the label `B:`, but
207// as `x` is only in use if we came in from the `var` edge and `y` only
208// if we came from the `!var` edge, they still can't be in use together.
209// See PR32488 for an important real-life case.
210//
211// If we wanted to find all points of interference precisely, we could
212// propagate `S in-use` and `S&T in-use` predicates through the CFG. That
213// would be precise, but requires propagating `O(n^2)` dataflow facts.
214//
215// However, we aren't interested in the *set* of points of interference
216// between 2 stack slots, only *whether* there *is* such a point. So we
217// can rely on a little trick: for `S` and `T` to be in-use together,
218// one of them needs to become in-use while the other is in-use (or
219// they might both become in use simultaneously). We can check this
220// by also keeping track of the points at which a stack slot might *start*
221// being in-use.
222//
223// Exact first use:
224// ----------------
225//
226// Consider the following motivating example:
227//
228// int foo() {
229// char b1[1024], b2[1024];
230// if (...) {
231// char b3[1024];
232// <uses of b1, b3>;
233// return x;
234// } else {
235// char b4[1024], b5[1024];
236// <uses of b2, b4, b5>;
237// return y;
238// }
239// }
240//
241// In the code above, "b3" and "b4" are declared in distinct lexical
242// scopes, meaning that it is easy to prove that they can share the
243// same stack slot. Variables "b1" and "b2" are declared in the same
244// scope, meaning that from a lexical point of view, their lifetimes
245// overlap. From a control flow pointer of view, however, the two
246// variables are accessed in disjoint regions of the CFG, thus it
247// should be possible for them to share the same stack slot. An ideal
248// stack allocation for the function above would look like:
249//
250// slot 0: b1, b2
251// slot 1: b3, b4
252// slot 2: b5
253//
254// Achieving this allocation is tricky, however, due to the way
255// lifetime markers are inserted. Here is a simplified view of the
256// control flow graph for the code above:
257//
258// +------ block 0 -------+
259// 0| LIFETIME_START b1, b2 |
260// 1| <test 'if' condition> |
261// +-----------------------+
262// ./ \.
263// +------ block 1 -------+ +------ block 2 -------+
264// 2| LIFETIME_START b3 | 5| LIFETIME_START b4, b5 |
265// 3| <uses of b1, b3> | 6| <uses of b2, b4, b5> |
266// 4| LIFETIME_END b3 | 7| LIFETIME_END b4, b5 |
267// +-----------------------+ +-----------------------+
268// \. /.
269// +------ block 3 -------+
270// 8| <cleanupcode> |
271// 9| LIFETIME_END b1, b2 |
272// 10| return |
273// +-----------------------+
274//
275// If we create live intervals for the variables above strictly based
276// on the lifetime markers, we'll get the set of intervals on the
277// left. If we ignore the lifetime start markers and instead treat a
278// variable's lifetime as beginning with the first reference to the
279// var, then we get the intervals on the right.
280//
281// LIFETIME_START First Use
282// b1: [0,9] [3,4] [8,9]
283// b2: [0,9] [6,9]
284// b3: [2,4] [3,4]
285// b4: [5,7] [6,7]
286// b5: [5,7] [6,7]
287//
288// For the intervals on the left, the best we can do is overlap two
289// variables (b3 and b4, for example); this gives us a stack size of
290// 4*1024 bytes, not ideal. When treating first-use as the start of a
291// lifetime, we can additionally overlap b1 and b5, giving us a 3*1024
292// byte stack (better).
293//
294// Degenerate Slots:
295// -----------------
296//
297// Relying entirely on first-use of stack slots is problematic,
298// however, due to the fact that optimizations can sometimes migrate
299// uses of a variable outside of its lifetime start/end region. Here
300// is an example:
301//
302// int bar() {
303// char b1[1024], b2[1024];
304// if (...) {
305// <uses of b2>
306// return y;
307// } else {
308// <uses of b1>
309// while (...) {
310// char b3[1024];
311// <uses of b3>
312// }
313// }
314// }
315//
316// Before optimization, the control flow graph for the code above
317// might look like the following:
318//
319// +------ block 0 -------+
320// 0| LIFETIME_START b1, b2 |
321// 1| <test 'if' condition> |
322// +-----------------------+
323// ./ \.
324// +------ block 1 -------+ +------- block 2 -------+
325// 2| <uses of b2> | 3| <uses of b1> |
326// +-----------------------+ +-----------------------+
327// | |
328// | +------- block 3 -------+ <-\.
329// | 4| <while condition> | |
330// | +-----------------------+ |
331// | / | |
332// | / +------- block 4 -------+
333// \ / 5| LIFETIME_START b3 | |
334// \ / 6| <uses of b3> | |
335// \ / 7| LIFETIME_END b3 | |
336// \ | +------------------------+ |
337// \ | \ /
338// +------ block 5 -----+ \---------------
339// 8| <cleanupcode> |
340// 9| LIFETIME_END b1, b2 |
341// 10| return |
342// +---------------------+
343//
344// During optimization, however, it can happen that an instruction
345// computing an address in "b3" (for example, a loop-invariant GEP) is
346// hoisted up out of the loop from block 4 to block 2. [Note that
347// this is not an actual load from the stack, only an instruction that
348// computes the address to be loaded]. If this happens, there is now a
349// path leading from the first use of b3 to the return instruction
350// that does not encounter the b3 LIFETIME_END, hence b3's lifetime is
351// now larger than if we were computing live intervals strictly based
352// on lifetime markers. In the example above, this lengthened lifetime
353// would mean that it would appear illegal to overlap b3 with b2.
354//
355// To deal with this such cases, the code in ::collectMarkers() below
356// tries to identify "degenerate" slots -- those slots where on a single
357// forward pass through the CFG we encounter a first reference to slot
358// K before we hit the slot K lifetime start marker. For such slots,
359// we fall back on using the lifetime start marker as the beginning of
360// the variable's lifetime. NB: with this implementation, slots can
361// appear degenerate in cases where there is unstructured control flow:
362//
363// if (q) goto mid;
364// if (x > 9) {
365// int b[100];
366// memcpy(&b[0], ...);
367// mid: b[k] = ...;
368// abc(&b);
369// }
370//
371// If in RPO ordering chosen to walk the CFG we happen to visit the b[k]
372// before visiting the memcpy block (which will contain the lifetime start
373// for "b" then it will appear that 'b' has a degenerate lifetime.
374
375namespace {
376
377/// StackColoring - A machine pass for merging disjoint stack allocations,
378/// marked by the LIFETIME_START and LIFETIME_END pseudo instructions.
379class StackColoring : public MachineFunctionPass {
380 MachineFrameInfo *MFI = nullptr;
381 MachineFunction *MF = nullptr;
382
383 /// A class representing liveness information for a single basic block.
384 /// Each bit in the BitVector represents the liveness property
385 /// for a different stack slot.
386 struct BlockLifetimeInfo {
387 /// Which slots BEGINs in each basic block.
388 BitVector Begin;
389
390 /// Which slots ENDs in each basic block.
391 BitVector End;
392
393 /// Which slots are marked as LIVE_IN, coming into each basic block.
394 BitVector LiveIn;
395
396 /// Which slots are marked as LIVE_OUT, coming out of each basic block.
397 BitVector LiveOut;
398 };
399
400 /// Maps active slots (per bit) for each basic block.
401 using LivenessMap = DenseMap<const MachineBasicBlock *, BlockLifetimeInfo>;
402 LivenessMap BlockLiveness;
403
404 /// Maps serial numbers to basic blocks.
405 DenseMap<const MachineBasicBlock *, int> BasicBlocks;
406
407 /// Maps basic blocks to a serial number.
408 SmallVector<const MachineBasicBlock *, 8> BasicBlockNumbering;
409
410 /// Maps slots to their use interval. Outside of this interval, slots
411 /// values are either dead or `undef` and they will not be written to.
412 SmallVector<std::unique_ptr<LiveInterval>, 16> Intervals;
413
414 /// Maps slots to the points where they can become in-use.
415 SmallVector<SmallVector<SlotIndex, 4>, 16> LiveStarts;
416
417 /// VNInfo is used for the construction of LiveIntervals.
418 VNInfo::Allocator VNInfoAllocator;
419
420 /// SlotIndex analysis object.
421 SlotIndexes *Indexes = nullptr;
422
423 /// The list of lifetime markers found. These markers are to be removed
424 /// once the coloring is done.
425 SmallVector<MachineInstr*, 8> Markers;
426
427 /// Record the FI slots for which we have seen some sort of
428 /// lifetime marker (either start or end).
429 BitVector InterestingSlots;
430
431 /// FI slots that need to be handled conservatively (for these
432 /// slots lifetime-start-on-first-use is disabled).
433 BitVector ConservativeSlots;
434
435 /// Number of iterations taken during data flow analysis.
436 unsigned NumIterations;
437
438public:
439 static char ID;
440
441 StackColoring() : MachineFunctionPass(ID) {
442 initializeStackColoringPass(*PassRegistry::getPassRegistry());
443 }
444
445 void getAnalysisUsage(AnalysisUsage &AU) const override;
446 bool runOnMachineFunction(MachineFunction &Func) override;
447
448private:
449 /// Used in collectMarkers
450 using BlockBitVecMap = DenseMap<const MachineBasicBlock *, BitVector>;
451
452 /// Debug.
453 void dump() const;
454 void dumpIntervals() const;
455 void dumpBB(MachineBasicBlock *MBB) const;
456 void dumpBV(const char *tag, const BitVector &BV) const;
457
458 /// Removes all of the lifetime marker instructions from the function.
459 /// \returns true if any markers were removed.
460 bool removeAllMarkers();
461
462 /// Scan the machine function and find all of the lifetime markers.
463 /// Record the findings in the BEGIN and END vectors.
464 /// \returns the number of markers found.
465 unsigned collectMarkers(unsigned NumSlot);
466
467 /// Perform the dataflow calculation and calculate the lifetime for each of
468 /// the slots, based on the BEGIN/END vectors. Set the LifetimeLIVE_IN and
469 /// LifetimeLIVE_OUT maps that represent which stack slots are live coming
470 /// in and out blocks.
471 void calculateLocalLiveness();
472
473 /// Returns TRUE if we're using the first-use-begins-lifetime method for
474 /// this slot (if FALSE, then the start marker is treated as start of lifetime).
475 bool applyFirstUse(int Slot) {
476 if (!LifetimeStartOnFirstUse || ProtectFromEscapedAllocas)
477 return false;
478 if (ConservativeSlots.test(Idx: Slot))
479 return false;
480 return true;
481 }
482
483 /// Examines the specified instruction and returns TRUE if the instruction
484 /// represents the start or end of an interesting lifetime. The slot or slots
485 /// starting or ending are added to the vector "slots" and "isStart" is set
486 /// accordingly.
487 /// \returns True if inst contains a lifetime start or end
488 bool isLifetimeStartOrEnd(const MachineInstr &MI,
489 SmallVector<int, 4> &slots,
490 bool &isStart);
491
492 /// Construct the LiveIntervals for the slots.
493 void calculateLiveIntervals(unsigned NumSlots);
494
495 /// Go over the machine function and change instructions which use stack
496 /// slots to use the joint slots.
497 void remapInstructions(DenseMap<int, int> &SlotRemap);
498
499 /// The input program may contain instructions which are not inside lifetime
500 /// markers. This can happen due to a bug in the compiler or due to a bug in
501 /// user code (for example, returning a reference to a local variable).
502 /// This procedure checks all of the instructions in the function and
503 /// invalidates lifetime ranges which do not contain all of the instructions
504 /// which access that frame slot.
505 void removeInvalidSlotRanges();
506
507 /// Map entries which point to other entries to their destination.
508 /// A->B->C becomes A->C.
509 void expungeSlotMap(DenseMap<int, int> &SlotRemap, unsigned NumSlots);
510};
511
512} // end anonymous namespace
513
514char StackColoring::ID = 0;
515
516char &llvm::StackColoringID = StackColoring::ID;
517
518INITIALIZE_PASS_BEGIN(StackColoring, DEBUG_TYPE,
519 "Merge disjoint stack slots", false, false)
520INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
521INITIALIZE_PASS_END(StackColoring, DEBUG_TYPE,
522 "Merge disjoint stack slots", false, false)
523
524void StackColoring::getAnalysisUsage(AnalysisUsage &AU) const {
525 AU.addRequired<SlotIndexes>();
526 MachineFunctionPass::getAnalysisUsage(AU);
527}
528
529#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
530LLVM_DUMP_METHOD void StackColoring::dumpBV(const char *tag,
531 const BitVector &BV) const {
532 dbgs() << tag << " : { ";
533 for (unsigned I = 0, E = BV.size(); I != E; ++I)
534 dbgs() << BV.test(Idx: I) << " ";
535 dbgs() << "}\n";
536}
537
538LLVM_DUMP_METHOD void StackColoring::dumpBB(MachineBasicBlock *MBB) const {
539 LivenessMap::const_iterator BI = BlockLiveness.find(Val: MBB);
540 assert(BI != BlockLiveness.end() && "Block not found");
541 const BlockLifetimeInfo &BlockInfo = BI->second;
542
543 dumpBV(tag: "BEGIN", BV: BlockInfo.Begin);
544 dumpBV(tag: "END", BV: BlockInfo.End);
545 dumpBV(tag: "LIVE_IN", BV: BlockInfo.LiveIn);
546 dumpBV(tag: "LIVE_OUT", BV: BlockInfo.LiveOut);
547}
548
549LLVM_DUMP_METHOD void StackColoring::dump() const {
550 for (MachineBasicBlock *MBB : depth_first(G: MF)) {
551 dbgs() << "Inspecting block #" << MBB->getNumber() << " ["
552 << MBB->getName() << "]\n";
553 dumpBB(MBB);
554 }
555}
556
557LLVM_DUMP_METHOD void StackColoring::dumpIntervals() const {
558 for (unsigned I = 0, E = Intervals.size(); I != E; ++I) {
559 dbgs() << "Interval[" << I << "]:\n";
560 Intervals[I]->dump();
561 }
562}
563#endif
564
565static inline int getStartOrEndSlot(const MachineInstr &MI)
566{
567 assert((MI.getOpcode() == TargetOpcode::LIFETIME_START ||
568 MI.getOpcode() == TargetOpcode::LIFETIME_END) &&
569 "Expected LIFETIME_START or LIFETIME_END op");
570 const MachineOperand &MO = MI.getOperand(i: 0);
571 int Slot = MO.getIndex();
572 if (Slot >= 0)
573 return Slot;
574 return -1;
575}
576
577// At the moment the only way to end a variable lifetime is with
578// a VARIABLE_LIFETIME op (which can't contain a start). If things
579// change and the IR allows for a single inst that both begins
580// and ends lifetime(s), this interface will need to be reworked.
581bool StackColoring::isLifetimeStartOrEnd(const MachineInstr &MI,
582 SmallVector<int, 4> &slots,
583 bool &isStart) {
584 if (MI.getOpcode() == TargetOpcode::LIFETIME_START ||
585 MI.getOpcode() == TargetOpcode::LIFETIME_END) {
586 int Slot = getStartOrEndSlot(MI);
587 if (Slot < 0)
588 return false;
589 if (!InterestingSlots.test(Idx: Slot))
590 return false;
591 slots.push_back(Elt: Slot);
592 if (MI.getOpcode() == TargetOpcode::LIFETIME_END) {
593 isStart = false;
594 return true;
595 }
596 if (!applyFirstUse(Slot)) {
597 isStart = true;
598 return true;
599 }
600 } else if (LifetimeStartOnFirstUse && !ProtectFromEscapedAllocas) {
601 if (!MI.isDebugInstr()) {
602 bool found = false;
603 for (const MachineOperand &MO : MI.operands()) {
604 if (!MO.isFI())
605 continue;
606 int Slot = MO.getIndex();
607 if (Slot<0)
608 continue;
609 if (InterestingSlots.test(Idx: Slot) && applyFirstUse(Slot)) {
610 slots.push_back(Elt: Slot);
611 found = true;
612 }
613 }
614 if (found) {
615 isStart = true;
616 return true;
617 }
618 }
619 }
620 return false;
621}
622
623unsigned StackColoring::collectMarkers(unsigned NumSlot) {
624 unsigned MarkersFound = 0;
625 BlockBitVecMap SeenStartMap;
626 InterestingSlots.clear();
627 InterestingSlots.resize(N: NumSlot);
628 ConservativeSlots.clear();
629 ConservativeSlots.resize(N: NumSlot);
630
631 // number of start and end lifetime ops for each slot
632 SmallVector<int, 8> NumStartLifetimes(NumSlot, 0);
633 SmallVector<int, 8> NumEndLifetimes(NumSlot, 0);
634
635 // Step 1: collect markers and populate the "InterestingSlots"
636 // and "ConservativeSlots" sets.
637 for (MachineBasicBlock *MBB : depth_first(G: MF)) {
638 // Compute the set of slots for which we've seen a START marker but have
639 // not yet seen an END marker at this point in the walk (e.g. on entry
640 // to this bb).
641 BitVector BetweenStartEnd;
642 BetweenStartEnd.resize(N: NumSlot);
643 for (const MachineBasicBlock *Pred : MBB->predecessors()) {
644 BlockBitVecMap::const_iterator I = SeenStartMap.find(Val: Pred);
645 if (I != SeenStartMap.end()) {
646 BetweenStartEnd |= I->second;
647 }
648 }
649
650 // Walk the instructions in the block to look for start/end ops.
651 for (MachineInstr &MI : *MBB) {
652 if (MI.isDebugInstr())
653 continue;
654 if (MI.getOpcode() == TargetOpcode::LIFETIME_START ||
655 MI.getOpcode() == TargetOpcode::LIFETIME_END) {
656 int Slot = getStartOrEndSlot(MI);
657 if (Slot < 0)
658 continue;
659 InterestingSlots.set(Slot);
660 if (MI.getOpcode() == TargetOpcode::LIFETIME_START) {
661 BetweenStartEnd.set(Slot);
662 NumStartLifetimes[Slot] += 1;
663 } else {
664 BetweenStartEnd.reset(Idx: Slot);
665 NumEndLifetimes[Slot] += 1;
666 }
667 const AllocaInst *Allocation = MFI->getObjectAllocation(ObjectIdx: Slot);
668 if (Allocation) {
669 LLVM_DEBUG(dbgs() << "Found a lifetime ");
670 LLVM_DEBUG(dbgs() << (MI.getOpcode() == TargetOpcode::LIFETIME_START
671 ? "start"
672 : "end"));
673 LLVM_DEBUG(dbgs() << " marker for slot #" << Slot);
674 LLVM_DEBUG(dbgs()
675 << " with allocation: " << Allocation->getName() << "\n");
676 }
677 Markers.push_back(Elt: &MI);
678 MarkersFound += 1;
679 } else {
680 for (const MachineOperand &MO : MI.operands()) {
681 if (!MO.isFI())
682 continue;
683 int Slot = MO.getIndex();
684 if (Slot < 0)
685 continue;
686 if (! BetweenStartEnd.test(Idx: Slot)) {
687 ConservativeSlots.set(Slot);
688 }
689 }
690 }
691 }
692 BitVector &SeenStart = SeenStartMap[MBB];
693 SeenStart |= BetweenStartEnd;
694 }
695 if (!MarkersFound) {
696 return 0;
697 }
698
699 // PR27903: slots with multiple start or end lifetime ops are not
700 // safe to enable for "lifetime-start-on-first-use".
701 for (unsigned slot = 0; slot < NumSlot; ++slot) {
702 if (NumStartLifetimes[slot] > 1 || NumEndLifetimes[slot] > 1)
703 ConservativeSlots.set(slot);
704 }
705
706 // The write to the catch object by the personality function is not propely
707 // modeled in IR: It happens before any cleanuppads are executed, even if the
708 // first mention of the catch object is in a catchpad. As such, mark catch
709 // object slots as conservative, so they are excluded from first-use analysis.
710 if (WinEHFuncInfo *EHInfo = MF->getWinEHFuncInfo())
711 for (WinEHTryBlockMapEntry &TBME : EHInfo->TryBlockMap)
712 for (WinEHHandlerType &H : TBME.HandlerArray)
713 if (H.CatchObj.FrameIndex != std::numeric_limits<int>::max() &&
714 H.CatchObj.FrameIndex >= 0)
715 ConservativeSlots.set(H.CatchObj.FrameIndex);
716
717 LLVM_DEBUG(dumpBV("Conservative slots", ConservativeSlots));
718
719 // Step 2: compute begin/end sets for each block
720
721 // NOTE: We use a depth-first iteration to ensure that we obtain a
722 // deterministic numbering.
723 for (MachineBasicBlock *MBB : depth_first(G: MF)) {
724 // Assign a serial number to this basic block.
725 BasicBlocks[MBB] = BasicBlockNumbering.size();
726 BasicBlockNumbering.push_back(Elt: MBB);
727
728 // Keep a reference to avoid repeated lookups.
729 BlockLifetimeInfo &BlockInfo = BlockLiveness[MBB];
730
731 BlockInfo.Begin.resize(N: NumSlot);
732 BlockInfo.End.resize(N: NumSlot);
733
734 SmallVector<int, 4> slots;
735 for (MachineInstr &MI : *MBB) {
736 bool isStart = false;
737 slots.clear();
738 if (isLifetimeStartOrEnd(MI, slots, isStart)) {
739 if (!isStart) {
740 assert(slots.size() == 1 && "unexpected: MI ends multiple slots");
741 int Slot = slots[0];
742 if (BlockInfo.Begin.test(Idx: Slot)) {
743 BlockInfo.Begin.reset(Idx: Slot);
744 }
745 BlockInfo.End.set(Slot);
746 } else {
747 for (auto Slot : slots) {
748 LLVM_DEBUG(dbgs() << "Found a use of slot #" << Slot);
749 LLVM_DEBUG(dbgs()
750 << " at " << printMBBReference(*MBB) << " index ");
751 LLVM_DEBUG(Indexes->getInstructionIndex(MI).print(dbgs()));
752 const AllocaInst *Allocation = MFI->getObjectAllocation(ObjectIdx: Slot);
753 if (Allocation) {
754 LLVM_DEBUG(dbgs()
755 << " with allocation: " << Allocation->getName());
756 }
757 LLVM_DEBUG(dbgs() << "\n");
758 if (BlockInfo.End.test(Idx: Slot)) {
759 BlockInfo.End.reset(Idx: Slot);
760 }
761 BlockInfo.Begin.set(Slot);
762 }
763 }
764 }
765 }
766 }
767
768 // Update statistics.
769 NumMarkerSeen += MarkersFound;
770 return MarkersFound;
771}
772
773void StackColoring::calculateLocalLiveness() {
774 unsigned NumIters = 0;
775 bool changed = true;
776 while (changed) {
777 changed = false;
778 ++NumIters;
779
780 for (const MachineBasicBlock *BB : BasicBlockNumbering) {
781 // Use an iterator to avoid repeated lookups.
782 LivenessMap::iterator BI = BlockLiveness.find(Val: BB);
783 assert(BI != BlockLiveness.end() && "Block not found");
784 BlockLifetimeInfo &BlockInfo = BI->second;
785
786 // Compute LiveIn by unioning together the LiveOut sets of all preds.
787 BitVector LocalLiveIn;
788 for (MachineBasicBlock *Pred : BB->predecessors()) {
789 LivenessMap::const_iterator I = BlockLiveness.find(Val: Pred);
790 // PR37130: transformations prior to stack coloring can
791 // sometimes leave behind statically unreachable blocks; these
792 // can be safely skipped here.
793 if (I != BlockLiveness.end())
794 LocalLiveIn |= I->second.LiveOut;
795 }
796
797 // Compute LiveOut by subtracting out lifetimes that end in this
798 // block, then adding in lifetimes that begin in this block. If
799 // we have both BEGIN and END markers in the same basic block
800 // then we know that the BEGIN marker comes after the END,
801 // because we already handle the case where the BEGIN comes
802 // before the END when collecting the markers (and building the
803 // BEGIN/END vectors).
804 BitVector LocalLiveOut = LocalLiveIn;
805 LocalLiveOut.reset(RHS: BlockInfo.End);
806 LocalLiveOut |= BlockInfo.Begin;
807
808 // Update block LiveIn set, noting whether it has changed.
809 if (LocalLiveIn.test(RHS: BlockInfo.LiveIn)) {
810 changed = true;
811 BlockInfo.LiveIn |= LocalLiveIn;
812 }
813
814 // Update block LiveOut set, noting whether it has changed.
815 if (LocalLiveOut.test(RHS: BlockInfo.LiveOut)) {
816 changed = true;
817 BlockInfo.LiveOut |= LocalLiveOut;
818 }
819 }
820 } // while changed.
821
822 NumIterations = NumIters;
823}
824
825void StackColoring::calculateLiveIntervals(unsigned NumSlots) {
826 SmallVector<SlotIndex, 16> Starts;
827 SmallVector<bool, 16> DefinitelyInUse;
828
829 // For each block, find which slots are active within this block
830 // and update the live intervals.
831 for (const MachineBasicBlock &MBB : *MF) {
832 Starts.clear();
833 Starts.resize(N: NumSlots);
834 DefinitelyInUse.clear();
835 DefinitelyInUse.resize(N: NumSlots);
836
837 // Start the interval of the slots that we previously found to be 'in-use'.
838 BlockLifetimeInfo &MBBLiveness = BlockLiveness[&MBB];
839 for (int pos = MBBLiveness.LiveIn.find_first(); pos != -1;
840 pos = MBBLiveness.LiveIn.find_next(Prev: pos)) {
841 Starts[pos] = Indexes->getMBBStartIdx(mbb: &MBB);
842 }
843
844 // Create the interval for the basic blocks containing lifetime begin/end.
845 for (const MachineInstr &MI : MBB) {
846 SmallVector<int, 4> slots;
847 bool IsStart = false;
848 if (!isLifetimeStartOrEnd(MI, slots, isStart&: IsStart))
849 continue;
850 SlotIndex ThisIndex = Indexes->getInstructionIndex(MI);
851 for (auto Slot : slots) {
852 if (IsStart) {
853 // If a slot is already definitely in use, we don't have to emit
854 // a new start marker because there is already a pre-existing
855 // one.
856 if (!DefinitelyInUse[Slot]) {
857 LiveStarts[Slot].push_back(Elt: ThisIndex);
858 DefinitelyInUse[Slot] = true;
859 }
860 if (!Starts[Slot].isValid())
861 Starts[Slot] = ThisIndex;
862 } else {
863 if (Starts[Slot].isValid()) {
864 VNInfo *VNI = Intervals[Slot]->getValNumInfo(ValNo: 0);
865 Intervals[Slot]->addSegment(
866 S: LiveInterval::Segment(Starts[Slot], ThisIndex, VNI));
867 Starts[Slot] = SlotIndex(); // Invalidate the start index
868 DefinitelyInUse[Slot] = false;
869 }
870 }
871 }
872 }
873
874 // Finish up started segments
875 for (unsigned i = 0; i < NumSlots; ++i) {
876 if (!Starts[i].isValid())
877 continue;
878
879 SlotIndex EndIdx = Indexes->getMBBEndIdx(mbb: &MBB);
880 VNInfo *VNI = Intervals[i]->getValNumInfo(ValNo: 0);
881 Intervals[i]->addSegment(S: LiveInterval::Segment(Starts[i], EndIdx, VNI));
882 }
883 }
884}
885
886bool StackColoring::removeAllMarkers() {
887 unsigned Count = 0;
888 for (MachineInstr *MI : Markers) {
889 MI->eraseFromParent();
890 Count++;
891 }
892 Markers.clear();
893
894 LLVM_DEBUG(dbgs() << "Removed " << Count << " markers.\n");
895 return Count;
896}
897
898void StackColoring::remapInstructions(DenseMap<int, int> &SlotRemap) {
899 unsigned FixedInstr = 0;
900 unsigned FixedMemOp = 0;
901 unsigned FixedDbg = 0;
902
903 // Remap debug information that refers to stack slots.
904 for (auto &VI : MF->getVariableDbgInfo()) {
905 if (!VI.Var || !VI.inStackSlot())
906 continue;
907 int Slot = VI.getStackSlot();
908 if (SlotRemap.count(Val: Slot)) {
909 LLVM_DEBUG(dbgs() << "Remapping debug info for ["
910 << cast<DILocalVariable>(VI.Var)->getName() << "].\n");
911 VI.updateStackSlot(NewSlot: SlotRemap[Slot]);
912 FixedDbg++;
913 }
914 }
915
916 // Keep a list of *allocas* which need to be remapped.
917 DenseMap<const AllocaInst*, const AllocaInst*> Allocas;
918
919 // Keep a list of allocas which has been affected by the remap.
920 SmallPtrSet<const AllocaInst*, 32> MergedAllocas;
921
922 for (const std::pair<int, int> &SI : SlotRemap) {
923 const AllocaInst *From = MFI->getObjectAllocation(ObjectIdx: SI.first);
924 const AllocaInst *To = MFI->getObjectAllocation(ObjectIdx: SI.second);
925 assert(To && From && "Invalid allocation object");
926 Allocas[From] = To;
927
928 // If From is before wo, its possible that there is a use of From between
929 // them.
930 if (From->comesBefore(Other: To))
931 const_cast<AllocaInst*>(To)->moveBefore(MovePos: const_cast<AllocaInst*>(From));
932
933 // AA might be used later for instruction scheduling, and we need it to be
934 // able to deduce the correct aliasing releationships between pointers
935 // derived from the alloca being remapped and the target of that remapping.
936 // The only safe way, without directly informing AA about the remapping
937 // somehow, is to directly update the IR to reflect the change being made
938 // here.
939 Instruction *Inst = const_cast<AllocaInst *>(To);
940 if (From->getType() != To->getType()) {
941 BitCastInst *Cast = new BitCastInst(Inst, From->getType());
942 Cast->insertAfter(InsertPos: Inst);
943 Inst = Cast;
944 }
945
946 // We keep both slots to maintain AliasAnalysis metadata later.
947 MergedAllocas.insert(Ptr: From);
948 MergedAllocas.insert(Ptr: To);
949
950 // Transfer the stack protector layout tag, but make sure that SSPLK_AddrOf
951 // does not overwrite SSPLK_SmallArray or SSPLK_LargeArray, and make sure
952 // that SSPLK_SmallArray does not overwrite SSPLK_LargeArray.
953 MachineFrameInfo::SSPLayoutKind FromKind
954 = MFI->getObjectSSPLayout(ObjectIdx: SI.first);
955 MachineFrameInfo::SSPLayoutKind ToKind = MFI->getObjectSSPLayout(ObjectIdx: SI.second);
956 if (FromKind != MachineFrameInfo::SSPLK_None &&
957 (ToKind == MachineFrameInfo::SSPLK_None ||
958 (ToKind != MachineFrameInfo::SSPLK_LargeArray &&
959 FromKind != MachineFrameInfo::SSPLK_AddrOf)))
960 MFI->setObjectSSPLayout(ObjectIdx: SI.second, Kind: FromKind);
961
962 // The new alloca might not be valid in a llvm.dbg.declare for this
963 // variable, so undef out the use to make the verifier happy.
964 AllocaInst *FromAI = const_cast<AllocaInst *>(From);
965 if (FromAI->isUsedByMetadata())
966 ValueAsMetadata::handleRAUW(From: FromAI, To: UndefValue::get(T: FromAI->getType()));
967 for (auto &Use : FromAI->uses()) {
968 if (BitCastInst *BCI = dyn_cast<BitCastInst>(Val: Use.get()))
969 if (BCI->isUsedByMetadata())
970 ValueAsMetadata::handleRAUW(From: BCI, To: UndefValue::get(T: BCI->getType()));
971 }
972
973 // Note that this will not replace uses in MMOs (which we'll update below),
974 // or anywhere else (which is why we won't delete the original
975 // instruction).
976 FromAI->replaceAllUsesWith(V: Inst);
977 }
978
979 // Remap all instructions to the new stack slots.
980 std::vector<std::vector<MachineMemOperand *>> SSRefs(
981 MFI->getObjectIndexEnd());
982 for (MachineBasicBlock &BB : *MF)
983 for (MachineInstr &I : BB) {
984 // Skip lifetime markers. We'll remove them soon.
985 if (I.getOpcode() == TargetOpcode::LIFETIME_START ||
986 I.getOpcode() == TargetOpcode::LIFETIME_END)
987 continue;
988
989 // Update the MachineMemOperand to use the new alloca.
990 for (MachineMemOperand *MMO : I.memoperands()) {
991 // We've replaced IR-level uses of the remapped allocas, so we only
992 // need to replace direct uses here.
993 const AllocaInst *AI = dyn_cast_or_null<AllocaInst>(Val: MMO->getValue());
994 if (!AI)
995 continue;
996
997 if (!Allocas.count(Val: AI))
998 continue;
999
1000 MMO->setValue(Allocas[AI]);
1001 FixedMemOp++;
1002 }
1003
1004 // Update all of the machine instruction operands.
1005 for (MachineOperand &MO : I.operands()) {
1006 if (!MO.isFI())
1007 continue;
1008 int FromSlot = MO.getIndex();
1009
1010 // Don't touch arguments.
1011 if (FromSlot<0)
1012 continue;
1013
1014 // Only look at mapped slots.
1015 if (!SlotRemap.count(Val: FromSlot))
1016 continue;
1017
1018 // In a debug build, check that the instruction that we are modifying is
1019 // inside the expected live range. If the instruction is not inside
1020 // the calculated range then it means that the alloca usage moved
1021 // outside of the lifetime markers, or that the user has a bug.
1022 // NOTE: Alloca address calculations which happen outside the lifetime
1023 // zone are okay, despite the fact that we don't have a good way
1024 // for validating all of the usages of the calculation.
1025#ifndef NDEBUG
1026 bool TouchesMemory = I.mayLoadOrStore();
1027 // If we *don't* protect the user from escaped allocas, don't bother
1028 // validating the instructions.
1029 if (!I.isDebugInstr() && TouchesMemory && ProtectFromEscapedAllocas) {
1030 SlotIndex Index = Indexes->getInstructionIndex(MI: I);
1031 const LiveInterval *Interval = &*Intervals[FromSlot];
1032 assert(Interval->find(Index) != Interval->end() &&
1033 "Found instruction usage outside of live range.");
1034 }
1035#endif
1036
1037 // Fix the machine instructions.
1038 int ToSlot = SlotRemap[FromSlot];
1039 MO.setIndex(ToSlot);
1040 FixedInstr++;
1041 }
1042
1043 // We adjust AliasAnalysis information for merged stack slots.
1044 SmallVector<MachineMemOperand *, 2> NewMMOs;
1045 bool ReplaceMemOps = false;
1046 for (MachineMemOperand *MMO : I.memoperands()) {
1047 // Collect MachineMemOperands which reference
1048 // FixedStackPseudoSourceValues with old frame indices.
1049 if (const auto *FSV = dyn_cast_or_null<FixedStackPseudoSourceValue>(
1050 Val: MMO->getPseudoValue())) {
1051 int FI = FSV->getFrameIndex();
1052 auto To = SlotRemap.find(Val: FI);
1053 if (To != SlotRemap.end())
1054 SSRefs[FI].push_back(x: MMO);
1055 }
1056
1057 // If this memory location can be a slot remapped here,
1058 // we remove AA information.
1059 bool MayHaveConflictingAAMD = false;
1060 if (MMO->getAAInfo()) {
1061 if (const Value *MMOV = MMO->getValue()) {
1062 SmallVector<Value *, 4> Objs;
1063 getUnderlyingObjectsForCodeGen(V: MMOV, Objects&: Objs);
1064
1065 if (Objs.empty())
1066 MayHaveConflictingAAMD = true;
1067 else
1068 for (Value *V : Objs) {
1069 // If this memory location comes from a known stack slot
1070 // that is not remapped, we continue checking.
1071 // Otherwise, we need to invalidate AA infomation.
1072 const AllocaInst *AI = dyn_cast_or_null<AllocaInst>(Val: V);
1073 if (AI && MergedAllocas.count(Ptr: AI)) {
1074 MayHaveConflictingAAMD = true;
1075 break;
1076 }
1077 }
1078 }
1079 }
1080 if (MayHaveConflictingAAMD) {
1081 NewMMOs.push_back(Elt: MF->getMachineMemOperand(MMO, AAInfo: AAMDNodes()));
1082 ReplaceMemOps = true;
1083 } else {
1084 NewMMOs.push_back(Elt: MMO);
1085 }
1086 }
1087
1088 // If any memory operand is updated, set memory references of
1089 // this instruction.
1090 if (ReplaceMemOps)
1091 I.setMemRefs(MF&: *MF, MemRefs: NewMMOs);
1092 }
1093
1094 // Rewrite MachineMemOperands that reference old frame indices.
1095 for (auto E : enumerate(First&: SSRefs))
1096 if (!E.value().empty()) {
1097 const PseudoSourceValue *NewSV =
1098 MF->getPSVManager().getFixedStack(FI: SlotRemap.find(Val: E.index())->second);
1099 for (MachineMemOperand *Ref : E.value())
1100 Ref->setValue(NewSV);
1101 }
1102
1103 // Update the location of C++ catch objects for the MSVC personality routine.
1104 if (WinEHFuncInfo *EHInfo = MF->getWinEHFuncInfo())
1105 for (WinEHTryBlockMapEntry &TBME : EHInfo->TryBlockMap)
1106 for (WinEHHandlerType &H : TBME.HandlerArray)
1107 if (H.CatchObj.FrameIndex != std::numeric_limits<int>::max() &&
1108 SlotRemap.count(Val: H.CatchObj.FrameIndex))
1109 H.CatchObj.FrameIndex = SlotRemap[H.CatchObj.FrameIndex];
1110
1111 LLVM_DEBUG(dbgs() << "Fixed " << FixedMemOp << " machine memory operands.\n");
1112 LLVM_DEBUG(dbgs() << "Fixed " << FixedDbg << " debug locations.\n");
1113 LLVM_DEBUG(dbgs() << "Fixed " << FixedInstr << " machine instructions.\n");
1114 (void) FixedMemOp;
1115 (void) FixedDbg;
1116 (void) FixedInstr;
1117}
1118
1119void StackColoring::removeInvalidSlotRanges() {
1120 for (MachineBasicBlock &BB : *MF)
1121 for (MachineInstr &I : BB) {
1122 if (I.getOpcode() == TargetOpcode::LIFETIME_START ||
1123 I.getOpcode() == TargetOpcode::LIFETIME_END || I.isDebugInstr())
1124 continue;
1125
1126 // Some intervals are suspicious! In some cases we find address
1127 // calculations outside of the lifetime zone, but not actual memory
1128 // read or write. Memory accesses outside of the lifetime zone are a clear
1129 // violation, but address calculations are okay. This can happen when
1130 // GEPs are hoisted outside of the lifetime zone.
1131 // So, in here we only check instructions which can read or write memory.
1132 if (!I.mayLoad() && !I.mayStore())
1133 continue;
1134
1135 // Check all of the machine operands.
1136 for (const MachineOperand &MO : I.operands()) {
1137 if (!MO.isFI())
1138 continue;
1139
1140 int Slot = MO.getIndex();
1141
1142 if (Slot<0)
1143 continue;
1144
1145 if (Intervals[Slot]->empty())
1146 continue;
1147
1148 // Check that the used slot is inside the calculated lifetime range.
1149 // If it is not, warn about it and invalidate the range.
1150 LiveInterval *Interval = &*Intervals[Slot];
1151 SlotIndex Index = Indexes->getInstructionIndex(MI: I);
1152 if (Interval->find(Pos: Index) == Interval->end()) {
1153 Interval->clear();
1154 LLVM_DEBUG(dbgs() << "Invalidating range #" << Slot << "\n");
1155 EscapedAllocas++;
1156 }
1157 }
1158 }
1159}
1160
1161void StackColoring::expungeSlotMap(DenseMap<int, int> &SlotRemap,
1162 unsigned NumSlots) {
1163 // Expunge slot remap map.
1164 for (unsigned i=0; i < NumSlots; ++i) {
1165 // If we are remapping i
1166 if (SlotRemap.count(Val: i)) {
1167 int Target = SlotRemap[i];
1168 // As long as our target is mapped to something else, follow it.
1169 while (SlotRemap.count(Val: Target)) {
1170 Target = SlotRemap[Target];
1171 SlotRemap[i] = Target;
1172 }
1173 }
1174 }
1175}
1176
1177bool StackColoring::runOnMachineFunction(MachineFunction &Func) {
1178 LLVM_DEBUG(dbgs() << "********** Stack Coloring **********\n"
1179 << "********** Function: " << Func.getName() << '\n');
1180 MF = &Func;
1181 MFI = &MF->getFrameInfo();
1182 Indexes = &getAnalysis<SlotIndexes>();
1183 BlockLiveness.clear();
1184 BasicBlocks.clear();
1185 BasicBlockNumbering.clear();
1186 Markers.clear();
1187 Intervals.clear();
1188 LiveStarts.clear();
1189 VNInfoAllocator.Reset();
1190
1191 unsigned NumSlots = MFI->getObjectIndexEnd();
1192
1193 // If there are no stack slots then there are no markers to remove.
1194 if (!NumSlots)
1195 return false;
1196
1197 SmallVector<int, 8> SortedSlots;
1198 SortedSlots.reserve(N: NumSlots);
1199 Intervals.reserve(N: NumSlots);
1200 LiveStarts.resize(N: NumSlots);
1201
1202 unsigned NumMarkers = collectMarkers(NumSlot: NumSlots);
1203
1204 unsigned TotalSize = 0;
1205 LLVM_DEBUG(dbgs() << "Found " << NumMarkers << " markers and " << NumSlots
1206 << " slots\n");
1207 LLVM_DEBUG(dbgs() << "Slot structure:\n");
1208
1209 for (int i=0; i < MFI->getObjectIndexEnd(); ++i) {
1210 LLVM_DEBUG(dbgs() << "Slot #" << i << " - " << MFI->getObjectSize(i)
1211 << " bytes.\n");
1212 TotalSize += MFI->getObjectSize(ObjectIdx: i);
1213 }
1214
1215 LLVM_DEBUG(dbgs() << "Total Stack size: " << TotalSize << " bytes\n\n");
1216
1217 // Don't continue because there are not enough lifetime markers, or the
1218 // stack is too small, or we are told not to optimize the slots.
1219 if (NumMarkers < 2 || TotalSize < 16 || DisableColoring ||
1220 skipFunction(F: Func.getFunction())) {
1221 LLVM_DEBUG(dbgs() << "Will not try to merge slots.\n");
1222 return removeAllMarkers();
1223 }
1224
1225 for (unsigned i=0; i < NumSlots; ++i) {
1226 std::unique_ptr<LiveInterval> LI(new LiveInterval(i, 0));
1227 LI->getNextValue(Def: Indexes->getZeroIndex(), VNInfoAllocator);
1228 Intervals.push_back(Elt: std::move(LI));
1229 SortedSlots.push_back(Elt: i);
1230 }
1231
1232 // Calculate the liveness of each block.
1233 calculateLocalLiveness();
1234 LLVM_DEBUG(dbgs() << "Dataflow iterations: " << NumIterations << "\n");
1235 LLVM_DEBUG(dump());
1236
1237 // Propagate the liveness information.
1238 calculateLiveIntervals(NumSlots);
1239 LLVM_DEBUG(dumpIntervals());
1240
1241 // Search for allocas which are used outside of the declared lifetime
1242 // markers.
1243 if (ProtectFromEscapedAllocas)
1244 removeInvalidSlotRanges();
1245
1246 // Maps old slots to new slots.
1247 DenseMap<int, int> SlotRemap;
1248 unsigned RemovedSlots = 0;
1249 unsigned ReducedSize = 0;
1250
1251 // Do not bother looking at empty intervals.
1252 for (unsigned I = 0; I < NumSlots; ++I) {
1253 if (Intervals[SortedSlots[I]]->empty())
1254 SortedSlots[I] = -1;
1255 }
1256
1257 // This is a simple greedy algorithm for merging allocas. First, sort the
1258 // slots, placing the largest slots first. Next, perform an n^2 scan and look
1259 // for disjoint slots. When you find disjoint slots, merge the smaller one
1260 // into the bigger one and update the live interval. Remove the small alloca
1261 // and continue.
1262
1263 // Sort the slots according to their size. Place unused slots at the end.
1264 // Use stable sort to guarantee deterministic code generation.
1265 llvm::stable_sort(Range&: SortedSlots, C: [this](int LHS, int RHS) {
1266 // We use -1 to denote a uninteresting slot. Place these slots at the end.
1267 if (LHS == -1)
1268 return false;
1269 if (RHS == -1)
1270 return true;
1271 // Sort according to size.
1272 return MFI->getObjectSize(ObjectIdx: LHS) > MFI->getObjectSize(ObjectIdx: RHS);
1273 });
1274
1275 for (auto &s : LiveStarts)
1276 llvm::sort(C&: s);
1277
1278 bool Changed = true;
1279 while (Changed) {
1280 Changed = false;
1281 for (unsigned I = 0; I < NumSlots; ++I) {
1282 if (SortedSlots[I] == -1)
1283 continue;
1284
1285 for (unsigned J=I+1; J < NumSlots; ++J) {
1286 if (SortedSlots[J] == -1)
1287 continue;
1288
1289 int FirstSlot = SortedSlots[I];
1290 int SecondSlot = SortedSlots[J];
1291
1292 // Objects with different stack IDs cannot be merged.
1293 if (MFI->getStackID(ObjectIdx: FirstSlot) != MFI->getStackID(ObjectIdx: SecondSlot))
1294 continue;
1295
1296 LiveInterval *First = &*Intervals[FirstSlot];
1297 LiveInterval *Second = &*Intervals[SecondSlot];
1298 auto &FirstS = LiveStarts[FirstSlot];
1299 auto &SecondS = LiveStarts[SecondSlot];
1300 assert(!First->empty() && !Second->empty() && "Found an empty range");
1301
1302 // Merge disjoint slots. This is a little bit tricky - see the
1303 // Implementation Notes section for an explanation.
1304 if (!First->isLiveAtIndexes(Slots: SecondS) &&
1305 !Second->isLiveAtIndexes(Slots: FirstS)) {
1306 Changed = true;
1307 First->MergeSegmentsInAsValue(RHS: *Second, LHSValNo: First->getValNumInfo(ValNo: 0));
1308
1309 int OldSize = FirstS.size();
1310 FirstS.append(in_start: SecondS.begin(), in_end: SecondS.end());
1311 auto Mid = FirstS.begin() + OldSize;
1312 std::inplace_merge(first: FirstS.begin(), middle: Mid, last: FirstS.end());
1313
1314 SlotRemap[SecondSlot] = FirstSlot;
1315 SortedSlots[J] = -1;
1316 LLVM_DEBUG(dbgs() << "Merging #" << FirstSlot << " and slots #"
1317 << SecondSlot << " together.\n");
1318 Align MaxAlignment = std::max(a: MFI->getObjectAlign(ObjectIdx: FirstSlot),
1319 b: MFI->getObjectAlign(ObjectIdx: SecondSlot));
1320
1321 assert(MFI->getObjectSize(FirstSlot) >=
1322 MFI->getObjectSize(SecondSlot) &&
1323 "Merging a small object into a larger one");
1324
1325 RemovedSlots+=1;
1326 ReducedSize += MFI->getObjectSize(ObjectIdx: SecondSlot);
1327 MFI->setObjectAlignment(ObjectIdx: FirstSlot, Alignment: MaxAlignment);
1328 MFI->RemoveStackObject(ObjectIdx: SecondSlot);
1329 }
1330 }
1331 }
1332 }// While changed.
1333
1334 // Record statistics.
1335 StackSpaceSaved += ReducedSize;
1336 StackSlotMerged += RemovedSlots;
1337 LLVM_DEBUG(dbgs() << "Merge " << RemovedSlots << " slots. Saved "
1338 << ReducedSize << " bytes\n");
1339
1340 // Scan the entire function and update all machine operands that use frame
1341 // indices to use the remapped frame index.
1342 if (!SlotRemap.empty()) {
1343 expungeSlotMap(SlotRemap, NumSlots);
1344 remapInstructions(SlotRemap);
1345 }
1346
1347 return removeAllMarkers();
1348}
1349

source code of llvm/lib/CodeGen/StackColoring.cpp