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