Index: llvm/include/llvm/Transforms/IPO/Attributor.h =================================================================== --- llvm/include/llvm/Transforms/IPO/Attributor.h +++ llvm/include/llvm/Transforms/IPO/Attributor.h @@ -253,6 +253,15 @@ Function &F, InformationCache &InfoCache, DenseSet</* Attribute::AttrKind */ unsigned> *Whitelist = nullptr); + /// Check \p Pred on all function call cites. + /// + /// This method will evaluate \p Pred on call sites and return + /// 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<bool(CallSite)> &Pred, + bool RequireAllCallSites); + private: /// The set of all abstract attributes. ///{ @@ -663,6 +672,26 @@ static constexpr Attribute::AttrKind ID = Attribute::Returned; }; +/// An abstract interface for all nonnull attributes. +struct AANonNull : public AbstractAttribute { + + /// See AbstractAttribute::AbstractAttribute(...). + AANonNull(Value &V, InformationCache &InfoCache) + : AbstractAttribute(V, InfoCache) {} + + /// Return true if we assume that the underlying value is nonnull. + virtual bool isAssumedNonNull() const = 0; + + /// Return true if we know that underlying value is nonnull. + virtual bool isKnownNonNull() const = 0; + + /// See AbastractState::getAttrKind(). + Attribute::AttrKind getAttrKind() const override { return ID; } + + /// The identifier used by the Attributor for this class of attributes. + static constexpr Attribute::AttrKind ID = Attribute::NonNull; +}; + } // end namespace llvm #endif // LLVM_TRANSFORMS_IPO_FUNCTIONATTRS_H Index: llvm/lib/Transforms/IPO/Attributor.cpp =================================================================== --- llvm/lib/Transforms/IPO/Attributor.cpp +++ llvm/lib/Transforms/IPO/Attributor.cpp @@ -20,6 +20,7 @@ #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/GlobalsModRef.h" +#include "llvm/Analysis/ValueTracking.h" #include "llvm/IR/Argument.h" #include "llvm/IR/Attributes.h" #include "llvm/IR/InstIterator.h" @@ -656,6 +657,210 @@ return Changed; } +/// ------------------------ NonNull Argument Attribute ------------------------ +struct AANonNullImpl : AANonNull, BooleanState { + + AANonNullImpl(Value &V, InformationCache &InfoCache) + : AANonNull(V, InfoCache) {} + + /// See AbstractAttribute::getState() + /// { + AbstractState &getState() override { return *this; } + const AbstractState &getState() const override { return *this; } + /// } + + virtual const std::string getAsStr() const override { + return getAssumed() ? "nonnull" : "may-null"; + } + + /// See AANonNull::isAssumedNonNull(). + virtual bool isAssumedNonNull() const override { return getAssumed(); } + + /// See AANonNull::isKnownNonNull(). + virtual bool isKnownNonNull() const override { return getKnown(); } + + /// Generate a function to check whether the value is known as 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<bool(Value &)> generatePredicate(Attributor &); +}; + +std::function<bool(Value &)> 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<bool(Value &)> Pred = [&](Value &RV) -> bool { + if (isKnownNonZero(&RV, getAnchorScope().getParent()->getDataLayout())) + return true; + + auto *NonNullAA = A.getAAFor<AANonNullImpl>(*this, RV); + + ImmutableCallSite ICS(&RV); + + // We can deduce nonnull if all return value has nonnull attribute. + + if ((!NonNullAA || !NonNullAA->isValidState() || + !NonNullAA->isAssumedNonNull()) && + (!ICS || !ICS.hasRetAttr(Attribute::NonNull))) + return false; + + return true; + }; + + return Pred; +} + +/// NonNull attribute for function return value. +struct AANonNullReturned : AANonNullImpl { + + AANonNullReturned(Function &F, InformationCache &InfoCache) + : AANonNullImpl(F, InfoCache) {} + + /// See AbstractAttribute::getManifestPosition(). + virtual ManifestPosition getManifestPosition() const override { + return MP_RETURNED; + } + + /// See AbstractAttriubute::initialize(...). + void initialize(Attributor &A) override { + Function &F = getAnchorScope(); + + // Already nonnull. + if (F.getAttributes().hasAttribute(AttributeList::ReturnIndex, + Attribute::NonNull)) + indicateOptimisticFixpoint(); + } + + /// See AbstractAttribute::updateImpl(...). + virtual ChangeStatus updateImpl(Attributor &A) override; +}; + +ChangeStatus AANonNullReturned::updateImpl(Attributor &A) { + Function &F = getAnchorScope(); + + auto *AARetVal = A.getAAFor<AAReturnedValues>(*this, F); + if (!AARetVal) { + indicatePessimisticFixpoint(); + return ChangeStatus::CHANGED; + } + + std::function<bool(Value &)> Pred = this->generatePredicate(A); + if (!AARetVal->checkForallReturnedValues(Pred)) { + indicatePessimisticFixpoint(); + return ChangeStatus::CHANGED; + } + return ChangeStatus::UNCHANGED; +} + +/// NonNull attribute for function argument. +struct AANonNullArgument : AANonNullImpl { + + AANonNullArgument(Argument &A, InformationCache &InfoCache) + : AANonNullImpl(A, InfoCache) {} + + /// See AbstractAttribute::getManifestPosition(). + virtual ManifestPosition getManifestPosition() const override { + return MP_ARGUMENT; + } + + /// See AbstractAttriubute::initialize(...). + void initialize(Attributor &A) override { + Argument *Arg = cast<Argument>(getAssociatedValue()); + if (Arg->hasNonNullAttr()) + indicateOptimisticFixpoint(); + } + + /// See AbstractAttribute::updateImpl(...). + virtual ChangeStatus updateImpl(Attributor &A) override; +}; + +ChangeStatus AANonNullArgument::updateImpl(Attributor &A) { + Function &F = getAnchorScope(); + Argument &Arg = cast<Argument>(getAnchoredValue()); + + unsigned ArgNo = Arg.getArgNo(); + + // Callback function + std::function<bool(CallSite)> CallSiteCheck = [&](CallSite CS) { + assert(CS && "Sanity check: Call site was not initialized properly!"); + + if (CS.paramHasAttr(ArgNo, Attribute::NonNull)) + return true; + + auto *NonNullCSArgAA = + A.getAAFor<AANonNullImpl>(*this, *CS.getInstruction(), ArgNo); + if (!NonNullCSArgAA || !NonNullCSArgAA->isAssumedNonNull()) + return false; + + return true; + }; + + if (!A.checkForAllCallSites(F, CallSiteCheck, true)) { + indicatePessimisticFixpoint(); + return ChangeStatus::CHANGED; + } + return ChangeStatus::UNCHANGED; +} + +/// NonNull attribute for a call site argument. +struct AANonNullCallSiteArgument : public AANonNullImpl { + + /// See AANonNullImpl::AANonNullImpl(...). + AANonNullCallSiteArgument(CallSite CS, InformationCache &InfoCache, + uint32_t ArgNo) + : AANonNullImpl(*CS.getInstruction(), InfoCache), ArgNo(ArgNo) {} + + void initialize(Attributor &A) override { + // Determine if the IR already provides enough information. + if (CallSite(&getAnchoredValue()).paramHasAttr(ArgNo, getAttrKind())) + indicateOptimisticFixpoint(); + } + + /// See AbstractAttribute::updateImpl(Attributor &A). + virtual ChangeStatus updateImpl(Attributor &A) override; + + /// See AbstractAttribute::getAssociatedValue(). + virtual Value *getAssociatedValue() override { + return CallSite(&getAnchoredValue()).getArgument(ArgNo); + } + + /// See AbstractAttribute::getAssociatedValue(). + virtual const Value *getAssociatedValue() const override { + return ImmutableCallSite(&getAnchoredValue()).getArgument(ArgNo); + } + + /// Return associated values's argument index. + int getArgumentNo() const { return ArgNo; } + + /// See AbstractAttribute::getManifestPosition(). + virtual ManifestPosition getManifestPosition() const override { + return MP_CALL_SITE_ARGUMENT; + }; + +private: + /// The underlying value is the argument at position "ArgNo" of the call site + /// that is used as the underyling anchor. See + /// AbstractAttribute::getAssociatedValue(). + const unsigned ArgNo; +}; + +ChangeStatus AANonNullCallSiteArgument::updateImpl(Attributor &A) { + Value &V = *getAssociatedValue(); + + auto *AANonNull = A.getAAFor<AANonNullImpl>(*this, V); + if (!AANonNull || !AANonNull->isAssumedNonNull()) { + indicatePessimisticFixpoint(); + return ChangeStatus::CHANGED; + } + + return ChangeStatus::UNCHANGED; +} + /// ---------------------------------------------------------------------------- /// Attributor /// ---------------------------------------------------------------------------- @@ -805,6 +1010,17 @@ // though it is an argument attribute. if (!Whitelist || Whitelist->count(AAReturnedValues::ID)) registerAA(*new AAReturnedValuesImpl(F, InfoCache)); + + // Every function with pointer return type might be marked nonnull. + if (ReturnType->isPointerTy() && + (!Whitelist || Whitelist->count(AANonNullReturned::ID))) + registerAA(*new AANonNullReturned(F, InfoCache)); + } + + // Every argument with pointer type might be marked nonnull. + for (Argument &Arg : F.args()) { + if (Arg.getType()->isPointerTy()) + registerAA(*new AANonNullArgument(Arg, InfoCache)); } // Walk all instructions to find more attribute opportunities and also @@ -831,9 +1047,57 @@ InstOpcodeMap[I.getOpcode()].push_back(&I); if (I.mayReadOrWriteMemory()) ReadOrWriteInsts.push_back(&I); + + CallSite CS(&I); + if (CS && CS.getCalledFunction()) { + for (int i = 0, e = CS.getCalledFunction()->arg_size(); i < e; i++) { + if (!CS.getArgument(i)->getType()->isPointerTy()) + continue; + + // Call site argument attribute "non-null". + registerAA(*new AANonNullCallSiteArgument(CS, InfoCache, i)); + } + } } } +bool Attributor::checkForAllCallSites(Function &F, + std::function<bool(CallSite)> &Pred, + bool RequireAllCallSites) { + // we can try to determine information from + // the call sites. However, this is only possible all call sites are known, + // hence the function has internal linkage. + if (RequireAllCallSites && !F.hasInternalLinkage()) { + LLVM_DEBUG( + dbgs() + << "Attributor: Function " << F.getName() + << " has no internal linkage, hence not all call sites are known\n"); + return false; + } + + for (const Use &U : F.uses()) { + + CallSite CS(U.getUser()); + if (!CS || !CS.isCallee(&U) || !CS.getCaller()->hasExactDefinition()) { + if (!RequireAllCallSites) + continue; + + LLVM_DEBUG(dbgs() << "Attributor: User " << *U.getUser() + << " is an invalid use of " << F.getName() << "\n"); + return false; + } + + if (Pred(CS)) + continue; + + LLVM_DEBUG(dbgs() << "Attributor: Call site callback failed for " + << *CS.getInstruction() << "\n"); + return false; + } + + return true; +} + /// Helpers to ease debugging through output streams and print calls. /// ///{ Index: llvm/test/Transforms/FunctionAttrs/arg_returned.ll =================================================================== --- llvm/test/Transforms/FunctionAttrs/arg_returned.ll +++ llvm/test/Transforms/FunctionAttrs/arg_returned.ll @@ -278,7 +278,7 @@ ; FIXME: no-return missing ; FNATTR: define noalias i32* @rt1(i32* nocapture readonly %a) ; BOTH: Function Attrs: noinline nounwind readonly uwtable -; BOTH-NEXT: define noalias i32* @rt1(i32* nocapture readonly %a) +; BOTH-NEXT: define noalias nonnull i32* @rt1(i32* nocapture readonly %a) define i32* @rt1(i32* %a) #0 { entry: %v = load i32, i32* %a, align 4 Index: llvm/test/Transforms/FunctionAttrs/nonnull.ll =================================================================== --- llvm/test/Transforms/FunctionAttrs/nonnull.ll +++ llvm/test/Transforms/FunctionAttrs/nonnull.ll @@ -1,11 +1,13 @@ ; RUN: opt -S -functionattrs -enable-nonnull-arg-prop %s | FileCheck %s ; RUN: opt -S -passes=function-attrs -enable-nonnull-arg-prop %s | FileCheck %s +; RUN: opt -attributor --attributor-disable=false -S < %s | FileCheck %s --check-prefix=ATTRIBUTOR declare nonnull i8* @ret_nonnull() ; Return a pointer trivially nonnull (call return attribute) define i8* @test1() { ; CHECK: define nonnull i8* @test1 +; ATTRIBUTOR: define nonnull i8* @test1 %ret = call i8* @ret_nonnull() ret i8* %ret } @@ -13,6 +15,7 @@ ; Return a pointer trivially nonnull (argument attribute) define i8* @test2(i8* nonnull %p) { ; CHECK: define nonnull i8* @test2 +; ATTRIBUTOR: define nonnull i8* @test2 ret i8* %p } @@ -20,12 +23,14 @@ ; can we still mark the other one which is trivially nonnull define i8* @scc_binder() { ; CHECK: define i8* @scc_binder +; ATTRIBUTOR: define i8* @scc_binder call i8* @test3() ret i8* null } define i8* @test3() { ; CHECK: define nonnull i8* @test3 +; ATTRIBUTOR: define nonnull i8* @test3 call i8* @scc_binder() %ret = call i8* @ret_nonnull() ret i8* %ret @@ -36,12 +41,14 @@ ; just never return period.) define i8* @test4_helper() { ; CHECK: define noalias nonnull i8* @test4_helper +; ATTRIBUTOR: define nonnull i8* @test4_helper %ret = call i8* @test4() ret i8* %ret } define i8* @test4() { ; CHECK: define noalias nonnull i8* @test4 +; ATTRIBUTOR: define nonnull i8* @test4 %ret = call i8* @test4_helper() ret i8* %ret } @@ -50,12 +57,14 @@ ; make sure we haven't marked them as nonnull. define i8* @test5_helper() { ; CHECK: define noalias i8* @test5_helper +; ATTRIBUTOR: define i8* @test5_helper %ret = call i8* @test5() ret i8* null } define i8* @test5() { ; CHECK: define noalias i8* @test5 +; ATTRIBUTOR: define i8* @test5 %ret = call i8* @test5_helper() ret i8* %ret } @@ -64,6 +73,7 @@ define i8* @test6() { entry: ; CHECK: define nonnull i8* @test6 +; ATTRIBUTOR: define nonnull i8* @test6 %ret = call i8* @ret_nonnull() br label %loop loop: @@ -73,6 +83,83 @@ ret i8* %phi } +; CHECK: define i8* @test7 +; ATTRIBUTOR: define i8* @test7 +define i8* @test7(i8* %a) { + %b = getelementptr inbounds i8, i8* %a, i64 0 + ret i8* %b +} + +; CHECK: define nonnull i8* @test8 +; ATTRIBUTOR: define nonnull i8* @test8 +define i8* @test8(i8* %a) { + %b = getelementptr inbounds i8, i8* %a, i64 1 + ret i8* %b +} + +; CHECK: define i8* @test9 +; ATTRIBUTOR: define i8* @test9 +define i8* @test9(i8* %a, i64 %n) { + %b = getelementptr inbounds i8, i8* %a, i64 %n + ret i8* %b +} + +declare void @llvm.assume(i1) +; CHECK: define i8* @test10 +; FIXME: missing nonnull +; ATTRIBUTOR: define i8* @test10 +define i8* @test10(i8* %a, i64 %n) { + %cmp = icmp ne i64 %n, 0 + call void @llvm.assume(i1 %cmp) + %b = getelementptr inbounds i8, i8* %a, i64 %n + ret i8* %b +} + +; TEST 11 +; char* test11(char *p) { +; return p? p: nonnull(); +; } +; CHECK: define i8* @test11 +; FIXME: missing nonnull +; ATTRIBUTOR: define i8* @test11 +define i8* @test11(i8*) local_unnamed_addr { + %2 = icmp eq i8* %0, null + br i1 %2, label %3, label %5 + +; <label>:3: ; preds = %1 + %4 = tail call i8* @nonnull(i64 1) + br label %5 + +; <label>:5: ; preds = %3, %1 + %6 = phi i8* [ %4, %3 ], [ %0, %1 ] + ret i8* %6 +} + +; TEST 12 +; Simple CallSite Test +declare void @test12_helper(i8*) +define void @test12(i8* nonnull %a) { +; ATTRIBUTOR: define void @test12(i8* nonnull %a) +; ATTRIBUTOR-NEXT: tail call void @test12_helper(i8* nonnull %a) + tail call void @test12_helper(i8* %a) + ret void +} + +; TEST 13 +; Simple Argument Tests +define void @test13_helper(i8* nonnull %a) { +; ATTRIBUTOR: define void @test13_helper(i8* nonnull %a) + ret void +} +define internal void @test13(i8* %a) { +; ATTRIBUTOR: define internal void @test13(i8* nonnull %a) + tail call void @test13_helper(i8* %a) + ret void +} + +declare nonnull i8* @nonnull(i64) + + ; Test propagation of nonnull callsite args back to caller. declare void @use1(i8* %x) @@ -93,6 +180,11 @@ ; CHECK-NEXT: call void @use3nonnull(i8* %b, i8* %c, i8* %a) ; CHECK-NEXT: ret void ; +; ATTRIBUTOR-LABEL: @parent1(i8* %a, i8* %b, i8* %c) +; ATTRIBUTOR-NEXT: call void @use3(i8* %c, i8* %a, i8* %b) +; ATTRIBUTOR-NEXT: call void @use3nonnull(i8* nonnull %b, i8* nonnull %c, i8* nonnull %a) +; ATTRIBUTOR-NEXT: ret void + call void @use3(i8* %c, i8* %a, i8* %b) call void @use3nonnull(i8* %b, i8* %c, i8* %a) ret void @@ -106,6 +198,11 @@ ; CHECK-NEXT: call void @use3(i8* %c, i8* %a, i8* %b) ; CHECK-NEXT: ret void ; +; ATTRIBUTOR-LABEL: @parent2(i8* %a, i8* %b, i8* %c) +; ATTRIBUTOR-NEXT: call void @use3nonnull(i8* nonnull %b, i8* nonnull %c, i8* nonnull %a) +; ATTRIBUTOR-NEXT: call void @use3(i8* %c, i8* %a, i8* %b) +; ATTRIBUTOR-NEXT: ret void + call void @use3nonnull(i8* %b, i8* %c, i8* %a) call void @use3(i8* %c, i8* %a, i8* %b) ret void @@ -119,6 +216,11 @@ ; CHECK-NEXT: call void @use3(i8* %c, i8* %b, i8* %a) ; CHECK-NEXT: ret void ; +; ATTRIBUTOR-LABEL: @parent3(i8* %a, i8* %b, i8* %c) +; ATTRIBUTOR-NEXT: call void @use1nonnull(i8* nonnull %a) +; ATTRIBUTOR-NEXT: call void @use3(i8* %c, i8* %b, i8* %a) +; ATTRIBUTOR-NEXT: ret void + call void @use1nonnull(i8* %a) call void @use3(i8* %c, i8* %b, i8* %a) ret void @@ -133,6 +235,12 @@ ; CHECK-NEXT: call void @use1(i8* %b) ; CHECK-NEXT: ret void ; +; ATTRIBUTOR-LABEL: @parent4(i8* %a, i8* %b, i8* %c) +; ATTRIBUTOR-NEXT: call void @use2nonnull(i8* nonnull %c, i8* nonnull %b) +; ATTRIBUTOR-NEXT: call void @use2(i8* %a, i8* %c) +; ATTRIBUTOR-NEXT: call void @use1(i8* %b) +; ATTRIBUTOR-NEXT: ret void + call void @use2nonnull(i8* %c, i8* %b) call void @use2(i8* %a, i8* %c) call void @use1(i8* %b) @@ -152,6 +260,14 @@ ; CHECK: f: ; CHECK-NEXT: ret void ; +; ATTRIBUTOR-LABEL: @parent5(i8* %a, i1 %a_is_notnull) +; ATTRIBUTOR-NEXT: br i1 %a_is_notnull, label %t, label %f +; ATTRIBUTOR: t: +; ATTRIBUTOR-NEXT: call void @use1nonnull(i8* nonnull %a) +; ATTRIBUTOR-NEXT: ret void +; ATTRIBUTOR: f: +; ATTRIBUTOR-NEXT: ret void + br i1 %a_is_notnull, label %t, label %f t: call void @use1nonnull(i8* %a) @@ -169,6 +285,11 @@ ; CHECK-NEXT: call void @use1nonnull(i8* %a) ; CHECK-NEXT: ret i8 [[C]] ; +; ATTRIBUTOR-LABEL: @parent6(i8* %a, i8* %b) +; ATTRIBUTOR-NEXT: [[C:%.*]] = load volatile i8, i8* %b +; ATTRIBUTOR-NEXT: call void @use1nonnull(i8* nonnull %a) +; ATTRIBUTOR-NEXT: ret i8 [[C]] + %c = load volatile i8, i8* %b call void @use1nonnull(i8* %a) ret i8 %c @@ -182,6 +303,11 @@ ; CHECK-NEXT: call void @use1nonnull(i8* %a) ; CHECK-NEXT: ret i8 [[RET]] ; +; ATTRIBUTOR-LABEL: @parent7(i8* %a) +; ATTRIBUTOR-NEXT: [[RET:%.*]] = call i8 @use1safecall(i8* %a) +; ATTRIBUTOR-NEXT: call void @use1nonnull(i8* nonnull %a) +; ATTRIBUTOR-NEXT: ret i8 [[RET]] + %ret = call i8 @use1safecall(i8* %a) call void @use1nonnull(i8* %a) ret i8 %ret @@ -204,6 +330,18 @@ ; CHECK-NEXT: filter [0 x i8*] zeroinitializer ; CHECK-NEXT: unreachable ; +; ATTRIBUTOR-LABEL: @parent8(i8* %a, i8* %bogus1, i8* %b) +; ATTRIBUTOR-NEXT: entry: +; ATTRIBUTOR-NEXT: invoke void @use2nonnull(i8* nonnull %a, i8* nonnull %b) +; ATTRIBUTOR-NEXT: to label %cont unwind label %exc +; ATTRIBUTOR: cont: +; ATTRIBUTOR-NEXT: [[NULL_ATTRIBUTOR:%.*]] = icmp eq i8* %b, null +; ATTRIBUTOR-NEXT: ret i1 [[NULL_ATTRIBUTOR]] +; ATTRIBUTOR: exc: +; ATTRIBUTOR-NEXT: [[LP:%.*]] = landingpad { i8*, i32 } +; ATTRIBUTOR-NEXT: filter [0 x i8*] zeroinitializer +; ATTRIBUTOR-NEXT: unreachable + entry: invoke void @use2nonnull(i8* %a, i8* %b) to label %cont unwind label %exc