LLVM  6.0.0svn
RewriteStatepointsForGC.cpp
Go to the documentation of this file.
1 //===- RewriteStatepointsForGC.cpp - Make GC relocations explicit ---------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // Rewrite call/invoke instructions so as to make potential relocations
11 // performed by the garbage collector explicit in the IR.
12 //
13 //===----------------------------------------------------------------------===//
14 
16 
17 #include "llvm/ADT/ArrayRef.h"
18 #include "llvm/ADT/DenseMap.h"
19 #include "llvm/ADT/DenseSet.h"
20 #include "llvm/ADT/MapVector.h"
21 #include "llvm/ADT/None.h"
22 #include "llvm/ADT/Optional.h"
23 #include "llvm/ADT/STLExtras.h"
24 #include "llvm/ADT/SetVector.h"
25 #include "llvm/ADT/SmallSet.h"
26 #include "llvm/ADT/SmallVector.h"
27 #include "llvm/ADT/StringRef.h"
31 #include "llvm/IR/Argument.h"
32 #include "llvm/IR/Attributes.h"
33 #include "llvm/IR/BasicBlock.h"
34 #include "llvm/IR/CallSite.h"
35 #include "llvm/IR/CallingConv.h"
36 #include "llvm/IR/Constant.h"
37 #include "llvm/IR/Constants.h"
38 #include "llvm/IR/DataLayout.h"
39 #include "llvm/IR/DerivedTypes.h"
40 #include "llvm/IR/Dominators.h"
41 #include "llvm/IR/Function.h"
42 #include "llvm/IR/IRBuilder.h"
43 #include "llvm/IR/InstIterator.h"
44 #include "llvm/IR/InstrTypes.h"
45 #include "llvm/IR/Instruction.h"
46 #include "llvm/IR/Instructions.h"
47 #include "llvm/IR/IntrinsicInst.h"
48 #include "llvm/IR/Intrinsics.h"
49 #include "llvm/IR/LLVMContext.h"
50 #include "llvm/IR/MDBuilder.h"
51 #include "llvm/IR/Metadata.h"
52 #include "llvm/IR/Module.h"
53 #include "llvm/IR/Statepoint.h"
54 #include "llvm/IR/Type.h"
55 #include "llvm/IR/User.h"
56 #include "llvm/IR/Value.h"
57 #include "llvm/IR/ValueHandle.h"
58 #include "llvm/Pass.h"
59 #include "llvm/Support/Casting.h"
61 #include "llvm/Support/Compiler.h"
62 #include "llvm/Support/Debug.h"
65 #include "llvm/Transforms/Scalar.h"
69 #include <algorithm>
70 #include <cassert>
71 #include <cstddef>
72 #include <cstdint>
73 #include <iterator>
74 #include <set>
75 #include <string>
76 #include <utility>
77 #include <vector>
78 
79 #define DEBUG_TYPE "rewrite-statepoints-for-gc"
80 
81 using namespace llvm;
82 
83 // Print the liveset found at the insert location
84 static cl::opt<bool> PrintLiveSet("spp-print-liveset", cl::Hidden,
85  cl::init(false));
86 static cl::opt<bool> PrintLiveSetSize("spp-print-liveset-size", cl::Hidden,
87  cl::init(false));
88 
89 // Print out the base pointers for debugging
90 static cl::opt<bool> PrintBasePointers("spp-print-base-pointers", cl::Hidden,
91  cl::init(false));
92 
93 // Cost threshold measuring when it is profitable to rematerialize value instead
94 // of relocating it
95 static cl::opt<unsigned>
96 RematerializationThreshold("spp-rematerialization-threshold", cl::Hidden,
97  cl::init(6));
98 
99 #ifdef EXPENSIVE_CHECKS
100 static bool ClobberNonLive = true;
101 #else
102 static bool ClobberNonLive = false;
103 #endif
104 
105 static cl::opt<bool, true> ClobberNonLiveOverride("rs4gc-clobber-non-live",
106  cl::location(ClobberNonLive),
107  cl::Hidden);
108 
109 static cl::opt<bool>
110  AllowStatepointWithNoDeoptInfo("rs4gc-allow-statepoint-with-no-deopt-info",
111  cl::Hidden, cl::init(true));
112 
113 /// The IR fed into RewriteStatepointsForGC may have had attributes and
114 /// metadata implying dereferenceability that are no longer valid/correct after
115 /// RewriteStatepointsForGC has run. This is because semantically, after
116 /// RewriteStatepointsForGC runs, all calls to gc.statepoint "free" the entire
117 /// heap. stripNonValidData (conservatively) restores
118 /// correctness by erasing all attributes in the module that externally imply
119 /// dereferenceability. Similar reasoning also applies to the noalias
120 /// attributes and metadata. gc.statepoint can touch the entire heap including
121 /// noalias objects.
122 /// Apart from attributes and metadata, we also remove instructions that imply
123 /// constant physical memory: llvm.invariant.start.
124 static void stripNonValidData(Module &M);
125 
127 
129  ModuleAnalysisManager &AM) {
130  bool Changed = false;
131  auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
132  for (Function &F : M) {
133  // Nothing to do for declarations.
134  if (F.isDeclaration() || F.empty())
135  continue;
136 
137  // Policy choice says not to rewrite - the most common reason is that we're
138  // compiling code without a GCStrategy.
140  continue;
141 
142  auto &DT = FAM.getResult<DominatorTreeAnalysis>(F);
143  auto &TTI = FAM.getResult<TargetIRAnalysis>(F);
144  auto &TLI = FAM.getResult<TargetLibraryAnalysis>(F);
145  Changed |= runOnFunction(F, DT, TTI, TLI);
146  }
147  if (!Changed)
148  return PreservedAnalyses::all();
149 
150  // stripNonValidData asserts that shouldRewriteStatepointsIn
151  // returns true for at least one function in the module. Since at least
152  // one function changed, we know that the precondition is satisfied.
154 
158  return PA;
159 }
160 
161 namespace {
162 
163 class RewriteStatepointsForGCLegacyPass : public ModulePass {
165 
166 public:
167  static char ID; // Pass identification, replacement for typeid
168 
169  RewriteStatepointsForGCLegacyPass() : ModulePass(ID), Impl() {
172  }
173 
174  bool runOnModule(Module &M) override {
175  bool Changed = false;
176  const TargetLibraryInfo &TLI =
177  getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
178  for (Function &F : M) {
179  // Nothing to do for declarations.
180  if (F.isDeclaration() || F.empty())
181  continue;
182 
183  // Policy choice says not to rewrite - the most common reason is that
184  // we're compiling code without a GCStrategy.
186  continue;
187 
188  TargetTransformInfo &TTI =
189  getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
190  auto &DT = getAnalysis<DominatorTreeWrapperPass>(F).getDomTree();
191 
192  Changed |= Impl.runOnFunction(F, DT, TTI, TLI);
193  }
194 
195  if (!Changed)
196  return false;
197 
198  // stripNonValidData asserts that shouldRewriteStatepointsIn
199  // returns true for at least one function in the module. Since at least
200  // one function changed, we know that the precondition is satisfied.
202  return true;
203  }
204 
205  void getAnalysisUsage(AnalysisUsage &AU) const override {
206  // We add and rewrite a bunch of instructions, but don't really do much
207  // else. We could in theory preserve a lot more analyses here.
211  }
212 };
213 
214 } // end anonymous namespace
215 
217 
219  return new RewriteStatepointsForGCLegacyPass();
220 }
221 
222 INITIALIZE_PASS_BEGIN(RewriteStatepointsForGCLegacyPass,
223  "rewrite-statepoints-for-gc",
224  "Make relocations explicit at statepoints", false, false)
227 INITIALIZE_PASS_END(RewriteStatepointsForGCLegacyPass,
228  "rewrite-statepoints-for-gc",
229  "Make relocations explicit at statepoints", false, false)
230 
231 namespace {
232 
234  /// Values defined in this block.
236 
237  /// Values used in this block (and thus live); does not included values
238  /// killed within this block.
240 
241  /// Values live into this basic block (i.e. used by any
242  /// instruction in this basic block or ones reachable from here)
244 
245  /// Values live out of this basic block (i.e. live into
246  /// any successor block)
248 };
249 
250 // The type of the internal cache used inside the findBasePointers family
251 // of functions. From the callers perspective, this is an opaque type and
252 // should not be inspected.
253 //
254 // In the actual implementation this caches two relations:
255 // - The base relation itself (i.e. this pointer is based on that one)
256 // - The base defining value relation (i.e. before base_phi insertion)
257 // Generally, after the execution of a full findBasePointer call, only the
258 // base relation will remain. Internally, we add a mixture of the two
259 // types, then update all the second type to the first type
264 
266  /// The set of values known to be live across this safepoint
268 
269  /// Mapping from live pointers to a base-defining-value
271 
272  /// The *new* gc.statepoint instruction itself. This produces the token
273  /// that normal path gc.relocates and the gc.result are tied to.
275 
276  /// Instruction to which exceptional gc relocates are attached
277  /// Makes it easier to iterate through them during relocationViaAlloca.
279 
280  /// Record live values we are rematerialized instead of relocating.
281  /// They are not included into 'LiveSet' field.
282  /// Maps rematerialized copy to it's original value.
284 };
285 
286 } // end anonymous namespace
287 
289  Optional<OperandBundleUse> DeoptBundle =
291 
292  if (!DeoptBundle.hasValue()) {
294  "Found non-leaf call without deopt info!");
295  return None;
296  }
297 
298  return DeoptBundle.getValue().Inputs;
299 }
300 
301 /// Compute the live-in set for every basic block in the function
302 static void computeLiveInValues(DominatorTree &DT, Function &F,
303  GCPtrLivenessData &Data);
304 
305 /// Given results from the dataflow liveness computation, find the set of live
306 /// Values at a particular instruction.
307 static void findLiveSetAtInst(Instruction *inst, GCPtrLivenessData &Data,
308  StatepointLiveSetTy &out);
309 
310 // TODO: Once we can get to the GCStrategy, this becomes
311 // Optional<bool> isGCManagedPointer(const Type *Ty) const override {
312 
313 static bool isGCPointerType(Type *T) {
314  if (auto *PT = dyn_cast<PointerType>(T))
315  // For the sake of this example GC, we arbitrarily pick addrspace(1) as our
316  // GC managed heap. We know that a pointer into this heap needs to be
317  // updated and that no other pointer does.
318  return PT->getAddressSpace() == 1;
319  return false;
320 }
321 
322 // Return true if this type is one which a) is a gc pointer or contains a GC
323 // pointer and b) is of a type this code expects to encounter as a live value.
324 // (The insertion code will assert that a type which matches (a) and not (b)
325 // is not encountered.)
327  // We fully support gc pointers
328  if (isGCPointerType(T))
329  return true;
330  // We partially support vectors of gc pointers. The code will assert if it
331  // can't handle something.
332  if (auto VT = dyn_cast<VectorType>(T))
333  if (isGCPointerType(VT->getElementType()))
334  return true;
335  return false;
336 }
337 
338 #ifndef NDEBUG
339 /// Returns true if this type contains a gc pointer whether we know how to
340 /// handle that type or not.
341 static bool containsGCPtrType(Type *Ty) {
342  if (isGCPointerType(Ty))
343  return true;
344  if (VectorType *VT = dyn_cast<VectorType>(Ty))
345  return isGCPointerType(VT->getScalarType());
346  if (ArrayType *AT = dyn_cast<ArrayType>(Ty))
347  return containsGCPtrType(AT->getElementType());
348  if (StructType *ST = dyn_cast<StructType>(Ty))
349  return llvm::any_of(ST->subtypes(), containsGCPtrType);
350  return false;
351 }
352 
353 // Returns true if this is a type which a) is a gc pointer or contains a GC
354 // pointer and b) is of a type which the code doesn't expect (i.e. first class
355 // aggregates). Used to trip assertions.
356 static bool isUnhandledGCPointerType(Type *Ty) {
357  return containsGCPtrType(Ty) && !isHandledGCPointerType(Ty);
358 }
359 #endif
360 
361 // Return the name of the value suffixed with the provided value, or if the
362 // value didn't have a name, the default value specified.
363 static std::string suffixed_name_or(Value *V, StringRef Suffix,
364  StringRef DefaultName) {
365  return V->hasName() ? (V->getName() + Suffix).str() : DefaultName.str();
366 }
367 
368 // Conservatively identifies any definitions which might be live at the
369 // given instruction. The analysis is performed immediately before the
370 // given instruction. Values defined by that instruction are not considered
371 // live. Values used by that instruction are considered live.
372 static void
374  GCPtrLivenessData &OriginalLivenessData, CallSite CS,
375  PartiallyConstructedSafepointRecord &Result) {
376  Instruction *Inst = CS.getInstruction();
377 
378  StatepointLiveSetTy LiveSet;
379  findLiveSetAtInst(Inst, OriginalLivenessData, LiveSet);
380 
381  if (PrintLiveSet) {
382  dbgs() << "Live Variables:\n";
383  for (Value *V : LiveSet)
384  dbgs() << " " << V->getName() << " " << *V << "\n";
385  }
386  if (PrintLiveSetSize) {
387  dbgs() << "Safepoint For: " << CS.getCalledValue()->getName() << "\n";
388  dbgs() << "Number live values: " << LiveSet.size() << "\n";
389  }
390  Result.LiveSet = LiveSet;
391 }
392 
393 static bool isKnownBaseResult(Value *V);
394 
395 namespace {
396 
397 /// A single base defining value - An immediate base defining value for an
398 /// instruction 'Def' is an input to 'Def' whose base is also a base of 'Def'.
399 /// For instructions which have multiple pointer [vector] inputs or that
400 /// transition between vector and scalar types, there is no immediate base
401 /// defining value. The 'base defining value' for 'Def' is the transitive
402 /// closure of this relation stopping at the first instruction which has no
403 /// immediate base defining value. The b.d.v. might itself be a base pointer,
404 /// but it can also be an arbitrary derived pointer.
405 struct BaseDefiningValueResult {
406  /// Contains the value which is the base defining value.
407  Value * const BDV;
408 
409  /// True if the base defining value is also known to be an actual base
410  /// pointer.
411  const bool IsKnownBase;
412 
413  BaseDefiningValueResult(Value *BDV, bool IsKnownBase)
414  : BDV(BDV), IsKnownBase(IsKnownBase) {
415 #ifndef NDEBUG
416  // Check consistency between new and old means of checking whether a BDV is
417  // a base.
418  bool MustBeBase = isKnownBaseResult(BDV);
419  assert(!MustBeBase || MustBeBase == IsKnownBase);
420 #endif
421  }
422 };
423 
424 } // end anonymous namespace
425 
426 static BaseDefiningValueResult findBaseDefiningValue(Value *I);
427 
428 /// Return a base defining value for the 'Index' element of the given vector
429 /// instruction 'I'. If Index is null, returns a BDV for the entire vector
430 /// 'I'. As an optimization, this method will try to determine when the
431 /// element is known to already be a base pointer. If this can be established,
432 /// the second value in the returned pair will be true. Note that either a
433 /// vector or a pointer typed value can be returned. For the former, the
434 /// vector returned is a BDV (and possibly a base) of the entire vector 'I'.
435 /// If the later, the return pointer is a BDV (or possibly a base) for the
436 /// particular element in 'I'.
437 static BaseDefiningValueResult
439  // Each case parallels findBaseDefiningValue below, see that code for
440  // detailed motivation.
441 
442  if (isa<Argument>(I))
443  // An incoming argument to the function is a base pointer
444  return BaseDefiningValueResult(I, true);
445 
446  if (isa<Constant>(I))
447  // Base of constant vector consists only of constant null pointers.
448  // For reasoning see similar case inside 'findBaseDefiningValue' function.
449  return BaseDefiningValueResult(ConstantAggregateZero::get(I->getType()),
450  true);
451 
452  if (isa<LoadInst>(I))
453  return BaseDefiningValueResult(I, true);
454 
455  if (isa<InsertElementInst>(I))
456  // We don't know whether this vector contains entirely base pointers or
457  // not. To be conservatively correct, we treat it as a BDV and will
458  // duplicate code as needed to construct a parallel vector of bases.
459  return BaseDefiningValueResult(I, false);
460 
461  if (isa<ShuffleVectorInst>(I))
462  // We don't know whether this vector contains entirely base pointers or
463  // not. To be conservatively correct, we treat it as a BDV and will
464  // duplicate code as needed to construct a parallel vector of bases.
465  // TODO: There a number of local optimizations which could be applied here
466  // for particular sufflevector patterns.
467  return BaseDefiningValueResult(I, false);
468 
469  // The behavior of getelementptr instructions is the same for vector and
470  // non-vector data types.
471  if (auto *GEP = dyn_cast<GetElementPtrInst>(I))
472  return findBaseDefiningValue(GEP->getPointerOperand());
473 
474  // If the pointer comes through a bitcast of a vector of pointers to
475  // a vector of another type of pointer, then look through the bitcast
476  if (auto *BC = dyn_cast<BitCastInst>(I))
477  return findBaseDefiningValue(BC->getOperand(0));
478 
479  // A PHI or Select is a base defining value. The outer findBasePointer
480  // algorithm is responsible for constructing a base value for this BDV.
481  assert((isa<SelectInst>(I) || isa<PHINode>(I)) &&
482  "unknown vector instruction - no base found for vector element");
483  return BaseDefiningValueResult(I, false);
484 }
485 
486 /// Helper function for findBasePointer - Will return a value which either a)
487 /// defines the base pointer for the input, b) blocks the simple search
488 /// (i.e. a PHI or Select of two derived pointers), or c) involves a change
489 /// from pointer to vector type or back.
490 static BaseDefiningValueResult findBaseDefiningValue(Value *I) {
492  "Illegal to ask for the base pointer of a non-pointer type");
493 
494  if (I->getType()->isVectorTy())
496 
497  if (isa<Argument>(I))
498  // An incoming argument to the function is a base pointer
499  // We should have never reached here if this argument isn't an gc value
500  return BaseDefiningValueResult(I, true);
501 
502  if (isa<Constant>(I)) {
503  // We assume that objects with a constant base (e.g. a global) can't move
504  // and don't need to be reported to the collector because they are always
505  // live. Besides global references, all kinds of constants (e.g. undef,
506  // constant expressions, null pointers) can be introduced by the inliner or
507  // the optimizer, especially on dynamically dead paths.
508  // Here we treat all of them as having single null base. By doing this we
509  // trying to avoid problems reporting various conflicts in a form of
510  // "phi (const1, const2)" or "phi (const, regular gc ptr)".
511  // See constant.ll file for relevant test cases.
512 
513  return BaseDefiningValueResult(
514  ConstantPointerNull::get(cast<PointerType>(I->getType())), true);
515  }
516 
517  if (CastInst *CI = dyn_cast<CastInst>(I)) {
518  Value *Def = CI->stripPointerCasts();
519  // If stripping pointer casts changes the address space there is an
520  // addrspacecast in between.
521  assert(cast<PointerType>(Def->getType())->getAddressSpace() ==
522  cast<PointerType>(CI->getType())->getAddressSpace() &&
523  "unsupported addrspacecast");
524  // If we find a cast instruction here, it means we've found a cast which is
525  // not simply a pointer cast (i.e. an inttoptr). We don't know how to
526  // handle int->ptr conversion.
527  assert(!isa<CastInst>(Def) && "shouldn't find another cast here");
528  return findBaseDefiningValue(Def);
529  }
530 
531  if (isa<LoadInst>(I))
532  // The value loaded is an gc base itself
533  return BaseDefiningValueResult(I, true);
534 
535  if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(I))
536  // The base of this GEP is the base
537  return findBaseDefiningValue(GEP->getPointerOperand());
538 
539  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
540  switch (II->getIntrinsicID()) {
541  default:
542  // fall through to general call handling
543  break;
544  case Intrinsic::experimental_gc_statepoint:
545  llvm_unreachable("statepoints don't produce pointers");
546  case Intrinsic::experimental_gc_relocate:
547  // Rerunning safepoint insertion after safepoints are already
548  // inserted is not supported. It could probably be made to work,
549  // but why are you doing this? There's no good reason.
550  llvm_unreachable("repeat safepoint insertion is not supported");
551  case Intrinsic::gcroot:
552  // Currently, this mechanism hasn't been extended to work with gcroot.
553  // There's no reason it couldn't be, but I haven't thought about the
554  // implications much.
556  "interaction with the gcroot mechanism is not supported");
557  }
558  }
559  // We assume that functions in the source language only return base
560  // pointers. This should probably be generalized via attributes to support
561  // both source language and internal functions.
562  if (isa<CallInst>(I) || isa<InvokeInst>(I))
563  return BaseDefiningValueResult(I, true);
564 
565  // TODO: I have absolutely no idea how to implement this part yet. It's not
566  // necessarily hard, I just haven't really looked at it yet.
567  assert(!isa<LandingPadInst>(I) && "Landing Pad is unimplemented");
568 
569  if (isa<AtomicCmpXchgInst>(I))
570  // A CAS is effectively a atomic store and load combined under a
571  // predicate. From the perspective of base pointers, we just treat it
572  // like a load.
573  return BaseDefiningValueResult(I, true);
574 
575  assert(!isa<AtomicRMWInst>(I) && "Xchg handled above, all others are "
576  "binary ops which don't apply to pointers");
577 
578  // The aggregate ops. Aggregates can either be in the heap or on the
579  // stack, but in either case, this is simply a field load. As a result,
580  // this is a defining definition of the base just like a load is.
581  if (isa<ExtractValueInst>(I))
582  return BaseDefiningValueResult(I, true);
583 
584  // We should never see an insert vector since that would require we be
585  // tracing back a struct value not a pointer value.
586  assert(!isa<InsertValueInst>(I) &&
587  "Base pointer for a struct is meaningless");
588 
589  // An extractelement produces a base result exactly when it's input does.
590  // We may need to insert a parallel instruction to extract the appropriate
591  // element out of the base vector corresponding to the input. Given this,
592  // it's analogous to the phi and select case even though it's not a merge.
593  if (isa<ExtractElementInst>(I))
594  // Note: There a lot of obvious peephole cases here. This are deliberately
595  // handled after the main base pointer inference algorithm to make writing
596  // test cases to exercise that code easier.
597  return BaseDefiningValueResult(I, false);
598 
599  // The last two cases here don't return a base pointer. Instead, they
600  // return a value which dynamically selects from among several base
601  // derived pointers (each with it's own base potentially). It's the job of
602  // the caller to resolve these.
603  assert((isa<SelectInst>(I) || isa<PHINode>(I)) &&
604  "missing instruction case in findBaseDefiningValing");
605  return BaseDefiningValueResult(I, false);
606 }
607 
608 /// Returns the base defining value for this value.
610  Value *&Cached = Cache[I];
611  if (!Cached) {
612  Cached = findBaseDefiningValue(I).BDV;
613  DEBUG(dbgs() << "fBDV-cached: " << I->getName() << " -> "
614  << Cached->getName() << "\n");
615  }
616  assert(Cache[I] != nullptr);
617  return Cached;
618 }
619 
620 /// Return a base pointer for this value if known. Otherwise, return it's
621 /// base defining value.
624  auto Found = Cache.find(Def);
625  if (Found != Cache.end()) {
626  // Either a base-of relation, or a self reference. Caller must check.
627  return Found->second;
628  }
629  // Only a BDV available
630  return Def;
631 }
632 
633 /// Given the result of a call to findBaseDefiningValue, or findBaseOrBDV,
634 /// is it known to be a base pointer? Or do we need to continue searching.
635 static bool isKnownBaseResult(Value *V) {
636  if (!isa<PHINode>(V) && !isa<SelectInst>(V) &&
637  !isa<ExtractElementInst>(V) && !isa<InsertElementInst>(V) &&
638  !isa<ShuffleVectorInst>(V)) {
639  // no recursion possible
640  return true;
641  }
642  if (isa<Instruction>(V) &&
643  cast<Instruction>(V)->getMetadata("is_base_value")) {
644  // This is a previously inserted base phi or select. We know
645  // that this is a base value.
646  return true;
647  }
648 
649  // We need to keep searching
650  return false;
651 }
652 
653 namespace {
654 
655 /// Models the state of a single base defining value in the findBasePointer
656 /// algorithm for determining where a new instruction is needed to propagate
657 /// the base of this BDV.
658 class BDVState {
659 public:
660  enum Status { Unknown, Base, Conflict };
661 
662  BDVState() : BaseValue(nullptr) {}
663 
664  explicit BDVState(Status Status, Value *BaseValue = nullptr)
665  : Status(Status), BaseValue(BaseValue) {
666  assert(Status != Base || BaseValue);
667  }
668 
669  explicit BDVState(Value *BaseValue) : Status(Base), BaseValue(BaseValue) {}
670 
671  Status getStatus() const { return Status; }
672  Value *getBaseValue() const { return BaseValue; }
673 
674  bool isBase() const { return getStatus() == Base; }
675  bool isUnknown() const { return getStatus() == Unknown; }
676  bool isConflict() const { return getStatus() == Conflict; }
677 
678  bool operator==(const BDVState &Other) const {
679  return BaseValue == Other.BaseValue && Status == Other.Status;
680  }
681 
682  bool operator!=(const BDVState &other) const { return !(*this == other); }
683 
685  void dump() const {
686  print(dbgs());
687  dbgs() << '\n';
688  }
689 
690  void print(raw_ostream &OS) const {
691  switch (getStatus()) {
692  case Unknown:
693  OS << "U";
694  break;
695  case Base:
696  OS << "B";
697  break;
698  case Conflict:
699  OS << "C";
700  break;
701  }
702  OS << " (" << getBaseValue() << " - "
703  << (getBaseValue() ? getBaseValue()->getName() : "nullptr") << "): ";
704  }
705 
706 private:
707  Status Status = Unknown;
708  AssertingVH<Value> BaseValue; // Non-null only if Status == Base.
709 };
710 
711 } // end anonymous namespace
712 
713 #ifndef NDEBUG
714 static raw_ostream &operator<<(raw_ostream &OS, const BDVState &State) {
715  State.print(OS);
716  return OS;
717 }
718 #endif
719 
720 static BDVState meetBDVStateImpl(const BDVState &LHS, const BDVState &RHS) {
721  switch (LHS.getStatus()) {
722  case BDVState::Unknown:
723  return RHS;
724 
725  case BDVState::Base:
726  assert(LHS.getBaseValue() && "can't be null");
727  if (RHS.isUnknown())
728  return LHS;
729 
730  if (RHS.isBase()) {
731  if (LHS.getBaseValue() == RHS.getBaseValue()) {
732  assert(LHS == RHS && "equality broken!");
733  return LHS;
734  }
735  return BDVState(BDVState::Conflict);
736  }
737  assert(RHS.isConflict() && "only three states!");
738  return BDVState(BDVState::Conflict);
739 
740  case BDVState::Conflict:
741  return LHS;
742  }
743  llvm_unreachable("only three states!");
744 }
745 
746 // Values of type BDVState form a lattice, and this function implements the meet
747 // operation.
748 static BDVState meetBDVState(const BDVState &LHS, const BDVState &RHS) {
749  BDVState Result = meetBDVStateImpl(LHS, RHS);
750  assert(Result == meetBDVStateImpl(RHS, LHS) &&
751  "Math is wrong: meet does not commute!");
752  return Result;
753 }
754 
755 /// For a given value or instruction, figure out what base ptr its derived from.
756 /// For gc objects, this is simply itself. On success, returns a value which is
757 /// the base pointer. (This is reliable and can be used for relocation.) On
758 /// failure, returns nullptr.
760  Value *Def = findBaseOrBDV(I, Cache);
761 
762  if (isKnownBaseResult(Def))
763  return Def;
764 
765  // Here's the rough algorithm:
766  // - For every SSA value, construct a mapping to either an actual base
767  // pointer or a PHI which obscures the base pointer.
768  // - Construct a mapping from PHI to unknown TOP state. Use an
769  // optimistic algorithm to propagate base pointer information. Lattice
770  // looks like:
771  // UNKNOWN
772  // b1 b2 b3 b4
773  // CONFLICT
774  // When algorithm terminates, all PHIs will either have a single concrete
775  // base or be in a conflict state.
776  // - For every conflict, insert a dummy PHI node without arguments. Add
777  // these to the base[Instruction] = BasePtr mapping. For every
778  // non-conflict, add the actual base.
779  // - For every conflict, add arguments for the base[a] of each input
780  // arguments.
781  //
782  // Note: A simpler form of this would be to add the conflict form of all
783  // PHIs without running the optimistic algorithm. This would be
784  // analogous to pessimistic data flow and would likely lead to an
785  // overall worse solution.
786 
787 #ifndef NDEBUG
788  auto isExpectedBDVType = [](Value *BDV) {
789  return isa<PHINode>(BDV) || isa<SelectInst>(BDV) ||
790  isa<ExtractElementInst>(BDV) || isa<InsertElementInst>(BDV) ||
791  isa<ShuffleVectorInst>(BDV);
792  };
793 #endif
794 
795  // Once populated, will contain a mapping from each potentially non-base BDV
796  // to a lattice value (described above) which corresponds to that BDV.
797  // We use the order of insertion (DFS over the def/use graph) to provide a
798  // stable deterministic ordering for visiting DenseMaps (which are unordered)
799  // below. This is important for deterministic compilation.
801 
802  // Recursively fill in all base defining values reachable from the initial
803  // one for which we don't already know a definite base value for
804  /* scope */ {
805  SmallVector<Value*, 16> Worklist;
806  Worklist.push_back(Def);
807  States.insert({Def, BDVState()});
808  while (!Worklist.empty()) {
809  Value *Current = Worklist.pop_back_val();
810  assert(!isKnownBaseResult(Current) && "why did it get added?");
811 
812  auto visitIncomingValue = [&](Value *InVal) {
813  Value *Base = findBaseOrBDV(InVal, Cache);
814  if (isKnownBaseResult(Base))
815  // Known bases won't need new instructions introduced and can be
816  // ignored safely
817  return;
818  assert(isExpectedBDVType(Base) && "the only non-base values "
819  "we see should be base defining values");
820  if (States.insert(std::make_pair(Base, BDVState())).second)
821  Worklist.push_back(Base);
822  };
823  if (PHINode *PN = dyn_cast<PHINode>(Current)) {
824  for (Value *InVal : PN->incoming_values())
825  visitIncomingValue(InVal);
826  } else if (SelectInst *SI = dyn_cast<SelectInst>(Current)) {
827  visitIncomingValue(SI->getTrueValue());
828  visitIncomingValue(SI->getFalseValue());
829  } else if (auto *EE = dyn_cast<ExtractElementInst>(Current)) {
830  visitIncomingValue(EE->getVectorOperand());
831  } else if (auto *IE = dyn_cast<InsertElementInst>(Current)) {
832  visitIncomingValue(IE->getOperand(0)); // vector operand
833  visitIncomingValue(IE->getOperand(1)); // scalar operand
834  } else if (auto *SV = dyn_cast<ShuffleVectorInst>(Current)) {
835  visitIncomingValue(SV->getOperand(0));
836  visitIncomingValue(SV->getOperand(1));
837  }
838  else {
839  llvm_unreachable("Unimplemented instruction case");
840  }
841  }
842  }
843 
844 #ifndef NDEBUG
845  DEBUG(dbgs() << "States after initialization:\n");
846  for (auto Pair : States) {
847  DEBUG(dbgs() << " " << Pair.second << " for " << *Pair.first << "\n");
848  }
849 #endif
850 
851  // Return a phi state for a base defining value. We'll generate a new
852  // base state for known bases and expect to find a cached state otherwise.
853  auto getStateForBDV = [&](Value *baseValue) {
854  if (isKnownBaseResult(baseValue))
855  return BDVState(baseValue);
856  auto I = States.find(baseValue);
857  assert(I != States.end() && "lookup failed!");
858  return I->second;
859  };
860 
861  bool Progress = true;
862  while (Progress) {
863 #ifndef NDEBUG
864  const size_t OldSize = States.size();
865 #endif
866  Progress = false;
867  // We're only changing values in this loop, thus safe to keep iterators.
868  // Since this is computing a fixed point, the order of visit does not
869  // effect the result. TODO: We could use a worklist here and make this run
870  // much faster.
871  for (auto Pair : States) {
872  Value *BDV = Pair.first;
873  assert(!isKnownBaseResult(BDV) && "why did it get added?");
874 
875  // Given an input value for the current instruction, return a BDVState
876  // instance which represents the BDV of that value.
877  auto getStateForInput = [&](Value *V) mutable {
878  Value *BDV = findBaseOrBDV(V, Cache);
879  return getStateForBDV(BDV);
880  };
881 
882  BDVState NewState;
883  if (SelectInst *SI = dyn_cast<SelectInst>(BDV)) {
884  NewState = meetBDVState(NewState, getStateForInput(SI->getTrueValue()));
885  NewState =
886  meetBDVState(NewState, getStateForInput(SI->getFalseValue()));
887  } else if (PHINode *PN = dyn_cast<PHINode>(BDV)) {
888  for (Value *Val : PN->incoming_values())
889  NewState = meetBDVState(NewState, getStateForInput(Val));
890  } else if (auto *EE = dyn_cast<ExtractElementInst>(BDV)) {
891  // The 'meet' for an extractelement is slightly trivial, but it's still
892  // useful in that it drives us to conflict if our input is.
893  NewState =
894  meetBDVState(NewState, getStateForInput(EE->getVectorOperand()));
895  } else if (auto *IE = dyn_cast<InsertElementInst>(BDV)){
896  // Given there's a inherent type mismatch between the operands, will
897  // *always* produce Conflict.
898  NewState = meetBDVState(NewState, getStateForInput(IE->getOperand(0)));
899  NewState = meetBDVState(NewState, getStateForInput(IE->getOperand(1)));
900  } else {
901  // The only instance this does not return a Conflict is when both the
902  // vector operands are the same vector.
903  auto *SV = cast<ShuffleVectorInst>(BDV);
904  NewState = meetBDVState(NewState, getStateForInput(SV->getOperand(0)));
905  NewState = meetBDVState(NewState, getStateForInput(SV->getOperand(1)));
906  }
907 
908  BDVState OldState = States[BDV];
909  if (OldState != NewState) {
910  Progress = true;
911  States[BDV] = NewState;
912  }
913  }
914 
915  assert(OldSize == States.size() &&
916  "fixed point shouldn't be adding any new nodes to state");
917  }
918 
919 #ifndef NDEBUG
920  DEBUG(dbgs() << "States after meet iteration:\n");
921  for (auto Pair : States) {
922  DEBUG(dbgs() << " " << Pair.second << " for " << *Pair.first << "\n");
923  }
924 #endif
925 
926  // Insert Phis for all conflicts
927  // TODO: adjust naming patterns to avoid this order of iteration dependency
928  for (auto Pair : States) {
929  Instruction *I = cast<Instruction>(Pair.first);
930  BDVState State = Pair.second;
931  assert(!isKnownBaseResult(I) && "why did it get added?");
932  assert(!State.isUnknown() && "Optimistic algorithm didn't complete!");
933 
934  // extractelement instructions are a bit special in that we may need to
935  // insert an extract even when we know an exact base for the instruction.
936  // The problem is that we need to convert from a vector base to a scalar
937  // base for the particular indice we're interested in.
938  if (State.isBase() && isa<ExtractElementInst>(I) &&
939  isa<VectorType>(State.getBaseValue()->getType())) {
940  auto *EE = cast<ExtractElementInst>(I);
941  // TODO: In many cases, the new instruction is just EE itself. We should
942  // exploit this, but can't do it here since it would break the invariant
943  // about the BDV not being known to be a base.
944  auto *BaseInst = ExtractElementInst::Create(
945  State.getBaseValue(), EE->getIndexOperand(), "base_ee", EE);
946  BaseInst->setMetadata("is_base_value", MDNode::get(I->getContext(), {}));
947  States[I] = BDVState(BDVState::Base, BaseInst);
948  }
949 
950  // Since we're joining a vector and scalar base, they can never be the
951  // same. As a result, we should always see insert element having reached
952  // the conflict state.
953  assert(!isa<InsertElementInst>(I) || State.isConflict());
954 
955  if (!State.isConflict())
956  continue;
957 
958  /// Create and insert a new instruction which will represent the base of
959  /// the given instruction 'I'.
960  auto MakeBaseInstPlaceholder = [](Instruction *I) -> Instruction* {
961  if (isa<PHINode>(I)) {
962  BasicBlock *BB = I->getParent();
963  int NumPreds = std::distance(pred_begin(BB), pred_end(BB));
964  assert(NumPreds > 0 && "how did we reach here");
965  std::string Name = suffixed_name_or(I, ".base", "base_phi");
966  return PHINode::Create(I->getType(), NumPreds, Name, I);
967  } else if (SelectInst *SI = dyn_cast<SelectInst>(I)) {
968  // The undef will be replaced later
969  UndefValue *Undef = UndefValue::get(SI->getType());
970  std::string Name = suffixed_name_or(I, ".base", "base_select");
971  return SelectInst::Create(SI->getCondition(), Undef, Undef, Name, SI);
972  } else if (auto *EE = dyn_cast<ExtractElementInst>(I)) {
973  UndefValue *Undef = UndefValue::get(EE->getVectorOperand()->getType());
974  std::string Name = suffixed_name_or(I, ".base", "base_ee");
975  return ExtractElementInst::Create(Undef, EE->getIndexOperand(), Name,
976  EE);
977  } else if (auto *IE = dyn_cast<InsertElementInst>(I)) {
978  UndefValue *VecUndef = UndefValue::get(IE->getOperand(0)->getType());
979  UndefValue *ScalarUndef = UndefValue::get(IE->getOperand(1)->getType());
980  std::string Name = suffixed_name_or(I, ".base", "base_ie");
981  return InsertElementInst::Create(VecUndef, ScalarUndef,
982  IE->getOperand(2), Name, IE);
983  } else {
984  auto *SV = cast<ShuffleVectorInst>(I);
985  UndefValue *VecUndef = UndefValue::get(SV->getOperand(0)->getType());
986  std::string Name = suffixed_name_or(I, ".base", "base_sv");
987  return new ShuffleVectorInst(VecUndef, VecUndef, SV->getOperand(2),
988  Name, SV);
989  }
990  };
991  Instruction *BaseInst = MakeBaseInstPlaceholder(I);
992  // Add metadata marking this as a base value
993  BaseInst->setMetadata("is_base_value", MDNode::get(I->getContext(), {}));
994  States[I] = BDVState(BDVState::Conflict, BaseInst);
995  }
996 
997  // Returns a instruction which produces the base pointer for a given
998  // instruction. The instruction is assumed to be an input to one of the BDVs
999  // seen in the inference algorithm above. As such, we must either already
1000  // know it's base defining value is a base, or have inserted a new
1001  // instruction to propagate the base of it's BDV and have entered that newly
1002  // introduced instruction into the state table. In either case, we are
1003  // assured to be able to determine an instruction which produces it's base
1004  // pointer.
1005  auto getBaseForInput = [&](Value *Input, Instruction *InsertPt) {
1006  Value *BDV = findBaseOrBDV(Input, Cache);
1007  Value *Base = nullptr;
1008  if (isKnownBaseResult(BDV)) {
1009  Base = BDV;
1010  } else {
1011  // Either conflict or base.
1012  assert(States.count(BDV));
1013  Base = States[BDV].getBaseValue();
1014  }
1015  assert(Base && "Can't be null");
1016  // The cast is needed since base traversal may strip away bitcasts
1017  if (Base->getType() != Input->getType() && InsertPt)
1018  Base = new BitCastInst(Base, Input->getType(), "cast", InsertPt);
1019  return Base;
1020  };
1021 
1022  // Fixup all the inputs of the new PHIs. Visit order needs to be
1023  // deterministic and predictable because we're naming newly created
1024  // instructions.
1025  for (auto Pair : States) {
1026  Instruction *BDV = cast<Instruction>(Pair.first);
1027  BDVState State = Pair.second;
1028 
1029  assert(!isKnownBaseResult(BDV) && "why did it get added?");
1030  assert(!State.isUnknown() && "Optimistic algorithm didn't complete!");
1031  if (!State.isConflict())
1032  continue;
1033 
1034  if (PHINode *BasePHI = dyn_cast<PHINode>(State.getBaseValue())) {
1035  PHINode *PN = cast<PHINode>(BDV);
1036  unsigned NumPHIValues = PN->getNumIncomingValues();
1037  for (unsigned i = 0; i < NumPHIValues; i++) {
1038  Value *InVal = PN->getIncomingValue(i);
1039  BasicBlock *InBB = PN->getIncomingBlock(i);
1040 
1041  // If we've already seen InBB, add the same incoming value
1042  // we added for it earlier. The IR verifier requires phi
1043  // nodes with multiple entries from the same basic block
1044  // to have the same incoming value for each of those
1045  // entries. If we don't do this check here and basephi
1046  // has a different type than base, we'll end up adding two
1047  // bitcasts (and hence two distinct values) as incoming
1048  // values for the same basic block.
1049 
1050  int BlockIndex = BasePHI->getBasicBlockIndex(InBB);
1051  if (BlockIndex != -1) {
1052  Value *OldBase = BasePHI->getIncomingValue(BlockIndex);
1053  BasePHI->addIncoming(OldBase, InBB);
1054 
1055 #ifndef NDEBUG
1056  Value *Base = getBaseForInput(InVal, nullptr);
1057  // In essence this assert states: the only way two values
1058  // incoming from the same basic block may be different is by
1059  // being different bitcasts of the same value. A cleanup
1060  // that remains TODO is changing findBaseOrBDV to return an
1061  // llvm::Value of the correct type (and still remain pure).
1062  // This will remove the need to add bitcasts.
1063  assert(Base->stripPointerCasts() == OldBase->stripPointerCasts() &&
1064  "Sanity -- findBaseOrBDV should be pure!");
1065 #endif
1066  continue;
1067  }
1068 
1069  // Find the instruction which produces the base for each input. We may
1070  // need to insert a bitcast in the incoming block.
1071  // TODO: Need to split critical edges if insertion is needed
1072  Value *Base = getBaseForInput(InVal, InBB->getTerminator());
1073  BasePHI->addIncoming(Base, InBB);
1074  }
1075  assert(BasePHI->getNumIncomingValues() == NumPHIValues);
1076  } else if (SelectInst *BaseSI =
1077  dyn_cast<SelectInst>(State.getBaseValue())) {
1078  SelectInst *SI = cast<SelectInst>(BDV);
1079 
1080  // Find the instruction which produces the base for each input.
1081  // We may need to insert a bitcast.
1082  BaseSI->setTrueValue(getBaseForInput(SI->getTrueValue(), BaseSI));
1083  BaseSI->setFalseValue(getBaseForInput(SI->getFalseValue(), BaseSI));
1084  } else if (auto *BaseEE =
1085  dyn_cast<ExtractElementInst>(State.getBaseValue())) {
1086  Value *InVal = cast<ExtractElementInst>(BDV)->getVectorOperand();
1087  // Find the instruction which produces the base for each input. We may
1088  // need to insert a bitcast.
1089  BaseEE->setOperand(0, getBaseForInput(InVal, BaseEE));
1090  } else if (auto *BaseIE = dyn_cast<InsertElementInst>(State.getBaseValue())){
1091  auto *BdvIE = cast<InsertElementInst>(BDV);
1092  auto UpdateOperand = [&](int OperandIdx) {
1093  Value *InVal = BdvIE->getOperand(OperandIdx);
1094  Value *Base = getBaseForInput(InVal, BaseIE);
1095  BaseIE->setOperand(OperandIdx, Base);
1096  };
1097  UpdateOperand(0); // vector operand
1098  UpdateOperand(1); // scalar operand
1099  } else {
1100  auto *BaseSV = cast<ShuffleVectorInst>(State.getBaseValue());
1101  auto *BdvSV = cast<ShuffleVectorInst>(BDV);
1102  auto UpdateOperand = [&](int OperandIdx) {
1103  Value *InVal = BdvSV->getOperand(OperandIdx);
1104  Value *Base = getBaseForInput(InVal, BaseSV);
1105  BaseSV->setOperand(OperandIdx, Base);
1106  };
1107  UpdateOperand(0); // vector operand
1108  UpdateOperand(1); // vector operand
1109  }
1110  }
1111 
1112  // Cache all of our results so we can cheaply reuse them
1113  // NOTE: This is actually two caches: one of the base defining value
1114  // relation and one of the base pointer relation! FIXME
1115  for (auto Pair : States) {
1116  auto *BDV = Pair.first;
1117  Value *Base = Pair.second.getBaseValue();
1118  assert(BDV && Base);
1119  assert(!isKnownBaseResult(BDV) && "why did it get added?");
1120 
1121  DEBUG(dbgs() << "Updating base value cache"
1122  << " for: " << BDV->getName() << " from: "
1123  << (Cache.count(BDV) ? Cache[BDV]->getName().str() : "none")
1124  << " to: " << Base->getName() << "\n");
1125 
1126  if (Cache.count(BDV)) {
1127  assert(isKnownBaseResult(Base) &&
1128  "must be something we 'know' is a base pointer");
1129  // Once we transition from the BDV relation being store in the Cache to
1130  // the base relation being stored, it must be stable
1131  assert((!isKnownBaseResult(Cache[BDV]) || Cache[BDV] == Base) &&
1132  "base relation should be stable");
1133  }
1134  Cache[BDV] = Base;
1135  }
1136  assert(Cache.count(Def));
1137  return Cache[Def];
1138 }
1139 
1140 // For a set of live pointers (base and/or derived), identify the base
1141 // pointer of the object which they are derived from. This routine will
1142 // mutate the IR graph as needed to make the 'base' pointer live at the
1143 // definition site of 'derived'. This ensures that any use of 'derived' can
1144 // also use 'base'. This may involve the insertion of a number of
1145 // additional PHI nodes.
1146 //
1147 // preconditions: live is a set of pointer type Values
1148 //
1149 // side effects: may insert PHI nodes into the existing CFG, will preserve
1150 // CFG, will not remove or mutate any existing nodes
1151 //
1152 // post condition: PointerToBase contains one (derived, base) pair for every
1153 // pointer in live. Note that derived can be equal to base if the original
1154 // pointer was a base pointer.
1155 static void
1157  MapVector<Value *, Value *> &PointerToBase,
1158  DominatorTree *DT, DefiningValueMapTy &DVCache) {
1159  for (Value *ptr : live) {
1160  Value *base = findBasePointer(ptr, DVCache);
1161  assert(base && "failed to find base pointer");
1162  PointerToBase[ptr] = base;
1163  assert((!isa<Instruction>(base) || !isa<Instruction>(ptr) ||
1164  DT->dominates(cast<Instruction>(base)->getParent(),
1165  cast<Instruction>(ptr)->getParent())) &&
1166  "The base we found better dominate the derived pointer");
1167  }
1168 }
1169 
1170 /// Find the required based pointers (and adjust the live set) for the given
1171 /// parse point.
1173  CallSite CS,
1174  PartiallyConstructedSafepointRecord &result) {
1175  MapVector<Value *, Value *> PointerToBase;
1176  findBasePointers(result.LiveSet, PointerToBase, &DT, DVCache);
1177 
1178  if (PrintBasePointers) {
1179  errs() << "Base Pairs (w/o Relocation):\n";
1180  for (auto &Pair : PointerToBase) {
1181  errs() << " derived ";
1182  Pair.first->printAsOperand(errs(), false);
1183  errs() << " base ";
1184  Pair.second->printAsOperand(errs(), false);
1185  errs() << "\n";;
1186  }
1187  }
1188 
1189  result.PointerToBase = PointerToBase;
1190 }
1191 
1192 /// Given an updated version of the dataflow liveness results, update the
1193 /// liveset and base pointer maps for the call site CS.
1194 static void recomputeLiveInValues(GCPtrLivenessData &RevisedLivenessData,
1195  CallSite CS,
1196  PartiallyConstructedSafepointRecord &result);
1197 
1199  Function &F, DominatorTree &DT, ArrayRef<CallSite> toUpdate,
1201  // TODO-PERF: reuse the original liveness, then simply run the dataflow
1202  // again. The old values are still live and will help it stabilize quickly.
1203  GCPtrLivenessData RevisedLivenessData;
1204  computeLiveInValues(DT, F, RevisedLivenessData);
1205  for (size_t i = 0; i < records.size(); i++) {
1206  struct PartiallyConstructedSafepointRecord &info = records[i];
1207  recomputeLiveInValues(RevisedLivenessData, toUpdate[i], info);
1208  }
1209 }
1210 
1211 // When inserting gc.relocate and gc.result calls, we need to ensure there are
1212 // no uses of the original value / return value between the gc.statepoint and
1213 // the gc.relocate / gc.result call. One case which can arise is a phi node
1214 // starting one of the successor blocks. We also need to be able to insert the
1215 // gc.relocates only on the path which goes through the statepoint. We might
1216 // need to split an edge to make this possible.
1217 static BasicBlock *
1219  DominatorTree &DT) {
1220  BasicBlock *Ret = BB;
1221  if (!BB->getUniquePredecessor())
1222  Ret = SplitBlockPredecessors(BB, InvokeParent, "", &DT);
1223 
1224  // Now that 'Ret' has unique predecessor we can safely remove all phi nodes
1225  // from it
1227  assert(!isa<PHINode>(Ret->begin()) &&
1228  "All PHI nodes should have been removed!");
1229 
1230  // At this point, we can safely insert a gc.relocate or gc.result as the first
1231  // instruction in Ret if needed.
1232  return Ret;
1233 }
1234 
1235 // Create new attribute set containing only attributes which can be transferred
1236 // from original call to the safepoint.
1238  if (AL.isEmpty())
1239  return AL;
1240 
1241  // Remove the readonly, readnone, and statepoint function attributes.
1242  AttrBuilder FnAttrs = AL.getFnAttributes();
1243  FnAttrs.removeAttribute(Attribute::ReadNone);
1244  FnAttrs.removeAttribute(Attribute::ReadOnly);
1245  for (Attribute A : AL.getFnAttributes()) {
1247  FnAttrs.remove(A);
1248  }
1249 
1250  // Just skip parameter and return attributes for now
1251  LLVMContext &Ctx = AL.getContext();
1253  AttributeSet::get(Ctx, FnAttrs));
1254 }
1255 
1256 /// Helper function to place all gc relocates necessary for the given
1257 /// statepoint.
1258 /// Inputs:
1259 /// liveVariables - list of variables to be relocated.
1260 /// liveStart - index of the first live variable.
1261 /// basePtrs - base pointers.
1262 /// statepointToken - statepoint instruction to which relocates should be
1263 /// bound.
1264 /// Builder - Llvm IR builder to be used to construct new calls.
1266  const int LiveStart,
1267  ArrayRef<Value *> BasePtrs,
1268  Instruction *StatepointToken,
1269  IRBuilder<> Builder) {
1270  if (LiveVariables.empty())
1271  return;
1272 
1273  auto FindIndex = [](ArrayRef<Value *> LiveVec, Value *Val) {
1274  auto ValIt = llvm::find(LiveVec, Val);
1275  assert(ValIt != LiveVec.end() && "Val not found in LiveVec!");
1276  size_t Index = std::distance(LiveVec.begin(), ValIt);
1277  assert(Index < LiveVec.size() && "Bug in std::find?");
1278  return Index;
1279  };
1280  Module *M = StatepointToken->getModule();
1281 
1282  // All gc_relocate are generated as i8 addrspace(1)* (or a vector type whose
1283  // element type is i8 addrspace(1)*). We originally generated unique
1284  // declarations for each pointer type, but this proved problematic because
1285  // the intrinsic mangling code is incomplete and fragile. Since we're moving
1286  // towards a single unified pointer type anyways, we can just cast everything
1287  // to an i8* of the right address space. A bitcast is added later to convert
1288  // gc_relocate to the actual value's type.
1289  auto getGCRelocateDecl = [&] (Type *Ty) {
1291  auto AS = Ty->getScalarType()->getPointerAddressSpace();
1292  Type *NewTy = Type::getInt8PtrTy(M->getContext(), AS);
1293  if (auto *VT = dyn_cast<VectorType>(Ty))
1294  NewTy = VectorType::get(NewTy, VT->getNumElements());
1295  return Intrinsic::getDeclaration(M, Intrinsic::experimental_gc_relocate,
1296  {NewTy});
1297  };
1298 
1299  // Lazily populated map from input types to the canonicalized form mentioned
1300  // in the comment above. This should probably be cached somewhere more
1301  // broadly.
1302  DenseMap<Type*, Value*> TypeToDeclMap;
1303 
1304  for (unsigned i = 0; i < LiveVariables.size(); i++) {
1305  // Generate the gc.relocate call and save the result
1306  Value *BaseIdx =
1307  Builder.getInt32(LiveStart + FindIndex(LiveVariables, BasePtrs[i]));
1308  Value *LiveIdx = Builder.getInt32(LiveStart + i);
1309 
1310  Type *Ty = LiveVariables[i]->getType();
1311  if (!TypeToDeclMap.count(Ty))
1312  TypeToDeclMap[Ty] = getGCRelocateDecl(Ty);
1313  Value *GCRelocateDecl = TypeToDeclMap[Ty];
1314 
1315  // only specify a debug name if we can give a useful one
1316  CallInst *Reloc = Builder.CreateCall(
1317  GCRelocateDecl, {StatepointToken, BaseIdx, LiveIdx},
1318  suffixed_name_or(LiveVariables[i], ".relocated", ""));
1319  // Trick CodeGen into thinking there are lots of free registers at this
1320  // fake call.
1322  }
1323 }
1324 
1325 namespace {
1326 
1327 /// This struct is used to defer RAUWs and `eraseFromParent` s. Using this
1328 /// avoids having to worry about keeping around dangling pointers to Values.
1329 class DeferredReplacement {
1332  bool IsDeoptimize = false;
1333 
1334  DeferredReplacement() = default;
1335 
1336 public:
1337  static DeferredReplacement createRAUW(Instruction *Old, Instruction *New) {
1338  assert(Old != New && Old && New &&
1339  "Cannot RAUW equal values or to / from null!");
1340 
1341  DeferredReplacement D;
1342  D.Old = Old;
1343  D.New = New;
1344  return D;
1345  }
1346 
1347  static DeferredReplacement createDelete(Instruction *ToErase) {
1348  DeferredReplacement D;
1349  D.Old = ToErase;
1350  return D;
1351  }
1352 
1353  static DeferredReplacement createDeoptimizeReplacement(Instruction *Old) {
1354 #ifndef NDEBUG
1355  auto *F = cast<CallInst>(Old)->getCalledFunction();
1356  assert(F && F->getIntrinsicID() == Intrinsic::experimental_deoptimize &&
1357  "Only way to construct a deoptimize deferred replacement");
1358 #endif
1359  DeferredReplacement D;
1360  D.Old = Old;
1361  D.IsDeoptimize = true;
1362  return D;
1363  }
1364 
1365  /// Does the task represented by this instance.
1366  void doReplacement() {
1367  Instruction *OldI = Old;
1368  Instruction *NewI = New;
1369 
1370  assert(OldI != NewI && "Disallowed at construction?!");
1371  assert((!IsDeoptimize || !New) &&
1372  "Deoptimize instrinsics are not replaced!");
1373 
1374  Old = nullptr;
1375  New = nullptr;
1376 
1377  if (NewI)
1378  OldI->replaceAllUsesWith(NewI);
1379 
1380  if (IsDeoptimize) {
1381  // Note: we've inserted instructions, so the call to llvm.deoptimize may
1382  // not necessarilly be followed by the matching return.
1383  auto *RI = cast<ReturnInst>(OldI->getParent()->getTerminator());
1384  new UnreachableInst(RI->getContext(), RI);
1385  RI->eraseFromParent();
1386  }
1387 
1388  OldI->eraseFromParent();
1389  }
1390 };
1391 
1392 } // end anonymous namespace
1393 
1395  const char *DeoptLowering = "deopt-lowering";
1396  if (CS.hasFnAttr(DeoptLowering)) {
1397  // FIXME: CallSite has a *really* confusing interface around attributes
1398  // with values.
1399  const AttributeList &CSAS = CS.getAttributes();
1400  if (CSAS.hasAttribute(AttributeList::FunctionIndex, DeoptLowering))
1401  return CSAS.getAttribute(AttributeList::FunctionIndex, DeoptLowering)
1402  .getValueAsString();
1403  Function *F = CS.getCalledFunction();
1404  assert(F && F->hasFnAttribute(DeoptLowering));
1405  return F->getFnAttribute(DeoptLowering).getValueAsString();
1406  }
1407  return "live-through";
1408 }
1409 
1410 static void
1411 makeStatepointExplicitImpl(const CallSite CS, /* to replace */
1412  const SmallVectorImpl<Value *> &BasePtrs,
1414  PartiallyConstructedSafepointRecord &Result,
1415  std::vector<DeferredReplacement> &Replacements) {
1416  assert(BasePtrs.size() == LiveVariables.size());
1417 
1418  // Then go ahead and use the builder do actually do the inserts. We insert
1419  // immediately before the previous instruction under the assumption that all
1420  // arguments will be available here. We can't insert afterwards since we may
1421  // be replacing a terminator.
1422  Instruction *InsertBefore = CS.getInstruction();
1423  IRBuilder<> Builder(InsertBefore);
1424 
1425  ArrayRef<Value *> GCArgs(LiveVariables);
1426  uint64_t StatepointID = StatepointDirectives::DefaultStatepointID;
1427  uint32_t NumPatchBytes = 0;
1429 
1430  ArrayRef<Use> CallArgs(CS.arg_begin(), CS.arg_end());
1431  ArrayRef<Use> DeoptArgs = GetDeoptBundleOperands(CS);
1432  ArrayRef<Use> TransitionArgs;
1433  if (auto TransitionBundle =
1436  TransitionArgs = TransitionBundle->Inputs;
1437  }
1438 
1439  // Instead of lowering calls to @llvm.experimental.deoptimize as normal calls
1440  // with a return value, we lower then as never returning calls to
1441  // __llvm_deoptimize that are followed by unreachable to get better codegen.
1442  bool IsDeoptimize = false;
1443 
1446  if (SD.NumPatchBytes)
1447  NumPatchBytes = *SD.NumPatchBytes;
1448  if (SD.StatepointID)
1449  StatepointID = *SD.StatepointID;
1450 
1451  // Pass through the requested lowering if any. The default is live-through.
1452  StringRef DeoptLowering = getDeoptLowering(CS);
1453  if (DeoptLowering.equals("live-in"))
1455  else {
1456  assert(DeoptLowering.equals("live-through") && "Unsupported value!");
1457  }
1458 
1459  Value *CallTarget = CS.getCalledValue();
1460  if (Function *F = dyn_cast<Function>(CallTarget)) {
1461  if (F->getIntrinsicID() == Intrinsic::experimental_deoptimize) {
1462  // Calls to llvm.experimental.deoptimize are lowered to calls to the
1463  // __llvm_deoptimize symbol. We want to resolve this now, since the
1464  // verifier does not allow taking the address of an intrinsic function.
1465 
1466  SmallVector<Type *, 8> DomainTy;
1467  for (Value *Arg : CallArgs)
1468  DomainTy.push_back(Arg->getType());
1469  auto *FTy = FunctionType::get(Type::getVoidTy(F->getContext()), DomainTy,
1470  /* isVarArg = */ false);
1471 
1472  // Note: CallTarget can be a bitcast instruction of a symbol if there are
1473  // calls to @llvm.experimental.deoptimize with different argument types in
1474  // the same module. This is fine -- we assume the frontend knew what it
1475  // was doing when generating this kind of IR.
1476  CallTarget =
1477  F->getParent()->getOrInsertFunction("__llvm_deoptimize", FTy);
1478 
1479  IsDeoptimize = true;
1480  }
1481  }
1482 
1483  // Create the statepoint given all the arguments
1484  Instruction *Token = nullptr;
1485  if (CS.isCall()) {
1486  CallInst *ToReplace = cast<CallInst>(CS.getInstruction());
1487  CallInst *Call = Builder.CreateGCStatepointCall(
1488  StatepointID, NumPatchBytes, CallTarget, Flags, CallArgs,
1489  TransitionArgs, DeoptArgs, GCArgs, "safepoint_token");
1490 
1491  Call->setTailCallKind(ToReplace->getTailCallKind());
1492  Call->setCallingConv(ToReplace->getCallingConv());
1493 
1494  // Currently we will fail on parameter attributes and on certain
1495  // function attributes. In case if we can handle this set of attributes -
1496  // set up function attrs directly on statepoint and return attrs later for
1497  // gc_result intrinsic.
1498  Call->setAttributes(legalizeCallAttributes(ToReplace->getAttributes()));
1499 
1500  Token = Call;
1501 
1502  // Put the following gc_result and gc_relocate calls immediately after the
1503  // the old call (which we're about to delete)
1504  assert(ToReplace->getNextNode() && "Not a terminator, must have next!");
1505  Builder.SetInsertPoint(ToReplace->getNextNode());
1506  Builder.SetCurrentDebugLocation(ToReplace->getNextNode()->getDebugLoc());
1507  } else {
1508  InvokeInst *ToReplace = cast<InvokeInst>(CS.getInstruction());
1509 
1510  // Insert the new invoke into the old block. We'll remove the old one in a
1511  // moment at which point this will become the new terminator for the
1512  // original block.
1513  InvokeInst *Invoke = Builder.CreateGCStatepointInvoke(
1514  StatepointID, NumPatchBytes, CallTarget, ToReplace->getNormalDest(),
1515  ToReplace->getUnwindDest(), Flags, CallArgs, TransitionArgs, DeoptArgs,
1516  GCArgs, "statepoint_token");
1517 
1518  Invoke->setCallingConv(ToReplace->getCallingConv());
1519 
1520  // Currently we will fail on parameter attributes and on certain
1521  // function attributes. In case if we can handle this set of attributes -
1522  // set up function attrs directly on statepoint and return attrs later for
1523  // gc_result intrinsic.
1524  Invoke->setAttributes(legalizeCallAttributes(ToReplace->getAttributes()));
1525 
1526  Token = Invoke;
1527 
1528  // Generate gc relocates in exceptional path
1529  BasicBlock *UnwindBlock = ToReplace->getUnwindDest();
1530  assert(!isa<PHINode>(UnwindBlock->begin()) &&
1531  UnwindBlock->getUniquePredecessor() &&
1532  "can't safely insert in this block!");
1533 
1534  Builder.SetInsertPoint(&*UnwindBlock->getFirstInsertionPt());
1535  Builder.SetCurrentDebugLocation(ToReplace->getDebugLoc());
1536 
1537  // Attach exceptional gc relocates to the landingpad.
1538  Instruction *ExceptionalToken = UnwindBlock->getLandingPadInst();
1539  Result.UnwindToken = ExceptionalToken;
1540 
1541  const unsigned LiveStartIdx = Statepoint(Token).gcArgsStartIdx();
1542  CreateGCRelocates(LiveVariables, LiveStartIdx, BasePtrs, ExceptionalToken,
1543  Builder);
1544 
1545  // Generate gc relocates and returns for normal block
1546  BasicBlock *NormalDest = ToReplace->getNormalDest();
1547  assert(!isa<PHINode>(NormalDest->begin()) &&
1548  NormalDest->getUniquePredecessor() &&
1549  "can't safely insert in this block!");
1550 
1551  Builder.SetInsertPoint(&*NormalDest->getFirstInsertionPt());
1552 
1553  // gc relocates will be generated later as if it were regular call
1554  // statepoint
1555  }
1556  assert(Token && "Should be set in one of the above branches!");
1557 
1558  if (IsDeoptimize) {
1559  // If we're wrapping an @llvm.experimental.deoptimize in a statepoint, we
1560  // transform the tail-call like structure to a call to a void function
1561  // followed by unreachable to get better codegen.
1562  Replacements.push_back(
1563  DeferredReplacement::createDeoptimizeReplacement(CS.getInstruction()));
1564  } else {
1565  Token->setName("statepoint_token");
1566  if (!CS.getType()->isVoidTy() && !CS.getInstruction()->use_empty()) {
1567  StringRef Name =
1568  CS.getInstruction()->hasName() ? CS.getInstruction()->getName() : "";
1569  CallInst *GCResult = Builder.CreateGCResult(Token, CS.getType(), Name);
1570  GCResult->setAttributes(
1573 
1574  // We cannot RAUW or delete CS.getInstruction() because it could be in the
1575  // live set of some other safepoint, in which case that safepoint's
1576  // PartiallyConstructedSafepointRecord will hold a raw pointer to this
1577  // llvm::Instruction. Instead, we defer the replacement and deletion to
1578  // after the live sets have been made explicit in the IR, and we no longer
1579  // have raw pointers to worry about.
1580  Replacements.emplace_back(
1581  DeferredReplacement::createRAUW(CS.getInstruction(), GCResult));
1582  } else {
1583  Replacements.emplace_back(
1584  DeferredReplacement::createDelete(CS.getInstruction()));
1585  }
1586  }
1587 
1588  Result.StatepointToken = Token;
1589 
1590  // Second, create a gc.relocate for every live variable
1591  const unsigned LiveStartIdx = Statepoint(Token).gcArgsStartIdx();
1592  CreateGCRelocates(LiveVariables, LiveStartIdx, BasePtrs, Token, Builder);
1593 }
1594 
1595 // Replace an existing gc.statepoint with a new one and a set of gc.relocates
1596 // which make the relocations happening at this safepoint explicit.
1597 //
1598 // WARNING: Does not do any fixup to adjust users of the original live
1599 // values. That's the callers responsibility.
1600 static void
1602  PartiallyConstructedSafepointRecord &Result,
1603  std::vector<DeferredReplacement> &Replacements) {
1604  const auto &LiveSet = Result.LiveSet;
1605  const auto &PointerToBase = Result.PointerToBase;
1606 
1607  // Convert to vector for efficient cross referencing.
1608  SmallVector<Value *, 64> BaseVec, LiveVec;
1609  LiveVec.reserve(LiveSet.size());
1610  BaseVec.reserve(LiveSet.size());
1611  for (Value *L : LiveSet) {
1612  LiveVec.push_back(L);
1613  assert(PointerToBase.count(L));
1614  Value *Base = PointerToBase.find(L)->second;
1615  BaseVec.push_back(Base);
1616  }
1617  assert(LiveVec.size() == BaseVec.size());
1618 
1619  // Do the actual rewriting and delete the old statepoint
1620  makeStatepointExplicitImpl(CS, BaseVec, LiveVec, Result, Replacements);
1621 }
1622 
1623 // Helper function for the relocationViaAlloca.
1624 //
1625 // It receives iterator to the statepoint gc relocates and emits a store to the
1626 // assigned location (via allocaMap) for the each one of them. It adds the
1627 // visited values into the visitedLiveValues set, which we will later use them
1628 // for sanity checking.
1629 static void
1631  DenseMap<Value *, Value *> &AllocaMap,
1632  DenseSet<Value *> &VisitedLiveValues) {
1633  for (User *U : GCRelocs) {
1634  GCRelocateInst *Relocate = dyn_cast<GCRelocateInst>(U);
1635  if (!Relocate)
1636  continue;
1637 
1638  Value *OriginalValue = Relocate->getDerivedPtr();
1639  assert(AllocaMap.count(OriginalValue));
1640  Value *Alloca = AllocaMap[OriginalValue];
1641 
1642  // Emit store into the related alloca
1643  // All gc_relocates are i8 addrspace(1)* typed, and it must be bitcasted to
1644  // the correct type according to alloca.
1645  assert(Relocate->getNextNode() &&
1646  "Should always have one since it's not a terminator");
1647  IRBuilder<> Builder(Relocate->getNextNode());
1648  Value *CastedRelocatedValue =
1649  Builder.CreateBitCast(Relocate,
1650  cast<AllocaInst>(Alloca)->getAllocatedType(),
1651  suffixed_name_or(Relocate, ".casted", ""));
1652 
1653  StoreInst *Store = new StoreInst(CastedRelocatedValue, Alloca);
1654  Store->insertAfter(cast<Instruction>(CastedRelocatedValue));
1655 
1656 #ifndef NDEBUG
1657  VisitedLiveValues.insert(OriginalValue);
1658 #endif
1659  }
1660 }
1661 
1662 // Helper function for the "relocationViaAlloca". Similar to the
1663 // "insertRelocationStores" but works for rematerialized values.
1665  const RematerializedValueMapTy &RematerializedValues,
1666  DenseMap<Value *, Value *> &AllocaMap,
1667  DenseSet<Value *> &VisitedLiveValues) {
1668  for (auto RematerializedValuePair: RematerializedValues) {
1669  Instruction *RematerializedValue = RematerializedValuePair.first;
1670  Value *OriginalValue = RematerializedValuePair.second;
1671 
1672  assert(AllocaMap.count(OriginalValue) &&
1673  "Can not find alloca for rematerialized value");
1674  Value *Alloca = AllocaMap[OriginalValue];
1675 
1676  StoreInst *Store = new StoreInst(RematerializedValue, Alloca);
1677  Store->insertAfter(RematerializedValue);
1678 
1679 #ifndef NDEBUG
1680  VisitedLiveValues.insert(OriginalValue);
1681 #endif
1682  }
1683 }
1684 
1685 /// Do all the relocation update via allocas and mem2reg
1689 #ifndef NDEBUG
1690  // record initial number of (static) allocas; we'll check we have the same
1691  // number when we get done.
1692  int InitialAllocaNum = 0;
1693  for (Instruction &I : F.getEntryBlock())
1694  if (isa<AllocaInst>(I))
1695  InitialAllocaNum++;
1696 #endif
1697 
1698  // TODO-PERF: change data structures, reserve
1699  DenseMap<Value *, Value *> AllocaMap;
1700  SmallVector<AllocaInst *, 200> PromotableAllocas;
1701  // Used later to chack that we have enough allocas to store all values
1702  std::size_t NumRematerializedValues = 0;
1703  PromotableAllocas.reserve(Live.size());
1704 
1705  // Emit alloca for "LiveValue" and record it in "allocaMap" and
1706  // "PromotableAllocas"
1707  const DataLayout &DL = F.getParent()->getDataLayout();
1708  auto emitAllocaFor = [&](Value *LiveValue) {
1709  AllocaInst *Alloca = new AllocaInst(LiveValue->getType(),
1710  DL.getAllocaAddrSpace(), "",
1712  AllocaMap[LiveValue] = Alloca;
1713  PromotableAllocas.push_back(Alloca);
1714  };
1715 
1716  // Emit alloca for each live gc pointer
1717  for (Value *V : Live)
1718  emitAllocaFor(V);
1719 
1720  // Emit allocas for rematerialized values
1721  for (const auto &Info : Records)
1722  for (auto RematerializedValuePair : Info.RematerializedValues) {
1723  Value *OriginalValue = RematerializedValuePair.second;
1724  if (AllocaMap.count(OriginalValue) != 0)
1725  continue;
1726 
1727  emitAllocaFor(OriginalValue);
1728  ++NumRematerializedValues;
1729  }
1730 
1731  // The next two loops are part of the same conceptual operation. We need to
1732  // insert a store to the alloca after the original def and at each
1733  // redefinition. We need to insert a load before each use. These are split
1734  // into distinct loops for performance reasons.
1735 
1736  // Update gc pointer after each statepoint: either store a relocated value or
1737  // null (if no relocated value was found for this gc pointer and it is not a
1738  // gc_result). This must happen before we update the statepoint with load of
1739  // alloca otherwise we lose the link between statepoint and old def.
1740  for (const auto &Info : Records) {
1741  Value *Statepoint = Info.StatepointToken;
1742 
1743  // This will be used for consistency check
1744  DenseSet<Value *> VisitedLiveValues;
1745 
1746  // Insert stores for normal statepoint gc relocates
1747  insertRelocationStores(Statepoint->users(), AllocaMap, VisitedLiveValues);
1748 
1749  // In case if it was invoke statepoint
1750  // we will insert stores for exceptional path gc relocates.
1751  if (isa<InvokeInst>(Statepoint)) {
1752  insertRelocationStores(Info.UnwindToken->users(), AllocaMap,
1753  VisitedLiveValues);
1754  }
1755 
1756  // Do similar thing with rematerialized values
1757  insertRematerializationStores(Info.RematerializedValues, AllocaMap,
1758  VisitedLiveValues);
1759 
1760  if (ClobberNonLive) {
1761  // As a debugging aid, pretend that an unrelocated pointer becomes null at
1762  // the gc.statepoint. This will turn some subtle GC problems into
1763  // slightly easier to debug SEGVs. Note that on large IR files with
1764  // lots of gc.statepoints this is extremely costly both memory and time
1765  // wise.
1767  for (auto Pair : AllocaMap) {
1768  Value *Def = Pair.first;
1769  AllocaInst *Alloca = cast<AllocaInst>(Pair.second);
1770 
1771  // This value was relocated
1772  if (VisitedLiveValues.count(Def)) {
1773  continue;
1774  }
1775  ToClobber.push_back(Alloca);
1776  }
1777 
1778  auto InsertClobbersAt = [&](Instruction *IP) {
1779  for (auto *AI : ToClobber) {
1780  auto PT = cast<PointerType>(AI->getAllocatedType());
1782  StoreInst *Store = new StoreInst(CPN, AI);
1783  Store->insertBefore(IP);
1784  }
1785  };
1786 
1787  // Insert the clobbering stores. These may get intermixed with the
1788  // gc.results and gc.relocates, but that's fine.
1789  if (auto II = dyn_cast<InvokeInst>(Statepoint)) {
1790  InsertClobbersAt(&*II->getNormalDest()->getFirstInsertionPt());
1791  InsertClobbersAt(&*II->getUnwindDest()->getFirstInsertionPt());
1792  } else {
1793  InsertClobbersAt(cast<Instruction>(Statepoint)->getNextNode());
1794  }
1795  }
1796  }
1797 
1798  // Update use with load allocas and add store for gc_relocated.
1799  for (auto Pair : AllocaMap) {
1800  Value *Def = Pair.first;
1801  Value *Alloca = Pair.second;
1802 
1803  // We pre-record the uses of allocas so that we dont have to worry about
1804  // later update that changes the user information..
1805 
1807  // PERF: trade a linear scan for repeated reallocation
1808  Uses.reserve(std::distance(Def->user_begin(), Def->user_end()));
1809  for (User *U : Def->users()) {
1810  if (!isa<ConstantExpr>(U)) {
1811  // If the def has a ConstantExpr use, then the def is either a
1812  // ConstantExpr use itself or null. In either case
1813  // (recursively in the first, directly in the second), the oop
1814  // it is ultimately dependent on is null and this particular
1815  // use does not need to be fixed up.
1816  Uses.push_back(cast<Instruction>(U));
1817  }
1818  }
1819 
1820  std::sort(Uses.begin(), Uses.end());
1821  auto Last = std::unique(Uses.begin(), Uses.end());
1822  Uses.erase(Last, Uses.end());
1823 
1824  for (Instruction *Use : Uses) {
1825  if (isa<PHINode>(Use)) {
1826  PHINode *Phi = cast<PHINode>(Use);
1827  for (unsigned i = 0; i < Phi->getNumIncomingValues(); i++) {
1828  if (Def == Phi->getIncomingValue(i)) {
1829  LoadInst *Load = new LoadInst(
1830  Alloca, "", Phi->getIncomingBlock(i)->getTerminator());
1831  Phi->setIncomingValue(i, Load);
1832  }
1833  }
1834  } else {
1835  LoadInst *Load = new LoadInst(Alloca, "", Use);
1836  Use->replaceUsesOfWith(Def, Load);
1837  }
1838  }
1839 
1840  // Emit store for the initial gc value. Store must be inserted after load,
1841  // otherwise store will be in alloca's use list and an extra load will be
1842  // inserted before it.
1843  StoreInst *Store = new StoreInst(Def, Alloca);
1844  if (Instruction *Inst = dyn_cast<Instruction>(Def)) {
1845  if (InvokeInst *Invoke = dyn_cast<InvokeInst>(Inst)) {
1846  // InvokeInst is a TerminatorInst so the store need to be inserted
1847  // into its normal destination block.
1848  BasicBlock *NormalDest = Invoke->getNormalDest();
1849  Store->insertBefore(NormalDest->getFirstNonPHI());
1850  } else {
1851  assert(!Inst->isTerminator() &&
1852  "The only TerminatorInst that can produce a value is "
1853  "InvokeInst which is handled above.");
1854  Store->insertAfter(Inst);
1855  }
1856  } else {
1857  assert(isa<Argument>(Def));
1858  Store->insertAfter(cast<Instruction>(Alloca));
1859  }
1860  }
1861 
1862  assert(PromotableAllocas.size() == Live.size() + NumRematerializedValues &&
1863  "we must have the same allocas with lives");
1864  if (!PromotableAllocas.empty()) {
1865  // Apply mem2reg to promote alloca to SSA
1866  PromoteMemToReg(PromotableAllocas, DT);
1867  }
1868 
1869 #ifndef NDEBUG
1870  for (auto &I : F.getEntryBlock())
1871  if (isa<AllocaInst>(I))
1872  InitialAllocaNum--;
1873  assert(InitialAllocaNum == 0 && "We must not introduce any extra allocas");
1874 #endif
1875 }
1876 
1877 /// Implement a unique function which doesn't require we sort the input
1878 /// vector. Doing so has the effect of changing the output of a couple of
1879 /// tests in ways which make them less useful in testing fused safepoints.
1880 template <typename T> static void unique_unsorted(SmallVectorImpl<T> &Vec) {
1881  SmallSet<T, 8> Seen;
1882  Vec.erase(remove_if(Vec, [&](const T &V) { return !Seen.insert(V).second; }),
1883  Vec.end());
1884 }
1885 
1886 /// Insert holders so that each Value is obviously live through the entire
1887 /// lifetime of the call.
1888 static void insertUseHolderAfter(CallSite &CS, const ArrayRef<Value *> Values,
1889  SmallVectorImpl<CallInst *> &Holders) {
1890  if (Values.empty())
1891  // No values to hold live, might as well not insert the empty holder
1892  return;
1893 
1894  Module *M = CS.getInstruction()->getModule();
1895  // Use a dummy vararg function to actually hold the values live
1896  Function *Func = cast<Function>(M->getOrInsertFunction(
1897  "__tmp_use", FunctionType::get(Type::getVoidTy(M->getContext()), true)));
1898  if (CS.isCall()) {
1899  // For call safepoints insert dummy calls right after safepoint
1900  Holders.push_back(CallInst::Create(Func, Values, "",
1901  &*++CS.getInstruction()->getIterator()));
1902  return;
1903  }
1904  // For invoke safepooints insert dummy calls both in normal and
1905  // exceptional destination blocks
1906  auto *II = cast<InvokeInst>(CS.getInstruction());
1907  Holders.push_back(CallInst::Create(
1908  Func, Values, "", &*II->getNormalDest()->getFirstInsertionPt()));
1909  Holders.push_back(CallInst::Create(
1910  Func, Values, "", &*II->getUnwindDest()->getFirstInsertionPt()));
1911 }
1912 
1914  Function &F, DominatorTree &DT, ArrayRef<CallSite> toUpdate,
1916  GCPtrLivenessData OriginalLivenessData;
1917  computeLiveInValues(DT, F, OriginalLivenessData);
1918  for (size_t i = 0; i < records.size(); i++) {
1919  struct PartiallyConstructedSafepointRecord &info = records[i];
1920  analyzeParsePointLiveness(DT, OriginalLivenessData, toUpdate[i], info);
1921  }
1922 }
1923 
1924 // Helper function for the "rematerializeLiveValues". It walks use chain
1925 // starting from the "CurrentValue" until it reaches the root of the chain, i.e.
1926 // the base or a value it cannot process. Only "simple" values are processed
1927 // (currently it is GEP's and casts). The returned root is examined by the
1928 // callers of findRematerializableChainToBasePointer. Fills "ChainToBase" array
1929 // with all visited values.
1931  SmallVectorImpl<Instruction*> &ChainToBase,
1932  Value *CurrentValue) {
1933  if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(CurrentValue)) {
1934  ChainToBase.push_back(GEP);
1935  return findRematerializableChainToBasePointer(ChainToBase,
1936  GEP->getPointerOperand());
1937  }
1938 
1939  if (CastInst *CI = dyn_cast<CastInst>(CurrentValue)) {
1940  if (!CI->isNoopCast(CI->getModule()->getDataLayout()))
1941  return CI;
1942 
1943  ChainToBase.push_back(CI);
1944  return findRematerializableChainToBasePointer(ChainToBase,
1945  CI->getOperand(0));
1946  }
1947 
1948  // We have reached the root of the chain, which is either equal to the base or
1949  // is the first unsupported value along the use chain.
1950  return CurrentValue;
1951 }
1952 
1953 // Helper function for the "rematerializeLiveValues". Compute cost of the use
1954 // chain we are going to rematerialize.
1955 static unsigned
1957  TargetTransformInfo &TTI) {
1958  unsigned Cost = 0;
1959 
1960  for (Instruction *Instr : Chain) {
1961  if (CastInst *CI = dyn_cast<CastInst>(Instr)) {
1962  assert(CI->isNoopCast(CI->getModule()->getDataLayout()) &&
1963  "non noop cast is found during rematerialization");
1964 
1965  Type *SrcTy = CI->getOperand(0)->getType();
1966  Cost += TTI.getCastInstrCost(CI->getOpcode(), CI->getType(), SrcTy, CI);
1967 
1968  } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Instr)) {
1969  // Cost of the address calculation
1970  Type *ValTy = GEP->getSourceElementType();
1971  Cost += TTI.getAddressComputationCost(ValTy);
1972 
1973  // And cost of the GEP itself
1974  // TODO: Use TTI->getGEPCost here (it exists, but appears to be not
1975  // allowed for the external usage)
1976  if (!GEP->hasAllConstantIndices())
1977  Cost += 2;
1978 
1979  } else {
1980  llvm_unreachable("unsupported instruciton type during rematerialization");
1981  }
1982  }
1983 
1984  return Cost;
1985 }
1986 
1987 static bool AreEquivalentPhiNodes(PHINode &OrigRootPhi, PHINode &AlternateRootPhi) {
1988  unsigned PhiNum = OrigRootPhi.getNumIncomingValues();
1989  if (PhiNum != AlternateRootPhi.getNumIncomingValues() ||
1990  OrigRootPhi.getParent() != AlternateRootPhi.getParent())
1991  return false;
1992  // Map of incoming values and their corresponding basic blocks of
1993  // OrigRootPhi.
1994  SmallDenseMap<Value *, BasicBlock *, 8> CurrentIncomingValues;
1995  for (unsigned i = 0; i < PhiNum; i++)
1996  CurrentIncomingValues[OrigRootPhi.getIncomingValue(i)] =
1997  OrigRootPhi.getIncomingBlock(i);
1998 
1999  // Both current and base PHIs should have same incoming values and
2000  // the same basic blocks corresponding to the incoming values.
2001  for (unsigned i = 0; i < PhiNum; i++) {
2002  auto CIVI =
2003  CurrentIncomingValues.find(AlternateRootPhi.getIncomingValue(i));
2004  if (CIVI == CurrentIncomingValues.end())
2005  return false;
2006  BasicBlock *CurrentIncomingBB = CIVI->second;
2007  if (CurrentIncomingBB != AlternateRootPhi.getIncomingBlock(i))
2008  return false;
2009  }
2010  return true;
2011 }
2012 
2013 // From the statepoint live set pick values that are cheaper to recompute then
2014 // to relocate. Remove this values from the live set, rematerialize them after
2015 // statepoint and record them in "Info" structure. Note that similar to
2016 // relocated values we don't do any user adjustments here.
2018  PartiallyConstructedSafepointRecord &Info,
2019  TargetTransformInfo &TTI) {
2020  const unsigned int ChainLengthThreshold = 10;
2021 
2022  // Record values we are going to delete from this statepoint live set.
2023  // We can not di this in following loop due to iterator invalidation.
2024  SmallVector<Value *, 32> LiveValuesToBeDeleted;
2025 
2026  for (Value *LiveValue: Info.LiveSet) {
2027  // For each live pointer find it's defining chain
2028  SmallVector<Instruction *, 3> ChainToBase;
2029  assert(Info.PointerToBase.count(LiveValue));
2030  Value *RootOfChain =
2032  LiveValue);
2033 
2034  // Nothing to do, or chain is too long
2035  if ( ChainToBase.size() == 0 ||
2036  ChainToBase.size() > ChainLengthThreshold)
2037  continue;
2038 
2039  // Handle the scenario where the RootOfChain is not equal to the
2040  // Base Value, but they are essentially the same phi values.
2041  if (RootOfChain != Info.PointerToBase[LiveValue]) {
2042  PHINode *OrigRootPhi = dyn_cast<PHINode>(RootOfChain);
2043  PHINode *AlternateRootPhi = dyn_cast<PHINode>(Info.PointerToBase[LiveValue]);
2044  if (!OrigRootPhi || !AlternateRootPhi)
2045  continue;
2046  // PHI nodes that have the same incoming values, and belonging to the same
2047  // basic blocks are essentially the same SSA value. When the original phi
2048  // has incoming values with different base pointers, the original phi is
2049  // marked as conflict, and an additional `AlternateRootPhi` with the same
2050  // incoming values get generated by the findBasePointer function. We need
2051  // to identify the newly generated AlternateRootPhi (.base version of phi)
2052  // and RootOfChain (the original phi node itself) are the same, so that we
2053  // can rematerialize the gep and casts. This is a workaround for the
2054  // deficiency in the findBasePointer algorithm.
2055  if (!AreEquivalentPhiNodes(*OrigRootPhi, *AlternateRootPhi))
2056  continue;
2057  // Now that the phi nodes are proved to be the same, assert that
2058  // findBasePointer's newly generated AlternateRootPhi is present in the
2059  // liveset of the call.
2060  assert(Info.LiveSet.count(AlternateRootPhi));
2061  }
2062  // Compute cost of this chain
2063  unsigned Cost = chainToBasePointerCost(ChainToBase, TTI);
2064  // TODO: We can also account for cases when we will be able to remove some
2065  // of the rematerialized values by later optimization passes. I.e if
2066  // we rematerialized several intersecting chains. Or if original values
2067  // don't have any uses besides this statepoint.
2068 
2069  // For invokes we need to rematerialize each chain twice - for normal and
2070  // for unwind basic blocks. Model this by multiplying cost by two.
2071  if (CS.isInvoke()) {
2072  Cost *= 2;
2073  }
2074  // If it's too expensive - skip it
2075  if (Cost >= RematerializationThreshold)
2076  continue;
2077 
2078  // Remove value from the live set
2079  LiveValuesToBeDeleted.push_back(LiveValue);
2080 
2081  // Clone instructions and record them inside "Info" structure
2082 
2083  // Walk backwards to visit top-most instructions first
2084  std::reverse(ChainToBase.begin(), ChainToBase.end());
2085 
2086  // Utility function which clones all instructions from "ChainToBase"
2087  // and inserts them before "InsertBefore". Returns rematerialized value
2088  // which should be used after statepoint.
2089  auto rematerializeChain = [&ChainToBase](
2090  Instruction *InsertBefore, Value *RootOfChain, Value *AlternateLiveBase) {
2091  Instruction *LastClonedValue = nullptr;
2092  Instruction *LastValue = nullptr;
2093  for (Instruction *Instr: ChainToBase) {
2094  // Only GEP's and casts are supported as we need to be careful to not
2095  // introduce any new uses of pointers not in the liveset.
2096  // Note that it's fine to introduce new uses of pointers which were
2097  // otherwise not used after this statepoint.
2098  assert(isa<GetElementPtrInst>(Instr) || isa<CastInst>(Instr));
2099 
2100  Instruction *ClonedValue = Instr->clone();
2101  ClonedValue->insertBefore(InsertBefore);
2102  ClonedValue->setName(Instr->getName() + ".remat");
2103 
2104  // If it is not first instruction in the chain then it uses previously
2105  // cloned value. We should update it to use cloned value.
2106  if (LastClonedValue) {
2107  assert(LastValue);
2108  ClonedValue->replaceUsesOfWith(LastValue, LastClonedValue);
2109 #ifndef NDEBUG
2110  for (auto OpValue : ClonedValue->operand_values()) {
2111  // Assert that cloned instruction does not use any instructions from
2112  // this chain other than LastClonedValue
2113  assert(!is_contained(ChainToBase, OpValue) &&
2114  "incorrect use in rematerialization chain");
2115  // Assert that the cloned instruction does not use the RootOfChain
2116  // or the AlternateLiveBase.
2117  assert(OpValue != RootOfChain && OpValue != AlternateLiveBase);
2118  }
2119 #endif
2120  } else {
2121  // For the first instruction, replace the use of unrelocated base i.e.
2122  // RootOfChain/OrigRootPhi, with the corresponding PHI present in the
2123  // live set. They have been proved to be the same PHI nodes. Note
2124  // that the *only* use of the RootOfChain in the ChainToBase list is
2125  // the first Value in the list.
2126  if (RootOfChain != AlternateLiveBase)
2127  ClonedValue->replaceUsesOfWith(RootOfChain, AlternateLiveBase);
2128  }
2129 
2130  LastClonedValue = ClonedValue;
2131  LastValue = Instr;
2132  }
2133  assert(LastClonedValue);
2134  return LastClonedValue;
2135  };
2136 
2137  // Different cases for calls and invokes. For invokes we need to clone
2138  // instructions both on normal and unwind path.
2139  if (CS.isCall()) {
2140  Instruction *InsertBefore = CS.getInstruction()->getNextNode();
2141  assert(InsertBefore);
2142  Instruction *RematerializedValue = rematerializeChain(
2143  InsertBefore, RootOfChain, Info.PointerToBase[LiveValue]);
2144  Info.RematerializedValues[RematerializedValue] = LiveValue;
2145  } else {
2146  InvokeInst *Invoke = cast<InvokeInst>(CS.getInstruction());
2147 
2148  Instruction *NormalInsertBefore =
2149  &*Invoke->getNormalDest()->getFirstInsertionPt();
2150  Instruction *UnwindInsertBefore =
2151  &*Invoke->getUnwindDest()->getFirstInsertionPt();
2152 
2153  Instruction *NormalRematerializedValue = rematerializeChain(
2154  NormalInsertBefore, RootOfChain, Info.PointerToBase[LiveValue]);
2155  Instruction *UnwindRematerializedValue = rematerializeChain(
2156  UnwindInsertBefore, RootOfChain, Info.PointerToBase[LiveValue]);
2157 
2158  Info.RematerializedValues[NormalRematerializedValue] = LiveValue;
2159  Info.RematerializedValues[UnwindRematerializedValue] = LiveValue;
2160  }
2161  }
2162 
2163  // Remove rematerializaed values from the live set
2164  for (auto LiveValue: LiveValuesToBeDeleted) {
2165  Info.LiveSet.remove(LiveValue);
2166  }
2167 }
2168 
2170  TargetTransformInfo &TTI,
2171  SmallVectorImpl<CallSite> &ToUpdate) {
2172 #ifndef NDEBUG
2173  // sanity check the input
2174  std::set<CallSite> Uniqued;
2175  Uniqued.insert(ToUpdate.begin(), ToUpdate.end());
2176  assert(Uniqued.size() == ToUpdate.size() && "no duplicates please!");
2177 
2178  for (CallSite CS : ToUpdate)
2179  assert(CS.getInstruction()->getFunction() == &F);
2180 #endif
2181 
2182  // When inserting gc.relocates for invokes, we need to be able to insert at
2183  // the top of the successor blocks. See the comment on
2184  // normalForInvokeSafepoint on exactly what is needed. Note that this step
2185  // may restructure the CFG.
2186  for (CallSite CS : ToUpdate) {
2187  if (!CS.isInvoke())
2188  continue;
2189  auto *II = cast<InvokeInst>(CS.getInstruction());
2190  normalizeForInvokeSafepoint(II->getNormalDest(), II->getParent(), DT);
2191  normalizeForInvokeSafepoint(II->getUnwindDest(), II->getParent(), DT);
2192  }
2193 
2194  // A list of dummy calls added to the IR to keep various values obviously
2195  // live in the IR. We'll remove all of these when done.
2197 
2198  // Insert a dummy call with all of the deopt operands we'll need for the
2199  // actual safepoint insertion as arguments. This ensures reference operands
2200  // in the deopt argument list are considered live through the safepoint (and
2201  // thus makes sure they get relocated.)
2202  for (CallSite CS : ToUpdate) {
2203  SmallVector<Value *, 64> DeoptValues;
2204 
2205  for (Value *Arg : GetDeoptBundleOperands(CS)) {
2207  "support for FCA unimplemented");
2209  DeoptValues.push_back(Arg);
2210  }
2211 
2212  insertUseHolderAfter(CS, DeoptValues, Holders);
2213  }
2214 
2216 
2217  // A) Identify all gc pointers which are statically live at the given call
2218  // site.
2219  findLiveReferences(F, DT, ToUpdate, Records);
2220 
2221  // B) Find the base pointers for each live pointer
2222  /* scope for caching */ {
2223  // Cache the 'defining value' relation used in the computation and
2224  // insertion of base phis and selects. This ensures that we don't insert
2225  // large numbers of duplicate base_phis.
2226  DefiningValueMapTy DVCache;
2227 
2228  for (size_t i = 0; i < Records.size(); i++) {
2229  PartiallyConstructedSafepointRecord &info = Records[i];
2230  findBasePointers(DT, DVCache, ToUpdate[i], info);
2231  }
2232  } // end of cache scope
2233 
2234  // The base phi insertion logic (for any safepoint) may have inserted new
2235  // instructions which are now live at some safepoint. The simplest such
2236  // example is:
2237  // loop:
2238  // phi a <-- will be a new base_phi here
2239  // safepoint 1 <-- that needs to be live here
2240  // gep a + 1
2241  // safepoint 2
2242  // br loop
2243  // We insert some dummy calls after each safepoint to definitely hold live
2244  // the base pointers which were identified for that safepoint. We'll then
2245  // ask liveness for _every_ base inserted to see what is now live. Then we
2246  // remove the dummy calls.
2247  Holders.reserve(Holders.size() + Records.size());
2248  for (size_t i = 0; i < Records.size(); i++) {
2249  PartiallyConstructedSafepointRecord &Info = Records[i];
2250 
2252  for (auto Pair : Info.PointerToBase)
2253  Bases.push_back(Pair.second);
2254 
2255  insertUseHolderAfter(ToUpdate[i], Bases, Holders);
2256  }
2257 
2258  // By selecting base pointers, we've effectively inserted new uses. Thus, we
2259  // need to rerun liveness. We may *also* have inserted new defs, but that's
2260  // not the key issue.
2261  recomputeLiveInValues(F, DT, ToUpdate, Records);
2262 
2263  if (PrintBasePointers) {
2264  for (auto &Info : Records) {
2265  errs() << "Base Pairs: (w/Relocation)\n";
2266  for (auto Pair : Info.PointerToBase) {
2267  errs() << " derived ";
2268  Pair.first->printAsOperand(errs(), false);
2269  errs() << " base ";
2270  Pair.second->printAsOperand(errs(), false);
2271  errs() << "\n";
2272  }
2273  }
2274  }
2275 
2276  // It is possible that non-constant live variables have a constant base. For
2277  // example, a GEP with a variable offset from a global. In this case we can
2278  // remove it from the liveset. We already don't add constants to the liveset
2279  // because we assume they won't move at runtime and the GC doesn't need to be
2280  // informed about them. The same reasoning applies if the base is constant.
2281  // Note that the relocation placement code relies on this filtering for
2282  // correctness as it expects the base to be in the liveset, which isn't true
2283  // if the base is constant.
2284  for (auto &Info : Records)
2285  for (auto &BasePair : Info.PointerToBase)
2286  if (isa<Constant>(BasePair.second))
2287  Info.LiveSet.remove(BasePair.first);
2288 
2289  for (CallInst *CI : Holders)
2290  CI->eraseFromParent();
2291 
2292  Holders.clear();
2293 
2294  // In order to reduce live set of statepoint we might choose to rematerialize
2295  // some values instead of relocating them. This is purely an optimization and
2296  // does not influence correctness.
2297  for (size_t i = 0; i < Records.size(); i++)
2298  rematerializeLiveValues(ToUpdate[i], Records[i], TTI);
2299 
2300  // We need this to safely RAUW and delete call or invoke return values that
2301  // may themselves be live over a statepoint. For details, please see usage in
2302  // makeStatepointExplicitImpl.
2303  std::vector<DeferredReplacement> Replacements;
2304 
2305  // Now run through and replace the existing statepoints with new ones with
2306  // the live variables listed. We do not yet update uses of the values being
2307  // relocated. We have references to live variables that need to
2308  // survive to the last iteration of this loop. (By construction, the
2309  // previous statepoint can not be a live variable, thus we can and remove
2310  // the old statepoint calls as we go.)
2311  for (size_t i = 0; i < Records.size(); i++)
2312  makeStatepointExplicit(DT, ToUpdate[i], Records[i], Replacements);
2313 
2314  ToUpdate.clear(); // prevent accident use of invalid CallSites
2315 
2316  for (auto &PR : Replacements)
2317  PR.doReplacement();
2318 
2319  Replacements.clear();
2320 
2321  for (auto &Info : Records) {
2322  // These live sets may contain state Value pointers, since we replaced calls
2323  // with operand bundles with calls wrapped in gc.statepoint, and some of
2324  // those calls may have been def'ing live gc pointers. Clear these out to
2325  // avoid accidentally using them.
2326  //
2327  // TODO: We should create a separate data structure that does not contain
2328  // these live sets, and migrate to using that data structure from this point
2329  // onward.
2330  Info.LiveSet.clear();
2331  Info.PointerToBase.clear();
2332  }
2333 
2334  // Do all the fixups of the original live variables to their relocated selves
2336  for (size_t i = 0; i < Records.size(); i++) {
2337  PartiallyConstructedSafepointRecord &Info = Records[i];
2338 
2339  // We can't simply save the live set from the original insertion. One of
2340  // the live values might be the result of a call which needs a safepoint.
2341  // That Value* no longer exists and we need to use the new gc_result.
2342  // Thankfully, the live set is embedded in the statepoint (and updated), so
2343  // we just grab that.
2344  Statepoint Statepoint(Info.StatepointToken);
2345  Live.insert(Live.end(), Statepoint.gc_args_begin(),
2346  Statepoint.gc_args_end());
2347 #ifndef NDEBUG
2348  // Do some basic sanity checks on our liveness results before performing
2349  // relocation. Relocation can and will turn mistakes in liveness results
2350  // into non-sensical code which is must harder to debug.
2351  // TODO: It would be nice to test consistency as well
2352  assert(DT.isReachableFromEntry(Info.StatepointToken->getParent()) &&
2353  "statepoint must be reachable or liveness is meaningless");
2354  for (Value *V : Statepoint.gc_args()) {
2355  if (!isa<Instruction>(V))
2356  // Non-instruction values trivial dominate all possible uses
2357  continue;
2358  auto *LiveInst = cast<Instruction>(V);
2359  assert(DT.isReachableFromEntry(LiveInst->getParent()) &&
2360  "unreachable values should never be live");
2361  assert(DT.dominates(LiveInst, Info.StatepointToken) &&
2362  "basic SSA liveness expectation violated by liveness analysis");
2363  }
2364 #endif
2365  }
2366  unique_unsorted(Live);
2367 
2368 #ifndef NDEBUG
2369  // sanity check
2370  for (auto *Ptr : Live)
2371  assert(isHandledGCPointerType(Ptr->getType()) &&
2372  "must be a gc pointer type");
2373 #endif
2374 
2375  relocationViaAlloca(F, DT, Live, Records);
2376  return !Records.empty();
2377 }
2378 
2379 // Handles both return values and arguments for Functions and CallSites.
2380 template <typename AttrHolder>
2381 static void RemoveNonValidAttrAtIndex(LLVMContext &Ctx, AttrHolder &AH,
2382  unsigned Index) {
2383  AttrBuilder R;
2384  if (AH.getDereferenceableBytes(Index))
2385  R.addAttribute(Attribute::get(Ctx, Attribute::Dereferenceable,
2386  AH.getDereferenceableBytes(Index)));
2387  if (AH.getDereferenceableOrNullBytes(Index))
2388  R.addAttribute(Attribute::get(Ctx, Attribute::DereferenceableOrNull,
2389  AH.getDereferenceableOrNullBytes(Index)));
2390  if (AH.getAttributes().hasAttribute(Index, Attribute::NoAlias))
2392 
2393  if (!R.empty())
2394  AH.setAttributes(AH.getAttributes().removeAttributes(Ctx, Index, R));
2395 }
2396 
2398  LLVMContext &Ctx = F.getContext();
2399 
2400  for (Argument &A : F.args())
2401  if (isa<PointerType>(A.getType()))
2403  A.getArgNo() + AttributeList::FirstArgIndex);
2404 
2405  if (isa<PointerType>(F.getReturnType()))
2407 }
2408 
2409 /// Certain metadata on instructions are invalid after running RS4GC.
2410 /// Optimizations that run after RS4GC can incorrectly use this metadata to
2411 /// optimize functions. We drop such metadata on the instruction.
2413  if (!isa<LoadInst>(I) && !isa<StoreInst>(I))
2414  return;
2415  // These are the attributes that are still valid on loads and stores after
2416  // RS4GC.
2417  // The metadata implying dereferenceability and noalias are (conservatively)
2418  // dropped. This is because semantically, after RewriteStatepointsForGC runs,
2419  // all calls to gc.statepoint "free" the entire heap. Also, gc.statepoint can
2420  // touch the entire heap including noalias objects. Note: The reasoning is
2421  // same as stripping the dereferenceability and noalias attributes that are
2422  // analogous to the metadata counterparts.
2423  // We also drop the invariant.load metadata on the load because that metadata
2424  // implies the address operand to the load points to memory that is never
2425  // changed once it became dereferenceable. This is no longer true after RS4GC.
2426  // Similar reasoning applies to invariant.group metadata, which applies to
2427  // loads within a group.
2428  unsigned ValidMetadataAfterRS4GC[] = {LLVMContext::MD_tbaa,
2435 
2436  // Drops all metadata on the instruction other than ValidMetadataAfterRS4GC.
2437  I.dropUnknownNonDebugMetadata(ValidMetadataAfterRS4GC);
2438 }
2439 
2441  if (F.empty())
2442  return;
2443 
2444  LLVMContext &Ctx = F.getContext();
2445  MDBuilder Builder(Ctx);
2446 
2447  // Set of invariantstart instructions that we need to remove.
2448  // Use this to avoid invalidating the instruction iterator.
2449  SmallVector<IntrinsicInst*, 12> InvariantStartInstructions;
2450 
2451  for (Instruction &I : instructions(F)) {
2452  // invariant.start on memory location implies that the referenced memory
2453  // location is constant and unchanging. This is no longer true after
2454  // RewriteStatepointsForGC runs because there can be calls to gc.statepoint
2455  // which frees the entire heap and the presence of invariant.start allows
2456  // the optimizer to sink the load of a memory location past a statepoint,
2457  // which is incorrect.
2458  if (auto *II = dyn_cast<IntrinsicInst>(&I))
2459  if (II->getIntrinsicID() == Intrinsic::invariant_start) {
2460  InvariantStartInstructions.push_back(II);
2461  continue;
2462  }
2463 
2464  if (const MDNode *MD = I.getMetadata(LLVMContext::MD_tbaa)) {
2465  assert(MD->getNumOperands() < 5 && "unrecognized metadata shape!");
2466  bool IsImmutableTBAA =
2467  MD->getNumOperands() == 4 &&
2468  mdconst::extract<ConstantInt>(MD->getOperand(3))->getValue() == 1;
2469 
2470  if (!IsImmutableTBAA)
2471  continue; // no work to do, MD_tbaa is already marked mutable
2472 
2473  MDNode *Base = cast<MDNode>(MD->getOperand(0));
2474  MDNode *Access = cast<MDNode>(MD->getOperand(1));
2475  uint64_t Offset =
2476  mdconst::extract<ConstantInt>(MD->getOperand(2))->getZExtValue();
2477 
2478  MDNode *MutableTBAA =
2479  Builder.createTBAAStructTagNode(Base, Access, Offset);
2480  I.setMetadata(LLVMContext::MD_tbaa, MutableTBAA);
2481  }
2482 
2484 
2485  if (CallSite CS = CallSite(&I)) {
2486  for (int i = 0, e = CS.arg_size(); i != e; i++)
2487  if (isa<PointerType>(CS.getArgument(i)->getType()))
2489  if (isa<PointerType>(CS.getType()))
2491  }
2492  }
2493 
2494  // Delete the invariant.start instructions and RAUW undef.
2495  for (auto *II : InvariantStartInstructions) {
2496  II->replaceAllUsesWith(UndefValue::get(II->getType()));
2497  II->eraseFromParent();
2498  }
2499 }
2500 
2501 /// Returns true if this function should be rewritten by this pass. The main
2502 /// point of this function is as an extension point for custom logic.
2504  // TODO: This should check the GCStrategy
2505  if (F.hasGC()) {
2506  const auto &FunctionGCName = F.getGC();
2507  const StringRef StatepointExampleName("statepoint-example");
2508  const StringRef CoreCLRName("coreclr");
2509  return (StatepointExampleName == FunctionGCName) ||
2510  (CoreCLRName == FunctionGCName);
2511  } else
2512  return false;
2513 }
2514 
2515 static void stripNonValidData(Module &M) {
2516 #ifndef NDEBUG
2517  assert(llvm::any_of(M, shouldRewriteStatepointsIn) && "precondition!");
2518 #endif
2519 
2520  for (Function &F : M)
2522 
2523  for (Function &F : M)
2525 }
2526 
2528  TargetTransformInfo &TTI,
2529  const TargetLibraryInfo &TLI) {
2530  assert(!F.isDeclaration() && !F.empty() &&
2531  "need function body to rewrite statepoints in");
2532  assert(shouldRewriteStatepointsIn(F) && "mismatch in rewrite decision");
2533 
2534  auto NeedsRewrite = [&TLI](Instruction &I) {
2535  if (ImmutableCallSite CS = ImmutableCallSite(&I))
2536  return !callsGCLeafFunction(CS, TLI) && !isStatepoint(CS);
2537  return false;
2538  };
2539 
2540  // Gather all the statepoints which need rewritten. Be careful to only
2541  // consider those in reachable code since we need to ask dominance queries
2542  // when rewriting. We'll delete the unreachable ones in a moment.
2543  SmallVector<CallSite, 64> ParsePointNeeded;
2544  bool HasUnreachableStatepoint = false;
2545  for (Instruction &I : instructions(F)) {
2546  // TODO: only the ones with the flag set!
2547  if (NeedsRewrite(I)) {
2548  if (DT.isReachableFromEntry(I.getParent()))
2549  ParsePointNeeded.push_back(CallSite(&I));
2550  else
2551  HasUnreachableStatepoint = true;
2552  }
2553  }
2554 
2555  bool MadeChange = false;
2556 
2557  // Delete any unreachable statepoints so that we don't have unrewritten
2558  // statepoints surviving this pass. This makes testing easier and the
2559  // resulting IR less confusing to human readers. Rather than be fancy, we
2560  // just reuse a utility function which removes the unreachable blocks.
2561  if (HasUnreachableStatepoint)
2562  MadeChange |= removeUnreachableBlocks(F);
2563 
2564  // Return early if no work to do.
2565  if (ParsePointNeeded.empty())
2566  return MadeChange;
2567 
2568  // As a prepass, go ahead and aggressively destroy single entry phi nodes.
2569  // These are created by LCSSA. They have the effect of increasing the size
2570  // of liveness sets for no good reason. It may be harder to do this post
2571  // insertion since relocations and base phis can confuse things.
2572  for (BasicBlock &BB : F)
2573  if (BB.getUniquePredecessor()) {
2574  MadeChange = true;
2576  }
2577 
2578  // Before we start introducing relocations, we want to tweak the IR a bit to
2579  // avoid unfortunate code generation effects. The main example is that we
2580  // want to try to make sure the comparison feeding a branch is after any
2581  // safepoints. Otherwise, we end up with a comparison of pre-relocation
2582  // values feeding a branch after relocation. This is semantically correct,
2583  // but results in extra register pressure since both the pre-relocation and
2584  // post-relocation copies must be available in registers. For code without
2585  // relocations this is handled elsewhere, but teaching the scheduler to
2586  // reverse the transform we're about to do would be slightly complex.
2587  // Note: This may extend the live range of the inputs to the icmp and thus
2588  // increase the liveset of any statepoint we move over. This is profitable
2589  // as long as all statepoints are in rare blocks. If we had in-register
2590  // lowering for live values this would be a much safer transform.
2591  auto getConditionInst = [](TerminatorInst *TI) -> Instruction* {
2592  if (auto *BI = dyn_cast<BranchInst>(TI))
2593  if (BI->isConditional())
2594  return dyn_cast<Instruction>(BI->getCondition());
2595  // TODO: Extend this to handle switches
2596  return nullptr;
2597  };
2598  for (BasicBlock &BB : F) {
2599  TerminatorInst *TI = BB.getTerminator();
2600  if (auto *Cond = getConditionInst(TI))
2601  // TODO: Handle more than just ICmps here. We should be able to move
2602  // most instructions without side effects or memory access.
2603  if (isa<ICmpInst>(Cond) && Cond->hasOneUse()) {
2604  MadeChange = true;
2605  Cond->moveBefore(TI);
2606  }
2607  }
2608 
2609  MadeChange |= insertParsePoints(F, DT, TTI, ParsePointNeeded);
2610  return MadeChange;
2611 }
2612 
2613 // liveness computation via standard dataflow
2614 // -------------------------------------------------------------------
2615 
2616 // TODO: Consider using bitvectors for liveness, the set of potentially
2617 // interesting values should be small and easy to pre-compute.
2618 
2619 /// Compute the live-in set for the location rbegin starting from
2620 /// the live-out set of the basic block
2623  SetVector<Value *> &LiveTmp) {
2624  for (auto &I : make_range(Begin, End)) {
2625  // KILL/Def - Remove this definition from LiveIn
2626  LiveTmp.remove(&I);
2627 
2628  // Don't consider *uses* in PHI nodes, we handle their contribution to
2629  // predecessor blocks when we seed the LiveOut sets
2630  if (isa<PHINode>(I))
2631  continue;
2632 
2633  // USE - Add to the LiveIn set for this instruction
2634  for (Value *V : I.operands()) {
2636  "support for FCA unimplemented");
2637  if (isHandledGCPointerType(V->getType()) && !isa<Constant>(V)) {
2638  // The choice to exclude all things constant here is slightly subtle.
2639  // There are two independent reasons:
2640  // - We assume that things which are constant (from LLVM's definition)
2641  // do not move at runtime. For example, the address of a global
2642  // variable is fixed, even though it's contents may not be.
2643  // - Second, we can't disallow arbitrary inttoptr constants even
2644  // if the language frontend does. Optimization passes are free to
2645  // locally exploit facts without respect to global reachability. This
2646  // can create sections of code which are dynamically unreachable and
2647  // contain just about anything. (see constants.ll in tests)
2648  LiveTmp.insert(V);
2649  }
2650  }
2651  }
2652 }
2653 
2655  for (BasicBlock *Succ : successors(BB)) {
2656  for (auto &I : *Succ) {
2657  PHINode *PN = dyn_cast<PHINode>(&I);
2658  if (!PN)
2659  break;
2660 
2661  Value *V = PN->getIncomingValueForBlock(BB);
2663  "support for FCA unimplemented");
2664  if (isHandledGCPointerType(V->getType()) && !isa<Constant>(V))
2665  LiveTmp.insert(V);
2666  }
2667  }
2668 }
2669 
2671  SetVector<Value *> KillSet;
2672  for (Instruction &I : *BB)
2674  KillSet.insert(&I);
2675  return KillSet;
2676 }
2677 
2678 #ifndef NDEBUG
2679 /// Check that the items in 'Live' dominate 'TI'. This is used as a basic
2680 /// sanity check for the liveness computation.
2682  TerminatorInst *TI, bool TermOkay = false) {
2683  for (Value *V : Live) {
2684  if (auto *I = dyn_cast<Instruction>(V)) {
2685  // The terminator can be a member of the LiveOut set. LLVM's definition
2686  // of instruction dominance states that V does not dominate itself. As
2687  // such, we need to special case this to allow it.
2688  if (TermOkay && TI == I)
2689  continue;
2690  assert(DT.dominates(I, TI) &&
2691  "basic SSA liveness expectation violated by liveness analysis");
2692  }
2693  }
2694 }
2695 
2696 /// Check that all the liveness sets used during the computation of liveness
2697 /// obey basic SSA properties. This is useful for finding cases where we miss
2698 /// a def.
2699 static void checkBasicSSA(DominatorTree &DT, GCPtrLivenessData &Data,
2700  BasicBlock &BB) {
2701  checkBasicSSA(DT, Data.LiveSet[&BB], BB.getTerminator());
2702  checkBasicSSA(DT, Data.LiveOut[&BB], BB.getTerminator(), true);
2703  checkBasicSSA(DT, Data.LiveIn[&BB], BB.getTerminator());
2704 }
2705 #endif
2706 
2708  GCPtrLivenessData &Data) {
2710 
2711  // Seed the liveness for each individual block
2712  for (BasicBlock &BB : F) {
2713  Data.KillSet[&BB] = computeKillSet(&BB);
2714  Data.LiveSet[&BB].clear();
2715  computeLiveInValues(BB.rbegin(), BB.rend(), Data.LiveSet[&BB]);
2716 
2717 #ifndef NDEBUG
2718  for (Value *Kill : Data.KillSet[&BB])
2719  assert(!Data.LiveSet[&BB].count(Kill) && "live set contains kill");
2720 #endif
2721 
2722  Data.LiveOut[&BB] = SetVector<Value *>();
2723  computeLiveOutSeed(&BB, Data.LiveOut[&BB]);
2724  Data.LiveIn[&BB] = Data.LiveSet[&BB];
2725  Data.LiveIn[&BB].set_union(Data.LiveOut[&BB]);
2726  Data.LiveIn[&BB].set_subtract(Data.KillSet[&BB]);
2727  if (!Data.LiveIn[&BB].empty())
2728  Worklist.insert(pred_begin(&BB), pred_end(&BB));
2729  }
2730 
2731  // Propagate that liveness until stable
2732  while (!Worklist.empty()) {
2733  BasicBlock *BB = Worklist.pop_back_val();
2734 
2735  // Compute our new liveout set, then exit early if it hasn't changed despite
2736  // the contribution of our successor.
2737  SetVector<Value *> LiveOut = Data.LiveOut[BB];
2738  const auto OldLiveOutSize = LiveOut.size();
2739  for (BasicBlock *Succ : successors(BB)) {
2740  assert(Data.LiveIn.count(Succ));
2741  LiveOut.set_union(Data.LiveIn[Succ]);
2742  }
2743  // assert OutLiveOut is a subset of LiveOut
2744  if (OldLiveOutSize == LiveOut.size()) {
2745  // If the sets are the same size, then we didn't actually add anything
2746  // when unioning our successors LiveIn. Thus, the LiveIn of this block
2747  // hasn't changed.
2748  continue;
2749  }
2750  Data.LiveOut[BB] = LiveOut;
2751 
2752  // Apply the effects of this basic block
2753  SetVector<Value *> LiveTmp = LiveOut;
2754  LiveTmp.set_union(Data.LiveSet[BB]);
2755  LiveTmp.set_subtract(Data.KillSet[BB]);
2756 
2757  assert(Data.LiveIn.count(BB));
2758  const SetVector<Value *> &OldLiveIn = Data.LiveIn[BB];
2759  // assert: OldLiveIn is a subset of LiveTmp
2760  if (OldLiveIn.size() != LiveTmp.size()) {
2761  Data.LiveIn[BB] = LiveTmp;
2762  Worklist.insert(pred_begin(BB), pred_end(BB));
2763  }
2764  } // while (!Worklist.empty())
2765 
2766 #ifndef NDEBUG
2767  // Sanity check our output against SSA properties. This helps catch any
2768  // missing kills during the above iteration.
2769  for (BasicBlock &BB : F)
2770  checkBasicSSA(DT, Data, BB);
2771 #endif
2772 }
2773 
2774 static void findLiveSetAtInst(Instruction *Inst, GCPtrLivenessData &Data,
2775  StatepointLiveSetTy &Out) {
2776  BasicBlock *BB = Inst->getParent();
2777 
2778  // Note: The copy is intentional and required
2779  assert(Data.LiveOut.count(BB));
2780  SetVector<Value *> LiveOut = Data.LiveOut[BB];
2781 
2782  // We want to handle the statepoint itself oddly. It's
2783  // call result is not live (normal), nor are it's arguments
2784  // (unless they're used again later). This adjustment is
2785  // specifically what we need to relocate
2786  computeLiveInValues(BB->rbegin(), ++Inst->getIterator().getReverse(),
2787  LiveOut);
2788  LiveOut.remove(Inst);
2789  Out.insert(LiveOut.begin(), LiveOut.end());
2790 }
2791 
2792 static void recomputeLiveInValues(GCPtrLivenessData &RevisedLivenessData,
2793  CallSite CS,
2794  PartiallyConstructedSafepointRecord &Info) {
2795  Instruction *Inst = CS.getInstruction();
2796  StatepointLiveSetTy Updated;
2797  findLiveSetAtInst(Inst, RevisedLivenessData, Updated);
2798 
2799 #ifndef NDEBUG
2800  DenseSet<Value *> Bases;
2801  for (auto KVPair : Info.PointerToBase)
2802  Bases.insert(KVPair.second);
2803 #endif
2804 
2805  // We may have base pointers which are now live that weren't before. We need
2806  // to update the PointerToBase structure to reflect this.
2807  for (auto V : Updated)
2808  if (Info.PointerToBase.insert({V, V}).second) {
2809  assert(Bases.count(V) && "Can't find base for unexpected live value!");
2810  continue;
2811  }
2812 
2813 #ifndef NDEBUG
2814  for (auto V : Updated)
2815  assert(Info.PointerToBase.count(V) &&
2816  "Must be able to find base for live value!");
2817 #endif
2818 
2819  // Remove any stale base mappings - this can happen since our liveness is
2820  // more precise then the one inherent in the base pointer analysis.
2821  DenseSet<Value *> ToErase;
2822  for (auto KVPair : Info.PointerToBase)
2823  if (!Updated.count(KVPair.first))
2824  ToErase.insert(KVPair.first);
2825 
2826  for (auto *V : ToErase)
2827  Info.PointerToBase.erase(V);
2828 
2829 #ifndef NDEBUG
2830  for (auto KVPair : Info.PointerToBase)
2831  assert(Updated.count(KVPair.first) && "record for non-live value");
2832 #endif
2833 
2834  Info.LiveSet = Updated;
2835 }
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:67
static void findLiveReferences(Function &F, DominatorTree &DT, ArrayRef< CallSite > toUpdate, MutableArrayRef< struct PartiallyConstructedSafepointRecord > records)
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:109
static void unique_unsorted(SmallVectorImpl< T > &Vec)
Implement a unique function which doesn&#39;t require we sort the input vector.
static void computeLiveOutSeed(BasicBlock *BB, SetVector< Value *> &LiveTmp)
static bool isHandledGCPointerType(Type *T)
bool empty() const
Definition: Function.h:594
static cl::opt< bool, true > ClobberNonLiveOverride("rs4gc-clobber-non-live", cl::location(ClobberNonLive), cl::Hidden)
raw_ostream & errs()
This returns a reference to a raw_ostream for standard error.
MapVector< Value *, Value * > DefiningValueMapTy
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
This class represents an incoming formal argument to a Function.
Definition: Argument.h:30
LLVM_NODISCARD std::string str() const
str - Get the contents as an std::string.
Definition: StringRef.h:228
static Value * findBaseDefiningValueCached(Value *I, DefiningValueMapTy &Cache)
Returns the base defining value for this value.
static bool AreEquivalentPhiNodes(PHINode &OrigRootPhi, PHINode &AlternateRootPhi)
unsigned arg_size() const
Definition: CallSite.h:219
static BDVState meetBDVStateImpl(const BDVState &LHS, const BDVState &RHS)
static bool insertParsePoints(Function &F, DominatorTree &DT, TargetTransformInfo &TTI, SmallVectorImpl< CallSite > &ToUpdate)
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
Definition: ilist_node.h:289
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:687
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:449
Instruction * StatepointToken
The new gc.statepoint instruction itself.
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:78
Constant * getOrInsertFunction(StringRef Name, FunctionType *T, AttributeList AttributeList)
Look up the specified function in the module symbol table.
Definition: Module.cpp:142
static void stripInvalidMetadataFromInstruction(Instruction &I)
Certain metadata on instructions are invalid after running RS4GC.
Instruction * UnwindToken
Instruction to which exceptional gc relocates are attached Makes it easier to iterate through them du...
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:63
void dropUnknownNonDebugMetadata(ArrayRef< unsigned > KnownIDs)
Drop all unknown metadata except for debug locations.
Definition: Metadata.cpp:1187
iterator begin() const
Definition: ArrayRef.h:137
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:136
StatepointDirectives parseStatepointDirectivesFromAttrs(AttributeList AS)
Parse out statepoint directives from the function attributes present in AS.
Definition: Statepoint.cpp:69
static ConstantAggregateZero * get(Type *Ty)
Definition: Constants.cpp:1236
This provides a very simple, boring adaptor for a begin and end iterator into a range type...
static void rematerializeLiveValues(CallSite CS, PartiallyConstructedSafepointRecord &Info, TargetTransformInfo &TTI)
static StringRef getDeoptLowering(CallSite CS)
This class represents a function call, abstracting a target machine&#39;s calling convention.
INITIALIZE_PASS_BEGIN(RewriteStatepointsForGCLegacyPass, "rewrite-statepoints-for-gc", "Make relocations explicit at statepoints", false, false) INITIALIZE_PASS_END(RewriteStatepointsForGCLegacyPass
This file contains the declarations for metadata subclasses.
MapVector< BasicBlock *, SetVector< Value * > > KillSet
Values defined in this block.
const Value * getTrueValue() const
Analysis pass providing the TargetTransformInfo.
This instruction constructs a fixed permutation of two input vectors.
static SelectInst * Create(Value *C, Value *S1, Value *S2, const Twine &NameStr="", Instruction *InsertBefore=nullptr, Instruction *MDFrom=nullptr)
MapVector< BasicBlock *, SetVector< Value * > > LiveSet
Values used in this block (and thus live); does not included values killed within this block...
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:728
static void stripNonValidAttributesFromPrototype(Function &F)
MapVector< BasicBlock *, SetVector< Value * > > LiveIn
Values live into this basic block (i.e.
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
Definition: Function.h:262
This class implements a map that also provides access to all stored values in a deterministic order...
Definition: MapVector.h:38
Metadata node.
Definition: Metadata.h:862
The two locations do not alias at all.
Definition: AliasAnalysis.h:85
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:238
F(f)
static CallInst * Create(Value *Func, ArrayRef< Value *> Args, ArrayRef< OperandBundleDef > Bundles=None, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
static void makeStatepointExplicitImpl(const CallSite CS, const SmallVectorImpl< Value *> &BasePtrs, const SmallVectorImpl< Value *> &LiveVariables, PartiallyConstructedSafepointRecord &Result, std::vector< DeferredReplacement > &Replacements)
An instruction for reading from memory.
Definition: Instructions.h:164
reverse_iterator rbegin()
Definition: BasicBlock.h:257
AttrBuilder & addAttribute(Attribute::AttrKind Val)
Add an attribute to the builder.
Hexagon Common GEP
bool isVectorTy() const
True if this is an instance of VectorType.
Definition: Type.h:227
static void stripNonValidDataFromBody(Function &F)
static BaseDefiningValueResult findBaseDefiningValueOfVector(Value *I)
Return a base defining value for the &#39;Index&#39; element of the given vector instruction &#39;I&#39;...
void reserve(size_type N)
Definition: SmallVector.h:380
CallingConv::ID getCallingConv() const
getCallingConv/setCallingConv - Get or set the calling convention of this function call...
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:290
static void checkBasicSSA(DominatorTree &DT, SetVector< Value *> &Live, TerminatorInst *TI, bool TermOkay=false)
Check that the items in &#39;Live&#39; dominate &#39;TI&#39;.
bool hasAttribute(unsigned Index, Attribute::AttrKind Kind) const
Return true if the attribute exists at the given index.
static void computeLiveInValues(DominatorTree &DT, Function &F, GCPtrLivenessData &Data)
Compute the live-in set for every basic block in the function.
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:252
void setCallingConv(CallingConv::ID CC)
AttributeList getAttributes() const
Return the parameter attributes for this call.
unsigned getAllocaAddrSpace() const
Definition: DataLayout.h:253
AnalysisUsage & addRequired()
static InsertElementInst * Create(Value *Vec, Value *NewElt, Value *Idx, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
CallSiteTy::arg_iterator gc_args_begin() const
Definition: Statepoint.h:250
static void relocationViaAlloca(Function &F, DominatorTree &DT, ArrayRef< Value *> Live, ArrayRef< PartiallyConstructedSafepointRecord > Records)
Do all the relocation update via allocas and mem2reg.
This class represents the LLVM &#39;select&#39; instruction.
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:361
CallingConv::ID getCallingConv() const
getCallingConv/setCallingConv - Get or set the calling convention of this function call...
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:560
&#39;undef&#39; values are things that do not have specified contents.
Definition: Constants.h:1247
int getCastInstrCost(unsigned Opcode, Type *Dst, Type *Src, const Instruction *I=nullptr) const
static bool isKnownBaseResult(Value *V)
Given the result of a call to findBaseDefiningValue, or findBaseOrBDV, is it known to be a base point...
TailCallKind getTailCallKind() const
Class to represent struct types.
Definition: DerivedTypes.h:201
LLVMContext & getContext() const
Get the global data context.
Definition: Module.h:237
static Value * findBasePointer(Value *I, DefiningValueMapTy &Cache)
For a given value or instruction, figure out what base ptr its derived from.
A Use represents the edge between a Value definition and its users.
Definition: Use.h:56
Value * getDerivedPtr() const
Definition: Statepoint.h:402
IterTy arg_end() const
Definition: CallSite.h:575
static Value * findRematerializableChainToBasePointer(SmallVectorImpl< Instruction *> &ChainToBase, Value *CurrentValue)
static bool isGCPointerType(Type *T)
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:668
static void makeStatepointExplicit(DominatorTree &DT, CallSite CS, PartiallyConstructedSafepointRecord &Result, std::vector< DeferredReplacement > &Replacements)
This file contains the simple types necessary to represent the attributes associated with functions a...
AttributeSet getRetAttributes() const
The attributes for the ret value are returned.
InstrTy * getInstruction() const
Definition: CallSite.h:92
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:286
bool remove(const value_type &X)
Remove an item from the set vector.
Definition: SetVector.h:158
ELFYAML::ELF_STO Other
Definition: ELFYAML.cpp:736
void initializeRewriteStatepointsForGCLegacyPassPass(PassRegistry &)
LLVMContext & getContext() const
Retrieve the LLVM context.
auto reverse(ContainerTy &&C, typename std::enable_if< has_rbegin< ContainerTy >::value >::type *=nullptr) -> decltype(make_range(C.rbegin(), C.rend()))
Definition: STLExtras.h:232
ValTy * getCalledValue() const
Return the pointer to function that is being called.
Definition: CallSite.h:100
static cl::opt< bool > PrintLiveSet("spp-print-liveset", cl::Hidden, cl::init(false))
Instruction * clone() const
Create a copy of &#39;this&#39; instruction that is identical in all ways except the following: ...
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:142
CallSiteTy::arg_iterator gc_args_end() const
Definition: Statepoint.h:253
const T & getValue() const LLVM_LVALUE_FUNCTION
Definition: Optional.h:127
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
Definition: BasicBlock.cpp:230
Class to represent array types.
Definition: DerivedTypes.h:369
This class represents a no-op cast from one type to another.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
AttrBuilder & remove(const AttrBuilder &B)
Remove the attributes from the builder.
const std::string & getGC() const
Definition: Function.cpp:443
An instruction for storing to memory.
Definition: Instructions.h:306
void SetCurrentDebugLocation(DebugLoc L)
Set location information used by debugging information.
Definition: IRBuilder.h:152
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:430
ModulePass * createRewriteStatepointsForGCLegacyPass()
StatepointLiveSetTy LiveSet
The set of values known to be live across this safepoint.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:140
int getAddressComputationCost(Type *Ty, ScalarEvolution *SE=nullptr, const SCEV *Ptr=nullptr) const
Function * getDeclaration(Module *M, ID id, ArrayRef< Type *> Tys=None)
Create or insert an LLVM Function declaration for an intrinsic, and return it.
Definition: Function.cpp:979
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block...
Definition: IRBuilder.h:128
static unsigned chainToBasePointerCost(SmallVectorImpl< Instruction *> &Chain, TargetTransformInfo &TTI)
SetVector< Value * > StatepointLiveSetTy
void replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
Definition: User.cpp:21
bool isCall() const
Return true if a CallInst is enclosed.
Definition: CallSite.h:87
Optional< OperandBundleUse > getOperandBundle(StringRef Name) const
Definition: CallSite.h:555
static SetVector< Value * > computeKillSet(BasicBlock *BB)
bool isVoidTy() const
Return true if this is &#39;void&#39;.
Definition: Type.h:141
const BasicBlock & getEntryBlock() const
Definition: Function.h:572
an instruction for type-safe pointer arithmetic to access elements of arrays and structs ...
Definition: Instructions.h:837
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata *> MDs)
Definition: Metadata.h:1164
CallInst * CreateGCStatepointCall(uint64_t ID, uint32_t NumPatchBytes, Value *ActualCallee, ArrayRef< Value *> CallArgs, ArrayRef< Value *> DeoptArgs, ArrayRef< Value *> GCArgs, const Twine &Name="")
Create a call to the experimental.gc.statepoint intrinsic to start a new statepoint sequence...
Definition: IRBuilder.cpp:516
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:406
Type * getReturnType() const
Returns the type of the ret val.
Definition: Function.h:150
static void RemoveNonValidAttrAtIndex(LLVMContext &Ctx, AttrHolder &AH, unsigned Index)
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
Definition: BasicBlock.cpp:171
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
Subclasses of this class are all able to terminate a basic block.
Definition: InstrTypes.h:54
Wrapper pass for TargetTransformInfo.
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
static AttributeSet get(LLVMContext &C, const AttrBuilder &B)
Definition: Attributes.cpp:505
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
Definition: BasicBlock.cpp:200
static ConstantPointerNull * get(PointerType *T)
Static factory methods - Return objects of the specified value.
Definition: Constants.cpp:1305
MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...
Definition: ArrayRef.h:291
static ArrayRef< Use > GetDeoptBundleOperands(ImmutableCallSite CS)
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction...
Definition: Instruction.cpp:73
bool hasName() const
Definition: Value.h:251
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:69
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:149
This function has undefined behavior.
This is an important base class in LLVM.
Definition: Constant.h:42
bool set_union(const STy &S)
Compute This := This u S, return whether &#39;This&#39; changed.
Definition: SetVector.h:246
static void analyzeParsePointLiveness(DominatorTree &DT, GCPtrLivenessData &OriginalLivenessData, CallSite CS, PartiallyConstructedSafepointRecord &Result)
ArrayRef< Use > Inputs
Definition: InstrTypes.h:1163
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:116
bool hasFnAttr(Attribute::AttrKind Kind) const
Return true if this function has the given attribute.
Definition: CallSite.h:362
static cl::opt< unsigned > RematerializationThreshold("spp-rematerialization-threshold", cl::Hidden, cl::init(6))
Value * getIncomingValueForBlock(const BasicBlock *BB) const
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:36
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static AttributeList legalizeCallAttributes(AttributeList AL)
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:187
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:113
bool runOnFunction(Function &F, DominatorTree &, TargetTransformInfo &, const TargetLibraryInfo &)
Optional< uint32_t > NumPatchBytes
Definition: Statepoint.h:457
InvokeInst * CreateGCStatepointInvoke(uint64_t ID, uint32_t NumPatchBytes, Value *ActualInvokee, BasicBlock *NormalDest, BasicBlock *UnwindDest, ArrayRef< Value *> InvokeArgs, ArrayRef< Value *> DeoptArgs, ArrayRef< Value *> GCArgs, const Twine &Name="")
brief Create an invoke to the experimental.gc.statepoint intrinsic to start a new statepoint sequence...
Definition: IRBuilder.cpp:566
Represent the analysis usage information of a pass.
static Type * getVoidTy(LLVMContext &C)
Definition: Type.cpp:161
bool any_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:820
RematerializedValueMapTy RematerializedValues
Record live values we are rematerialized instead of relocating.
static const unsigned End
static FunctionType * get(Type *Result, ArrayRef< Type *> Params, bool isVarArg)
This static method is the primary way of constructing a FunctionType.
Definition: Type.cpp:297
A specialization of it&#39;s base class for read-write access to a gc.statepoint.
Definition: Statepoint.h:319
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:116
BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock *> Preds, const char *Suffix, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, bool PreserveLCSSA=false)
This method introduces at least one new basic block into the function and moves some of the predecess...
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
bool callsGCLeafFunction(ImmutableCallSite CS, const TargetLibraryInfo &TLI)
Return true if the CallSite CS calls a gc leaf function.
Definition: Local.cpp:1898
self_iterator getIterator()
Definition: ilist_node.h:82
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn&#39;t already there.
Definition: SmallSet.h:81
static void insertRelocationStores(iterator_range< Value::user_iterator > GCRelocs, DenseMap< Value *, Value *> &AllocaMap, DenseSet< Value *> &VisitedLiveValues)
static void insertRematerializationStores(const RematerializedValueMapTy &RematerializedValues, DenseMap< Value *, Value *> &AllocaMap, DenseSet< Value *> &VisitedLiveValues)
static void stripNonValidData(Module &M)
The IR fed into RewriteStatepointsForGC may have had attributes and metadata implying dereferenceabil...
void setTailCallKind(TailCallKind TCK)
const Function * getFunction() const
Return the function this instruction belongs to.
Definition: Instruction.cpp:59
lazy value info
static bool containsGCPtrType(Type *Ty)
Returns true if this type contains a gc pointer whether we know how to handle that type or not...
auto remove_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range))
Provide wrappers to std::remove_if which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:853
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function. ...
Definition: Function.cpp:193
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1319
const AMDGPUAS & AS
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs, and aliases.
Definition: Value.cpp:558
iterator erase(const_iterator CI)
Definition: SmallVector.h:449
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
Attribute getAttribute(unsigned Index, Attribute::AttrKind Kind) const
Return the attribute object that exists at the given index.
static void findLiveSetAtInst(Instruction *inst, GCPtrLivenessData &Data, StatepointLiveSetTy &out)
Given results from the dataflow liveness computation, find the set of live Values at a particular ins...
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range))
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:834
static PointerType * getInt8PtrTy(LLVMContext &C, unsigned AS=0)
Definition: Type.cpp:220
static Value * findBaseOrBDV(Value *I, DefiningValueMapTy &Cache)
Return a base pointer for this value if known.
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
Definition: Metadata.cpp:1214
static bool shouldRewriteStatepointsIn(Function &F)
Returns true if this function should be rewritten by this pass.
bool isInvoke() const
Return true if a InvokeInst is enclosed.
Definition: CallSite.h:90
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
BasicBlock * getNormalDest() const
bool isPtrOrPtrVectorTy() const
Return true if this is a pointer type or a vector of pointer types.
Definition: Type.h:224
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: MapVector.h:114
static cl::opt< bool > PrintBasePointers("spp-print-base-pointers", cl::Hidden, cl::init(false))
static cl::opt< bool > AllowStatepointWithNoDeoptInfo("rs4gc-allow-statepoint-with-no-deopt-info", cl::Hidden, cl::init(true))
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:298
Iterator for intrusive lists based on ilist_node.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
ValTy * getArgument(unsigned ArgNo) const
Definition: CallSite.h:186
bool removeUnreachableBlocks(Function &F, LazyValueInfo *LVI=nullptr)
Remove all blocks that can not be reached from the function&#39;s entry.
Definition: Local.cpp:1732
AttrBuilder & removeAttribute(Attribute::AttrKind Val)
Remove an attribute from the builder.
IterTy arg_begin() const
Definition: CallSite.h:571
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
static BDVState meetBDVState(const BDVState &LHS, const BDVState &RHS)
bool dominates(const Instruction *Def, const Use &U) const
Return true if Def dominates a use in User.
Definition: Dominators.cpp:239
Module.h This file contains the declarations for the Module class.
Provides information about what library functions are available for the current target.
iterator end() const
Definition: ArrayRef.h:138
static void insertUseHolderAfter(CallSite &CS, const ArrayRef< Value *> Values, SmallVectorImpl< CallInst *> &Holders)
Insert holders so that each Value is obviously live through the entire lifetime of the call...
Indicates that this statepoint is a transition from GC-aware code to code that is not GC-aware...
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:385
ConstantInt * getInt32(uint32_t C)
Get a constant 32-bit value.
Definition: IRBuilder.h:308
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static BasicBlock * normalizeForInvokeSafepoint(BasicBlock *BB, BasicBlock *InvokeParent, DominatorTree &DT)
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static const Function * getCalledFunction(const Value *V, bool LookThroughBitCast, bool &IsNoBuiltin)
void set_subtract(const STy &S)
Compute This := This - B TODO: We should be able to use set_subtract from SetOperations.h, but SetVector interface is inconsistent with DenseSet.
Definition: SetVector.h:261
Value handle that asserts if the Value is deleted.
Definition: ValueHandle.h:238
Intrinsic::ID getIntrinsicID() const LLVM_READONLY
getIntrinsicID - This method returns the ID number of the specified function, or Intrinsic::not_intri...
Definition: Function.h:175
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
static bool ClobberNonLive
A range adaptor for a pair of iterators.
Class to represent vector types.
Definition: DerivedTypes.h:393
static std::string suffixed_name_or(Value *V, StringRef Suffix, StringRef DefaultName)
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:55
void setAttributes(AttributeList A)
Set the parameter attributes for this call.
MapVector< AssertingVH< Instruction >, AssertingVH< Value > > RematerializedValueMapTy
bool isStatepointDirectiveAttr(Attribute Attr)
Return true if the the Attr is an attribute that is a statepoint directive.
Definition: Statepoint.cpp:63
Optional< uint64_t > StatepointID
Definition: Statepoint.h:458
iterator_range< user_iterator > users()
Definition: Value.h:405
static const uint64_t DefaultStatepointID
Definition: Statepoint.h:460
void FoldSingleEntryPHINodes(BasicBlock *BB, MemoryDependenceResults *MemDep=nullptr)
We know that BB has one predecessor.
iterator insert(iterator I, T &&Elt)
Definition: SmallVector.h:482
LLVM_NODISCARD LLVM_ATTRIBUTE_ALWAYS_INLINE bool equals(StringRef RHS) const
equals - Check for string equality, this is more efficient than compare() when the relative ordering ...
Definition: StringRef.h:169
const Value * getFalseValue() const
amdgpu Simplify well known AMD library false Value Value * Arg
Call sites that get wrapped by a gc.statepoint (currently only in RewriteStatepointsForGC and potenti...
Definition: Statepoint.h:456
bool operator!=(uint64_t V1, const APInt &V2)
Definition: APInt.h:1948
static void CreateGCRelocates(ArrayRef< Value *> LiveVariables, const int LiveStart, ArrayRef< Value *> BasePtrs, Instruction *StatepointToken, IRBuilder<> Builder)
Helper function to place all gc relocates necessary for the given statepoint.
bool hasValue() const
Definition: Optional.h:137
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:120
bool hasGC() const
hasGC/getGC/setGC/clearGC - The name of the garbage collection algorithm to use during code generatio...
Definition: Function.h:286
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:285
static cl::opt< bool > PrintLiveSetSize("spp-print-liveset-size", cl::Hidden, cl::init(false))
bool empty() const
Return true if the builder contains no target-independent attributes.
Definition: Attributes.h:794
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:61
StringRef getValueAsString() const
Return the attribute&#39;s value as a string.
Definition: Attributes.cpp:195
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:220
static bool isUnhandledGCPointerType(Type *Ty)
Establish a view to a call site for examination.
Definition: CallSite.h:713
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
void insertAfter(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately after the specified instruction...
Definition: Instruction.cpp:79
#define I(x, y, z)
Definition: MD5.cpp:58
CallInst * CreateGCResult(Instruction *Statepoint, Type *ResultType, const Twine &Name="")
Create a call to the experimental.gc.result intrinsic to extract the result from a call wrapped in a ...
Definition: IRBuilder.cpp:597
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:73
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
Definition: Pass.h:225
AttributeList getAttributes() const
Return the parameter attributes for this invoke.
static void findBasePointers(const StatepointLiveSetTy &live, MapVector< Value *, Value *> &PointerToBase, DominatorTree *DT, DefiningValueMapTy &DVCache)
iterator_range< value_op_iterator > operand_values()
Definition: User.h:246
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:323
ilist_iterator< OptionsT, !IsReverse, IsConst > getReverse() const
Get a reverse iterator to the same node.
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:174
static Attribute get(LLVMContext &Context, AttrKind Kind, uint64_t Val=0)
Return a uniquified Attribute object.
Definition: Attributes.cpp:81
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
Definition: DenseSet.h:91
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2018
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:141
Type * getType() const
Return the type of the instruction that generated this call site.
Definition: CallSite.h:264
bool isDeclaration() const
Return true if the primary definition of this global value is outside of the current translation unit...
Definition: Globals.cpp:201
bool isStatepoint(ImmutableCallSite CS)
Definition: Statepoint.cpp:27
FunTy * getCalledFunction() const
Return the function being called if this is a direct call, otherwise return null (if it&#39;s an indirect...
Definition: CallSite.h:107
Analysis pass providing the TargetLibraryInfo.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
user_iterator user_begin()
Definition: Value.h:381
MDNode * createTBAAStructTagNode(MDNode *BaseType, MDNode *AccessType, uint64_t Offset, bool IsConstant=false)
Return metadata for a TBAA tag node with the given base type, access type and offset relative to the ...
Definition: MDBuilder.cpp:190
BasicBlock * getUnwindDest() const
Represents calls to the gc.relocate intrinsic.
Definition: Statepoint.h:374
Mark the deopt arguments associated with the statepoint as only being "live-in".
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:556
LLVM Value Representation.
Definition: Value.h:73
succ_range successors(BasicBlock *BB)
Definition: CFG.h:143
A vector that has set insertion semantics.
Definition: SetVector.h:41
static VectorType * get(Type *ElementType, unsigned NumElements)
This static method is the primary way to construct an VectorType.
Definition: Type.cpp:593
static void recomputeLiveInValues(GCPtrLivenessData &RevisedLivenessData, CallSite CS, PartiallyConstructedSafepointRecord &result)
Given an updated version of the dataflow liveness results, update the liveset and base pointer maps f...
static const Function * getParent(const Value *V)
AttributeSet getFnAttributes() const
The function attributes are returned.
iterator_range< arg_iterator > gc_args() const
range adapter for gc arguments
Definition: Statepoint.h:262
void setCallingConv(CallingConv::ID CC)
Attribute getFnAttribute(Attribute::AttrKind Kind) const
Return the attribute for the given attribute kind.
Definition: Function.h:270
MapVector< BasicBlock *, SetVector< Value * > > LiveOut
Values live out of this basic block (i.e.
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:44
void PromoteMemToReg(ArrayRef< AllocaInst *> Allocas, DominatorTree &DT, AssumptionCache *AC=nullptr)
Promote the specified list of alloca instructions into scalar registers, inserting PHI nodes as appro...
Invoke instruction.
#define DEBUG(X)
Definition: Debug.h:118
unsigned gcArgsStartIdx() const
Definition: Statepoint.h:257
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
inst_range instructions(Function *F)
Definition: InstIterator.h:134
A container for analyses that lazily runs them and caches their results.
const LandingPadInst * getLandingPadInst() const
Return the landingpad instruction associated with the landing pad.
Definition: BasicBlock.cpp:447
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:267
AttributeList getAttributes() const
Get the parameter attributes of the call.
Definition: CallSite.h:329
void sort(Policy policy, RandomAccessIterator Start, RandomAccessIterator End, const Comparator &Comp=Comparator())
Definition: Parallel.h:199
This pass exposes codegen information to IR-level passes.
bool operator==(uint64_t V1, const APInt &V2)
Definition: APInt.h:1946
MapVector< Value *, Value * > PointerToBase
Mapping from live pointers to a base-defining-value.
const TerminatorInst * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:120
void setIncomingValue(unsigned i, Value *V)
static ExtractElementInst * Create(Value *Vec, Value *Idx, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
bool isEmpty() const
Return true if there are no attributes.
Definition: Attributes.h:646
bool use_empty() const
Definition: Value.h:328
LocationClass< Ty > location(Ty &L)
Definition: CommandLine.h:422
static AttributeList get(LLVMContext &C, ArrayRef< std::pair< unsigned, Attribute >> Attrs)
Create an AttributeList with the specified parameters in it.
Definition: Attributes.cpp:870
iterator_range< arg_iterator > args()
Definition: Function.h:621
bool empty() const
empty - Check if the array is empty.
Definition: ArrayRef.h:144
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:44
const BasicBlock * getParent() const
Definition: Instruction.h:67
an instruction to allocate memory on the stack
Definition: Instructions.h:60
static BaseDefiningValueResult findBaseDefiningValue(Value *I)
Helper function for findBasePointer - Will return a value which either a) defines the base pointer fo...
CallInst * CreateCall(Value *Callee, ArrayRef< Value *> Args=None, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:1663
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:946
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:867
user_iterator user_end()
Definition: Value.h:389