From 14a0493a88e8314b03d7d32bb995a675f6499e33 Mon Sep 17 00:00:00 2001 From: Johannes Doerfert Date: Wed, 7 Aug 2019 22:27:24 +0000 Subject: [PATCH] [Attributor] Provide easier checkForallReturnedValues functionality Summary: So far, whenever one wants to look at returned values, one had to deal with the AAReturnedValues and potentially with the AAIsDead attribute. In the same spirit as other checkForAllXXX methods, we add this functionality now to the Attributor. By adopting the use sites we got better results when return instructions were dead. Reviewers: sstefan1, uenoku Subscribers: hiraditya, bollu, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D65733 llvm-svn: 368222 --- llvm/include/llvm/Transforms/IPO/Attributor.h | 46 ++++-- llvm/lib/Transforms/IPO/Attributor.cpp | 144 +++++++++++------- .../Transforms/FunctionAttrs/arg_nocapture.ll | 2 +- .../Transforms/FunctionAttrs/arg_returned.ll | 4 +- 4 files changed, 122 insertions(+), 74 deletions(-) diff --git a/llvm/include/llvm/Transforms/IPO/Attributor.h b/llvm/include/llvm/Transforms/IPO/Attributor.h index b41d9e4aeca4..78c74e0a5e75 100644 --- a/llvm/include/llvm/Transforms/IPO/Attributor.h +++ b/llvm/include/llvm/Transforms/IPO/Attributor.h @@ -170,7 +170,7 @@ struct Attributor { /// the one reasoning about the "captured" state for the argument or the one /// reasoning on the memory access behavior of the function as a whole. template - const AAType *getAAFor(AbstractAttribute &QueryingAA, const Value &V, + const AAType *getAAFor(const AbstractAttribute &QueryingAA, const Value &V, int ArgNo = -1) { static_assert(std::is_base_of::value, "Cannot query an attribute with a type not derived from " @@ -199,7 +199,7 @@ struct Attributor { // Do not return an attribute with an invalid state. This minimizes checks // at the calls sites and allows the fallback below to kick in. if (AA->getState().isValidState()) { - QueryMap[AA].insert(&QueryingAA); + QueryMap[AA].insert(const_cast(&QueryingAA)); return AA; } } @@ -266,24 +266,43 @@ struct Attributor { /// true if \p Pred holds in every call sites. However, this is only possible /// all call sites are known, hence the function has internal linkage. bool checkForAllCallSites(Function &F, std::function &Pred, - AbstractAttribute &QueryingAA, + const AbstractAttribute &QueryingAA, bool RequireAllCallSites); + /// Check \p Pred on all values potentially returned by \p F. + /// + /// This method will evaluate \p Pred on all values potentially returned by + /// \p F associated to their respective return instructions. Return true if + /// \p Pred holds on all of them. + bool checkForAllReturnedValuesAndReturnInsts( + const Function &F, + const function_ref &)> + &Pred, + const AbstractAttribute &QueryingAA); + + /// Check \p Pred on all values potentially returned by \p F. + /// + /// This is the context insensitive version of the method above. + bool checkForAllReturnedValues(const Function &F, + const function_ref &Pred, + const AbstractAttribute &QueryingAA); + /// Check \p Pred on all instructions with an opcode present in \p Opcodes. /// /// This method will evaluate \p Pred on all instructions with an opcode /// present in \p Opcode and return true if \p Pred holds on all of them. - bool checkForAllInstructions( - const Function &F, const llvm::function_ref &Pred, - AbstractAttribute &QueryingAA, InformationCache &InfoCache, - const ArrayRef &Opcodes); + bool checkForAllInstructions(const Function &F, + const function_ref &Pred, + const AbstractAttribute &QueryingAA, + InformationCache &InfoCache, + const ArrayRef &Opcodes); /// Check \p Pred on all call-like instructions (=CallBased derived). /// /// See checkForAllCallLikeInstructions(...) for more information. bool checkForAllCallLikeInstructions( - const Function &F, const llvm::function_ref &Pred, - AbstractAttribute &QueryingAA, InformationCache &InfoCache) { + const Function &F, const function_ref &Pred, + const AbstractAttribute &QueryingAA, InformationCache &InfoCache) { return checkForAllInstructions(F, Pred, QueryingAA, InfoCache, {(unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr, @@ -845,9 +864,12 @@ struct AAReturnedValues /// This method will evaluate \p Pred on returned values and return /// true if (1) all returned values are known, and (2) \p Pred returned true /// for all returned values. - virtual bool checkForallReturnedValues( - std::function &)> &Pred) - const = 0; + /// + /// Note: Unlike the Attributor::checkForAllReturnedValuesAndReturnInsts + /// method, this one will not filter dead return instructions. + virtual bool checkForAllReturnedValuesAndReturnInsts( + const function_ref &)> + &Pred) const = 0; /// Unique ID (due to the unique address) static const char ID; diff --git a/llvm/lib/Transforms/IPO/Attributor.cpp b/llvm/lib/Transforms/IPO/Attributor.cpp index d25d532d3ef6..46dd8b447ec0 100644 --- a/llvm/lib/Transforms/IPO/Attributor.cpp +++ b/llvm/lib/Transforms/IPO/Attributor.cpp @@ -444,6 +444,9 @@ ChangeStatus AANoUnwindImpl::updateImpl(Attributor &A, /// /// If there is a unique returned value R, the manifest method will: /// - mark R with the "returned" attribute, if R is an argument. +/// +/// TODO: We should use liveness during construction of the returned values map +/// and before we set HasOverdefinedReturnedCalls. class AAReturnedValuesImpl : public AAReturnedValues, public AbstractState { /// Mapping of values potentially returned by the associated function to the @@ -539,13 +542,12 @@ public: /// Return an assumed unique return value if a single candidate is found. If /// there cannot be one, return a nullptr. If it is not clear yet, return the /// Optional::NoneType. - Optional - getAssumedUniqueReturnValue(const AAIsDead *LivenessAA) const; + Optional getAssumedUniqueReturnValue(Attributor &A) const; - /// See AbstractState::checkForallReturnedValues(...). - bool checkForallReturnedValues( - std::function &)> &Pred) - const override; + /// See AbstractState::checkForAllReturnedValues(...). + bool checkForAllReturnedValuesAndReturnInsts( + const function_ref &)> + &Pred) const override; /// Pretty print the attribute similar to the IR representation. const std::string getAsStr() const override; @@ -582,10 +584,8 @@ ChangeStatus AAReturnedValuesImpl::manifest(Attributor &A) { assert(isValidState()); NumFnKnownReturns++; - auto *LivenessAA = A.getAAFor(*this, getAnchorScope()); - // Check if we have an assumed unique return value that we could manifest. - Optional UniqueRV = getAssumedUniqueReturnValue(LivenessAA); + Optional UniqueRV = getAssumedUniqueReturnValue(A); if (!UniqueRV.hasValue() || !UniqueRV.getValue()) return Changed; @@ -609,23 +609,16 @@ const std::string AAReturnedValuesImpl::getAsStr() const { ")[OD: " + std::to_string(HasOverdefinedReturnedCalls) + "]"; } -Optional AAReturnedValuesImpl::getAssumedUniqueReturnValue( - const AAIsDead *LivenessAA) const { - // If checkForallReturnedValues provides a unique value, ignoring potential +Optional +AAReturnedValuesImpl::getAssumedUniqueReturnValue(Attributor &A) const { + // If checkForAllReturnedValues provides a unique value, ignoring potential // undef values that can also be present, it is assumed to be the actual // return value and forwarded to the caller of this method. If there are // multiple, a nullptr is returned indicating there cannot be a unique // returned value. Optional UniqueRV; - std::function &)> Pred = - [&](Value &RV, const SmallPtrSetImpl &RetInsts) -> bool { - // If all ReturnInsts are dead, then ReturnValue is dead as well - // and can be ignored. - if (LivenessAA && - !LivenessAA->isLiveInstSet(RetInsts.begin(), RetInsts.end())) - return true; - + auto Pred = [&](Value &RV) -> bool { // If we found a second returned value and neither the current nor the saved // one is an undef, there is no unique returned value. Undefs are special // since we can pretend they have any value. @@ -642,15 +635,15 @@ Optional AAReturnedValuesImpl::getAssumedUniqueReturnValue( return true; }; - if (!checkForallReturnedValues(Pred)) + if (!A.checkForAllReturnedValues(getAnchorScope(), Pred, *this)) UniqueRV = nullptr; return UniqueRV; } -bool AAReturnedValuesImpl::checkForallReturnedValues( - std::function &)> &Pred) - const { +bool AAReturnedValuesImpl::checkForAllReturnedValuesAndReturnInsts( + const function_ref &)> + &Pred) const { if (!isValidState()) return false; @@ -728,11 +721,8 @@ ChangeStatus AAReturnedValuesImpl::updateImpl(Attributor &A, continue; } - auto *LivenessCSAA = A.getAAFor(*this, RetCSAA->getAnchorScope()); - // Try to find a assumed unique return value for the called function. - Optional AssumedUniqueRV = - RetCSAA->getAssumedUniqueReturnValue(LivenessCSAA); + Optional AssumedUniqueRV = RetCSAA->getAssumedUniqueReturnValue(A); // If no assumed unique return value was found due to the lack of // candidates, we may need to resolve more calls (through more update @@ -1101,14 +1091,10 @@ ChangeStatus AANonNullReturned::updateImpl(Attributor &A, InformationCache &InfoCache) { Function &F = getAnchorScope(); - auto *AARetVal = A.getAAFor(*this, F); - if (!AARetVal) - return indicatePessimisticFixpoint(); - std::function &)> Pred = this->generatePredicate(A); - if (!AARetVal->checkForallReturnedValues(Pred)) + if (!A.checkForAllReturnedValuesAndReturnInsts(F, Pred, *this)) return indicatePessimisticFixpoint(); return ChangeStatus::UNCHANGED; } @@ -1342,12 +1328,7 @@ ChangeStatus AANoAliasReturned::updateImpl(Attributor &A, InformationCache &InfoCache) { Function &F = getAnchorScope(); - auto *AARetValImpl = A.getAAFor(*this, F); - if (!AARetValImpl) - return indicatePessimisticFixpoint(); - - std::function &)> Pred = - [&](Value &RV, const SmallPtrSetImpl &RetInsts) -> bool { + auto CheckReturnValue = [&](Value &RV) -> bool { if (Constant *C = dyn_cast(&RV)) if (C->isNullValue() || isa(C)) return true; @@ -1358,11 +1339,11 @@ ChangeStatus AANoAliasReturned::updateImpl(Attributor &A, if (!ICS) return false; - auto *NoAliasAA = A.getAAFor(*this, RV); - - if (!ICS.returnDoesNotAlias() && - (!NoAliasAA || !NoAliasAA->isAssumedNoAlias())) - return false; + if (!ICS.returnDoesNotAlias()) { + auto *NoAliasAA = A.getAAFor(*this, RV); + if (!NoAliasAA || !NoAliasAA->isAssumedNoAlias()) + return false; + } /// FIXME: We can improve capture check in two ways: /// 1. Use the AANoCapture facilities. @@ -1374,7 +1355,7 @@ ChangeStatus AANoAliasReturned::updateImpl(Attributor &A, return true; }; - if (!AARetValImpl->checkForallReturnedValues(Pred)) + if (!A.checkForAllReturnedValues(F, CheckReturnValue, *this)) return indicatePessimisticFixpoint(); return ChangeStatus::UNCHANGED; @@ -1853,21 +1834,16 @@ AADereferenceableReturned::updateImpl(Attributor &A, syncNonNull(A.getAAFor(*this, F)); - auto *AARetVal = A.getAAFor(*this, F); - if (!AARetVal) - return indicatePessimisticFixpoint(); - bool IsNonNull = isAssumedNonNull(); bool IsGlobal = isAssumedGlobal(); - std::function &)> Pred = - [&](Value &RV, const SmallPtrSetImpl &RetInsts) -> bool { + auto CheckReturnValue = [&](Value &RV) -> bool { takeAssumedDerefBytesMinimum( computeAssumedDerefenceableBytes(A, RV, IsNonNull, IsGlobal)); return isValidState(); }; - if (AARetVal->checkForallReturnedValues(Pred)) { + if (A.checkForAllReturnedValues(F, CheckReturnValue, *this)) { updateAssumedNonNullGlobalState(IsNonNull, IsGlobal); return BeforeState == static_cast(*this) ? ChangeStatus::UNCHANGED @@ -2035,9 +2011,6 @@ struct AAAlignReturned final : AAAlignImpl { ChangeStatus AAAlignReturned::updateImpl(Attributor &A, InformationCache &InfoCache) { Function &F = getAnchorScope(); - auto *AARetValImpl = A.getAAFor(*this, F); - if (!AARetValImpl) - return indicatePessimisticFixpoint(); // Currently, align is deduced if alignments in return values are assumed // as greater than n. We reach pessimistic fixpoint if any of the return value @@ -2045,7 +2018,7 @@ ChangeStatus AAAlignReturned::updateImpl(Attributor &A, // optimistic fixpoint is reached earlier. base_t BeforeState = getAssumed(); - std::function &)> Pred = + auto CheckReturnValue = [&](Value &RV, const SmallPtrSetImpl &RetInsts) -> bool { auto *AlignAA = A.getAAFor(*this, RV); @@ -2059,7 +2032,7 @@ ChangeStatus AAAlignReturned::updateImpl(Attributor &A, return isValidState(); }; - if (!AARetValImpl->checkForallReturnedValues(Pred)) + if (!A.checkForAllReturnedValuesAndReturnInsts(F, CheckReturnValue, *this)) return indicatePessimisticFixpoint(); return (getAssumed() != BeforeState) ? ChangeStatus::CHANGED @@ -2201,7 +2174,7 @@ struct AANoReturnFunction final : AANoReturnImpl { bool Attributor::checkForAllCallSites(Function &F, std::function &Pred, - AbstractAttribute &QueryingAA, + const AbstractAttribute &QueryingAA, bool RequireAllCallSites) { // We can try to determine information from // the call sites. However, this is only possible all call sites are known, @@ -2245,9 +2218,62 @@ bool Attributor::checkForAllCallSites(Function &F, return true; } +bool Attributor::checkForAllReturnedValuesAndReturnInsts( + const Function &F, + const function_ref &)> + &Pred, + const AbstractAttribute &QueryingAA) { + + auto *AARetVal = getAAFor(QueryingAA, F); + if (!AARetVal) + return false; + + auto *LivenessAA = getAAFor(QueryingAA, F); + if (!LivenessAA) + return AARetVal->checkForAllReturnedValuesAndReturnInsts(Pred); + + auto LivenessFilter = [&](Value &RV, + const SmallPtrSetImpl &ReturnInsts) { + SmallPtrSet FilteredReturnInsts; + for (ReturnInst *RI : ReturnInsts) + if (!LivenessAA->isAssumedDead(RI)) + FilteredReturnInsts.insert(RI); + if (!FilteredReturnInsts.empty()) + return Pred(RV, FilteredReturnInsts); + return true; + }; + + return AARetVal->checkForAllReturnedValuesAndReturnInsts(LivenessFilter); +} + +bool Attributor::checkForAllReturnedValues( + const Function &F, const function_ref &Pred, + const AbstractAttribute &QueryingAA) { + + auto *AARetVal = getAAFor(QueryingAA, F); + if (!AARetVal) + return false; + + auto *LivenessAA = getAAFor(QueryingAA, F); + if (!LivenessAA) + return AARetVal->checkForAllReturnedValuesAndReturnInsts( + [&](Value &RV, const SmallPtrSetImpl &) { + return Pred(RV); + }); + + auto LivenessFilter = [&](Value &RV, + const SmallPtrSetImpl &ReturnInsts) { + if (LivenessAA->isLiveInstSet(ReturnInsts.begin(), ReturnInsts.end())) + return Pred(RV); + return true; + }; + + return AARetVal->checkForAllReturnedValuesAndReturnInsts(LivenessFilter); +} + bool Attributor::checkForAllInstructions( const Function &F, const llvm::function_ref &Pred, - AbstractAttribute &QueryingAA, InformationCache &InfoCache, + const AbstractAttribute &QueryingAA, InformationCache &InfoCache, const ArrayRef &Opcodes) { auto *LivenessAA = getAAFor(QueryingAA, F); diff --git a/llvm/test/Transforms/FunctionAttrs/arg_nocapture.ll b/llvm/test/Transforms/FunctionAttrs/arg_nocapture.ll index 917d037ab3aa..7a20b1346af5 100644 --- a/llvm/test/Transforms/FunctionAttrs/arg_nocapture.ll +++ b/llvm/test/Transforms/FunctionAttrs/arg_nocapture.ll @@ -66,7 +66,7 @@ return: ; preds = %if.end3, %if.then2, ; return 0; ; } ; -; CHECK: define noalias double* @srec0(double* nocapture readnone %a) +; CHECK: define noalias nonnull align 536870912 dereferenceable(4294967295) double* @srec0(double* nocapture readnone %a) define double* @srec0(double* %a) #0 { entry: %call = call double* @srec0(double* %a) diff --git a/llvm/test/Transforms/FunctionAttrs/arg_returned.ll b/llvm/test/Transforms/FunctionAttrs/arg_returned.ll index 1cd01a7a3407..9e80b33cc610 100644 --- a/llvm/test/Transforms/FunctionAttrs/arg_returned.ll +++ b/llvm/test/Transforms/FunctionAttrs/arg_returned.ll @@ -261,7 +261,7 @@ return: ; preds = %cond.end, %if.then3 ; ; FNATTR: define i32* @rt0(i32* readonly %a) ; BOTH: Function Attrs: nofree noinline noreturn nosync nounwind readonly uwtable -; BOTH-NEXT: define i32* @rt0(i32* readonly %a) +; BOTH-NEXT: define noalias nonnull align 536870912 dereferenceable(4294967295) i32* @rt0(i32* readonly %a) define i32* @rt0(i32* %a) #0 { entry: %v = load i32, i32* %a, align 4 @@ -279,7 +279,7 @@ entry: ; ; FNATTR: define noalias i32* @rt1(i32* nocapture readonly %a) ; BOTH: Function Attrs: nofree noinline noreturn nosync nounwind readonly uwtable -; BOTH-NEXT: define noalias i32* @rt1(i32* nocapture readonly %a) +; BOTH-NEXT: define noalias nonnull align 536870912 dereferenceable(4294967295) i32* @rt1(i32* nocapture readonly %a) define i32* @rt1(i32* %a) #0 { entry: %v = load i32, i32* %a, align 4 -- 2.34.1