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