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