Index: llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp =================================================================== --- llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp +++ llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp @@ -125,6 +125,9 @@ static bool shouldRewriteStatepointsIn(Function &F); +// Returns true is V is a knownBaseResult. +static bool isKnownBaseResult(Value *V); + PreservedAnalyses RewriteStatepointsForGC::run(Module &M, ModuleAnalysisManager &AM) { bool Changed = false; @@ -230,6 +233,72 @@ namespace { +/// A single base defining value - An immediate base defining value for an +/// instruction 'Def' is an input to 'Def' whose base is also a base of 'Def'. +/// For instructions which have multiple pointer [vector] inputs or that +/// transition between vector and scalar types, there is no immediate base +/// defining value. The 'base defining value' for 'Def' is the transitive +/// closure of this relation stopping at the first instruction which has no +/// immediate base defining value. The b.d.v. might itself be a base pointer, +/// but it can also be an arbitrary derived pointer. +struct BaseDefiningValueResult { + explicit BaseDefiningValueResult(Value *BDV = nullptr, + bool IsKnownBase = false) + : BDV(BDV), IsKnownBase(IsKnownBase) { +#ifndef NDEBUG + // Check consistency between new and old means of checking whether a BDV is + // a base. + if (BDV && BDV != DenseMapInfo::getEmptyKey() && + BDV != DenseMapInfo::getTombstoneKey()) { + bool MustBeBase = isKnownBaseResult(BDV); + assert(!MustBeBase || MustBeBase == IsKnownBase); + } +#endif + } + + Value *getBDV() { return BDV; } + const Value *getBDV() const { return BDV; } + bool isKnownBase() const { return IsKnownBase; } + + bool operator==(const BaseDefiningValueResult &Other) const { + return BDV == Other.BDV && IsKnownBase == Other.IsKnownBase; + } + +private: + friend struct DenseMapInfo; + + /// Contains the value which is the base defining value. + Value *BDV; + + /// True if the base defining value is also known to be an actual base + /// pointer. + bool IsKnownBase; +}; + +} // end anonymous namespace + +template <> struct llvm::DenseMapInfo { + static BaseDefiningValueResult getEmptyKey() { + return BaseDefiningValueResult(DenseMapInfo::getEmptyKey()); + } + static BaseDefiningValueResult getTombstoneKey() { + return BaseDefiningValueResult(DenseMapInfo::getTombstoneKey()); + } + static unsigned getHashValue(const BaseDefiningValueResult &S) { + assert(!isEqual(S, getEmptyKey()) && "Cannot hash the empty key!"); + assert(!isEqual(S, getTombstoneKey()) && "Cannot hash the tombstone key!"); + return hash_combine(S.getBDV(), S.isKnownBase()); + } + static bool isEqual(const BaseDefiningValueResult &LHS, + const BaseDefiningValueResult &RHS) { + // dbgs() << "LHS BDV = " << LHS.getBDV() << ", RHS BDV = " << RHS.getBDV() << "LHS IsKnownBase = " << LHS.isKnownBase() << ", RHS IsKnownBase = " << RHS.isKnownBase() << "\n"; + return LHS.getBDV() == RHS.getBDV() && + LHS.isKnownBase() == RHS.isKnownBase(); + } +}; + +namespace { + struct GCPtrLivenessData { /// Values defined in this block. MapVector> KillSet; @@ -257,7 +326,7 @@ // 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 -using DefiningValueMapTy = MapVector; +using DefiningValueMapTy = MapVector; using PointerToBaseTy = MapVector; using StatepointLiveSetTy = SetVector; using RematerializedValueMapTy = @@ -395,44 +464,10 @@ Result.LiveSet = LiveSet; } -// Returns true is V is a knownBaseResult. -static bool isKnownBaseResult(Value *V); - // Returns true if V is a BaseResult that already exists in the IR, i.e. it is // not created by the findBasePointers algorithm. static bool isOriginalBaseResult(Value *V); -namespace { - -/// A single base defining value - An immediate base defining value for an -/// instruction 'Def' is an input to 'Def' whose base is also a base of 'Def'. -/// For instructions which have multiple pointer [vector] inputs or that -/// transition between vector and scalar types, there is no immediate base -/// defining value. The 'base defining value' for 'Def' is the transitive -/// closure of this relation stopping at the first instruction which has no -/// immediate base defining value. The b.d.v. might itself be a base pointer, -/// but it can also be an arbitrary derived pointer. -struct BaseDefiningValueResult { - /// Contains the value which is the base defining value. - Value * const BDV; - - /// True if the base defining value is also known to be an actual base - /// pointer. - const bool IsKnownBase; - - BaseDefiningValueResult(Value *BDV, bool IsKnownBase) - : BDV(BDV), IsKnownBase(IsKnownBase) { -#ifndef NDEBUG - // Check consistency between new and old means of checking whether a BDV is - // a base. - bool MustBeBase = isKnownBaseResult(BDV); - assert(!MustBeBase || MustBeBase == IsKnownBase); -#endif - } -}; - -} // end anonymous namespace - static BaseDefiningValueResult findBaseDefiningValue(Value *I); /// Return a base defining value for the 'Index' element of the given vector @@ -637,22 +672,25 @@ } /// Returns the base defining value for this value. -static Value *findBaseDefiningValueCached(Value *I, DefiningValueMapTy &Cache) { - Value *&Cached = Cache[I]; - if (!Cached) { - Cached = findBaseDefiningValue(I).BDV; +static BaseDefiningValueResult +findBaseDefiningValueCached(Value *I, DefiningValueMapTy &Cache) { + auto It = Cache.find(I); + if (It == Cache.end()) { + Cache[I] = findBaseDefiningValue(I); LLVM_DEBUG(dbgs() << "fBDV-cached: " << I->getName() << " -> " - << Cached->getName() << "\n"); + << Cache[I].getBDV()->getName() << ", is known base = " + << Cache[I].isKnownBase() << "\n"); } - assert(Cache[I] != nullptr); - return Cached; + assert(Cache[I].getBDV() != nullptr); + return Cache[I]; } /// Return a base pointer for this value if known. Otherwise, return it's /// base defining value. -static Value *findBaseOrBDV(Value *I, DefiningValueMapTy &Cache) { - Value *Def = findBaseDefiningValueCached(I, Cache); - auto Found = Cache.find(Def); +static BaseDefiningValueResult findBaseOrBDV(Value *I, + DefiningValueMapTy &Cache) { + auto Def = findBaseDefiningValueCached(I, Cache); + auto Found = Cache.find(Def.getBDV()); if (Found != Cache.end()) { // Either a base-of relation, or a self reference. Caller must check. return Found->second; @@ -812,9 +850,10 @@ /// the base pointer. (This is reliable and can be used for relocation.) On /// failure, returns nullptr. static Value *findBasePointer(Value *I, DefiningValueMapTy &Cache) { - Value *Def = findBaseOrBDV(I, Cache); + auto DefBase = findBaseOrBDV(I, Cache); + Value *Def = DefBase.getBDV(); - if (isKnownBaseResult(Def) && areBothVectorOrScalar(Def, I)) + if (DefBase.isKnownBase() && areBothVectorOrScalar(Def, I)) return Def; // Here's the rough algorithm: @@ -852,12 +891,12 @@ // We use the order of insertion (DFS over the def/use graph) to provide a // stable deterministic ordering for visiting DenseMaps (which are unordered) // below. This is important for deterministic compilation. - MapVector States; + MapVector States; #ifndef NDEBUG auto VerifyStates = [&]() { for (auto &Entry : States) { - assert(Entry.first == Entry.second.getOriginalValue()); + assert(Entry.first.getBDV() == Entry.second.getOriginalValue()); } }; #endif @@ -891,24 +930,25 @@ /* scope */ { SmallVector Worklist; Worklist.push_back(Def); - States.insert({Def, BDVState(Def)}); + States.insert({DefBase, BDVState(Def)}); while (!Worklist.empty()) { Value *Current = Worklist.pop_back_val(); assert(!isOriginalBaseResult(Current) && "why did it get added?"); auto visitIncomingValue = [&](Value *InVal) { - Value *Base = findBaseOrBDV(InVal, Cache); - if (isKnownBaseResult(Base) && areBothVectorOrScalar(Base, InVal)) + auto Base = findBaseOrBDV(InVal, Cache); + if (Base.isKnownBase() && areBothVectorOrScalar(Base.getBDV(), InVal)) // Known bases won't need new instructions introduced and can be // ignored safely. However, this can only be done when InVal and Base // are both scalar or both vector. Otherwise, we need to find a // correct BDV for InVal, by creating an entry in the lattice // (States). return; - assert(isExpectedBDVType(Base) && "the only non-base values " + Value *BDV = Base.getBDV(); + assert(isExpectedBDVType(BDV) && "the only non-base values " "we see should be base defining values"); - if (States.insert(std::make_pair(Base, BDVState(Base))).second) - Worklist.push_back(Base); + if (States.insert(std::make_pair(Base, BDVState(BDV))).second) + Worklist.push_back(BDV); }; visitBDVOperands(Current, visitIncomingValue); @@ -919,7 +959,8 @@ VerifyStates(); LLVM_DEBUG(dbgs() << "States after initialization:\n"); for (const auto &Pair : States) { - LLVM_DEBUG(dbgs() << " " << Pair.second << " for " << *Pair.first << "\n"); + LLVM_DEBUG(dbgs() << " " << Pair.second << " for " << *Pair.first.getBDV() + << "\n"); } #endif @@ -928,22 +969,24 @@ // reuse existing values when the derived pointer we were asked to materialize // a base pointer for happens to be a base pointer itself. (Or a sub-graph // feeding it does.) - SmallVector ToRemove; + SmallVector ToRemove; do { ToRemove.clear(); for (auto Pair : States) { - Value *BDV = Pair.first; + auto &Base = Pair.first; + Value *BDV = Base.getBDV(); auto canPruneInput = [&](Value *V) { // If the input of the BDV is the BDV itself we can prune it. This is // only possible if the BDV is a PHI node. if (V->stripPointerCasts() == BDV) return true; - Value *VBDV = findBaseOrBDV(V, Cache); + auto VBase = findBaseOrBDV(V, Cache); + Value *VBDV = VBase.getBDV(); if (V->stripPointerCasts() != VBDV) return false; // The assumption is that anything not in the state list is // propagates a base pointer. - return States.count(VBDV) == 0; + return States.count(VBase) == 0; }; bool CanPrune = true; @@ -951,27 +994,27 @@ CanPrune = CanPrune && canPruneInput(Op); }); if (CanPrune) - ToRemove.push_back(BDV); + ToRemove.push_back(Base); } - for (Value *V : ToRemove) { + for (auto &V : ToRemove) { States.erase(V); // Cache the fact V is it's own base for later usage. - Cache[V] = V; + Cache[V.getBDV()] = V; } } while (!ToRemove.empty()); // Did we manage to prove that Def itself must be a base pointer? - if (!States.count(Def)) + if (!States.count(DefBase)) return Def; // Return a phi state for a base defining value. We'll generate a new // base state for known bases and expect to find a cached state otherwise. - auto GetStateForBDV = [&](Value *BaseValue, Value *Input) { + auto GetStateForBDV = [&](BaseDefiningValueResult &BaseValue, Value *Input) { auto I = States.find(BaseValue); if (I != States.end()) return I->second; - assert(areBothVectorOrScalar(BaseValue, Input)); - return BDVState(BaseValue, BDVState::Base, BaseValue); + assert(areBothVectorOrScalar(BaseValue.getBDV(), Input)); + return BDVState(BaseValue.getBDV(), BDVState::Base, BaseValue.getBDV()); }; bool Progress = true; @@ -985,25 +1028,27 @@ // effect the result. TODO: We could use a worklist here and make this run // much faster. for (auto Pair : States) { - Value *BDV = Pair.first; + auto &Base = Pair.first; + Value *BDV = Base.getBDV(); // Only values that do not have known bases or those that have differing // type (scalar versus vector) from a possible known base should be in the // lattice. - assert((!isKnownBaseResult(BDV) || + assert((!Base.isKnownBase() || !areBothVectorOrScalar(BDV, Pair.second.getBaseValue())) && "why did it get added?"); BDVState NewState(BDV); visitBDVOperands(BDV, [&](Value *Op) { - Value *BDV = findBaseOrBDV(Op, Cache); - auto OpState = GetStateForBDV(BDV, Op); + auto BaseOrBDV = findBaseOrBDV(Op, Cache); + Value *BDV = BaseOrBDV.getBDV(); + auto OpState = GetStateForBDV(BaseOrBDV, Op); NewState.meet(OpState); }); - BDVState OldState = States[BDV]; + BDVState OldState = States[Base]; if (OldState != NewState) { Progress = true; - States[BDV] = NewState; + States[Base] = NewState; } } @@ -1015,21 +1060,24 @@ VerifyStates(); LLVM_DEBUG(dbgs() << "States after meet iteration:\n"); for (const auto &Pair : States) { - LLVM_DEBUG(dbgs() << " " << Pair.second << " for " << *Pair.first << "\n"); + LLVM_DEBUG(dbgs() << " " << Pair.second << " for " << *Pair.first.getBDV() + << "\n"); } #endif // Handle all instructions that have a vector BDV, but the instruction itself // is of scalar type. for (auto Pair : States) { - Instruction *I = cast(Pair.first); + auto &V = Pair.first; + Instruction *I = cast(V.getBDV()); BDVState State = Pair.second; auto *BaseValue = State.getBaseValue(); // Only values that do not have known bases or those that have differing // type (scalar versus vector) from a possible known base should be in the // lattice. - assert((!isKnownBaseResult(I) || !areBothVectorOrScalar(I, BaseValue)) && - "why did it get added?"); + assert( + (!Pair.first.isKnownBase() || !areBothVectorOrScalar(I, BaseValue)) && + "why did it get added?"); assert(!State.isUnknown() && "Optimistic algorithm didn't complete!"); if (!State.isBase() || !isa(BaseValue->getType())) @@ -1046,14 +1094,14 @@ auto *BaseInst = ExtractElementInst::Create( State.getBaseValue(), EE->getIndexOperand(), "base_ee", EE); BaseInst->setMetadata("is_base_value", MDNode::get(I->getContext(), {})); - States[I] = BDVState(I, BDVState::Base, BaseInst); + States[V] = BDVState(I, BDVState::Base, BaseInst); } else if (!isa(I->getType())) { // We need to handle cases that have a vector base but the instruction is // a scalar type (these could be phis or selects or any instruction that // are of scalar type, but the base can be a vector type). We // conservatively set this as conflict. Setting the base value for these // conflicts is handled in the next loop which traverses States. - States[I] = BDVState(I, BDVState::Conflict); + States[V] = BDVState(I, BDVState::Conflict); } } @@ -1064,12 +1112,14 @@ // Insert Phis for all conflicts // TODO: adjust naming patterns to avoid this order of iteration dependency for (auto Pair : States) { - Instruction *I = cast(Pair.first); + auto &V = Pair.first; + Instruction *I = cast(V.getBDV()); BDVState State = Pair.second; // Only values that do not have known bases or those that have differing // type (scalar versus vector) from a possible known base should be in the // lattice. - assert((!isKnownBaseResult(I) || !areBothVectorOrScalar(I, State.getBaseValue())) && + assert((!Pair.first.isKnownBase() || + !areBothVectorOrScalar(I, State.getBaseValue())) && "why did it get added?"); assert(!State.isUnknown() && "Optimistic algorithm didn't complete!"); @@ -1100,7 +1150,7 @@ BaseInst->setName(getMangledName(I)); // Add metadata marking this as a base value BaseInst->setMetadata("is_base_value", MDNode::get(I->getContext(), {})); - States[I] = BDVState(I, BDVState::Conflict, BaseInst); + States[V] = BDVState(I, BDVState::Conflict, BaseInst); } #ifndef NDEBUG @@ -1116,15 +1166,16 @@ // assured to be able to determine an instruction which produces it's base // pointer. auto getBaseForInput = [&](Value *Input, Instruction *InsertPt) { - Value *BDV = findBaseOrBDV(Input, Cache); + auto InputBaseOrBDV = findBaseOrBDV(Input, Cache); + Value *BDV = InputBaseOrBDV.getBDV(); Value *Base = nullptr; - if (!States.count(BDV)) { + if (!States.count(InputBaseOrBDV)) { assert(areBothVectorOrScalar(BDV, Input)); Base = BDV; } else { // Either conflict or base. - assert(States.count(BDV)); - Base = States[BDV].getBaseValue(); + assert(States.count(InputBaseOrBDV)); + Base = States[InputBaseOrBDV].getBaseValue(); } assert(Base && "Can't be null"); // The cast is needed since base traversal may strip away bitcasts @@ -1137,13 +1188,13 @@ // deterministic and predictable because we're naming newly created // instructions. for (auto Pair : States) { - Instruction *BDV = cast(Pair.first); + Instruction *BDV = cast(Pair.first.getBDV()); BDVState State = Pair.second; // Only values that do not have known bases or those that have differing // type (scalar versus vector) from a possible known base should be in the // lattice. - assert((!isKnownBaseResult(BDV) || + assert((!Pair.first.isKnownBase() || !areBothVectorOrScalar(BDV, State.getBaseValue())) && "why did it get added?"); assert(!State.isUnknown() && "Optimistic algorithm didn't complete!"); @@ -1239,25 +1290,26 @@ // NOTE: This is actually two caches: one of the base defining value // relation and one of the base pointer relation! FIXME for (auto Pair : States) { - auto *BDV = Pair.first; + auto *BDV = Pair.first.getBDV(); Value *Base = Pair.second.getBaseValue(); assert(BDV && Base); // Only values that do not have known bases or those that have differing // type (scalar versus vector) from a possible known base should be in the // lattice. - assert((!isKnownBaseResult(BDV) || !areBothVectorOrScalar(BDV, Base)) && + assert((!Pair.first.isKnownBase() || !areBothVectorOrScalar(BDV, Base)) && "why did it get added?"); - LLVM_DEBUG( - dbgs() << "Updating base value cache" - << " for: " << BDV->getName() << " from: " - << (Cache.count(BDV) ? Cache[BDV]->getName().str() : "none") - << " to: " << Base->getName() << "\n"); + LLVM_DEBUG(dbgs() << "Updating base value cache" + << " for: " << BDV->getName() << " from: " + << (Cache.count(BDV) + ? Cache[BDV].getBDV()->getName().str() + : "none") + << " to: " << Base->getName() << "\n"); - Cache[BDV] = Base; + Cache[BDV] = BaseDefiningValueResult(Base, /*IsKnownBase=*/true); } assert(Cache.count(Def)); - return Cache[Def]; + return Cache[Def].getBDV(); } // For a set of live pointers (base and/or derived), identify the base @@ -2441,7 +2493,7 @@ auto *BaseBC = IRBuilder<>(Callsite).CreateBitCast( Base, Callsite->getType(), suffixed_name_or(Base, ".cast", "")); if (BaseBC != Base) - DVCache[BaseBC] = Base; + DVCache[BaseBC] = BaseDefiningValueResult(Base, /*IsKnownBase=*/true); Callsite->replaceAllUsesWith(BaseBC); if (!BaseBC->hasName()) BaseBC->takeName(Callsite);