From 1b82a898f64457e3baba40e478d227328f0ce927 Mon Sep 17 00:00:00 2001 From: Johannes Doerfert Date: Fri, 16 Aug 2019 19:51:23 +0000 Subject: [PATCH] [Attributor] Towards a more structured deduction pattern Summary: This is the first commit aiming to structure the attribute deduction. The base idea is that we have default propagation patterns as listed below on top of which we can add specific, e.g., context sensitive, logic. Deduction patterns used in this patch: - argument states are determined from call site argument states, see AAAlignArgument and AAArgumentFromCallSiteArguments. - call site argument states are determined as if they were floating values, see AAAlignCallSiteArgument and AAAlignFloating. - floating value states are determined by traversing the def-use chain and combining the states determined for the leaves, see AAAlignFloating and genericValueTraversal. - call site return states are determined from function return states, see AAAlignCallSiteReturned and AACallSiteReturnedFromReturned. - function return states are determined from returned value states, see AAAlignReturned and AAReturnedFromReturnedValues. Through this strategy all logic for alignment is concentrated in the AAAlignFloating::updateImpl method. Note: This commit works on its own but is part of a larger change that involves "on-demand" creation of abstract attributes that will participate in the fixpoint iteration. Without this part, we sometimes do not have an AAAlign abstract attribute to query, loosing information we determined before. All tests have appropriate FIXMEs and the information will be recovered once we added all parts. Reviewers: sstefan1, uenoku Subscribers: hiraditya, bollu, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D66126 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@369144 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/IPO/Attributor.cpp | 333 ++++++++++++------ test/Transforms/FunctionAttrs/align.ll | 32 +- .../FunctionAttrs/noalias_returned.ll | 10 +- 3 files changed, 257 insertions(+), 118 deletions(-) diff --git a/lib/Transforms/IPO/Attributor.cpp b/lib/Transforms/IPO/Attributor.cpp index 5ba0f1b90b7..7ae990fbd60 100644 --- a/lib/Transforms/IPO/Attributor.cpp +++ b/lib/Transforms/IPO/Attributor.cpp @@ -452,6 +452,172 @@ void IRPosition::verify() { } } +/// Helper functions to clamp a state \p S of type \p StateType with the +/// information in \p R and indicate/return if \p S did change (as-in update is +/// required to be run again). +/// +///{ +template +ChangeStatus clampStateAndIndicateChange(StateType &S, const StateType &R); + +template <> +ChangeStatus clampStateAndIndicateChange(IntegerState &S, + const IntegerState &R) { + auto Assumed = S.getAssumed(); + S ^= R; + return Assumed == S.getAssumed() ? ChangeStatus::UNCHANGED + : ChangeStatus::CHANGED; +} +///} + +/// Clamp the information known for all returned values of a function +/// (identified by \p QueryingAA) into \p S. +template +static void clampReturnedValueStates(Attributor &A, const AAType &QueryingAA, + StateType &S) { + LLVM_DEBUG(dbgs() << "[Attributor] Clamp return value states for " + << static_cast(QueryingAA) + << " into " << S << "\n"); + + assert((QueryingAA.getIRPosition().getPositionKind() == + IRPosition::IRP_RETURNED || + QueryingAA.getIRPosition().getPositionKind() == + IRPosition::IRP_CALL_SITE_RETURNED) && + "Can only clamp returned value states for a function returned or call " + "site returned position!"); + + // Use an optional state as there might not be any return values and we want + // to join (IntegerState::operator&) the state of all there are. + Optional T; + + // Callback for each possibly returned value. + auto CheckReturnValue = [&](Value &RV) -> bool { + const IRPosition &RVPos = IRPosition::value(RV); + const AAType *AA = A.getAAFor(QueryingAA, RVPos); + LLVM_DEBUG(dbgs() << "[Attributor] RV: " << RV + << " AA: " << (AA ? AA->getAsStr() : "n/a") << " @ " + << RVPos << "\n"); + // TODO: We should create abstract attributes on-demand, patches are already + // prepared, pending approval. + if (!AA || AA->getIRPosition() != RVPos) + return false; + const StateType &AAS = static_cast(AA->getState()); + if (T.hasValue()) + *T &= AAS; + else + T = AAS; + LLVM_DEBUG(dbgs() << "[Attributor] AA State: " << AAS << " RV State: " << T + << "\n"); + return T->isValidState(); + }; + + if (!A.checkForAllReturnedValues(CheckReturnValue, QueryingAA)) + S.indicatePessimisticFixpoint(); + else if (T.hasValue()) + S ^= *T; +} + +/// Helper class for generic deduction: return value -> returned position. +template +struct AAReturnedFromReturnedValues : public AAType { + AAReturnedFromReturnedValues(const IRPosition &IRP) : AAType(IRP) {} + + /// See AbstractAttribute::updateImpl(...). + ChangeStatus updateImpl(Attributor &A) override { + StateType S; + clampReturnedValueStates(A, *this, S); + return clampStateAndIndicateChange(this->getState(), S); + } +}; + +/// Clamp the information known at all call sites for a given argument +/// (identified by \p QueryingAA) into \p S. +template +static void clampCallSiteArgumentStates(Attributor &A, const AAType &QueryingAA, + StateType &S) { + LLVM_DEBUG(dbgs() << "[Attributor] Clamp call site argument states for " + << static_cast(QueryingAA) + << " into " << S << "\n"); + + assert(QueryingAA.getIRPosition().getPositionKind() == + IRPosition::IRP_ARGUMENT && + "Can only clamp call site argument states for an argument position!"); + + // Use an optional state as there might not be any return values and we want + // to join (IntegerState::operator&) the state of all there are. + Optional T; + + // The argument number which is also the call site argument number. + unsigned ArgNo = QueryingAA.getIRPosition().getArgNo(); + + auto CallSiteCheck = [&](CallSite CS) { + const IRPosition &CSArgPos = IRPosition::callsite_argument(CS, ArgNo); + const AAType *AA = A.getAAFor(QueryingAA, CSArgPos); + LLVM_DEBUG(dbgs() << "[Attributor] CS: " << *CS.getInstruction() + << " AA: " << (AA ? AA->getAsStr() : "n/a") << " @" + << CSArgPos << "\n"); + // TODO: We should create abstract attributes on-demand, patches are already + // prepared, pending approval. + if (!AA || AA->getIRPosition() != CSArgPos) + return false; + const StateType &AAS = static_cast(AA->getState()); + if (T.hasValue()) + *T &= AAS; + else + T = AAS; + LLVM_DEBUG(dbgs() << "[Attributor] AA State: " << AAS << " CSA State: " << T + << "\n"); + return T->isValidState(); + }; + + if (!A.checkForAllCallSites(CallSiteCheck, QueryingAA, true)) + S.indicatePessimisticFixpoint(); + else if (T.hasValue()) + S ^= *T; +} + +/// Helper class for generic deduction: call site argument -> argument position. +template +struct AAArgumentFromCallSiteArguments : public AAType { + AAArgumentFromCallSiteArguments(const IRPosition &IRP) : AAType(IRP) {} + + /// See AbstractAttribute::updateImpl(...). + ChangeStatus updateImpl(Attributor &A) override { + StateType S; + clampCallSiteArgumentStates(A, *this, S); + return clampStateAndIndicateChange(this->getState(), S); + } +}; + +/// Helper class for generic replication: function returned -> cs returned. +template +struct AACallSiteReturnedFromReturned : public AAType { + AACallSiteReturnedFromReturned(const IRPosition &IRP) : AAType(IRP) {} + + /// See AbstractAttribute::updateImpl(...). + ChangeStatus updateImpl(Attributor &A) override { + assert(this->getIRPosition().getPositionKind() == + IRPosition::IRP_CALL_SITE_RETURNED && + "Can only wrap function returned positions for call site returned " + "positions!"); + auto &S = this->getState(); + + const Function *AssociatedFunction = + this->getIRPosition().getAssociatedFunction(); + if (!AssociatedFunction) + return S.indicatePessimisticFixpoint(); + + IRPosition FnPos = IRPosition::returned(*AssociatedFunction); + // TODO: We should create abstract attributes on-demand, patches are already + // prepared, pending approval. + const AAType *AA = A.getAAFor(*this, FnPos); + if (!AA) + return S.indicatePessimisticFixpoint(); + return clampStateAndIndicateChange( + S, static_cast(AA->getState())); + } +}; + /// -----------------------NoUnwind Function Attribute-------------------------- struct AANoUnwindImpl : AANoUnwind { @@ -1288,7 +1454,7 @@ struct AANoAliasImpl : AANoAlias { struct AANoAliasReturned final : AANoAliasImpl { AANoAliasReturned(const IRPosition &IRP) : AANoAliasImpl(IRP) {} - /// See AbstractAttriubute::initialize(...). + /// See AbstractAttribute::initialize(...). void initialize(Attributor &A) override { Function &F = *getAnchorScope(); @@ -1942,13 +2108,7 @@ struct AAAlignImpl : AAAlign { // Max alignemnt value allowed in IR static const unsigned MAX_ALIGN = 1U << 29; - const std::string getAsStr() const override { - return getAssumedAlign() ? ("align<" + std::to_string(getKnownAlign()) + - "-" + std::to_string(getAssumedAlign()) + ">") - : "unknown-align"; - } - - /// See AbstractAttriubute::initialize(...). + /// See AbstractAttribute::initialize(...). void initialize(Attributor &A) override { takeAssumedMinimum(MAX_ALIGN); @@ -1962,131 +2122,82 @@ struct AAAlignImpl : AAAlign { virtual void getDeducedAttributes(LLVMContext &Ctx, SmallVectorImpl &Attrs) const override { - Attrs.emplace_back(Attribute::getWithAlignment(Ctx, getAssumedAlign())); + if (getAssumedAlign() > 1) + Attrs.emplace_back(Attribute::getWithAlignment(Ctx, getAssumedAlign())); } -}; - -/// Align attribute for function return value. -struct AAAlignReturned final : AAAlignImpl { - AAAlignReturned(const IRPosition &IRP) : AAAlignImpl(IRP) {} - /// See AbstractAttribute::updateImpl(...). - ChangeStatus updateImpl(Attributor &A) override; - - /// See AbstractAttribute::trackStatistics() - void trackStatistics() const override { STATS_DECLTRACK_FNRET_ATTR(aligned) } + /// See AbstractAttribute::getAsStr(). + const std::string getAsStr() const override { + return getAssumedAlign() ? ("align<" + std::to_string(getKnownAlign()) + + "-" + std::to_string(getAssumedAlign()) + ">") + : "unknown-align"; + } }; -ChangeStatus AAAlignReturned::updateImpl(Attributor &A) { +/// Align attribute for a floating value. +struct AAAlignFloating : AAAlignImpl { + AAAlignFloating(const IRPosition &IRP) : AAAlignImpl(IRP) {} - // 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 - // wouldn't have align. If no assumed state was used for reasoning, an - // optimistic fixpoint is reached earlier. + /// See AbstractAttribute::updateImpl(...). + ChangeStatus updateImpl(Attributor &A) override { + const DataLayout &DL = A.getDataLayout(); + + auto VisitValueCB = [&](Value &V, AAAlign::StateType &T, bool Stripped) { + if (!Stripped && + getIRPosition().getPositionKind() == IRPosition::IRP_FLOAT) { + // Use only IR information if we did not strip anything. + T.takeKnownMaximum(V.getPointerAlignment(DL)); + T.indicatePessimisticFixpoint(); + } else if (const auto *AA = + A.getAAFor(*this, IRPosition::value(V))) { + // Try to use abstract attribute information. + const AAAlign::StateType &DS = + static_cast(AA->getState()); + T.takeAssumedMinimum(DS.getAssumed()); + } else { + // Last resort, look into the IR. + T.takeKnownMaximum(V.getPointerAlignment(DL)); + T.indicatePessimisticFixpoint(); + } + }; - base_t BeforeState = getAssumed(); - auto CheckReturnValue = - [&](Value &RV, const SmallPtrSetImpl &RetInsts) -> bool { - auto *AlignAA = A.getAAFor(*this, IRPosition::value(RV)); + StateType T; + if (!genericValueTraversal(A, getIRPosition(), *this, T, + VisitValueCB)) + indicatePessimisticFixpoint(); - if (AlignAA) - takeAssumedMinimum(AlignAA->getAssumedAlign()); - else - // Use IR information. - takeAssumedMinimum(RV.getPointerAlignment(A.getDataLayout())); + return clampStateAndIndicateChange(getState(), T); + } - return isValidState(); - }; + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { STATS_DECLTRACK_FLOATING_ATTR(align) } +}; - if (!A.checkForAllReturnedValuesAndReturnInsts(CheckReturnValue, *this)) - return indicatePessimisticFixpoint(); +/// Align attribute for function return value. +struct AAAlignReturned final : AAReturnedFromReturnedValues { + AAAlignReturned(const IRPosition &IRP) + : AAReturnedFromReturnedValues(IRP) {} - return (getAssumed() != BeforeState) ? ChangeStatus::CHANGED - : ChangeStatus::UNCHANGED; -} + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { STATS_DECLTRACK_FNRET_ATTR(aligned) } +}; /// Align attribute for function argument. -struct AAAlignArgument final : AAAlignImpl { - AAAlignArgument(const IRPosition &IRP) : AAAlignImpl(IRP) {} - - /// See AbstractAttribute::updateImpl(...). - virtual ChangeStatus updateImpl(Attributor &A) override; +struct AAAlignArgument final : AAArgumentFromCallSiteArguments { + AAAlignArgument(const IRPosition &IRP) + : AAArgumentFromCallSiteArguments(IRP) {} /// See AbstractAttribute::trackStatistics() void trackStatistics() const override{STATS_DECLTRACK_ARG_ATTR(aligned)}; }; -ChangeStatus AAAlignArgument::updateImpl(Attributor &A) { - - Argument &Arg = cast(getAnchorValue()); - - unsigned ArgNo = Arg.getArgNo(); - const DataLayout &DL = A.getDataLayout(); - - auto BeforeState = getAssumed(); - - // Callback function - std::function CallSiteCheck = [&](CallSite CS) { - assert(CS && "Sanity check: Call site was not initialized properly!"); - - auto *AlignAA = - A.getAAFor(*this, IRPosition::callsite_argument(CS, ArgNo)); - - // Check that AlignAA is AAAlignCallSiteArgument. - if (AlignAA) { - ImmutableCallSite ICS(&AlignAA->getIRPosition().getAnchorValue()); - if (ICS && CS.getInstruction() == ICS.getInstruction()) { - takeAssumedMinimum(AlignAA->getAssumedAlign()); - return isValidState(); - } - } - - Value *V = CS.getArgOperand(ArgNo); - takeAssumedMinimum(V->getPointerAlignment(DL)); - return isValidState(); - }; - - if (!A.checkForAllCallSites(CallSiteCheck, *this, true)) - indicatePessimisticFixpoint(); - - return BeforeState == getAssumed() ? ChangeStatus::UNCHANGED - : ChangeStatus ::CHANGED; -} - -struct AAAlignCallSiteArgument final : AAAlignImpl { - AAAlignCallSiteArgument(const IRPosition &IRP) : AAAlignImpl(IRP) {} - - /// See AbstractAttribute::initialize(...). - void initialize(Attributor &A) override { - takeKnownMaximum( - getAssociatedValue().getPointerAlignment(A.getDataLayout())); - } - - /// See AbstractAttribute::updateImpl(Attributor &A). - ChangeStatus updateImpl(Attributor &A) override; +struct AAAlignCallSiteArgument final : AAAlignFloating { + AAAlignCallSiteArgument(const IRPosition &IRP) : AAAlignFloating(IRP) {} /// See AbstractAttribute::trackStatistics() void trackStatistics() const override { STATS_DECLTRACK_CSARG_ATTR(aligned) } }; -ChangeStatus AAAlignCallSiteArgument::updateImpl(Attributor &A) { - // NOTE: Never look at the argument of the callee in this method. - // If we do this, "align" is always deduced because of the assumption. - - auto BeforeState = getAssumed(); - - Value &V = getAssociatedValue(); - auto *AlignAA = A.getAAFor(*this, IRPosition::value(V)); - - if (AlignAA) - takeAssumedMinimum(AlignAA->getAssumedAlign()); - else - indicatePessimisticFixpoint(); - - return BeforeState == getAssumed() ? ChangeStatus::UNCHANGED - : ChangeStatus::CHANGED; -} - /// Align attribute deduction for a call site return value. using AAAlignCallSiteReturned = AAAlignReturned; diff --git a/test/Transforms/FunctionAttrs/align.ll b/test/Transforms/FunctionAttrs/align.ll index d762d516d9a..32ccbb72fbf 100644 --- a/test/Transforms/FunctionAttrs/align.ll +++ b/test/Transforms/FunctionAttrs/align.ll @@ -37,13 +37,19 @@ declare i32* @unknown() declare align 8 i32* @align8() -; ATTRIBUTOR: define align 8 i32* @test5_1() +; FIXME: Until we have "on-demand" attribute generation we do not determine the +; alignment for the return value here. +; define align 8 i32* @test5_1() +; ATTRIBUTOR: define i32* @test5_1() define i32* @test5_1() { %ret = tail call align 8 i32* @unknown() ret i32* %ret } -; ATTRIBUTOR: define align 8 i32* @test5_2() +; FIXME: Until we have "on-demand" attribute generation we do not determine the +; alignment for the return value here. +; define align 8 i32* @test5_2() +; ATTRIBUTOR: define i32* @test5_2() define i32* @test5_2() { %ret = tail call i32* @align8() ret i32* %ret @@ -83,7 +89,10 @@ define i32* @test6_2() #0 { ; Function Attrs: nounwind readnone ssp uwtable define internal i8* @f1(i8* readnone %0) local_unnamed_addr #0 { -; ATTRIBUTOR: define internal nonnull align 8 i8* @f1(i8* nonnull readnone align 8 %0) +; FIXME: Until we have "on-demand" attribute generation we do not determine the +; alignment for the return value here. +; define internal nonnull align 8 i8* @f1(i8* nonnull readnone align 8 %0) +; ATTRIBUTOR: define internal nonnull i8* @f1(i8* nonnull readnone align 8 %0) %2 = icmp eq i8* %0, null br i1 %2, label %3, label %5 @@ -99,7 +108,10 @@ define internal i8* @f1(i8* readnone %0) local_unnamed_addr #0 { ; Function Attrs: nounwind readnone ssp uwtable define internal i8* @f2(i8* readnone %0) local_unnamed_addr #0 { -; ATTRIBUTOR: define internal nonnull align 8 i8* @f2(i8* nonnull readnone align 8 %0) +; FIXME: Until we have "on-demand" attribute generation we do not determine the +; alignment for the return value here. +; define internal nonnull align 8 i8* @f2(i8* nonnull readnone align 8 %0) +; ATTRIBUTOR: define internal nonnull i8* @f2(i8* nonnull readnone align 8 %0) %2 = icmp eq i8* %0, null br i1 %2, label %5, label %3 @@ -121,7 +133,10 @@ define internal i8* @f2(i8* readnone %0) local_unnamed_addr #0 { ; Function Attrs: nounwind readnone ssp uwtable define internal i8* @f3(i8* readnone %0) local_unnamed_addr #0 { -; ATTRIBUTOR: define internal nonnull align 8 i8* @f3(i8* nonnull readnone align 16 %0) +; FIXME: Until we have "on-demand" attribute generation we do not determine the +; alignment for the return value here. +; define internal nonnull align 8 i8* @f3(i8* nonnull readnone align 16 %0) +; ATTRIBUTOR: define internal nonnull i8* @f3(i8* nonnull readnone align 16 %0) %2 = icmp eq i8* %0, null br i1 %2, label %3, label %5 @@ -163,6 +178,13 @@ define internal void @test8(i32* %a, i32* %b, i32* %c) { ret void } +declare void @test9_helper(i32* %A) +define void @test9_traversal(i1 %c, i32* align 4 %B, i32* align 8 %C) { + %sel = select i1 %c, i32* %B, i32* %C + call void @test9_helper(i32* %sel) + ret void +} + attributes #0 = { nounwind uwtable noinline } attributes #1 = { uwtable noinline } diff --git a/test/Transforms/FunctionAttrs/noalias_returned.ll b/test/Transforms/FunctionAttrs/noalias_returned.ll index 2cffec7f2e7..755263233da 100644 --- a/test/Transforms/FunctionAttrs/noalias_returned.ll +++ b/test/Transforms/FunctionAttrs/noalias_returned.ll @@ -79,13 +79,19 @@ declare i8* @baz(...) nounwind uwtable ; TEST 5 ; Returning global pointer. Should not be noalias. -; CHECK: define nonnull align 8 dereferenceable(8) i8** @getter() +; FIXME: Until we have "on-demand" attribute generation we do not determine the +; alignment for the return value here. +; define nonnull align 8 dereferenceable(8) i8** @getter() +; CHECK: define nonnull dereferenceable(8) i8** @getter() define i8** @getter() { ret i8** @G } +; FIXME: Until we have "on-demand" attribute generation we do not determine the +; alignment for the return value here. ; Returning global pointer. Should not be noalias. -; CHECK: define nonnull align 8 dereferenceable(8) i8** @calle1() +; define nonnull align 8 dereferenceable(8) i8** @calle1() +; CHECK: define nonnull dereferenceable(8) i8** @calle1() define i8** @calle1(){ %1 = call i8** @getter() ret i8** %1 -- 2.49.0