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