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