Index: llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp =================================================================== --- llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp +++ 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 IsKnownBaseMapTy = MapVector; using PointerToBaseTy = MapVector; using StatepointLiveSetTy = SetVector; using RematerializedValueMapTy = @@ -402,38 +403,7 @@ // 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); +static Value *findBaseDefiningValue(Value *I, 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 @@ -444,76 +414,92 @@ /// 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 BaseDefiningValueResult -findBaseDefiningValueOfVector(Value *I) { +static Value *findBaseDefiningValueOfVector(Value *I, + IsKnownBaseMapTy &KnownBases) { // Each case parallels findBaseDefiningValue below, see that code for // detailed motivation. - if (isa(I)) + if (isa(I)) { // An incoming argument to the function is a base pointer - return BaseDefiningValueResult(I, true); + KnownBases[I] = true; + return I; + } - if (isa(I)) + if (isa(I)) { // Base of constant vector consists only of constant null pointers. // For reasoning see similar case inside 'findBaseDefiningValue' function. - return BaseDefiningValueResult(ConstantAggregateZero::get(I->getType()), - true); + auto *CAZ = ConstantAggregateZero::get(I->getType()); + KnownBases[CAZ] = true; + return CAZ; + } - if (isa(I)) - return BaseDefiningValueResult(I, true); + if (isa(I)) { + KnownBases[I] = true; + return I; + } - if (isa(I)) + if (isa(I)) { // We don't know whether this vector contains entirely base pointers or // not. To be conservatively correct, we treat it as a BDV and will // duplicate code as needed to construct a parallel vector of bases. - return BaseDefiningValueResult(I, false); + KnownBases[I] = false; + return I; + } - if (isa(I)) + if (isa(I)) { // We don't know whether this vector contains entirely base pointers or // not. To be conservatively correct, we treat it as a BDV and will // duplicate code as needed to construct a parallel vector of bases. // TODO: There a number of local optimizations which could be applied here // for particular sufflevector patterns. - return BaseDefiningValueResult(I, false); + KnownBases[I] = false; + return I; + } // The behavior of getelementptr instructions is the same for vector and // non-vector data types. if (auto *GEP = dyn_cast(I)) - return findBaseDefiningValue(GEP->getPointerOperand()); + return findBaseDefiningValue(GEP->getPointerOperand(), KnownBases); // If the pointer comes through a bitcast of a vector of pointers to // a vector of another type of pointer, then look through the bitcast if (auto *BC = dyn_cast(I)) - return findBaseDefiningValue(BC->getOperand(0)); + return findBaseDefiningValue(BC->getOperand(0), KnownBases); // We assume that functions in the source language only return base // pointers. This should probably be generalized via attributes to support // both source language and internal functions. - if (isa(I) || isa(I)) - return BaseDefiningValueResult(I, true); + if (isa(I) || isa(I)) { + KnownBases[I] = true; + return I; + } // A PHI or Select is a base defining value. The outer findBasePointer // algorithm is responsible for constructing a base value for this BDV. assert((isa(I) || isa(I)) && "unknown vector instruction - no base found for vector element"); - return BaseDefiningValueResult(I, false); + KnownBases[I] = false; + return I; } /// 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 BaseDefiningValueResult findBaseDefiningValue(Value *I) { +static Value * +findBaseDefiningValue(Value *I, IsKnownBaseMapTy &KnownBases) { assert(I->getType()->isPtrOrPtrVectorTy() && "Illegal to ask for the base pointer of a non-pointer type"); if (I->getType()->isVectorTy()) - return findBaseDefiningValueOfVector(I); + return findBaseDefiningValueOfVector(I, KnownBases); - if (isa(I)) + if (isa(I)) { // An incoming argument to the function is a base pointer // We should have never reached here if this argument isn't an gc value - return BaseDefiningValueResult(I, true); + KnownBases[I] = true; + return I; + } if (isa(I)) { // We assume that objects with a constant base (e.g. a global) can't move @@ -525,9 +511,10 @@ // trying to avoid problems reporting various conflicts in a form of // "phi (const1, const2)" or "phi (const, regular gc ptr)". // See constant.ll file for relevant test cases. - - return BaseDefiningValueResult( - ConstantPointerNull::get(cast(I->getType())), true); + + auto *CPN = ConstantPointerNull::get(cast(I->getType())); + KnownBases[CPN] = true; + return CPN; } // inttoptrs in an integral address space are currently ill-defined. We @@ -535,8 +522,10 @@ // constant rule above and because we don't really have a better semantic // to give them. Note that the optimizer is always free to insert undefined // behavior on dynamically dead paths as well. - if (isa(I)) - return BaseDefiningValueResult(I, true); + if (isa(I)) { + KnownBases[I] = true; + return I; + } if (CastInst *CI = dyn_cast(I)) { Value *Def = CI->stripPointerCasts(); @@ -549,19 +538,21 @@ // not simply a pointer cast (i.e. an inttoptr). We don't know how to // handle int->ptr conversion. assert(!isa(Def) && "shouldn't find another cast here"); - return findBaseDefiningValue(Def); + return findBaseDefiningValue(Def, KnownBases); } - if (isa(I)) + if (isa(I)) { // The value loaded is an gc base itself - return BaseDefiningValueResult(I, true); + KnownBases[I] = true; + return I; + } if (GetElementPtrInst *GEP = dyn_cast(I)) // The base of this GEP is the base - return findBaseDefiningValue(GEP->getPointerOperand()); + return findBaseDefiningValue(GEP->getPointerOperand(), KnownBases); if (auto *Freeze = dyn_cast(I)) - return findBaseDefiningValue(Freeze->getOperand(0)); + return findBaseDefiningValue(Freeze->getOperand(0), KnownBases); if (IntrinsicInst *II = dyn_cast(I)) { switch (II->getIntrinsicID()) { @@ -582,24 +573,28 @@ llvm_unreachable( "interaction with the gcroot mechanism is not supported"); case Intrinsic::experimental_gc_get_pointer_base: - return findBaseDefiningValue(II->getOperand(0)); + return findBaseDefiningValue(II->getOperand(0), KnownBases); } } // We assume that functions in the source language only return base // pointers. This should probably be generalized via attributes to support // both source language and internal functions. - if (isa(I) || isa(I)) - return BaseDefiningValueResult(I, true); + if (isa(I) || isa(I)) { + KnownBases[I] = true; + return I; + } // TODO: I have absolutely no idea how to implement this part yet. It's not // necessarily hard, I just haven't really looked at it yet. assert(!isa(I) && "Landing Pad is unimplemented"); - if (isa(I)) + if (isa(I)) { // A CAS is effectively a atomic store and load combined under a // predicate. From the perspective of base pointers, we just treat it // like a load. - return BaseDefiningValueResult(I, true); + KnownBases[I] = true; + return I; + } assert(!isa(I) && "Xchg handled above, all others are " "binary ops which don't apply to pointers"); @@ -607,8 +602,10 @@ // The aggregate ops. Aggregates can either be in the heap or on the // stack, but in either case, this is simply a field load. As a result, // this is a defining definition of the base just like a load is. - if (isa(I)) - return BaseDefiningValueResult(I, true); + if (isa(I)) { + KnownBases[I] = true; + return I; + } // We should never see an insert vector since that would require we be // tracing back a struct value not a pointer value. @@ -617,7 +614,7 @@ // This value might have been generated by findBasePointer() called when // substituting gc.get.pointer.base() intrinsic. - bool IsKnownBase = + KnownBases[I] = isa(I) && cast(I)->getMetadata("is_base_value"); // An extractelement produces a base result exactly when it's input does. @@ -628,7 +625,7 @@ // Note: There a lot of obvious peephole cases here. This are deliberately // handled after the main base pointer inference algorithm to make writing // test cases to exercise that code easier. - return BaseDefiningValueResult(I, IsKnownBase); + return I; // The last two cases here don't return a base pointer. Instead, they // return a value which dynamically selects from among several base @@ -636,25 +633,30 @@ // the caller to resolve these. assert((isa(I) || isa(I)) && "missing instruction case in findBaseDefiningValue"); - return BaseDefiningValueResult(I, IsKnownBase); + return I; } /// Returns the base defining value for this value. -static Value *findBaseDefiningValueCached(Value *I, DefiningValueMapTy &Cache) { +static Value *findBaseDefiningValueCached(Value *I, DefiningValueMapTy &Cache, + IsKnownBaseMapTy &KnownBases) { Value *&Cached = Cache[I]; if (!Cached) { - Cached = findBaseDefiningValue(I).BDV; + Cached = findBaseDefiningValue(I, KnownBases); LLVM_DEBUG(dbgs() << "fBDV-cached: " << I->getName() << " -> " - << Cached->getName() << "\n"); + << Cached->getName() << ", is known base = " + << KnownBases[I] << "\n"); } assert(Cache[I] != nullptr); + assert(KnownBases.find(Cache[I]) != KnownBases.end() && + "Cached value must be present in known bases map"); return Cached; } /// 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); +static Value *findBaseOrBDV(Value *I, DefiningValueMapTy &Cache, + IsKnownBaseMapTy &KnownBases) { + Value *Def = findBaseDefiningValueCached(I, Cache, KnownBases); auto Found = Cache.find(Def); if (Found != Cache.end()) { // Either a base-of relation, or a self reference. Caller must check. @@ -689,6 +691,10 @@ return false; } +static bool isKnownBase(Value *V, IsKnownBaseMapTy &KnownBases) { + return KnownBases[V]; +} + // Returns true if First and Second values are both scalar or both vector. static bool areBothVectorOrScalar(Value *First, Value *Second) { return isa(First->getType()) == @@ -814,10 +820,11 @@ /// 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) { - Value *Def = findBaseOrBDV(I, Cache); +static Value *findBasePointer(Value *I, DefiningValueMapTy &Cache, + IsKnownBaseMapTy &KnownBases) { + Value *Def = findBaseOrBDV(I, Cache, KnownBases); - if (isKnownBaseResult(Def) && areBothVectorOrScalar(Def, I)) + if (isKnownBase(Def, KnownBases) && areBothVectorOrScalar(Def, I)) return Def; // Here's the rough algorithm: @@ -900,8 +907,8 @@ assert(!isOriginalBaseResult(Current) && "why did it get added?"); auto visitIncomingValue = [&](Value *InVal) { - Value *Base = findBaseOrBDV(InVal, Cache); - if (isKnownBaseResult(Base) && areBothVectorOrScalar(Base, InVal)) + Value *Base = findBaseOrBDV(InVal, Cache, KnownBases); + if (isKnownBase(Base, KnownBases) && areBothVectorOrScalar(Base, 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 @@ -941,7 +948,7 @@ // only possible if the BDV is a PHI node. if (V->stripPointerCasts() == BDV) return true; - Value *VBDV = findBaseOrBDV(V, Cache); + Value *VBDV = findBaseOrBDV(V, Cache, KnownBases); if (V->stripPointerCasts() != VBDV) return false; // The assumption is that anything not in the state list is @@ -992,13 +999,13 @@ // 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((!isKnownBase(BDV, KnownBases) || !areBothVectorOrScalar(BDV, Pair.second.getBaseValue())) && "why did it get added?"); BDVState NewState(BDV); visitBDVOperands(BDV, [&](Value *Op) { - Value *BDV = findBaseOrBDV(Op, Cache); + Value *BDV = findBaseOrBDV(Op, Cache, KnownBases); auto OpState = GetStateForBDV(BDV, Op); NewState.meet(OpState); }); @@ -1031,8 +1038,9 @@ // 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( + (!isKnownBase(I, KnownBases) || !areBothVectorOrScalar(I, BaseValue)) && + "why did it get added?"); assert(!State.isUnknown() && "Optimistic algorithm didn't complete!"); if (!State.isBase() || !isa(BaseValue->getType())) @@ -1072,7 +1080,8 @@ // 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((!isKnownBase(I, KnownBases) || + !areBothVectorOrScalar(I, State.getBaseValue())) && "why did it get added?"); assert(!State.isUnknown() && "Optimistic algorithm didn't complete!"); @@ -1119,7 +1128,7 @@ // 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); + Value *BDV = findBaseOrBDV(Input, Cache, KnownBases); Value *Base = nullptr; if (!States.count(BDV)) { assert(areBothVectorOrScalar(BDV, Input)); @@ -1146,7 +1155,7 @@ // 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((!isKnownBase(BDV, KnownBases) || !areBothVectorOrScalar(BDV, State.getBaseValue())) && "why did it get added?"); assert(!State.isUnknown() && "Optimistic algorithm didn't complete!"); @@ -1248,8 +1257,9 @@ // 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)) && - "why did it get added?"); + assert( + (!isKnownBase(BDV, KnownBases) || !areBothVectorOrScalar(BDV, Base)) && + "why did it get added?"); LLVM_DEBUG( dbgs() << "Updating base value cache" @@ -1258,6 +1268,7 @@ << " to: " << Base->getName() << "\n"); Cache[BDV] = Base; + KnownBases[Base] = true; } assert(Cache.count(Def)); return Cache[Def]; @@ -1280,9 +1291,10 @@ // pointer was a base pointer. static void findBasePointers(const StatepointLiveSetTy &live, PointerToBaseTy &PointerToBase, DominatorTree *DT, - DefiningValueMapTy &DVCache) { + DefiningValueMapTy &DVCache, + IsKnownBaseMapTy &KnownBases) { for (Value *ptr : live) { - Value *base = findBasePointer(ptr, DVCache); + Value *base = findBasePointer(ptr, DVCache, KnownBases); assert(base && "failed to find base pointer"); PointerToBase[ptr] = base; assert((!isa(base) || !isa(ptr) || @@ -1297,7 +1309,8 @@ static void findBasePointers(DominatorTree &DT, DefiningValueMapTy &DVCache, CallBase *Call, PartiallyConstructedSafepointRecord &result, - PointerToBaseTy &PointerToBase) { + PointerToBaseTy &PointerToBase, + IsKnownBaseMapTy &KnownBases) { 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 @@ -1311,7 +1324,8 @@ PotentiallyDerivedPointers.remove(V); PointerToBase[V] = V; } - findBasePointers(PotentiallyDerivedPointers, PointerToBase, &DT, DVCache); + findBasePointers(PotentiallyDerivedPointers, PointerToBase, &DT, DVCache, + KnownBases); } /// Given an updated version of the dataflow liveness results, update the @@ -2430,7 +2444,8 @@ static bool inlineGetBaseAndOffset(Function &F, SmallVectorImpl &Intrinsics, - DefiningValueMapTy &DVCache) { + DefiningValueMapTy &DVCache, + IsKnownBaseMapTy &KnownBases) { auto &Context = F.getContext(); auto &DL = F.getParent()->getDataLayout(); bool Changed = false; @@ -2439,7 +2454,8 @@ switch (Callsite->getIntrinsicID()) { case Intrinsic::experimental_gc_get_pointer_base: { Changed = true; - Value *Base = findBasePointer(Callsite->getOperand(0), DVCache); + Value *Base = + findBasePointer(Callsite->getOperand(0), DVCache, KnownBases); assert(!DVCache.count(Callsite)); auto *BaseBC = IRBuilder<>(Callsite).CreateBitCast( Base, Callsite->getType(), suffixed_name_or(Base, ".cast", "")); @@ -2454,7 +2470,7 @@ case Intrinsic::experimental_gc_get_pointer_offset: { Changed = true; Value *Derived = Callsite->getOperand(0); - Value *Base = findBasePointer(Derived, DVCache); + Value *Base = findBasePointer(Derived, DVCache, KnownBases); assert(!DVCache.count(Callsite)); unsigned AddressSpace = Derived->getType()->getPointerAddressSpace(); unsigned IntPtrSize = DL.getPointerSizeInBits(AddressSpace); @@ -2481,7 +2497,8 @@ static bool insertParsePoints(Function &F, DominatorTree &DT, TargetTransformInfo &TTI, SmallVectorImpl &ToUpdate, - DefiningValueMapTy &DVCache) { + DefiningValueMapTy &DVCache, + IsKnownBaseMapTy &KnownBases) { #ifndef NDEBUG // Validate the input std::set Uniqued; @@ -2537,7 +2554,7 @@ // 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, PointerToBase); + findBasePointers(DT, DVCache, ToUpdate[i], info, PointerToBase, KnownBases); } if (PrintBasePointers) { errs() << "Base Pairs (w/o Relocation):\n"; @@ -2985,13 +3002,18 @@ // inlineGetBaseAndOffset() and insertParsePoints(). DefiningValueMapTy DVCache; + // Mapping between a base values and a flag indicating whether it's a known + // base or not. + IsKnownBaseMapTy KnownBases; + if (!Intrinsics.empty()) // Inline @gc.get.pointer.base() and @gc.get.pointer.offset() before finding // live references. - MadeChange |= inlineGetBaseAndOffset(F, Intrinsics, DVCache); + MadeChange |= inlineGetBaseAndOffset(F, Intrinsics, DVCache, KnownBases); if (!ParsePointNeeded.empty()) - MadeChange |= insertParsePoints(F, DT, TTI, ParsePointNeeded, DVCache); + MadeChange |= + insertParsePoints(F, DT, TTI, ParsePointNeeded, DVCache, KnownBases); return MadeChange; }