diff --git a/llvm/include/llvm/Analysis/AssumeBundleQueries.h b/llvm/include/llvm/Analysis/AssumeBundleQueries.h --- a/llvm/include/llvm/Analysis/AssumeBundleQueries.h +++ b/llvm/include/llvm/Analysis/AssumeBundleQueries.h @@ -31,14 +31,6 @@ 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 @@ /// 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 --- a/llvm/lib/Analysis/AssumeBundleQueries.cpp +++ b/llvm/lib/Analysis/AssumeBundleQueries.cpp @@ -29,8 +29,7 @@ } 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 @@ 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 --- a/llvm/lib/Transforms/Utils/AssumeBundleBuilder.cpp +++ b/llvm/lib/Transforms/Utils/AssumeBundleBuilder.cpp @@ -30,43 +30,6 @@ 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 @@ 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 @@ } 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 @@ } 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 --- a/llvm/test/Transforms/Util/assume-builder.ll +++ b/llvm/test/Transforms/Util/assume-builder.ll @@ -22,7 +22,7 @@ ; 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 @@ ; 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 --- a/llvm/unittests/Analysis/AssumeBundleQueriesTest.cpp +++ b/llvm/unittests/Analysis/AssumeBundleQueriesTest.cpp @@ -58,25 +58,11 @@ } 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 @@ 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 @@ 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 @@ 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 @@ 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 @@ 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 @@ 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) {