//===- RewriteStatepointsForGC.cpp - Make GC relocations explicit ---------===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// // // Rewrite call/invoke instructions so as to make potential relocations // performed by the garbage collector explicit in the IR. // //===----------------------------------------------------------------------===// #include "llvm/Transforms/Scalar/RewriteStatepointsForGC.h" #include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/DenseSet.h" #include "llvm/ADT/MapVector.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/Sequence.h" #include "llvm/ADT/SetVector.h" #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/StringRef.h" #include "llvm/ADT/iterator_range.h" #include "llvm/Analysis/DomTreeUpdater.h" #include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/Analysis/TargetTransformInfo.h" #include "llvm/IR/Argument.h" #include "llvm/IR/AttributeMask.h" #include "llvm/IR/Attributes.h" #include "llvm/IR/BasicBlock.h" #include "llvm/IR/CallingConv.h" #include "llvm/IR/Constant.h" #include "llvm/IR/Constants.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/DerivedTypes.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/Function.h" #include "llvm/IR/GCStrategy.h" #include "llvm/IR/IRBuilder.h" #include "llvm/IR/InstIterator.h" #include "llvm/IR/InstrTypes.h" #include "llvm/IR/Instruction.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/Intrinsics.h" #include "llvm/IR/LLVMContext.h" #include "llvm/IR/MDBuilder.h" #include "llvm/IR/Metadata.h" #include "llvm/IR/Module.h" #include "llvm/IR/Statepoint.h" #include "llvm/IR/Type.h" #include "llvm/IR/User.h" #include "llvm/IR/Value.h" #include "llvm/IR/ValueHandle.h" #include "llvm/Support/Casting.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Compiler.h" #include "llvm/Support/Debug.h" #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Transforms/Utils/BasicBlockUtils.h" #include "llvm/Transforms/Utils/Local.h" #include "llvm/Transforms/Utils/PromoteMemToReg.h" #include <algorithm> #include <cassert> #include <cstddef> #include <cstdint> #include <iterator> #include <optional> #include <set> #include <string> #include <utility> #include <vector> #define DEBUG_TYPE … usingnamespacellvm; // Print the liveset found at the insert location static cl::opt<bool> PrintLiveSet("spp-print-liveset", cl::Hidden, cl::init(false)); static cl::opt<bool> PrintLiveSetSize("spp-print-liveset-size", cl::Hidden, cl::init(false)); // Print out the base pointers for debugging static cl::opt<bool> PrintBasePointers("spp-print-base-pointers", cl::Hidden, cl::init(false)); // Cost threshold measuring when it is profitable to rematerialize value instead // of relocating it static cl::opt<unsigned> RematerializationThreshold("spp-rematerialization-threshold", cl::Hidden, cl::init(6)); #ifdef EXPENSIVE_CHECKS static bool ClobberNonLive = true; #else static bool ClobberNonLive = …; #endif static cl::opt<bool, true> ClobberNonLiveOverride("rs4gc-clobber-non-live", cl::location(ClobberNonLive), cl::Hidden); static cl::opt<bool> AllowStatepointWithNoDeoptInfo("rs4gc-allow-statepoint-with-no-deopt-info", cl::Hidden, cl::init(true)); static cl::opt<bool> RematDerivedAtUses("rs4gc-remat-derived-at-uses", cl::Hidden, cl::init(true)); /// The IR fed into RewriteStatepointsForGC may have had attributes and /// metadata implying dereferenceability that are no longer valid/correct after /// RewriteStatepointsForGC has run. This is because semantically, after /// RewriteStatepointsForGC runs, all calls to gc.statepoint "free" the entire /// heap. stripNonValidData (conservatively) restores /// correctness by erasing all attributes in the module that externally imply /// dereferenceability. Similar reasoning also applies to the noalias /// attributes and metadata. gc.statepoint can touch the entire heap including /// noalias objects. /// Apart from attributes and metadata, we also remove instructions that imply /// constant physical memory: llvm.invariant.start. static void stripNonValidData(Module &M); // Find the GC strategy for a function, or null if it doesn't have one. static std::unique_ptr<GCStrategy> findGCStrategy(Function &F); static bool shouldRewriteStatepointsIn(Function &F); PreservedAnalyses RewriteStatepointsForGC::run(Module &M, ModuleAnalysisManager &AM) { … } namespace { struct GCPtrLivenessData { … }; // The type of the internal cache used inside the findBasePointers family // of functions. From the callers perspective, this is an opaque type and // should not be inspected. // // In the actual implementation this caches two relations: // - The base relation itself (i.e. this pointer is based on that one) // - The base defining value relation (i.e. before base_phi insertion) // Generally, after the execution of a full findBasePointer call, only the // base relation will remain. Internally, we add a mixture of the two // types, then update all the second type to the first type DefiningValueMapTy; IsKnownBaseMapTy; PointerToBaseTy; StatepointLiveSetTy; RematerializedValueMapTy; struct PartiallyConstructedSafepointRecord { … }; struct RematerizlizationCandidateRecord { … }; RematCandTy; } // end anonymous namespace static ArrayRef<Use> GetDeoptBundleOperands(const CallBase *Call) { … } /// Compute the live-in set for every basic block in the function static void computeLiveInValues(DominatorTree &DT, Function &F, GCPtrLivenessData &Data, GCStrategy *GC); /// Given results from the dataflow liveness computation, find the set of live /// Values at a particular instruction. static void findLiveSetAtInst(Instruction *inst, GCPtrLivenessData &Data, StatepointLiveSetTy &out, GCStrategy *GC); static bool isGCPointerType(Type *T, GCStrategy *GC) { … } // Return true if this type is one which a) is a gc pointer or contains a GC // pointer and b) is of a type this code expects to encounter as a live value. // (The insertion code will assert that a type which matches (a) and not (b) // is not encountered.) static bool isHandledGCPointerType(Type *T, GCStrategy *GC) { … } #ifndef NDEBUG /// Returns true if this type contains a gc pointer whether we know how to /// handle that type or not. static bool containsGCPtrType(Type *Ty, GCStrategy *GC) { if (isGCPointerType(Ty, GC)) return true; if (VectorType *VT = dyn_cast<VectorType>(Ty)) return isGCPointerType(VT->getScalarType(), GC); if (ArrayType *AT = dyn_cast<ArrayType>(Ty)) return containsGCPtrType(AT->getElementType(), GC); if (StructType *ST = dyn_cast<StructType>(Ty)) return llvm::any_of(ST->elements(), [GC](Type *Ty) { return containsGCPtrType(Ty, GC); }); return false; } // Returns true if this is a type which a) is a gc pointer or contains a GC // pointer and b) is of a type which the code doesn't expect (i.e. first class // aggregates). Used to trip assertions. static bool isUnhandledGCPointerType(Type *Ty, GCStrategy *GC) { return containsGCPtrType(Ty, GC) && !isHandledGCPointerType(Ty, GC); } #endif // Return the name of the value suffixed with the provided value, or if the // value didn't have a name, the default value specified. static std::string suffixed_name_or(Value *V, StringRef Suffix, StringRef DefaultName) { … } // Conservatively identifies any definitions which might be live at the // given instruction. The analysis is performed immediately before the // given instruction. Values defined by that instruction are not considered // live. Values used by that instruction are considered live. static void analyzeParsePointLiveness( DominatorTree &DT, GCPtrLivenessData &OriginalLivenessData, CallBase *Call, PartiallyConstructedSafepointRecord &Result, GCStrategy *GC) { … } /// Returns true if V is a known base. static bool isKnownBase(Value *V, const IsKnownBaseMapTy &KnownBases); /// Caches the IsKnownBase flag for a value and asserts that it wasn't present /// in the cache before. static void setKnownBase(Value *V, bool IsKnownBase, IsKnownBaseMapTy &KnownBases); static Value *findBaseDefiningValue(Value *I, DefiningValueMapTy &Cache, IsKnownBaseMapTy &KnownBases); /// Return a base defining value for the 'Index' element of the given vector /// instruction 'I'. If Index is null, returns a BDV for the entire vector /// 'I'. As an optimization, this method will try to determine when the /// element is known to already be a base pointer. If this can be established, /// the second value in the returned pair will be true. Note that either a /// vector or a pointer typed value can be returned. For the former, the /// vector returned is a BDV (and possibly a base) of the entire vector 'I'. /// If the later, the return pointer is a BDV (or possibly a base) for the /// particular element in 'I'. static Value *findBaseDefiningValueOfVector(Value *I, DefiningValueMapTy &Cache, IsKnownBaseMapTy &KnownBases) { … } /// Helper function for findBasePointer - Will return a value which either a) /// defines the base pointer for the input, b) blocks the simple search /// (i.e. a PHI or Select of two derived pointers), or c) involves a change /// from pointer to vector type or back. static Value *findBaseDefiningValue(Value *I, DefiningValueMapTy &Cache, IsKnownBaseMapTy &KnownBases) { … } /// Returns the base defining value for this value. static Value *findBaseDefiningValueCached(Value *I, DefiningValueMapTy &Cache, IsKnownBaseMapTy &KnownBases) { … } /// Return a base pointer for this value if known. Otherwise, return it's /// base defining value. static Value *findBaseOrBDV(Value *I, DefiningValueMapTy &Cache, IsKnownBaseMapTy &KnownBases) { … } #ifndef NDEBUG /// This value is a base pointer that is not generated by RS4GC, i.e. it already /// exists in the code. static bool isOriginalBaseResult(Value *V) { // no recursion possible return !isa<PHINode>(V) && !isa<SelectInst>(V) && !isa<ExtractElementInst>(V) && !isa<InsertElementInst>(V) && !isa<ShuffleVectorInst>(V); } #endif static bool isKnownBase(Value *V, const IsKnownBaseMapTy &KnownBases) { … } static void setKnownBase(Value *V, bool IsKnownBase, IsKnownBaseMapTy &KnownBases) { … } // Returns true if First and Second values are both scalar or both vector. static bool areBothVectorOrScalar(Value *First, Value *Second) { … } namespace { /// Models the state of a single base defining value in the findBasePointer /// algorithm for determining where a new instruction is needed to propagate /// the base of this BDV. class BDVState { … }; } // end anonymous namespace #ifndef NDEBUG static raw_ostream &operator<<(raw_ostream &OS, const BDVState &State) { State.print(OS); return OS; } #endif /// For a given value or instruction, figure out what base ptr its derived from. /// For gc objects, this is simply itself. On success, returns a value which is /// the base pointer. (This is reliable and can be used for relocation.) On /// failure, returns nullptr. static Value *findBasePointer(Value *I, DefiningValueMapTy &Cache, IsKnownBaseMapTy &KnownBases) { … } // For a set of live pointers (base and/or derived), identify the base // pointer of the object which they are derived from. This routine will // mutate the IR graph as needed to make the 'base' pointer live at the // definition site of 'derived'. This ensures that any use of 'derived' can // also use 'base'. This may involve the insertion of a number of // additional PHI nodes. // // preconditions: live is a set of pointer type Values // // side effects: may insert PHI nodes into the existing CFG, will preserve // CFG, will not remove or mutate any existing nodes // // post condition: PointerToBase contains one (derived, base) pair for every // pointer in live. Note that derived can be equal to base if the original // pointer was a base pointer. static void findBasePointers(const StatepointLiveSetTy &live, PointerToBaseTy &PointerToBase, DominatorTree *DT, DefiningValueMapTy &DVCache, IsKnownBaseMapTy &KnownBases) { … } /// Find the required based pointers (and adjust the live set) for the given /// parse point. static void findBasePointers(DominatorTree &DT, DefiningValueMapTy &DVCache, CallBase *Call, PartiallyConstructedSafepointRecord &result, PointerToBaseTy &PointerToBase, IsKnownBaseMapTy &KnownBases) { … } /// Given an updated version of the dataflow liveness results, update the /// liveset and base pointer maps for the call site CS. static void recomputeLiveInValues(GCPtrLivenessData &RevisedLivenessData, CallBase *Call, PartiallyConstructedSafepointRecord &result, PointerToBaseTy &PointerToBase, GCStrategy *GC); static void recomputeLiveInValues( Function &F, DominatorTree &DT, ArrayRef<CallBase *> toUpdate, MutableArrayRef<struct PartiallyConstructedSafepointRecord> records, PointerToBaseTy &PointerToBase, GCStrategy *GC) { … } // Utility function which clones all instructions from "ChainToBase" // and inserts them before "InsertBefore". Returns rematerialized value // which should be used after statepoint. static Instruction *rematerializeChain(ArrayRef<Instruction *> ChainToBase, Instruction *InsertBefore, Value *RootOfChain, Value *AlternateLiveBase) { … } // When inserting gc.relocate and gc.result calls, we need to ensure there are // no uses of the original value / return value between the gc.statepoint and // the gc.relocate / gc.result call. One case which can arise is a phi node // starting one of the successor blocks. We also need to be able to insert the // gc.relocates only on the path which goes through the statepoint. We might // need to split an edge to make this possible. static BasicBlock * normalizeForInvokeSafepoint(BasicBlock *BB, BasicBlock *InvokeParent, DominatorTree &DT) { … } // List of all function attributes which must be stripped when lowering from // abstract machine model to physical machine model. Essentially, these are // all the effects a safepoint might have which we ignored in the abstract // machine model for purposes of optimization. We have to strip these on // both function declarations and call sites. static constexpr Attribute::AttrKind FnAttrsToStrip[] = …; // Create new attribute set containing only attributes which can be transferred // from the original call to the safepoint. static AttributeList legalizeCallAttributes(CallBase *Call, bool IsMemIntrinsic, AttributeList StatepointAL) { … } /// Helper function to place all gc relocates necessary for the given /// statepoint. /// Inputs: /// liveVariables - list of variables to be relocated. /// basePtrs - base pointers. /// statepointToken - statepoint instruction to which relocates should be /// bound. /// Builder - Llvm IR builder to be used to construct new calls. static void CreateGCRelocates(ArrayRef<Value *> LiveVariables, ArrayRef<Value *> BasePtrs, Instruction *StatepointToken, IRBuilder<> &Builder, GCStrategy *GC) { … } namespace { /// This struct is used to defer RAUWs and `eraseFromParent` s. Using this /// avoids having to worry about keeping around dangling pointers to Values. class DeferredReplacement { … }; } // end anonymous namespace static StringRef getDeoptLowering(CallBase *Call) { … } static void makeStatepointExplicitImpl(CallBase *Call, /* to replace */ const SmallVectorImpl<Value *> &BasePtrs, const SmallVectorImpl<Value *> &LiveVariables, PartiallyConstructedSafepointRecord &Result, std::vector<DeferredReplacement> &Replacements, const PointerToBaseTy &PointerToBase, GCStrategy *GC) { … } // Replace an existing gc.statepoint with a new one and a set of gc.relocates // which make the relocations happening at this safepoint explicit. // // WARNING: Does not do any fixup to adjust users of the original live // values. That's the callers responsibility. static void makeStatepointExplicit(DominatorTree &DT, CallBase *Call, PartiallyConstructedSafepointRecord &Result, std::vector<DeferredReplacement> &Replacements, const PointerToBaseTy &PointerToBase, GCStrategy *GC) { … } // Helper function for the relocationViaAlloca. // // It receives iterator to the statepoint gc relocates and emits a store to the // assigned location (via allocaMap) for the each one of them. It adds the // visited values into the visitedLiveValues set, which we will later use them // for validation checking. static void insertRelocationStores(iterator_range<Value::user_iterator> GCRelocs, DenseMap<Value *, AllocaInst *> &AllocaMap, DenseSet<Value *> &VisitedLiveValues) { … } // Helper function for the "relocationViaAlloca". Similar to the // "insertRelocationStores" but works for rematerialized values. static void insertRematerializationStores( const RematerializedValueMapTy &RematerializedValues, DenseMap<Value *, AllocaInst *> &AllocaMap, DenseSet<Value *> &VisitedLiveValues) { … } /// Do all the relocation update via allocas and mem2reg static void relocationViaAlloca( Function &F, DominatorTree &DT, ArrayRef<Value *> Live, ArrayRef<PartiallyConstructedSafepointRecord> Records) { … } /// Implement a unique function which doesn't require we sort the input /// vector. Doing so has the effect of changing the output of a couple of /// tests in ways which make them less useful in testing fused safepoints. template <typename T> static void unique_unsorted(SmallVectorImpl<T> &Vec) { … } /// Insert holders so that each Value is obviously live through the entire /// lifetime of the call. static void insertUseHolderAfter(CallBase *Call, const ArrayRef<Value *> Values, SmallVectorImpl<CallInst *> &Holders) { … } static void findLiveReferences( Function &F, DominatorTree &DT, ArrayRef<CallBase *> toUpdate, MutableArrayRef<struct PartiallyConstructedSafepointRecord> records, GCStrategy *GC) { … } // Helper function for the "rematerializeLiveValues". It walks use chain // starting from the "CurrentValue" until it reaches the root of the chain, i.e. // the base or a value it cannot process. Only "simple" values are processed // (currently it is GEP's and casts). The returned root is examined by the // callers of findRematerializableChainToBasePointer. Fills "ChainToBase" array // with all visited values. static Value* findRematerializableChainToBasePointer( SmallVectorImpl<Instruction*> &ChainToBase, Value *CurrentValue) { … } // Helper function for the "rematerializeLiveValues". Compute cost of the use // chain we are going to rematerialize. static InstructionCost chainToBasePointerCost(SmallVectorImpl<Instruction *> &Chain, TargetTransformInfo &TTI) { … } static bool AreEquivalentPhiNodes(PHINode &OrigRootPhi, PHINode &AlternateRootPhi) { … } // Find derived pointers that can be recomputed cheap enough and fill // RematerizationCandidates with such candidates. static void findRematerializationCandidates(PointerToBaseTy PointerToBase, RematCandTy &RematerizationCandidates, TargetTransformInfo &TTI) { … } // Try to rematerialize derived pointers immediately before their uses // (instead of rematerializing after every statepoint it is live through). // This can be beneficial when derived pointer is live across many // statepoints, but uses are rare. static void rematerializeLiveValuesAtUses( RematCandTy &RematerizationCandidates, MutableArrayRef<PartiallyConstructedSafepointRecord> Records, PointerToBaseTy &PointerToBase) { … } // From the statepoint live set pick values that are cheaper to recompute then // to relocate. Remove this values from the live set, rematerialize them after // statepoint and record them in "Info" structure. Note that similar to // relocated values we don't do any user adjustments here. static void rematerializeLiveValues(CallBase *Call, PartiallyConstructedSafepointRecord &Info, PointerToBaseTy &PointerToBase, RematCandTy &RematerizationCandidates, TargetTransformInfo &TTI) { … } static bool inlineGetBaseAndOffset(Function &F, SmallVectorImpl<CallInst *> &Intrinsics, DefiningValueMapTy &DVCache, IsKnownBaseMapTy &KnownBases) { … } static bool insertParsePoints(Function &F, DominatorTree &DT, TargetTransformInfo &TTI, SmallVectorImpl<CallBase *> &ToUpdate, DefiningValueMapTy &DVCache, IsKnownBaseMapTy &KnownBases) { … } // List of all parameter and return attributes which must be stripped when // lowering from the abstract machine model. Note that we list attributes // here which aren't valid as return attributes, that is okay. static AttributeMask getParamAndReturnAttributesToRemove() { … } static void stripNonValidAttributesFromPrototype(Function &F) { … } /// Certain metadata on instructions are invalid after running RS4GC. /// Optimizations that run after RS4GC can incorrectly use this metadata to /// optimize functions. We drop such metadata on the instruction. static void stripInvalidMetadataFromInstruction(Instruction &I) { … } static void stripNonValidDataFromBody(Function &F) { … } /// Looks up the GC strategy for a given function, returning null if the /// function doesn't have a GC tag. The strategy is stored in the cache. static std::unique_ptr<GCStrategy> findGCStrategy(Function &F) { … } /// Returns true if this function should be rewritten by this pass. The main /// point of this function is as an extension point for custom logic. static bool shouldRewriteStatepointsIn(Function &F) { … } static void stripNonValidData(Module &M) { … } bool RewriteStatepointsForGC::runOnFunction(Function &F, DominatorTree &DT, TargetTransformInfo &TTI, const TargetLibraryInfo &TLI) { … } // liveness computation via standard dataflow // ------------------------------------------------------------------- // TODO: Consider using bitvectors for liveness, the set of potentially // interesting values should be small and easy to pre-compute. /// Compute the live-in set for the location rbegin starting from /// the live-out set of the basic block static void computeLiveInValues(BasicBlock::reverse_iterator Begin, BasicBlock::reverse_iterator End, SetVector<Value *> &LiveTmp, GCStrategy *GC) { … } static void computeLiveOutSeed(BasicBlock *BB, SetVector<Value *> &LiveTmp, GCStrategy *GC) { … } static SetVector<Value *> computeKillSet(BasicBlock *BB, GCStrategy *GC) { … } #ifndef NDEBUG /// Check that the items in 'Live' dominate 'TI'. This is used as a basic /// validation check for the liveness computation. static void checkBasicSSA(DominatorTree &DT, SetVector<Value *> &Live, Instruction *TI, bool TermOkay = false) { for (Value *V : Live) { if (auto *I = dyn_cast<Instruction>(V)) { // The terminator can be a member of the LiveOut set. LLVM's definition // of instruction dominance states that V does not dominate itself. As // such, we need to special case this to allow it. if (TermOkay && TI == I) continue; assert(DT.dominates(I, TI) && "basic SSA liveness expectation violated by liveness analysis"); } } } /// Check that all the liveness sets used during the computation of liveness /// obey basic SSA properties. This is useful for finding cases where we miss /// a def. static void checkBasicSSA(DominatorTree &DT, GCPtrLivenessData &Data, BasicBlock &BB) { checkBasicSSA(DT, Data.LiveSet[&BB], BB.getTerminator()); checkBasicSSA(DT, Data.LiveOut[&BB], BB.getTerminator(), true); checkBasicSSA(DT, Data.LiveIn[&BB], BB.getTerminator()); } #endif static void computeLiveInValues(DominatorTree &DT, Function &F, GCPtrLivenessData &Data, GCStrategy *GC) { … } static void findLiveSetAtInst(Instruction *Inst, GCPtrLivenessData &Data, StatepointLiveSetTy &Out, GCStrategy *GC) { … } static void recomputeLiveInValues(GCPtrLivenessData &RevisedLivenessData, CallBase *Call, PartiallyConstructedSafepointRecord &Info, PointerToBaseTy &PointerToBase, GCStrategy *GC) { … }
Codebase Browser
llvm