LLVM  15.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::ReadNone, Attribute::ReadOnly, Attribute::WriteOnly,
1434  Attribute::ArgMemOnly, Attribute::InaccessibleMemOnly,
1435  Attribute::InaccessibleMemOrArgMemOnly,
1436  Attribute::NoSync, Attribute::NoFree};
1437 
1438 // Create new attribute set containing only attributes which can be transferred
1439 // from original call to the safepoint.
1441  AttributeList OrigAL,
1442  AttributeList StatepointAL) {
1443  if (OrigAL.isEmpty())
1444  return StatepointAL;
1445 
1446  // Remove the readonly, readnone, and statepoint function attributes.
1447  AttrBuilder FnAttrs(Ctx, OrigAL.getFnAttrs());
1448  for (auto Attr : FnAttrsToStrip)
1449  FnAttrs.removeAttribute(Attr);
1450 
1451  for (Attribute A : OrigAL.getFnAttrs()) {
1453  FnAttrs.removeAttribute(A);
1454  }
1455 
1456  // Just skip parameter and return attributes for now
1457  return StatepointAL.addFnAttributes(Ctx, FnAttrs);
1458 }
1459 
1460 /// Helper function to place all gc relocates necessary for the given
1461 /// statepoint.
1462 /// Inputs:
1463 /// liveVariables - list of variables to be relocated.
1464 /// basePtrs - base pointers.
1465 /// statepointToken - statepoint instruction to which relocates should be
1466 /// bound.
1467 /// Builder - Llvm IR builder to be used to construct new calls.
1469  ArrayRef<Value *> BasePtrs,
1470  Instruction *StatepointToken,
1471  IRBuilder<> &Builder) {
1472  if (LiveVariables.empty())
1473  return;
1474 
1475  auto FindIndex = [](ArrayRef<Value *> LiveVec, Value *Val) {
1476  auto ValIt = llvm::find(LiveVec, Val);
1477  assert(ValIt != LiveVec.end() && "Val not found in LiveVec!");
1478  size_t Index = std::distance(LiveVec.begin(), ValIt);
1479  assert(Index < LiveVec.size() && "Bug in std::find?");
1480  return Index;
1481  };
1482  Module *M = StatepointToken->getModule();
1483 
1484  // All gc_relocate are generated as i8 addrspace(1)* (or a vector type whose
1485  // element type is i8 addrspace(1)*). We originally generated unique
1486  // declarations for each pointer type, but this proved problematic because
1487  // the intrinsic mangling code is incomplete and fragile. Since we're moving
1488  // towards a single unified pointer type anyways, we can just cast everything
1489  // to an i8* of the right address space. A bitcast is added later to convert
1490  // gc_relocate to the actual value's type.
1491  auto getGCRelocateDecl = [&] (Type *Ty) {
1493  auto AS = Ty->getScalarType()->getPointerAddressSpace();
1494  Type *NewTy = Type::getInt8PtrTy(M->getContext(), AS);
1495  if (auto *VT = dyn_cast<VectorType>(Ty))
1496  NewTy = FixedVectorType::get(NewTy,
1497  cast<FixedVectorType>(VT)->getNumElements());
1498  return Intrinsic::getDeclaration(M, Intrinsic::experimental_gc_relocate,
1499  {NewTy});
1500  };
1501 
1502  // Lazily populated map from input types to the canonicalized form mentioned
1503  // in the comment above. This should probably be cached somewhere more
1504  // broadly.
1505  DenseMap<Type *, Function *> TypeToDeclMap;
1506 
1507  for (unsigned i = 0; i < LiveVariables.size(); i++) {
1508  // Generate the gc.relocate call and save the result
1509  Value *BaseIdx = Builder.getInt32(FindIndex(LiveVariables, BasePtrs[i]));
1510  Value *LiveIdx = Builder.getInt32(i);
1511 
1512  Type *Ty = LiveVariables[i]->getType();
1513  if (!TypeToDeclMap.count(Ty))
1514  TypeToDeclMap[Ty] = getGCRelocateDecl(Ty);
1515  Function *GCRelocateDecl = TypeToDeclMap[Ty];
1516 
1517  // only specify a debug name if we can give a useful one
1518  CallInst *Reloc = Builder.CreateCall(
1519  GCRelocateDecl, {StatepointToken, BaseIdx, LiveIdx},
1520  suffixed_name_or(LiveVariables[i], ".relocated", ""));
1521  // Trick CodeGen into thinking there are lots of free registers at this
1522  // fake call.
1524  }
1525 }
1526 
1527 namespace {
1528 
1529 /// This struct is used to defer RAUWs and `eraseFromParent` s. Using this
1530 /// avoids having to worry about keeping around dangling pointers to Values.
1531 class DeferredReplacement {
1534  bool IsDeoptimize = false;
1535 
1536  DeferredReplacement() = default;
1537 
1538 public:
1539  static DeferredReplacement createRAUW(Instruction *Old, Instruction *New) {
1540  assert(Old != New && Old && New &&
1541  "Cannot RAUW equal values or to / from null!");
1542 
1543  DeferredReplacement D;
1544  D.Old = Old;
1545  D.New = New;
1546  return D;
1547  }
1548 
1549  static DeferredReplacement createDelete(Instruction *ToErase) {
1550  DeferredReplacement D;
1551  D.Old = ToErase;
1552  return D;
1553  }
1554 
1555  static DeferredReplacement createDeoptimizeReplacement(Instruction *Old) {
1556 #ifndef NDEBUG
1557  auto *F = cast<CallInst>(Old)->getCalledFunction();
1558  assert(F && F->getIntrinsicID() == Intrinsic::experimental_deoptimize &&
1559  "Only way to construct a deoptimize deferred replacement");
1560 #endif
1561  DeferredReplacement D;
1562  D.Old = Old;
1563  D.IsDeoptimize = true;
1564  return D;
1565  }
1566 
1567  /// Does the task represented by this instance.
1568  void doReplacement() {
1569  Instruction *OldI = Old;
1570  Instruction *NewI = New;
1571 
1572  assert(OldI != NewI && "Disallowed at construction?!");
1573  assert((!IsDeoptimize || !New) &&
1574  "Deoptimize intrinsics are not replaced!");
1575 
1576  Old = nullptr;
1577  New = nullptr;
1578 
1579  if (NewI)
1580  OldI->replaceAllUsesWith(NewI);
1581 
1582  if (IsDeoptimize) {
1583  // Note: we've inserted instructions, so the call to llvm.deoptimize may
1584  // not necessarily be followed by the matching return.
1585  auto *RI = cast<ReturnInst>(OldI->getParent()->getTerminator());
1586  new UnreachableInst(RI->getContext(), RI);
1587  RI->eraseFromParent();
1588  }
1589 
1590  OldI->eraseFromParent();
1591  }
1592 };
1593 
1594 } // end anonymous namespace
1595 
1597  const char *DeoptLowering = "deopt-lowering";
1598  if (Call->hasFnAttr(DeoptLowering)) {
1599  // FIXME: Calls have a *really* confusing interface around attributes
1600  // with values.
1601  const AttributeList &CSAS = Call->getAttributes();
1602  if (CSAS.hasFnAttr(DeoptLowering))
1603  return CSAS.getFnAttr(DeoptLowering).getValueAsString();
1604  Function *F = Call->getCalledFunction();
1605  assert(F && F->hasFnAttribute(DeoptLowering));
1606  return F->getFnAttribute(DeoptLowering).getValueAsString();
1607  }
1608  return "live-through";
1609 }
1610 
1611 static void
1612 makeStatepointExplicitImpl(CallBase *Call, /* to replace */
1613  const SmallVectorImpl<Value *> &BasePtrs,
1615  PartiallyConstructedSafepointRecord &Result,
1616  std::vector<DeferredReplacement> &Replacements,
1617  const PointerToBaseTy &PointerToBase) {
1618  assert(BasePtrs.size() == LiveVariables.size());
1619 
1620  // Then go ahead and use the builder do actually do the inserts. We insert
1621  // immediately before the previous instruction under the assumption that all
1622  // arguments will be available here. We can't insert afterwards since we may
1623  // be replacing a terminator.
1624  IRBuilder<> Builder(Call);
1625 
1628  uint32_t NumPatchBytes = 0;
1630 
1631  SmallVector<Value *, 8> CallArgs(Call->args());
1632  Optional<ArrayRef<Use>> DeoptArgs;
1633  if (auto Bundle = Call->getOperandBundle(LLVMContext::OB_deopt))
1634  DeoptArgs = Bundle->Inputs;
1635  Optional<ArrayRef<Use>> TransitionArgs;
1636  if (auto Bundle = Call->getOperandBundle(LLVMContext::OB_gc_transition)) {
1637  TransitionArgs = Bundle->Inputs;
1638  // TODO: This flag no longer serves a purpose and can be removed later
1640  }
1641 
1642  // Instead of lowering calls to @llvm.experimental.deoptimize as normal calls
1643  // with a return value, we lower then as never returning calls to
1644  // __llvm_deoptimize that are followed by unreachable to get better codegen.
1645  bool IsDeoptimize = false;
1646 
1648  parseStatepointDirectivesFromAttrs(Call->getAttributes());
1649  if (SD.NumPatchBytes)
1650  NumPatchBytes = *SD.NumPatchBytes;
1651  if (SD.StatepointID)
1652  StatepointID = *SD.StatepointID;
1653 
1654  // Pass through the requested lowering if any. The default is live-through.
1655  StringRef DeoptLowering = getDeoptLowering(Call);
1656  if (DeoptLowering.equals("live-in"))
1658  else {
1659  assert(DeoptLowering.equals("live-through") && "Unsupported value!");
1660  }
1661 
1662  FunctionCallee CallTarget(Call->getFunctionType(), Call->getCalledOperand());
1663  if (Function *F = dyn_cast<Function>(CallTarget.getCallee())) {
1664  auto IID = F->getIntrinsicID();
1665  if (IID == Intrinsic::experimental_deoptimize) {
1666  // Calls to llvm.experimental.deoptimize are lowered to calls to the
1667  // __llvm_deoptimize symbol. We want to resolve this now, since the
1668  // verifier does not allow taking the address of an intrinsic function.
1669 
1670  SmallVector<Type *, 8> DomainTy;
1671  for (Value *Arg : CallArgs)
1672  DomainTy.push_back(Arg->getType());
1673  auto *FTy = FunctionType::get(Type::getVoidTy(F->getContext()), DomainTy,
1674  /* isVarArg = */ false);
1675 
1676  // Note: CallTarget can be a bitcast instruction of a symbol if there are
1677  // calls to @llvm.experimental.deoptimize with different argument types in
1678  // the same module. This is fine -- we assume the frontend knew what it
1679  // was doing when generating this kind of IR.
1680  CallTarget = F->getParent()
1681  ->getOrInsertFunction("__llvm_deoptimize", FTy);
1682 
1683  IsDeoptimize = true;
1684  } else if (IID == Intrinsic::memcpy_element_unordered_atomic ||
1685  IID == Intrinsic::memmove_element_unordered_atomic) {
1686  // Unordered atomic memcpy and memmove intrinsics which are not explicitly
1687  // marked as "gc-leaf-function" should be lowered in a GC parseable way.
1688  // Specifically, these calls should be lowered to the
1689  // __llvm_{memcpy|memmove}_element_unordered_atomic_safepoint symbols.
1690  // Similarly to __llvm_deoptimize we want to resolve this now, since the
1691  // verifier does not allow taking the address of an intrinsic function.
1692  //
1693  // Moreover we need to shuffle the arguments for the call in order to
1694  // accommodate GC. The underlying source and destination objects might be
1695  // relocated during copy operation should the GC occur. To relocate the
1696  // derived source and destination pointers the implementation of the
1697  // intrinsic should know the corresponding base pointers.
1698  //
1699  // To make the base pointers available pass them explicitly as arguments:
1700  // memcpy(dest_derived, source_derived, ...) =>
1701  // memcpy(dest_base, dest_offset, source_base, source_offset, ...)
1702  auto &Context = Call->getContext();
1703  auto &DL = Call->getModule()->getDataLayout();
1704  auto GetBaseAndOffset = [&](Value *Derived) {
1705  assert(PointerToBase.count(Derived));
1706  unsigned AddressSpace = Derived->getType()->getPointerAddressSpace();
1707  unsigned IntPtrSize = DL.getPointerSizeInBits(AddressSpace);
1708  Value *Base = PointerToBase.find(Derived)->second;
1709  Value *Base_int = Builder.CreatePtrToInt(
1710  Base, Type::getIntNTy(Context, IntPtrSize));
1711  Value *Derived_int = Builder.CreatePtrToInt(
1712  Derived, Type::getIntNTy(Context, IntPtrSize));
1713  return std::make_pair(Base, Builder.CreateSub(Derived_int, Base_int));
1714  };
1715 
1716  auto *Dest = CallArgs[0];
1717  Value *DestBase, *DestOffset;
1718  std::tie(DestBase, DestOffset) = GetBaseAndOffset(Dest);
1719 
1720  auto *Source = CallArgs[1];
1721  Value *SourceBase, *SourceOffset;
1722  std::tie(SourceBase, SourceOffset) = GetBaseAndOffset(Source);
1723 
1724  auto *LengthInBytes = CallArgs[2];
1725  auto *ElementSizeCI = cast<ConstantInt>(CallArgs[3]);
1726 
1727  CallArgs.clear();
1728  CallArgs.push_back(DestBase);
1729  CallArgs.push_back(DestOffset);
1730  CallArgs.push_back(SourceBase);
1731  CallArgs.push_back(SourceOffset);
1732  CallArgs.push_back(LengthInBytes);
1733 
1734  SmallVector<Type *, 8> DomainTy;
1735  for (Value *Arg : CallArgs)
1736  DomainTy.push_back(Arg->getType());
1737  auto *FTy = FunctionType::get(Type::getVoidTy(F->getContext()), DomainTy,
1738  /* isVarArg = */ false);
1739 
1740  auto GetFunctionName = [](Intrinsic::ID IID, ConstantInt *ElementSizeCI) {
1741  uint64_t ElementSize = ElementSizeCI->getZExtValue();
1742  if (IID == Intrinsic::memcpy_element_unordered_atomic) {
1743  switch (ElementSize) {
1744  case 1:
1745  return "__llvm_memcpy_element_unordered_atomic_safepoint_1";
1746  case 2:
1747  return "__llvm_memcpy_element_unordered_atomic_safepoint_2";
1748  case 4:
1749  return "__llvm_memcpy_element_unordered_atomic_safepoint_4";
1750  case 8:
1751  return "__llvm_memcpy_element_unordered_atomic_safepoint_8";
1752  case 16:
1753  return "__llvm_memcpy_element_unordered_atomic_safepoint_16";
1754  default:
1755  llvm_unreachable("unexpected element size!");
1756  }
1757  }
1758  assert(IID == Intrinsic::memmove_element_unordered_atomic);
1759  switch (ElementSize) {
1760  case 1:
1761  return "__llvm_memmove_element_unordered_atomic_safepoint_1";
1762  case 2:
1763  return "__llvm_memmove_element_unordered_atomic_safepoint_2";
1764  case 4:
1765  return "__llvm_memmove_element_unordered_atomic_safepoint_4";
1766  case 8:
1767  return "__llvm_memmove_element_unordered_atomic_safepoint_8";
1768  case 16:
1769  return "__llvm_memmove_element_unordered_atomic_safepoint_16";
1770  default:
1771  llvm_unreachable("unexpected element size!");
1772  }
1773  };
1774 
1775  CallTarget =
1776  F->getParent()
1777  ->getOrInsertFunction(GetFunctionName(IID, ElementSizeCI), FTy);
1778  }
1779  }
1780 
1781  // Create the statepoint given all the arguments
1782  GCStatepointInst *Token = nullptr;
1783  if (auto *CI = dyn_cast<CallInst>(Call)) {
1784  CallInst *SPCall = Builder.CreateGCStatepointCall(
1785  StatepointID, NumPatchBytes, CallTarget, Flags, CallArgs,
1786  TransitionArgs, DeoptArgs, GCArgs, "safepoint_token");
1787 
1788  SPCall->setTailCallKind(CI->getTailCallKind());
1789  SPCall->setCallingConv(CI->getCallingConv());
1790 
1791  // Currently we will fail on parameter attributes and on certain
1792  // function attributes. In case if we can handle this set of attributes -
1793  // set up function attrs directly on statepoint and return attrs later for
1794  // gc_result intrinsic.
1796  CI->getContext(), CI->getAttributes(), SPCall->getAttributes()));
1797 
1798  Token = cast<GCStatepointInst>(SPCall);
1799 
1800  // Put the following gc_result and gc_relocate calls immediately after the
1801  // the old call (which we're about to delete)
1802  assert(CI->getNextNode() && "Not a terminator, must have next!");
1803  Builder.SetInsertPoint(CI->getNextNode());
1804  Builder.SetCurrentDebugLocation(CI->getNextNode()->getDebugLoc());
1805  } else {
1806  auto *II = cast<InvokeInst>(Call);
1807 
1808  // Insert the new invoke into the old block. We'll remove the old one in a
1809  // moment at which point this will become the new terminator for the
1810  // original block.
1811  InvokeInst *SPInvoke = Builder.CreateGCStatepointInvoke(
1812  StatepointID, NumPatchBytes, CallTarget, II->getNormalDest(),
1813  II->getUnwindDest(), Flags, CallArgs, TransitionArgs, DeoptArgs, GCArgs,
1814  "statepoint_token");
1815 
1816  SPInvoke->setCallingConv(II->getCallingConv());
1817 
1818  // Currently we will fail on parameter attributes and on certain
1819  // function attributes. In case if we can handle this set of attributes -
1820  // set up function attrs directly on statepoint and return attrs later for
1821  // gc_result intrinsic.
1823  II->getContext(), II->getAttributes(), SPInvoke->getAttributes()));
1824 
1825  Token = cast<GCStatepointInst>(SPInvoke);
1826 
1827  // Generate gc relocates in exceptional path
1828  BasicBlock *UnwindBlock = II->getUnwindDest();
1829  assert(!isa<PHINode>(UnwindBlock->begin()) &&
1830  UnwindBlock->getUniquePredecessor() &&
1831  "can't safely insert in this block!");
1832 
1833  Builder.SetInsertPoint(&*UnwindBlock->getFirstInsertionPt());
1834  Builder.SetCurrentDebugLocation(II->getDebugLoc());
1835 
1836  // Attach exceptional gc relocates to the landingpad.
1837  Instruction *ExceptionalToken = UnwindBlock->getLandingPadInst();
1838  Result.UnwindToken = ExceptionalToken;
1839 
1840  CreateGCRelocates(LiveVariables, BasePtrs, ExceptionalToken, Builder);
1841 
1842  // Generate gc relocates and returns for normal block
1843  BasicBlock *NormalDest = II->getNormalDest();
1844  assert(!isa<PHINode>(NormalDest->begin()) &&
1845  NormalDest->getUniquePredecessor() &&
1846  "can't safely insert in this block!");
1847 
1848  Builder.SetInsertPoint(&*NormalDest->getFirstInsertionPt());
1849 
1850  // gc relocates will be generated later as if it were regular call
1851  // statepoint
1852  }
1853  assert(Token && "Should be set in one of the above branches!");
1854 
1855  if (IsDeoptimize) {
1856  // If we're wrapping an @llvm.experimental.deoptimize in a statepoint, we
1857  // transform the tail-call like structure to a call to a void function
1858  // followed by unreachable to get better codegen.
1859  Replacements.push_back(
1860  DeferredReplacement::createDeoptimizeReplacement(Call));
1861  } else {
1862  Token->setName("statepoint_token");
1863  if (!Call->getType()->isVoidTy() && !Call->use_empty()) {
1864  StringRef Name = Call->hasName() ? Call->getName() : "";
1865  CallInst *GCResult = Builder.CreateGCResult(Token, Call->getType(), Name);
1866  GCResult->setAttributes(
1868  Call->getAttributes().getRetAttrs()));
1869 
1870  // We cannot RAUW or delete CS.getInstruction() because it could be in the
1871  // live set of some other safepoint, in which case that safepoint's
1872  // PartiallyConstructedSafepointRecord will hold a raw pointer to this
1873  // llvm::Instruction. Instead, we defer the replacement and deletion to
1874  // after the live sets have been made explicit in the IR, and we no longer
1875  // have raw pointers to worry about.
1876  Replacements.emplace_back(
1877  DeferredReplacement::createRAUW(Call, GCResult));
1878  } else {
1879  Replacements.emplace_back(DeferredReplacement::createDelete(Call));
1880  }
1881  }
1882 
1883  Result.StatepointToken = Token;
1884 
1885  // Second, create a gc.relocate for every live variable
1886  CreateGCRelocates(LiveVariables, BasePtrs, Token, Builder);
1887 }
1888 
1889 // Replace an existing gc.statepoint with a new one and a set of gc.relocates
1890 // which make the relocations happening at this safepoint explicit.
1891 //
1892 // WARNING: Does not do any fixup to adjust users of the original live
1893 // values. That's the callers responsibility.
1894 static void
1896  PartiallyConstructedSafepointRecord &Result,
1897  std::vector<DeferredReplacement> &Replacements,
1898  const PointerToBaseTy &PointerToBase) {
1899  const auto &LiveSet = Result.LiveSet;
1900 
1901  // Convert to vector for efficient cross referencing.
1902  SmallVector<Value *, 64> BaseVec, LiveVec;
1903  LiveVec.reserve(LiveSet.size());
1904  BaseVec.reserve(LiveSet.size());
1905  for (Value *L : LiveSet) {
1906  LiveVec.push_back(L);
1907  assert(PointerToBase.count(L));
1908  Value *Base = PointerToBase.find(L)->second;
1909  BaseVec.push_back(Base);
1910  }
1911  assert(LiveVec.size() == BaseVec.size());
1912 
1913  // Do the actual rewriting and delete the old statepoint
1914  makeStatepointExplicitImpl(Call, BaseVec, LiveVec, Result, Replacements,
1915  PointerToBase);
1916 }
1917 
1918 // Helper function for the relocationViaAlloca.
1919 //
1920 // It receives iterator to the statepoint gc relocates and emits a store to the
1921 // assigned location (via allocaMap) for the each one of them. It adds the
1922 // visited values into the visitedLiveValues set, which we will later use them
1923 // for validation checking.
1924 static void
1927  DenseSet<Value *> &VisitedLiveValues) {
1928  for (User *U : GCRelocs) {
1929  GCRelocateInst *Relocate = dyn_cast<GCRelocateInst>(U);
1930  if (!Relocate)
1931  continue;
1932 
1933  Value *OriginalValue = Relocate->getDerivedPtr();
1934  assert(AllocaMap.count(OriginalValue));
1935  Value *Alloca = AllocaMap[OriginalValue];
1936 
1937  // Emit store into the related alloca
1938  // All gc_relocates are i8 addrspace(1)* typed, and it must be bitcasted to
1939  // the correct type according to alloca.
1940  assert(Relocate->getNextNode() &&
1941  "Should always have one since it's not a terminator");
1942  IRBuilder<> Builder(Relocate->getNextNode());
1943  Value *CastedRelocatedValue =
1944  Builder.CreateBitCast(Relocate,
1945  cast<AllocaInst>(Alloca)->getAllocatedType(),
1946  suffixed_name_or(Relocate, ".casted", ""));
1947 
1948  new StoreInst(CastedRelocatedValue, Alloca,
1949  cast<Instruction>(CastedRelocatedValue)->getNextNode());
1950 
1951 #ifndef NDEBUG
1952  VisitedLiveValues.insert(OriginalValue);
1953 #endif
1954  }
1955 }
1956 
1957 // Helper function for the "relocationViaAlloca". Similar to the
1958 // "insertRelocationStores" but works for rematerialized values.
1960  const RematerializedValueMapTy &RematerializedValues,
1962  DenseSet<Value *> &VisitedLiveValues) {
1963  for (auto RematerializedValuePair: RematerializedValues) {
1964  Instruction *RematerializedValue = RematerializedValuePair.first;
1965  Value *OriginalValue = RematerializedValuePair.second;
1966 
1967  assert(AllocaMap.count(OriginalValue) &&
1968  "Can not find alloca for rematerialized value");
1969  Value *Alloca = AllocaMap[OriginalValue];
1970 
1971  new StoreInst(RematerializedValue, Alloca,
1972  RematerializedValue->getNextNode());
1973 
1974 #ifndef NDEBUG
1975  VisitedLiveValues.insert(OriginalValue);
1976 #endif
1977  }
1978 }
1979 
1980 /// Do all the relocation update via allocas and mem2reg
1984 #ifndef NDEBUG
1985  // record initial number of (static) allocas; we'll check we have the same
1986  // number when we get done.
1987  int InitialAllocaNum = 0;
1988  for (Instruction &I : F.getEntryBlock())
1989  if (isa<AllocaInst>(I))
1990  InitialAllocaNum++;
1991 #endif
1992 
1993  // TODO-PERF: change data structures, reserve
1995  SmallVector<AllocaInst *, 200> PromotableAllocas;
1996  // Used later to chack that we have enough allocas to store all values
1997  std::size_t NumRematerializedValues = 0;
1998  PromotableAllocas.reserve(Live.size());
1999 
2000  // Emit alloca for "LiveValue" and record it in "allocaMap" and
2001  // "PromotableAllocas"
2002  const DataLayout &DL = F.getParent()->getDataLayout();
2003  auto emitAllocaFor = [&](Value *LiveValue) {
2004  AllocaInst *Alloca = new AllocaInst(LiveValue->getType(),
2005  DL.getAllocaAddrSpace(), "",
2006  F.getEntryBlock().getFirstNonPHI());
2007  AllocaMap[LiveValue] = Alloca;
2008  PromotableAllocas.push_back(Alloca);
2009  };
2010 
2011  // Emit alloca for each live gc pointer
2012  for (Value *V : Live)
2013  emitAllocaFor(V);
2014 
2015  // Emit allocas for rematerialized values
2016  for (const auto &Info : Records)
2017  for (auto RematerializedValuePair : Info.RematerializedValues) {
2018  Value *OriginalValue = RematerializedValuePair.second;
2019  if (AllocaMap.count(OriginalValue) != 0)
2020  continue;
2021 
2022  emitAllocaFor(OriginalValue);
2023  ++NumRematerializedValues;
2024  }
2025 
2026  // The next two loops are part of the same conceptual operation. We need to
2027  // insert a store to the alloca after the original def and at each
2028  // redefinition. We need to insert a load before each use. These are split
2029  // into distinct loops for performance reasons.
2030 
2031  // Update gc pointer after each statepoint: either store a relocated value or
2032  // null (if no relocated value was found for this gc pointer and it is not a
2033  // gc_result). This must happen before we update the statepoint with load of
2034  // alloca otherwise we lose the link between statepoint and old def.
2035  for (const auto &Info : Records) {
2036  Value *Statepoint = Info.StatepointToken;
2037 
2038  // This will be used for consistency check
2039  DenseSet<Value *> VisitedLiveValues;
2040 
2041  // Insert stores for normal statepoint gc relocates
2042  insertRelocationStores(Statepoint->users(), AllocaMap, VisitedLiveValues);
2043 
2044  // In case if it was invoke statepoint
2045  // we will insert stores for exceptional path gc relocates.
2046  if (isa<InvokeInst>(Statepoint)) {
2047  insertRelocationStores(Info.UnwindToken->users(), AllocaMap,
2048  VisitedLiveValues);
2049  }
2050 
2051  // Do similar thing with rematerialized values
2052  insertRematerializationStores(Info.RematerializedValues, AllocaMap,
2053  VisitedLiveValues);
2054 
2055  if (ClobberNonLive) {
2056  // As a debugging aid, pretend that an unrelocated pointer becomes null at
2057  // the gc.statepoint. This will turn some subtle GC problems into
2058  // slightly easier to debug SEGVs. Note that on large IR files with
2059  // lots of gc.statepoints this is extremely costly both memory and time
2060  // wise.
2062  for (auto Pair : AllocaMap) {
2063  Value *Def = Pair.first;
2064  AllocaInst *Alloca = Pair.second;
2065 
2066  // This value was relocated
2067  if (VisitedLiveValues.count(Def)) {
2068  continue;
2069  }
2070  ToClobber.push_back(Alloca);
2071  }
2072 
2073  auto InsertClobbersAt = [&](Instruction *IP) {
2074  for (auto *AI : ToClobber) {
2075  auto PT = cast<PointerType>(AI->getAllocatedType());
2077  new StoreInst(CPN, AI, IP);
2078  }
2079  };
2080 
2081  // Insert the clobbering stores. These may get intermixed with the
2082  // gc.results and gc.relocates, but that's fine.
2083  if (auto II = dyn_cast<InvokeInst>(Statepoint)) {
2084  InsertClobbersAt(&*II->getNormalDest()->getFirstInsertionPt());
2085  InsertClobbersAt(&*II->getUnwindDest()->getFirstInsertionPt());
2086  } else {
2087  InsertClobbersAt(cast<Instruction>(Statepoint)->getNextNode());
2088  }
2089  }
2090  }
2091 
2092  // Update use with load allocas and add store for gc_relocated.
2093  for (auto Pair : AllocaMap) {
2094  Value *Def = Pair.first;
2095  AllocaInst *Alloca = Pair.second;
2096 
2097  // We pre-record the uses of allocas so that we dont have to worry about
2098  // later update that changes the user information..
2099 
2101  // PERF: trade a linear scan for repeated reallocation
2102  Uses.reserve(Def->getNumUses());
2103  for (User *U : Def->users()) {
2104  if (!isa<ConstantExpr>(U)) {
2105  // If the def has a ConstantExpr use, then the def is either a
2106  // ConstantExpr use itself or null. In either case
2107  // (recursively in the first, directly in the second), the oop
2108  // it is ultimately dependent on is null and this particular
2109  // use does not need to be fixed up.
2110  Uses.push_back(cast<Instruction>(U));
2111  }
2112  }
2113 
2114  llvm::sort(Uses);
2115  auto Last = std::unique(Uses.begin(), Uses.end());
2116  Uses.erase(Last, Uses.end());
2117 
2118  for (Instruction *Use : Uses) {
2119  if (isa<PHINode>(Use)) {
2120  PHINode *Phi = cast<PHINode>(Use);
2121  for (unsigned i = 0; i < Phi->getNumIncomingValues(); i++) {
2122  if (Def == Phi->getIncomingValue(i)) {
2123  LoadInst *Load =
2124  new LoadInst(Alloca->getAllocatedType(), Alloca, "",
2125  Phi->getIncomingBlock(i)->getTerminator());
2126  Phi->setIncomingValue(i, Load);
2127  }
2128  }
2129  } else {
2130  LoadInst *Load =
2131  new LoadInst(Alloca->getAllocatedType(), Alloca, "", Use);
2132  Use->replaceUsesOfWith(Def, Load);
2133  }
2134  }
2135 
2136  // Emit store for the initial gc value. Store must be inserted after load,
2137  // otherwise store will be in alloca's use list and an extra load will be
2138  // inserted before it.
2139  StoreInst *Store = new StoreInst(Def, Alloca, /*volatile*/ false,
2140  DL.getABITypeAlign(Def->getType()));
2141  if (Instruction *Inst = dyn_cast<Instruction>(Def)) {
2142  if (InvokeInst *Invoke = dyn_cast<InvokeInst>(Inst)) {
2143  // InvokeInst is a terminator so the store need to be inserted into its
2144  // normal destination block.
2145  BasicBlock *NormalDest = Invoke->getNormalDest();
2146  Store->insertBefore(NormalDest->getFirstNonPHI());
2147  } else {
2148  assert(!Inst->isTerminator() &&
2149  "The only terminator that can produce a value is "
2150  "InvokeInst which is handled above.");
2151  Store->insertAfter(Inst);
2152  }
2153  } else {
2154  assert(isa<Argument>(Def));
2155  Store->insertAfter(cast<Instruction>(Alloca));
2156  }
2157  }
2158 
2159  assert(PromotableAllocas.size() == Live.size() + NumRematerializedValues &&
2160  "we must have the same allocas with lives");
2161  (void) NumRematerializedValues;
2162  if (!PromotableAllocas.empty()) {
2163  // Apply mem2reg to promote alloca to SSA
2164  PromoteMemToReg(PromotableAllocas, DT);
2165  }
2166 
2167 #ifndef NDEBUG
2168  for (auto &I : F.getEntryBlock())
2169  if (isa<AllocaInst>(I))
2170  InitialAllocaNum--;
2171  assert(InitialAllocaNum == 0 && "We must not introduce any extra allocas");
2172 #endif
2173 }
2174 
2175 /// Implement a unique function which doesn't require we sort the input
2176 /// vector. Doing so has the effect of changing the output of a couple of
2177 /// tests in ways which make them less useful in testing fused safepoints.
2178 template <typename T> static void unique_unsorted(SmallVectorImpl<T> &Vec) {
2179  SmallSet<T, 8> Seen;
2180  erase_if(Vec, [&](const T &V) { return !Seen.insert(V).second; });
2181 }
2182 
2183 /// Insert holders so that each Value is obviously live through the entire
2184 /// lifetime of the call.
2185 static void insertUseHolderAfter(CallBase *Call, const ArrayRef<Value *> Values,
2186  SmallVectorImpl<CallInst *> &Holders) {
2187  if (Values.empty())
2188  // No values to hold live, might as well not insert the empty holder
2189  return;
2190 
2191  Module *M = Call->getModule();
2192  // Use a dummy vararg function to actually hold the values live
2193  FunctionCallee Func = M->getOrInsertFunction(
2194  "__tmp_use", FunctionType::get(Type::getVoidTy(M->getContext()), true));
2195  if (isa<CallInst>(Call)) {
2196  // For call safepoints insert dummy calls right after safepoint
2197  Holders.push_back(
2198  CallInst::Create(Func, Values, "", &*++Call->getIterator()));
2199  return;
2200  }
2201  // For invoke safepooints insert dummy calls both in normal and
2202  // exceptional destination blocks
2203  auto *II = cast<InvokeInst>(Call);
2204  Holders.push_back(CallInst::Create(
2205  Func, Values, "", &*II->getNormalDest()->getFirstInsertionPt()));
2206  Holders.push_back(CallInst::Create(
2207  Func, Values, "", &*II->getUnwindDest()->getFirstInsertionPt()));
2208 }
2209 
2211  Function &F, DominatorTree &DT, ArrayRef<CallBase *> toUpdate,
2213  GCPtrLivenessData OriginalLivenessData;
2214  computeLiveInValues(DT, F, OriginalLivenessData);
2215  for (size_t i = 0; i < records.size(); i++) {
2216  struct PartiallyConstructedSafepointRecord &info = records[i];
2217  analyzeParsePointLiveness(DT, OriginalLivenessData, toUpdate[i], info);
2218  }
2219 }
2220 
2221 // Helper function for the "rematerializeLiveValues". It walks use chain
2222 // starting from the "CurrentValue" until it reaches the root of the chain, i.e.
2223 // the base or a value it cannot process. Only "simple" values are processed
2224 // (currently it is GEP's and casts). The returned root is examined by the
2225 // callers of findRematerializableChainToBasePointer. Fills "ChainToBase" array
2226 // with all visited values.
2228  SmallVectorImpl<Instruction*> &ChainToBase,
2229  Value *CurrentValue) {
2230  if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(CurrentValue)) {
2231  ChainToBase.push_back(GEP);
2232  return findRematerializableChainToBasePointer(ChainToBase,
2233  GEP->getPointerOperand());
2234  }
2235 
2236  if (CastInst *CI = dyn_cast<CastInst>(CurrentValue)) {
2237  if (!CI->isNoopCast(CI->getModule()->getDataLayout()))
2238  return CI;
2239 
2240  ChainToBase.push_back(CI);
2241  return findRematerializableChainToBasePointer(ChainToBase,
2242  CI->getOperand(0));
2243  }
2244 
2245  // We have reached the root of the chain, which is either equal to the base or
2246  // is the first unsupported value along the use chain.
2247  return CurrentValue;
2248 }
2249 
2250 // Helper function for the "rematerializeLiveValues". Compute cost of the use
2251 // chain we are going to rematerialize.
2252 static InstructionCost
2255  InstructionCost Cost = 0;
2256 
2257  for (Instruction *Instr : Chain) {
2258  if (CastInst *CI = dyn_cast<CastInst>(Instr)) {
2259  assert(CI->isNoopCast(CI->getModule()->getDataLayout()) &&
2260  "non noop cast is found during rematerialization");
2261 
2262  Type *SrcTy = CI->getOperand(0)->getType();
2263  Cost += TTI.getCastInstrCost(CI->getOpcode(), CI->getType(), SrcTy,
2266 
2267  } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Instr)) {
2268  // Cost of the address calculation
2269  Type *ValTy = GEP->getSourceElementType();
2270  Cost += TTI.getAddressComputationCost(ValTy);
2271 
2272  // And cost of the GEP itself
2273  // TODO: Use TTI->getGEPCost here (it exists, but appears to be not
2274  // allowed for the external usage)
2275  if (!GEP->hasAllConstantIndices())
2276  Cost += 2;
2277 
2278  } else {
2279  llvm_unreachable("unsupported instruction type during rematerialization");
2280  }
2281  }
2282 
2283  return Cost;
2284 }
2285 
2286 static bool AreEquivalentPhiNodes(PHINode &OrigRootPhi, PHINode &AlternateRootPhi) {
2287  unsigned PhiNum = OrigRootPhi.getNumIncomingValues();
2288  if (PhiNum != AlternateRootPhi.getNumIncomingValues() ||
2289  OrigRootPhi.getParent() != AlternateRootPhi.getParent())
2290  return false;
2291  // Map of incoming values and their corresponding basic blocks of
2292  // OrigRootPhi.
2293  SmallDenseMap<Value *, BasicBlock *, 8> CurrentIncomingValues;
2294  for (unsigned i = 0; i < PhiNum; i++)
2295  CurrentIncomingValues[OrigRootPhi.getIncomingValue(i)] =
2296  OrigRootPhi.getIncomingBlock(i);
2297 
2298  // Both current and base PHIs should have same incoming values and
2299  // the same basic blocks corresponding to the incoming values.
2300  for (unsigned i = 0; i < PhiNum; i++) {
2301  auto CIVI =
2302  CurrentIncomingValues.find(AlternateRootPhi.getIncomingValue(i));
2303  if (CIVI == CurrentIncomingValues.end())
2304  return false;
2305  BasicBlock *CurrentIncomingBB = CIVI->second;
2306  if (CurrentIncomingBB != AlternateRootPhi.getIncomingBlock(i))
2307  return false;
2308  }
2309  return true;
2310 }
2311 
2312 // Find derived pointers that can be recomputed cheap enough and fill
2313 // RematerizationCandidates with such candidates.
2314 static void
2316  RematCandTy &RematerizationCandidates,
2318  const unsigned int ChainLengthThreshold = 10;
2319 
2320  for (auto P2B : PointerToBase) {
2321  auto *Derived = P2B.first;
2322  auto *Base = P2B.second;
2323  // Consider only derived pointers.
2324  if (Derived == Base)
2325  continue;
2326 
2327  // For each live pointer find its defining chain.
2328  SmallVector<Instruction *, 3> ChainToBase;
2329  Value *RootOfChain =
2330  findRematerializableChainToBasePointer(ChainToBase, Derived);
2331 
2332  // Nothing to do, or chain is too long
2333  if ( ChainToBase.size() == 0 ||
2334  ChainToBase.size() > ChainLengthThreshold)
2335  continue;
2336 
2337  // Handle the scenario where the RootOfChain is not equal to the
2338  // Base Value, but they are essentially the same phi values.
2339  if (RootOfChain != PointerToBase[Derived]) {
2340  PHINode *OrigRootPhi = dyn_cast<PHINode>(RootOfChain);
2341  PHINode *AlternateRootPhi = dyn_cast<PHINode>(PointerToBase[Derived]);
2342  if (!OrigRootPhi || !AlternateRootPhi)
2343  continue;
2344  // PHI nodes that have the same incoming values, and belonging to the same
2345  // basic blocks are essentially the same SSA value. When the original phi
2346  // has incoming values with different base pointers, the original phi is
2347  // marked as conflict, and an additional `AlternateRootPhi` with the same
2348  // incoming values get generated by the findBasePointer function. We need
2349  // to identify the newly generated AlternateRootPhi (.base version of phi)
2350  // and RootOfChain (the original phi node itself) are the same, so that we
2351  // can rematerialize the gep and casts. This is a workaround for the
2352  // deficiency in the findBasePointer algorithm.
2353  if (!AreEquivalentPhiNodes(*OrigRootPhi, *AlternateRootPhi))
2354  continue;
2355  }
2356  // Compute cost of this chain.
2357  InstructionCost Cost = chainToBasePointerCost(ChainToBase, TTI);
2358  // TODO: We can also account for cases when we will be able to remove some
2359  // of the rematerialized values by later optimization passes. I.e if
2360  // we rematerialized several intersecting chains. Or if original values
2361  // don't have any uses besides this statepoint.
2362 
2363  // Ok, there is a candidate.
2364  RematerizlizationCandidateRecord Record;
2365  Record.ChainToBase = ChainToBase;
2366  Record.RootOfChain = RootOfChain;
2367  Record.Cost = Cost;
2368  RematerizationCandidates.insert({ Derived, Record });
2369  }
2370 }
2371 
2372 // From the statepoint live set pick values that are cheaper to recompute then
2373 // to relocate. Remove this values from the live set, rematerialize them after
2374 // statepoint and record them in "Info" structure. Note that similar to
2375 // relocated values we don't do any user adjustments here.
2377  PartiallyConstructedSafepointRecord &Info,
2378  PointerToBaseTy &PointerToBase,
2379  RematCandTy &RematerizationCandidates,
2381  // Record values we are going to delete from this statepoint live set.
2382  // We can not di this in following loop due to iterator invalidation.
2383  SmallVector<Value *, 32> LiveValuesToBeDeleted;
2384 
2385  for (Value *LiveValue : Info.LiveSet) {
2386  auto It = RematerizationCandidates.find(LiveValue);
2387  if (It == RematerizationCandidates.end())
2388  continue;
2389 
2390  RematerizlizationCandidateRecord &Record = It->second;
2391 
2392  InstructionCost Cost = Record.Cost;
2393  // For invokes we need to rematerialize each chain twice - for normal and
2394  // for unwind basic blocks. Model this by multiplying cost by two.
2395  if (isa<InvokeInst>(Call))
2396  Cost *= 2;
2397 
2398  // If it's too expensive - skip it.
2399  if (Cost >= RematerializationThreshold)
2400  continue;
2401 
2402  // Remove value from the live set
2403  LiveValuesToBeDeleted.push_back(LiveValue);
2404 
2405  // Clone instructions and record them inside "Info" structure.
2406 
2407  // For each live pointer find get its defining chain.
2408  SmallVector<Instruction *, 3> ChainToBase = Record.ChainToBase;
2409  // Walk backwards to visit top-most instructions first.
2410  std::reverse(ChainToBase.begin(), ChainToBase.end());
2411 
2412  // Utility function which clones all instructions from "ChainToBase"
2413  // and inserts them before "InsertBefore". Returns rematerialized value
2414  // which should be used after statepoint.
2415  auto rematerializeChain = [&ChainToBase](
2416  Instruction *InsertBefore, Value *RootOfChain, Value *AlternateLiveBase) {
2417  Instruction *LastClonedValue = nullptr;
2418  Instruction *LastValue = nullptr;
2419  for (Instruction *Instr: ChainToBase) {
2420  // Only GEP's and casts are supported as we need to be careful to not
2421  // introduce any new uses of pointers not in the liveset.
2422  // Note that it's fine to introduce new uses of pointers which were
2423  // otherwise not used after this statepoint.
2424  assert(isa<GetElementPtrInst>(Instr) || isa<CastInst>(Instr));
2425 
2426  Instruction *ClonedValue = Instr->clone();
2427  ClonedValue->insertBefore(InsertBefore);
2428  ClonedValue->setName(Instr->getName() + ".remat");
2429 
2430  // If it is not first instruction in the chain then it uses previously
2431  // cloned value. We should update it to use cloned value.
2432  if (LastClonedValue) {
2433  assert(LastValue);
2434  ClonedValue->replaceUsesOfWith(LastValue, LastClonedValue);
2435 #ifndef NDEBUG
2436  for (auto OpValue : ClonedValue->operand_values()) {
2437  // Assert that cloned instruction does not use any instructions from
2438  // this chain other than LastClonedValue
2439  assert(!is_contained(ChainToBase, OpValue) &&
2440  "incorrect use in rematerialization chain");
2441  // Assert that the cloned instruction does not use the RootOfChain
2442  // or the AlternateLiveBase.
2443  assert(OpValue != RootOfChain && OpValue != AlternateLiveBase);
2444  }
2445 #endif
2446  } else {
2447  // For the first instruction, replace the use of unrelocated base i.e.
2448  // RootOfChain/OrigRootPhi, with the corresponding PHI present in the
2449  // live set. They have been proved to be the same PHI nodes. Note
2450  // that the *only* use of the RootOfChain in the ChainToBase list is
2451  // the first Value in the list.
2452  if (RootOfChain != AlternateLiveBase)
2453  ClonedValue->replaceUsesOfWith(RootOfChain, AlternateLiveBase);
2454  }
2455 
2456  LastClonedValue = ClonedValue;
2457  LastValue = Instr;
2458  }
2459  assert(LastClonedValue);
2460  return LastClonedValue;
2461  };
2462 
2463  // Different cases for calls and invokes. For invokes we need to clone
2464  // instructions both on normal and unwind path.
2465  if (isa<CallInst>(Call)) {
2466  Instruction *InsertBefore = Call->getNextNode();
2467  assert(InsertBefore);
2468  Instruction *RematerializedValue = rematerializeChain(
2469  InsertBefore, Record.RootOfChain, PointerToBase[LiveValue]);
2470  Info.RematerializedValues[RematerializedValue] = LiveValue;
2471  } else {
2472  auto *Invoke = cast<InvokeInst>(Call);
2473 
2474  Instruction *NormalInsertBefore =
2475  &*Invoke->getNormalDest()->getFirstInsertionPt();
2476  Instruction *UnwindInsertBefore =
2477  &*Invoke->getUnwindDest()->getFirstInsertionPt();
2478 
2479  Instruction *NormalRematerializedValue = rematerializeChain(
2480  NormalInsertBefore, Record.RootOfChain, PointerToBase[LiveValue]);
2481  Instruction *UnwindRematerializedValue = rematerializeChain(
2482  UnwindInsertBefore, Record.RootOfChain, PointerToBase[LiveValue]);
2483 
2484  Info.RematerializedValues[NormalRematerializedValue] = LiveValue;
2485  Info.RematerializedValues[UnwindRematerializedValue] = LiveValue;
2486  }
2487  }
2488 
2489  // Remove rematerializaed values from the live set
2490  for (auto LiveValue: LiveValuesToBeDeleted) {
2491  Info.LiveSet.remove(LiveValue);
2492  }
2493 }
2494 
2496  SmallVectorImpl<CallInst *> &Intrinsics,
2497  DefiningValueMapTy &DVCache,
2498  IsKnownBaseMapTy &KnownBases) {
2499  auto &Context = F.getContext();
2500  auto &DL = F.getParent()->getDataLayout();
2501  bool Changed = false;
2502 
2503  for (auto *Callsite : Intrinsics)
2504  switch (Callsite->getIntrinsicID()) {
2505  case Intrinsic::experimental_gc_get_pointer_base: {
2506  Changed = true;
2507  Value *Base =
2508  findBasePointer(Callsite->getOperand(0), DVCache, KnownBases);
2509  assert(!DVCache.count(Callsite));
2510  auto *BaseBC = IRBuilder<>(Callsite).CreateBitCast(
2511  Base, Callsite->getType(), suffixed_name_or(Base, ".cast", ""));
2512  if (BaseBC != Base)
2513  DVCache[BaseBC] = Base;
2514  Callsite->replaceAllUsesWith(BaseBC);
2515  if (!BaseBC->hasName())
2516  BaseBC->takeName(Callsite);
2517  Callsite->eraseFromParent();
2518  break;
2519  }
2520  case Intrinsic::experimental_gc_get_pointer_offset: {
2521  Changed = true;
2522  Value *Derived = Callsite->getOperand(0);
2523  Value *Base = findBasePointer(Derived, DVCache, KnownBases);
2524  assert(!DVCache.count(Callsite));
2525  unsigned AddressSpace = Derived->getType()->getPointerAddressSpace();
2526  unsigned IntPtrSize = DL.getPointerSizeInBits(AddressSpace);
2527  IRBuilder<> Builder(Callsite);
2528  Value *BaseInt =
2529  Builder.CreatePtrToInt(Base, Type::getIntNTy(Context, IntPtrSize),
2530  suffixed_name_or(Base, ".int", ""));
2531  Value *DerivedInt =
2532  Builder.CreatePtrToInt(Derived, Type::getIntNTy(Context, IntPtrSize),
2533  suffixed_name_or(Derived, ".int", ""));
2534  Value *Offset = Builder.CreateSub(DerivedInt, BaseInt);
2535  Callsite->replaceAllUsesWith(Offset);
2536  Offset->takeName(Callsite);
2537  Callsite->eraseFromParent();
2538  break;
2539  }
2540  default:
2541  llvm_unreachable("Unknown intrinsic");
2542  }
2543 
2544  return Changed;
2545 }
2546 
2549  SmallVectorImpl<CallBase *> &ToUpdate,
2550  DefiningValueMapTy &DVCache,
2551  IsKnownBaseMapTy &KnownBases) {
2552 #ifndef NDEBUG
2553  // Validate the input
2554  std::set<CallBase *> Uniqued;
2555  Uniqued.insert(ToUpdate.begin(), ToUpdate.end());
2556  assert(Uniqued.size() == ToUpdate.size() && "no duplicates please!");
2557 
2558  for (CallBase *Call : ToUpdate)
2559  assert(Call->getFunction() == &F);
2560 #endif
2561 
2562  // When inserting gc.relocates for invokes, we need to be able to insert at
2563  // the top of the successor blocks. See the comment on
2564  // normalForInvokeSafepoint on exactly what is needed. Note that this step
2565  // may restructure the CFG.
2566  for (CallBase *Call : ToUpdate) {
2567  auto *II = dyn_cast<InvokeInst>(Call);
2568  if (!II)
2569  continue;
2570  normalizeForInvokeSafepoint(II->getNormalDest(), II->getParent(), DT);
2571  normalizeForInvokeSafepoint(II->getUnwindDest(), II->getParent(), DT);
2572  }
2573 
2574  // A list of dummy calls added to the IR to keep various values obviously
2575  // live in the IR. We'll remove all of these when done.
2577 
2578  // Insert a dummy call with all of the deopt operands we'll need for the
2579  // actual safepoint insertion as arguments. This ensures reference operands
2580  // in the deopt argument list are considered live through the safepoint (and
2581  // thus makes sure they get relocated.)
2582  for (CallBase *Call : ToUpdate) {
2583  SmallVector<Value *, 64> DeoptValues;
2584 
2585  for (Value *Arg : GetDeoptBundleOperands(Call)) {
2586  assert(!isUnhandledGCPointerType(Arg->getType()) &&
2587  "support for FCA unimplemented");
2588  if (isHandledGCPointerType(Arg->getType()))
2589  DeoptValues.push_back(Arg);
2590  }
2591 
2592  insertUseHolderAfter(Call, DeoptValues, Holders);
2593  }
2594 
2596 
2597  // A) Identify all gc pointers which are statically live at the given call
2598  // site.
2599  findLiveReferences(F, DT, ToUpdate, Records);
2600 
2601  /// Global mapping from live pointers to a base-defining-value.
2602  PointerToBaseTy PointerToBase;
2603 
2604  // B) Find the base pointers for each live pointer
2605  for (size_t i = 0; i < Records.size(); i++) {
2606  PartiallyConstructedSafepointRecord &info = Records[i];
2607  findBasePointers(DT, DVCache, ToUpdate[i], info, PointerToBase, KnownBases);
2608  }
2609  if (PrintBasePointers) {
2610  errs() << "Base Pairs (w/o Relocation):\n";
2611  for (auto &Pair : PointerToBase) {
2612  errs() << " derived ";
2613  Pair.first->printAsOperand(errs(), false);
2614  errs() << " base ";
2615  Pair.second->printAsOperand(errs(), false);
2616  errs() << "\n";
2617  ;
2618  }
2619  }
2620 
2621  // The base phi insertion logic (for any safepoint) may have inserted new
2622  // instructions which are now live at some safepoint. The simplest such
2623  // example is:
2624  // loop:
2625  // phi a <-- will be a new base_phi here
2626  // safepoint 1 <-- that needs to be live here
2627  // gep a + 1
2628  // safepoint 2
2629  // br loop
2630  // We insert some dummy calls after each safepoint to definitely hold live
2631  // the base pointers which were identified for that safepoint. We'll then
2632  // ask liveness for _every_ base inserted to see what is now live. Then we
2633  // remove the dummy calls.
2634  Holders.reserve(Holders.size() + Records.size());
2635  for (size_t i = 0; i < Records.size(); i++) {
2636  PartiallyConstructedSafepointRecord &Info = Records[i];
2637 
2639  for (auto *Derived : Info.LiveSet) {
2640  assert(PointerToBase.count(Derived) && "Missed base for derived pointer");
2641  Bases.push_back(PointerToBase[Derived]);
2642  }
2643 
2644  insertUseHolderAfter(ToUpdate[i], Bases, Holders);
2645  }
2646 
2647  // By selecting base pointers, we've effectively inserted new uses. Thus, we
2648  // need to rerun liveness. We may *also* have inserted new defs, but that's
2649  // not the key issue.
2650  recomputeLiveInValues(F, DT, ToUpdate, Records, PointerToBase);
2651 
2652  if (PrintBasePointers) {
2653  errs() << "Base Pairs: (w/Relocation)\n";
2654  for (auto Pair : PointerToBase) {
2655  errs() << " derived ";
2656  Pair.first->printAsOperand(errs(), false);
2657  errs() << " base ";
2658  Pair.second->printAsOperand(errs(), false);
2659  errs() << "\n";
2660  }
2661  }
2662 
2663  // It is possible that non-constant live variables have a constant base. For
2664  // example, a GEP with a variable offset from a global. In this case we can
2665  // remove it from the liveset. We already don't add constants to the liveset
2666  // because we assume they won't move at runtime and the GC doesn't need to be
2667  // informed about them. The same reasoning applies if the base is constant.
2668  // Note that the relocation placement code relies on this filtering for
2669  // correctness as it expects the base to be in the liveset, which isn't true
2670  // if the base is constant.
2671  for (auto &Info : Records) {
2672  Info.LiveSet.remove_if([&](Value *LiveV) {
2673  assert(PointerToBase.count(LiveV) && "Missed base for derived pointer");
2674  return isa<Constant>(PointerToBase[LiveV]);
2675  });
2676  }
2677 
2678  for (CallInst *CI : Holders)
2679  CI->eraseFromParent();
2680 
2681  Holders.clear();
2682 
2683  // Compute the cost of possible re-materialization of derived pointers.
2684  RematCandTy RematerizationCandidates;
2685  findRematerializationCandidates(PointerToBase, RematerizationCandidates, TTI);
2686 
2687  // In order to reduce live set of statepoint we might choose to rematerialize
2688  // some values instead of relocating them. This is purely an optimization and
2689  // does not influence correctness.
2690  for (size_t i = 0; i < Records.size(); i++)
2691  rematerializeLiveValues(ToUpdate[i], Records[i], PointerToBase,
2692  RematerizationCandidates, TTI);
2693 
2694  // We need this to safely RAUW and delete call or invoke return values that
2695  // may themselves be live over a statepoint. For details, please see usage in
2696  // makeStatepointExplicitImpl.
2697  std::vector<DeferredReplacement> Replacements;
2698 
2699  // Now run through and replace the existing statepoints with new ones with
2700  // the live variables listed. We do not yet update uses of the values being
2701  // relocated. We have references to live variables that need to
2702  // survive to the last iteration of this loop. (By construction, the
2703  // previous statepoint can not be a live variable, thus we can and remove
2704  // the old statepoint calls as we go.)
2705  for (size_t i = 0; i < Records.size(); i++)
2706  makeStatepointExplicit(DT, ToUpdate[i], Records[i], Replacements,
2707  PointerToBase);
2708 
2709  ToUpdate.clear(); // prevent accident use of invalid calls.
2710 
2711  for (auto &PR : Replacements)
2712  PR.doReplacement();
2713 
2714  Replacements.clear();
2715 
2716  for (auto &Info : Records) {
2717  // These live sets may contain state Value pointers, since we replaced calls
2718  // with operand bundles with calls wrapped in gc.statepoint, and some of
2719  // those calls may have been def'ing live gc pointers. Clear these out to
2720  // avoid accidentally using them.
2721  //
2722  // TODO: We should create a separate data structure that does not contain
2723  // these live sets, and migrate to using that data structure from this point
2724  // onward.
2725  Info.LiveSet.clear();
2726  }
2727  PointerToBase.clear();
2728 
2729  // Do all the fixups of the original live variables to their relocated selves
2731  for (size_t i = 0; i < Records.size(); i++) {
2732  PartiallyConstructedSafepointRecord &Info = Records[i];
2733 
2734  // We can't simply save the live set from the original insertion. One of
2735  // the live values might be the result of a call which needs a safepoint.
2736  // That Value* no longer exists and we need to use the new gc_result.
2737  // Thankfully, the live set is embedded in the statepoint (and updated), so
2738  // we just grab that.
2739  llvm::append_range(Live, Info.StatepointToken->gc_args());
2740 #ifndef NDEBUG
2741  // Do some basic validation checking on our liveness results before
2742  // performing relocation. Relocation can and will turn mistakes in liveness
2743  // results into non-sensical code which is must harder to debug.
2744  // TODO: It would be nice to test consistency as well
2745  assert(DT.isReachableFromEntry(Info.StatepointToken->getParent()) &&
2746  "statepoint must be reachable or liveness is meaningless");
2747  for (Value *V : Info.StatepointToken->gc_args()) {
2748  if (!isa<Instruction>(V))
2749  // Non-instruction values trivial dominate all possible uses
2750  continue;
2751  auto *LiveInst = cast<Instruction>(V);
2752  assert(DT.isReachableFromEntry(LiveInst->getParent()) &&
2753  "unreachable values should never be live");
2754  assert(DT.dominates(LiveInst, Info.StatepointToken) &&
2755  "basic SSA liveness expectation violated by liveness analysis");
2756  }
2757 #endif
2758  }
2759  unique_unsorted(Live);
2760 
2761 #ifndef NDEBUG
2762  // Validation check
2763  for (auto *Ptr : Live)
2764  assert(isHandledGCPointerType(Ptr->getType()) &&
2765  "must be a gc pointer type");
2766 #endif
2767 
2768  relocationViaAlloca(F, DT, Live, Records);
2769  return !Records.empty();
2770 }
2771 
2772 // List of all parameter and return attributes which must be stripped when
2773 // lowering from the abstract machine model. Note that we list attributes
2774 // here which aren't valid as return attributes, that is okay.
2776  AttributeMask R;
2777  R.addAttribute(Attribute::Dereferenceable);
2778  R.addAttribute(Attribute::DereferenceableOrNull);
2779  R.addAttribute(Attribute::ReadNone);
2780  R.addAttribute(Attribute::ReadOnly);
2781  R.addAttribute(Attribute::WriteOnly);
2782  R.addAttribute(Attribute::NoAlias);
2783  R.addAttribute(Attribute::NoFree);
2784  return R;
2785 }
2786 
2788  LLVMContext &Ctx = F.getContext();
2789 
2790  // Intrinsics are very delicate. Lowering sometimes depends the presence
2791  // of certain attributes for correctness, but we may have also inferred
2792  // additional ones in the abstract machine model which need stripped. This
2793  // assumes that the attributes defined in Intrinsic.td are conservatively
2794  // correct for both physical and abstract model.
2795  if (Intrinsic::ID id = F.getIntrinsicID()) {
2796  F.setAttributes(Intrinsic::getAttributes(Ctx, id));
2797  return;
2798  }
2799 
2801  for (Argument &A : F.args())
2802  if (isa<PointerType>(A.getType()))
2803  F.removeParamAttrs(A.getArgNo(), R);
2804 
2805  if (isa<PointerType>(F.getReturnType()))
2806  F.removeRetAttrs(R);
2807 
2808  for (auto Attr : FnAttrsToStrip)
2809  F.removeFnAttr(Attr);
2810 }
2811 
2812 /// Certain metadata on instructions are invalid after running RS4GC.
2813 /// Optimizations that run after RS4GC can incorrectly use this metadata to
2814 /// optimize functions. We drop such metadata on the instruction.
2816  if (!isa<LoadInst>(I) && !isa<StoreInst>(I))
2817  return;
2818  // These are the attributes that are still valid on loads and stores after
2819  // RS4GC.
2820  // The metadata implying dereferenceability and noalias are (conservatively)
2821  // dropped. This is because semantically, after RewriteStatepointsForGC runs,
2822  // all calls to gc.statepoint "free" the entire heap. Also, gc.statepoint can
2823  // touch the entire heap including noalias objects. Note: The reasoning is
2824  // same as stripping the dereferenceability and noalias attributes that are
2825  // analogous to the metadata counterparts.
2826  // We also drop the invariant.load metadata on the load because that metadata
2827  // implies the address operand to the load points to memory that is never
2828  // changed once it became dereferenceable. This is no longer true after RS4GC.
2829  // Similar reasoning applies to invariant.group metadata, which applies to
2830  // loads within a group.
2831  unsigned ValidMetadataAfterRS4GC[] = {LLVMContext::MD_tbaa,
2832  LLVMContext::MD_range,
2833  LLVMContext::MD_alias_scope,
2834  LLVMContext::MD_nontemporal,
2835  LLVMContext::MD_nonnull,
2836  LLVMContext::MD_align,
2837  LLVMContext::MD_type};
2838 
2839  // Drops all metadata on the instruction other than ValidMetadataAfterRS4GC.
2840  I.dropUnknownNonDebugMetadata(ValidMetadataAfterRS4GC);
2841 }
2842 
2844  if (F.empty())
2845  return;
2846 
2847  LLVMContext &Ctx = F.getContext();
2848  MDBuilder Builder(Ctx);
2849 
2850  // Set of invariantstart instructions that we need to remove.
2851  // Use this to avoid invalidating the instruction iterator.
2852  SmallVector<IntrinsicInst*, 12> InvariantStartInstructions;
2853 
2854  for (Instruction &I : instructions(F)) {
2855  // invariant.start on memory location implies that the referenced memory
2856  // location is constant and unchanging. This is no longer true after
2857  // RewriteStatepointsForGC runs because there can be calls to gc.statepoint
2858  // which frees the entire heap and the presence of invariant.start allows
2859  // the optimizer to sink the load of a memory location past a statepoint,
2860  // which is incorrect.
2861  if (auto *II = dyn_cast<IntrinsicInst>(&I))
2862  if (II->getIntrinsicID() == Intrinsic::invariant_start) {
2863  InvariantStartInstructions.push_back(II);
2864  continue;
2865  }
2866 
2867  if (MDNode *Tag = I.getMetadata(LLVMContext::MD_tbaa)) {
2868  MDNode *MutableTBAA = Builder.createMutableTBAAAccessTag(Tag);
2869  I.setMetadata(LLVMContext::MD_tbaa, MutableTBAA);
2870  }
2871 
2873 
2875  if (auto *Call = dyn_cast<CallBase>(&I)) {
2876  for (int i = 0, e = Call->arg_size(); i != e; i++)
2877  if (isa<PointerType>(Call->getArgOperand(i)->getType()))
2878  Call->removeParamAttrs(i, R);
2879  if (isa<PointerType>(Call->getType()))
2880  Call->removeRetAttrs(R);
2881  }
2882  }
2883 
2884  // Delete the invariant.start instructions and RAUW undef.
2885  for (auto *II : InvariantStartInstructions) {
2886  II->replaceAllUsesWith(UndefValue::get(II->getType()));
2887  II->eraseFromParent();
2888  }
2889 }
2890 
2891 /// Returns true if this function should be rewritten by this pass. The main
2892 /// point of this function is as an extension point for custom logic.
2894  // TODO: This should check the GCStrategy
2895  if (F.hasGC()) {
2896  const auto &FunctionGCName = F.getGC();
2897  const StringRef StatepointExampleName("statepoint-example");
2898  const StringRef CoreCLRName("coreclr");
2899  return (StatepointExampleName == FunctionGCName) ||
2900  (CoreCLRName == FunctionGCName);
2901  } else
2902  return false;
2903 }
2904 
2905 static void stripNonValidData(Module &M) {
2906 #ifndef NDEBUG
2907  assert(llvm::any_of(M, shouldRewriteStatepointsIn) && "precondition!");
2908 #endif
2909 
2910  for (Function &F : M)
2912 
2913  for (Function &F : M)
2915 }
2916 
2919  const TargetLibraryInfo &TLI) {
2920  assert(!F.isDeclaration() && !F.empty() &&
2921  "need function body to rewrite statepoints in");
2922  assert(shouldRewriteStatepointsIn(F) && "mismatch in rewrite decision");
2923 
2924  auto NeedsRewrite = [&TLI](Instruction &I) {
2925  if (const auto *Call = dyn_cast<CallBase>(&I)) {
2926  if (isa<GCStatepointInst>(Call))
2927  return false;
2928  if (callsGCLeafFunction(Call, TLI))
2929  return false;
2930 
2931  // Normally it's up to the frontend to make sure that non-leaf calls also
2932  // have proper deopt state if it is required. We make an exception for
2933  // element atomic memcpy/memmove intrinsics here. Unlike other intrinsics
2934  // these are non-leaf by default. They might be generated by the optimizer
2935  // which doesn't know how to produce a proper deopt state. So if we see a
2936  // non-leaf memcpy/memmove without deopt state just treat it as a leaf
2937  // copy and don't produce a statepoint.
2939  !Call->getOperandBundle(LLVMContext::OB_deopt)) {
2940  assert((isa<AtomicMemCpyInst>(Call) || isa<AtomicMemMoveInst>(Call)) &&
2941  "Don't expect any other calls here!");
2942  return false;
2943  }
2944  return true;
2945  }
2946  return false;
2947  };
2948 
2949  // Delete any unreachable statepoints so that we don't have unrewritten
2950  // statepoints surviving this pass. This makes testing easier and the
2951  // resulting IR less confusing to human readers.
2953  bool MadeChange = removeUnreachableBlocks(F, &DTU);
2954  // Flush the Dominator Tree.
2955  DTU.getDomTree();
2956 
2957  // Gather all the statepoints which need rewritten. Be careful to only
2958  // consider those in reachable code since we need to ask dominance queries
2959  // when rewriting. We'll delete the unreachable ones in a moment.
2960  SmallVector<CallBase *, 64> ParsePointNeeded;
2961  SmallVector<CallInst *, 64> Intrinsics;
2962  for (Instruction &I : instructions(F)) {
2963  // TODO: only the ones with the flag set!
2964  if (NeedsRewrite(I)) {
2965  // NOTE removeUnreachableBlocks() is stronger than
2966  // DominatorTree::isReachableFromEntry(). In other words
2967  // removeUnreachableBlocks can remove some blocks for which
2968  // isReachableFromEntry() returns true.
2969  assert(DT.isReachableFromEntry(I.getParent()) &&
2970  "no unreachable blocks expected");
2971  ParsePointNeeded.push_back(cast<CallBase>(&I));
2972  }
2973  if (auto *CI = dyn_cast<CallInst>(&I))
2974  if (CI->getIntrinsicID() == Intrinsic::experimental_gc_get_pointer_base ||
2975  CI->getIntrinsicID() == Intrinsic::experimental_gc_get_pointer_offset)
2976  Intrinsics.emplace_back(CI);
2977  }
2978 
2979  // Return early if no work to do.
2980  if (ParsePointNeeded.empty() && Intrinsics.empty())
2981  return MadeChange;
2982 
2983  // As a prepass, go ahead and aggressively destroy single entry phi nodes.
2984  // These are created by LCSSA. They have the effect of increasing the size
2985  // of liveness sets for no good reason. It may be harder to do this post
2986  // insertion since relocations and base phis can confuse things.
2987  for (BasicBlock &BB : F)
2988  if (BB.getUniquePredecessor())
2989  MadeChange |= FoldSingleEntryPHINodes(&BB);
2990 
2991  // Before we start introducing relocations, we want to tweak the IR a bit to
2992  // avoid unfortunate code generation effects. The main example is that we
2993  // want to try to make sure the comparison feeding a branch is after any
2994  // safepoints. Otherwise, we end up with a comparison of pre-relocation
2995  // values feeding a branch after relocation. This is semantically correct,
2996  // but results in extra register pressure since both the pre-relocation and
2997  // post-relocation copies must be available in registers. For code without
2998  // relocations this is handled elsewhere, but teaching the scheduler to
2999  // reverse the transform we're about to do would be slightly complex.
3000  // Note: This may extend the live range of the inputs to the icmp and thus
3001  // increase the liveset of any statepoint we move over. This is profitable
3002  // as long as all statepoints are in rare blocks. If we had in-register
3003  // lowering for live values this would be a much safer transform.
3004  auto getConditionInst = [](Instruction *TI) -> Instruction * {
3005  if (auto *BI = dyn_cast<BranchInst>(TI))
3006  if (BI->isConditional())
3007  return dyn_cast<Instruction>(BI->getCondition());
3008  // TODO: Extend this to handle switches
3009  return nullptr;
3010  };
3011  for (BasicBlock &BB : F) {
3012  Instruction *TI = BB.getTerminator();
3013  if (auto *Cond = getConditionInst(TI))
3014  // TODO: Handle more than just ICmps here. We should be able to move
3015  // most instructions without side effects or memory access.
3016  if (isa<ICmpInst>(Cond) && Cond->hasOneUse()) {
3017  MadeChange = true;
3018  Cond->moveBefore(TI);
3019  }
3020  }
3021 
3022  // Nasty workaround - The base computation code in the main algorithm doesn't
3023  // consider the fact that a GEP can be used to convert a scalar to a vector.
3024  // The right fix for this is to integrate GEPs into the base rewriting
3025  // algorithm properly, this is just a short term workaround to prevent
3026  // crashes by canonicalizing such GEPs into fully vector GEPs.
3027  for (Instruction &I : instructions(F)) {
3028  if (!isa<GetElementPtrInst>(I))
3029  continue;
3030 
3031  unsigned VF = 0;
3032  for (unsigned i = 0; i < I.getNumOperands(); i++)
3033  if (auto *OpndVTy = dyn_cast<VectorType>(I.getOperand(i)->getType())) {
3034  assert(VF == 0 ||
3035  VF == cast<FixedVectorType>(OpndVTy)->getNumElements());
3036  VF = cast<FixedVectorType>(OpndVTy)->getNumElements();
3037  }
3038 
3039  // It's the vector to scalar traversal through the pointer operand which
3040  // confuses base pointer rewriting, so limit ourselves to that case.
3041  if (!I.getOperand(0)->getType()->isVectorTy() && VF != 0) {
3042  IRBuilder<> B(&I);
3043  auto *Splat = B.CreateVectorSplat(VF, I.getOperand(0));
3044  I.setOperand(0, Splat);
3045  MadeChange = true;
3046  }
3047  }
3048 
3049  // Cache the 'defining value' relation used in the computation and
3050  // insertion of base phis and selects. This ensures that we don't insert
3051  // large numbers of duplicate base_phis. Use one cache for both
3052  // inlineGetBaseAndOffset() and insertParsePoints().
3053  DefiningValueMapTy DVCache;
3054 
3055  // Mapping between a base values and a flag indicating whether it's a known
3056  // base or not.
3057  IsKnownBaseMapTy KnownBases;
3058 
3059  if (!Intrinsics.empty())
3060  // Inline @gc.get.pointer.base() and @gc.get.pointer.offset() before finding
3061  // live references.
3062  MadeChange |= inlineGetBaseAndOffset(F, Intrinsics, DVCache, KnownBases);
3063 
3064  if (!ParsePointNeeded.empty())
3065  MadeChange |=
3066  insertParsePoints(F, DT, TTI, ParsePointNeeded, DVCache, KnownBases);
3067 
3068  return MadeChange;
3069 }
3070 
3071 // liveness computation via standard dataflow
3072 // -------------------------------------------------------------------
3073 
3074 // TODO: Consider using bitvectors for liveness, the set of potentially
3075 // interesting values should be small and easy to pre-compute.
3076 
3077 /// Compute the live-in set for the location rbegin starting from
3078 /// the live-out set of the basic block
3081  SetVector<Value *> &LiveTmp) {
3082  for (auto &I : make_range(Begin, End)) {
3083  // KILL/Def - Remove this definition from LiveIn
3084  LiveTmp.remove(&I);
3085 
3086  // Don't consider *uses* in PHI nodes, we handle their contribution to
3087  // predecessor blocks when we seed the LiveOut sets
3088  if (isa<PHINode>(I))
3089  continue;
3090 
3091  // USE - Add to the LiveIn set for this instruction
3092  for (Value *V : I.operands()) {
3093  assert(!isUnhandledGCPointerType(V->getType()) &&
3094  "support for FCA unimplemented");
3095  if (isHandledGCPointerType(V->getType()) && !isa<Constant>(V)) {
3096  // The choice to exclude all things constant here is slightly subtle.
3097  // There are two independent reasons:
3098  // - We assume that things which are constant (from LLVM's definition)
3099  // do not move at runtime. For example, the address of a global
3100  // variable is fixed, even though it's contents may not be.
3101  // - Second, we can't disallow arbitrary inttoptr constants even
3102  // if the language frontend does. Optimization passes are free to
3103  // locally exploit facts without respect to global reachability. This
3104  // can create sections of code which are dynamically unreachable and
3105  // contain just about anything. (see constants.ll in tests)
3106  LiveTmp.insert(V);
3107  }
3108  }
3109  }
3110 }
3111 
3113  for (BasicBlock *Succ : successors(BB)) {
3114  for (auto &I : *Succ) {
3115  PHINode *PN = dyn_cast<PHINode>(&I);
3116  if (!PN)
3117  break;
3118 
3119  Value *V = PN->getIncomingValueForBlock(BB);
3121  "support for FCA unimplemented");
3122  if (isHandledGCPointerType(V->getType()) && !isa<Constant>(V))
3123  LiveTmp.insert(V);
3124  }
3125  }
3126 }
3127 
3129  SetVector<Value *> KillSet;
3130  for (Instruction &I : *BB)
3131  if (isHandledGCPointerType(I.getType()))
3132  KillSet.insert(&I);
3133  return KillSet;
3134 }
3135 
3136 #ifndef NDEBUG
3137 /// Check that the items in 'Live' dominate 'TI'. This is used as a basic
3138 /// validation check for the liveness computation.
3140  Instruction *TI, bool TermOkay = false) {
3141  for (Value *V : Live) {
3142  if (auto *I = dyn_cast<Instruction>(V)) {
3143  // The terminator can be a member of the LiveOut set. LLVM's definition
3144  // of instruction dominance states that V does not dominate itself. As
3145  // such, we need to special case this to allow it.
3146  if (TermOkay && TI == I)
3147  continue;
3148  assert(DT.dominates(I, TI) &&
3149  "basic SSA liveness expectation violated by liveness analysis");
3150  }
3151  }
3152 }
3153 
3154 /// Check that all the liveness sets used during the computation of liveness
3155 /// obey basic SSA properties. This is useful for finding cases where we miss
3156 /// a def.
3157 static void checkBasicSSA(DominatorTree &DT, GCPtrLivenessData &Data,
3158  BasicBlock &BB) {
3159  checkBasicSSA(DT, Data.LiveSet[&BB], BB.getTerminator());
3160  checkBasicSSA(DT, Data.LiveOut[&BB], BB.getTerminator(), true);
3161  checkBasicSSA(DT, Data.LiveIn[&BB], BB.getTerminator());
3162 }
3163 #endif
3164 
3166  GCPtrLivenessData &Data) {
3168 
3169  // Seed the liveness for each individual block
3170  for (BasicBlock &BB : F) {
3171  Data.KillSet[&BB] = computeKillSet(&BB);
3172  Data.LiveSet[&BB].clear();
3173  computeLiveInValues(BB.rbegin(), BB.rend(), Data.LiveSet[&BB]);
3174 
3175 #ifndef NDEBUG
3176  for (Value *Kill : Data.KillSet[&BB])
3177  assert(!Data.LiveSet[&BB].count(Kill) && "live set contains kill");
3178 #endif
3179 
3180  Data.LiveOut[&BB] = SetVector<Value *>();
3181  computeLiveOutSeed(&BB, Data.LiveOut[&BB]);
3182  Data.LiveIn[&BB] = Data.LiveSet[&BB];
3183  Data.LiveIn[&BB].set_union(Data.LiveOut[&BB]);
3184  Data.LiveIn[&BB].set_subtract(Data.KillSet[&BB]);
3185  if (!Data.LiveIn[&BB].empty())
3186  Worklist.insert(pred_begin(&BB), pred_end(&BB));
3187  }
3188 
3189  // Propagate that liveness until stable
3190  while (!Worklist.empty()) {
3191  BasicBlock *BB = Worklist.pop_back_val();
3192 
3193  // Compute our new liveout set, then exit early if it hasn't changed despite
3194  // the contribution of our successor.
3195  SetVector<Value *> LiveOut = Data.LiveOut[BB];
3196  const auto OldLiveOutSize = LiveOut.size();
3197  for (BasicBlock *Succ : successors(BB)) {
3198  assert(Data.LiveIn.count(Succ));
3199  LiveOut.set_union(Data.LiveIn[Succ]);
3200  }
3201  // assert OutLiveOut is a subset of LiveOut
3202  if (OldLiveOutSize == LiveOut.size()) {
3203  // If the sets are the same size, then we didn't actually add anything
3204  // when unioning our successors LiveIn. Thus, the LiveIn of this block
3205  // hasn't changed.
3206  continue;
3207  }
3208  Data.LiveOut[BB] = LiveOut;
3209 
3210  // Apply the effects of this basic block
3211  SetVector<Value *> LiveTmp = LiveOut;
3212  LiveTmp.set_union(Data.LiveSet[BB]);
3213  LiveTmp.set_subtract(Data.KillSet[BB]);
3214 
3215  assert(Data.LiveIn.count(BB));
3216  const SetVector<Value *> &OldLiveIn = Data.LiveIn[BB];
3217  // assert: OldLiveIn is a subset of LiveTmp
3218  if (OldLiveIn.size() != LiveTmp.size()) {
3219  Data.LiveIn[BB] = LiveTmp;
3220  Worklist.insert(pred_begin(BB), pred_end(BB));
3221  }
3222  } // while (!Worklist.empty())
3223 
3224 #ifndef NDEBUG
3225  // Verify our output against SSA properties. This helps catch any
3226  // missing kills during the above iteration.
3227  for (BasicBlock &BB : F)
3228  checkBasicSSA(DT, Data, BB);
3229 #endif
3230 }
3231 
3232 static void findLiveSetAtInst(Instruction *Inst, GCPtrLivenessData &Data,
3233  StatepointLiveSetTy &Out) {
3234  BasicBlock *BB = Inst->getParent();
3235 
3236  // Note: The copy is intentional and required
3237  assert(Data.LiveOut.count(BB));
3238  SetVector<Value *> LiveOut = Data.LiveOut[BB];
3239 
3240  // We want to handle the statepoint itself oddly. It's
3241  // call result is not live (normal), nor are it's arguments
3242  // (unless they're used again later). This adjustment is
3243  // specifically what we need to relocate
3244  computeLiveInValues(BB->rbegin(), ++Inst->getIterator().getReverse(),
3245  LiveOut);
3246  LiveOut.remove(Inst);
3247  Out.insert(LiveOut.begin(), LiveOut.end());
3248 }
3249 
3250 static void recomputeLiveInValues(GCPtrLivenessData &RevisedLivenessData,
3251  CallBase *Call,
3252  PartiallyConstructedSafepointRecord &Info,
3253  PointerToBaseTy &PointerToBase) {
3254  StatepointLiveSetTy Updated;
3255  findLiveSetAtInst(Call, RevisedLivenessData, Updated);
3256 
3257  // We may have base pointers which are now live that weren't before. We need
3258  // to update the PointerToBase structure to reflect this.
3259  for (auto V : Updated)
3260  PointerToBase.insert({ V, V });
3261 
3262  Info.LiveSet = Updated;
3263 }
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:29
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:1925
stripInvalidMetadataFromInstruction
static void stripInvalidMetadataFromInstruction(Instruction &I)
Certain metadata on instructions are invalid after running RS4GC.
Definition: RewriteStatepointsForGC.cpp:2815
llvm::TargetIRAnalysis
Analysis pass providing the TargetTransformInfo.
Definition: TargetTransformInfo.h:2485
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:494
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:17
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:65
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:2185
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:2917
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:113
print
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
Definition: ArchiveWriter.cpp:189
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:1419
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:1981
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:780
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:3165
T
AreEquivalentPhiNodes
static bool AreEquivalentPhiNodes(PHINode &OrigRootPhi, PHINode &AlternateRootPhi)
Definition: RewriteStatepointsForGC.cpp:2286
llvm::Function
Definition: Function.h:60
llvm::cl::location
LocationClass< Ty > location(Ty &L)
Definition: CommandLine.h:447
llvm::Attribute
Definition: Attributes.h:65
llvm::callsGCLeafFunction
bool callsGCLeafFunction(const CallBase *Call, const TargetLibraryInfo &TLI)
Return true if this call calls a gc leaf function.
Definition: Local.cpp:2750
StringRef.h
Pass.h
legalizeCallAttributes
static AttributeList legalizeCallAttributes(LLVMContext &Ctx, AttributeList OrigAL, AttributeList StatepointAL)
Definition: RewriteStatepointsForGC.cpp:1440
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:5212
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:942
llvm::SmallVector< Instruction *, 3 >
llvm::CallInst::setTailCallKind
void setTailCallKind(TailCallKind TCK)
Definition: Instructions.h:1664
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:3128
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:168
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:542
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:1807
llvm::SmallDenseMap
Definition: DenseMap.h:882
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:1050
llvm::Instruction::insertBefore
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
Definition: Instruction.cpp:83
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:139
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:1895
llvm::ExtractElementInst::Create
static ExtractElementInst * Create(Value *Vec, Value *Idx, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Definition: Instructions.h:1872
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:2485
Module.h
llvm::reverse
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:380
llvm::AttributeList
Definition: Attributes.h:425
llvm::AttributeMask
Definition: Attributes.h:963
llvm::CallBase::getAttributes
AttributeList getAttributes() const
Return the parameter attributes for this call.
Definition: InstrTypes.h:1474
stripNonValidAttributesFromPrototype
static void stripNonValidAttributesFromPrototype(Function &F)
Definition: RewriteStatepointsForGC.cpp:2787
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:1388
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:1992
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:147
Offset
uint64_t Offset
Definition: ELFObjHandler.cpp:79
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.
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:1013
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:893
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::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:654
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:2750
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:1384
llvm::AttrBuilder::removeAttribute
AttrBuilder & removeAttribute(Attribute::AttrKind Val)
Remove an attribute from the builder.
Definition: Attributes.cpp:1626
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:241
llvm::Instruction::setMetadata
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
Definition: Metadata.cpp:1434
llvm::DomTreeUpdater::UpdateStrategy::Lazy
@ Lazy
Uses
SmallPtrSet< MachineInstr *, 2 > Uses
Definition: ARMLowOverheadLoops.cpp:585
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
findRematerializableChainToBasePointer
static Value * findRematerializableChainToBasePointer(SmallVectorImpl< Instruction * > &ChainToBase, Value *CurrentValue)
Definition: RewriteStatepointsForGC.cpp:2227
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:186
findRematerializationCandidates
static void findRematerializationCandidates(PointerToBaseTy PointerToBase, RematCandTy &RematerizationCandidates, TargetTransformInfo &TTI)
Definition: RewriteStatepointsForGC.cpp:2315
Instruction.h
CommandLine.h
llvm::SPII::Load
@ Load
Definition: SparcInstrInfo.h:32
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:781
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:31
rematerializeLiveValues
static void rematerializeLiveValues(CallBase *Call, PartiallyConstructedSafepointRecord &Info, PointerToBaseTy &PointerToBase, RematCandTy &RematerizationCandidates, TargetTransformInfo &TTI)
Definition: RewriteStatepointsForGC.cpp:2376
llvm::MutableArrayRef
MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...
Definition: ArrayRef.h:306
Constants.h
llvm::PHINode::getIncomingValue
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
Definition: Instructions.h:2747
chainToBasePointerCost
static InstructionCost chainToBasePointerCost(SmallVectorImpl< Instruction * > &Chain, TargetTransformInfo &TTI)
Definition: RewriteStatepointsForGC.cpp:2253
llvm::AllocaInst::getAllocatedType
Type * getAllocatedType() const
Return the type that is being allocated by the instruction.
Definition: Instructions.h:114
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:1612
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:1478
llvm::BasicBlock::begin
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:297
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:1504
isUnhandledGCPointerType
static bool isUnhandledGCPointerType(Type *Ty)
Definition: RewriteStatepointsForGC.cpp:365
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::RegState::Kill
@ Kill
The last use of a register.
Definition: MachineInstrBuilder.h:48
insertRematerializationStores
static void insertRematerializationStores(const RematerializedValueMapTy &RematerializedValues, DenseMap< Value *, AllocaInst * > &AllocaMap, DenseSet< Value * > &VisitedLiveValues)
Definition: RewriteStatepointsForGC.cpp:1959
analyzeParsePointLiveness
static void analyzeParsePointLiveness(DominatorTree &DT, GCPtrLivenessData &OriginalLivenessData, CallBase *Call, PartiallyConstructedSafepointRecord &Result)
Definition: RewriteStatepointsForGC.cpp:381
IP
Definition: NVPTXLowerArgs.cpp:167
TargetLibraryInfo.h
getDeoptLowering
static StringRef getDeoptLowering(CallBase *Call)
Definition: RewriteStatepointsForGC.cpp:1596
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:2836
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:1405
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:54
llvm::Value::setName
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:372
llvm::operator<<
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:230
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1768
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:1176
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::SPII::Store
@ Store
Definition: SparcInstrInfo.h:33
llvm::AddressSpace
AddressSpace
Definition: NVPTXBaseInfo.h:21
llvm::StringRef::str
LLVM_NODISCARD std::string str() const
str - Get the contents as an std::string.
Definition: StringRef.h:249
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:304
llvm::PHINode::getNumIncomingValues
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: Instructions.h:2743
llvm::None
const NoneType None
Definition: None.h:24
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:2547
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::StringRef::equals
LLVM_NODISCARD bool equals(StringRef RHS) const
equals - Check for string equality, this is more efficient than compare() when the relative ordering ...
Definition: StringRef.h:187
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::AttributeList::addFnAttributes
LLVM_NODISCARD AttributeList addFnAttributes(LLVMContext &C, const AttrBuilder &B) const
Add function attribute to the list.
Definition: Attributes.h:533
llvm::InvokeInst
Invoke instruction.
Definition: Instructions.h:3763
llvm::ARM_PROC::IE
@ IE
Definition: ARMBaseInfo.h:27
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:428
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:3139
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:1952
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:297
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:77
llvm::GCRelocateInst
Represents calls to the gc.relocate intrinsic.
Definition: IntrinsicInst.h:1388
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:3232
llvm::StatepointFlags::None
@ None
Index
uint32_t Index
Definition: ELFObjHandler.cpp:82
llvm::TargetLibraryInfoWrapperPass
Definition: TargetLibraryInfo.h:468
uint64_t
llvm::pdb::Unknown
@ Unknown
Definition: PDBTypes.h:396
llvm::TargetTransformInfoWrapperPass
Wrapper pass for TargetTransformInfo.
Definition: TargetTransformInfo.h:2541
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:1637
llvm::ARM_MB::ST
@ ST
Definition: ARMBaseInfo.h:73
llvm::GCRelocateInst::getDerivedPtr
Value * getDerivedPtr() const
Definition: IntrinsicInst.cpp:722
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:1754
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:68
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
PromoteMemToReg.h
llvm::DomTreeUpdater::getDomTree
DominatorTree & getDomTree()
Flush DomTree updates and return DomTree.
Definition: DomTreeUpdater.cpp:304
llvm::DenseMap
Definition: DenseMap.h:716
FnAttrsToStrip
static constexpr Attribute::AttrKind FnAttrsToStrip[]
Definition: RewriteStatepointsForGC.cpp:1432
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::LLVMContext::OB_gc_transition
@ OB_gc_transition
Definition: LLVMContext.h:92
llvm::AttrBuilder
Definition: Attributes.h:1024
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:916
llvm::Attribute::AttrKind
AttrKind
This enumeration lists the attributes that can be associated with parameters, function results,...
Definition: Attributes.h:84
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
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:1682
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:152
IRBuilder.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
SI
StandardInstrumentations SI(Debug, VerifyEach)
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:1990
llvm::DominatorTree::isReachableFromEntry
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:335
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1724
iterator_range.h
function
print Print MemDeps of function
Definition: MemDepPrinter.cpp:82
llvm::Record
Definition: Record.h:1543
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:824
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:2893
gc
rewrite statepoints for gc
Definition: RewriteStatepointsForGC.cpp:228
info
lazy value info
Definition: LazyValueInfo.cpp:58
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
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:862
getParamAndReturnAttributesToRemove
static AttributeMask getParamAndReturnAttributesToRemove()
Definition: RewriteStatepointsForGC.cpp:2775
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
llvm::StatepointDirectives::StatepointID
Optional< uint64_t > StatepointID
Definition: Statepoint.h:238
None.h
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:1624
DataLayout.h
llvm::StructType
Class to represent struct types.
Definition: DerivedTypes.h:213
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:137
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
llvm::LLVMContext::OB_deopt
@ OB_deopt
Definition: LLVMContext.h:90
llvm::TargetTransformInfo::TCK_SizeAndLatency
@ TCK_SizeAndLatency
The weighted sum of size and latency.
Definition: TargetTransformInfo.h:215
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:269
llvm::Value::replaceAllUsesWith
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:529
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:1823
llvm::Value::getContext
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:991
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:82
llvm::StatepointDirectives::NumPatchBytes
Optional< uint32_t > NumPatchBytes
Definition: Statepoint.h:237
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:429
llvm::SmallSet::insert
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Definition: SmallSet.h:182
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:305
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:173
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:1070
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
llvm::GraphProgram::Name
Name
Definition: GraphWriter.h:50
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::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::pred_end
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:112
false::RematerizlizationCandidateRecord::Cost
InstructionCost Cost
Definition: RewriteStatepointsForGC.cpp:291
Casting.h
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:2178
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1562
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:2495
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:222
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:1779
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:591
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::FoldSingleEntryPHINodes
bool FoldSingleEntryPHINodes(BasicBlock *BB, MemoryDependenceResults *MemDep=nullptr)
We know that BB has one predecessor.
Definition: BasicBlockUtils.cpp:143
computeLiveOutSeed
static void computeLiveOutSeed(BasicBlock *BB, SetVector< Value * > &LiveTmp)
Definition: RewriteStatepointsForGC.cpp:3112
llvm::IntrinsicInst
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:46
llvm::MDBuilder
Definition: MDBuilder.h:35
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:2905
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::PHINode::getIncomingBlock
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Definition: Instructions.h:2767
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:2651
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:3250
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:1468
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1174
llvm::BasicBlock::getLandingPadInst
const LandingPadInst * getLandingPadInst() const
Return the landingpad instruction associated with the landing pad.
Definition: BasicBlock.cpp:473
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::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:937
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1461
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:4727
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:58
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:2210
llvm::SetVector< Value * >
llvm::ConstantAggregateZero::get
static ConstantAggregateZero * get(Type *Ty)
Definition: Constants.cpp:1647
llvm::SmallVectorImpl::reserve
void reserve(size_type N)
Definition: SmallVector.h:644
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:810
Value.h
stripNonValidDataFromBody
static void stripNonValidDataFromBody(Function &F)
Definition: RewriteStatepointsForGC.cpp:2843
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::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SetVector.h:232
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:443
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:926
SetVector.h
llvm::sampleprof::Base
@ Base
Definition: Discriminator.h:58
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1237
llvm::CallingConv::Cold
@ Cold
Definition: CallingConv.h:48
llvm::CallBase::setCallingConv
void setCallingConv(CallingConv::ID CC)
Definition: InstrTypes.h:1459
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:927
SmallSet.h
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38
false::RematCandTy
MapVector< Value *, RematerizlizationCandidateRecord > RematCandTy
Definition: RewriteStatepointsForGC.cpp:293