LLVM  16.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"
26 #include "llvm/ADT/SmallPtrSet.h"
27 #include "llvm/ADT/SmallVector.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"
45 #include "llvm/IR/Instructions.h"
46 #include "llvm/IR/Metadata.h"
47 #include "llvm/IR/Use.h"
48 #include "llvm/IR/Value.h"
49 #include "llvm/InitializePasses.h"
50 #include "llvm/Pass.h"
51 #include "llvm/Support/Casting.h"
53 #include "llvm/Support/Compiler.h"
54 #include "llvm/Support/Debug.h"
56 #include <algorithm>
57 #include <cassert>
58 #include <limits>
59 #include <memory>
60 #include <utility>
61 
62 using namespace llvm;
63 
64 #define DEBUG_TYPE "stack-coloring"
65 
66 static cl::opt<bool>
67 DisableColoring("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.
76 static cl::opt<bool>
77 ProtectFromEscapedAllocas("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.
86 static cl::opt<bool>
87 LifetimeStartOnFirstUse("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 
92 STATISTIC(NumMarkerSeen, "Number of lifetime markers found.");
93 STATISTIC(StackSpaceSaved, "Number of bytes saved due to merging slots.");
94 STATISTIC(StackSlotMerged, "Number of stack slot merged.");
95 STATISTIC(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 
405 namespace {
406 
407 /// StackColoring - A machine pass for merging disjoint stack allocations,
408 /// marked by the LIFETIME_START and LIFETIME_END pseudo instructions.
409 class 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.
438  SmallVector<const MachineBasicBlock *, 8> BasicBlockNumbering;
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 
471 public:
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 
481 private:
482  /// Used in collectMarkers
483  using BlockBitVecMap = DenseMap<const MachineBasicBlock *, BitVector>;
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 
547 char StackColoring::ID = 0;
548 
550 
551 INITIALIZE_PASS_BEGIN(StackColoring, DEBUG_TYPE,
552  "Merge disjoint stack slots", false, false)
555  "Merge disjoint stack slots", false, false)
556 
557 void StackColoring::getAnalysisUsage(AnalysisUsage &AU) const {
558  AU.addRequired<SlotIndexes>();
560 }
561 
562 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
563 LLVM_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 
571 LLVM_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 
583  for (MachineBasicBlock *MBB : depth_first(MF)) {
584  dbgs() << "Inspecting block #" << MBB->getNumber() << " ["
585  << MBB->getName() << "]\n";
586  dumpBB(MBB);
587  }
588 }
589 
590 LLVM_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 
598 static 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.
614 bool StackColoring::isLifetimeStartOrEnd(const MachineInstr &MI,
616  bool &isStart) {
617  if (MI.getOpcode() == TargetOpcode::LIFETIME_START ||
618  MI.getOpcode() == TargetOpcode::LIFETIME_END) {
619  int Slot = getStartOrEndSlot(MI);
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 
656 unsigned 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) {
692  int Slot = getStartOrEndSlot(MI);
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);
710  LLVM_DEBUG(dbgs()
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);
782  LLVM_DEBUG(dbgs()
783  << " at " << printMBBReference(*MBB) << " index ");
785  const AllocaInst *Allocation = MFI->getObjectAllocation(Slot);
786  if (Allocation) {
787  LLVM_DEBUG(dbgs()
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 
806 void 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 
858 void 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 
919 bool 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 
931 void 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) {
1062  SlotIndex Index = Indexes->getInstructionIndex(I);
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()) {
1095  getUnderlyingObjectsForCodeGen(MMOV, Objs);
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 
1151 void 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];
1183  SlotIndex Index = Indexes->getInstructionIndex(I);
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 
1193 void 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 
1209 bool 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 }
ProtectFromEscapedAllocas
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.
i
i
Definition: README.txt:29
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:108
MachineInstr.h
LLVM_DUMP_METHOD
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:492
Merge
R600 Clause Merge
Definition: R600ClauseMergePass.cpp:70
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::LiveRange::empty
bool empty() const
Definition: LiveInterval.h:382
llvm::AArch64PACKey::ID
ID
Definition: AArch64BaseInfo.h:818
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(StackColoring, DEBUG_TYPE, "Merge disjoint stack slots", false, false) INITIALIZE_PASS_END(StackColoring
llvm::BumpPtrAllocatorImpl::Reset
void Reset()
Deallocate all but the current slab and reset the current pointer to the beginning of it,...
Definition: Allocator.h:123
Metadata.h
llvm::ISD::LIFETIME_END
@ LIFETIME_END
Definition: ISDOpcodes.h:1225
DEBUG_TYPE
#define DEBUG_TYPE
Definition: StackColoring.cpp:64
DebugInfoMetadata.h
llvm::ISD::LIFETIME_START
@ LIFETIME_START
This corresponds to the llvm.lifetime.
Definition: ISDOpcodes.h:1224
Pass.h
llvm::BitVector::set
BitVector & set()
Definition: BitVector.h:344
llvm::BitVector::clear
void clear()
clear - Removes all bits from the bitvector.
Definition: BitVector.h:328
llvm::BitCastInst
This class represents a no-op cast from one type to another.
Definition: Instructions.h:5255
llvm::Target
Target - Wrapper for Target specific information.
Definition: TargetRegistry.h:149
llvm::AllocaInst::getType
PointerType * getType() const
Overload to return most specific pointer type.
Definition: Instructions.h:100
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
Statistic.h
llvm::printMBBReference
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
Definition: MachineBasicBlock.cpp:117
llvm::enumerate
detail::enumerator< R > enumerate(R &&TheRange)
Given an input range, returns a new range whose values are are pair (A,B) such that A is the 0-based ...
Definition: STLExtras.h:2238
llvm::Use::get
Value * get() const
Definition: Use.h:66
llvm::MachineFunctionPass
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Definition: MachineFunctionPass.h:30
llvm::WinEHHandlerType
Definition: WinEHFuncInfo.h:60
ValueTracking.h
MachineBasicBlock.h
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:140
llvm::AAMDNodes
A collection of metadata nodes that might be associated with a memory access used by the alias-analys...
Definition: Metadata.h:652
DenseMap.h
llvm::BitVector::resize
void resize(unsigned N, bool t=false)
resize - Grow or shrink the bitvector.
Definition: BitVector.h:334
llvm::MachineMemOperand
A description of a memory reference used in the backend.
Definition: MachineMemOperand.h:127
llvm::MachineFrameInfo::SSPLK_LargeArray
@ SSPLK_LargeArray
Array or nested array >= SSP-buffer-size.
Definition: MachineFrameInfo.h:113
DisableColoring
static cl::opt< bool > DisableColoring("no-stack-coloring", cl::init(false), cl::Hidden, cl::desc("Disable stack coloring"))
slot
Since we know that Vector is byte aligned and we know the element offset of we should change the load into a lve *x instead of doing a load store lve *x sequence Implement passing vectors by value into calls and receiving them as arguments GCC apparently tries to then a load and vperm of Variable We need a way to teach tblgen that some operands of an intrinsic are required to be constants The verifier should enforce this constraint We currently codegen SCALAR_TO_VECTOR as a store of the scalar to a byte aligned stack slot
Definition: README_ALTIVEC.txt:57
llvm::DenseMapBase::count
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:145
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
llvm::SlotIndexes::getMBBEndIdx
SlotIndex getMBBEndIdx(unsigned Num) const
Returns the last index in the given basic block number.
Definition: SlotIndexes.h:481
llvm::max
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:337
llvm::dump
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
Definition: SparseBitVector.h:877
llvm::MachineFrameInfo::RemoveStackObject
void RemoveStackObject(int ObjectIdx)
Remove or mark dead a statically sized stack object.
Definition: MachineFrameInfo.h:776
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
llvm::MachineFrameInfo::getObjectIndexEnd
int getObjectIndexEnd() const
Return one past the maximum frame object index.
Definition: MachineFrameInfo.h:410
Use.h
llvm::MachineFrameInfo::setObjectAlignment
void setObjectAlignment(int ObjectIdx, Align Alignment)
setObjectAlignment - Change the alignment of the specified stack object.
Definition: MachineFrameInfo.h:497
llvm::MachineFunctionPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Definition: MachineFunctionPass.cpp:167
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
DepthFirstIterator.h
llvm::LiveRange::isLiveAtIndexes
bool isLiveAtIndexes(ArrayRef< SlotIndex > Slots) const
Definition: LiveInterval.cpp:800
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
CommandLine.h
LHS
Value * LHS
Definition: X86PartialReduction.cpp:75
llvm::Instruction::insertAfter
void insertAfter(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately after the specified instruction.
Definition: Instruction.cpp:93
Markers
R600 Emit Clause Markers
Definition: R600EmitClauseMarkers.cpp:333
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:24
llvm::ModRefInfo::Ref
@ Ref
The access may reference the value stored in memory.
Constants.h
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::MachineFrameInfo::setObjectSSPLayout
void setObjectSSPLayout(int ObjectIdx, SSPLayoutKind Kind)
Definition: MachineFrameInfo.h:574
llvm::BitVector::size
size_type size() const
size - Returns the number of bits in this bitvector.
Definition: BitVector.h:152
getStartOrEndSlot
static int getStartOrEndSlot(const MachineInstr &MI)
Definition: StackColoring.cpp:598
SI
@ SI
Definition: SIInstrInfo.cpp:7882
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::Value::uses
iterator_range< use_iterator > uses()
Definition: Value.h:376
false
Definition: StackSlotColoring.cpp:141
TargetOpcodes.h
llvm::dwarf::Index
Index
Definition: Dwarf.h:472
First
into llvm powi allowing the code generator to produce balanced multiplication trees First
Definition: README.txt:54
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:48
llvm::Instruction
Definition: Instruction.h:42
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::MachineFrameInfo::getStackID
uint8_t getStackID(int ObjectIdx) const
Definition: MachineFrameInfo.h:731
llvm::SlotIndexes::getInstructionIndex
SlotIndex getInstructionIndex(const MachineInstr &MI, bool IgnoreBundle=false) const
Returns the base index for the given instruction.
Definition: SlotIndexes.h:390
llvm::MachineFrameInfo::SSPLK_None
@ SSPLK_None
Did not trigger a stack protector.
Definition: MachineFrameInfo.h:111
llvm::SmallVectorImpl::resize
void resize(size_type N)
Definition: SmallVector.h:642
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1713
BitVector.h
llvm::SlotIndexes
SlotIndexes pass.
Definition: SlotIndexes.h:319
SmallPtrSet.h
llvm::BitVector
Definition: BitVector.h:75
llvm::PseudoSourceValue
Special value supplied for machine level alias analysis.
Definition: PseudoSourceValue.h:35
llvm::LiveInterval
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:686
llvm::Align
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:39
llvm::SlotIndex
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:82
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:94
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1657
Passes.h
llvm::cl::opt< bool >
llvm::WinEHTryBlockMapEntry
Definition: WinEHFuncInfo.h:72
VI
@ VI
Definition: SIInstrInfo.cpp:7883
llvm::SlotIndexes::getMBBStartIdx
SlotIndex getMBBStartIdx(unsigned Num) const
Returns the first index in the given basic block number.
Definition: SlotIndexes.h:471
llvm::StackColoringID
char & StackColoringID
StackSlotColoring - This pass performs stack coloring and merging.
Definition: StackColoring.cpp:549
llvm::WinEHFuncInfo
Definition: WinEHFuncInfo.h:90
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::clear
void clear()
Definition: DenseMap.h:110
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:66
llvm::MachineFrameInfo::getObjectSize
int64_t getObjectSize(int ObjectIdx) const
Return the size of the specified object.
Definition: MachineFrameInfo.h:470
llvm::Interval
Interval Class - An Interval is a set of nodes defined such that every node in the interval has all o...
Definition: Interval.h:36
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
s
multiplies can be turned into SHL s
Definition: README.txt:370
llvm::BumpPtrAllocatorImpl
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:63
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::DenseMap
Definition: DenseMap.h:714
llvm::WinEHTryBlockMapEntry::HandlerArray
SmallVector< WinEHHandlerType, 1 > HandlerArray
Definition: WinEHFuncInfo.h:76
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::MachineFrameInfo::getObjectAlign
Align getObjectAlign(int ObjectIdx) const
Return the alignment of the specified stack object.
Definition: MachineFrameInfo.h:484
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:447
MachineFunctionPass.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::getUnderlyingObjectsForCodeGen
bool getUnderlyingObjectsForCodeGen(const Value *V, SmallVectorImpl< Value * > &Objects)
This is a wrapper around getUnderlyingObjects and adds support for basic ptrtoint+arithmetic+inttoptr...
Definition: ValueTracking.cpp:4614
llvm::MachineBasicBlock::predecessors
iterator_range< pred_iterator > predecessors()
Definition: MachineBasicBlock.h:386
llvm::SmallPtrSetImpl::count
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:383
llvm::MachineFunction
Definition: MachineFunction.h:257
llvm::MachineBasicBlock::getNumber
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
Definition: MachineBasicBlock.h:1115
llvm::MachineBasicBlock::isEHPad
bool isEHPad() const
Returns true if the block is a landing pad.
Definition: MachineBasicBlock.h:576
llvm::Value::replaceAllUsesWith
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:532
llvm::SlotIndex::print
void print(raw_ostream &os) const
Print this index to the given raw_ostream.
Definition: SlotIndexes.cpp:259
Compiler.h
llvm::ifs::IFSSymbolType::Func
@ Func
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:308
llvm::SlotIndexes::getZeroIndex
SlotIndex getZeroIndex()
Returns the zero index for this analysis.
Definition: SlotIndexes.h:373
llvm::depth_first
iterator_range< df_iterator< T > > depth_first(const T &G)
Definition: DepthFirstIterator.h:230
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::BitVector::test
bool test(unsigned Idx) const
Definition: BitVector.h:454
llvm::stable_sort
void stable_sort(R &&Range)
Definition: STLExtras.h:1922
llvm::MachineFrameInfo::getObjectSSPLayout
SSPLayoutKind getObjectSSPLayout(int ObjectIdx) const
Definition: MachineFrameInfo.h:568
H
#define H(x, y, z)
Definition: MD5.cpp:57
MachineFrameInfo.h
llvm::MachineFunction::getWinEHFuncInfo
const WinEHFuncInfo * getWinEHFuncInfo() const
getWinEHFuncInfo - Return information about how the current function uses Windows exception handling.
Definition: MachineFunction.h:701
llvm::MachineOperand::getIndex
int getIndex() const
Definition: MachineOperand.h:566
Casting.h
llvm::pdb::PDB_LocType::Slot
@ Slot
slots
Merge disjoint stack slots
Definition: StackColoring.cpp:555
llvm::VNInfo
VNInfo - Value Number Information.
Definition: LiveInterval.h:53
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:614
llvm::BitVector::reset
BitVector & reset()
Definition: BitVector.h:385
WinEHFuncInfo.h
llvm::ValueAsMetadata::handleRAUW
static void handleRAUW(Value *From, Value *To)
Definition: Metadata.cpp:436
LiveInterval.h
llvm::MachineFrameInfo
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted.
Definition: MachineFrameInfo.h:106
isValid
static bool isValid(const char C)
Returns true if C is a valid mangled character: <0-9a-zA-Z_>.
Definition: RustDemangle.cpp:184
Instructions.h
SmallVector.h
llvm::Value::isUsedByMetadata
bool isUsedByMetadata() const
Return true if there is metadata referencing this value.
Definition: Value.h:557
llvm::MachineFrameInfo::SSPLK_AddrOf
@ SSPLK_AddrOf
The address of this allocation is exposed and triggered protection.
Definition: MachineFrameInfo.h:117
llvm::MachineFrameInfo::SSPLayoutKind
SSPLayoutKind
Stack Smashing Protection (SSP) rules require that vulnerable stack allocations are located close the...
Definition: MachineFrameInfo.h:110
stack
S is passed via registers r2 But gcc stores them to the stack
Definition: README.txt:189
MachineMemOperand.h
MachineOperand.h
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::initializeStackColoringPass
void initializeStackColoringPass(PassRegistry &)
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
llvm::AllocaInst
an instruction to allocate memory on the stack
Definition: Instructions.h:58
SlotIndexes.h
llvm::cl::desc
Definition: CommandLine.h:413
LifetimeStartOnFirstUse
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...
raw_ostream.h
MachineFunction.h
llvm::SmallVectorImpl::reserve
void reserve(size_type N)
Definition: SmallVector.h:667
Value.h
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::MachineBasicBlock::getName
StringRef getName() const
Return the name of the corresponding LLVM basic block, or an empty string.
Definition: MachineBasicBlock.cpp:311
Debug.h
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
llvm::SmallPtrSetImpl::insert
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
llvm::MachineFrameInfo::getObjectAllocation
const AllocaInst * getObjectAllocation(int ObjectIdx) const
Return the underlying Alloca of the specified stack object if it exists.
Definition: MachineFrameInfo.h:510