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