diff --git a/llvm/include/llvm/Transforms/IPO/Attributor.h b/llvm/include/llvm/Transforms/IPO/Attributor.h --- a/llvm/include/llvm/Transforms/IPO/Attributor.h +++ b/llvm/include/llvm/Transforms/IPO/Attributor.h @@ -301,19 +301,6 @@ const DataLayout &DL, RangeTy *RangePtr = nullptr); -/// Collect all potential underlying objects of \p Ptr at position \p CtxI in -/// \p Objects. Assumed information is used and dependences onto \p QueryingAA -/// are added appropriately. -/// -/// \returns True if \p Objects contains all assumed underlying objects, and -/// false if something went wrong and the objects could not be -/// determined. -bool getAssumedUnderlyingObjects( - Attributor &A, const Value &Ptr, SmallSetVector &Objects, - const AbstractAttribute &QueryingAA, const Instruction *CtxI, - bool &UsedAssumedInformation, AA::ValueScope VS = AA::Interprocedural, - SmallPtrSetImpl *SeenObjects = nullptr); - /// Collect all potential values \p LI could read into \p PotentialValues. That /// is, the only values read by \p LI are assumed to be known and all are in /// \p PotentialValues. \p PotentialValueOrigins will contain all the @@ -5445,6 +5432,37 @@ static const char ID; }; +/// An abstract attribute for getting all assumption underlying objects. +struct AAUnderlyingObjects : AbstractAttribute { + AAUnderlyingObjects(const IRPosition &IRP) : AbstractAttribute(IRP) {} + + /// Create an abstract attribute biew for the position \p IRP. + static AAUnderlyingObjects &createForPosition(const IRPosition &IRP, + Attributor &A); + + /// See AbstractAttribute::getName() + const std::string getName() const override { return "AAUnderlyingObjects"; } + + /// See AbstractAttribute::getIdAddr() + const char *getIdAddr() const override { return &ID; } + + /// This function should return true if the type of the \p AA is + /// AAUnderlyingObjects. + static bool classof(const AbstractAttribute *AA) { + return (AA->getIdAddr() == &ID); + } + + /// Unique ID (due to the unique address) + static const char ID; + + /// Check \p Pred on all underlying objects collected so far. + /// + /// This method will evaluate \p Pred on all underlying objects collected so + /// far and return true if \p Pred holds on all of them. + virtual bool + forallUnderlyingObjects(function_ref Pred) const = 0; +}; + raw_ostream &operator<<(raw_ostream &, const AAPointerInfo::Access &); /// Run options, used by the pass manager. diff --git a/llvm/lib/Transforms/IPO/Attributor.cpp b/llvm/lib/Transforms/IPO/Attributor.cpp --- a/llvm/lib/Transforms/IPO/Attributor.cpp +++ b/llvm/lib/Transforms/IPO/Attributor.cpp @@ -340,9 +340,9 @@ << " (only exact: " << OnlyExact << ")\n";); Value &Ptr = *I.getPointerOperand(); - SmallSetVector Objects; - if (!AA::getAssumedUnderlyingObjects(A, Ptr, Objects, QueryingAA, &I, - UsedAssumedInformation)) { + const auto &AA = A.getAAFor( + QueryingAA, IRPosition::value(Ptr), DepClassTy::REQUIRED); + if (!AA.getState().isValidState()) { LLVM_DEBUG( dbgs() << "Underlying objects stored into could not be determined\n";); return false; @@ -357,11 +357,12 @@ const auto *TLI = A.getInfoCache().getTargetLibraryInfoForFunction(*I.getFunction()); - LLVM_DEBUG(dbgs() << "Visit " << Objects.size() << " objects:\n"); - for (Value *Obj : Objects) { + + auto Pred = [&](Value &V) { + Value *Obj = &V; LLVM_DEBUG(dbgs() << "Visit underlying object " << *Obj << "\n"); if (isa(Obj)) - continue; + return true; if (isa(Obj)) { // A null pointer access can be undefined but any offset from null may // be OK. We do not try to optimize the latter. @@ -369,7 +370,7 @@ Ptr.getType()->getPointerAddressSpace()) && A.getAssumedSimplified(Ptr, QueryingAA, UsedAssumedInformation, AA::Interprocedural) == Obj) - continue; + return true; LLVM_DEBUG( dbgs() << "Underlying object is a valid nullptr, giving up.\n";); return false; @@ -489,7 +490,12 @@ } PIs.push_back(&PI); - } + + return true; + }; + + if (!AA.forallUnderlyingObjects(Pred)) + return false; // Only if we were successful collection all potential copies we record // dependences (on non-fix AAPointerInfo AAs). We also only then modify the diff --git a/llvm/lib/Transforms/IPO/AttributorAttributes.cpp b/llvm/lib/Transforms/IPO/AttributorAttributes.cpp --- a/llvm/lib/Transforms/IPO/AttributorAttributes.cpp +++ b/llvm/lib/Transforms/IPO/AttributorAttributes.cpp @@ -185,6 +185,7 @@ PIPE_OPERATOR(AAFunctionReachability) PIPE_OPERATOR(AAPointerInfo) PIPE_OPERATOR(AAAssumptionInfo) +PIPE_OPERATOR(AAUnderlyingObjects) #undef PIPE_OPERATOR @@ -311,38 +312,6 @@ return Ptr; } -bool AA::getAssumedUnderlyingObjects(Attributor &A, const Value &Ptr, - SmallSetVector &Objects, - const AbstractAttribute &QueryingAA, - const Instruction *CtxI, - bool &UsedAssumedInformation, - AA::ValueScope S, - SmallPtrSetImpl *SeenObjects) { - SmallPtrSet LocalSeenObjects; - if (!SeenObjects) - SeenObjects = &LocalSeenObjects; - - SmallVector Values; - if (!A.getAssumedSimplifiedValues(IRPosition::value(Ptr), &QueryingAA, Values, - S, UsedAssumedInformation)) { - Objects.insert(const_cast(&Ptr)); - return true; - } - - for (auto &VAC : Values) { - Value *UO = getUnderlyingObject(VAC.getValue()); - if (UO && UO != VAC.getValue() && SeenObjects->insert(UO).second) { - if (!getAssumedUnderlyingObjects(A, *UO, Objects, QueryingAA, - VAC.getCtxI(), UsedAssumedInformation, S, - SeenObjects)) - return false; - continue; - } - Objects.insert(VAC.getValue()); - } - return true; -} - static const Value * stripAndAccumulateOffsets(Attributor &A, const AbstractAttribute &QueryingAA, const Value *Val, const DataLayout &DL, APInt &Offset, @@ -8193,23 +8162,12 @@ << Ptr << " [" << getMemoryLocationsAsStr(State.getAssumed()) << "]\n"); - SmallSetVector Objects; - bool UsedAssumedInformation = false; - if (!AA::getAssumedUnderlyingObjects(A, Ptr, Objects, *this, &I, - UsedAssumedInformation, - AA::Intraprocedural)) { - LLVM_DEBUG( - dbgs() << "[AAMemoryLocation] Pointer locations not categorized\n"); - updateStateAndAccessesMap(State, NO_UNKOWN_MEM, &I, nullptr, Changed, - getAccessKindFromInst(&I)); - return; - } - - for (Value *Obj : Objects) { + auto Pred = [&](Value &V) { + Value *Obj = &V; // TODO: recognize the TBAA used for constant accesses. MemoryLocationsKind MLK = NO_LOCATIONS; if (isa(Obj)) - continue; + return true; if (isa(Obj)) { // TODO: For now we do not treat byval arguments as local copies performed // on the call edge, though, we should. To make that happen we need to @@ -8224,7 +8182,7 @@ // similar. (We know we do not write it because it is constant.) if (auto *GVar = dyn_cast(GV)) if (GVar->isConstant()) - continue; + return true; if (GV->hasLocalLinkage()) MLK = NO_GLOBAL_INTERNAL_MEM; @@ -8233,7 +8191,7 @@ } else if (isa(Obj) && !NullPointerIsDefined(getAssociatedFunction(), Ptr.getType()->getPointerAddressSpace())) { - continue; + return true; } else if (isa(Obj)) { MLK = NO_LOCAL_MEM; } else if (const auto *CB = dyn_cast(Obj)) { @@ -8253,6 +8211,18 @@ << "\n"); updateStateAndAccessesMap(getState(), MLK, &I, Obj, Changed, getAccessKindFromInst(&I)); + + return true; + }; + + const auto &AA = A.getAAFor( + *this, IRPosition::value(Ptr), DepClassTy::REQUIRED); + if (!AA.forallUnderlyingObjects(Pred)) { + LLVM_DEBUG( + dbgs() << "[AAMemoryLocation] Pointer locations not categorized\n"); + updateStateAndAccessesMap(State, NO_UNKOWN_MEM, &I, nullptr, Changed, + getAccessKindFromInst(&I)); + return; } LLVM_DEBUG( @@ -11231,6 +11201,146 @@ void AttributorCallGraph::print() { llvm::WriteGraph(outs(), this); } +/// ------------------------ UnderlyingObjects --------------------------------- + +namespace { +struct AAUnderlyingObjectsImpl + : StateWrapper { + using BaseTy = StateWrapper; + AAUnderlyingObjectsImpl(const IRPosition &IRP, Attributor &A) : BaseTy(IRP) {} + + /// See AbstractAttribute::getAsStr(). + const std::string getAsStr() const override { + return std::string("UnderlyingObjects ") + + (isValidState() + ? (std::string("#") + + std::to_string(AssumedUnderlyingObjects.size()) + " objs") + : ""); + } + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override {} + + /// See AbstractAttribute::updateImpl(...). + ChangeStatus updateImpl(Attributor &A) override { + auto &Ptr = getAssociatedValue(); + + bool UsedAssumedInformation; + SmallPtrSet SeenObjects; + SmallSetVector Objects; + SmallVector Values; + + if (!A.getAssumedSimplifiedValues(IRPosition::value(Ptr), *this, Values, + AA::ValueScope::Intraprocedural, + UsedAssumedInformation)) + return AssumedUnderlyingObjects.insert(const_cast(&Ptr)) + ? ChangeStatus::CHANGED + : ChangeStatus::UNCHANGED; + + bool Changed = false; + + for (auto &VAC : Values) { + Value *UO = getUnderlyingObject(VAC.getValue()); + if (UO && UO != VAC.getValue() && SeenObjects.insert(UO).second) { + const auto &OtherAA = A.getAAFor( + *this, IRPosition::value(*UO), DepClassTy::REQUIRED); + + auto Pred = [&](Value &V) { + Objects.insert(&V); + return true; + }; + + if (!OtherAA.forallUnderlyingObjects(Pred)) + return indicatePessimisticFixpoint(); + + continue; + } + + Objects.insert(VAC.getValue()); + } + + for (auto *Obj : Objects) { + if (isa(Obj) || isa(Obj)) { + Changed |= handleIndirect(A, *Obj); + continue; + } + + Changed |= AssumedUnderlyingObjects.insert(Obj); + } + + return Changed ? ChangeStatus::CHANGED : ChangeStatus::UNCHANGED; + } + + bool + forallUnderlyingObjects(function_ref Pred) const override { + if (!isValidState()) + return false; + + for (Value *Obj : AssumedUnderlyingObjects) + if (!Pred(*Obj)) + return false; + + return true; + } + +private: + /// Handle the case where the value is not the actual underlying value, such + /// as a phi node or a select instruction. + bool handleIndirect(Attributor &A, Value &V) { + const auto &AA = A.getAAFor( + *this, IRPosition::value(V), DepClassTy::REQUIRED); + + bool Changed = false; + auto Pred = [&](Value &V) { + Changed |= AssumedUnderlyingObjects.insert(&V); + return true; + }; + + if (!AA.forallUnderlyingObjects(Pred)) + indicatePessimisticFixpoint(); + + return Changed; + } + + SmallSetVector AssumedUnderlyingObjects; +}; + +struct AAUnderlyingObjectsFloating final : AAUnderlyingObjectsImpl { + AAUnderlyingObjectsFloating(const IRPosition &IRP, Attributor &A) + : AAUnderlyingObjectsImpl(IRP, A) {} +}; + +struct AAUnderlyingObjectsArgument final : AAUnderlyingObjectsImpl { + AAUnderlyingObjectsArgument(const IRPosition &IRP, Attributor &A) + : AAUnderlyingObjectsImpl(IRP, A) {} +}; + +struct AAUnderlyingObjectsCallSite final : AAUnderlyingObjectsImpl { + AAUnderlyingObjectsCallSite(const IRPosition &IRP, Attributor &A) + : AAUnderlyingObjectsImpl(IRP, A) {} +}; + +struct AAUnderlyingObjectsCallSiteArgument final : AAUnderlyingObjectsImpl { + AAUnderlyingObjectsCallSiteArgument(const IRPosition &IRP, Attributor &A) + : AAUnderlyingObjectsImpl(IRP, A) {} +}; + +struct AAUnderlyingObjectsReturned final : AAUnderlyingObjectsImpl { + AAUnderlyingObjectsReturned(const IRPosition &IRP, Attributor &A) + : AAUnderlyingObjectsImpl(IRP, A) {} +}; + +struct AAUnderlyingObjectsCallSiteReturned final : AAUnderlyingObjectsImpl { + AAUnderlyingObjectsCallSiteReturned(const IRPosition &IRP, Attributor &A) + : AAUnderlyingObjectsImpl(IRP, A) {} +}; + +struct AAUnderlyingObjectsFunction final : AAUnderlyingObjectsImpl { + AAUnderlyingObjectsFunction(const IRPosition &IRP, Attributor &A) + : AAUnderlyingObjectsImpl(IRP, A) {} +}; +} + const char AAReturnedValues::ID = 0; const char AANoUnwind::ID = 0; const char AANoSync::ID = 0; @@ -11260,6 +11370,7 @@ const char AAFunctionReachability::ID = 0; const char AAPointerInfo::ID = 0; const char AAAssumptionInfo::ID = 0; +const char AAUnderlyingObjects::ID = 0; // Macro magic to create the static generator function for attributes that // follow the naming scheme. @@ -11380,6 +11491,7 @@ CREATE_ALL_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAValueSimplify) CREATE_ALL_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAIsDead) CREATE_ALL_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANoFree) +CREATE_ALL_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAUnderlyingObjects) CREATE_FUNCTION_ONLY_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAHeapToStack) CREATE_FUNCTION_ONLY_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAReachability)