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 @@ -582,6 +582,26 @@ static constexpr Attribute::AttrKind ID = Attribute::Returned; }; +/// An abstract interface for all noalias attributes. +struct AANoAlias : public AbstractAttribute { + + /// See AbstractAttribute::AbstractAttribute(...). + AANoAlias(Value &V, InformationCache &InfoCache) + : AbstractAttribute(V, InfoCache) {} + + /// Return true if we assume that the underlying value does not alias. + virtual bool isAssumedNoAlias() const = 0; + + /// Return true if we know that underlying value is noalias. + virtual bool isKnownNoAlias() 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::NoAlias; +}; + } // end namespace llvm #endif // LLVM_TRANSFORMS_IPO_FUNCTIONATTRS_H 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 @@ -19,6 +19,7 @@ #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" +#include "llvm/Analysis/CaptureTracking.h" #include "llvm/Analysis/GlobalsModRef.h" #include "llvm/IR/Argument.h" #include "llvm/IR/Attributes.h" @@ -47,6 +48,7 @@ STATISTIC(NumFnKnownReturns, "Number of function with known return values"); STATISTIC(NumFnArgumentReturned, "Number of function arguments marked returned"); +STATISTIC(NumFnArgumentNoAlias, "Number of function arguments marked noalias"); // TODO: Determine a good default value. // @@ -91,10 +93,14 @@ if (!Attr.isEnumAttribute()) return; + switch (Attr.getKindAsEnum()) { case Attribute::Returned: NumFnArgumentReturned++; return; + case Attribute::NoAlias: + NumFnArgumentNoAlias++; + return; default: return; } @@ -646,6 +652,110 @@ return Changed; } +/// ------------------------ NoAlias Argument Attribute ------------------------ + +struct AANoAliasImpl : AANoAlias, BooleanState { + + AANoAliasImpl(Value &V, InformationCache &InfoCache) + : AANoAlias(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() ? "noalias" : "may-alias"; + } + + /// Return deduced attributes in \p Attrs. + virtual void + getDeducedAttributes(SmallVectorImpl &Attrs) const override { + LLVMContext &Ctx = AnchoredVal.getContext(); + Attrs.emplace_back(Attribute::get(Ctx, "noalias")); + } + + /// See AANoAlias::isAssumedNoAlias(). + virtual bool isAssumedNoAlias() const override { return getAssumed(); } + + /// See AANoAlias::isKnowndNoAlias(). + virtual bool isKnownNoAlias() const override { return getKnown(); } +}; + +/// NoAlias attribute for function return value. +struct AANoAliasReturned : AANoAliasImpl { + + AANoAliasReturned(Function &F, InformationCache &InfoCache) + : AANoAliasImpl(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 noalias. + if (F.returnDoesNotAlias()) { + indicateOptimisticFixpoint(); + return; + } + } + + /// See AbstractAttribute::updateImpl(...). + virtual ChangeStatus updateImpl(Attributor &A) override; +}; + +ChangeStatus AANoAliasReturned::updateImpl(Attributor &A) { + Function &F = getAnchorScope(); + + auto *AARetValImpl = A.getAAFor(*this, F); + if (!AARetValImpl) { + indicatePessimisticFixpoint(); + return ChangeStatus::CHANGED; + } + + for (auto &It : *AARetValImpl) { + Value *RV = It.first; + + if (Constant *C = dyn_cast(RV)) + if (C->isNullValue() || isa(C)) + continue; + + /// For now, we can only deduce noalias if we have call sites. + /// FIXME: add more support. + ImmutableCallSite ICS(RV); + if (!ICS) { + indicatePessimisticFixpoint(); + return ChangeStatus::CHANGED; + } + + if (ICS.returnDoesNotAlias()) + continue; + + /// FIXME: We can improve capture check in two ways: + /// 1. Use the AANoCapture facilities. + /// 2. Use the location of return insts for escape queries. + if (PointerMayBeCaptured(RV, /* ReturnCaptures */ false, + /* StoreCaptures */ true)) { + indicatePessimisticFixpoint(); + return ChangeStatus::CHANGED; + } + + auto *NoAliasAA = A.getAAFor(*this, *RV); + + if (!NoAliasAA || !NoAliasAA->isAssumedNoAlias()) { + indicatePessimisticFixpoint(); + return ChangeStatus::CHANGED; + } + } + + return ChangeStatus::UNCHANGED; +} + /// ---------------------------------------------------------------------------- /// Attributor /// ---------------------------------------------------------------------------- @@ -795,6 +905,11 @@ // 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 noalias. + if (ReturnType->isPointerTy() && + (!Whitelist || Whitelist->count(AANoAliasReturned::ID))) + registerAA(*new AANoAliasReturned(F, InfoCache)); } // Walk all instructions to find more attribute opportunities and also diff --git a/llvm/test/Transforms/FunctionAttrs/noalias_returned.ll b/llvm/test/Transforms/FunctionAttrs/noalias_returned.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/FunctionAttrs/noalias_returned.ll @@ -0,0 +1,99 @@ +; RUN: opt -S -attributor -attributor-disable=false < %s | FileCheck %s + +; TEST 1 - negative. + +; void *G; +; void *foo(){ +; void *V = malloc(4); +; G = V; +; return V; +; } + +@G = external global i8* + +; CHECK: define i8* @foo() +define i8* @foo() { + %1 = tail call noalias i8* @malloc(i64 4) + store i8* %1, i8** @G, align 8 + ret i8* %1 +} + +declare noalias i8* @malloc(i64) + +; TEST 2 +; call noalias function in return instruction. +; CHECK: define "noalias" i8* @return_noalias() +define i8* @return_noalias(){ + %1 = tail call noalias i8* @malloc(i64 4) + ret i8* %1 +} + +declare i8* @alias() + +; TEST 3 +; CHECK: define i8* @call_alias() +; CHECK-NOT: "noalias" +define i8* @call_alias(){ + %1 = tail call i8* @alias() + ret i8* %1 +} + +; TEST 4 +; void *baz(); +; void *foo(int a); +; +; void *bar() { +; foo(0); +; return baz(); +; } +; +; void *foo(int a) { +; if (a) +; bar(); +; return malloc(4); +; } + +; CHECK: define i8* @bar() +define i8* @bar() nounwind uwtable { + %1 = tail call i8* (...) @baz() + ret i8* %1 +} + +; CHECK: define "noalias" i8* @foo(i32) +define i8* @foo(i32) nounwind uwtable { + %2 = icmp eq i32 %0, 0 + br i1 %2, label %5, label %3 + +3: ; preds = %1 + %4 = tail call i8* (...) @baz() + br label %5 + +5: ; preds = %1, %3 + %6 = tail call noalias i8* @malloc(i64 4) + ret i8* %6 +} + +declare i8* @baz(...) nounwind uwtable + +; TEST 5 + +define i8* @getter() { + ret i8* @G +} + +define i8* @calle1(){ + %1 = call i8* @getter() + ret i8* %1 +} + +define i8* @calle2(){ + %1 = tail call i8* @getter() + ret i8* %1 +} + +; %1 & %2 alias +define void entry(){ + %1 = tail call i8* @calle1() + %2 = tail call i8* @calee2() +} + diff --git a/llvm/test/Transforms/FunctionAttrs/nonnull.ll b/llvm/test/Transforms/FunctionAttrs/nonnull.ll --- a/llvm/test/Transforms/FunctionAttrs/nonnull.ll +++ b/llvm/test/Transforms/FunctionAttrs/nonnull.ll @@ -1,5 +1,6 @@ ; 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 -S -attributor < %s | FileCheck %s --check-prefix=ATTRIBUTOR declare nonnull i8* @ret_nonnull() @@ -20,6 +21,7 @@ ; can we still mark the other one which is trivially nonnull define i8* @scc_binder() { ; CHECK: define i8* @scc_binder +; ATTRIBUTOR: define "noalias" i8* @scc_binder call i8* @test3() ret i8* null } @@ -36,12 +38,14 @@ ; just never return period.) define i8* @test4_helper() { ; CHECK: define noalias nonnull i8* @test4_helper +; ATTRIBUTOR: define "noalias" i8* @test4_helper %ret = call i8* @test4() ret i8* %ret } define i8* @test4() { ; CHECK: define noalias nonnull i8* @test4 +; ATTRIBUTOR: define "noalias" i8* @test4 %ret = call i8* @test4_helper() ret i8* %ret } @@ -50,12 +54,14 @@ ; make sure we haven't marked them as nonnull. define i8* @test5_helper() { ; CHECK: define noalias i8* @test5_helper +; ATTRIBUTOR: define "noalias" i8* @test5_helper %ret = call i8* @test5() ret i8* null } define i8* @test5() { ; CHECK: define noalias i8* @test5 +; ATTRIBUTOR: define "noalias" i8* @test5 %ret = call i8* @test5_helper() ret i8* %ret }