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