Index: llvm/trunk/lib/Transforms/IPO/Attributor.cpp =================================================================== --- llvm/trunk/lib/Transforms/IPO/Attributor.cpp +++ llvm/trunk/lib/Transforms/IPO/Attributor.cpp @@ -139,7 +139,7 @@ template bool genericValueTraversal( Attributor &A, IRPosition IRP, const AAType &QueryingAA, StateTy &State, - const function_ref &VisitValueCB, + const function_ref &VisitValueCB, int MaxValues = 8) { const AAIsDead *LivenessAA = nullptr; @@ -204,7 +204,8 @@ } // Once a leaf is reached we inform the user through the callback. - VisitValueCB(*V, State, Iteration > 1); + if (!VisitValueCB(*V, State, Iteration > 1)) + return false; } while (!Worklist.empty()); // All values have been visited. @@ -468,6 +469,12 @@ return Assumed == S.getAssumed() ? ChangeStatus::UNCHANGED : ChangeStatus::CHANGED; } + +template <> +ChangeStatus clampStateAndIndicateChange(BooleanState &S, + const BooleanState &R) { + return clampStateAndIndicateChange(S, R); +} ///} /// Clamp the information known for all returned values of a function @@ -888,7 +895,7 @@ }; // Callback for a leaf value returned by the associated function. - auto VisitValueCB = [](Value &Val, RVState &RVS, bool) { + auto VisitValueCB = [](Value &Val, RVState &RVS, bool) -> bool { auto Size = RVS.RetValsMap[&Val].size(); RVS.RetValsMap[&Val].insert(RVS.RetInsts.begin(), RVS.RetInsts.end()); bool Inserted = RVS.RetValsMap[&Val].size() != Size; @@ -898,6 +905,7 @@ dbgs() << "[AAReturnedValues] 1 Add new returned value " << Val << " => " << RVS.RetInsts.size() << "\n"; }); + return true; }; // Helper method to invoke the generic value traversal. @@ -1245,141 +1253,111 @@ struct AANonNullImpl : AANonNull { AANonNullImpl(const IRPosition &IRP) : AANonNull(IRP) {} - /// See AbstractAttribute::getAsStr(). - const std::string getAsStr() const override { - return getAssumed() ? "nonnull" : "may-null"; - } - /// See AbstractAttribute::initialize(...). void initialize(Attributor &A) override { if (hasAttr({Attribute::NonNull, Attribute::Dereferenceable})) indicateOptimisticFixpoint(); } - /// Generate a predicate that checks if a given value is assumed nonnull. - /// The generated function returns true if a value satisfies any of - /// following conditions. - /// (i) A value is known nonZero(=nonnull). - /// (ii) A value is associated with AANonNull and its isAssumedNonNull() is - /// true. - std::function &)> - generatePredicate(Attributor &); -}; - -std::function &)> -AANonNullImpl::generatePredicate(Attributor &A) { - // FIXME: The `AAReturnedValues` should provide the predicate with the - // `ReturnInst` vector as well such that we can use the control flow sensitive - // version of `isKnownNonZero`. This should fix `test11` in - // `test/Transforms/FunctionAttrs/nonnull.ll` - - std::function &)> Pred = - [&](Value &RV, const SmallPtrSetImpl &RetInsts) -> bool { - if (isKnownNonZero(&RV, A.getDataLayout())) - return true; + /// See AbstractAttribute::getAsStr(). + const std::string getAsStr() const override { + return getAssumed() ? "nonnull" : "may-null"; + } +}; - if (ImmutableCallSite ICS = ImmutableCallSite(&RV)) - if (ICS.hasRetAttr(Attribute::NonNull)) - return true; +/// NonNull attribute for a floating value. +struct AANonNullFloating : AANonNullImpl { + AANonNullFloating(const IRPosition &IRP) : AANonNullImpl(IRP) {} - auto *NonNullAA = A.getAAFor(*this, IRPosition::value(RV)); - return (NonNullAA && NonNullAA->isAssumedNonNull()); - }; + /// See AbstractAttribute::initialize(...). + void initialize(Attributor &A) override { + AANonNullImpl::initialize(A); - return Pred; -} + if (isAtFixpoint()) + return; -/// NonNull attribute for function return value. -struct AANonNullReturned final : AANonNullImpl { - AANonNullReturned(const IRPosition &IRP) : AANonNullImpl(IRP) {} + const IRPosition &IRP = getIRPosition(); + const Value &V = IRP.getAssociatedValue(); + const DataLayout &DL = A.getDataLayout(); + + // TODO: This context sensitive query should be removed once we can do + // context sensitive queries in the genericValueTraversal below. + if (isKnownNonZero(&V, DL, 0, /* TODO: AC */ nullptr, IRP.getCtxI(), + /* TODO: DT */ nullptr)) + indicateOptimisticFixpoint(); + } /// See AbstractAttribute::updateImpl(...). ChangeStatus updateImpl(Attributor &A) override { - std::function &)> Pred = - this->generatePredicate(A); + const DataLayout &DL = A.getDataLayout(); - if (!A.checkForAllReturnedValuesAndReturnInsts(Pred, *this)) + auto VisitValueCB = [&](Value &V, AAAlign::StateType &T, + bool Stripped) -> bool { + if (isKnownNonZero(&V, DL, 0, /* TODO: AC */ nullptr, + /* TODO: CtxI */ nullptr, + /* TODO: DT */ nullptr)) { + // Known non-zero, all good. + } else if (const auto *AA = + A.getAAFor(*this, IRPosition::value(V))) { + // Try to use abstract attribute information. + if (!AA->isAssumedNonNull()) + T.indicatePessimisticFixpoint(); + } else { + // IR information was not sufficient and we did not find an abstract + // attribute to use. TODO: on-demand attribute creation! + T.indicatePessimisticFixpoint(); + } + return T.isValidState(); + }; + + StateType T; + if (!genericValueTraversal(A, getIRPosition(), *this, + T, VisitValueCB)) return indicatePessimisticFixpoint(); - return ChangeStatus::UNCHANGED; + + return clampStateAndIndicateChange(getState(), T); } /// See AbstractAttribute::trackStatistics() void trackStatistics() const override { STATS_DECLTRACK_FNRET_ATTR(nonnull) } }; -/// NonNull attribute for function argument. -struct AANonNullArgument final : AANonNullImpl { - AANonNullArgument(const IRPosition &IRP) : AANonNullImpl(IRP) {} - - /// See AbstractAttribute::updateImpl(...). - ChangeStatus updateImpl(Attributor &A) override { - unsigned ArgNo = getArgNo(); - - // Callback function - std::function CallSiteCheck = [&](CallSite CS) { - assert(CS && "Sanity check: Call site was not initialized properly!"); - - IRPosition CSArgPos = IRPosition::callsite_argument(CS, ArgNo); - if (CSArgPos.hasAttr({Attribute::NonNull, Attribute::Dereferenceable})) - return true; - - // Check that NonNullAA is AANonNullCallSiteArgument. - if (auto *NonNullAA = A.getAAFor(*this, CSArgPos)) { - ImmutableCallSite ICS(&NonNullAA->getAnchorValue()); - if (ICS && CS.getInstruction() == ICS.getInstruction()) - return NonNullAA->isAssumedNonNull(); - return false; - } +/// NonNull attribute for function return value. +struct AANonNullReturned final : AAReturnedFromReturnedValues { + AANonNullReturned(const IRPosition &IRP) + : AAReturnedFromReturnedValues(IRP) {} - Value *V = CS.getArgOperand(ArgNo); - if (isKnownNonZero(V, A.getDataLayout())) - return true; + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { STATS_DECLTRACK_FNRET_ATTR(nonnull) } +}; - return false; - }; - if (!A.checkForAllCallSites(CallSiteCheck, *this, true)) - return indicatePessimisticFixpoint(); - return ChangeStatus::UNCHANGED; - } +/// NonNull attribute for function argument. +struct AANonNullArgument final + : AAArgumentFromCallSiteArguments { + AANonNullArgument(const IRPosition &IRP) + : AAArgumentFromCallSiteArguments(IRP) {} /// See AbstractAttribute::trackStatistics() void trackStatistics() const override { STATS_DECLTRACK_ARG_ATTR(nonnull) } }; -/// NonNull attribute for a call site argument. -struct AANonNullCallSiteArgument final : AANonNullImpl { - AANonNullCallSiteArgument(const IRPosition &IRP) : AANonNullImpl(IRP) {} - - /// See AbstractAttribute::initialize(...). - void initialize(Attributor &A) override { - AANonNullImpl::initialize(A); - if (!isKnownNonNull() && - isKnownNonZero(&getAssociatedValue(), A.getDataLayout())) - indicateOptimisticFixpoint(); - } +struct AANonNullCallSiteArgument final : AANonNullFloating { + AANonNullCallSiteArgument(const IRPosition &IRP) : AANonNullFloating(IRP) {} - /// See AbstractAttribute::updateImpl(Attributor &A). - ChangeStatus updateImpl(Attributor &A) override { - // NOTE: Never look at the argument of the callee in this method. - // If we do this, "nonnull" is always deduced because of the - // assumption. - - Value &V = getAssociatedValue(); - auto *NonNullAA = A.getAAFor(*this, IRPosition::value(V)); - - if (!NonNullAA || !NonNullAA->isAssumedNonNull()) - return indicatePessimisticFixpoint(); + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { STATS_DECLTRACK_CSARG_ATTR(aligned) } +}; - return ChangeStatus::UNCHANGED; - } +/// NonNull attribute for a call site return position. +struct AANonNullCallSiteReturned final + : AACallSiteReturnedFromReturned { + AANonNullCallSiteReturned(const IRPosition &IRP) + : AACallSiteReturnedFromReturned(IRP) {} /// See AbstractAttribute::trackStatistics() - void trackStatistics() const override { STATS_DECLTRACK_CSARG_ATTR(nonnull) } + void trackStatistics() const override { STATS_DECLTRACK_CSRET_ATTR(nonnull) } }; -/// NonNull attribute deduction for a call sites. -using AANonNullCallSiteReturned = AANonNullReturned; - /// ------------------------ No-Recurse Attributes ---------------------------- struct AANoRecurseImpl : public AANoRecurse { @@ -2245,7 +2223,8 @@ ChangeStatus updateImpl(Attributor &A) override { const DataLayout &DL = A.getDataLayout(); - auto VisitValueCB = [&](Value &V, AAAlign::StateType &T, bool Stripped) { + auto VisitValueCB = [&](Value &V, AAAlign::StateType &T, + bool Stripped) -> bool { if (!Stripped && getIRPosition().getPositionKind() == IRPosition::IRP_FLOAT) { // Use only IR information if we did not strip anything. @@ -2262,6 +2241,7 @@ T.takeKnownMaximum(V.getPointerAlignment(DL)); T.indicatePessimisticFixpoint(); } + return T.isValidState(); }; StateType T; Index: llvm/trunk/test/Transforms/FunctionAttrs/align.ll =================================================================== --- llvm/trunk/test/Transforms/FunctionAttrs/align.ll +++ llvm/trunk/test/Transforms/FunctionAttrs/align.ll @@ -92,7 +92,7 @@ ; 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) +; ATTRIBUTOR: define internal i8* @f1(i8* nonnull readnone align 8 %0) %2 = icmp eq i8* %0, null br i1 %2, label %3, label %5 @@ -111,7 +111,7 @@ ; 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) +; ATTRIBUTOR: define internal i8* @f2(i8* nonnull readnone align 8 %0) %2 = icmp eq i8* %0, null br i1 %2, label %5, label %3 @@ -136,7 +136,7 @@ ; 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) +; ATTRIBUTOR: define internal i8* @f3(i8* nonnull readnone align 16 %0) %2 = icmp eq i8* %0, null br i1 %2, label %3, label %5 Index: llvm/trunk/test/Transforms/FunctionAttrs/dereferenceable.ll =================================================================== --- llvm/trunk/test/Transforms/FunctionAttrs/dereferenceable.ll +++ llvm/trunk/test/Transforms/FunctionAttrs/dereferenceable.ll @@ -22,20 +22,23 @@ ; TEST 3 ; GEP inbounds define i32* @test3_1(i32* dereferenceable(8) %0) local_unnamed_addr { -; ATTRIBUTOR: define nonnull dereferenceable(4) i32* @test3_1(i32* nonnull dereferenceable(8) %0) +; define nonnull dereferenceable(4) i32* @test3_1(i32* nonnull dereferenceable(8) %0) +; ATTRIBUTOR: define dereferenceable_or_null(4) i32* @test3_1(i32* nonnull dereferenceable(8) %0) %ret = getelementptr inbounds i32, i32* %0, i64 1 ret i32* %ret } define i32* @test3_2(i32* dereferenceable_or_null(32) %0) local_unnamed_addr { ; FIXME: Argument should be mark dereferenceable because of GEP `inbounds`. -; ATTRIBUTOR: define nonnull dereferenceable(16) i32* @test3_2(i32* dereferenceable_or_null(32) %0) +; define nonnull dereferenceable(16) i32* @test3_2(i32* dereferenceable_or_null(32) %0) +; ATTRIBUTOR: define dereferenceable_or_null(16) i32* @test3_2(i32* dereferenceable_or_null(32) %0) %ret = getelementptr inbounds i32, i32* %0, i64 4 ret i32* %ret } define i32* @test3_3(i32* dereferenceable(8) %0, i32* dereferenceable(16) %1, i1 %2) local_unnamed_addr { -; ATTRIBUTOR: define nonnull dereferenceable(4) i32* @test3_3(i32* nonnull dereferenceable(8) %0, i32* nonnull dereferenceable(16) %1, i1 %2) local_unnamed_addr +; define nonnull dereferenceable(4) i32* @test3_3(i32* nonnull dereferenceable(8) %0, i32* nonnull dereferenceable(16) %1, i1 %2) local_unnamed_addr +; ATTRIBUTOR: define dereferenceable_or_null(4) i32* @test3_3(i32* nonnull dereferenceable(8) %0, i32* nonnull dereferenceable(16) %1, i1 %2) local_unnamed_addr %ret1 = getelementptr inbounds i32, i32* %0, i64 1 %ret2 = getelementptr inbounds i32, i32* %1, i64 2 %ret = select i1 %2, i32* %ret1, i32* %ret2 Index: llvm/trunk/test/Transforms/FunctionAttrs/noalias_returned.ll =================================================================== --- llvm/trunk/test/Transforms/FunctionAttrs/noalias_returned.ll +++ llvm/trunk/test/Transforms/FunctionAttrs/noalias_returned.ll @@ -82,7 +82,7 @@ ; 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() +; CHECK: define dereferenceable_or_null(8) i8** @getter() define i8** @getter() { ret i8** @G } @@ -91,7 +91,7 @@ ; alignment for the return value here. ; Returning global pointer. Should not be noalias. ; define nonnull align 8 dereferenceable(8) i8** @calle1() -; CHECK: define nonnull dereferenceable(8) i8** @calle1() +; CHECK: define dereferenceable_or_null(8) i8** @calle1() define i8** @calle1(){ %1 = call i8** @getter() ret i8** %1 Index: llvm/trunk/test/Transforms/FunctionAttrs/nonnull.ll =================================================================== --- llvm/trunk/test/Transforms/FunctionAttrs/nonnull.ll +++ llvm/trunk/test/Transforms/FunctionAttrs/nonnull.ll @@ -8,13 +8,18 @@ ; Return a pointer trivially nonnull (call return attribute) define i8* @test1() { -; BOTH: define nonnull i8* @test1 +; FIXME: Until we have "on-demand" attribute generation we do not determine the +; return value properties. +; FNATTR: define nonnull i8* @test1 +; ATTRIBUTOR: define i8* @test1 %ret = call i8* @ret_nonnull() ret i8* %ret } ; Return a pointer trivially nonnull (argument attribute) define i8* @test2(i8* nonnull %p) { +; FIXME: Until we have "on-demand" attribute generation we do not determine the +; return value properties. ; BOTH: define nonnull i8* @test2 ret i8* %p } @@ -33,7 +38,10 @@ } define i8* @test3(i1 %c) { -; BOTH: define nonnull i8* @test3 +; FIXME: Until we have "on-demand" attribute generation we do not determine the +; return value properties. +; FNATTR: define nonnull i8* @test3 +; ATTRIBUTOR: define i8* @test3 call i8* @scc_binder(i1 %c) %ret = call i8* @ret_nonnull() ret i8* %ret @@ -79,7 +87,10 @@ ; Local analysis, but going through a self recursive phi define i8* @test6() { entry: -; BOTH: define nonnull i8* @test6 +; FIXME: Until we have "on-demand" attribute generation we do not determine the +; return value properties. +; FNATTR: define nonnull i8* @test6 +; ATTRIBUTOR: define i8* @test6 %ret = call i8* @ret_nonnull() br label %loop loop: @@ -95,7 +106,10 @@ ret i8* %b } -; BOTH: define nonnull i8* @test8 +; FIXME: Until we have "on-demand" attribute generation we do not determine the +; return value properties. +; FNATTR: define nonnull i8* @test8 +; ATTRIBUTOR: define i8* @test8 define i8* @test8(i8* %a) { %b = getelementptr inbounds i8, i8* %a, i64 1 ret i8* %b @@ -179,7 +193,7 @@ define internal i32* @f1(i32* %arg) { ; FIXME: missing nonnull It should be nonnull @f1(i32* nonnull %arg) -; ATTRIBUTOR: define internal nonnull i32* @f1(i32* %arg) +; ATTRIBUTOR: define internal i32* @f1(i32* %arg) bb: %tmp = icmp eq i32* %arg, null @@ -209,7 +223,7 @@ define internal i32* @f2(i32* %arg) { ; FIXME: missing nonnull. It should be nonnull @f2(i32* nonnull %arg) -; ATTRIBUTOR: define internal nonnull i32* @f2(i32* %arg) +; ATTRIBUTOR: define internal i32* @f2(i32* %arg) bb: ; FIXME: missing nonnull. It should be @f1(i32* nonnull %arg) @@ -429,7 +443,10 @@ unreachable } -; BOTH: define nonnull i32* @gep1( +; FIXME: Until we have "on-demand" attribute generation we do not determine the +; return value properties. +; FNATTR: define nonnull i32* @gep1( +; ATTRIBUTOR: define i32* @gep1( define i32* @gep1(i32* %p) { %q = getelementptr inbounds i32, i32* %p, i32 1 ret i32* %q @@ -448,7 +465,10 @@ ret i32 addrspace(3)* %q } -; BOTH: define internal nonnull i32* @g2() +; FIXME: Until we have "on-demand" attribute generation we do not determine the +; return value properties. +; FNATTR: define internal nonnull i32* @g2() +; ATTRIBUTOR: define internal i32* @g2() define internal i32* @g2() { ret i32* inttoptr (i64 4 to i32*) } Index: llvm/trunk/test/Transforms/FunctionAttrs/noreturn_async.ll =================================================================== --- llvm/trunk/test/Transforms/FunctionAttrs/noreturn_async.ll +++ llvm/trunk/test/Transforms/FunctionAttrs/noreturn_async.ll @@ -83,7 +83,7 @@ ; CHECK-NOT: nounwind ; CHECK-NEXT: define ; CHECK-NEXT: entry: -; CHECK-NEXT: %call3 = call i32 (i8*, ...) @printf(i8* dereferenceable_or_null(18) getelementptr inbounds ([18 x i8], [18 x i8]* @"??_C@_0BC@NKPAGFFJ@Exception?5caught?6?$AA@", i64 0, i64 0)) +; CHECK-NEXT: %call3 = call i32 (i8*, ...) @printf(i8* nonnull dereferenceable(18) getelementptr inbounds ([18 x i8], [18 x i8]* @"??_C@_0BC@NKPAGFFJ@Exception?5caught?6?$AA@", i64 0, i64 0)) ; CHECK-NEXT: call void @"?overflow@@YAXXZ_may_throw"() ; CHECK-NEXT: unreachable %call3 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([18 x i8], [18 x i8]* @"??_C@_0BC@NKPAGFFJ@Exception?5caught?6?$AA@", i64 0, i64 0)) Index: llvm/trunk/test/Transforms/FunctionAttrs/noreturn_sync.ll =================================================================== --- llvm/trunk/test/Transforms/FunctionAttrs/noreturn_sync.ll +++ llvm/trunk/test/Transforms/FunctionAttrs/noreturn_sync.ll @@ -79,7 +79,7 @@ ; CHECK-NOT: nounwind ; CHECK-NEXT: define ; CHECK-NEXT: entry: -; CHECK-NEXT: %call3 = call i32 (i8*, ...) @printf(i8* dereferenceable_or_null(18) getelementptr inbounds ([18 x i8], [18 x i8]* @"??_C@_0BC@NKPAGFFJ@Exception?5caught?6?$AA@", i64 0, i64 0)) +; CHECK-NEXT: %call3 = call i32 (i8*, ...) @printf(i8* nonnull dereferenceable(18) getelementptr inbounds ([18 x i8], [18 x i8]* @"??_C@_0BC@NKPAGFFJ@Exception?5caught?6?$AA@", i64 0, i64 0)) ; CHECK-NEXT: call void @"?overflow@@YAXXZ_may_throw"() ; CHECK-NEXT: unreachable %call3 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([18 x i8], [18 x i8]* @"??_C@_0BC@NKPAGFFJ@Exception?5caught?6?$AA@", i64 0, i64 0)) Index: llvm/trunk/test/Transforms/FunctionAttrs/nosync.ll =================================================================== --- llvm/trunk/test/Transforms/FunctionAttrs/nosync.ll +++ llvm/trunk/test/Transforms/FunctionAttrs/nosync.ll @@ -27,8 +27,11 @@ ; FNATTR: Function Attrs: norecurse nounwind optsize readnone ssp uwtable ; FNATTR-NEXT: define nonnull i32* @foo(%struct.ST* readnone %s) +; FIXME: Until we have "on-demand" attribute generation we do not determine the +; return value properties. ; ATTRIBUTOR: Function Attrs: nofree nosync nounwind optsize readnone ssp uwtable -; ATTRIBUTOR-NEXT: define nonnull i32* @foo(%struct.ST* %s) +; define nonnull i32* @foo(%struct.ST* %s) +; ATTRIBUTOR-NEXT: define i32* @foo(%struct.ST* %s) define i32* @foo(%struct.ST* %s) nounwind uwtable readnone optsize ssp { entry: %arrayidx = getelementptr inbounds %struct.ST, %struct.ST* %s, i64 1, i32 2, i32 1, i64 5, i64 13