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