LLVM 24.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 (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
24#include "CodeGenOptions.h"
25#include "llvm/ADT/BitVector.h"
26#include "llvm/ADT/DenseMap.h"
30#include "llvm/ADT/Statistic.h"
40#include "llvm/CodeGen/Passes.h"
46#include "llvm/Config/llvm-config.h"
47#include "llvm/IR/Constants.h"
50#include "llvm/IR/Metadata.h"
51#include "llvm/IR/Use.h"
52#include "llvm/IR/Value.h"
54#include "llvm/Pass.h"
57#include "llvm/Support/Debug.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.
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.
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.
387
388 /// Maps slots to the points where they can become in-use.
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(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
499 "Merge disjoint stack slots", false, false)
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>();
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(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) {
568 if (Slot < 0)
569 return false;
570 if (!InterestingSlots.test(Slot))
571 return false;
572 slots.push_back(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(Slot) && applyFirstUse(Slot)) {
592 slots.push_back(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(NumSlot);
610 ConservativeSlots.clear();
611 ConservativeSlots.resize(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(MF)) {
620 BasicBlockOrdering.push_back(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(NumSlot);
627 for (const MachineBasicBlock *Pred : MBB->predecessors()) {
628 BlockBitVecMap::const_iterator I = SeenStartMap.find(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) {
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(Slot);
649 NumEndLifetimes[Slot] += 1;
650 }
651 const AllocaInst *Allocation = MFI->getObjectAllocation(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);
659 << " with allocation: " << Allocation->getName() << "\n");
660 }
661 Markers.push_back(&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(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(NumSlot);
714 BlockInfo.End.resize(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(Slot)) {
725 BlockInfo.Begin.reset(Slot);
726 }
727 BlockInfo.End.set(Slot);
728 } else {
729 for (auto Slot : slots) {
730 LLVM_DEBUG(dbgs() << "Found a use of slot #" << Slot);
732 << " at " << printMBBReference(*MBB) << " index ");
734 const AllocaInst *Allocation = MFI->getObjectAllocation(Slot);
735 if (Allocation) {
737 << " with allocation: " << Allocation->getName());
738 }
739 LLVM_DEBUG(dbgs() << "\n");
740 if (BlockInfo.End.test(Slot)) {
741 BlockInfo.End.reset(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(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(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(BlockInfo.End);
792 LocalLiveOut |= BlockInfo.Begin;
793
794 // Update block LiveIn set, noting whether it has changed.
795 if (!LocalLiveIn.subsetOf(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(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) {
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(NumSlots);
820 DefinitelyInUse.clear();
821 DefinitelyInUse.resize(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(pos)) {
827 Starts[pos] = Indexes->getMBBStartIdx(&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))
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(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(0);
851 Intervals[Slot]->addSegment(
852 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);
866 VNInfo *VNI = Intervals[i]->getValNumInfo(0);
867 Intervals[i]->addSegment(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(Slot); It != SlotRemap.end()) {
895 LLVM_DEBUG(dbgs() << "Remapping debug info for ["
896 << cast<DILocalVariable>(VI.Var)->getName() << "].\n");
897 VI.updateStackSlot(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(FromIdx));
911 AllocaInst *To = const_cast<AllocaInst *>(MFI->getObjectAllocation(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(To))
925 To->moveBefore(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(From);
933 MergedAllocas.insert(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.
940 if (FromKind != MachineFrameInfo::SSPLK_None &&
941 (ToKind == MachineFrameInfo::SSPLK_None ||
943 FromKind != MachineFrameInfo::SSPLK_AddrOf)))
944 MFI->setObjectSSPLayout(ToIdx, 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())
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(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>(MMO->getValue());
972 if (!AI)
973 continue;
974
975 auto It = Allocas.find(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(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.
1025 bool ReplaceMemOps = false;
1026 for (MachineMemOperand *MMO : I.memoperands()) {
1027 // Collect MachineMemOperands which reference
1028 // FixedStackPseudoSourceValues with old frame indices.
1030 MMO->getPseudoValue())) {
1031 int FI = FSV->getFrameIndex();
1032 auto To = SlotRemap.find(FI);
1033 if (To != SlotRemap.end())
1034 SSRefs[FI].push_back(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(MMOV, 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>(V);
1052 if (AI && MergedAllocas.count(AI)) {
1053 MayHaveConflictingAAMD = true;
1054 break;
1055 }
1056 }
1057 }
1058 }
1059 if (MayHaveConflictingAAMD) {
1060 NewMMOs.push_back(MF->getMachineMemOperand(MMO, AAMDNodes()));
1061 ReplaceMemOps = true;
1062 } else {
1063 NewMMOs.push_back(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, NewMMOs);
1071 }
1072
1073 // Rewrite MachineMemOperands that reference old frame indices.
1074 for (auto E : enumerate(SSRefs))
1075 if (!E.value().empty()) {
1076 const PseudoSourceValue *NewSV =
1077 MF->getPSVManager().getFixedStack(SlotRemap.find(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(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(I);
1132 if (Interval->find(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(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(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(MF, skipFunction(MF.getFunction()));
1164}
1165
1168 StackColoring SC(getCodeGenOptions(MF),
1169 &MFAM.getResult<SlotIndexesAnalysis>(MF));
1170 bool OnlyRemoveMarkers = MF.getFunction().hasOptNone() ||
1172 if (SC.run(MF, OnlyRemoveMarkers)) {
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(NumSlots);
1200 Intervals.reserve(NumSlots);
1201 LiveStarts.resize(NumSlots);
1202
1203 unsigned NumMarkers = collectMarkers(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(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(Indexes->getZeroIndex(), VNInfoAllocator);
1230 Intervals.push_back(std::move(LI));
1231 SortedSlots.push_back(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(SortedSlots, [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(LHS) > MFI->getObjectSize(RHS);
1275 });
1276
1277 for (auto &s : LiveStarts)
1278 llvm::sort(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(FirstSlot) != MFI->getStackID(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(SecondS) &&
1307 !Second->isLiveAtIndexes(FirstS)) {
1308 Changed = true;
1309 First->MergeSegmentsInAsValue(*Second, First->getValNumInfo(0));
1310
1311 int OldSize = FirstS.size();
1312 FirstS.append(SecondS.begin(), SecondS.end());
1313 auto Mid = FirstS.begin() + OldSize;
1314 std::inplace_merge(FirstS.begin(), Mid, 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(MFI->getObjectAlign(FirstSlot),
1321 MFI->getObjectAlign(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(SecondSlot);
1329 MFI->setObjectAlignment(FirstSlot, MaxAlignment);
1330 MFI->RemoveStackObject(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}
SDValue Pred
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
MachineBasicBlock & MBB
This file implements the BitVector class.
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:702
This file contains the declarations for the subclasses of Constant, which represent the different fla...
This file defines the DenseMap class.
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
#define DEBUG_TYPE
Hexagon Lower HLX Pair Allocas
IRTranslator LLVM IR MI
This defines the Use class.
#define I(x, y, z)
Definition MD5.cpp:57
#define H(x, y, z)
Definition MD5.cpp:56
std::pair< uint64_t, uint64_t > Interval
This file contains the declarations for metadata subclasses.
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition PassSupport.h:42
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition PassSupport.h:44
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition PassSupport.h:39
R600 Emit Clause Markers
static bool isValid(const char C)
Returns true if C is a valid mangled character: <0-9a-zA-Z_>.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
static int getStartOrEndSlot(const MachineInstr &MI)
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:171
#define LLVM_DEBUG(...)
Definition Debug.h:119
Value * RHS
Value * LHS
Align getAlign() const
Return the alignment of the memory that is being allocated by the instruction.
PointerType * getType() const
Overload to return most specific pointer type.
void setAlignment(Align Align)
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Represent the analysis usage information of a pass.
bool test(unsigned Idx) const
Returns true if bit Idx is set.
Definition BitVector.h:483
BitVector & reset()
Reset all bits in the bitvector.
Definition BitVector.h:410
void resize(unsigned N, bool t=false)
Grow or shrink the bitvector.
Definition BitVector.h:356
void clear()
Removes all bits from the bitvector.
Definition BitVector.h:350
BitVector & set()
Set all bits in the bitvector.
Definition BitVector.h:367
size_type size() const
Returns the number of bits in this bitvector.
Definition BitVector.h:179
bool subsetOf(const BitVector &RHS) const
Check if This is a subset of RHS.
Definition BitVector.h:592
bool empty() const
Definition DenseMap.h:716
iterator find(const_arg_type_t< KeyT > Val)
Definition DenseMap.h:766
iterator end()
Definition DenseMap.h:686
bool hasOptNone() const
Do not optimize this function (-O0).
Definition Function.h:686
LLVM_ABI void moveBefore(InstListType::iterator InsertPos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
LLVM_ABI bool comesBefore(const Instruction *Other) const
Given an instruction Other in the same basic block as this instruction, return true if this instructi...
LLVM_ABI bool isLiveAtIndexes(ArrayRef< SlotIndex > Slots) const
bool empty() const
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
iterator_range< pred_iterator > predecessors()
LLVM_ABI 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.
const WinEHFuncInfo * getWinEHFuncInfo() const
getWinEHFuncInfo - Return information about how the current function uses Windows exception handling.
bool exposesReturnsTwice() const
exposesReturnsTwice - Returns true if the function calls setjmp or any other similar functions with a...
MachineFrameInfo & getFrameInfo()
getFrameInfo - Return the frame info object for the current function.
Function & getFunction()
Return the LLVM function that this machine code represents.
Representation of each machine instruction.
MachineOperand class - Representation of each machine instruction operand.
static LLVM_ABI PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
A set of analyses that are preserved following a run of a transformation pass.
Definition Analysis.h:112
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition Analysis.h:118
LLVM_ABI void print(raw_ostream &os) const
Print this index to the given raw_ostream.
SlotIndex getInstructionIndex(const MachineInstr &MI, bool IgnoreBundle=false) const
Returns the base index for the given instruction.
SlotIndex getZeroIndex()
Returns the zero index for this analysis.
SlotIndex getMBBEndIdx(const MachineBasicBlock *mbb) const
Returns the index past the last valid index in the given basic block.
SlotIndex getMBBStartIdx(const MachineBasicBlock *mbb) const
Returns the first index in the given basic block.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
void reserve(size_type N)
void resize(size_type N)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
LLVM_ABI PreservedAnalyses run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)
BumpPtrAllocator Allocator
static LLVM_ABI void handleRAUW(Value *From, Value *To)
Definition Metadata.cpp:555
LLVM_ABI void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition Value.cpp:548
bool isUsedByMetadata() const
Return true if there is metadata referencing this value.
Definition Value.h:560
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
Definition Value.cpp:314
self_iterator getIterator()
Definition ilist_node.h:123
constexpr char Align[]
Key for Kernel::Arg::Metadata::mAlign.
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
bool empty() const
Definition BasicBlock.h:101
This is an optimization pass for GlobalISel generic memory operations.
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
void stable_sort(R &&Range)
Definition STLExtras.h:2132
auto enumerate(FirstRange &&First, RestRanges &&...Rest)
Given two or more input ranges, returns a new range whose values are tuples (A, B,...
Definition STLExtras.h:2570
LLVM_ABI bool getUnderlyingObjectsForCodeGen(const Value *V, SmallVectorImpl< Value * > &Objects)
This is a wrapper around getUnderlyingObjects and adds support for basic ptrtoint+arithmetic+inttoptr...
AnalysisManager< MachineFunction > MachineFunctionAnalysisManager
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Value
Definition InstrProf.h:143
LLVM_ABI PreservedAnalyses getMachineFunctionPassPreservedAnalyses()
Returns the minimum set of Analyses that all machine function passes must preserve.
auto dyn_cast_or_null(const Y &Val)
Definition Casting.h:753
void sort(IteratorTy Start, IteratorTy End)
Definition STLExtras.h:1652
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition Debug.cpp:209
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
@ Ref
The access may reference the value stored in memory.
Definition ModRef.h:32
@ First
Helpers to iterate all locations in the MemoryEffectsBase class.
Definition ModRef.h:74
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Count
Definition InstrProf.h:145
LLVM_ABI char & StackColoringLegacyID
StackSlotColoring - This pass performs stack coloring and merging.
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:559
iterator_range< df_iterator< T > > depth_first(const T &G)
@ End
Run the machine verifier once, at the end of the pipeline.
Definition CodeGen.h:320
LLVM_ABI Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
const CodeGenOptions & getCodeGenOptions(const LLVMContext &C)
SmallVector< WinEHHandlerType, 1 > HandlerArray