From cb9f78e1c3951337de4ba24902eced2c72184319 Mon Sep 17 00:00:00 2001 From: Hal Finkel Date: Thu, 15 Dec 2016 02:53:42 +0000 Subject: Make processing @llvm.assume more efficient by using operand bundles There was an efficiency problem with how we processed @llvm.assume in ValueTracking (and other places). The AssumptionCache tracked all of the assumptions in a given function. In order to find assumptions relevant to computing known bits, etc. we searched every assumption in the function. For ValueTracking, that means that we did O(#assumes * #values) work in InstCombine and other passes (with a constant factor that can be quite large because we'd repeat this search at every level of recursion of the analysis). Several of us discussed this situation at the last developers' meeting, and this implements the discussed solution: Make the values that an assume might affect operands of the assume itself. To avoid exposing this detail to frontends and passes that need not worry about it, I've used the new operand-bundle feature to add these extra call "operands" in a way that does not affect the intrinsic's signature. I think this solution is relatively clean. InstCombine adds these extra operands based on what ValueTracking, LVI, etc. will need and then those passes need only search the users of the values under consideration. This should fix the computational-complexity problem. At this point, no passes depend on the AssumptionCache, and so I'll remove that as a follow-up change. Differential Revision: https://reviews.llvm.org/D27259 llvm-svn: 289755 --- .../Transforms/InstCombine/InstCombineCalls.cpp | 72 ++++++++++++++++++++++ .../Transforms/Scalar/AlignmentFromAssumptions.cpp | 9 ++- 2 files changed, 78 insertions(+), 3 deletions(-) (limited to 'llvm/lib/Transforms') diff --git a/llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp b/llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp index 2e50b2f3e06..958bd1110f3 100644 --- a/llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp +++ b/llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp @@ -2518,6 +2518,78 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) { if (KnownOne.isAllOnesValue()) return eraseInstFromFunction(*II); + // For assumptions, add to the associated operand bundle the values to which + // the assumption might apply. + // Note: This code must be kept in-sync with the code in + // computeKnownBitsFromAssume in ValueTracking. + SmallVector Affected; + auto AddAffected = [&Affected](Value *V) { + if (isa(V)) { + Affected.push_back(V); + } else if (auto *I = dyn_cast(V)) { + Affected.push_back(I); + + if (I->getOpcode() == Instruction::BitCast || + I->getOpcode() == Instruction::PtrToInt) { + V = I->getOperand(0); + if (isa(V) || isa(V)) + Affected.push_back(V); + } + } + }; + + CmpInst::Predicate Pred; + if (match(IIOperand, m_ICmp(Pred, m_Value(A), m_Value(B)))) { + AddAffected(A); + AddAffected(B); + + if (Pred == ICmpInst::ICMP_EQ) { + // For equality comparisons, we handle the case of bit inversion. + auto AddAffectedFromEq = [&AddAffected](Value *V) { + Value *A; + if (match(V, m_Not(m_Value(A)))) { + AddAffected(A); + V = A; + } + + Value *B; + ConstantInt *C; + if (match(V, + m_CombineOr(m_And(m_Value(A), m_Value(B)), + m_CombineOr(m_Or(m_Value(A), m_Value(B)), + m_Xor(m_Value(A), m_Value(B)))))) { + AddAffected(A); + AddAffected(B); + } else if (match(V, + m_CombineOr(m_Shl(m_Value(A), m_ConstantInt(C)), + m_CombineOr(m_LShr(m_Value(A), m_ConstantInt(C)), + m_AShr(m_Value(A), + m_ConstantInt(C)))))) { + AddAffected(A); + } + }; + + AddAffectedFromEq(A); + AddAffectedFromEq(B); + } + } + + // If the list of affected values is the same as the existing list then + // there's nothing more to do here. + if (!Affected.empty()) + if (auto OB = CI.getOperandBundle("affected")) + if (Affected.size() == OB.getValue().Inputs.size() && + std::equal(Affected.begin(), Affected.end(), + OB.getValue().Inputs.begin())) + Affected.clear(); + + if (!Affected.empty()) { + Builder->CreateCall(AssumeIntrinsic, IIOperand, + OperandBundleDef("affected", Affected), + II->getName()); + return eraseInstFromFunction(*II); + } + break; } case Intrinsic::experimental_gc_relocate: { diff --git a/llvm/lib/Transforms/Scalar/AlignmentFromAssumptions.cpp b/llvm/lib/Transforms/Scalar/AlignmentFromAssumptions.cpp index c1df3173c0f..82cfbd16ca3 100644 --- a/llvm/lib/Transforms/Scalar/AlignmentFromAssumptions.cpp +++ b/llvm/lib/Transforms/Scalar/AlignmentFromAssumptions.cpp @@ -425,9 +425,12 @@ bool AlignmentFromAssumptionsPass::runImpl(Function &F, AssumptionCache &AC, NewSrcAlignments.clear(); bool Changed = false; - for (auto &AssumeVH : AC.assumptions()) - if (AssumeVH) - Changed |= processAssumption(cast(AssumeVH)); + + for (auto &B : F) + for (auto &I : B) + if (auto *II = dyn_cast(&I)) + if (II->getIntrinsicID() == Intrinsic::assume) + Changed |= processAssumption(II); return Changed; } -- cgit v1.2.3