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