LLVM  16.0.0git
RewriteStatepointsForGC.cpp
Go to the documentation of this file.
1 //===- RewriteStatepointsForGC.cpp - Make GC relocations explicit ---------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // Rewrite call/invoke instructions so as to make potential relocations
10 // performed by the garbage collector explicit in the IR.
11 //
12 //===----------------------------------------------------------------------===//
13 
15 
16 #include "llvm/ADT/ArrayRef.h"
17 #include "llvm/ADT/DenseMap.h"
18 #include "llvm/ADT/DenseSet.h"
19 #include "llvm/ADT/MapVector.h"
20 #include "llvm/ADT/None.h"
21 #include "llvm/ADT/Optional.h"
22 #include "llvm/ADT/STLExtras.h"
23 #include "llvm/ADT/SetVector.h"
24 #include "llvm/ADT/SmallSet.h"
25 #include "llvm/ADT/SmallVector.h"
26 #include "llvm/ADT/StringRef.h"
31 #include "llvm/IR/Argument.h"
32 #include "llvm/IR/Attributes.h"
33 #include "llvm/IR/BasicBlock.h"
34 #include "llvm/IR/CallingConv.h"
35 #include "llvm/IR/Constant.h"
36 #include "llvm/IR/Constants.h"
37 #include "llvm/IR/DataLayout.h"
38 #include "llvm/IR/DerivedTypes.h"
39 #include "llvm/IR/Dominators.h"
40 #include "llvm/IR/Function.h"
41 #include "llvm/IR/IRBuilder.h"
42 #include "llvm/IR/InstIterator.h"
43 #include "llvm/IR/InstrTypes.h"
44 #include "llvm/IR/Instruction.h"
45 #include "llvm/IR/Instructions.h"
46 #include "llvm/IR/IntrinsicInst.h"
47 #include "llvm/IR/Intrinsics.h"
48 #include "llvm/IR/LLVMContext.h"
49 #include "llvm/IR/MDBuilder.h"
50 #include "llvm/IR/Metadata.h"
51 #include "llvm/IR/Module.h"
52 #include "llvm/IR/Statepoint.h"
53 #include "llvm/IR/Type.h"
54 #include "llvm/IR/User.h"
55 #include "llvm/IR/Value.h"
56 #include "llvm/IR/ValueHandle.h"
57 #include "llvm/InitializePasses.h"
58 #include "llvm/Pass.h"
59 #include "llvm/Support/Casting.h"
61 #include "llvm/Support/Compiler.h"
62 #include "llvm/Support/Debug.h"
65 #include "llvm/Transforms/Scalar.h"
69 #include <algorithm>
70 #include <cassert>
71 #include <cstddef>
72 #include <cstdint>
73 #include <iterator>
74 #include <set>
75 #include <string>
76 #include <utility>
77 #include <vector>
78 
79 #define DEBUG_TYPE "rewrite-statepoints-for-gc"
80 
81 using namespace llvm;
82 
83 // Print the liveset found at the insert location
84 static cl::opt<bool> PrintLiveSet("spp-print-liveset", cl::Hidden,
85  cl::init(false));
86 static cl::opt<bool> PrintLiveSetSize("spp-print-liveset-size", cl::Hidden,
87  cl::init(false));
88 
89 // Print out the base pointers for debugging
90 static cl::opt<bool> PrintBasePointers("spp-print-base-pointers", cl::Hidden,
91  cl::init(false));
92 
93 // Cost threshold measuring when it is profitable to rematerialize value instead
94 // of relocating it
95 static cl::opt<unsigned>
96 RematerializationThreshold("spp-rematerialization-threshold", cl::Hidden,
97  cl::init(6));
98 
99 #ifdef EXPENSIVE_CHECKS
100 static bool ClobberNonLive = true;
101 #else
102 static bool ClobberNonLive = false;
103 #endif
104 
105 static cl::opt<bool, true> ClobberNonLiveOverride("rs4gc-clobber-non-live",
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  for (Function &F : M) {
177  // Nothing to do for declarations.
178  if (F.isDeclaration() || F.empty())
179  continue;
180 
181  // Policy choice says not to rewrite - the most common reason is that
182  // we're compiling code without a GCStrategy.
184  continue;
185 
187  getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
188  const TargetLibraryInfo &TLI =
189  getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(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,
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
266 
268  /// The set of values known to be live across this safepoint
270 
271  /// The *new* gc.statepoint instruction itself. This produces the token
272  /// that normal path gc.relocates and the gc.result are tied to.
274 
275  /// Instruction to which exceptional gc relocates are attached
276  /// Makes it easier to iterate through them during relocationViaAlloca.
278 
279  /// Record live values we are rematerialized instead of relocating.
280  /// They are not included into 'LiveSet' field.
281  /// Maps rematerialized copy to it's original value.
283 };
284 
286  // Chain from derived pointer to base.
288  // Original base.
290  // Cost of chain.
292 };
294 
295 } // end anonymous namespace
296 
298  Optional<OperandBundleUse> DeoptBundle =
299  Call->getOperandBundle(LLVMContext::OB_deopt);
300 
301  if (!DeoptBundle) {
303  "Found non-leaf call without deopt info!");
304  return None;
305  }
306 
307  return DeoptBundle->Inputs;
308 }
309 
310 /// Compute the live-in set for every basic block in the function
311 static void computeLiveInValues(DominatorTree &DT, Function &F,
312  GCPtrLivenessData &Data);
313 
314 /// Given results from the dataflow liveness computation, find the set of live
315 /// Values at a particular instruction.
316 static void findLiveSetAtInst(Instruction *inst, GCPtrLivenessData &Data,
317  StatepointLiveSetTy &out);
318 
319 // TODO: Once we can get to the GCStrategy, this becomes
320 // Optional<bool> isGCManagedPointer(const Type *Ty) const override {
321 
322 static bool isGCPointerType(Type *T) {
323  if (auto *PT = dyn_cast<PointerType>(T))
324  // For the sake of this example GC, we arbitrarily pick addrspace(1) as our
325  // GC managed heap. We know that a pointer into this heap needs to be
326  // updated and that no other pointer does.
327  return PT->getAddressSpace() == 1;
328  return false;
329 }
330 
331 // Return true if this type is one which a) is a gc pointer or contains a GC
332 // pointer and b) is of a type this code expects to encounter as a live value.
333 // (The insertion code will assert that a type which matches (a) and not (b)
334 // is not encountered.)
336  // We fully support gc pointers
337  if (isGCPointerType(T))
338  return true;
339  // We partially support vectors of gc pointers. The code will assert if it
340  // can't handle something.
341  if (auto VT = dyn_cast<VectorType>(T))
342  if (isGCPointerType(VT->getElementType()))
343  return true;
344  return false;
345 }
346 
347 #ifndef NDEBUG
348 /// Returns true if this type contains a gc pointer whether we know how to
349 /// handle that type or not.
350 static bool containsGCPtrType(Type *Ty) {
351  if (isGCPointerType(Ty))
352  return true;
353  if (VectorType *VT = dyn_cast<VectorType>(Ty))
354  return isGCPointerType(VT->getScalarType());
355  if (ArrayType *AT = dyn_cast<ArrayType>(Ty))
356  return containsGCPtrType(AT->getElementType());
357  if (StructType *ST = dyn_cast<StructType>(Ty))
358  return llvm::any_of(ST->elements(), containsGCPtrType);
359  return false;
360 }
361 
362 // Returns true if this is a type which a) is a gc pointer or contains a GC
363 // pointer and b) is of a type which the code doesn't expect (i.e. first class
364 // aggregates). Used to trip assertions.
365 static bool isUnhandledGCPointerType(Type *Ty) {
366  return containsGCPtrType(Ty) && !isHandledGCPointerType(Ty);
367 }
368 #endif
369 
370 // Return the name of the value suffixed with the provided value, or if the
371 // value didn't have a name, the default value specified.
372 static std::string suffixed_name_or(Value *V, StringRef Suffix,
373  StringRef DefaultName) {
374  return V->hasName() ? (V->getName() + Suffix).str() : DefaultName.str();
375 }
376 
377 // Conservatively identifies any definitions which might be live at the
378 // given instruction. The analysis is performed immediately before the
379 // given instruction. Values defined by that instruction are not considered
380 // live. Values used by that instruction are considered live.
382  DominatorTree &DT, GCPtrLivenessData &OriginalLivenessData, CallBase *Call,
383  PartiallyConstructedSafepointRecord &Result) {
384  StatepointLiveSetTy LiveSet;
385  findLiveSetAtInst(Call, OriginalLivenessData, LiveSet);
386 
387  if (PrintLiveSet) {
388  dbgs() << "Live Variables:\n";
389  for (Value *V : LiveSet)
390  dbgs() << " " << V->getName() << " " << *V << "\n";
391  }
392  if (PrintLiveSetSize) {
393  dbgs() << "Safepoint For: " << Call->getCalledOperand()->getName() << "\n";
394  dbgs() << "Number live values: " << LiveSet.size() << "\n";
395  }
396  Result.LiveSet = LiveSet;
397 }
398 
399 /// Returns true if V is a known base.
400 static bool isKnownBase(Value *V, const IsKnownBaseMapTy &KnownBases);
401 
402 /// Caches the IsKnownBase flag for a value and asserts that it wasn't present
403 /// in the cache before.
404 static void setKnownBase(Value *V, bool IsKnownBase,
405  IsKnownBaseMapTy &KnownBases);
406 
408  IsKnownBaseMapTy &KnownBases);
409 
410 /// Return a base defining value for the 'Index' element of the given vector
411 /// instruction 'I'. If Index is null, returns a BDV for the entire vector
412 /// 'I'. As an optimization, this method will try to determine when the
413 /// element is known to already be a base pointer. If this can be established,
414 /// the second value in the returned pair will be true. Note that either a
415 /// vector or a pointer typed value can be returned. For the former, the
416 /// vector returned is a BDV (and possibly a base) of the entire vector 'I'.
417 /// If the later, the return pointer is a BDV (or possibly a base) for the
418 /// particular element in 'I'.
420  IsKnownBaseMapTy &KnownBases) {
421  // Each case parallels findBaseDefiningValue below, see that code for
422  // detailed motivation.
423 
424  auto Cached = Cache.find(I);
425  if (Cached != Cache.end())
426  return Cached->second;
427 
428  if (isa<Argument>(I)) {
429  // An incoming argument to the function is a base pointer
430  Cache[I] = I;
431  setKnownBase(I, /* IsKnownBase */true, KnownBases);
432  return I;
433  }
434 
435  if (isa<Constant>(I)) {
436  // Base of constant vector consists only of constant null pointers.
437  // For reasoning see similar case inside 'findBaseDefiningValue' function.
438  auto *CAZ = ConstantAggregateZero::get(I->getType());
439  Cache[I] = CAZ;
440  setKnownBase(CAZ, /* IsKnownBase */true, KnownBases);
441  return CAZ;
442  }
443 
444  if (isa<LoadInst>(I)) {
445  Cache[I] = I;
446  setKnownBase(I, /* IsKnownBase */true, KnownBases);
447  return I;
448  }
449 
450  if (isa<InsertElementInst>(I)) {
451  // We don't know whether this vector contains entirely base pointers or
452  // not. To be conservatively correct, we treat it as a BDV and will
453  // duplicate code as needed to construct a parallel vector of bases.
454  Cache[I] = I;
455  setKnownBase(I, /* IsKnownBase */false, KnownBases);
456  return I;
457  }
458 
459  if (isa<ShuffleVectorInst>(I)) {
460  // We don't know whether this vector contains entirely base pointers or
461  // not. To be conservatively correct, we treat it as a BDV and will
462  // duplicate code as needed to construct a parallel vector of bases.
463  // TODO: There a number of local optimizations which could be applied here
464  // for particular sufflevector patterns.
465  Cache[I] = I;
466  setKnownBase(I, /* IsKnownBase */false, KnownBases);
467  return I;
468  }
469 
470  // The behavior of getelementptr instructions is the same for vector and
471  // non-vector data types.
472  if (auto *GEP = dyn_cast<GetElementPtrInst>(I)) {
473  auto *BDV =
474  findBaseDefiningValue(GEP->getPointerOperand(), Cache, KnownBases);
475  Cache[GEP] = BDV;
476  return BDV;
477  }
478 
479  // The behavior of freeze instructions is the same for vector and
480  // non-vector data types.
481  if (auto *Freeze = dyn_cast<FreezeInst>(I)) {
482  auto *BDV = findBaseDefiningValue(Freeze->getOperand(0), Cache, KnownBases);
483  Cache[Freeze] = BDV;
484  return BDV;
485  }
486 
487  // If the pointer comes through a bitcast of a vector of pointers to
488  // a vector of another type of pointer, then look through the bitcast
489  if (auto *BC = dyn_cast<BitCastInst>(I)) {
490  auto *BDV = findBaseDefiningValue(BC->getOperand(0), Cache, KnownBases);
491  Cache[BC] = BDV;
492  return BDV;
493  }
494 
495  // We assume that functions in the source language only return base
496  // pointers. This should probably be generalized via attributes to support
497  // both source language and internal functions.
498  if (isa<CallInst>(I) || isa<InvokeInst>(I)) {
499  Cache[I] = I;
500  setKnownBase(I, /* IsKnownBase */true, KnownBases);
501  return I;
502  }
503 
504  // A PHI or Select is a base defining value. The outer findBasePointer
505  // algorithm is responsible for constructing a base value for this BDV.
506  assert((isa<SelectInst>(I) || isa<PHINode>(I)) &&
507  "unknown vector instruction - no base found for vector element");
508  Cache[I] = I;
509  setKnownBase(I, /* IsKnownBase */false, KnownBases);
510  return I;
511 }
512 
513 /// Helper function for findBasePointer - Will return a value which either a)
514 /// defines the base pointer for the input, b) blocks the simple search
515 /// (i.e. a PHI or Select of two derived pointers), or c) involves a change
516 /// from pointer to vector type or back.
518  IsKnownBaseMapTy &KnownBases) {
519  assert(I->getType()->isPtrOrPtrVectorTy() &&
520  "Illegal to ask for the base pointer of a non-pointer type");
521  auto Cached = Cache.find(I);
522  if (Cached != Cache.end())
523  return Cached->second;
524 
525  if (I->getType()->isVectorTy())
526  return findBaseDefiningValueOfVector(I, Cache, KnownBases);
527 
528  if (isa<Argument>(I)) {
529  // An incoming argument to the function is a base pointer
530  // We should have never reached here if this argument isn't an gc value
531  Cache[I] = I;
532  setKnownBase(I, /* IsKnownBase */true, KnownBases);
533  return I;
534  }
535 
536  if (isa<Constant>(I)) {
537  // We assume that objects with a constant base (e.g. a global) can't move
538  // and don't need to be reported to the collector because they are always
539  // live. Besides global references, all kinds of constants (e.g. undef,
540  // constant expressions, null pointers) can be introduced by the inliner or
541  // the optimizer, especially on dynamically dead paths.
542  // Here we treat all of them as having single null base. By doing this we
543  // trying to avoid problems reporting various conflicts in a form of
544  // "phi (const1, const2)" or "phi (const, regular gc ptr)".
545  // See constant.ll file for relevant test cases.
546 
547  auto *CPN = ConstantPointerNull::get(cast<PointerType>(I->getType()));
548  Cache[I] = CPN;
549  setKnownBase(CPN, /* IsKnownBase */true, KnownBases);
550  return CPN;
551  }
552 
553  // inttoptrs in an integral address space are currently ill-defined. We
554  // treat them as defining base pointers here for consistency with the
555  // constant rule above and because we don't really have a better semantic
556  // to give them. Note that the optimizer is always free to insert undefined
557  // behavior on dynamically dead paths as well.
558  if (isa<IntToPtrInst>(I)) {
559  Cache[I] = I;
560  setKnownBase(I, /* IsKnownBase */true, KnownBases);
561  return I;
562  }
563 
564  if (CastInst *CI = dyn_cast<CastInst>(I)) {
565  Value *Def = CI->stripPointerCasts();
566  // If stripping pointer casts changes the address space there is an
567  // addrspacecast in between.
568  assert(cast<PointerType>(Def->getType())->getAddressSpace() ==
569  cast<PointerType>(CI->getType())->getAddressSpace() &&
570  "unsupported addrspacecast");
571  // If we find a cast instruction here, it means we've found a cast which is
572  // not simply a pointer cast (i.e. an inttoptr). We don't know how to
573  // handle int->ptr conversion.
574  assert(!isa<CastInst>(Def) && "shouldn't find another cast here");
575  auto *BDV = findBaseDefiningValue(Def, Cache, KnownBases);
576  Cache[CI] = BDV;
577  return BDV;
578  }
579 
580  if (isa<LoadInst>(I)) {
581  // The value loaded is an gc base itself
582  Cache[I] = I;
583  setKnownBase(I, /* IsKnownBase */true, KnownBases);
584  return I;
585  }
586 
587  if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(I)) {
588  // The base of this GEP is the base
589  auto *BDV =
590  findBaseDefiningValue(GEP->getPointerOperand(), Cache, KnownBases);
591  Cache[GEP] = BDV;
592  return BDV;
593  }
594 
595  if (auto *Freeze = dyn_cast<FreezeInst>(I)) {
596  auto *BDV = findBaseDefiningValue(Freeze->getOperand(0), Cache, KnownBases);
597  Cache[Freeze] = BDV;
598  return BDV;
599  }
600 
601  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
602  switch (II->getIntrinsicID()) {
603  default:
604  // fall through to general call handling
605  break;
606  case Intrinsic::experimental_gc_statepoint:
607  llvm_unreachable("statepoints don't produce pointers");
608  case Intrinsic::experimental_gc_relocate:
609  // Rerunning safepoint insertion after safepoints are already
610  // inserted is not supported. It could probably be made to work,
611  // but why are you doing this? There's no good reason.
612  llvm_unreachable("repeat safepoint insertion is not supported");
613  case Intrinsic::gcroot:
614  // Currently, this mechanism hasn't been extended to work with gcroot.
615  // There's no reason it couldn't be, but I haven't thought about the
616  // implications much.
618  "interaction with the gcroot mechanism is not supported");
619  case Intrinsic::experimental_gc_get_pointer_base:
620  auto *BDV = findBaseDefiningValue(II->getOperand(0), Cache, KnownBases);
621  Cache[II] = BDV;
622  return BDV;
623  }
624  }
625  // We assume that functions in the source language only return base
626  // pointers. This should probably be generalized via attributes to support
627  // both source language and internal functions.
628  if (isa<CallInst>(I) || isa<InvokeInst>(I)) {
629  Cache[I] = I;
630  setKnownBase(I, /* IsKnownBase */true, KnownBases);
631  return I;
632  }
633 
634  // TODO: I have absolutely no idea how to implement this part yet. It's not
635  // necessarily hard, I just haven't really looked at it yet.
636  assert(!isa<LandingPadInst>(I) && "Landing Pad is unimplemented");
637 
638  if (isa<AtomicCmpXchgInst>(I)) {
639  // A CAS is effectively a atomic store and load combined under a
640  // predicate. From the perspective of base pointers, we just treat it
641  // like a load.
642  Cache[I] = I;
643  setKnownBase(I, /* IsKnownBase */true, KnownBases);
644  return I;
645  }
646 
647  assert(!isa<AtomicRMWInst>(I) && "Xchg handled above, all others are "
648  "binary ops which don't apply to pointers");
649 
650  // The aggregate ops. Aggregates can either be in the heap or on the
651  // stack, but in either case, this is simply a field load. As a result,
652  // this is a defining definition of the base just like a load is.
653  if (isa<ExtractValueInst>(I)) {
654  Cache[I] = I;
655  setKnownBase(I, /* IsKnownBase */true, KnownBases);
656  return I;
657  }
658 
659  // We should never see an insert vector since that would require we be
660  // tracing back a struct value not a pointer value.
661  assert(!isa<InsertValueInst>(I) &&
662  "Base pointer for a struct is meaningless");
663 
664  // This value might have been generated by findBasePointer() called when
665  // substituting gc.get.pointer.base() intrinsic.
666  bool IsKnownBase =
667  isa<Instruction>(I) && cast<Instruction>(I)->getMetadata("is_base_value");
668  setKnownBase(I, /* IsKnownBase */IsKnownBase, KnownBases);
669  Cache[I] = I;
670 
671  // An extractelement produces a base result exactly when it's input does.
672  // We may need to insert a parallel instruction to extract the appropriate
673  // element out of the base vector corresponding to the input. Given this,
674  // it's analogous to the phi and select case even though it's not a merge.
675  if (isa<ExtractElementInst>(I))
676  // Note: There a lot of obvious peephole cases here. This are deliberately
677  // handled after the main base pointer inference algorithm to make writing
678  // test cases to exercise that code easier.
679  return I;
680 
681  // The last two cases here don't return a base pointer. Instead, they
682  // return a value which dynamically selects from among several base
683  // derived pointers (each with it's own base potentially). It's the job of
684  // the caller to resolve these.
685  assert((isa<SelectInst>(I) || isa<PHINode>(I)) &&
686  "missing instruction case in findBaseDefiningValue");
687  return I;
688 }
689 
690 /// Returns the base defining value for this value.
692  IsKnownBaseMapTy &KnownBases) {
693  if (Cache.find(I) == Cache.end()) {
694  auto *BDV = findBaseDefiningValue(I, Cache, KnownBases);
695  Cache[I] = BDV;
696  LLVM_DEBUG(dbgs() << "fBDV-cached: " << I->getName() << " -> "
697  << Cache[I]->getName() << ", is known base = "
698  << KnownBases[I] << "\n");
699  }
700  assert(Cache[I] != nullptr);
701  assert(KnownBases.find(Cache[I]) != KnownBases.end() &&
702  "Cached value must be present in known bases map");
703  return Cache[I];
704 }
705 
706 /// Return a base pointer for this value if known. Otherwise, return it's
707 /// base defining value.
709  IsKnownBaseMapTy &KnownBases) {
710  Value *Def = findBaseDefiningValueCached(I, Cache, KnownBases);
711  auto Found = Cache.find(Def);
712  if (Found != Cache.end()) {
713  // Either a base-of relation, or a self reference. Caller must check.
714  return Found->second;
715  }
716  // Only a BDV available
717  return Def;
718 }
719 
720 #ifndef NDEBUG
721 /// This value is a base pointer that is not generated by RS4GC, i.e. it already
722 /// exists in the code.
723 static bool isOriginalBaseResult(Value *V) {
724  // no recursion possible
725  return !isa<PHINode>(V) && !isa<SelectInst>(V) &&
726  !isa<ExtractElementInst>(V) && !isa<InsertElementInst>(V) &&
727  !isa<ShuffleVectorInst>(V);
728 }
729 #endif
730 
731 static bool isKnownBase(Value *V, const IsKnownBaseMapTy &KnownBases) {
732  auto It = KnownBases.find(V);
733  assert(It != KnownBases.end() && "Value not present in the map");
734  return It->second;
735 }
736 
737 static void setKnownBase(Value *V, bool IsKnownBase,
738  IsKnownBaseMapTy &KnownBases) {
739 #ifndef NDEBUG
740  auto It = KnownBases.find(V);
741  if (It != KnownBases.end())
742  assert(It->second == IsKnownBase && "Changing already present value");
743 #endif
744  KnownBases[V] = IsKnownBase;
745 }
746 
747 // Returns true if First and Second values are both scalar or both vector.
748 static bool areBothVectorOrScalar(Value *First, Value *Second) {
749  return isa<VectorType>(First->getType()) ==
750  isa<VectorType>(Second->getType());
751 }
752 
753 namespace {
754 
755 /// Models the state of a single base defining value in the findBasePointer
756 /// algorithm for determining where a new instruction is needed to propagate
757 /// the base of this BDV.
758 class BDVState {
759 public:
760  enum StatusTy {
761  // Starting state of lattice
762  Unknown,
763  // Some specific base value -- does *not* mean that instruction
764  // propagates the base of the object
765  // ex: gep %arg, 16 -> %arg is the base value
766  Base,
767  // Need to insert a node to represent a merge.
768  Conflict
769  };
770 
771  BDVState() {
772  llvm_unreachable("missing state in map");
773  }
774 
775  explicit BDVState(Value *OriginalValue)
776  : OriginalValue(OriginalValue) {}
777  explicit BDVState(Value *OriginalValue, StatusTy Status, Value *BaseValue = nullptr)
778  : OriginalValue(OriginalValue), Status(Status), BaseValue(BaseValue) {
779  assert(Status != Base || BaseValue);
780  }
781 
782  StatusTy getStatus() const { return Status; }
783  Value *getOriginalValue() const { return OriginalValue; }
784  Value *getBaseValue() const { return BaseValue; }
785 
786  bool isBase() const { return getStatus() == Base; }
787  bool isUnknown() const { return getStatus() == Unknown; }
788  bool isConflict() const { return getStatus() == Conflict; }
789 
790  // Values of type BDVState form a lattice, and this function implements the
791  // meet
792  // operation.
793  void meet(const BDVState &Other) {
794  auto markConflict = [&]() {
795  Status = BDVState::Conflict;
796  BaseValue = nullptr;
797  };
798  // Conflict is a final state.
799  if (isConflict())
800  return;
801  // if we are not known - just take other state.
802  if (isUnknown()) {
803  Status = Other.getStatus();
804  BaseValue = Other.getBaseValue();
805  return;
806  }
807  // We are base.
808  assert(isBase() && "Unknown state");
809  // If other is unknown - just keep our state.
810  if (Other.isUnknown())
811  return;
812  // If other is conflict - it is a final state.
813  if (Other.isConflict())
814  return markConflict();
815  // Other is base as well.
816  assert(Other.isBase() && "Unknown state");
817  // If bases are different - Conflict.
818  if (getBaseValue() != Other.getBaseValue())
819  return markConflict();
820  // We are identical, do nothing.
821  }
822 
823  bool operator==(const BDVState &Other) const {
824  return OriginalValue == Other.OriginalValue && BaseValue == Other.BaseValue &&
825  Status == Other.Status;
826  }
827 
828  bool operator!=(const BDVState &other) const { return !(*this == other); }
829 
831  void dump() const {
832  print(dbgs());
833  dbgs() << '\n';
834  }
835 
836  void print(raw_ostream &OS) const {
837  switch (getStatus()) {
838  case Unknown:
839  OS << "U";
840  break;
841  case Base:
842  OS << "B";
843  break;
844  case Conflict:
845  OS << "C";
846  break;
847  }
848  OS << " (base " << getBaseValue() << " - "
849  << (getBaseValue() ? getBaseValue()->getName() : "nullptr") << ")"
850  << " for " << OriginalValue->getName() << ":";
851  }
852 
853 private:
854  AssertingVH<Value> OriginalValue; // instruction this state corresponds to
855  StatusTy Status = Unknown;
856  AssertingVH<Value> BaseValue = nullptr; // Non-null only if Status == Base.
857 };
858 
859 } // end anonymous namespace
860 
861 #ifndef NDEBUG
862 static raw_ostream &operator<<(raw_ostream &OS, const BDVState &State) {
863  State.print(OS);
864  return OS;
865 }
866 #endif
867 
868 /// For a given value or instruction, figure out what base ptr its derived from.
869 /// For gc objects, this is simply itself. On success, returns a value which is
870 /// the base pointer. (This is reliable and can be used for relocation.) On
871 /// failure, returns nullptr.
873  IsKnownBaseMapTy &KnownBases) {
874  Value *Def = findBaseOrBDV(I, Cache, KnownBases);
875 
876  if (isKnownBase(Def, KnownBases) && areBothVectorOrScalar(Def, I))
877  return Def;
878 
879  // Here's the rough algorithm:
880  // - For every SSA value, construct a mapping to either an actual base
881  // pointer or a PHI which obscures the base pointer.
882  // - Construct a mapping from PHI to unknown TOP state. Use an
883  // optimistic algorithm to propagate base pointer information. Lattice
884  // looks like:
885  // UNKNOWN
886  // b1 b2 b3 b4
887  // CONFLICT
888  // When algorithm terminates, all PHIs will either have a single concrete
889  // base or be in a conflict state.
890  // - For every conflict, insert a dummy PHI node without arguments. Add
891  // these to the base[Instruction] = BasePtr mapping. For every
892  // non-conflict, add the actual base.
893  // - For every conflict, add arguments for the base[a] of each input
894  // arguments.
895  //
896  // Note: A simpler form of this would be to add the conflict form of all
897  // PHIs without running the optimistic algorithm. This would be
898  // analogous to pessimistic data flow and would likely lead to an
899  // overall worse solution.
900 
901 #ifndef NDEBUG
902  auto isExpectedBDVType = [](Value *BDV) {
903  return isa<PHINode>(BDV) || isa<SelectInst>(BDV) ||
904  isa<ExtractElementInst>(BDV) || isa<InsertElementInst>(BDV) ||
905  isa<ShuffleVectorInst>(BDV);
906  };
907 #endif
908 
909  // Once populated, will contain a mapping from each potentially non-base BDV
910  // to a lattice value (described above) which corresponds to that BDV.
911  // We use the order of insertion (DFS over the def/use graph) to provide a
912  // stable deterministic ordering for visiting DenseMaps (which are unordered)
913  // below. This is important for deterministic compilation.
915 
916 #ifndef NDEBUG
917  auto VerifyStates = [&]() {
918  for (auto &Entry : States) {
919  assert(Entry.first == Entry.second.getOriginalValue());
920  }
921  };
922 #endif
923 
924  auto visitBDVOperands = [](Value *BDV, std::function<void (Value*)> F) {
925  if (PHINode *PN = dyn_cast<PHINode>(BDV)) {
926  for (Value *InVal : PN->incoming_values())
927  F(InVal);
928  } else if (SelectInst *SI = dyn_cast<SelectInst>(BDV)) {
929  F(SI->getTrueValue());
930  F(SI->getFalseValue());
931  } else if (auto *EE = dyn_cast<ExtractElementInst>(BDV)) {
932  F(EE->getVectorOperand());
933  } else if (auto *IE = dyn_cast<InsertElementInst>(BDV)) {
934  F(IE->getOperand(0));
935  F(IE->getOperand(1));
936  } else if (auto *SV = dyn_cast<ShuffleVectorInst>(BDV)) {
937  // For a canonical broadcast, ignore the undef argument
938  // (without this, we insert a parallel base shuffle for every broadcast)
939  F(SV->getOperand(0));
940  if (!SV->isZeroEltSplat())
941  F(SV->getOperand(1));
942  } else {
943  llvm_unreachable("unexpected BDV type");
944  }
945  };
946 
947 
948  // Recursively fill in all base defining values reachable from the initial
949  // one for which we don't already know a definite base value for
950  /* scope */ {
951  SmallVector<Value*, 16> Worklist;
952  Worklist.push_back(Def);
953  States.insert({Def, BDVState(Def)});
954  while (!Worklist.empty()) {
955  Value *Current = Worklist.pop_back_val();
956  assert(!isOriginalBaseResult(Current) && "why did it get added?");
957 
958  auto visitIncomingValue = [&](Value *InVal) {
959  Value *Base = findBaseOrBDV(InVal, Cache, KnownBases);
960  if (isKnownBase(Base, KnownBases) && areBothVectorOrScalar(Base, InVal))
961  // Known bases won't need new instructions introduced and can be
962  // ignored safely. However, this can only be done when InVal and Base
963  // are both scalar or both vector. Otherwise, we need to find a
964  // correct BDV for InVal, by creating an entry in the lattice
965  // (States).
966  return;
967  assert(isExpectedBDVType(Base) && "the only non-base values "
968  "we see should be base defining values");
969  if (States.insert(std::make_pair(Base, BDVState(Base))).second)
970  Worklist.push_back(Base);
971  };
972 
973  visitBDVOperands(Current, visitIncomingValue);
974  }
975  }
976 
977 #ifndef NDEBUG
978  VerifyStates();
979  LLVM_DEBUG(dbgs() << "States after initialization:\n");
980  for (const auto &Pair : States) {
981  LLVM_DEBUG(dbgs() << " " << Pair.second << " for " << *Pair.first << "\n");
982  }
983 #endif
984 
985  // Iterate forward through the value graph pruning any node from the state
986  // list where all of the inputs are base pointers. The purpose of this is to
987  // reuse existing values when the derived pointer we were asked to materialize
988  // a base pointer for happens to be a base pointer itself. (Or a sub-graph
989  // feeding it does.)
991  do {
992  ToRemove.clear();
993  for (auto Pair : States) {
994  Value *BDV = Pair.first;
995  auto canPruneInput = [&](Value *V) {
996  // If the input of the BDV is the BDV itself we can prune it. This is
997  // only possible if the BDV is a PHI node.
998  if (V->stripPointerCasts() == BDV)
999  return true;
1000  Value *VBDV = findBaseOrBDV(V, Cache, KnownBases);
1001  if (V->stripPointerCasts() != VBDV)
1002  return false;
1003  // The assumption is that anything not in the state list is
1004  // propagates a base pointer.
1005  return States.count(VBDV) == 0;
1006  };
1007 
1008  bool CanPrune = true;
1009  visitBDVOperands(BDV, [&](Value *Op) {
1010  CanPrune = CanPrune && canPruneInput(Op);
1011  });
1012  if (CanPrune)
1013  ToRemove.push_back(BDV);
1014  }
1015  for (Value *V : ToRemove) {
1016  States.erase(V);
1017  // Cache the fact V is it's own base for later usage.
1018  Cache[V] = V;
1019  }
1020  } while (!ToRemove.empty());
1021 
1022  // Did we manage to prove that Def itself must be a base pointer?
1023  if (!States.count(Def))
1024  return Def;
1025 
1026  // Return a phi state for a base defining value. We'll generate a new
1027  // base state for known bases and expect to find a cached state otherwise.
1028  auto GetStateForBDV = [&](Value *BaseValue, Value *Input) {
1029  auto I = States.find(BaseValue);
1030  if (I != States.end())
1031  return I->second;
1032  assert(areBothVectorOrScalar(BaseValue, Input));
1033  return BDVState(BaseValue, BDVState::Base, BaseValue);
1034  };
1035 
1036  bool Progress = true;
1037  while (Progress) {
1038 #ifndef NDEBUG
1039  const size_t OldSize = States.size();
1040 #endif
1041  Progress = false;
1042  // We're only changing values in this loop, thus safe to keep iterators.
1043  // Since this is computing a fixed point, the order of visit does not
1044  // effect the result. TODO: We could use a worklist here and make this run
1045  // much faster.
1046  for (auto Pair : States) {
1047  Value *BDV = Pair.first;
1048  // Only values that do not have known bases or those that have differing
1049  // type (scalar versus vector) from a possible known base should be in the
1050  // lattice.
1051  assert((!isKnownBase(BDV, KnownBases) ||
1052  !areBothVectorOrScalar(BDV, Pair.second.getBaseValue())) &&
1053  "why did it get added?");
1054 
1055  BDVState NewState(BDV);
1056  visitBDVOperands(BDV, [&](Value *Op) {
1057  Value *BDV = findBaseOrBDV(Op, Cache, KnownBases);
1058  auto OpState = GetStateForBDV(BDV, Op);
1059  NewState.meet(OpState);
1060  });
1061 
1062  BDVState OldState = States[BDV];
1063  if (OldState != NewState) {
1064  Progress = true;
1065  States[BDV] = NewState;
1066  }
1067  }
1068 
1069  assert(OldSize == States.size() &&
1070  "fixed point shouldn't be adding any new nodes to state");
1071  }
1072 
1073 #ifndef NDEBUG
1074  VerifyStates();
1075  LLVM_DEBUG(dbgs() << "States after meet iteration:\n");
1076  for (const auto &Pair : States) {
1077  LLVM_DEBUG(dbgs() << " " << Pair.second << " for " << *Pair.first << "\n");
1078  }
1079 #endif
1080 
1081  // Handle all instructions that have a vector BDV, but the instruction itself
1082  // is of scalar type.
1083  for (auto Pair : States) {
1084  Instruction *I = cast<Instruction>(Pair.first);
1085  BDVState State = Pair.second;
1086  auto *BaseValue = State.getBaseValue();
1087  // Only values that do not have known bases or those that have differing
1088  // type (scalar versus vector) from a possible known base should be in the
1089  // lattice.
1090  assert(
1091  (!isKnownBase(I, KnownBases) || !areBothVectorOrScalar(I, BaseValue)) &&
1092  "why did it get added?");
1093  assert(!State.isUnknown() && "Optimistic algorithm didn't complete!");
1094 
1095  if (!State.isBase() || !isa<VectorType>(BaseValue->getType()))
1096  continue;
1097  // extractelement instructions are a bit special in that we may need to
1098  // insert an extract even when we know an exact base for the instruction.
1099  // The problem is that we need to convert from a vector base to a scalar
1100  // base for the particular indice we're interested in.
1101  if (isa<ExtractElementInst>(I)) {
1102  auto *EE = cast<ExtractElementInst>(I);
1103  // TODO: In many cases, the new instruction is just EE itself. We should
1104  // exploit this, but can't do it here since it would break the invariant
1105  // about the BDV not being known to be a base.
1106  auto *BaseInst = ExtractElementInst::Create(
1107  State.getBaseValue(), EE->getIndexOperand(), "base_ee", EE);
1108  BaseInst->setMetadata("is_base_value", MDNode::get(I->getContext(), {}));
1109  States[I] = BDVState(I, BDVState::Base, BaseInst);
1110  setKnownBase(BaseInst, /* IsKnownBase */true, KnownBases);
1111  } else if (!isa<VectorType>(I->getType())) {
1112  // We need to handle cases that have a vector base but the instruction is
1113  // a scalar type (these could be phis or selects or any instruction that
1114  // are of scalar type, but the base can be a vector type). We
1115  // conservatively set this as conflict. Setting the base value for these
1116  // conflicts is handled in the next loop which traverses States.
1117  States[I] = BDVState(I, BDVState::Conflict);
1118  }
1119  }
1120 
1121 #ifndef NDEBUG
1122  VerifyStates();
1123 #endif
1124 
1125  // Insert Phis for all conflicts
1126  // TODO: adjust naming patterns to avoid this order of iteration dependency
1127  for (auto Pair : States) {
1128  Instruction *I = cast<Instruction>(Pair.first);
1129  BDVState State = Pair.second;
1130  // Only values that do not have known bases or those that have differing
1131  // type (scalar versus vector) from a possible known base should be in the
1132  // lattice.
1133  assert((!isKnownBase(I, KnownBases) ||
1134  !areBothVectorOrScalar(I, State.getBaseValue())) &&
1135  "why did it get added?");
1136  assert(!State.isUnknown() && "Optimistic algorithm didn't complete!");
1137 
1138  // Since we're joining a vector and scalar base, they can never be the
1139  // same. As a result, we should always see insert element having reached
1140  // the conflict state.
1141  assert(!isa<InsertElementInst>(I) || State.isConflict());
1142 
1143  if (!State.isConflict())
1144  continue;
1145 
1146  auto getMangledName = [](Instruction *I) -> std::string {
1147  if (isa<PHINode>(I)) {
1148  return suffixed_name_or(I, ".base", "base_phi");
1149  } else if (isa<SelectInst>(I)) {
1150  return suffixed_name_or(I, ".base", "base_select");
1151  } else if (isa<ExtractElementInst>(I)) {
1152  return suffixed_name_or(I, ".base", "base_ee");
1153  } else if (isa<InsertElementInst>(I)) {
1154  return suffixed_name_or(I, ".base", "base_ie");
1155  } else {
1156  return suffixed_name_or(I, ".base", "base_sv");
1157  }
1158  };
1159 
1160  Instruction *BaseInst = I->clone();
1161  BaseInst->insertBefore(I);
1162  BaseInst->setName(getMangledName(I));
1163  // Add metadata marking this as a base value
1164  BaseInst->setMetadata("is_base_value", MDNode::get(I->getContext(), {}));
1165  States[I] = BDVState(I, BDVState::Conflict, BaseInst);
1166  setKnownBase(BaseInst, /* IsKnownBase */true, KnownBases);
1167  }
1168 
1169 #ifndef NDEBUG
1170  VerifyStates();
1171 #endif
1172 
1173  // Returns a instruction which produces the base pointer for a given
1174  // instruction. The instruction is assumed to be an input to one of the BDVs
1175  // seen in the inference algorithm above. As such, we must either already
1176  // know it's base defining value is a base, or have inserted a new
1177  // instruction to propagate the base of it's BDV and have entered that newly
1178  // introduced instruction into the state table. In either case, we are
1179  // assured to be able to determine an instruction which produces it's base
1180  // pointer.
1181  auto getBaseForInput = [&](Value *Input, Instruction *InsertPt) {
1182  Value *BDV = findBaseOrBDV(Input, Cache, KnownBases);
1183  Value *Base = nullptr;
1184  if (!States.count(BDV)) {
1185  assert(areBothVectorOrScalar(BDV, Input));
1186  Base = BDV;
1187  } else {
1188  // Either conflict or base.
1189  assert(States.count(BDV));
1190  Base = States[BDV].getBaseValue();
1191  }
1192  assert(Base && "Can't be null");
1193  // The cast is needed since base traversal may strip away bitcasts
1194  if (Base->getType() != Input->getType() && InsertPt)
1195  Base = new BitCastInst(Base, Input->getType(), "cast", InsertPt);
1196  return Base;
1197  };
1198 
1199  // Fixup all the inputs of the new PHIs. Visit order needs to be
1200  // deterministic and predictable because we're naming newly created
1201  // instructions.
1202  for (auto Pair : States) {
1203  Instruction *BDV = cast<Instruction>(Pair.first);
1204  BDVState State = Pair.second;
1205 
1206  // Only values that do not have known bases or those that have differing
1207  // type (scalar versus vector) from a possible known base should be in the
1208  // lattice.
1209  assert((!isKnownBase(BDV, KnownBases) ||
1210  !areBothVectorOrScalar(BDV, State.getBaseValue())) &&
1211  "why did it get added?");
1212  assert(!State.isUnknown() && "Optimistic algorithm didn't complete!");
1213  if (!State.isConflict())
1214  continue;
1215 
1216  if (PHINode *BasePHI = dyn_cast<PHINode>(State.getBaseValue())) {
1217  PHINode *PN = cast<PHINode>(BDV);
1218  const unsigned NumPHIValues = PN->getNumIncomingValues();
1219 
1220  // The IR verifier requires phi nodes with multiple entries from the
1221  // same basic block to have the same incoming value for each of those
1222  // entries. Since we're inserting bitcasts in the loop, make sure we
1223  // do so at least once per incoming block.
1224  DenseMap<BasicBlock *, Value*> BlockToValue;
1225  for (unsigned i = 0; i < NumPHIValues; i++) {
1226  Value *InVal = PN->getIncomingValue(i);
1227  BasicBlock *InBB = PN->getIncomingBlock(i);
1228  if (!BlockToValue.count(InBB))
1229  BlockToValue[InBB] = getBaseForInput(InVal, InBB->getTerminator());
1230  else {
1231 #ifndef NDEBUG
1232  Value *OldBase = BlockToValue[InBB];
1233  Value *Base = getBaseForInput(InVal, nullptr);
1234 
1235  // We can't use `stripPointerCasts` instead of this function because
1236  // `stripPointerCasts` doesn't handle vectors of pointers.
1237  auto StripBitCasts = [](Value *V) -> Value * {
1238  while (auto *BC = dyn_cast<BitCastInst>(V))
1239  V = BC->getOperand(0);
1240  return V;
1241  };
1242  // In essence this assert states: the only way two values
1243  // incoming from the same basic block may be different is by
1244  // being different bitcasts of the same value. A cleanup
1245  // that remains TODO is changing findBaseOrBDV to return an
1246  // llvm::Value of the correct type (and still remain pure).
1247  // This will remove the need to add bitcasts.
1248  assert(StripBitCasts(Base) == StripBitCasts(OldBase) &&
1249  "findBaseOrBDV should be pure!");
1250 #endif
1251  }
1252  Value *Base = BlockToValue[InBB];
1253  BasePHI->setIncomingValue(i, Base);
1254  }
1255  } else if (SelectInst *BaseSI =
1256  dyn_cast<SelectInst>(State.getBaseValue())) {
1257  SelectInst *SI = cast<SelectInst>(BDV);
1258 
1259  // Find the instruction which produces the base for each input.
1260  // We may need to insert a bitcast.
1261  BaseSI->setTrueValue(getBaseForInput(SI->getTrueValue(), BaseSI));
1262  BaseSI->setFalseValue(getBaseForInput(SI->getFalseValue(), BaseSI));
1263  } else if (auto *BaseEE =
1264  dyn_cast<ExtractElementInst>(State.getBaseValue())) {
1265  Value *InVal = cast<ExtractElementInst>(BDV)->getVectorOperand();
1266  // Find the instruction which produces the base for each input. We may
1267  // need to insert a bitcast.
1268  BaseEE->setOperand(0, getBaseForInput(InVal, BaseEE));
1269  } else if (auto *BaseIE = dyn_cast<InsertElementInst>(State.getBaseValue())){
1270  auto *BdvIE = cast<InsertElementInst>(BDV);
1271  auto UpdateOperand = [&](int OperandIdx) {
1272  Value *InVal = BdvIE->getOperand(OperandIdx);
1273  Value *Base = getBaseForInput(InVal, BaseIE);
1274  BaseIE->setOperand(OperandIdx, Base);
1275  };
1276  UpdateOperand(0); // vector operand
1277  UpdateOperand(1); // scalar operand
1278  } else {
1279  auto *BaseSV = cast<ShuffleVectorInst>(State.getBaseValue());
1280  auto *BdvSV = cast<ShuffleVectorInst>(BDV);
1281  auto UpdateOperand = [&](int OperandIdx) {
1282  Value *InVal = BdvSV->getOperand(OperandIdx);
1283  Value *Base = getBaseForInput(InVal, BaseSV);
1284  BaseSV->setOperand(OperandIdx, Base);
1285  };
1286  UpdateOperand(0); // vector operand
1287  if (!BdvSV->isZeroEltSplat())
1288  UpdateOperand(1); // vector operand
1289  else {
1290  // Never read, so just use undef
1291  Value *InVal = BdvSV->getOperand(1);
1292  BaseSV->setOperand(1, UndefValue::get(InVal->getType()));
1293  }
1294  }
1295  }
1296 
1297 #ifndef NDEBUG
1298  VerifyStates();
1299 #endif
1300 
1301  // Cache all of our results so we can cheaply reuse them
1302  // NOTE: This is actually two caches: one of the base defining value
1303  // relation and one of the base pointer relation! FIXME
1304  for (auto Pair : States) {
1305  auto *BDV = Pair.first;
1306  Value *Base = Pair.second.getBaseValue();
1307  assert(BDV && Base);
1308  // Only values that do not have known bases or those that have differing
1309  // type (scalar versus vector) from a possible known base should be in the
1310  // lattice.
1311  assert(
1312  (!isKnownBase(BDV, KnownBases) || !areBothVectorOrScalar(BDV, Base)) &&
1313  "why did it get added?");
1314 
1315  LLVM_DEBUG(
1316  dbgs() << "Updating base value cache"
1317  << " for: " << BDV->getName() << " from: "
1318  << (Cache.count(BDV) ? Cache[BDV]->getName().str() : "none")
1319  << " to: " << Base->getName() << "\n");
1320 
1321  Cache[BDV] = Base;
1322  }
1323  assert(Cache.count(Def));
1324  return Cache[Def];
1325 }
1326 
1327 // For a set of live pointers (base and/or derived), identify the base
1328 // pointer of the object which they are derived from. This routine will
1329 // mutate the IR graph as needed to make the 'base' pointer live at the
1330 // definition site of 'derived'. This ensures that any use of 'derived' can
1331 // also use 'base'. This may involve the insertion of a number of
1332 // additional PHI nodes.
1333 //
1334 // preconditions: live is a set of pointer type Values
1335 //
1336 // side effects: may insert PHI nodes into the existing CFG, will preserve
1337 // CFG, will not remove or mutate any existing nodes
1338 //
1339 // post condition: PointerToBase contains one (derived, base) pair for every
1340 // pointer in live. Note that derived can be equal to base if the original
1341 // pointer was a base pointer.
1342 static void findBasePointers(const StatepointLiveSetTy &live,
1343  PointerToBaseTy &PointerToBase, DominatorTree *DT,
1344  DefiningValueMapTy &DVCache,
1345  IsKnownBaseMapTy &KnownBases) {
1346  for (Value *ptr : live) {
1347  Value *base = findBasePointer(ptr, DVCache, KnownBases);
1348  assert(base && "failed to find base pointer");
1349  PointerToBase[ptr] = base;
1350  assert((!isa<Instruction>(base) || !isa<Instruction>(ptr) ||
1351  DT->dominates(cast<Instruction>(base)->getParent(),
1352  cast<Instruction>(ptr)->getParent())) &&
1353  "The base we found better dominate the derived pointer");
1354  }
1355 }
1356 
1357 /// Find the required based pointers (and adjust the live set) for the given
1358 /// parse point.
1360  CallBase *Call,
1361  PartiallyConstructedSafepointRecord &result,
1362  PointerToBaseTy &PointerToBase,
1363  IsKnownBaseMapTy &KnownBases) {
1364  StatepointLiveSetTy PotentiallyDerivedPointers = result.LiveSet;
1365  // We assume that all pointers passed to deopt are base pointers; as an
1366  // optimization, we can use this to avoid seperately materializing the base
1367  // pointer graph. This is only relevant since we're very conservative about
1368  // generating new conflict nodes during base pointer insertion. If we were
1369  // smarter there, this would be irrelevant.
1370  if (auto Opt = Call->getOperandBundle(LLVMContext::OB_deopt))
1371  for (Value *V : Opt->Inputs) {
1372  if (!PotentiallyDerivedPointers.count(V))
1373  continue;
1374  PotentiallyDerivedPointers.remove(V);
1375  PointerToBase[V] = V;
1376  }
1377  findBasePointers(PotentiallyDerivedPointers, PointerToBase, &DT, DVCache,
1378  KnownBases);
1379 }
1380 
1381 /// Given an updated version of the dataflow liveness results, update the
1382 /// liveset and base pointer maps for the call site CS.
1383 static void recomputeLiveInValues(GCPtrLivenessData &RevisedLivenessData,
1384  CallBase *Call,
1385  PartiallyConstructedSafepointRecord &result,
1386  PointerToBaseTy &PointerToBase);
1387 
1389  Function &F, DominatorTree &DT, ArrayRef<CallBase *> toUpdate,
1391  PointerToBaseTy &PointerToBase) {
1392  // TODO-PERF: reuse the original liveness, then simply run the dataflow
1393  // again. The old values are still live and will help it stabilize quickly.
1394  GCPtrLivenessData RevisedLivenessData;
1395  computeLiveInValues(DT, F, RevisedLivenessData);
1396  for (size_t i = 0; i < records.size(); i++) {
1397  struct PartiallyConstructedSafepointRecord &info = records[i];
1398  recomputeLiveInValues(RevisedLivenessData, toUpdate[i], info,
1399  PointerToBase);
1400  }
1401 }
1402 
1403 // When inserting gc.relocate and gc.result calls, we need to ensure there are
1404 // no uses of the original value / return value between the gc.statepoint and
1405 // the gc.relocate / gc.result call. One case which can arise is a phi node
1406 // starting one of the successor blocks. We also need to be able to insert the
1407 // gc.relocates only on the path which goes through the statepoint. We might
1408 // need to split an edge to make this possible.
1409 static BasicBlock *
1411  DominatorTree &DT) {
1412  BasicBlock *Ret = BB;
1413  if (!BB->getUniquePredecessor())
1414  Ret = SplitBlockPredecessors(BB, InvokeParent, "", &DT);
1415 
1416  // Now that 'Ret' has unique predecessor we can safely remove all phi nodes
1417  // from it
1419  assert(!isa<PHINode>(Ret->begin()) &&
1420  "All PHI nodes should have been removed!");
1421 
1422  // At this point, we can safely insert a gc.relocate or gc.result as the first
1423  // instruction in Ret if needed.
1424  return Ret;
1425 }
1426 
1427 // List of all function attributes which must be stripped when lowering from
1428 // abstract machine model to physical machine model. Essentially, these are
1429 // all the effects a safepoint might have which we ignored in the abstract
1430 // machine model for purposes of optimization. We have to strip these on
1431 // both function declarations and call sites.
1433  {Attribute::Memory, Attribute::NoSync, Attribute::NoFree};
1434 
1435 // Create new attribute set containing only attributes which can be transferred
1436 // from original call to the safepoint.
1438  AttributeList OrigAL,
1439  AttributeList StatepointAL) {
1440  if (OrigAL.isEmpty())
1441  return StatepointAL;
1442 
1443  // Remove the readonly, readnone, and statepoint function attributes.
1444  AttrBuilder FnAttrs(Ctx, OrigAL.getFnAttrs());
1445  for (auto Attr : FnAttrsToStrip)
1446  FnAttrs.removeAttribute(Attr);
1447 
1448  for (Attribute A : OrigAL.getFnAttrs()) {
1450  FnAttrs.removeAttribute(A);
1451  }
1452 
1453  // Just skip parameter and return attributes for now
1454  return StatepointAL.addFnAttributes(Ctx, FnAttrs);
1455 }
1456 
1457 /// Helper function to place all gc relocates necessary for the given
1458 /// statepoint.
1459 /// Inputs:
1460 /// liveVariables - list of variables to be relocated.
1461 /// basePtrs - base pointers.
1462 /// statepointToken - statepoint instruction to which relocates should be
1463 /// bound.
1464 /// Builder - Llvm IR builder to be used to construct new calls.
1466  ArrayRef<Value *> BasePtrs,
1467  Instruction *StatepointToken,
1468  IRBuilder<> &Builder) {
1469  if (LiveVariables.empty())
1470  return;
1471 
1472  auto FindIndex = [](ArrayRef<Value *> LiveVec, Value *Val) {
1473  auto ValIt = llvm::find(LiveVec, Val);
1474  assert(ValIt != LiveVec.end() && "Val not found in LiveVec!");
1475  size_t Index = std::distance(LiveVec.begin(), ValIt);
1476  assert(Index < LiveVec.size() && "Bug in std::find?");
1477  return Index;
1478  };
1479  Module *M = StatepointToken->getModule();
1480 
1481  // All gc_relocate are generated as i8 addrspace(1)* (or a vector type whose
1482  // element type is i8 addrspace(1)*). We originally generated unique
1483  // declarations for each pointer type, but this proved problematic because
1484  // the intrinsic mangling code is incomplete and fragile. Since we're moving
1485  // towards a single unified pointer type anyways, we can just cast everything
1486  // to an i8* of the right address space. A bitcast is added later to convert
1487  // gc_relocate to the actual value's type.
1488  auto getGCRelocateDecl = [&] (Type *Ty) {
1490  auto AS = Ty->getScalarType()->getPointerAddressSpace();
1491  Type *NewTy = Type::getInt8PtrTy(M->getContext(), AS);
1492  if (auto *VT = dyn_cast<VectorType>(Ty))
1493  NewTy = FixedVectorType::get(NewTy,
1494  cast<FixedVectorType>(VT)->getNumElements());
1495  return Intrinsic::getDeclaration(M, Intrinsic::experimental_gc_relocate,
1496  {NewTy});
1497  };
1498 
1499  // Lazily populated map from input types to the canonicalized form mentioned
1500  // in the comment above. This should probably be cached somewhere more
1501  // broadly.
1502  DenseMap<Type *, Function *> TypeToDeclMap;
1503 
1504  for (unsigned i = 0; i < LiveVariables.size(); i++) {
1505  // Generate the gc.relocate call and save the result
1506  Value *BaseIdx = Builder.getInt32(FindIndex(LiveVariables, BasePtrs[i]));
1507  Value *LiveIdx = Builder.getInt32(i);
1508 
1509  Type *Ty = LiveVariables[i]->getType();
1510  if (!TypeToDeclMap.count(Ty))
1511  TypeToDeclMap[Ty] = getGCRelocateDecl(Ty);
1512  Function *GCRelocateDecl = TypeToDeclMap[Ty];
1513 
1514  // only specify a debug name if we can give a useful one
1515  CallInst *Reloc = Builder.CreateCall(
1516  GCRelocateDecl, {StatepointToken, BaseIdx, LiveIdx},
1517  suffixed_name_or(LiveVariables[i], ".relocated", ""));
1518  // Trick CodeGen into thinking there are lots of free registers at this
1519  // fake call.
1521  }
1522 }
1523 
1524 namespace {
1525 
1526 /// This struct is used to defer RAUWs and `eraseFromParent` s. Using this
1527 /// avoids having to worry about keeping around dangling pointers to Values.
1528 class DeferredReplacement {
1531  bool IsDeoptimize = false;
1532 
1533  DeferredReplacement() = default;
1534 
1535 public:
1536  static DeferredReplacement createRAUW(Instruction *Old, Instruction *New) {
1537  assert(Old != New && Old && New &&
1538  "Cannot RAUW equal values or to / from null!");
1539 
1540  DeferredReplacement D;
1541  D.Old = Old;
1542  D.New = New;
1543  return D;
1544  }
1545 
1546  static DeferredReplacement createDelete(Instruction *ToErase) {
1547  DeferredReplacement D;
1548  D.Old = ToErase;
1549  return D;
1550  }
1551 
1552  static DeferredReplacement createDeoptimizeReplacement(Instruction *Old) {
1553 #ifndef NDEBUG
1554  auto *F = cast<CallInst>(Old)->getCalledFunction();
1555  assert(F && F->getIntrinsicID() == Intrinsic::experimental_deoptimize &&
1556  "Only way to construct a deoptimize deferred replacement");
1557 #endif
1558  DeferredReplacement D;
1559  D.Old = Old;
1560  D.IsDeoptimize = true;
1561  return D;
1562  }
1563 
1564  /// Does the task represented by this instance.
1565  void doReplacement() {
1566  Instruction *OldI = Old;
1567  Instruction *NewI = New;
1568 
1569  assert(OldI != NewI && "Disallowed at construction?!");
1570  assert((!IsDeoptimize || !New) &&
1571  "Deoptimize intrinsics are not replaced!");
1572 
1573  Old = nullptr;
1574  New = nullptr;
1575 
1576  if (NewI)
1577  OldI->replaceAllUsesWith(NewI);
1578 
1579  if (IsDeoptimize) {
1580  // Note: we've inserted instructions, so the call to llvm.deoptimize may
1581  // not necessarily be followed by the matching return.
1582  auto *RI = cast<ReturnInst>(OldI->getParent()->getTerminator());
1583  new UnreachableInst(RI->getContext(), RI);
1584  RI->eraseFromParent();
1585  }
1586 
1587  OldI->eraseFromParent();
1588  }
1589 };
1590 
1591 } // end anonymous namespace
1592 
1594  const char *DeoptLowering = "deopt-lowering";
1595  if (Call->hasFnAttr(DeoptLowering)) {
1596  // FIXME: Calls have a *really* confusing interface around attributes
1597  // with values.
1598  const AttributeList &CSAS = Call->getAttributes();
1599  if (CSAS.hasFnAttr(DeoptLowering))
1600  return CSAS.getFnAttr(DeoptLowering).getValueAsString();
1601  Function *F = Call->getCalledFunction();
1602  assert(F && F->hasFnAttribute(DeoptLowering));
1603  return F->getFnAttribute(DeoptLowering).getValueAsString();
1604  }
1605  return "live-through";
1606 }
1607 
1608 static void
1609 makeStatepointExplicitImpl(CallBase *Call, /* to replace */
1610  const SmallVectorImpl<Value *> &BasePtrs,
1612  PartiallyConstructedSafepointRecord &Result,
1613  std::vector<DeferredReplacement> &Replacements,
1614  const PointerToBaseTy &PointerToBase) {
1615  assert(BasePtrs.size() == LiveVariables.size());
1616 
1617  // Then go ahead and use the builder do actually do the inserts. We insert
1618  // immediately before the previous instruction under the assumption that all
1619  // arguments will be available here. We can't insert afterwards since we may
1620  // be replacing a terminator.
1621  IRBuilder<> Builder(Call);
1622 
1625  uint32_t NumPatchBytes = 0;
1627 
1628  SmallVector<Value *, 8> CallArgs(Call->args());
1629  Optional<ArrayRef<Use>> DeoptArgs;
1630  if (auto Bundle = Call->getOperandBundle(LLVMContext::OB_deopt))
1631  DeoptArgs = Bundle->Inputs;
1632  Optional<ArrayRef<Use>> TransitionArgs;
1633  if (auto Bundle = Call->getOperandBundle(LLVMContext::OB_gc_transition)) {
1634  TransitionArgs = Bundle->Inputs;
1635  // TODO: This flag no longer serves a purpose and can be removed later
1637  }
1638 
1639  // Instead of lowering calls to @llvm.experimental.deoptimize as normal calls
1640  // with a return value, we lower then as never returning calls to
1641  // __llvm_deoptimize that are followed by unreachable to get better codegen.
1642  bool IsDeoptimize = false;
1643 
1645  parseStatepointDirectivesFromAttrs(Call->getAttributes());
1646  if (SD.NumPatchBytes)
1647  NumPatchBytes = *SD.NumPatchBytes;
1648  if (SD.StatepointID)
1649  StatepointID = *SD.StatepointID;
1650 
1651  // Pass through the requested lowering if any. The default is live-through.
1652  StringRef DeoptLowering = getDeoptLowering(Call);
1653  if (DeoptLowering.equals("live-in"))
1655  else {
1656  assert(DeoptLowering.equals("live-through") && "Unsupported value!");
1657  }
1658 
1659  FunctionCallee CallTarget(Call->getFunctionType(), Call->getCalledOperand());
1660  if (Function *F = dyn_cast<Function>(CallTarget.getCallee())) {
1661  auto IID = F->getIntrinsicID();
1662  if (IID == Intrinsic::experimental_deoptimize) {
1663  // Calls to llvm.experimental.deoptimize are lowered to calls to the
1664  // __llvm_deoptimize symbol. We want to resolve this now, since the
1665  // verifier does not allow taking the address of an intrinsic function.
1666 
1667  SmallVector<Type *, 8> DomainTy;
1668  for (Value *Arg : CallArgs)
1669  DomainTy.push_back(Arg->getType());
1670  auto *FTy = FunctionType::get(Type::getVoidTy(F->getContext()), DomainTy,
1671  /* isVarArg = */ false);
1672 
1673  // Note: CallTarget can be a bitcast instruction of a symbol if there are
1674  // calls to @llvm.experimental.deoptimize with different argument types in
1675  // the same module. This is fine -- we assume the frontend knew what it
1676  // was doing when generating this kind of IR.
1677  CallTarget = F->getParent()
1678  ->getOrInsertFunction("__llvm_deoptimize", FTy);
1679 
1680  IsDeoptimize = true;
1681  } else if (IID == Intrinsic::memcpy_element_unordered_atomic ||
1682  IID == Intrinsic::memmove_element_unordered_atomic) {
1683  // Unordered atomic memcpy and memmove intrinsics which are not explicitly
1684  // marked as "gc-leaf-function" should be lowered in a GC parseable way.
1685  // Specifically, these calls should be lowered to the
1686  // __llvm_{memcpy|memmove}_element_unordered_atomic_safepoint symbols.
1687  // Similarly to __llvm_deoptimize we want to resolve this now, since the
1688  // verifier does not allow taking the address of an intrinsic function.
1689  //
1690  // Moreover we need to shuffle the arguments for the call in order to
1691  // accommodate GC. The underlying source and destination objects might be
1692  // relocated during copy operation should the GC occur. To relocate the
1693  // derived source and destination pointers the implementation of the
1694  // intrinsic should know the corresponding base pointers.
1695  //
1696  // To make the base pointers available pass them explicitly as arguments:
1697  // memcpy(dest_derived, source_derived, ...) =>
1698  // memcpy(dest_base, dest_offset, source_base, source_offset, ...)
1699  auto &Context = Call->getContext();
1700  auto &DL = Call->getModule()->getDataLayout();
1701  auto GetBaseAndOffset = [&](Value *Derived) {
1702  Value *Base = nullptr;
1703  // Optimizations in unreachable code might substitute the real pointer
1704  // with undef, poison or null-derived constant. Return null base for
1705  // them to be consistent with the handling in the main algorithm in
1706  // findBaseDefiningValue.
1707  if (isa<Constant>(Derived))
1708  Base =
1709  ConstantPointerNull::get(cast<PointerType>(Derived->getType()));
1710  else {
1711  assert(PointerToBase.count(Derived));
1712  Base = PointerToBase.find(Derived)->second;
1713  }
1714  unsigned AddressSpace = Derived->getType()->getPointerAddressSpace();
1715  unsigned IntPtrSize = DL.getPointerSizeInBits(AddressSpace);
1716  Value *Base_int = Builder.CreatePtrToInt(
1717  Base, Type::getIntNTy(Context, IntPtrSize));
1718  Value *Derived_int = Builder.CreatePtrToInt(
1719  Derived, Type::getIntNTy(Context, IntPtrSize));
1720  return std::make_pair(Base, Builder.CreateSub(Derived_int, Base_int));
1721  };
1722 
1723  auto *Dest = CallArgs[0];
1724  Value *DestBase, *DestOffset;
1725  std::tie(DestBase, DestOffset) = GetBaseAndOffset(Dest);
1726 
1727  auto *Source = CallArgs[1];
1728  Value *SourceBase, *SourceOffset;
1729  std::tie(SourceBase, SourceOffset) = GetBaseAndOffset(Source);
1730 
1731  auto *LengthInBytes = CallArgs[2];
1732  auto *ElementSizeCI = cast<ConstantInt>(CallArgs[3]);
1733 
1734  CallArgs.clear();
1735  CallArgs.push_back(DestBase);
1736  CallArgs.push_back(DestOffset);
1737  CallArgs.push_back(SourceBase);
1738  CallArgs.push_back(SourceOffset);
1739  CallArgs.push_back(LengthInBytes);
1740 
1741  SmallVector<Type *, 8> DomainTy;
1742  for (Value *Arg : CallArgs)
1743  DomainTy.push_back(Arg->getType());
1744  auto *FTy = FunctionType::get(Type::getVoidTy(F->getContext()), DomainTy,
1745  /* isVarArg = */ false);
1746 
1747  auto GetFunctionName = [](Intrinsic::ID IID, ConstantInt *ElementSizeCI) {
1748  uint64_t ElementSize = ElementSizeCI->getZExtValue();
1749  if (IID == Intrinsic::memcpy_element_unordered_atomic) {
1750  switch (ElementSize) {
1751  case 1:
1752  return "__llvm_memcpy_element_unordered_atomic_safepoint_1";
1753  case 2:
1754  return "__llvm_memcpy_element_unordered_atomic_safepoint_2";
1755  case 4:
1756  return "__llvm_memcpy_element_unordered_atomic_safepoint_4";
1757  case 8:
1758  return "__llvm_memcpy_element_unordered_atomic_safepoint_8";
1759  case 16:
1760  return "__llvm_memcpy_element_unordered_atomic_safepoint_16";
1761  default:
1762  llvm_unreachable("unexpected element size!");
1763  }
1764  }
1765  assert(IID == Intrinsic::memmove_element_unordered_atomic);
1766  switch (ElementSize) {
1767  case 1:
1768  return "__llvm_memmove_element_unordered_atomic_safepoint_1";
1769  case 2:
1770  return "__llvm_memmove_element_unordered_atomic_safepoint_2";
1771  case 4:
1772  return "__llvm_memmove_element_unordered_atomic_safepoint_4";
1773  case 8:
1774  return "__llvm_memmove_element_unordered_atomic_safepoint_8";
1775  case 16:
1776  return "__llvm_memmove_element_unordered_atomic_safepoint_16";
1777  default:
1778  llvm_unreachable("unexpected element size!");
1779  }
1780  };
1781 
1782  CallTarget =
1783  F->getParent()
1784  ->getOrInsertFunction(GetFunctionName(IID, ElementSizeCI), FTy);
1785  }
1786  }
1787 
1788  // Create the statepoint given all the arguments
1789  GCStatepointInst *Token = nullptr;
1790  if (auto *CI = dyn_cast<CallInst>(Call)) {
1791  CallInst *SPCall = Builder.CreateGCStatepointCall(
1792  StatepointID, NumPatchBytes, CallTarget, Flags, CallArgs,
1793  TransitionArgs, DeoptArgs, GCArgs, "safepoint_token");
1794 
1795  SPCall->setTailCallKind(CI->getTailCallKind());
1796  SPCall->setCallingConv(CI->getCallingConv());
1797 
1798  // Currently we will fail on parameter attributes and on certain
1799  // function attributes. In case if we can handle this set of attributes -
1800  // set up function attrs directly on statepoint and return attrs later for
1801  // gc_result intrinsic.
1803  CI->getContext(), CI->getAttributes(), SPCall->getAttributes()));
1804 
1805  Token = cast<GCStatepointInst>(SPCall);
1806 
1807  // Put the following gc_result and gc_relocate calls immediately after the
1808  // the old call (which we're about to delete)
1809  assert(CI->getNextNode() && "Not a terminator, must have next!");
1810  Builder.SetInsertPoint(CI->getNextNode());
1811  Builder.SetCurrentDebugLocation(CI->getNextNode()->getDebugLoc());
1812  } else {
1813  auto *II = cast<InvokeInst>(Call);
1814 
1815  // Insert the new invoke into the old block. We'll remove the old one in a
1816  // moment at which point this will become the new terminator for the
1817  // original block.
1818  InvokeInst *SPInvoke = Builder.CreateGCStatepointInvoke(
1819  StatepointID, NumPatchBytes, CallTarget, II->getNormalDest(),
1820  II->getUnwindDest(), Flags, CallArgs, TransitionArgs, DeoptArgs, GCArgs,
1821  "statepoint_token");
1822 
1823  SPInvoke->setCallingConv(II->getCallingConv());
1824 
1825  // Currently we will fail on parameter attributes and on certain
1826  // function attributes. In case if we can handle this set of attributes -
1827  // set up function attrs directly on statepoint and return attrs later for
1828  // gc_result intrinsic.
1830  II->getContext(), II->getAttributes(), SPInvoke->getAttributes()));
1831 
1832  Token = cast<GCStatepointInst>(SPInvoke);
1833 
1834  // Generate gc relocates in exceptional path
1835  BasicBlock *UnwindBlock = II->getUnwindDest();
1836  assert(!isa<PHINode>(UnwindBlock->begin()) &&
1837  UnwindBlock->getUniquePredecessor() &&
1838  "can't safely insert in this block!");
1839 
1840  Builder.SetInsertPoint(&*UnwindBlock->getFirstInsertionPt());
1841  Builder.SetCurrentDebugLocation(II->getDebugLoc());
1842 
1843  // Attach exceptional gc relocates to the landingpad.
1844  Instruction *ExceptionalToken = UnwindBlock->getLandingPadInst();
1845  Result.UnwindToken = ExceptionalToken;
1846 
1847  CreateGCRelocates(LiveVariables, BasePtrs, ExceptionalToken, Builder);
1848 
1849  // Generate gc relocates and returns for normal block
1850  BasicBlock *NormalDest = II->getNormalDest();
1851  assert(!isa<PHINode>(NormalDest->begin()) &&
1852  NormalDest->getUniquePredecessor() &&
1853  "can't safely insert in this block!");
1854 
1855  Builder.SetInsertPoint(&*NormalDest->getFirstInsertionPt());
1856 
1857  // gc relocates will be generated later as if it were regular call
1858  // statepoint
1859  }
1860  assert(Token && "Should be set in one of the above branches!");
1861 
1862  if (IsDeoptimize) {
1863  // If we're wrapping an @llvm.experimental.deoptimize in a statepoint, we
1864  // transform the tail-call like structure to a call to a void function
1865  // followed by unreachable to get better codegen.
1866  Replacements.push_back(
1867  DeferredReplacement::createDeoptimizeReplacement(Call));
1868  } else {
1869  Token->setName("statepoint_token");
1870  if (!Call->getType()->isVoidTy() && !Call->use_empty()) {
1871  StringRef Name = Call->hasName() ? Call->getName() : "";
1872  CallInst *GCResult = Builder.CreateGCResult(Token, Call->getType(), Name);
1873  GCResult->setAttributes(
1875  Call->getAttributes().getRetAttrs()));
1876 
1877  // We cannot RAUW or delete CS.getInstruction() because it could be in the
1878  // live set of some other safepoint, in which case that safepoint's
1879  // PartiallyConstructedSafepointRecord will hold a raw pointer to this
1880  // llvm::Instruction. Instead, we defer the replacement and deletion to
1881  // after the live sets have been made explicit in the IR, and we no longer
1882  // have raw pointers to worry about.
1883  Replacements.emplace_back(
1884  DeferredReplacement::createRAUW(Call, GCResult));
1885  } else {
1886  Replacements.emplace_back(DeferredReplacement::createDelete(Call));
1887  }
1888  }
1889 
1890  Result.StatepointToken = Token;
1891 
1892  // Second, create a gc.relocate for every live variable
1893  CreateGCRelocates(LiveVariables, BasePtrs, Token, Builder);
1894 }
1895 
1896 // Replace an existing gc.statepoint with a new one and a set of gc.relocates
1897 // which make the relocations happening at this safepoint explicit.
1898 //
1899 // WARNING: Does not do any fixup to adjust users of the original live
1900 // values. That's the callers responsibility.
1901 static void
1903  PartiallyConstructedSafepointRecord &Result,
1904  std::vector<DeferredReplacement> &Replacements,
1905  const PointerToBaseTy &PointerToBase) {
1906  const auto &LiveSet = Result.LiveSet;
1907 
1908  // Convert to vector for efficient cross referencing.
1909  SmallVector<Value *, 64> BaseVec, LiveVec;
1910  LiveVec.reserve(LiveSet.size());
1911  BaseVec.reserve(LiveSet.size());
1912  for (Value *L : LiveSet) {
1913  LiveVec.push_back(L);
1914  assert(PointerToBase.count(L));
1915  Value *Base = PointerToBase.find(L)->second;
1916  BaseVec.push_back(Base);
1917  }
1918  assert(LiveVec.size() == BaseVec.size());
1919 
1920  // Do the actual rewriting and delete the old statepoint
1921  makeStatepointExplicitImpl(Call, BaseVec, LiveVec, Result, Replacements,
1922  PointerToBase);
1923 }
1924 
1925 // Helper function for the relocationViaAlloca.
1926 //
1927 // It receives iterator to the statepoint gc relocates and emits a store to the
1928 // assigned location (via allocaMap) for the each one of them. It adds the
1929 // visited values into the visitedLiveValues set, which we will later use them
1930 // for validation checking.
1931 static void
1934  DenseSet<Value *> &VisitedLiveValues) {
1935  for (User *U : GCRelocs) {
1936  GCRelocateInst *Relocate = dyn_cast<GCRelocateInst>(U);
1937  if (!Relocate)
1938  continue;
1939 
1940  Value *OriginalValue = Relocate->getDerivedPtr();
1941  assert(AllocaMap.count(OriginalValue));
1942  Value *Alloca = AllocaMap[OriginalValue];
1943 
1944  // Emit store into the related alloca
1945  // All gc_relocates are i8 addrspace(1)* typed, and it must be bitcasted to
1946  // the correct type according to alloca.
1947  assert(Relocate->getNextNode() &&
1948  "Should always have one since it's not a terminator");
1949  IRBuilder<> Builder(Relocate->getNextNode());
1950  Value *CastedRelocatedValue =
1951  Builder.CreateBitCast(Relocate,
1952  cast<AllocaInst>(Alloca)->getAllocatedType(),
1953  suffixed_name_or(Relocate, ".casted", ""));
1954 
1955  new StoreInst(CastedRelocatedValue, Alloca,
1956  cast<Instruction>(CastedRelocatedValue)->getNextNode());
1957 
1958 #ifndef NDEBUG
1959  VisitedLiveValues.insert(OriginalValue);
1960 #endif
1961  }
1962 }
1963 
1964 // Helper function for the "relocationViaAlloca". Similar to the
1965 // "insertRelocationStores" but works for rematerialized values.
1967  const RematerializedValueMapTy &RematerializedValues,
1969  DenseSet<Value *> &VisitedLiveValues) {
1970  for (auto RematerializedValuePair: RematerializedValues) {
1971  Instruction *RematerializedValue = RematerializedValuePair.first;
1972  Value *OriginalValue = RematerializedValuePair.second;
1973 
1974  assert(AllocaMap.count(OriginalValue) &&
1975  "Can not find alloca for rematerialized value");
1976  Value *Alloca = AllocaMap[OriginalValue];
1977 
1978  new StoreInst(RematerializedValue, Alloca,
1979  RematerializedValue->getNextNode());
1980 
1981 #ifndef NDEBUG
1982  VisitedLiveValues.insert(OriginalValue);
1983 #endif
1984  }
1985 }
1986 
1987 /// Do all the relocation update via allocas and mem2reg
1991 #ifndef NDEBUG
1992  // record initial number of (static) allocas; we'll check we have the same
1993  // number when we get done.
1994  int InitialAllocaNum = 0;
1995  for (Instruction &I : F.getEntryBlock())
1996  if (isa<AllocaInst>(I))
1997  InitialAllocaNum++;
1998 #endif
1999 
2000  // TODO-PERF: change data structures, reserve
2002  SmallVector<AllocaInst *, 200> PromotableAllocas;
2003  // Used later to chack that we have enough allocas to store all values
2004  std::size_t NumRematerializedValues = 0;
2005  PromotableAllocas.reserve(Live.size());
2006 
2007  // Emit alloca for "LiveValue" and record it in "allocaMap" and
2008  // "PromotableAllocas"
2009  const DataLayout &DL = F.getParent()->getDataLayout();
2010  auto emitAllocaFor = [&](Value *LiveValue) {
2011  AllocaInst *Alloca = new AllocaInst(LiveValue->getType(),
2012  DL.getAllocaAddrSpace(), "",
2013  F.getEntryBlock().getFirstNonPHI());
2014  AllocaMap[LiveValue] = Alloca;
2015  PromotableAllocas.push_back(Alloca);
2016  };
2017 
2018  // Emit alloca for each live gc pointer
2019  for (Value *V : Live)
2020  emitAllocaFor(V);
2021 
2022  // Emit allocas for rematerialized values
2023  for (const auto &Info : Records)
2024  for (auto RematerializedValuePair : Info.RematerializedValues) {
2025  Value *OriginalValue = RematerializedValuePair.second;
2026  if (AllocaMap.count(OriginalValue) != 0)
2027  continue;
2028 
2029  emitAllocaFor(OriginalValue);
2030  ++NumRematerializedValues;
2031  }
2032 
2033  // The next two loops are part of the same conceptual operation. We need to
2034  // insert a store to the alloca after the original def and at each
2035  // redefinition. We need to insert a load before each use. These are split
2036  // into distinct loops for performance reasons.
2037 
2038  // Update gc pointer after each statepoint: either store a relocated value or
2039  // null (if no relocated value was found for this gc pointer and it is not a
2040  // gc_result). This must happen before we update the statepoint with load of
2041  // alloca otherwise we lose the link between statepoint and old def.
2042  for (const auto &Info : Records) {
2043  Value *Statepoint = Info.StatepointToken;
2044 
2045  // This will be used for consistency check
2046  DenseSet<Value *> VisitedLiveValues;
2047 
2048  // Insert stores for normal statepoint gc relocates
2049  insertRelocationStores(Statepoint->users(), AllocaMap, VisitedLiveValues);
2050 
2051  // In case if it was invoke statepoint
2052  // we will insert stores for exceptional path gc relocates.
2053  if (isa<InvokeInst>(Statepoint)) {
2054  insertRelocationStores(Info.UnwindToken->users(), AllocaMap,
2055  VisitedLiveValues);
2056  }
2057 
2058  // Do similar thing with rematerialized values
2059  insertRematerializationStores(Info.RematerializedValues, AllocaMap,
2060  VisitedLiveValues);
2061 
2062  if (ClobberNonLive) {
2063  // As a debugging aid, pretend that an unrelocated pointer becomes null at
2064  // the gc.statepoint. This will turn some subtle GC problems into
2065  // slightly easier to debug SEGVs. Note that on large IR files with
2066  // lots of gc.statepoints this is extremely costly both memory and time
2067  // wise.
2069  for (auto Pair : AllocaMap) {
2070  Value *Def = Pair.first;
2071  AllocaInst *Alloca = Pair.second;
2072 
2073  // This value was relocated
2074  if (VisitedLiveValues.count(Def)) {
2075  continue;
2076  }
2077  ToClobber.push_back(Alloca);
2078  }
2079 
2080  auto InsertClobbersAt = [&](Instruction *IP) {
2081  for (auto *AI : ToClobber) {
2082  auto AT = AI->getAllocatedType();
2083  Constant *CPN;
2084  if (AT->isVectorTy())
2085  CPN = ConstantAggregateZero::get(AT);
2086  else
2087  CPN = ConstantPointerNull::get(cast<PointerType>(AT));
2088  new StoreInst(CPN, AI, IP);
2089  }
2090  };
2091 
2092  // Insert the clobbering stores. These may get intermixed with the
2093  // gc.results and gc.relocates, but that's fine.
2094  if (auto II = dyn_cast<InvokeInst>(Statepoint)) {
2095  InsertClobbersAt(&*II->getNormalDest()->getFirstInsertionPt());
2096  InsertClobbersAt(&*II->getUnwindDest()->getFirstInsertionPt());
2097  } else {
2098  InsertClobbersAt(cast<Instruction>(Statepoint)->getNextNode());
2099  }
2100  }
2101  }
2102 
2103  // Update use with load allocas and add store for gc_relocated.
2104  for (auto Pair : AllocaMap) {
2105  Value *Def = Pair.first;
2106  AllocaInst *Alloca = Pair.second;
2107 
2108  // We pre-record the uses of allocas so that we dont have to worry about
2109  // later update that changes the user information..
2110 
2112  // PERF: trade a linear scan for repeated reallocation
2113  Uses.reserve(Def->getNumUses());
2114  for (User *U : Def->users()) {
2115  if (!isa<ConstantExpr>(U)) {
2116  // If the def has a ConstantExpr use, then the def is either a
2117  // ConstantExpr use itself or null. In either case
2118  // (recursively in the first, directly in the second), the oop
2119  // it is ultimately dependent on is null and this particular
2120  // use does not need to be fixed up.
2121  Uses.push_back(cast<Instruction>(U));
2122  }
2123  }
2124 
2125  llvm::sort(Uses);
2126  auto Last = std::unique(Uses.begin(), Uses.end());
2127  Uses.erase(Last, Uses.end());
2128 
2129  for (Instruction *Use : Uses) {
2130  if (isa<PHINode>(Use)) {
2131  PHINode *Phi = cast<PHINode>(Use);
2132  for (unsigned i = 0; i < Phi->getNumIncomingValues(); i++) {
2133  if (Def == Phi->getIncomingValue(i)) {
2134  LoadInst *Load =
2135  new LoadInst(Alloca->getAllocatedType(), Alloca, "",
2136  Phi->getIncomingBlock(i)->getTerminator());
2137  Phi->setIncomingValue(i, Load);
2138  }
2139  }
2140  } else {
2141  LoadInst *Load =
2142  new LoadInst(Alloca->getAllocatedType(), Alloca, "", Use);
2143  Use->replaceUsesOfWith(Def, Load);
2144  }
2145  }
2146 
2147  // Emit store for the initial gc value. Store must be inserted after load,
2148  // otherwise store will be in alloca's use list and an extra load will be
2149  // inserted before it.
2150  StoreInst *Store = new StoreInst(Def, Alloca, /*volatile*/ false,
2151  DL.getABITypeAlign(Def->getType()));
2152  if (Instruction *Inst = dyn_cast<Instruction>(Def)) {
2153  if (InvokeInst *Invoke = dyn_cast<InvokeInst>(Inst)) {
2154  // InvokeInst is a terminator so the store need to be inserted into its
2155  // normal destination block.
2156  BasicBlock *NormalDest = Invoke->getNormalDest();
2157  Store->insertBefore(NormalDest->getFirstNonPHI());
2158  } else {
2159  assert(!Inst->isTerminator() &&
2160  "The only terminator that can produce a value is "
2161  "InvokeInst which is handled above.");
2162  Store->insertAfter(Inst);
2163  }
2164  } else {
2165  assert(isa<Argument>(Def));
2166  Store->insertAfter(cast<Instruction>(Alloca));
2167  }
2168  }
2169 
2170  assert(PromotableAllocas.size() == Live.size() + NumRematerializedValues &&
2171  "we must have the same allocas with lives");
2172  (void) NumRematerializedValues;
2173  if (!PromotableAllocas.empty()) {
2174  // Apply mem2reg to promote alloca to SSA
2175  PromoteMemToReg(PromotableAllocas, DT);
2176  }
2177 
2178 #ifndef NDEBUG
2179  for (auto &I : F.getEntryBlock())
2180  if (isa<AllocaInst>(I))
2181  InitialAllocaNum--;
2182  assert(InitialAllocaNum == 0 && "We must not introduce any extra allocas");
2183 #endif
2184 }
2185 
2186 /// Implement a unique function which doesn't require we sort the input
2187 /// vector. Doing so has the effect of changing the output of a couple of
2188 /// tests in ways which make them less useful in testing fused safepoints.
2189 template <typename T> static void unique_unsorted(SmallVectorImpl<T> &Vec) {
2190  SmallSet<T, 8> Seen;
2191  erase_if(Vec, [&](const T &V) { return !Seen.insert(V).second; });
2192 }
2193 
2194 /// Insert holders so that each Value is obviously live through the entire
2195 /// lifetime of the call.
2196 static void insertUseHolderAfter(CallBase *Call, const ArrayRef<Value *> Values,
2197  SmallVectorImpl<CallInst *> &Holders) {
2198  if (Values.empty())
2199  // No values to hold live, might as well not insert the empty holder
2200  return;
2201 
2202  Module *M = Call->getModule();
2203  // Use a dummy vararg function to actually hold the values live
2204  FunctionCallee Func = M->getOrInsertFunction(
2205  "__tmp_use", FunctionType::get(Type::getVoidTy(M->getContext()), true));
2206  if (isa<CallInst>(Call)) {
2207  // For call safepoints insert dummy calls right after safepoint
2208  Holders.push_back(
2209  CallInst::Create(Func, Values, "", &*++Call->getIterator()));
2210  return;
2211  }
2212  // For invoke safepooints insert dummy calls both in normal and
2213  // exceptional destination blocks
2214  auto *II = cast<InvokeInst>(Call);
2215  Holders.push_back(CallInst::Create(
2216  Func, Values, "", &*II->getNormalDest()->getFirstInsertionPt()));
2217  Holders.push_back(CallInst::Create(
2218  Func, Values, "", &*II->getUnwindDest()->getFirstInsertionPt()));
2219 }
2220 
2222  Function &F, DominatorTree &DT, ArrayRef<CallBase *> toUpdate,
2224  GCPtrLivenessData OriginalLivenessData;
2225  computeLiveInValues(DT, F, OriginalLivenessData);
2226  for (size_t i = 0; i < records.size(); i++) {
2227  struct PartiallyConstructedSafepointRecord &info = records[i];
2228  analyzeParsePointLiveness(DT, OriginalLivenessData, toUpdate[i], info);
2229  }
2230 }
2231 
2232 // Helper function for the "rematerializeLiveValues". It walks use chain
2233 // starting from the "CurrentValue" until it reaches the root of the chain, i.e.
2234 // the base or a value it cannot process. Only "simple" values are processed
2235 // (currently it is GEP's and casts). The returned root is examined by the
2236 // callers of findRematerializableChainToBasePointer. Fills "ChainToBase" array
2237 // with all visited values.
2239  SmallVectorImpl<Instruction*> &ChainToBase,
2240  Value *CurrentValue) {
2241  if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(CurrentValue)) {
2242  ChainToBase.push_back(GEP);
2243  return findRematerializableChainToBasePointer(ChainToBase,
2244  GEP->getPointerOperand());
2245  }
2246 
2247  if (CastInst *CI = dyn_cast<CastInst>(CurrentValue)) {
2248  if (!CI->isNoopCast(CI->getModule()->getDataLayout()))
2249  return CI;
2250 
2251  ChainToBase.push_back(CI);
2252  return findRematerializableChainToBasePointer(ChainToBase,
2253  CI->getOperand(0));
2254  }
2255 
2256  // We have reached the root of the chain, which is either equal to the base or
2257  // is the first unsupported value along the use chain.
2258  return CurrentValue;
2259 }
2260 
2261 // Helper function for the "rematerializeLiveValues". Compute cost of the use
2262 // chain we are going to rematerialize.
2263 static InstructionCost
2266  InstructionCost Cost = 0;
2267 
2268  for (Instruction *Instr : Chain) {
2269  if (CastInst *CI = dyn_cast<CastInst>(Instr)) {
2270  assert(CI->isNoopCast(CI->getModule()->getDataLayout()) &&
2271  "non noop cast is found during rematerialization");
2272 
2273  Type *SrcTy = CI->getOperand(0)->getType();
2274  Cost += TTI.getCastInstrCost(CI->getOpcode(), CI->getType(), SrcTy,
2277 
2278  } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Instr)) {
2279  // Cost of the address calculation
2280  Type *ValTy = GEP->getSourceElementType();
2282 
2283  // And cost of the GEP itself
2284  // TODO: Use TTI->getGEPCost here (it exists, but appears to be not
2285  // allowed for the external usage)
2286  if (!GEP->hasAllConstantIndices())
2287  Cost += 2;
2288 
2289  } else {
2290  llvm_unreachable("unsupported instruction type during rematerialization");
2291  }
2292  }
2293 
2294  return Cost;
2295 }
2296 
2297 static bool AreEquivalentPhiNodes(PHINode &OrigRootPhi, PHINode &AlternateRootPhi) {
2298  unsigned PhiNum = OrigRootPhi.getNumIncomingValues();
2299  if (PhiNum != AlternateRootPhi.getNumIncomingValues() ||
2300  OrigRootPhi.getParent() != AlternateRootPhi.getParent())
2301  return false;
2302  // Map of incoming values and their corresponding basic blocks of
2303  // OrigRootPhi.
2304  SmallDenseMap<Value *, BasicBlock *, 8> CurrentIncomingValues;
2305  for (unsigned i = 0; i < PhiNum; i++)
2306  CurrentIncomingValues[OrigRootPhi.getIncomingValue(i)] =
2307  OrigRootPhi.getIncomingBlock(i);
2308 
2309  // Both current and base PHIs should have same incoming values and
2310  // the same basic blocks corresponding to the incoming values.
2311  for (unsigned i = 0; i < PhiNum; i++) {
2312  auto CIVI =
2313  CurrentIncomingValues.find(AlternateRootPhi.getIncomingValue(i));
2314  if (CIVI == CurrentIncomingValues.end())
2315  return false;
2316  BasicBlock *CurrentIncomingBB = CIVI->second;
2317  if (CurrentIncomingBB != AlternateRootPhi.getIncomingBlock(i))
2318  return false;
2319  }
2320  return true;
2321 }
2322 
2323 // Find derived pointers that can be recomputed cheap enough and fill
2324 // RematerizationCandidates with such candidates.
2325 static void
2327  RematCandTy &RematerizationCandidates,
2329  const unsigned int ChainLengthThreshold = 10;
2330 
2331  for (auto P2B : PointerToBase) {
2332  auto *Derived = P2B.first;
2333  auto *Base = P2B.second;
2334  // Consider only derived pointers.
2335  if (Derived == Base)
2336  continue;
2337 
2338  // For each live pointer find its defining chain.
2339  SmallVector<Instruction *, 3> ChainToBase;
2340  Value *RootOfChain =
2341  findRematerializableChainToBasePointer(ChainToBase, Derived);
2342 
2343  // Nothing to do, or chain is too long
2344  if ( ChainToBase.size() == 0 ||
2345  ChainToBase.size() > ChainLengthThreshold)
2346  continue;
2347 
2348  // Handle the scenario where the RootOfChain is not equal to the
2349  // Base Value, but they are essentially the same phi values.
2350  if (RootOfChain != PointerToBase[Derived]) {
2351  PHINode *OrigRootPhi = dyn_cast<PHINode>(RootOfChain);
2352  PHINode *AlternateRootPhi = dyn_cast<PHINode>(PointerToBase[Derived]);
2353  if (!OrigRootPhi || !AlternateRootPhi)
2354  continue;
2355  // PHI nodes that have the same incoming values, and belonging to the same
2356  // basic blocks are essentially the same SSA value. When the original phi
2357  // has incoming values with different base pointers, the original phi is
2358  // marked as conflict, and an additional `AlternateRootPhi` with the same
2359  // incoming values get generated by the findBasePointer function. We need
2360  // to identify the newly generated AlternateRootPhi (.base version of phi)
2361  // and RootOfChain (the original phi node itself) are the same, so that we
2362  // can rematerialize the gep and casts. This is a workaround for the
2363  // deficiency in the findBasePointer algorithm.
2364  if (!AreEquivalentPhiNodes(*OrigRootPhi, *AlternateRootPhi))
2365  continue;
2366  }
2367  // Compute cost of this chain.
2369  // TODO: We can also account for cases when we will be able to remove some
2370  // of the rematerialized values by later optimization passes. I.e if
2371  // we rematerialized several intersecting chains. Or if original values
2372  // don't have any uses besides this statepoint.
2373 
2374  // Ok, there is a candidate.
2375  RematerizlizationCandidateRecord Record;
2376  Record.ChainToBase = ChainToBase;
2377  Record.RootOfChain = RootOfChain;
2378  Record.Cost = Cost;
2379  RematerizationCandidates.insert({ Derived, Record });
2380  }
2381 }
2382 
2383 // From the statepoint live set pick values that are cheaper to recompute then
2384 // to relocate. Remove this values from the live set, rematerialize them after
2385 // statepoint and record them in "Info" structure. Note that similar to
2386 // relocated values we don't do any user adjustments here.
2388  PartiallyConstructedSafepointRecord &Info,
2389  PointerToBaseTy &PointerToBase,
2390  RematCandTy &RematerizationCandidates,
2392  // Record values we are going to delete from this statepoint live set.
2393  // We can not di this in following loop due to iterator invalidation.
2394  SmallVector<Value *, 32> LiveValuesToBeDeleted;
2395 
2396  for (Value *LiveValue : Info.LiveSet) {
2397  auto It = RematerizationCandidates.find(LiveValue);
2398  if (It == RematerizationCandidates.end())
2399  continue;
2400 
2401  RematerizlizationCandidateRecord &Record = It->second;
2402 
2403  InstructionCost Cost = Record.Cost;
2404  // For invokes we need to rematerialize each chain twice - for normal and
2405  // for unwind basic blocks. Model this by multiplying cost by two.
2406  if (isa<InvokeInst>(Call))
2407  Cost *= 2;
2408 
2409  // If it's too expensive - skip it.
2411  continue;
2412 
2413  // Remove value from the live set
2414  LiveValuesToBeDeleted.push_back(LiveValue);
2415 
2416  // Clone instructions and record them inside "Info" structure.
2417 
2418  // For each live pointer find get its defining chain.
2419  SmallVector<Instruction *, 3> ChainToBase = Record.ChainToBase;
2420  // Walk backwards to visit top-most instructions first.
2421  std::reverse(ChainToBase.begin(), ChainToBase.end());
2422 
2423  // Utility function which clones all instructions from "ChainToBase"
2424  // and inserts them before "InsertBefore". Returns rematerialized value
2425  // which should be used after statepoint.
2426  auto rematerializeChain = [&ChainToBase](
2427  Instruction *InsertBefore, Value *RootOfChain, Value *AlternateLiveBase) {
2428  Instruction *LastClonedValue = nullptr;
2429  Instruction *LastValue = nullptr;
2430  for (Instruction *Instr: ChainToBase) {
2431  // Only GEP's and casts are supported as we need to be careful to not
2432  // introduce any new uses of pointers not in the liveset.
2433  // Note that it's fine to introduce new uses of pointers which were
2434  // otherwise not used after this statepoint.
2435  assert(isa<GetElementPtrInst>(Instr) || isa<CastInst>(Instr));
2436 
2437  Instruction *ClonedValue = Instr->clone();
2438  ClonedValue->insertBefore(InsertBefore);
2439  ClonedValue->setName(Instr->getName() + ".remat");
2440 
2441  // If it is not first instruction in the chain then it uses previously
2442  // cloned value. We should update it to use cloned value.
2443  if (LastClonedValue) {
2444  assert(LastValue);
2445  ClonedValue->replaceUsesOfWith(LastValue, LastClonedValue);
2446 #ifndef NDEBUG
2447  for (auto *OpValue : ClonedValue->operand_values()) {
2448  // Assert that cloned instruction does not use any instructions from
2449  // this chain other than LastClonedValue
2450  assert(!is_contained(ChainToBase, OpValue) &&
2451  "incorrect use in rematerialization chain");
2452  // Assert that the cloned instruction does not use the RootOfChain
2453  // or the AlternateLiveBase.
2454  assert(OpValue != RootOfChain && OpValue != AlternateLiveBase);
2455  }
2456 #endif
2457  } else {
2458  // For the first instruction, replace the use of unrelocated base i.e.
2459  // RootOfChain/OrigRootPhi, with the corresponding PHI present in the
2460  // live set. They have been proved to be the same PHI nodes. Note
2461  // that the *only* use of the RootOfChain in the ChainToBase list is
2462  // the first Value in the list.
2463  if (RootOfChain != AlternateLiveBase)
2464  ClonedValue->replaceUsesOfWith(RootOfChain, AlternateLiveBase);
2465  }
2466 
2467  LastClonedValue = ClonedValue;
2468  LastValue = Instr;
2469  }
2470  assert(LastClonedValue);
2471  return LastClonedValue;
2472  };
2473 
2474  // Different cases for calls and invokes. For invokes we need to clone
2475  // instructions both on normal and unwind path.
2476  if (isa<CallInst>(Call)) {
2477  Instruction *InsertBefore = Call->getNextNode();
2478  assert(InsertBefore);
2479  Instruction *RematerializedValue = rematerializeChain(
2480  InsertBefore, Record.RootOfChain, PointerToBase[LiveValue]);
2481  Info.RematerializedValues[RematerializedValue] = LiveValue;
2482  } else {
2483  auto *Invoke = cast<InvokeInst>(Call);
2484 
2485  Instruction *NormalInsertBefore =
2486  &*Invoke->getNormalDest()->getFirstInsertionPt();
2487  Instruction *UnwindInsertBefore =
2488  &*Invoke->getUnwindDest()->getFirstInsertionPt();
2489 
2490  Instruction *NormalRematerializedValue = rematerializeChain(
2491  NormalInsertBefore, Record.RootOfChain, PointerToBase[LiveValue]);
2492  Instruction *UnwindRematerializedValue = rematerializeChain(
2493  UnwindInsertBefore, Record.RootOfChain, PointerToBase[LiveValue]);
2494 
2495  Info.RematerializedValues[NormalRematerializedValue] = LiveValue;
2496  Info.RematerializedValues[UnwindRematerializedValue] = LiveValue;
2497  }
2498  }
2499 
2500  // Remove rematerializaed values from the live set
2501  for (auto *LiveValue: LiveValuesToBeDeleted) {
2502  Info.LiveSet.remove(LiveValue);
2503  }
2504 }
2505 
2507  SmallVectorImpl<CallInst *> &Intrinsics,
2508  DefiningValueMapTy &DVCache,
2509  IsKnownBaseMapTy &KnownBases) {
2510  auto &Context = F.getContext();
2511  auto &DL = F.getParent()->getDataLayout();
2512  bool Changed = false;
2513 
2514  for (auto *Callsite : Intrinsics)
2515  switch (Callsite->getIntrinsicID()) {
2516  case Intrinsic::experimental_gc_get_pointer_base: {
2517  Changed = true;
2518  Value *Base =
2519  findBasePointer(Callsite->getOperand(0), DVCache, KnownBases);
2520  assert(!DVCache.count(Callsite));
2521  auto *BaseBC = IRBuilder<>(Callsite).CreateBitCast(
2522  Base, Callsite->getType(), suffixed_name_or(Base, ".cast", ""));
2523  if (BaseBC != Base)
2524  DVCache[BaseBC] = Base;
2525  Callsite->replaceAllUsesWith(BaseBC);
2526  if (!BaseBC->hasName())
2527  BaseBC->takeName(Callsite);
2528  Callsite->eraseFromParent();
2529  break;
2530  }
2531  case Intrinsic::experimental_gc_get_pointer_offset: {
2532  Changed = true;
2533  Value *Derived = Callsite->getOperand(0);
2534  Value *Base = findBasePointer(Derived, DVCache, KnownBases);
2535  assert(!DVCache.count(Callsite));
2536  unsigned AddressSpace = Derived->getType()->getPointerAddressSpace();
2537  unsigned IntPtrSize = DL.getPointerSizeInBits(AddressSpace);
2538  IRBuilder<> Builder(Callsite);
2539  Value *BaseInt =
2540  Builder.CreatePtrToInt(Base, Type::getIntNTy(Context, IntPtrSize),
2541  suffixed_name_or(Base, ".int", ""));
2542  Value *DerivedInt =
2543  Builder.CreatePtrToInt(Derived, Type::getIntNTy(Context, IntPtrSize),
2544  suffixed_name_or(Derived, ".int", ""));
2545  Value *Offset = Builder.CreateSub(DerivedInt, BaseInt);
2546  Callsite->replaceAllUsesWith(Offset);
2547  Offset->takeName(Callsite);
2548  Callsite->eraseFromParent();
2549  break;
2550  }
2551  default:
2552  llvm_unreachable("Unknown intrinsic");
2553  }
2554 
2555  return Changed;
2556 }
2557 
2560  SmallVectorImpl<CallBase *> &ToUpdate,
2561  DefiningValueMapTy &DVCache,
2562  IsKnownBaseMapTy &KnownBases) {
2563 #ifndef NDEBUG
2564  // Validate the input
2565  std::set<CallBase *> Uniqued;
2566  Uniqued.insert(ToUpdate.begin(), ToUpdate.end());
2567  assert(Uniqued.size() == ToUpdate.size() && "no duplicates please!");
2568 
2569  for (CallBase *Call : ToUpdate)
2570  assert(Call->getFunction() == &F);
2571 #endif
2572 
2573  // When inserting gc.relocates for invokes, we need to be able to insert at
2574  // the top of the successor blocks. See the comment on
2575  // normalForInvokeSafepoint on exactly what is needed. Note that this step
2576  // may restructure the CFG.
2577  for (CallBase *Call : ToUpdate) {
2578  auto *II = dyn_cast<InvokeInst>(Call);
2579  if (!II)
2580  continue;
2581  normalizeForInvokeSafepoint(II->getNormalDest(), II->getParent(), DT);
2582  normalizeForInvokeSafepoint(II->getUnwindDest(), II->getParent(), DT);
2583  }
2584 
2585  // A list of dummy calls added to the IR to keep various values obviously
2586  // live in the IR. We'll remove all of these when done.
2588 
2589  // Insert a dummy call with all of the deopt operands we'll need for the
2590  // actual safepoint insertion as arguments. This ensures reference operands
2591  // in the deopt argument list are considered live through the safepoint (and
2592  // thus makes sure they get relocated.)
2593  for (CallBase *Call : ToUpdate) {
2594  SmallVector<Value *, 64> DeoptValues;
2595 
2596  for (Value *Arg : GetDeoptBundleOperands(Call)) {
2597  assert(!isUnhandledGCPointerType(Arg->getType()) &&
2598  "support for FCA unimplemented");
2599  if (isHandledGCPointerType(Arg->getType()))
2600  DeoptValues.push_back(Arg);
2601  }
2602 
2603  insertUseHolderAfter(Call, DeoptValues, Holders);
2604  }
2605 
2607 
2608  // A) Identify all gc pointers which are statically live at the given call
2609  // site.
2610  findLiveReferences(F, DT, ToUpdate, Records);
2611 
2612  /// Global mapping from live pointers to a base-defining-value.
2613  PointerToBaseTy PointerToBase;
2614 
2615  // B) Find the base pointers for each live pointer
2616  for (size_t i = 0; i < Records.size(); i++) {
2617  PartiallyConstructedSafepointRecord &info = Records[i];
2618  findBasePointers(DT, DVCache, ToUpdate[i], info, PointerToBase, KnownBases);
2619  }
2620  if (PrintBasePointers) {
2621  errs() << "Base Pairs (w/o Relocation):\n";
2622  for (auto &Pair : PointerToBase) {
2623  errs() << " derived ";
2624  Pair.first->printAsOperand(errs(), false);
2625  errs() << " base ";
2626  Pair.second->printAsOperand(errs(), false);
2627  errs() << "\n";
2628  ;
2629  }
2630  }
2631 
2632  // The base phi insertion logic (for any safepoint) may have inserted new
2633  // instructions which are now live at some safepoint. The simplest such
2634  // example is:
2635  // loop:
2636  // phi a <-- will be a new base_phi here
2637  // safepoint 1 <-- that needs to be live here
2638  // gep a + 1
2639  // safepoint 2
2640  // br loop
2641  // We insert some dummy calls after each safepoint to definitely hold live
2642  // the base pointers which were identified for that safepoint. We'll then
2643  // ask liveness for _every_ base inserted to see what is now live. Then we
2644  // remove the dummy calls.
2645  Holders.reserve(Holders.size() + Records.size());
2646  for (size_t i = 0; i < Records.size(); i++) {
2647  PartiallyConstructedSafepointRecord &Info = Records[i];
2648 
2650  for (auto *Derived : Info.LiveSet) {
2651  assert(PointerToBase.count(Derived) && "Missed base for derived pointer");
2652  Bases.push_back(PointerToBase[Derived]);
2653  }
2654 
2655  insertUseHolderAfter(ToUpdate[i], Bases, Holders);
2656  }
2657 
2658  // By selecting base pointers, we've effectively inserted new uses. Thus, we
2659  // need to rerun liveness. We may *also* have inserted new defs, but that's
2660  // not the key issue.
2661  recomputeLiveInValues(F, DT, ToUpdate, Records, PointerToBase);
2662 
2663  if (PrintBasePointers) {
2664  errs() << "Base Pairs: (w/Relocation)\n";
2665  for (auto Pair : PointerToBase) {
2666  errs() << " derived ";
2667  Pair.first->printAsOperand(errs(), false);
2668  errs() << " base ";
2669  Pair.second->printAsOperand(errs(), false);
2670  errs() << "\n";
2671  }
2672  }
2673 
2674  // It is possible that non-constant live variables have a constant base. For
2675  // example, a GEP with a variable offset from a global. In this case we can
2676  // remove it from the liveset. We already don't add constants to the liveset
2677  // because we assume they won't move at runtime and the GC doesn't need to be
2678  // informed about them. The same reasoning applies if the base is constant.
2679  // Note that the relocation placement code relies on this filtering for
2680  // correctness as it expects the base to be in the liveset, which isn't true
2681  // if the base is constant.
2682  for (auto &Info : Records) {
2683  Info.LiveSet.remove_if([&](Value *LiveV) {
2684  assert(PointerToBase.count(LiveV) && "Missed base for derived pointer");
2685  return isa<Constant>(PointerToBase[LiveV]);
2686  });
2687  }
2688 
2689  for (CallInst *CI : Holders)
2690  CI->eraseFromParent();
2691 
2692  Holders.clear();
2693 
2694  // Compute the cost of possible re-materialization of derived pointers.
2695  RematCandTy RematerizationCandidates;
2696  findRematerializationCandidates(PointerToBase, RematerizationCandidates, TTI);
2697 
2698  // In order to reduce live set of statepoint we might choose to rematerialize
2699  // some values instead of relocating them. This is purely an optimization and
2700  // does not influence correctness.
2701  for (size_t i = 0; i < Records.size(); i++)
2702  rematerializeLiveValues(ToUpdate[i], Records[i], PointerToBase,
2703  RematerizationCandidates, TTI);
2704 
2705  // We need this to safely RAUW and delete call or invoke return values that
2706  // may themselves be live over a statepoint. For details, please see usage in
2707  // makeStatepointExplicitImpl.
2708  std::vector<DeferredReplacement> Replacements;
2709 
2710  // Now run through and replace the existing statepoints with new ones with
2711  // the live variables listed. We do not yet update uses of the values being
2712  // relocated. We have references to live variables that need to
2713  // survive to the last iteration of this loop. (By construction, the
2714  // previous statepoint can not be a live variable, thus we can and remove
2715  // the old statepoint calls as we go.)
2716  for (size_t i = 0; i < Records.size(); i++)
2717  makeStatepointExplicit(DT, ToUpdate[i], Records[i], Replacements,
2718  PointerToBase);
2719 
2720  ToUpdate.clear(); // prevent accident use of invalid calls.
2721 
2722  for (auto &PR : Replacements)
2723  PR.doReplacement();
2724 
2725  Replacements.clear();
2726 
2727  for (auto &Info : Records) {
2728  // These live sets may contain state Value pointers, since we replaced calls
2729  // with operand bundles with calls wrapped in gc.statepoint, and some of
2730  // those calls may have been def'ing live gc pointers. Clear these out to
2731  // avoid accidentally using them.
2732  //
2733  // TODO: We should create a separate data structure that does not contain
2734  // these live sets, and migrate to using that data structure from this point
2735  // onward.
2736  Info.LiveSet.clear();
2737  }
2738  PointerToBase.clear();
2739 
2740  // Do all the fixups of the original live variables to their relocated selves
2742  for (size_t i = 0; i < Records.size(); i++) {
2743  PartiallyConstructedSafepointRecord &Info = Records[i];
2744 
2745  // We can't simply save the live set from the original insertion. One of
2746  // the live values might be the result of a call which needs a safepoint.
2747  // That Value* no longer exists and we need to use the new gc_result.
2748  // Thankfully, the live set is embedded in the statepoint (and updated), so
2749  // we just grab that.
2750  llvm::append_range(Live, Info.StatepointToken->gc_args());
2751 #ifndef NDEBUG
2752  // Do some basic validation checking on our liveness results before
2753  // performing relocation. Relocation can and will turn mistakes in liveness
2754  // results into non-sensical code which is must harder to debug.
2755  // TODO: It would be nice to test consistency as well
2756  assert(DT.isReachableFromEntry(Info.StatepointToken->getParent()) &&
2757  "statepoint must be reachable or liveness is meaningless");
2758  for (Value *V : Info.StatepointToken->gc_args()) {
2759  if (!isa<Instruction>(V))
2760  // Non-instruction values trivial dominate all possible uses
2761  continue;
2762  auto *LiveInst = cast<Instruction>(V);
2763  assert(DT.isReachableFromEntry(LiveInst->getParent()) &&
2764  "unreachable values should never be live");
2765  assert(DT.dominates(LiveInst, Info.StatepointToken) &&
2766  "basic SSA liveness expectation violated by liveness analysis");
2767  }
2768 #endif
2769  }
2770  unique_unsorted(Live);
2771 
2772 #ifndef NDEBUG
2773  // Validation check
2774  for (auto *Ptr : Live)
2775  assert(isHandledGCPointerType(Ptr->getType()) &&
2776  "must be a gc pointer type");
2777 #endif
2778 
2779  relocationViaAlloca(F, DT, Live, Records);
2780  return !Records.empty();
2781 }
2782 
2783 // List of all parameter and return attributes which must be stripped when
2784 // lowering from the abstract machine model. Note that we list attributes
2785 // here which aren't valid as return attributes, that is okay.
2787  AttributeMask R;
2788  R.addAttribute(Attribute::Dereferenceable);
2789  R.addAttribute(Attribute::DereferenceableOrNull);
2790  R.addAttribute(Attribute::ReadNone);
2791  R.addAttribute(Attribute::ReadOnly);
2792  R.addAttribute(Attribute::WriteOnly);
2793  R.addAttribute(Attribute::NoAlias);
2794  R.addAttribute(Attribute::NoFree);
2795  return R;
2796 }
2797 
2799  LLVMContext &Ctx = F.getContext();
2800 
2801  // Intrinsics are very delicate. Lowering sometimes depends the presence
2802  // of certain attributes for correctness, but we may have also inferred
2803  // additional ones in the abstract machine model which need stripped. This
2804  // assumes that the attributes defined in Intrinsic.td are conservatively
2805  // correct for both physical and abstract model.
2806  if (Intrinsic::ID id = F.getIntrinsicID()) {
2807  F.setAttributes(Intrinsic::getAttributes(Ctx, id));
2808  return;
2809  }
2810 
2812  for (Argument &A : F.args())
2813  if (isa<PointerType>(A.getType()))
2814  F.removeParamAttrs(A.getArgNo(), R);
2815 
2816  if (isa<PointerType>(F.getReturnType()))
2817  F.removeRetAttrs(R);
2818 
2819  for (auto Attr : FnAttrsToStrip)
2820  F.removeFnAttr(Attr);
2821 }
2822 
2823 /// Certain metadata on instructions are invalid after running RS4GC.
2824 /// Optimizations that run after RS4GC can incorrectly use this metadata to
2825 /// optimize functions. We drop such metadata on the instruction.
2827  if (!isa<LoadInst>(I) && !isa<StoreInst>(I))
2828  return;
2829  // These are the attributes that are still valid on loads and stores after
2830  // RS4GC.
2831  // The metadata implying dereferenceability and noalias are (conservatively)
2832  // dropped. This is because semantically, after RewriteStatepointsForGC runs,
2833  // all calls to gc.statepoint "free" the entire heap. Also, gc.statepoint can
2834  // touch the entire heap including noalias objects. Note: The reasoning is
2835  // same as stripping the dereferenceability and noalias attributes that are
2836  // analogous to the metadata counterparts.
2837  // We also drop the invariant.load metadata on the load because that metadata
2838  // implies the address operand to the load points to memory that is never
2839  // changed once it became dereferenceable. This is no longer true after RS4GC.
2840  // Similar reasoning applies to invariant.group metadata, which applies to
2841  // loads within a group.
2842  unsigned ValidMetadataAfterRS4GC[] = {LLVMContext::MD_tbaa,
2843  LLVMContext::MD_range,
2844  LLVMContext::MD_alias_scope,
2845  LLVMContext::MD_nontemporal,
2846  LLVMContext::MD_nonnull,
2847  LLVMContext::MD_align,
2848  LLVMContext::MD_type};
2849 
2850  // Drops all metadata on the instruction other than ValidMetadataAfterRS4GC.
2851  I.dropUnknownNonDebugMetadata(ValidMetadataAfterRS4GC);
2852 }
2853 
2855  if (F.empty())
2856  return;
2857 
2858  LLVMContext &Ctx = F.getContext();
2859  MDBuilder Builder(Ctx);
2860 
2861  // Set of invariantstart instructions that we need to remove.
2862  // Use this to avoid invalidating the instruction iterator.
2863  SmallVector<IntrinsicInst*, 12> InvariantStartInstructions;
2864 
2865  for (Instruction &I : instructions(F)) {
2866  // invariant.start on memory location implies that the referenced memory
2867  // location is constant and unchanging. This is no longer true after
2868  // RewriteStatepointsForGC runs because there can be calls to gc.statepoint
2869  // which frees the entire heap and the presence of invariant.start allows
2870  // the optimizer to sink the load of a memory location past a statepoint,
2871  // which is incorrect.
2872  if (auto *II = dyn_cast<IntrinsicInst>(&I))
2873  if (II->getIntrinsicID() == Intrinsic::invariant_start) {
2874  InvariantStartInstructions.push_back(II);
2875  continue;
2876  }
2877 
2878  if (MDNode *Tag = I.getMetadata(LLVMContext::MD_tbaa)) {
2879  MDNode *MutableTBAA = Builder.createMutableTBAAAccessTag(Tag);
2880  I.setMetadata(LLVMContext::MD_tbaa, MutableTBAA);
2881  }
2882 
2884 
2886  if (auto *Call = dyn_cast<CallBase>(&I)) {
2887  for (int i = 0, e = Call->arg_size(); i != e; i++)
2888  if (isa<PointerType>(Call->getArgOperand(i)->getType()))
2889  Call->removeParamAttrs(i, R);
2890  if (isa<PointerType>(Call->getType()))
2891  Call->removeRetAttrs(R);
2892  }
2893  }
2894 
2895  // Delete the invariant.start instructions and RAUW undef.
2896  for (auto *II : InvariantStartInstructions) {
2897  II->replaceAllUsesWith(UndefValue::get(II->getType()));
2898  II->eraseFromParent();
2899  }
2900 }
2901 
2902 /// Returns true if this function should be rewritten by this pass. The main
2903 /// point of this function is as an extension point for custom logic.
2905  // TODO: This should check the GCStrategy
2906  if (F.hasGC()) {
2907  const auto &FunctionGCName = F.getGC();
2908  const StringRef StatepointExampleName("statepoint-example");
2909  const StringRef CoreCLRName("coreclr");
2910  return (StatepointExampleName == FunctionGCName) ||
2911  (CoreCLRName == FunctionGCName);
2912  } else
2913  return false;
2914 }
2915 
2916 static void stripNonValidData(Module &M) {
2917 #ifndef NDEBUG
2918  assert(llvm::any_of(M, shouldRewriteStatepointsIn) && "precondition!");
2919 #endif
2920 
2921  for (Function &F : M)
2923 
2924  for (Function &F : M)
2926 }
2927 
2930  const TargetLibraryInfo &TLI) {
2931  assert(!F.isDeclaration() && !F.empty() &&
2932  "need function body to rewrite statepoints in");
2933  assert(shouldRewriteStatepointsIn(F) && "mismatch in rewrite decision");
2934 
2935  auto NeedsRewrite = [&TLI](Instruction &I) {
2936  if (const auto *Call = dyn_cast<CallBase>(&I)) {
2937  if (isa<GCStatepointInst>(Call))
2938  return false;
2939  if (callsGCLeafFunction(Call, TLI))
2940  return false;
2941 
2942  // Normally it's up to the frontend to make sure that non-leaf calls also
2943  // have proper deopt state if it is required. We make an exception for
2944  // element atomic memcpy/memmove intrinsics here. Unlike other intrinsics
2945  // these are non-leaf by default. They might be generated by the optimizer
2946  // which doesn't know how to produce a proper deopt state. So if we see a
2947  // non-leaf memcpy/memmove without deopt state just treat it as a leaf
2948  // copy and don't produce a statepoint.
2950  !Call->getOperandBundle(LLVMContext::OB_deopt)) {
2951  assert((isa<AtomicMemCpyInst>(Call) || isa<AtomicMemMoveInst>(Call)) &&
2952  "Don't expect any other calls here!");
2953  return false;
2954  }
2955  return true;
2956  }
2957  return false;
2958  };
2959 
2960  // Delete any unreachable statepoints so that we don't have unrewritten
2961  // statepoints surviving this pass. This makes testing easier and the
2962  // resulting IR less confusing to human readers.
2964  bool MadeChange = removeUnreachableBlocks(F, &DTU);
2965  // Flush the Dominator Tree.
2966  DTU.getDomTree();
2967 
2968  // Gather all the statepoints which need rewritten. Be careful to only
2969  // consider those in reachable code since we need to ask dominance queries
2970  // when rewriting. We'll delete the unreachable ones in a moment.
2971  SmallVector<CallBase *, 64> ParsePointNeeded;
2972  SmallVector<CallInst *, 64> Intrinsics;
2973  for (Instruction &I : instructions(F)) {
2974  // TODO: only the ones with the flag set!
2975  if (NeedsRewrite(I)) {
2976  // NOTE removeUnreachableBlocks() is stronger than
2977  // DominatorTree::isReachableFromEntry(). In other words
2978  // removeUnreachableBlocks can remove some blocks for which
2979  // isReachableFromEntry() returns true.
2980  assert(DT.isReachableFromEntry(I.getParent()) &&
2981  "no unreachable blocks expected");
2982  ParsePointNeeded.push_back(cast<CallBase>(&I));
2983  }
2984  if (auto *CI = dyn_cast<CallInst>(&I))
2985  if (CI->getIntrinsicID() == Intrinsic::experimental_gc_get_pointer_base ||
2986  CI->getIntrinsicID() == Intrinsic::experimental_gc_get_pointer_offset)
2987  Intrinsics.emplace_back(CI);
2988  }
2989 
2990  // Return early if no work to do.
2991  if (ParsePointNeeded.empty() && Intrinsics.empty())
2992  return MadeChange;
2993 
2994  // As a prepass, go ahead and aggressively destroy single entry phi nodes.
2995  // These are created by LCSSA. They have the effect of increasing the size
2996  // of liveness sets for no good reason. It may be harder to do this post
2997  // insertion since relocations and base phis can confuse things.
2998  for (BasicBlock &BB : F)
2999  if (BB.getUniquePredecessor())
3000  MadeChange |= FoldSingleEntryPHINodes(&BB);
3001 
3002  // Before we start introducing relocations, we want to tweak the IR a bit to
3003  // avoid unfortunate code generation effects. The main example is that we
3004  // want to try to make sure the comparison feeding a branch is after any
3005  // safepoints. Otherwise, we end up with a comparison of pre-relocation
3006  // values feeding a branch after relocation. This is semantically correct,
3007  // but results in extra register pressure since both the pre-relocation and
3008  // post-relocation copies must be available in registers. For code without
3009  // relocations this is handled elsewhere, but teaching the scheduler to
3010  // reverse the transform we're about to do would be slightly complex.
3011  // Note: This may extend the live range of the inputs to the icmp and thus
3012  // increase the liveset of any statepoint we move over. This is profitable
3013  // as long as all statepoints are in rare blocks. If we had in-register
3014  // lowering for live values this would be a much safer transform.
3015  auto getConditionInst = [](Instruction *TI) -> Instruction * {
3016  if (auto *BI = dyn_cast<BranchInst>(TI))
3017  if (BI->isConditional())
3018  return dyn_cast<Instruction>(BI->getCondition());
3019  // TODO: Extend this to handle switches
3020  return nullptr;
3021  };
3022  for (BasicBlock &BB : F) {
3023  Instruction *TI = BB.getTerminator();
3024  if (auto *Cond = getConditionInst(TI))
3025  // TODO: Handle more than just ICmps here. We should be able to move
3026  // most instructions without side effects or memory access.
3027  if (isa<ICmpInst>(Cond) && Cond->hasOneUse()) {
3028  MadeChange = true;
3029  Cond->moveBefore(TI);
3030  }
3031  }
3032 
3033  // Nasty workaround - The base computation code in the main algorithm doesn't
3034  // consider the fact that a GEP can be used to convert a scalar to a vector.
3035  // The right fix for this is to integrate GEPs into the base rewriting
3036  // algorithm properly, this is just a short term workaround to prevent
3037  // crashes by canonicalizing such GEPs into fully vector GEPs.
3038  for (Instruction &I : instructions(F)) {
3039  if (!isa<GetElementPtrInst>(I))
3040  continue;
3041 
3042  unsigned VF = 0;
3043  for (unsigned i = 0; i < I.getNumOperands(); i++)
3044  if (auto *OpndVTy = dyn_cast<VectorType>(I.getOperand(i)->getType())) {
3045  assert(VF == 0 ||
3046  VF == cast<FixedVectorType>(OpndVTy)->getNumElements());
3047  VF = cast<FixedVectorType>(OpndVTy)->getNumElements();
3048  }
3049 
3050  // It's the vector to scalar traversal through the pointer operand which
3051  // confuses base pointer rewriting, so limit ourselves to that case.
3052  if (!I.getOperand(0)->getType()->isVectorTy() && VF != 0) {
3053  IRBuilder<> B(&I);
3054  auto *Splat = B.CreateVectorSplat(VF, I.getOperand(0));
3055  I.setOperand(0, Splat);
3056  MadeChange = true;
3057  }
3058  }
3059 
3060  // Cache the 'defining value' relation used in the computation and
3061  // insertion of base phis and selects. This ensures that we don't insert
3062  // large numbers of duplicate base_phis. Use one cache for both
3063  // inlineGetBaseAndOffset() and insertParsePoints().
3064  DefiningValueMapTy DVCache;
3065 
3066  // Mapping between a base values and a flag indicating whether it's a known
3067  // base or not.
3068  IsKnownBaseMapTy KnownBases;
3069 
3070  if (!Intrinsics.empty())
3071  // Inline @gc.get.pointer.base() and @gc.get.pointer.offset() before finding
3072  // live references.
3073  MadeChange |= inlineGetBaseAndOffset(F, Intrinsics, DVCache, KnownBases);
3074 
3075  if (!ParsePointNeeded.empty())
3076  MadeChange |=
3077  insertParsePoints(F, DT, TTI, ParsePointNeeded, DVCache, KnownBases);
3078 
3079  return MadeChange;
3080 }
3081 
3082 // liveness computation via standard dataflow
3083 // -------------------------------------------------------------------
3084 
3085 // TODO: Consider using bitvectors for liveness, the set of potentially
3086 // interesting values should be small and easy to pre-compute.
3087 
3088 /// Compute the live-in set for the location rbegin starting from
3089 /// the live-out set of the basic block
3092  SetVector<Value *> &LiveTmp) {
3093  for (auto &I : make_range(Begin, End)) {
3094  // KILL/Def - Remove this definition from LiveIn
3095  LiveTmp.remove(&I);
3096 
3097  // Don't consider *uses* in PHI nodes, we handle their contribution to
3098  // predecessor blocks when we seed the LiveOut sets
3099  if (isa<PHINode>(I))
3100  continue;
3101 
3102  // USE - Add to the LiveIn set for this instruction
3103  for (Value *V : I.operands()) {
3104  assert(!isUnhandledGCPointerType(V->getType()) &&
3105  "support for FCA unimplemented");
3106  if (isHandledGCPointerType(V->getType()) && !isa<Constant>(V)) {
3107  // The choice to exclude all things constant here is slightly subtle.
3108  // There are two independent reasons:
3109  // - We assume that things which are constant (from LLVM's definition)
3110  // do not move at runtime. For example, the address of a global
3111  // variable is fixed, even though it's contents may not be.
3112  // - Second, we can't disallow arbitrary inttoptr constants even
3113  // if the language frontend does. Optimization passes are free to
3114  // locally exploit facts without respect to global reachability. This
3115  // can create sections of code which are dynamically unreachable and
3116  // contain just about anything. (see constants.ll in tests)
3117  LiveTmp.insert(V);
3118  }
3119  }
3120  }
3121 }
3122 
3124  for (BasicBlock *Succ : successors(BB)) {
3125  for (auto &I : *Succ) {
3126  PHINode *PN = dyn_cast<PHINode>(&I);
3127  if (!PN)
3128  break;
3129 
3130  Value *V = PN->getIncomingValueForBlock(BB);
3132  "support for FCA unimplemented");
3133  if (isHandledGCPointerType(V->getType()) && !isa<Constant>(V))
3134  LiveTmp.insert(V);
3135  }
3136  }
3137 }
3138 
3140  SetVector<Value *> KillSet;
3141  for (Instruction &I : *BB)
3142  if (isHandledGCPointerType(I.getType()))
3143  KillSet.insert(&I);
3144  return KillSet;
3145 }
3146 
3147 #ifndef NDEBUG
3148 /// Check that the items in 'Live' dominate 'TI'. This is used as a basic
3149 /// validation check for the liveness computation.
3151  Instruction *TI, bool TermOkay = false) {
3152  for (Value *V : Live) {
3153  if (auto *I = dyn_cast<Instruction>(V)) {
3154  // The terminator can be a member of the LiveOut set. LLVM's definition
3155  // of instruction dominance states that V does not dominate itself. As
3156  // such, we need to special case this to allow it.
3157  if (TermOkay && TI == I)
3158  continue;
3159  assert(DT.dominates(I, TI) &&
3160  "basic SSA liveness expectation violated by liveness analysis");
3161  }
3162  }
3163 }
3164 
3165 /// Check that all the liveness sets used during the computation of liveness
3166 /// obey basic SSA properties. This is useful for finding cases where we miss
3167 /// a def.
3168 static void checkBasicSSA(DominatorTree &DT, GCPtrLivenessData &Data,
3169  BasicBlock &BB) {
3170  checkBasicSSA(DT, Data.LiveSet[&BB], BB.getTerminator());
3171  checkBasicSSA(DT, Data.LiveOut[&BB], BB.getTerminator(), true);
3172  checkBasicSSA(DT, Data.LiveIn[&BB], BB.getTerminator());
3173 }
3174 #endif
3175 
3177  GCPtrLivenessData &Data) {
3179 
3180  // Seed the liveness for each individual block
3181  for (BasicBlock &BB : F) {
3182  Data.KillSet[&BB] = computeKillSet(&BB);
3183  Data.LiveSet[&BB].clear();
3184  computeLiveInValues(BB.rbegin(), BB.rend(), Data.LiveSet[&BB]);
3185 
3186 #ifndef NDEBUG
3187  for (Value *Kill : Data.KillSet[&BB])
3188  assert(!Data.LiveSet[&BB].count(Kill) && "live set contains kill");
3189 #endif
3190 
3191  Data.LiveOut[&BB] = SetVector<Value *>();
3192  computeLiveOutSeed(&BB, Data.LiveOut[&BB]);
3193  Data.LiveIn[&BB] = Data.LiveSet[&BB];
3194  Data.LiveIn[&BB].set_union(Data.LiveOut[&BB]);
3195  Data.LiveIn[&BB].set_subtract(Data.KillSet[&BB]);
3196  if (!Data.LiveIn[&BB].empty())
3197  Worklist.insert(pred_begin(&BB), pred_end(&BB));
3198  }
3199 
3200  // Propagate that liveness until stable
3201  while (!Worklist.empty()) {
3202  BasicBlock *BB = Worklist.pop_back_val();
3203 
3204  // Compute our new liveout set, then exit early if it hasn't changed despite
3205  // the contribution of our successor.
3206  SetVector<Value *> LiveOut = Data.LiveOut[BB];
3207  const auto OldLiveOutSize = LiveOut.size();
3208  for (BasicBlock *Succ : successors(BB)) {
3209  assert(Data.LiveIn.count(Succ));
3210  LiveOut.set_union(Data.LiveIn[Succ]);
3211  }
3212  // assert OutLiveOut is a subset of LiveOut
3213  if (OldLiveOutSize == LiveOut.size()) {
3214  // If the sets are the same size, then we didn't actually add anything
3215  // when unioning our successors LiveIn. Thus, the LiveIn of this block
3216  // hasn't changed.
3217  continue;
3218  }
3219  Data.LiveOut[BB] = LiveOut;
3220 
3221  // Apply the effects of this basic block
3222  SetVector<Value *> LiveTmp = LiveOut;
3223  LiveTmp.set_union(Data.LiveSet[BB]);
3224  LiveTmp.set_subtract(Data.KillSet[BB]);
3225 
3226  assert(Data.LiveIn.count(BB));
3227  const SetVector<Value *> &OldLiveIn = Data.LiveIn[BB];
3228  // assert: OldLiveIn is a subset of LiveTmp
3229  if (OldLiveIn.size() != LiveTmp.size()) {
3230  Data.LiveIn[BB] = LiveTmp;
3231  Worklist.insert(pred_begin(BB), pred_end(BB));
3232  }
3233  } // while (!Worklist.empty())
3234 
3235 #ifndef NDEBUG
3236  // Verify our output against SSA properties. This helps catch any
3237  // missing kills during the above iteration.
3238  for (BasicBlock &BB : F)
3239  checkBasicSSA(DT, Data, BB);
3240 #endif
3241 }
3242 
3243 static void findLiveSetAtInst(Instruction *Inst, GCPtrLivenessData &Data,
3244  StatepointLiveSetTy &Out) {
3245  BasicBlock *BB = Inst->getParent();
3246 
3247  // Note: The copy is intentional and required
3248  assert(Data.LiveOut.count(BB));
3249  SetVector<Value *> LiveOut = Data.LiveOut[BB];
3250 
3251  // We want to handle the statepoint itself oddly. It's
3252  // call result is not live (normal), nor are it's arguments
3253  // (unless they're used again later). This adjustment is
3254  // specifically what we need to relocate
3255  computeLiveInValues(BB->rbegin(), ++Inst->getIterator().getReverse(),
3256  LiveOut);
3257  LiveOut.remove(Inst);
3258  Out.insert(LiveOut.begin(), LiveOut.end());
3259 }
3260 
3261 static void recomputeLiveInValues(GCPtrLivenessData &RevisedLivenessData,
3262  CallBase *Call,
3263  PartiallyConstructedSafepointRecord &Info,
3264  PointerToBaseTy &PointerToBase) {
3265  StatepointLiveSetTy Updated;
3266  findLiveSetAtInst(Call, RevisedLivenessData, Updated);
3267 
3268  // We may have base pointers which are now live that weren't before. We need
3269  // to update the PointerToBase structure to reflect this.
3270  for (auto *V : Updated)
3271  PointerToBase.insert({ V, V });
3272 
3273  Info.LiveSet = Updated;
3274 }
findBaseDefiningValueOfVector
static Value * findBaseDefiningValueOfVector(Value *I, DefiningValueMapTy &Cache, IsKnownBaseMapTy &KnownBases)
Return a base defining value for the 'Index' element of the given vector instruction 'I'.
Definition: RewriteStatepointsForGC.cpp:419
i
i
Definition: README.txt:29
llvm::InstructionCost
Definition: InstructionCost.h:30
llvm::LLVMContext::OB_deopt
@ OB_deopt
Definition: LLVMContext.h:89
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm::Argument
This class represents an incoming formal argument to a Function.
Definition: Argument.h:28
false::GCPtrLivenessData::LiveIn
MapVector< BasicBlock *, SetVector< Value * > > LiveIn
Values live into this basic block (i.e.
Definition: RewriteStatepointsForGC.cpp:243
insertRelocationStores
static void insertRelocationStores(iterator_range< Value::user_iterator > GCRelocs, DenseMap< Value *, AllocaInst * > &AllocaMap, DenseSet< Value * > &VisitedLiveValues)
Definition: RewriteStatepointsForGC.cpp:1932
stripInvalidMetadataFromInstruction
static void stripInvalidMetadataFromInstruction(Instruction &I)
Certain metadata on instructions are invalid after running RS4GC.
Definition: RewriteStatepointsForGC.cpp:2826
llvm::TargetIRAnalysis
Analysis pass providing the TargetTransformInfo.
Definition: TargetTransformInfo.h:2586
llvm::StatepointDirectives::StatepointID
std::optional< uint64_t > StatepointID
Definition: Statepoint.h:238
LLVM_DUMP_METHOD
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:492
llvm::LLVMContext::OB_gc_transition
@ OB_gc_transition
Definition: LLVMContext.h:91
false::PartiallyConstructedSafepointRecord::LiveSet
StatepointLiveSetTy LiveSet
The set of values known to be live across this safepoint.
Definition: RewriteStatepointsForGC.cpp:269
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::tgtok::Def
@ Def
Definition: TGLexer.h:50
ClobberNonLiveOverride
static cl::opt< bool, true > ClobberNonLiveOverride("rs4gc-clobber-non-live", cl::location(ClobberNonLive), cl::Hidden)
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::Instruction::getModule
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:69
false::GCPtrLivenessData
Definition: RewriteStatepointsForGC.cpp:233
insertUseHolderAfter
static void insertUseHolderAfter(CallBase *Call, const ArrayRef< Value * > Values, SmallVectorImpl< CallInst * > &Holders)
Insert holders so that each Value is obviously live through the entire lifetime of the call.
Definition: RewriteStatepointsForGC.cpp:2196
llvm::make_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:53
Optional.h
llvm::RewriteStatepointsForGC::runOnFunction
bool runOnFunction(Function &F, DominatorTree &, TargetTransformInfo &, const TargetLibraryInfo &)
Definition: RewriteStatepointsForGC.cpp:2928
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:113
llvm::AArch64PACKey::ID
ID
Definition: AArch64BaseInfo.h:818
llvm::Intrinsic::getDeclaration
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:1481
Metadata.h
llvm::Type::getInt8PtrTy
static PointerType * getInt8PtrTy(LLVMContext &C, unsigned AS=0)
Definition: Type.cpp:291
relocationViaAlloca
static void relocationViaAlloca(Function &F, DominatorTree &DT, ArrayRef< Value * > Live, ArrayRef< PartiallyConstructedSafepointRecord > Records)
Do all the relocation update via allocas and mem2reg.
Definition: RewriteStatepointsForGC.cpp:1988
llvm::ModulePass
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
Definition: Pass.h:248
IntrinsicInst.h
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:774
Scalar.h
llvm::initializeRewriteStatepointsForGCLegacyPassPass
void initializeRewriteStatepointsForGCLegacyPassPass(PassRegistry &)
InstIterator.h
computeLiveInValues
static void computeLiveInValues(DominatorTree &DT, Function &F, GCPtrLivenessData &Data)
Compute the live-in set for every basic block in the function.
Definition: RewriteStatepointsForGC.cpp:3176
T
AreEquivalentPhiNodes
static bool AreEquivalentPhiNodes(PHINode &OrigRootPhi, PHINode &AlternateRootPhi)
Definition: RewriteStatepointsForGC.cpp:2297
llvm::Function
Definition: Function.h:60
llvm::cl::location
LocationClass< Ty > location(Ty &L)
Definition: CommandLine.h:467
llvm::Attribute
Definition: Attributes.h:66
llvm::callsGCLeafFunction
bool callsGCLeafFunction(const CallBase *Call, const TargetLibraryInfo &TLI)
Return true if this call calls a gc leaf function.
Definition: Local.cpp:2849
llvm::PseudoProbeReservedId::Last
@ Last
StringRef.h
Pass.h
legalizeCallAttributes
static AttributeList legalizeCallAttributes(LLVMContext &Ctx, AttributeList OrigAL, AttributeList StatepointAL)
Definition: RewriteStatepointsForGC.cpp:1437
llvm::SetVector::size
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:77
llvm::BitCastInst
This class represents a no-op cast from one type to another.
Definition: Instructions.h:5256
llvm::AttributeList::addFnAttributes
AttributeList addFnAttributes(LLVMContext &C, const AttrBuilder &B) const
Add function attribute to the list.
Definition: Attributes.h:539
llvm::RewriteStatepointsForGC
Definition: RewriteStatepointsForGC.h:29
llvm::ilist_node_with_parent::getNextNode
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
Definition: ilist_node.h:289
llvm::TargetTransformInfo::getAddressComputationCost
InstructionCost getAddressComputationCost(Type *Ty, ScalarEvolution *SE=nullptr, const SCEV *Ptr=nullptr) const
Definition: TargetTransformInfo.cpp:989
llvm::SmallVector< Instruction *, 3 >
llvm::CallInst::setTailCallKind
void setTailCallKind(TailCallKind TCK)
Definition: Instructions.h:1677
containsGCPtrType
static bool containsGCPtrType(Type *Ty)
Returns true if this type contains a gc pointer whether we know how to handle that type or not.
Definition: RewriteStatepointsForGC.cpp:350
computeKillSet
static SetVector< Value * > computeKillSet(BasicBlock *BB)
Definition: RewriteStatepointsForGC.cpp:3139
llvm::Value::hasName
bool hasName() const
Definition: Value.h:261
ErrorHandling.h
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:173
llvm::Type::getPointerAddressSpace
unsigned getPointerAddressSpace() const
Get the address space of this pointer or pointer vector type.
Definition: DerivedTypes.h:729
ToRemove
ReachingDefAnalysis InstSet & ToRemove
Definition: ARMLowOverheadLoops.cpp:547
isOriginalBaseResult
static bool isOriginalBaseResult(Value *V)
This value is a base pointer that is not generated by RS4GC, i.e.
Definition: RewriteStatepointsForGC.cpp:723
llvm::IRBuilder<>
MapVector.h
DomTreeUpdater.h
llvm::erase_if
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
Definition: STLExtras.h:1997
llvm::SmallDenseMap
Definition: DenseMap.h:880
llvm::CallingConv::Cold
@ Cold
Attempts to make code in the caller as efficient as possible under the assumption that the call is no...
Definition: CallingConv.h:47
llvm::FunctionType::get
static FunctionType * get(Type *Result, ArrayRef< Type * > Params, bool isVarArg)
This static method is the primary way of constructing a FunctionType.
Definition: Type.cpp:361
Local.h
llvm::AttributeList::get
static AttributeList get(LLVMContext &C, ArrayRef< std::pair< unsigned, Attribute >> Attrs)
Create an AttributeList with the specified parameters in it.
Definition: Attributes.cpp:1131
llvm::Instruction::insertBefore
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
Definition: Instruction.cpp:87
isKnownBase
static bool isKnownBase(Value *V, const IsKnownBaseMapTy &KnownBases)
Returns true if V is a known base.
Definition: RewriteStatepointsForGC.cpp:731
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
FAM
FunctionAnalysisManager FAM
Definition: PassBuilderBindings.cpp:59
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:140
isGCPointerType
static bool isGCPointerType(Type *T)
Definition: RewriteStatepointsForGC.cpp:322
makeStatepointExplicit
static void makeStatepointExplicit(DominatorTree &DT, CallBase *Call, PartiallyConstructedSafepointRecord &Result, std::vector< DeferredReplacement > &Replacements, const PointerToBaseTy &PointerToBase)
Definition: RewriteStatepointsForGC.cpp:1902
llvm::ExtractElementInst::Create
static ExtractElementInst * Create(Value *Vec, Value *Idx, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Definition: Instructions.h:1885
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
DenseMap.h
llvm::removeUnreachableBlocks
bool removeUnreachableBlocks(Function &F, DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Remove all blocks that can not be reached from the function's entry.
Definition: Local.cpp:2581
Module.h
llvm::AttributeList
Definition: Attributes.h:430
llvm::AttributeMask
Definition: Attributes.h:977
llvm::CallBase::getAttributes
AttributeList getAttributes() const
Return the parameter attributes for this call.
Definition: InstrTypes.h:1475
stripNonValidAttributesFromPrototype
static void stripNonValidAttributesFromPrototype(Function &F)
Definition: RewriteStatepointsForGC.cpp:2798
llvm::SmallSet
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:136
llvm::AttributeList::getFnAttrs
AttributeSet getFnAttrs() const
The function attributes are returned.
Definition: Attributes.cpp:1469
false::PartiallyConstructedSafepointRecord::UnwindToken
Instruction * UnwindToken
Instruction to which exceptional gc relocates are attached Makes it easier to iterate through them du...
Definition: RewriteStatepointsForGC.cpp:277
llvm::operator!=
bool operator!=(uint64_t V1, const APInt &V2)
Definition: APInt.h:2012
llvm::Optional
Definition: APInt.h:33
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::count
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:145
Offset
uint64_t Offset
Definition: ELFObjHandler.cpp:80
llvm::MapVector
This class implements a map that also provides access to all stored values in a deterministic order.
Definition: MapVector.h:37
llvm::Intrinsic::getAttributes
AttributeList getAttributes(LLVMContext &C, ID id)
Return the attributes for an intrinsic.
llvm::SPII::Store
@ Store
Definition: SparcInstrInfo.h:33
at
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional ldr LCPI1_0 ldr ldr tst movne lsr ldr LCPI1_1 and r0 bx lr it saves an instruction and a register It might be profitable to cse MOVi16 if there are lots of bit immediates with the same bottom half Robert Muth started working on an alternate jump table implementation that does not put the tables in line in the text This is more like the llvm default jump table implementation This might be useful sometime Several revisions of patches are on the mailing beginning at
Definition: README.txt:582
llvm::PromoteMemToReg
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...
Definition: PromoteMemoryToRegister.cpp:1107
llvm::successors
auto successors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:29
llvm::errs
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
Definition: raw_ostream.cpp:891
llvm::MipsISD::Ret
@ Ret
Definition: MipsISelLowering.h:119
llvm::dump
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
Definition: SparseBitVector.h:877
STLExtras.h
llvm::ArrayType
Class to represent array types.
Definition: DerivedTypes.h:357
llvm::dwarf::Tag
Tag
Definition: Dwarf.h:105
llvm::detail::DenseSetImpl::insert
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
llvm::detail::DenseSetImpl::count
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:97
llvm::PHINode::setIncomingValue
void setIncomingValue(unsigned i, Value *V)
Definition: Instructions.h:2798
llvm::Data
@ Data
Definition: SIMachineScheduler.h:55
llvm::ArrayRef::empty
bool empty() const
empty - Check if the array is empty.
Definition: ArrayRef.h:159
llvm::createRewriteStatepointsForGCLegacyPass
ModulePass * createRewriteStatepointsForGCLegacyPass()
Definition: RewriteStatepointsForGC.cpp:218
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::MDNode::get
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
Definition: Metadata.h:1400
llvm::AttrBuilder::removeAttribute
AttrBuilder & removeAttribute(Attribute::AttrKind Val)
Remove an attribute from the builder.
Definition: Attributes.cpp:1711
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:265
llvm::Instruction::setMetadata
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
Definition: Metadata.cpp:1456
llvm::DomTreeUpdater::UpdateStrategy::Lazy
@ Lazy
Uses
SmallPtrSet< MachineInstr *, 2 > Uses
Definition: ARMLowOverheadLoops.cpp:590
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
findRematerializableChainToBasePointer
static Value * findRematerializableChainToBasePointer(SmallVectorImpl< Instruction * > &ChainToBase, Value *CurrentValue)
Definition: RewriteStatepointsForGC.cpp:2238
result
It looks like we only need to define PPCfmarto for these because according to these instructions perform RTO on fma s result
Definition: README_P9.txt:256
Context
LLVMContext & Context
Definition: NVVMIntrRange.cpp:66
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::GCStatepointInst
Represents a gc.statepoint intrinsic call.
Definition: Statepoint.h:62
llvm::DominatorTree::dominates
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:122
false::RematerizlizationCandidateRecord::ChainToBase
SmallVector< Instruction *, 3 > ChainToBase
Definition: RewriteStatepointsForGC.cpp:287
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:187
findRematerializationCandidates
static void findRematerializationCandidates(PointerToBaseTy PointerToBase, RematCandTy &RematerizationCandidates, TargetTransformInfo &TTI)
Definition: RewriteStatepointsForGC.cpp:2326
Instruction.h
CommandLine.h
llvm::SetVector::remove
bool remove(const value_type &X)
Remove an item from the set vector.
Definition: SetVector.h:157
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
false::PartiallyConstructedSafepointRecord
Definition: RewriteStatepointsForGC.cpp:267
llvm::TargetTransformInfo::getCastContextHint
static CastContextHint getCastContextHint(const Instruction *I)
Calculates a CastContextHint from I.
Definition: TargetTransformInfo.cpp:813
llvm::SetVector::begin
iterator begin()
Get an iterator to the beginning of the SetVector.
Definition: SetVector.h:82
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:24
rematerializeLiveValues
static void rematerializeLiveValues(CallBase *Call, PartiallyConstructedSafepointRecord &Info, PointerToBaseTy &PointerToBase, RematCandTy &RematerizationCandidates, TargetTransformInfo &TTI)
Definition: RewriteStatepointsForGC.cpp:2387
llvm::MutableArrayRef
MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...
Definition: ArrayRef.h:28
Constants.h
llvm::PHINode::getIncomingValue
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
Definition: Instructions.h:2795
chainToBasePointerCost
static InstructionCost chainToBasePointerCost(SmallVectorImpl< Instruction * > &Chain, TargetTransformInfo &TTI)
Definition: RewriteStatepointsForGC.cpp:2264
llvm::AllocaInst::getAllocatedType
Type * getAllocatedType() const
Return the type that is being allocated by the instruction.
Definition: Instructions.h:115
InlinePriorityMode::Cost
@ Cost
false::GCPtrLivenessData::KillSet
MapVector< BasicBlock *, SetVector< Value * > > KillSet
Values defined in this block.
Definition: RewriteStatepointsForGC.cpp:235
findBasePointers
static void findBasePointers(const StatepointLiveSetTy &live, PointerToBaseTy &PointerToBase, DominatorTree *DT, DefiningValueMapTy &DVCache, IsKnownBaseMapTy &KnownBases)
Definition: RewriteStatepointsForGC.cpp:1342
makeStatepointExplicitImpl
static void makeStatepointExplicitImpl(CallBase *Call, const SmallVectorImpl< Value * > &BasePtrs, const SmallVectorImpl< Value * > &LiveVariables, PartiallyConstructedSafepointRecord &Result, std::vector< DeferredReplacement > &Replacements, const PointerToBaseTy &PointerToBase)
Definition: RewriteStatepointsForGC.cpp:1609
llvm::User
Definition: User.h:44
Intrinsics.h
InstrTypes.h
llvm::CallBase::setAttributes
void setAttributes(AttributeList A)
Set the parameter attributes for this call.
Definition: InstrTypes.h:1479
llvm::BasicBlock::begin
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:306
false::RematerizlizationCandidateRecord::RootOfChain
Value * RootOfChain
Definition: RewriteStatepointsForGC.cpp:289
llvm::CallInst::Create
static CallInst * Create(FunctionType *Ty, Value *F, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Definition: Instructions.h:1517
isUnhandledGCPointerType
static bool isUnhandledGCPointerType(Type *Ty)
Definition: RewriteStatepointsForGC.cpp:365
SI
@ SI
Definition: SIInstrInfo.cpp:7966
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
insertRematerializationStores
static void insertRematerializationStores(const RematerializedValueMapTy &RematerializedValues, DenseMap< Value *, AllocaInst * > &AllocaMap, DenseSet< Value * > &VisitedLiveValues)
Definition: RewriteStatepointsForGC.cpp:1966
analyzeParsePointLiveness
static void analyzeParsePointLiveness(DominatorTree &DT, GCPtrLivenessData &OriginalLivenessData, CallBase *Call, PartiallyConstructedSafepointRecord &Result)
Definition: RewriteStatepointsForGC.cpp:381
IP
Definition: NVPTXLowerArgs.cpp:168
TargetLibraryInfo.h
getDeoptLowering
static StringRef getDeoptLowering(CallBase *Call)
Definition: RewriteStatepointsForGC.cpp:1593
RewriteStatepointsForGC.h
DenseSet.h
llvm::BasicBlock::getFirstInsertionPt
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:246
false
Definition: StackSlotColoring.cpp:141
ClobberNonLive
static bool ClobberNonLive
Definition: RewriteStatepointsForGC.cpp:102
llvm::dwarf::Index
Index
Definition: Dwarf.h:472
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
First
into llvm powi allowing the code generator to produce balanced multiplication trees First
Definition: README.txt:54
llvm::PHINode::getIncomingValueForBlock
Value * getIncomingValueForBlock(const BasicBlock *BB) const
Definition: Instructions.h:2884
llvm::Instruction
Definition: Instruction.h:42
statepoints
rewrite statepoints for Make relocations at statepoints
Definition: RewriteStatepointsForGC.cpp:229
llvm::AttributeList::hasFnAttr
bool hasFnAttr(Attribute::AttrKind Kind) const
Return true if the attribute exists for the function.
Definition: Attributes.cpp:1486
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:302
MDBuilder.h
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
llvm::Value::setName
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:375
llvm::operator<<
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:291
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1713
llvm::DomTreeUpdater
Definition: DomTreeUpdater.h:28
false::IsKnownBaseMapTy
MapVector< Value *, bool > IsKnownBaseMapTy
Definition: RewriteStatepointsForGC.cpp:261
llvm::SplitBlockPredecessors
BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock * > Preds, const char *Suffix, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, bool PreserveLCSSA=false)
This method introduces at least one new basic block into the function and moves some of the predecess...
Definition: BasicBlockUtils.cpp:1255
Info
Analysis containing CSE Info
Definition: CSEInfo.cpp:27
GetDeoptBundleOperands
static ArrayRef< Use > GetDeoptBundleOperands(const CallBase *Call)
Definition: RewriteStatepointsForGC.cpp:297
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(RewriteStatepointsForGCLegacyPass, "rewrite-statepoints-for-gc", "Make relocations explicit at statepoints", false, false) INITIALIZE_PASS_END(RewriteStatepointsForGCLegacyPass
areBothVectorOrScalar
static bool areBothVectorOrScalar(Value *First, Value *Second)
Definition: RewriteStatepointsForGC.cpp:748
llvm::BasicBlock::getFirstNonPHI
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
Definition: BasicBlock.cpp:209
llvm::FixedVectorType::get
static FixedVectorType * get(Type *ElementType, unsigned NumElts)
Definition: Type.cpp:684
llvm::MCID::Call
@ Call
Definition: MCInstrDesc.h:155
llvm::AddressSpace
AddressSpace
Definition: NVPTXBaseInfo.h:21
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::empty
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:72
llvm::Attribute::getValueAsString
StringRef getValueAsString() const
Return the attribute's value as a string.
Definition: Attributes.cpp:312
llvm::PHINode::getNumIncomingValues
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: Instructions.h:2791
false::GCPtrLivenessData::LiveOut
MapVector< BasicBlock *, SetVector< Value * > > LiveOut
Values live out of this basic block (i.e.
Definition: RewriteStatepointsForGC.cpp:247
Statepoint.h
insertParsePoints
static bool insertParsePoints(Function &F, DominatorTree &DT, TargetTransformInfo &TTI, SmallVectorImpl< CallBase * > &ToUpdate, DefiningValueMapTy &DVCache, IsKnownBaseMapTy &KnownBases)
Definition: RewriteStatepointsForGC.cpp:2558
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
PrintLiveSet
static cl::opt< bool > PrintLiveSet("spp-print-liveset", cl::Hidden, cl::init(false))
Type.h
normalizeForInvokeSafepoint
static BasicBlock * normalizeForInvokeSafepoint(BasicBlock *BB, BasicBlock *InvokeParent, DominatorTree &DT)
Definition: RewriteStatepointsForGC.cpp:1410
llvm::SetVector::set_union
bool set_union(const STy &S)
Compute This := This u S, return whether 'This' changed.
Definition: SetVector.h:250
setKnownBase
static void setKnownBase(Value *V, bool IsKnownBase, IsKnownBaseMapTy &KnownBases)
Caches the IsKnownBase flag for a value and asserts that it wasn't present in the cache before.
Definition: RewriteStatepointsForGC.cpp:737
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
llvm::StringRef::equals
bool equals(StringRef RHS) const
equals - Check for string equality, this is more efficient than compare() when the relative ordering ...
Definition: StringRef.h:164
llvm::InvokeInst
Invoke instruction.
Definition: Instructions.h:3811
llvm::ARM_PROC::IE
@ IE
Definition: ARMBaseInfo.h:27
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1682
llvm::VectorType
Base class of all SIMD vector types.
Definition: DerivedTypes.h:389
llvm::DenseSet< Value * >
false::DefiningValueMapTy
MapVector< Value *, Value * > DefiningValueMapTy
Definition: RewriteStatepointsForGC.cpp:260
BasicBlock.h
llvm::cl::opt< bool >
llvm::isStatepointDirectiveAttr
bool isStatepointDirectiveAttr(Attribute Attr)
Return true if the Attr is an attribute that is a statepoint directive.
Definition: Statepoint.cpp:18
llvm::AttributeList::ReturnIndex
@ ReturnIndex
Definition: Attributes.h:433
checkBasicSSA
static void checkBasicSSA(DominatorTree &DT, SetVector< Value * > &Live, Instruction *TI, bool TermOkay=false)
Check that the items in 'Live' dominate 'TI'.
Definition: RewriteStatepointsForGC.cpp:3150
llvm::instructions
inst_range instructions(Function *F)
Definition: InstIterator.h:133
llvm::IRBuilderBase::CreateBitCast
Value * CreateBitCast(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:1985
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:298
findBaseDefiningValueCached
static Value * findBaseDefiningValueCached(Value *I, DefiningValueMapTy &Cache, IsKnownBaseMapTy &KnownBases)
Returns the base defining value for this value.
Definition: RewriteStatepointsForGC.cpp:691
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:81
llvm::GCRelocateInst
Represents calls to the gc.relocate intrinsic.
Definition: IntrinsicInst.h:1469
findLiveSetAtInst
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...
Definition: RewriteStatepointsForGC.cpp:3243
llvm::StatepointFlags::None
@ None
Index
uint32_t Index
Definition: ELFObjHandler.cpp:83
llvm::TargetLibraryInfoWrapperPass
Definition: TargetLibraryInfo.h:475
uint64_t
llvm::pdb::Unknown
@ Unknown
Definition: PDBTypes.h:396
llvm::TargetTransformInfoWrapperPass
Wrapper pass for TargetTransformInfo.
Definition: TargetTransformInfo.h:2642
D
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
llvm::find
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1754
llvm::ARM_MB::ST
@ ST
Definition: ARMBaseInfo.h:73
llvm::GCRelocateInst::getDerivedPtr
Value * getDerivedPtr() const
Definition: IntrinsicInst.cpp:807
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::PreservedAnalyses::preserve
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:173
llvm::ConstantPointerNull::get
static ConstantPointerNull * get(PointerType *T)
Static factory methods - Return objects of the specified value.
Definition: Constants.cpp:1699
llvm::StatepointDirectives
Call sites that get wrapped by a gc.statepoint (currently only in RewriteStatepointsForGC and potenti...
Definition: Statepoint.h:236
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:67
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:53
PromoteMemToReg.h
llvm::DomTreeUpdater::getDomTree
DominatorTree & getDomTree()
Flush DomTree updates and return DomTree.
Definition: DomTreeUpdater.cpp:303
llvm::DenseMap
Definition: DenseMap.h:714
FnAttrsToStrip
static constexpr Attribute::AttrKind FnAttrsToStrip[]
Definition: RewriteStatepointsForGC.cpp:1432
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::AttrBuilder
Definition: Attributes.h:1038
llvm::SetVector::set_subtract
void set_subtract(const STy &S)
Compute This := This - B TODO: We should be able to use set_subtract from SetOperations....
Definition: SetVector.h:265
llvm::GetElementPtrInst
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:929
llvm::Attribute::AttrKind
AttrKind
This enumeration lists the attributes that can be associated with parameters, function results,...
Definition: Attributes.h:85
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:447
llvm::is_contained
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:1868
ArrayRef.h
llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, 4, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
IRBuilder.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::StatepointDirectives::NumPatchBytes
std::optional< uint32_t > NumPatchBytes
Definition: Statepoint.h:237
base
therefore end up llgh r3 lr r0 br r14 but truncating the load would lh r3 br r14 Functions ret i64 and ought to be implemented ngr r0 br r14 but two address optimizations reverse the order of the AND and ngr r2 lgr r0 br r14 CodeGen SystemZ and ll has several examples of this Out of range displacements are usually handled by loading the full address into a register In many cases it would be better to create an anchor point instead E g i64 base
Definition: README.txt:125
llvm::operator==
bool operator==(uint64_t V1, const APInt &V2)
Definition: APInt.h:2010
llvm::DominatorTree::isReachableFromEntry
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:335
Ptr
@ Ptr
Definition: TargetLibraryInfo.cpp:60
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1737
iterator_range.h
function
print Print MemDeps of function
Definition: MemDepPrinter.cpp:82
llvm::Record
Definition: Record.h:1573
llvm::TargetTransformInfo::getCastInstrCost
InstructionCost getCastInstrCost(unsigned Opcode, Type *Dst, Type *Src, TTI::CastContextHint CCH, TTI::TargetCostKind CostKind=TTI::TCK_SizeAndLatency, const Instruction *I=nullptr) const
Definition: TargetTransformInfo.cpp:856
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
llvm::MDNode
Metadata node.
Definition: Metadata.h:944
false::RematerializedValueMapTy
MapVector< AssertingVH< Instruction >, AssertingVH< Value > > RematerializedValueMapTy
Definition: RewriteStatepointsForGC.cpp:265
shouldRewriteStatepointsIn
static bool shouldRewriteStatepointsIn(Function &F)
Returns true if this function should be rewritten by this pass.
Definition: RewriteStatepointsForGC.cpp:2904
gc
rewrite statepoints for gc
Definition: RewriteStatepointsForGC.cpp:228
info
lazy value info
Definition: LazyValueInfo.cpp:59
Status
Definition: SIModeRegister.cpp:29
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:651
llvm::SetVector::insert
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
llvm::print
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr)
Definition: GCNRegPressure.cpp:138
AllowStatepointWithNoDeoptInfo
static cl::opt< bool > AllowStatepointWithNoDeoptInfo("rs4gc-allow-statepoint-with-no-deopt-info", cl::Hidden, cl::init(true))
false::PointerToBaseTy
MapVector< Value *, Value * > PointerToBaseTy
Definition: RewriteStatepointsForGC.cpp:262
llvm::Instruction::clone
Instruction * clone() const
Create a copy of 'this' instruction that is identical in all ways except the following:
Definition: Instruction.cpp:899
getParamAndReturnAttributesToRemove
static AttributeMask getParamAndReturnAttributesToRemove()
Definition: RewriteStatepointsForGC.cpp:2786
llvm::Sched::Source
@ Source
Definition: TargetLowering.h:99
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
None.h
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::pop_back_val
T pop_back_val()
Definition: SetVector.h:232
llvm::MapVector::insert
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: MapVector.h:118
llvm::any_of
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:1741
DataLayout.h
llvm::StructType
Class to represent struct types.
Definition: DerivedTypes.h:213
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:138
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
llvm::TargetTransformInfo::TCK_SizeAndLatency
@ TCK_SizeAndLatency
The weighted sum of size and latency.
Definition: TargetTransformInfo.h:222
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
llvm::BasicBlock::getUniquePredecessor
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
Definition: BasicBlock.cpp:293
llvm::Value::replaceAllUsesWith
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:532
A
* A
Definition: README_ALTIVEC.txt:89
llvm::ms_demangle::IntrinsicFunctionKind::New
@ New
uint32_t
Compiler.h
llvm::append_range
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:2013
llvm::Value::getContext
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:994
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:82
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::CastInst
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:430
llvm::StatepointFlags::GCTransition
@ GCTransition
Indicates that this statepoint is a transition from GC-aware code to code that is not GC-aware.
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:308
for
this could be done in SelectionDAGISel along with other special for
Definition: README.txt:104
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:174
ValueHandle.h
llvm::User::replaceUsesOfWith
bool replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
Definition: User.cpp:21
llvm::OperandBundleUse::Inputs
ArrayRef< Use > Inputs
Definition: InstrTypes.h:1071
rewrite
static bool rewrite(Function &F)
Definition: PoisonChecking.cpp:255
llvm::FunctionCallee::getCallee
Value * getCallee()
Definition: DerivedTypes.h:184
Argument.h
isHandledGCPointerType
static bool isHandledGCPointerType(Type *T)
Definition: RewriteStatepointsForGC.cpp:335
CallingConv.h
Attributes.h
Constant.h
false::PartiallyConstructedSafepointRecord::StatepointToken
GCStatepointInst * StatepointToken
The new gc.statepoint instruction itself.
Definition: RewriteStatepointsForGC.cpp:273
findBaseDefiningValue
static Value * findBaseDefiningValue(Value *I, DefiningValueMapTy &Cache, IsKnownBaseMapTy &KnownBases)
Helper function for findBasePointer - Will return a value which either a) defines the base pointer fo...
Definition: RewriteStatepointsForGC.cpp:517
llvm::Type::getIntNTy
static IntegerType * getIntNTy(LLVMContext &C, unsigned N)
Definition: Type.cpp:243
llvm::None
constexpr std::nullopt_t None
Definition: None.h:27
llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, 4, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::end
iterator end()
Definition: DenseMap.h:84
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:348
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
llvm::ArrayRef::begin
iterator begin() const
Definition: ArrayRef.h:152
RematerializationThreshold
static cl::opt< unsigned > RematerializationThreshold("spp-rematerialization-threshold", cl::Hidden, cl::init(6))
llvm::SPII::Load
@ Load
Definition: SparcInstrInfo.h:32
llvm::pred_end
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:112
false::RematerizlizationCandidateRecord::Cost
InstructionCost Cost
Definition: RewriteStatepointsForGC.cpp:291
Casting.h
llvm::RegState::Kill
@ Kill
The last use of a register.
Definition: MachineInstrBuilder.h:48
Function.h
unique_unsorted
static void unique_unsorted(SmallVectorImpl< T > &Vec)
Implement a unique function which doesn't require we sort the input vector.
Definition: RewriteStatepointsForGC.cpp:2189
PrintLiveSetSize
static cl::opt< bool > PrintLiveSetSize("spp-print-liveset-size", cl::Hidden, cl::init(false))
inlineGetBaseAndOffset
static bool inlineGetBaseAndOffset(Function &F, SmallVectorImpl< CallInst * > &Intrinsics, DefiningValueMapTy &DVCache, IsKnownBaseMapTy &KnownBases)
Definition: RewriteStatepointsForGC.cpp:2506
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:226
llvm::User::operand_values
iterator_range< value_op_iterator > operand_values()
Definition: User.h:266
llvm::unique
auto unique(Range &&R, Predicate P)
Definition: STLExtras.h:1965
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:614
findBasePointer
static Value * findBasePointer(Value *I, DefiningValueMapTy &Cache, IsKnownBaseMapTy &KnownBases)
For a given value or instruction, figure out what base ptr its derived from.
Definition: RewriteStatepointsForGC.cpp:872
llvm::SmallSet::insert
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Definition: SmallSet.h:178
llvm::FoldSingleEntryPHINodes
bool FoldSingleEntryPHINodes(BasicBlock *BB, MemoryDependenceResults *MemDep=nullptr)
We know that BB has one predecessor.
Definition: BasicBlockUtils.cpp:144
computeLiveOutSeed
static void computeLiveOutSeed(BasicBlock *BB, SetVector< Value * > &LiveTmp)
Definition: RewriteStatepointsForGC.cpp:3123
llvm::IntrinsicInst
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:46
llvm::MDBuilder
Definition: MDBuilder.h:36
llvm::pred_begin
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:109
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:267
llvm::Type::getVoidTy
static Type * getVoidTy(LLVMContext &C)
Definition: Type.cpp:222
llvm::SetVector::end
iterator end()
Get an iterator to the end of the SetVector.
Definition: SetVector.h:92
llvm::BasicBlock::reverse_iterator
InstListType::reverse_iterator reverse_iterator
Definition: BasicBlock.h:89
Instructions.h
llvm::parseStatepointDirectivesFromAttrs
StatepointDirectives parseStatepointDirectivesFromAttrs(AttributeList AS)
Parse out statepoint directives from the function attributes present in AS.
Definition: Statepoint.cpp:24
SmallVector.h
llvm::ilist_iterator::getReverse
ilist_iterator< OptionsT, !IsReverse, IsConst > getReverse() const
Get a reverse iterator to the same node.
Definition: ilist_iterator.h:121
User.h
Dominators.h
stripNonValidData
static void stripNonValidData(Module &M)
The IR fed into RewriteStatepointsForGC may have had attributes and metadata implying dereferenceabil...
Definition: RewriteStatepointsForGC.cpp:2916
llvm::StatepointDirectives::DefaultStatepointID
static const uint64_t DefaultStatepointID
Definition: Statepoint.h:240
false::GCPtrLivenessData::LiveSet
MapVector< BasicBlock *, SetVector< Value * > > LiveSet
Values used in this block (and thus live); does not included values killed within this block.
Definition: RewriteStatepointsForGC.cpp:239
llvm::AssertingVH
Value handle that asserts if the Value is deleted.
Definition: ValueHandle.h:260
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:91
llvm::SmallVectorImpl::pop_back_val
T pop_back_val()
Definition: SmallVector.h:677
llvm::PHINode::getIncomingBlock
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Definition: Instructions.h:2815
llvm::ArrayRef::size
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:164
TargetTransformInfo.h
llvm::iterator_range
A range adaptor for a pair of iterators.
Definition: iterator_range.h:30
llvm::FunctionCallee
A handy container for a FunctionType+Callee-pointer pair, which can be passed around as a single enti...
Definition: DerivedTypes.h:165
llvm::PHINode
Definition: Instructions.h:2699
llvm::BasicBlock::getTerminator
const Instruction * 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.h:119
false::RematerizlizationCandidateRecord
Definition: RewriteStatepointsForGC.cpp:285
llvm::SmallVectorImpl< Value * >
recomputeLiveInValues
static void recomputeLiveInValues(GCPtrLivenessData &RevisedLivenessData, CallBase *Call, PartiallyConstructedSafepointRecord &result, PointerToBaseTy &PointerToBase)
Given an updated version of the dataflow liveness results, update the liveset and base pointer maps f...
Definition: RewriteStatepointsForGC.cpp:3261
llvm::reverse
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:485
CreateGCRelocates
static void CreateGCRelocates(ArrayRef< Value * > LiveVariables, ArrayRef< Value * > BasePtrs, Instruction *StatepointToken, IRBuilder<> &Builder)
Helper function to place all gc relocates necessary for the given statepoint.
Definition: RewriteStatepointsForGC.cpp:1465
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1175
llvm::BasicBlock::getLandingPadInst
const LandingPadInst * getLandingPadInst() const
Return the landingpad instruction associated with the landing pad.
Definition: BasicBlock.cpp:501
DerivedTypes.h
llvm::SmallSetVector
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:307
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::StringRef::str
std::string str() const
str - Get the contents as an std::string.
Definition: StringRef.h:221
llvm::StatepointFlags::DeoptLiveIn
@ DeoptLiveIn
Mark the deopt arguments associated with the statepoint as only being "live-in".
llvm::InnerAnalysisManagerProxy
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:931
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1474
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
GEP
Hexagon Common GEP
Definition: HexagonCommonGEP.cpp:171
llvm::LiveVariables
Definition: LiveVariables.h:47
llvm::UnreachableInst
This function has undefined behavior.
Definition: Instructions.h:4771
suffixed_name_or
static std::string suffixed_name_or(Value *V, StringRef Suffix, StringRef DefaultName)
Definition: RewriteStatepointsForGC.cpp:372
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
LLVMContext.h
llvm::AllocaInst
an instruction to allocate memory on the stack
Definition: Instructions.h:59
false::PartiallyConstructedSafepointRecord::RematerializedValues
RematerializedValueMapTy RematerializedValues
Record live values we are rematerialized instead of relocating.
Definition: RewriteStatepointsForGC.cpp:282
llvm::RewriteStatepointsForGC::run
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
Definition: RewriteStatepointsForGC.cpp:128
raw_ostream.h
findLiveReferences
static void findLiveReferences(Function &F, DominatorTree &DT, ArrayRef< CallBase * > toUpdate, MutableArrayRef< struct PartiallyConstructedSafepointRecord > records)
Definition: RewriteStatepointsForGC.cpp:2221
llvm::SetVector< Value * >
llvm::ConstantAggregateZero::get
static ConstantAggregateZero * get(Type *Ty)
Definition: Constants.cpp:1587
llvm::SmallVectorImpl::reserve
void reserve(size_type N)
Definition: SmallVector.h:667
BasicBlockUtils.h
false::StatepointLiveSetTy
SetVector< Value * > StatepointLiveSetTy
Definition: RewriteStatepointsForGC.cpp:263
llvm::AttributeList::getFnAttr
Attribute getFnAttr(Attribute::AttrKind Kind) const
Return the attribute object that exists for the function.
Definition: Attributes.h:821
Value.h
stripNonValidDataFromBody
static void stripNonValidDataFromBody(Function &F)
Definition: RewriteStatepointsForGC.cpp:2854
InitializePasses.h
findBaseOrBDV
static Value * findBaseOrBDV(Value *I, DefiningValueMapTy &Cache, IsKnownBaseMapTy &KnownBases)
Return a base pointer for this value if known.
Definition: RewriteStatepointsForGC.cpp:708
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
PrintBasePointers
static cl::opt< bool > PrintBasePointers("spp-print-base-pointers", cl::Hidden, cl::init(false))
Debug.h
llvm::TargetLibraryAnalysis
Analysis pass providing the TargetLibraryInfo.
Definition: TargetLibraryInfo.h:450
llvm::Value::users
iterator_range< user_iterator > users()
Definition: Value.h:421
llvm::ArrayRef::end
iterator end() const
Definition: ArrayRef.h:153
llvm::AttributeList::isEmpty
bool isEmpty() const
Return true if there are no attributes.
Definition: Attributes.h:940
SetVector.h
llvm::sampleprof::Base
@ Base
Definition: Discriminator.h:58
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1251
llvm::CallBase::setCallingConv
void setCallingConv(CallingConv::ID CC)
Definition: InstrTypes.h:1460
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
llvm::SmallVectorImpl::emplace_back
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:941
SmallSet.h
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:39
false::RematCandTy
MapVector< Value *, RematerizlizationCandidateRecord > RematCandTy
Definition: RewriteStatepointsForGC.cpp:293