diff --git a/llvm/include/llvm/IR/KnowledgeRetention.h b/llvm/include/llvm/IR/KnowledgeRetention.h --- a/llvm/include/llvm/IR/KnowledgeRetention.h +++ b/llvm/include/llvm/IR/KnowledgeRetention.h @@ -22,6 +22,7 @@ #include "llvm/ADT/DenseMap.h" namespace llvm { +class IntrinsicInst; /// Build a call to llvm.assume to preserve informations that can be derived /// from the given instruction. @@ -84,7 +85,14 @@ unsigned Max; }; -using RetainedKnowledgeMap = DenseMap; +/// A mapping from intrinsics (=`llvm.assume` calls) to a value range +/// (=knowledge) that is encoded in them. How the value range is interpreted +/// depends on the RetainedKnowledgeKey that was used to get this out of the +/// RetainedKnowledgeMap. +using Assume2KnowledgeMap = DenseMap; + +using RetainedKnowledgeMap = + DenseMap; /// Insert into the map all the informations contained in the operand bundles of /// the llvm.assume. This should be used instead of hasAttributeInAssume when 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 @@ -110,11 +110,13 @@ #include "llvm/Analysis/TargetTransformInfo.h" #include "llvm/IR/CallSite.h" #include "llvm/IR/ConstantRange.h" +#include "llvm/IR/KnowledgeRetention.h" #include "llvm/IR/PassManager.h" #include "llvm/Transforms/Utils/CallGraphUpdater.h" namespace llvm { +struct Attributor; struct AbstractAttribute; struct InformationCache; struct AAIsDead; @@ -398,7 +400,8 @@ /// e.g., the function position if this is an /// argument position, should be ignored. bool hasAttr(ArrayRef AKs, - bool IgnoreSubsumingPositions = false) const; + bool IgnoreSubsumingPositions = false, + Attributor *A = nullptr) const; /// Return the attributes of any kind in \p AKs existing in the IR at a /// position that will affect this one. While each position can only have a @@ -410,7 +413,8 @@ /// argument position, should be ignored. void getAttrs(ArrayRef AKs, SmallVectorImpl &Attrs, - bool IgnoreSubsumingPositions = false) const; + bool IgnoreSubsumingPositions = false, + Attributor *A = nullptr) const; /// Remove the attribute of kind \p AKs existing in the IR at this position. void removeAttrs(ArrayRef AKs) const { @@ -470,6 +474,12 @@ bool getAttrsFromIRAttr(Attribute::AttrKind AK, SmallVectorImpl &Attrs) const; + /// Return the attributes of kind \p AK existing in the IR as operand bundles + /// of an llvm.assume. + bool getAttrsFromAssumes(Attribute::AttrKind AK, + SmallVectorImpl &Attrs, + Attributor &A) const; + protected: /// The value this position is anchored at. Value *AnchorVal; @@ -611,6 +621,9 @@ /// Return datalayout used in the module. const DataLayout &getDL() { return DL; } + /// Return the map conaining all the knowledge we have from `llvm.assume`s. + const RetainedKnowledgeMap &getKnowledgeMap() const { return KnowledgeMap; } + private: /// A map type from functions to opcode to instruction maps. using FuncInstOpcodeMapTy = DenseMap; @@ -631,6 +644,9 @@ /// MustBeExecutedContextExplorer MustBeExecutedContextExplorer Explorer; + /// A map with knowledge retained in `llvm.assume` instructions. + RetainedKnowledgeMap KnowledgeMap; + /// Getters for analysis. AnalysisGetter &AG; @@ -1717,7 +1733,8 @@ /// See AbstractAttribute::initialize(...). virtual void initialize(Attributor &A) override { const IRPosition &IRP = this->getIRPosition(); - if (isa(IRP.getAssociatedValue()) || hasAttr(getAttrKind())) { + if (isa(IRP.getAssociatedValue()) || + hasAttr(getAttrKind(), /* IgnoreSubsumingPositions */ false, &A)) { this->getState().indicateOptimisticFixpoint(); return; } diff --git a/llvm/lib/IR/KnowledgeRetention.cpp b/llvm/lib/IR/KnowledgeRetention.cpp --- a/llvm/lib/IR/KnowledgeRetention.cpp +++ b/llvm/lib/IR/KnowledgeRetention.cpp @@ -206,6 +206,8 @@ bool llvm::hasAttributeInAssume(CallInst &AssumeCI, Value *IsOn, StringRef AttrName, uint64_t *ArgVal, AssumeQuery AQR) { + assert(isa(AssumeCI) && + "this function is intended to be used on llvm.assume"); IntrinsicInst &Assume = cast(AssumeCI); assert(Assume.getIntrinsicID() == Intrinsic::assume && "this function is intended to be used on llvm.assume"); @@ -253,19 +255,19 @@ if (Key.first == nullptr && Key.second == Attribute::None) continue; if (!BundleHasArguement(Bundles, BOIE_Argument)) { - Result[Key] = {0, 0}; + Result[Key][&Assume] = {0, 0}; continue; } unsigned Val = cast( getValueFromBundleOpInfo(Assume, Bundles, BOIE_Argument)) ->getZExtValue(); auto Lookup = Result.find(Key); - if (Lookup == Result.end()) { - Result[Key] = {Val, Val}; + if (Lookup == Result.end() || !Lookup->second.count(&Assume)) { + Result[Key][&Assume] = {Val, Val}; continue; } - Lookup->second.Min = std::min(Val, Lookup->second.Min); - Lookup->second.Max = std::max(Val, Lookup->second.Max); + Lookup->second[&Assume].Min = std::min(Val, Lookup->second[&Assume].Min); + Lookup->second[&Assume].Max = std::max(Val, Lookup->second[&Assume].Max); } } 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 @@ -678,7 +678,7 @@ } bool IRPosition::hasAttr(ArrayRef AKs, - bool IgnoreSubsumingPositions) const { + bool IgnoreSubsumingPositions, Attributor *A) const { SmallVector Attrs; for (const IRPosition &EquivIRP : SubsumingPositionIterator(*this)) { for (Attribute::AttrKind AK : AKs) @@ -690,12 +690,16 @@ if (IgnoreSubsumingPositions) break; } + if (A) + for (Attribute::AttrKind AK : AKs) + if (getAttrsFromAssumes(AK, Attrs, *A)) + return true; return false; } void IRPosition::getAttrs(ArrayRef AKs, SmallVectorImpl &Attrs, - bool IgnoreSubsumingPositions) const { + bool IgnoreSubsumingPositions, Attributor *A) const { for (const IRPosition &EquivIRP : SubsumingPositionIterator(*this)) { for (Attribute::AttrKind AK : AKs) EquivIRP.getAttrsFromIRAttr(AK, Attrs); @@ -705,6 +709,9 @@ if (IgnoreSubsumingPositions) break; } + if (A) + for (Attribute::AttrKind AK : AKs) + getAttrsFromAssumes(AK, Attrs, *A); } bool IRPosition::getAttrsFromIRAttr(Attribute::AttrKind AK, @@ -724,6 +731,30 @@ return HasAttr; } +bool IRPosition::getAttrsFromAssumes(Attribute::AttrKind AK, + SmallVectorImpl &Attrs, + Attributor &A) const { + assert(getPositionKind() != IRP_INVALID && "Did expect a valid position!"); + Value &AssociatedValue = getAssociatedValue(); + + const Assume2KnowledgeMap &A2K = + A.getInfoCache().getKnowledgeMap().lookup({&AssociatedValue, AK}); + + // Check if we found any potential assume use, if not we don't need to create + // explorer iterators. + if (A2K.empty()) + return false; + + LLVMContext &Ctx = AssociatedValue.getContext(); + unsigned AttrsSize = Attrs.size(); + MustBeExecutedContextExplorer &Explorer = + A.getInfoCache().getMustBeExecutedContextExplorer(); + auto EIt = Explorer.begin(getCtxI()), EEnd = Explorer.end(getCtxI()); + for (auto &It : A2K) + if (Explorer.findInContextOf(It.first, EIt, EEnd)) + Attrs.push_back(Attribute::get(Ctx, AK, It.second.Max)); + return AttrsSize != Attrs.size(); +} void IRPosition::verify() { switch (KindOrArgNo) { @@ -2059,7 +2090,8 @@ /// See AbstractAttribute::initialize(...). void initialize(Attributor &A) override { if (!NullIsDefined && - hasAttr({Attribute::NonNull, Attribute::Dereferenceable})) + hasAttr({Attribute::NonNull, Attribute::Dereferenceable}, + /* IgnoreSubsumingPositions */ false, &A)) indicateOptimisticFixpoint(); else if (isa(getAssociatedValue())) indicatePessimisticFixpoint(); @@ -3656,7 +3688,7 @@ void initialize(Attributor &A) override { SmallVector Attrs; getAttrs({Attribute::Dereferenceable, Attribute::DereferenceableOrNull}, - Attrs); + Attrs, /* IgnoreSubsumingPositions */ false, &A); for (const Attribute &Attr : Attrs) takeKnownDerefBytesMaximum(Attr.getValueAsInt()); @@ -8321,11 +8353,18 @@ "New call site/base instruction type needs to be known int the " "Attributor."); break; + case Instruction::Call: + // Calls are interesting but for `llvm.assume` calls we also fill the + // KnowledgeMap as we find them. + if (IntrinsicInst *Assume = dyn_cast(&I)) { + if (Assume->getIntrinsicID() == Intrinsic::assume) + fillMapFromAssume(*Assume, InfoCache.KnowledgeMap); + } + LLVM_FALLTHROUGH; case Instruction::Load: // The alignment of a pointer is interesting for loads. case Instruction::Store: // The alignment of a pointer is interesting for stores. - case Instruction::Call: case Instruction::CallBr: case Instruction::Invoke: case Instruction::CleanupRet: diff --git a/llvm/test/Transforms/Attributor/dereferenceable-1.ll b/llvm/test/Transforms/Attributor/dereferenceable-1.ll --- a/llvm/test/Transforms/Attributor/dereferenceable-1.ll +++ b/llvm/test/Transforms/Attributor/dereferenceable-1.ll @@ -455,5 +455,64 @@ ret void } +declare void @unknown() +define void @nonnull_assume_pos(i8* %arg1, i8* %arg2, i8* %arg3, i8* %arg4) { +; ATTRIBUTOR-LABEL: define {{[^@]+}}@nonnull_assume_pos +; ATTRIBUTOR-SAME: (i8* nocapture nofree nonnull readnone dereferenceable(101) [[ARG1:%.*]], i8* nocapture nofree readnone dereferenceable_or_null(31) [[ARG2:%.*]], i8* nocapture nofree nonnull readnone [[ARG3:%.*]], i8* nocapture nofree readnone dereferenceable_or_null(42) [[ARG4:%.*]]) +; ATTRIBUTOR-NEXT: call void @unknown() +; ATTRIBUTOR-NEXT: ret void +; + call void @llvm.assume(i1 true) [ "nonnull"(i8* %arg3), "dereferenceable"(i8* %arg1, i64 1), "dereferenceable"(i8* %arg1, i64 2), "dereferenceable"(i8* %arg1, i64 101), "dereferenceable_or_null"(i8* %arg2, i64 31), "dereferenceable_or_null"(i8* %arg4, i64 42)] + call void @unknown() + ret void +} +define void @nonnull_assume_neg(i8* %arg1, i8* %arg2, i8* %arg3) { +; ATTRIBUTOR-LABEL: define {{[^@]+}}@nonnull_assume_neg +; ATTRIBUTOR-SAME: (i8* nocapture nofree readnone [[ARG1:%.*]], i8* nocapture nofree readnone [[ARG2:%.*]], i8* nocapture nofree readnone [[ARG3:%.*]]) +; ATTRIBUTOR-NEXT: call void @unknown() +; ATTRIBUTOR-NEXT: ret void +; + call void @unknown() + call void @llvm.assume(i1 true) ["dereferenceable"(i8* %arg1, i64 101), "dereferenceable"(i8* %arg2, i64 -2), "dereferenceable_or_null"(i8* %arg3, i64 31)] + ret void +} +define void @nonnull_assume_call(i8* %arg1, i8* %arg2, i8* %arg3, i8* %arg4) { +; ATTRIBUTOR-LABEL: define {{[^@]+}}@nonnull_assume_call +; ATTRIBUTOR-SAME: (i8* [[ARG1:%.*]], i8* [[ARG2:%.*]], i8* [[ARG3:%.*]], i8* [[ARG4:%.*]]) +; ATTRIBUTOR-NEXT: call void @unknown() +; ATTRIBUTOR-NEXT: [[P:%.*]] = call nonnull dereferenceable(101) i32* @unkown_ptr() +; ATTRIBUTOR-NEXT: call void @unknown_use32(i32* nonnull dereferenceable(101) [[P]]) +; ATTRIBUTOR-NEXT: call void @unknown_use8(i8* nonnull dereferenceable(42) [[ARG4]]) +; ATTRIBUTOR-NEXT: call void @unknown_use8(i8* nonnull [[ARG3]]) +; ATTRIBUTOR-NEXT: call void @unknown_use8(i8* nonnull dereferenceable(31) [[ARG2]]) +; ATTRIBUTOR-NEXT: call void @unknown_use8(i8* nonnull dereferenceable(2) [[ARG1]]) +; ATTRIBUTOR-NEXT: call void @unknown_use8(i8* nonnull dereferenceable(2) [[ARG1]]) +; ATTRIBUTOR-NEXT: call void @unknown_use8(i8* nonnull dereferenceable(31) [[ARG2]]) +; ATTRIBUTOR-NEXT: call void @unknown_use8(i8* nonnull [[ARG3]]) +; ATTRIBUTOR-NEXT: call void @unknown_use8(i8* nonnull dereferenceable(42) [[ARG4]]) +; ATTRIBUTOR-NEXT: call void @unknown_use32(i32* nonnull dereferenceable(101) [[P]]) +; ATTRIBUTOR-NEXT: call void @unknown() +; ATTRIBUTOR-NEXT: ret void +; + call void @unknown() + %p = call i32* @unkown_ptr() + call void @unknown_use32(i32* %p) + call void @unknown_use8(i8* %arg4) + call void @unknown_use8(i8* %arg3) + call void @unknown_use8(i8* %arg2) + call void @unknown_use8(i8* %arg1) + call void @llvm.assume(i1 true) [ "nonnull"(i8* %arg3), "dereferenceable"(i8* %arg1, i64 1), "dereferenceable"(i8* %arg1, i64 2), "dereferenceable"(i32* %p, i64 101), "dereferenceable_or_null"(i8* %arg2, i64 31), "dereferenceable_or_null"(i8* %arg4, i64 42)] + call void @unknown_use8(i8* %arg1) + call void @unknown_use8(i8* %arg2) + call void @unknown_use8(i8* %arg3) + call void @unknown_use8(i8* %arg4) + call void @unknown_use32(i32* %p) + call void @unknown() + ret void +} +declare void @unknown_use8(i8*) willreturn nounwind +declare void @unknown_use32(i32*) willreturn nounwind +declare void @llvm.assume(i1) + !0 = !{i64 10, i64 100} diff --git a/llvm/test/Transforms/Attributor/nofree.ll b/llvm/test/Transforms/Attributor/nofree.ll --- a/llvm/test/Transforms/Attributor/nofree.ll +++ b/llvm/test/Transforms/Attributor/nofree.ll @@ -247,6 +247,60 @@ ret void } +; UTC_ARGS: --enable + +define void @nonnull_assume_pos(i8* %arg1, i8* %arg2, i8* %arg3, i8* %arg4) { +; ATTRIBUTOR-LABEL: define {{[^@]+}}@nonnull_assume_pos +; ATTRIBUTOR-SAME: (i8* nofree [[ARG1:%.*]], i8* [[ARG2:%.*]], i8* nofree [[ARG3:%.*]], i8* [[ARG4:%.*]]) +; ATTRIBUTOR-NEXT: call void @unknown(i8* nofree [[ARG1]], i8* [[ARG2]], i8* nofree [[ARG3]], i8* [[ARG4]]) +; ATTRIBUTOR-NEXT: ret void +; + call void @llvm.assume(i1 true) ["nofree"(i8* %arg1), "nofree"(i8* %arg3)] + call void @unknown(i8* %arg1, i8* %arg2, i8* %arg3, i8* %arg4) + ret void +} +define void @nonnull_assume_neg(i8* %arg1, i8* %arg2, i8* %arg3, i8* %arg4) { +; ATTRIBUTOR-LABEL: define {{[^@]+}}@nonnull_assume_neg +; ATTRIBUTOR-SAME: (i8* [[ARG1:%.*]], i8* [[ARG2:%.*]], i8* [[ARG3:%.*]], i8* [[ARG4:%.*]]) +; ATTRIBUTOR-NEXT: call void @unknown(i8* [[ARG1]], i8* [[ARG2]], i8* [[ARG3]], i8* [[ARG4]]) +; ATTRIBUTOR-NEXT: ret void +; + call void @unknown(i8* %arg1, i8* %arg2, i8* %arg3, i8* %arg4) + call void @llvm.assume(i1 true) ["nofree"(i8* %arg1), "nofree"(i8* %arg3)] + ret void +} +define void @nonnull_assume_call(i8* %arg1, i8* %arg2, i8* %arg3, i8* %arg4) { +; ATTRIBUTOR-LABEL: define {{[^@]+}}@nonnull_assume_call +; ATTRIBUTOR-SAME: (i8* [[ARG1:%.*]], i8* [[ARG2:%.*]], i8* [[ARG3:%.*]], i8* [[ARG4:%.*]]) +; ATTRIBUTOR-NEXT: call void @unknown(i8* [[ARG1]], i8* [[ARG2]], i8* [[ARG3]], i8* [[ARG4]]) +; ATTRIBUTOR-NEXT: call void @use_i8_ptr(i8* noalias readnone [[ARG1]]) +; ATTRIBUTOR-NEXT: call void @use_i8_ptr(i8* noalias readnone [[ARG2]]) +; ATTRIBUTOR-NEXT: call void @use_i8_ptr(i8* noalias nofree readnone [[ARG3]]) +; ATTRIBUTOR-NEXT: call void @use_i8_ptr(i8* noalias readnone [[ARG4]]) +; ATTRIBUTOR-NEXT: call void @use_i8_ptr_ret(i8* noalias nofree readnone [[ARG1]]) +; ATTRIBUTOR-NEXT: call void @use_i8_ptr_ret(i8* noalias readnone [[ARG2]]) +; ATTRIBUTOR-NEXT: call void @use_i8_ptr_ret(i8* noalias nofree readnone [[ARG3]]) +; ATTRIBUTOR-NEXT: call void @use_i8_ptr_ret(i8* noalias nofree readnone [[ARG4]]) +; ATTRIBUTOR-NEXT: ret void +; + call void @unknown(i8* %arg1, i8* %arg2, i8* %arg3, i8* %arg4) + call void @use_i8_ptr(i8* %arg1) + call void @use_i8_ptr(i8* %arg2) + call void @llvm.assume(i1 true) ["nofree"(i8* %arg1), "nofree"(i8* %arg3)] + call void @use_i8_ptr(i8* %arg3) + call void @use_i8_ptr(i8* %arg4) + call void @use_i8_ptr_ret(i8* %arg1) + call void @use_i8_ptr_ret(i8* %arg2) + call void @llvm.assume(i1 true) ["nofree"(i8* %arg1), "nofree"(i8* %arg4)] + call void @use_i8_ptr_ret(i8* %arg3) + call void @use_i8_ptr_ret(i8* %arg4) + ret void +} +declare void @llvm.assume(i1) +declare void @unknown(i8*, i8*, i8*, i8*) +declare void @use_i8_ptr(i8* nocapture readnone) nounwind +declare void @use_i8_ptr_ret(i8* nocapture readnone) nounwind willreturn + declare noalias i8* @malloc(i64) attributes #0 = { nounwind uwtable noinline } diff --git a/llvm/test/Transforms/Attributor/nonnull.ll b/llvm/test/Transforms/Attributor/nonnull.ll --- a/llvm/test/Transforms/Attributor/nonnull.ll +++ b/llvm/test/Transforms/Attributor/nonnull.ll @@ -167,7 +167,6 @@ tail call void @test13(i8* %nonnullptr, i8* %maybenullptr, i8* %nonnullptr) ret void } -declare void @use_i8_ptr(i8* nofree nocapture readnone) nounwind define internal void @test13(i8* %a, i8* %b, i8* %c) { ; ATTRIBUTOR: define internal void @test13(i8* noalias nocapture nofree nonnull readnone %a, i8* noalias nocapture nofree readnone %b, i8* noalias nocapture nofree readnone %c) call void @use_i8_ptr(i8* %a) @@ -839,5 +838,41 @@ ret i8* %cond } +define void @nonnull_assume_pos(i8* %arg) { +; ATTRIBUTOR-LABEL: define {{[^@]+}}@nonnull_assume_pos +; ATTRIBUTOR-SAME: (i8* nocapture nofree nonnull readnone [[ARG:%.*]]) +; ATTRIBUTOR-NEXT: call void @use_i8_ptr(i8* noalias nocapture nofree nonnull readnone [[ARG]]) +; ATTRIBUTOR-NEXT: [[TMP1:%.*]] = call i8* @unknown() +; ATTRIBUTOR-NEXT: ret void +; + call void @llvm.assume(i1 true) ["nonnull"(i8* %arg)] + call void @use_i8_ptr(i8* %arg) + call i8* @unknown() + ret void +} +define void @nonnull_assume_neg(i8* %arg) { +; ATTRIBUTOR-LABEL: define {{[^@]+}}@nonnull_assume_neg +; ATTRIBUTOR-SAME: (i8* nocapture nofree readnone [[ARG:%.*]]) +; ATTRIBUTOR-NEXT: [[TMP1:%.*]] = call i8* @unknown() +; ATTRIBUTOR-NEXT: call void @use_i8_ptr(i8* noalias nocapture nofree readnone [[ARG]]) +; ATTRIBUTOR-NEXT: call void @use_i8_ptr(i8* noalias nocapture nofree nonnull readnone [[ARG]]) +; ATTRIBUTOR-NEXT: [[TMP2:%.*]] = call i8* @unknown() +; ATTRIBUTOR-NEXT: call void @use_i8_ptr_ret(i8* noalias nocapture nofree nonnull readnone [[ARG]]) +; ATTRIBUTOR-NEXT: call void @use_i8_ptr_ret(i8* noalias nocapture nofree nonnull readnone [[ARG]]) +; ATTRIBUTOR-NEXT: ret void +; + call i8* @unknown() + call void @use_i8_ptr(i8* %arg) + call void @llvm.assume(i1 true) ["nonnull"(i8* %arg)] + call void @use_i8_ptr(i8* %arg) + call i8* @unknown() + call void @use_i8_ptr_ret(i8* %arg) + call void @llvm.assume(i1 true) ["nonnull"(i8* %arg)] + call void @use_i8_ptr_ret(i8* %arg) + ret void +} +declare void @use_i8_ptr(i8* nofree nocapture readnone) nounwind +declare void @use_i8_ptr_ret(i8* nofree nocapture readnone) nounwind willreturn + attributes #0 = { "null-pointer-is-valid"="true" } attributes #1 = { nounwind willreturn}