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,38 @@ 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 in \p Scope collected so far. + /// + /// This method will evaluate \p Pred on all underlying objects in \p Scope + /// collected so far and return true if \p Pred holds on all of them. + virtual bool + forallUnderlyingObjects(function_ref Pred, + AA::ValueScope Scope = AA::Interprocedural) 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,14 +340,6 @@ << " (only exact: " << OnlyExact << ")\n";); Value &Ptr = *I.getPointerOperand(); - SmallSetVector Objects; - if (!AA::getAssumedUnderlyingObjects(A, Ptr, Objects, QueryingAA, &I, - UsedAssumedInformation)) { - LLVM_DEBUG( - dbgs() << "Underlying objects stored into could not be determined\n";); - return false; - } - // Containers to remember the pointer infos and new copies while we are not // sure that we can find all of them. If we abort we want to avoid spurious // dependences and potential copies in the provided container. @@ -357,36 +349,36 @@ const auto *TLI = A.getInfoCache().getTargetLibraryInfoForFunction(*I.getFunction()); - LLVM_DEBUG(dbgs() << "Visit " << Objects.size() << " objects:\n"); - for (Value *Obj : Objects) { - LLVM_DEBUG(dbgs() << "Visit underlying object " << *Obj << "\n"); - if (isa(Obj)) - continue; - if (isa(Obj)) { + + auto Pred = [&](Value &Obj) { + LLVM_DEBUG(dbgs() << "Visit underlying object " << Obj << "\n"); + if (isa(&Obj)) + 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. if (!NullPointerIsDefined(I.getFunction(), Ptr.getType()->getPointerAddressSpace()) && A.getAssumedSimplified(Ptr, QueryingAA, UsedAssumedInformation, - AA::Interprocedural) == Obj) - continue; + AA::Interprocedural) == &Obj) + return true; LLVM_DEBUG( dbgs() << "Underlying object is a valid nullptr, giving up.\n";); return false; } // TODO: Use assumed noalias return. - if (!isa(Obj) && !isa(Obj) && - !(IsLoad ? isAllocationFn(Obj, TLI) : isNoAliasCall(Obj))) { - LLVM_DEBUG(dbgs() << "Underlying object is not supported yet: " << *Obj + if (!isa(&Obj) && !isa(&Obj) && + !(IsLoad ? isAllocationFn(&Obj, TLI) : isNoAliasCall(&Obj))) { + LLVM_DEBUG(dbgs() << "Underlying object is not supported yet: " << Obj << "\n";); return false; } - if (auto *GV = dyn_cast(Obj)) + if (auto *GV = dyn_cast(&Obj)) if (!GV->hasLocalLinkage() && !(GV->isConstant() && GV->hasInitializer())) { LLVM_DEBUG(dbgs() << "Underlying object is global with external " "linkage, not supported yet: " - << *Obj << "\n";); + << Obj << "\n";); return false; } @@ -457,21 +449,21 @@ bool HasBeenWrittenTo = false; AA::RangeTy Range; - auto &PI = A.getAAFor(QueryingAA, IRPosition::value(*Obj), + auto &PI = A.getAAFor(QueryingAA, IRPosition::value(Obj), DepClassTy::NONE); if (!PI.forallInterferingAccesses(A, QueryingAA, I, CheckAccess, HasBeenWrittenTo, Range)) { LLVM_DEBUG( dbgs() << "Failed to verify all interfering accesses for underlying object: " - << *Obj << "\n"); + << Obj << "\n"); return false; } if (IsLoad && !HasBeenWrittenTo && !Range.isUnassigned()) { const DataLayout &DL = A.getDataLayout(); Value *InitialValue = - AA::getInitialValueForObj(*Obj, *I.getType(), TLI, DL, &Range); + AA::getInitialValueForObj(Obj, *I.getType(), TLI, DL, &Range); if (!InitialValue) { LLVM_DEBUG(dbgs() << "Could not determine required initial value of " "underlying object, abort!\n"); @@ -489,6 +481,16 @@ } PIs.push_back(&PI); + + return true; + }; + + const auto &AAUO = A.getAAFor( + QueryingAA, IRPosition::value(Ptr), DepClassTy::OPTIONAL); + if (!AAUO.forallUnderlyingObjects(Pred)) { + LLVM_DEBUG( + dbgs() << "Underlying objects stored into could not be determined\n";); + return false; } // Only if we were successful collection all potential copies we record 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,24 +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 &Obj) { // TODO: recognize the TBAA used for constant accesses. MemoryLocationsKind MLK = NO_LOCATIONS; - if (isa(Obj)) - continue; - if (isa(Obj)) { + if (isa(&Obj)) + 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 // teach various passes, e.g., DSE, about the copy effect of a byval. That @@ -8218,25 +8175,25 @@ // readnone again, arguably their accesses have no effect outside of the // function, like accesses to allocas. MLK = NO_ARGUMENT_MEM; - } else if (auto *GV = dyn_cast(Obj)) { + } else if (auto *GV = dyn_cast(&Obj)) { // Reading constant memory is not treated as a read "effect" by the // function attr pass so we won't neither. Constants defined by TBAA are // 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; else MLK = NO_GLOBAL_EXTERNAL_MEM; - } else if (isa(Obj) && + } else if (isa(&Obj) && !NullPointerIsDefined(getAssociatedFunction(), Ptr.getType()->getPointerAddressSpace())) { - continue; - } else if (isa(Obj)) { + return true; + } else if (isa(&Obj)) { MLK = NO_LOCAL_MEM; - } else if (const auto *CB = dyn_cast(Obj)) { + } else if (const auto *CB = dyn_cast(&Obj)) { const auto &NoAliasAA = A.getAAFor( *this, IRPosition::callsite_returned(*CB), DepClassTy::OPTIONAL); if (NoAliasAA.isAssumedNoAlias()) @@ -8249,10 +8206,21 @@ assert(MLK != NO_LOCATIONS && "No location specified!"); LLVM_DEBUG(dbgs() << "[AAMemoryLocation] Ptr value can be categorized: " - << *Obj << " -> " << getMemoryLocationsAsStr(MLK) - << "\n"); - updateStateAndAccessesMap(getState(), MLK, &I, Obj, Changed, + << Obj << " -> " << getMemoryLocationsAsStr(MLK) << "\n"); + updateStateAndAccessesMap(getState(), MLK, &I, &Obj, Changed, + getAccessKindFromInst(&I)); + + return true; + }; + + const auto &AA = A.getAAFor( + *this, IRPosition::value(Ptr), DepClassTy::OPTIONAL); + if (!AA.forallUnderlyingObjects(Pred, AA::Intraprocedural)) { + LLVM_DEBUG( + dbgs() << "[AAMemoryLocation] Pointer locations not categorized\n"); + updateStateAndAccessesMap(State, NO_UNKOWN_MEM, &I, nullptr, Changed, getAccessKindFromInst(&I)); + return; } LLVM_DEBUG( @@ -11231,6 +11199,164 @@ 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("inter #") + + std::to_string(InterAssumedUnderlyingObjects.size()) + + " objs" + std::string(", intra #") + + std::to_string(IntraAssumedUnderlyingObjects.size()) + + " objs") + : ""); + } + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override {} + + /// See AbstractAttribute::updateImpl(...). + ChangeStatus updateImpl(Attributor &A) override { + auto &Ptr = getAssociatedValue(); + + auto DoUpdate = [&](SmallSetVector &UnderlyingObjects, + AA::ValueScope Scope) { + bool UsedAssumedInformation; + SmallPtrSet SeenObjects; + SmallSetVector Objects; + SmallVector Values; + + if (!A.getAssumedSimplifiedValues(IRPosition::value(Ptr), *this, Values, + Scope, UsedAssumedInformation)) + return UnderlyingObjects.insert(const_cast(&Ptr)); + + bool Changed = false; + + for (unsigned I = 0; I < Values.size(); ++I) { + auto &VAC = Values[I]; + 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) { + Values.emplace_back(V, nullptr); + return true; + }; + + if (!OtherAA.forallUnderlyingObjects(Pred)) + Changed |= Objects.insert(UO); + + continue; + } + + Objects.insert(VAC.getValue()); + } + + for (auto *Obj : Objects) { + if (isa(Obj) || isa(Obj)) { + Changed |= handleIndirect(A, *Obj, UnderlyingObjects, Scope); + continue; + } + + Changed |= UnderlyingObjects.insert(Obj); + } + + return Changed; + }; + + bool Changed = false; + Changed |= DoUpdate(IntraAssumedUnderlyingObjects, AA::Intraprocedural); + Changed |= DoUpdate(InterAssumedUnderlyingObjects, AA::Interprocedural); + + return Changed ? ChangeStatus::CHANGED : ChangeStatus::UNCHANGED; + } + + bool forallUnderlyingObjects(function_ref Pred, + AA::ValueScope Scope) const override { + if (!isValidState()) + return false; + + auto &AssumedUnderlyingObjects = Scope == AA::ValueScope::Interprocedural + ? InterAssumedUnderlyingObjects + : IntraAssumedUnderlyingObjects; + 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, + SmallSetVector &UnderlyingObjects, + AA::ValueScope Scope) { + const auto &AA = A.getAAFor( + *this, IRPosition::value(V), DepClassTy::OPTIONAL); + + bool Changed = false; + auto Pred = [&](Value &V) { + Changed |= UnderlyingObjects.insert(&V); + return true; + }; + + if (!AA.forallUnderlyingObjects(Pred, Scope)) + indicatePessimisticFixpoint(); + + return Changed; + } + + /// All the underlying objects collected so far via intra procedural scope. + SmallSetVector IntraAssumedUnderlyingObjects; + /// All the underlying objects collected so far via inter procedural scope. + SmallSetVector InterAssumedUnderlyingObjects; +}; + +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 +11386,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 +11507,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)