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