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