From e5f8a77c1965c762c092e8736d2bf4dd38266754 Mon Sep 17 00:00:00 2001 From: Tyker Date: Fri, 24 Apr 2020 22:34:55 +0200 Subject: [PATCH] [AssumeBundles] Refactor asssume builder Summary: refactor assume bulider for the next patch. the assume builder now generate only one assume per attribute kind and per value they are on. to do this it takes the highest. this is desirable because currently, for all attributes the higest value is the most valuable. Reviewers: jdoerfert Reviewed By: jdoerfert Subscribers: hiraditya, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D78013 --- llvm/include/llvm/Analysis/AssumeBundleQueries.h | 18 +-- llvm/lib/Analysis/AssumeBundleQueries.cpp | 37 +++--- llvm/lib/Transforms/Utils/AssumeBundleBuilder.cpp | 129 ++++++++------------- llvm/test/Transforms/Util/assume-builder.ll | 7 +- .../unittests/Analysis/AssumeBundleQueriesTest.cpp | 77 ++++-------- 5 files changed, 95 insertions(+), 173 deletions(-) diff --git a/llvm/include/llvm/Analysis/AssumeBundleQueries.h b/llvm/include/llvm/Analysis/AssumeBundleQueries.h index 3d4195c..4c01717 100644 --- a/llvm/include/llvm/Analysis/AssumeBundleQueries.h +++ b/llvm/include/llvm/Analysis/AssumeBundleQueries.h @@ -31,14 +31,6 @@ enum AssumeBundleArg { ABA_Argument = 1, }; -/// It is possible to have multiple Value for the argument of an attribute in -/// the same llvm.assume on the same llvm::Value. This is rare but need to be -/// dealt with. -enum class AssumeQuery { - Highest, ///< Take the highest value available. - Lowest, ///< Take the lowest value available. -}; - /// Query the operand bundle of an llvm.assume to find a single attribute of /// the specified kind applied on a specified Value. /// @@ -48,14 +40,12 @@ enum class AssumeQuery { /// Return true iff the queried attribute was found. /// If ArgVal is set. the argument will be stored to ArgVal. bool hasAttributeInAssume(CallInst &AssumeCI, Value *IsOn, StringRef AttrName, - uint64_t *ArgVal = nullptr, - AssumeQuery AQR = AssumeQuery::Highest); + uint64_t *ArgVal = nullptr); inline bool hasAttributeInAssume(CallInst &AssumeCI, Value *IsOn, Attribute::AttrKind Kind, - uint64_t *ArgVal = nullptr, - AssumeQuery AQR = AssumeQuery::Highest) { - return hasAttributeInAssume( - AssumeCI, IsOn, Attribute::getNameFromAttrKind(Kind), ArgVal, AQR); + uint64_t *ArgVal = nullptr) { + return hasAttributeInAssume(AssumeCI, IsOn, + Attribute::getNameFromAttrKind(Kind), ArgVal); } template<> struct DenseMapInfo { diff --git a/llvm/lib/Analysis/AssumeBundleQueries.cpp b/llvm/lib/Analysis/AssumeBundleQueries.cpp index b6b11cb..ec1eb68 100644 --- a/llvm/lib/Analysis/AssumeBundleQueries.cpp +++ b/llvm/lib/Analysis/AssumeBundleQueries.cpp @@ -29,8 +29,7 @@ static Value *getValueFromBundleOpInfo(CallInst &Assume, } bool llvm::hasAttributeInAssume(CallInst &AssumeCI, Value *IsOn, - StringRef AttrName, uint64_t *ArgVal, - AssumeQuery AQR) { + StringRef AttrName, uint64_t *ArgVal) { assert(isa(AssumeCI) && "this function is intended to be used on llvm.assume"); IntrinsicInst &Assume = cast(AssumeCI); @@ -44,27 +43,21 @@ bool llvm::hasAttributeInAssume(CallInst &AssumeCI, Value *IsOn, if (Assume.bundle_op_infos().empty()) return false; - auto Loop = [&](auto &&Range) { - for (auto &BOI : Range) { - if (BOI.Tag->getKey() != AttrName) - continue; - if (IsOn && (BOI.End - BOI.Begin <= ABA_WasOn || - IsOn != getValueFromBundleOpInfo(Assume, BOI, ABA_WasOn))) - continue; - if (ArgVal) { - assert(BOI.End - BOI.Begin > ABA_Argument); - *ArgVal = cast( - getValueFromBundleOpInfo(Assume, BOI, ABA_Argument)) - ->getZExtValue(); - } - return true; + for (auto &BOI : Assume.bundle_op_infos()) { + if (BOI.Tag->getKey() != AttrName) + continue; + if (IsOn && (BOI.End - BOI.Begin <= ABA_WasOn || + IsOn != getValueFromBundleOpInfo(Assume, BOI, ABA_WasOn))) + continue; + if (ArgVal) { + assert(BOI.End - BOI.Begin > ABA_Argument); + *ArgVal = + cast(getValueFromBundleOpInfo(Assume, BOI, ABA_Argument)) + ->getZExtValue(); } - return false; - }; - - if (AQR == AssumeQuery::Lowest) - return Loop(Assume.bundle_op_infos()); - return Loop(reverse(Assume.bundle_op_infos())); + return true; + } + return false; } void llvm::fillMapFromAssume(CallInst &AssumeCI, RetainedKnowledgeMap &Result) { diff --git a/llvm/lib/Transforms/Utils/AssumeBundleBuilder.cpp b/llvm/lib/Transforms/Utils/AssumeBundleBuilder.cpp index 682e69f..ab82950 100644 --- a/llvm/lib/Transforms/Utils/AssumeBundleBuilder.cpp +++ b/llvm/lib/Transforms/Utils/AssumeBundleBuilder.cpp @@ -30,43 +30,6 @@ cl::opt EnableKnowledgeRetention( namespace { -struct AssumedKnowledge { - const char *Name; - Value *Argument; - enum { - None, - Empty, - Tombstone, - }; - /// Contain the argument and a flag if needed. - llvm::PointerIntPair WasOn; -}; - -} // namespace - -namespace llvm { - -template <> struct DenseMapInfo { - static AssumedKnowledge getEmptyKey() { - return {nullptr, nullptr, {nullptr, AssumedKnowledge::Empty}}; - } - static AssumedKnowledge getTombstoneKey() { - return {nullptr, nullptr, {nullptr, AssumedKnowledge::Tombstone}}; - } - static unsigned getHashValue(const AssumedKnowledge &AK) { - return hash_combine(AK.Name, AK.Argument, AK.WasOn.getPointer()); - } - static bool isEqual(const AssumedKnowledge &LHS, - const AssumedKnowledge &RHS) { - return LHS.WasOn == RHS.WasOn && LHS.Name == RHS.Name && - LHS.Argument == RHS.Argument; - } -}; - -} // namespace llvm - -namespace { - /// Deterministically compare OperandBundleDef. /// The ordering is: /// - by the attribute's name aka operand bundle tag, (doesn't change) @@ -108,26 +71,37 @@ bool isUsefullToPreserve(Attribute::AttrKind Kind) { struct AssumeBuilderState { Module *M; - SmallDenseSet AssumedKnowledgeSet; + using MapKey = std::pair; + SmallDenseMap AssumedKnowledgeMap; + Instruction *InsertBeforeInstruction = nullptr; AssumeBuilderState(Module *M) : M(M) {} + void addKnowledge(RetainedKnowledge RK) { + MapKey Key{RK.WasOn, RK.AttrKind}; + auto Lookup = AssumedKnowledgeMap.find(Key); + if (Lookup == AssumedKnowledgeMap.end()) { + AssumedKnowledgeMap[Key] = RK.ArgValue; + return; + } + assert(((Lookup->second == 0 && RK.ArgValue == 0) || + (Lookup->second != 0 && RK.ArgValue != 0)) && + "inconsistent argument value"); + + /// This is only desirable because for all attributes taking an argument + /// higher is better. + Lookup->second = std::max(Lookup->second, RK.ArgValue); + } + void addAttribute(Attribute Attr, Value *WasOn) { - if (!ShouldPreserveAllAttributes && - (Attr.isTypeAttribute() || Attr.isStringAttribute() || + if (Attr.isTypeAttribute() || Attr.isStringAttribute() || + (!ShouldPreserveAllAttributes && !isUsefullToPreserve(Attr.getKindAsEnum()))) return; - StringRef Name; - Value *AttrArg = nullptr; - if (Attr.isStringAttribute()) - Name = Attr.getKindAsString(); - else - Name = Attribute::getNameFromAttrKind(Attr.getKindAsEnum()); + unsigned AttrArg = 0; if (Attr.isIntAttribute()) - AttrArg = ConstantInt::get(Type::getInt64Ty(M->getContext()), - Attr.getValueAsInt()); - AssumedKnowledgeSet.insert( - {Name.data(), AttrArg, {WasOn, AssumedKnowledge::None}}); + AttrArg = Attr.getValueAsInt(); + addKnowledge({Attr.getKindAsEnum(), AttrArg, WasOn}); } void addCall(const CallBase *Call) { @@ -145,57 +119,45 @@ struct AssumeBuilderState { } IntrinsicInst *build() { - if (AssumedKnowledgeSet.empty()) + if (AssumedKnowledgeMap.empty()) return nullptr; Function *FnAssume = Intrinsic::getDeclaration(M, Intrinsic::assume); LLVMContext &C = M->getContext(); SmallVector OpBundle; - for (const AssumedKnowledge &Elem : AssumedKnowledgeSet) { + for (auto &MapElem : AssumedKnowledgeMap) { SmallVector Args; - assert(Attribute::getAttrKindFromName(Elem.Name) == - Attribute::AttrKind::None || - static_cast(Elem.Argument) == - Attribute::doesAttrKindHaveArgument( - Attribute::getAttrKindFromName(Elem.Name))); - if (Elem.WasOn.getPointer()) - Args.push_back(Elem.WasOn.getPointer()); - if (Elem.Argument) - Args.push_back(Elem.Argument); - OpBundle.push_back(OperandBundleDefT(Elem.Name, Args)); + if (MapElem.first.first) + Args.push_back(MapElem.first.first); + + /// This is only valid because for all attribute that currently exist a + /// value of 0 is useless. and should not be preserved. + if (MapElem.second) + Args.push_back(ConstantInt::get(Type::getInt64Ty(M->getContext()), + MapElem.second)); + OpBundle.push_back(OperandBundleDefT( + std::string(Attribute::getNameFromAttrKind(MapElem.first.second)), + Args)); } llvm::sort(OpBundle, isLowerOpBundle); return cast(CallInst::Create( FnAssume, ArrayRef({ConstantInt::getTrue(C)}), OpBundle)); } - void addAttr(Attribute::AttrKind Kind, Value *Val, unsigned Argument = 0) { - AssumedKnowledge AK; - AK.Name = Attribute::getNameFromAttrKind(Kind).data(); - AK.WasOn.setPointer(Val); - if (Attribute::doesAttrKindHaveArgument(Kind)) { - AK.Argument = - ConstantInt::get(Type::getInt64Ty(M->getContext()), Argument); - } else { - AK.Argument = nullptr; - assert(Argument == 0 && "there should be no argument"); - } - AssumedKnowledgeSet.insert(AK); - }; - void addAccessedPtr(Instruction *MemInst, Value *Pointer, Type *AccType, MaybeAlign MA) { - uint64_t DerefSize = MemInst->getModule() + unsigned DerefSize = MemInst->getModule() ->getDataLayout() .getTypeStoreSize(AccType) .getKnownMinSize(); if (DerefSize != 0) { - addAttr(Attribute::Dereferenceable, Pointer, DerefSize); + addKnowledge({Attribute::Dereferenceable, DerefSize, Pointer}); if (!NullPointerIsDefined(MemInst->getFunction(), Pointer->getType()->getPointerAddressSpace())) - addAttr(Attribute::NonNull, Pointer); + addKnowledge({Attribute::NonNull, 0u, Pointer}); } if (MA.valueOrOne() > 1) - addAttr(Attribute::Alignment, Pointer, MA.valueOrOne().value()); + addKnowledge( + {Attribute::Alignment, unsigned(MA.valueOrOne().value()), Pointer}); } void addInstruction(Instruction *I) { @@ -224,7 +186,12 @@ IntrinsicInst *llvm::buildAssumeFromInst(Instruction *I) { } void llvm::salvageKnowledge(Instruction *I, AssumptionCache *AC) { - if (IntrinsicInst *Intr = buildAssumeFromInst(I)) { + if (!EnableKnowledgeRetention) + return; + AssumeBuilderState Builder(I->getModule()); + Builder.InsertBeforeInstruction = I; + Builder.addInstruction(I); + if (IntrinsicInst *Intr = Builder.build()) { Intr->insertBefore(I); if (AC) AC->registerAssumption(Intr); diff --git a/llvm/test/Transforms/Util/assume-builder.ll b/llvm/test/Transforms/Util/assume-builder.ll index b39f5de..8e6d2ec 100644 --- a/llvm/test/Transforms/Util/assume-builder.ll +++ b/llvm/test/Transforms/Util/assume-builder.ll @@ -22,7 +22,7 @@ define void @test(i32* %P, i32* %P1, i32* %P2, i32* %P3) { ; BASIC-NEXT: call void @func_cold(i32* dereferenceable(12) [[P1]]) ; BASIC-NEXT: call void @func(i32* [[P1]], i32* [[P]]) ; BASIC-NEXT: call void @func_strbool(i32* [[P1]]) -; BASIC-NEXT: call void @llvm.assume(i1 true) [ "dereferenceable"(i32* [[P]], i64 8), "dereferenceable"(i32* [[P]], i64 16) ] +; BASIC-NEXT: call void @llvm.assume(i1 true) [ "dereferenceable"(i32* [[P]], i64 16) ] ; BASIC-NEXT: call void @func(i32* dereferenceable(16) [[P]], i32* dereferenceable(8) [[P]]) ; BASIC-NEXT: call void @llvm.assume(i1 true) [ "align"(i32* [[P1]], i64 8) ] ; BASIC-NEXT: call void @func_many(i32* align 8 [[P1]]) @@ -42,11 +42,10 @@ define void @test(i32* %P, i32* %P1, i32* %P2, i32* %P3) { ; ALL-NEXT: call void @llvm.assume(i1 true) [ "cold"(), "dereferenceable"(i32* [[P1]], i64 12) ] ; ALL-NEXT: call void @func_cold(i32* dereferenceable(12) [[P1]]) ; ALL-NEXT: call void @func(i32* [[P1]], i32* [[P]]) -; ALL-NEXT: call void @llvm.assume(i1 true) [ "no-jump-tables"() ] ; ALL-NEXT: call void @func_strbool(i32* [[P1]]) -; ALL-NEXT: call void @llvm.assume(i1 true) [ "dereferenceable"(i32* [[P]], i64 8), "dereferenceable"(i32* [[P]], i64 16) ] +; ALL-NEXT: call void @llvm.assume(i1 true) [ "dereferenceable"(i32* [[P]], i64 16) ] ; ALL-NEXT: call void @func(i32* dereferenceable(16) [[P]], i32* dereferenceable(8) [[P]]) -; ALL-NEXT: call void @llvm.assume(i1 true) [ "align"(i32* [[P1]], i64 8), "less-precise-fpmad"(), "no-jump-tables"(), "norecurse"(), "nounwind"(), "willreturn"() ] +; ALL-NEXT: call void @llvm.assume(i1 true) [ "align"(i32* [[P1]], i64 8), "norecurse"(), "nounwind"(), "willreturn"() ] ; ALL-NEXT: call void @func_many(i32* align 8 [[P1]]) ; ALL-NEXT: call void @llvm.assume(i1 true) [ "align"(i32* [[P2:%.*]], i64 8), "nonnull"(i32* [[P3:%.*]]), "nounwind"() ] ; ALL-NEXT: call void @func_argattr(i32* [[P2]], i32* [[P3]]) diff --git a/llvm/unittests/Analysis/AssumeBundleQueriesTest.cpp b/llvm/unittests/Analysis/AssumeBundleQueriesTest.cpp index 2260d03..d35a77f 100644 --- a/llvm/unittests/Analysis/AssumeBundleQueriesTest.cpp +++ b/llvm/unittests/Analysis/AssumeBundleQueriesTest.cpp @@ -58,25 +58,11 @@ bool hasMatchesExactlyAttributes(IntrinsicInst *Assume, Value *WasOn, } bool hasTheRightValue(IntrinsicInst *Assume, Value *WasOn, - Attribute::AttrKind Kind, unsigned Value, bool Both, - AssumeQuery AQ = AssumeQuery::Highest) { - if (!Both) { - uint64_t ArgVal = 0; - if (!hasAttributeInAssume(*Assume, WasOn, Kind, &ArgVal, AQ)) - return false; - if (ArgVal != Value) - return false; - return true; - } - uint64_t ArgValLow = 0; - uint64_t ArgValHigh = 0; - bool ResultLow = hasAttributeInAssume(*Assume, WasOn, Kind, &ArgValLow, - AssumeQuery::Lowest); - bool ResultHigh = hasAttributeInAssume(*Assume, WasOn, Kind, &ArgValHigh, - AssumeQuery::Highest); - if (ResultLow != ResultHigh || ResultHigh == false) + Attribute::AttrKind Kind, unsigned Value) { + uint64_t ArgVal = 0; + if (!hasAttributeInAssume(*Assume, WasOn, Kind, &ArgVal)) return false; - if (ArgValLow != Value || ArgValLow != ArgValHigh) + if (ArgVal != Value) return false; return true; } @@ -105,11 +91,11 @@ TEST(AssumeQueryAPI, hasAttributeInAssume) { ASSERT_TRUE(hasMatchesExactlyAttributes(Assume, I->getOperand(1), "(align)")); ASSERT_TRUE(hasTheRightValue(Assume, I->getOperand(0), - Attribute::AttrKind::Dereferenceable, 16, true)); + Attribute::AttrKind::Dereferenceable, 16)); ASSERT_TRUE(hasTheRightValue(Assume, I->getOperand(0), - Attribute::AttrKind::Alignment, 4, true)); + Attribute::AttrKind::Alignment, 4)); ASSERT_TRUE(hasTheRightValue(Assume, I->getOperand(0), - Attribute::AttrKind::Alignment, 4, true)); + Attribute::AttrKind::Alignment, 4)); })); Tests.push_back(std::make_pair( "call void @func1(i32* nonnull align 32 dereferenceable(48) %P, i32* " @@ -129,23 +115,11 @@ TEST(AssumeQueryAPI, hasAttributeInAssume) { ASSERT_TRUE(hasMatchesExactlyAttributes(Assume, I->getOperand(3), "(nonnull|align|dereferenceable)")); ASSERT_TRUE(hasTheRightValue(Assume, I->getOperand(0), - Attribute::AttrKind::Dereferenceable, 48, false, - AssumeQuery::Highest)); - ASSERT_TRUE(hasTheRightValue(Assume, I->getOperand(0), - Attribute::AttrKind::Alignment, 64, false, - AssumeQuery::Highest)); - ASSERT_TRUE(hasTheRightValue(Assume, I->getOperand(1), - Attribute::AttrKind::Alignment, 64, false, - AssumeQuery::Highest)); - ASSERT_TRUE(hasTheRightValue(Assume, I->getOperand(0), - Attribute::AttrKind::Dereferenceable, 4, false, - AssumeQuery::Lowest)); + Attribute::AttrKind::Dereferenceable, 48)); ASSERT_TRUE(hasTheRightValue(Assume, I->getOperand(0), - Attribute::AttrKind::Alignment, 8, false, - AssumeQuery::Lowest)); + Attribute::AttrKind::Alignment, 64)); ASSERT_TRUE(hasTheRightValue(Assume, I->getOperand(1), - Attribute::AttrKind::Alignment, 8, false, - AssumeQuery::Lowest)); + Attribute::AttrKind::Alignment, 64)); })); Tests.push_back(std::make_pair( "call void @func_many(i32* align 8 %P1) cold\n", [](Instruction *I) { @@ -153,9 +127,7 @@ TEST(AssumeQueryAPI, hasAttributeInAssume) { IntrinsicInst *Assume = buildAssumeFromInst(I); Assume->insertBefore(I); ASSERT_TRUE(hasMatchesExactlyAttributes( - Assume, nullptr, - "(align|no-jump-tables|less-precise-fpmad|" - "nounwind|norecurse|willreturn|cold)")); + Assume, nullptr, "(align|nounwind|norecurse|willreturn|cold)")); ShouldPreserveAllAttributes.setValue(false); })); Tests.push_back( @@ -182,21 +154,21 @@ TEST(AssumeQueryAPI, hasAttributeInAssume) { ASSERT_TRUE(hasMatchesExactlyAttributes(Assume, I->getOperand(3), "(nonnull|align|dereferenceable)")); ASSERT_TRUE(hasTheRightValue(Assume, I->getOperand(0), - Attribute::AttrKind::Alignment, 32, true)); + Attribute::AttrKind::Alignment, 32)); ASSERT_TRUE(hasTheRightValue(Assume, I->getOperand(0), - Attribute::AttrKind::Dereferenceable, 48, true)); + Attribute::AttrKind::Dereferenceable, 48)); ASSERT_TRUE(hasTheRightValue(Assume, I->getOperand(1), - Attribute::AttrKind::Dereferenceable, 28, true)); + Attribute::AttrKind::Dereferenceable, 28)); ASSERT_TRUE(hasTheRightValue(Assume, I->getOperand(1), - Attribute::AttrKind::Alignment, 8, true)); + Attribute::AttrKind::Alignment, 8)); ASSERT_TRUE(hasTheRightValue(Assume, I->getOperand(2), - Attribute::AttrKind::Alignment, 64, true)); + Attribute::AttrKind::Alignment, 64)); ASSERT_TRUE(hasTheRightValue(Assume, I->getOperand(2), - Attribute::AttrKind::Dereferenceable, 4, true)); + Attribute::AttrKind::Dereferenceable, 4)); ASSERT_TRUE(hasTheRightValue(Assume, I->getOperand(3), - Attribute::AttrKind::Alignment, 16, true)); + Attribute::AttrKind::Alignment, 16)); ASSERT_TRUE(hasTheRightValue(Assume, I->getOperand(3), - Attribute::AttrKind::Dereferenceable, 12, true)); + Attribute::AttrKind::Dereferenceable, 12)); })); Tests.push_back(std::make_pair( @@ -221,9 +193,9 @@ TEST(AssumeQueryAPI, hasAttributeInAssume) { ASSERT_TRUE(hasMatchesExactlyAttributes(Assume, I->getOperand(3), "")); ASSERT_TRUE(hasTheRightValue(Assume, I->getOperand(0), - Attribute::AttrKind::Alignment, 32, true)); + Attribute::AttrKind::Alignment, 32)); ASSERT_TRUE(hasTheRightValue(Assume, I->getOperand(0), - Attribute::AttrKind::Dereferenceable, 48, true)); + Attribute::AttrKind::Dereferenceable, 48)); })); Tests.push_back(std::make_pair( "call void @func(i32* nonnull align 4 dereferenceable(16) %P, i32* align " @@ -323,9 +295,10 @@ TEST(AssumeQueryAPI, fillMapFromAssume) { ASSERT_TRUE(FindExactlyAttributes(Map, I->getOperand(3), "(nonnull|align|dereferenceable)")); ASSERT_TRUE(MapHasRightValue( - Map, Assume, {I->getOperand(0), Attribute::Dereferenceable}, {4, 48})); - ASSERT_TRUE(MapHasRightValue(Map, Assume, {I->getOperand(0), Attribute::Alignment}, - {8, 64})); + Map, Assume, {I->getOperand(0), Attribute::Dereferenceable}, + {48, 48})); + ASSERT_TRUE(MapHasRightValue( + Map, Assume, {I->getOperand(0), Attribute::Alignment}, {64, 64})); })); Tests.push_back(std::make_pair( "call void @func_many(i32* align 8 %P1) cold\n", [](Instruction *I) { -- 2.7.4