diff --git a/llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp b/llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp --- a/llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp +++ b/llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp @@ -258,6 +258,7 @@ // base relation will remain. Internally, we add a mixture of the two // types, then update all the second type to the first type using DefiningValueMapTy = MapVector; +using PointerToBaseTy = MapVector; using StatepointLiveSetTy = SetVector; using RematerializedValueMapTy = MapVector, AssertingVH>; @@ -266,9 +267,6 @@ /// The set of values known to be live across this safepoint StatepointLiveSetTy LiveSet; - /// Mapping from live pointers to a base-defining-value - MapVector PointerToBase; - /// The *new* gc.statepoint instruction itself. This produces the token /// that normal path gc.relocates and the gc.result are tied to. GCStatepointInst *StatepointToken; @@ -1255,10 +1253,9 @@ // 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, - MapVector &PointerToBase, - DominatorTree *DT, DefiningValueMapTy &DVCache) { +static void findBasePointers(const StatepointLiveSetTy &live, + PointerToBaseTy &PointerToBase, DominatorTree *DT, + DefiningValueMapTy &DVCache) { for (Value *ptr : live) { Value *base = findBasePointer(ptr, DVCache); assert(base && "failed to find base pointer"); @@ -1274,8 +1271,8 @@ /// parse point. static void findBasePointers(DominatorTree &DT, DefiningValueMapTy &DVCache, CallBase *Call, - PartiallyConstructedSafepointRecord &result) { - MapVector PointerToBase; + PartiallyConstructedSafepointRecord &result, + PointerToBaseTy &PointerToBase) { StatepointLiveSetTy PotentiallyDerivedPointers = result.LiveSet; // We assume that all pointers passed to deopt are base pointers; as an // optimization, we can use this to avoid seperately materializing the base @@ -1290,37 +1287,27 @@ PointerToBase[V] = V; } findBasePointers(PotentiallyDerivedPointers, PointerToBase, &DT, DVCache); - - if (PrintBasePointers) { - errs() << "Base Pairs (w/o Relocation):\n"; - for (auto &Pair : PointerToBase) { - errs() << " derived "; - Pair.first->printAsOperand(errs(), false); - errs() << " base "; - Pair.second->printAsOperand(errs(), false); - errs() << "\n";; - } - } - - result.PointerToBase = PointerToBase; } /// 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); + PartiallyConstructedSafepointRecord &result, + PointerToBaseTy &PointerToBase); static void recomputeLiveInValues( Function &F, DominatorTree &DT, ArrayRef toUpdate, - MutableArrayRef records) { + MutableArrayRef records, + PointerToBaseTy &PointerToBase) { // TODO-PERF: reuse the original liveness, then simply run the dataflow // again. The old values are still live and will help it stabilize quickly. GCPtrLivenessData RevisedLivenessData; computeLiveInValues(DT, F, RevisedLivenessData); for (size_t i = 0; i < records.size(); i++) { struct PartiallyConstructedSafepointRecord &info = records[i]; - recomputeLiveInValues(RevisedLivenessData, toUpdate[i], info); + recomputeLiveInValues(RevisedLivenessData, toUpdate[i], info, + PointerToBase); } } @@ -1537,7 +1524,8 @@ const SmallVectorImpl &BasePtrs, const SmallVectorImpl &LiveVariables, PartiallyConstructedSafepointRecord &Result, - std::vector &Replacements) { + std::vector &Replacements, + const PointerToBaseTy &PointerToBase) { assert(BasePtrs.size() == LiveVariables.size()); // Then go ahead and use the builder do actually do the inserts. We insert @@ -1626,10 +1614,10 @@ auto &Context = Call->getContext(); auto &DL = Call->getModule()->getDataLayout(); auto GetBaseAndOffset = [&](Value *Derived) { - assert(Result.PointerToBase.count(Derived)); + assert(PointerToBase.count(Derived)); unsigned AddressSpace = Derived->getType()->getPointerAddressSpace(); unsigned IntPtrSize = DL.getPointerSizeInBits(AddressSpace); - Value *Base = Result.PointerToBase.find(Derived)->second; + Value *Base = PointerToBase.find(Derived)->second; Value *Base_int = Builder.CreatePtrToInt( Base, Type::getIntNTy(Context, IntPtrSize)); Value *Derived_int = Builder.CreatePtrToInt( @@ -1819,9 +1807,9 @@ static void makeStatepointExplicit(DominatorTree &DT, CallBase *Call, PartiallyConstructedSafepointRecord &Result, - std::vector &Replacements) { + std::vector &Replacements, + const PointerToBaseTy &PointerToBase) { const auto &LiveSet = Result.LiveSet; - const auto &PointerToBase = Result.PointerToBase; // Convert to vector for efficient cross referencing. SmallVector BaseVec, LiveVec; @@ -1836,7 +1824,8 @@ assert(LiveVec.size() == BaseVec.size()); // Do the actual rewriting and delete the old statepoint - makeStatepointExplicitImpl(Call, BaseVec, LiveVec, Result, Replacements); + makeStatepointExplicitImpl(Call, BaseVec, LiveVec, Result, Replacements, + PointerToBase); } // Helper function for the relocationViaAlloca. @@ -2238,6 +2227,7 @@ // relocated values we don't do any user adjustments here. static void rematerializeLiveValues(CallBase *Call, PartiallyConstructedSafepointRecord &Info, + PointerToBaseTy &PointerToBase, TargetTransformInfo &TTI) { const unsigned int ChainLengthThreshold = 10; @@ -2248,7 +2238,7 @@ for (Value *LiveValue: Info.LiveSet) { // For each live pointer find its defining chain SmallVector ChainToBase; - assert(Info.PointerToBase.count(LiveValue)); + assert(PointerToBase.count(LiveValue)); Value *RootOfChain = findRematerializableChainToBasePointer(ChainToBase, LiveValue); @@ -2260,9 +2250,9 @@ // Handle the scenario where the RootOfChain is not equal to the // Base Value, but they are essentially the same phi values. - if (RootOfChain != Info.PointerToBase[LiveValue]) { + if (RootOfChain != PointerToBase[LiveValue]) { PHINode *OrigRootPhi = dyn_cast(RootOfChain); - PHINode *AlternateRootPhi = dyn_cast(Info.PointerToBase[LiveValue]); + PHINode *AlternateRootPhi = dyn_cast(PointerToBase[LiveValue]); if (!OrigRootPhi || !AlternateRootPhi) continue; // PHI nodes that have the same incoming values, and belonging to the same @@ -2362,7 +2352,7 @@ Instruction *InsertBefore = Call->getNextNode(); assert(InsertBefore); Instruction *RematerializedValue = rematerializeChain( - InsertBefore, RootOfChain, Info.PointerToBase[LiveValue]); + InsertBefore, RootOfChain, PointerToBase[LiveValue]); Info.RematerializedValues[RematerializedValue] = LiveValue; } else { auto *Invoke = cast(Call); @@ -2373,9 +2363,9 @@ &*Invoke->getUnwindDest()->getFirstInsertionPt(); Instruction *NormalRematerializedValue = rematerializeChain( - NormalInsertBefore, RootOfChain, Info.PointerToBase[LiveValue]); + NormalInsertBefore, RootOfChain, PointerToBase[LiveValue]); Instruction *UnwindRematerializedValue = rematerializeChain( - UnwindInsertBefore, RootOfChain, Info.PointerToBase[LiveValue]); + UnwindInsertBefore, RootOfChain, PointerToBase[LiveValue]); Info.RematerializedValues[NormalRematerializedValue] = LiveValue; Info.RematerializedValues[UnwindRematerializedValue] = LiveValue; @@ -2491,10 +2481,24 @@ // site. findLiveReferences(F, DT, ToUpdate, Records); + /// Global mapping from live pointers to a base-defining-value. + PointerToBaseTy PointerToBase; + // B) Find the base pointers for each live pointer for (size_t i = 0; i < Records.size(); i++) { PartiallyConstructedSafepointRecord &info = Records[i]; - findBasePointers(DT, DVCache, ToUpdate[i], info); + findBasePointers(DT, DVCache, ToUpdate[i], info, PointerToBase); + } + if (PrintBasePointers) { + errs() << "Base Pairs (w/o Relocation):\n"; + for (auto &Pair : PointerToBase) { + errs() << " derived "; + Pair.first->printAsOperand(errs(), false); + errs() << " base "; + Pair.second->printAsOperand(errs(), false); + errs() << "\n"; + ; + } } // The base phi insertion logic (for any safepoint) may have inserted new @@ -2515,8 +2519,10 @@ PartiallyConstructedSafepointRecord &Info = Records[i]; SmallVector Bases; - for (auto Pair : Info.PointerToBase) - Bases.push_back(Pair.second); + for (auto *Derived : Info.LiveSet) { + assert(PointerToBase.count(Derived) && "Missed base for derived pointer"); + Bases.push_back(PointerToBase[Derived]); + } insertUseHolderAfter(ToUpdate[i], Bases, Holders); } @@ -2524,18 +2530,16 @@ // By selecting base pointers, we've effectively inserted new uses. Thus, we // need to rerun liveness. We may *also* have inserted new defs, but that's // not the key issue. - recomputeLiveInValues(F, DT, ToUpdate, Records); + recomputeLiveInValues(F, DT, ToUpdate, Records, PointerToBase); if (PrintBasePointers) { - for (auto &Info : Records) { - errs() << "Base Pairs: (w/Relocation)\n"; - for (auto Pair : Info.PointerToBase) { - errs() << " derived "; - Pair.first->printAsOperand(errs(), false); - errs() << " base "; - Pair.second->printAsOperand(errs(), false); - errs() << "\n"; - } + errs() << "Base Pairs: (w/Relocation)\n"; + for (auto Pair : PointerToBase) { + errs() << " derived "; + Pair.first->printAsOperand(errs(), false); + errs() << " base "; + Pair.second->printAsOperand(errs(), false); + errs() << "\n"; } } @@ -2547,10 +2551,12 @@ // Note that the relocation placement code relies on this filtering for // correctness as it expects the base to be in the liveset, which isn't true // if the base is constant. - for (auto &Info : Records) - for (auto &BasePair : Info.PointerToBase) - if (isa(BasePair.second)) - Info.LiveSet.remove(BasePair.first); + for (auto &Info : Records) { + Info.LiveSet.remove_if([&](Value *LiveV) { + assert(PointerToBase.count(LiveV) && "Missed base for derived pointer"); + return isa(PointerToBase[LiveV]); + }); + } for (CallInst *CI : Holders) CI->eraseFromParent(); @@ -2561,7 +2567,7 @@ // some values instead of relocating them. This is purely an optimization and // does not influence correctness. for (size_t i = 0; i < Records.size(); i++) - rematerializeLiveValues(ToUpdate[i], Records[i], TTI); + rematerializeLiveValues(ToUpdate[i], Records[i], PointerToBase, TTI); // We need this to safely RAUW and delete call or invoke return values that // may themselves be live over a statepoint. For details, please see usage in @@ -2575,7 +2581,8 @@ // previous statepoint can not be a live variable, thus we can and remove // the old statepoint calls as we go.) for (size_t i = 0; i < Records.size(); i++) - makeStatepointExplicit(DT, ToUpdate[i], Records[i], Replacements); + makeStatepointExplicit(DT, ToUpdate[i], Records[i], Replacements, + PointerToBase); ToUpdate.clear(); // prevent accident use of invalid calls. @@ -2594,8 +2601,8 @@ // these live sets, and migrate to using that data structure from this point // onward. Info.LiveSet.clear(); - Info.PointerToBase.clear(); } + PointerToBase.clear(); // Do all the fixups of the original live variables to their relocated selves SmallVector Live; @@ -3115,35 +3122,15 @@ static void recomputeLiveInValues(GCPtrLivenessData &RevisedLivenessData, CallBase *Call, - PartiallyConstructedSafepointRecord &Info) { + PartiallyConstructedSafepointRecord &Info, + PointerToBaseTy &PointerToBase) { StatepointLiveSetTy Updated; findLiveSetAtInst(Call, RevisedLivenessData, Updated); // We may have base pointers which are now live that weren't before. We need // to update the PointerToBase structure to reflect this. for (auto V : Updated) - Info.PointerToBase.insert({V, V}); - -#ifndef NDEBUG - for (auto V : Updated) - assert(Info.PointerToBase.count(V) && - "Must be able to find base for live value!"); -#endif - - // Remove any stale base mappings - this can happen since our liveness is - // more precise then the one inherent in the base pointer analysis. - DenseSet ToErase; - for (auto KVPair : Info.PointerToBase) - if (!Updated.count(KVPair.first)) - ToErase.insert(KVPair.first); - - for (auto *V : ToErase) - Info.PointerToBase.erase(V); - -#ifndef NDEBUG - for (auto KVPair : Info.PointerToBase) - assert(Updated.count(KVPair.first) && "record for non-live value"); -#endif + PointerToBase.insert({ V, V }); Info.LiveSet = Updated; }