From 6f3511a01a5227358a334803c264cfce4175ca5d Mon Sep 17 00:00:00 2001 From: Sanjay Patel Date: Wed, 19 Aug 2020 16:32:24 -0400 Subject: [PATCH] [ValueTracking] define/use max recursion depth in header There's a potential motivating case to increase this limit in PR47191: http://bugs.llvm.org/PR47191 But first we should make it less hacky. The limit in InstCombine is directly tied to this value because an increase there can cause asserts in the underlying value tracking calls if not changed together. The usage in VectorUtils is independent, but the comment suggests that we should use the same value unless there's a known reason to diverge. There are similar limits in codegen analysis, but I think we should leave those independent in case we intentionally want the optimization power/cost to be different there. Differential Revision: https://reviews.llvm.org/D86113 --- llvm/include/llvm/Analysis/ValueTracking.h | 2 + llvm/lib/Analysis/ValueTracking.cpp | 56 ++++++++++------------ llvm/lib/Analysis/VectorUtils.cpp | 8 +--- .../InstCombine/InstCombineSimplifyDemanded.cpp | 4 +- 4 files changed, 32 insertions(+), 38 deletions(-) diff --git a/llvm/include/llvm/Analysis/ValueTracking.h b/llvm/include/llvm/Analysis/ValueTracking.h index 0f95ad4..f1b9cc9 100644 --- a/llvm/include/llvm/Analysis/ValueTracking.h +++ b/llvm/include/llvm/Analysis/ValueTracking.h @@ -45,6 +45,8 @@ class StringRef; class TargetLibraryInfo; class Value; +constexpr unsigned MaxAnalysisRecursionDepth = 6; + /// Determine which bits of V are known to be either zero or one and return /// them in the KnownZero/KnownOne bit sets. /// diff --git a/llvm/lib/Analysis/ValueTracking.cpp b/llvm/lib/Analysis/ValueTracking.cpp index fa4f4ed..07c4e57 100644 --- a/llvm/lib/Analysis/ValueTracking.cpp +++ b/llvm/lib/Analysis/ValueTracking.cpp @@ -77,8 +77,6 @@ using namespace llvm; using namespace llvm::PatternMatch; -const unsigned MaxDepth = 6; - // Controls the number of uses of the value searched for possible // dominating comparisons. static cl::opt DomConditionsMaxUses("dom-conditions-max-uses", @@ -117,7 +115,7 @@ struct Query { /// bits in x, etc. Regarding the mutual recursion, computeKnownBits can call /// isKnownNonZero, which calls computeKnownBits and isKnownToBeAPowerOfTwo /// (all of which can call computeKnownBits), and so on. - std::array Excluded; + std::array Excluded; /// If true, it is safe to use metadata during simplification. InstrInfoQuery IIQ; @@ -778,7 +776,7 @@ static void computeKnownBitsFromAssume(const Value *V, KnownBits &Known, } // The remaining tests are all recursive, so bail out if we hit the limit. - if (Depth == MaxDepth) + if (Depth == MaxAnalysisRecursionDepth) continue; ICmpInst *Cmp = dyn_cast(Arg); @@ -1593,7 +1591,7 @@ static void computeKnownBitsFromOperator(const Operator *I, // Otherwise take the unions of the known bit sets of the operands, // taking conservative care to avoid excessive recursion. - if (Depth < MaxDepth - 1 && !Known.Zero && !Known.One) { + if (Depth < MaxAnalysisRecursionDepth - 1 && !Known.Zero && !Known.One) { // Skip if every incoming value references to ourself. if (dyn_cast_or_null(P->hasConstantValue())) break; @@ -1615,7 +1613,7 @@ static void computeKnownBitsFromOperator(const Operator *I, Known2 = KnownBits(BitWidth); // Recurse, but cap the recursion to one level, because we don't // want to waste time spinning around in loops. - computeKnownBits(IncValue, Known2, MaxDepth - 1, RecQ); + computeKnownBits(IncValue, Known2, MaxAnalysisRecursionDepth - 1, RecQ); Known.Zero &= Known2.Zero; Known.One &= Known2.One; // If all bits have been ruled out, there's no need to check @@ -1917,7 +1915,7 @@ void computeKnownBits(const Value *V, const APInt &DemandedElts, } assert(V && "No Value?"); - assert(Depth <= MaxDepth && "Limit Search Depth"); + assert(Depth <= MaxAnalysisRecursionDepth && "Limit Search Depth"); #ifndef NDEBUG Type *Ty = V->getType(); @@ -2004,9 +2002,8 @@ void computeKnownBits(const Value *V, const APInt &DemandedElts, // assumptions. Confirm that we've handled them all. assert(!isa(V) && "Unhandled constant data!"); - // Limit search depth. // All recursive calls that increase depth must come after this. - if (Depth == MaxDepth) + if (Depth == MaxAnalysisRecursionDepth) return; // A weak GlobalAlias is totally unknown. A non-weak GlobalAlias has @@ -2041,7 +2038,7 @@ void computeKnownBits(const Value *V, const APInt &DemandedElts, /// types and vectors of integers. bool isKnownToBeAPowerOfTwo(const Value *V, bool OrZero, unsigned Depth, const Query &Q) { - assert(Depth <= MaxDepth && "Limit Search Depth"); + assert(Depth <= MaxAnalysisRecursionDepth && "Limit Search Depth"); // Attempt to match against constants. if (OrZero && match(V, m_Power2OrZero())) @@ -2060,7 +2057,7 @@ bool isKnownToBeAPowerOfTwo(const Value *V, bool OrZero, unsigned Depth, return true; // The remaining tests are all recursive, so bail out if we hit the limit. - if (Depth++ == MaxDepth) + if (Depth++ == MaxAnalysisRecursionDepth) return false; Value *X = nullptr, *Y = nullptr; @@ -2189,7 +2186,7 @@ static bool isGEPKnownNonNull(const GEPOperator *GEP, unsigned Depth, // to recurse 10k times just because we have 10k GEP operands. We don't // bail completely out because we want to handle constant GEPs regardless // of depth. - if (Depth++ >= MaxDepth) + if (Depth++ >= MaxAnalysisRecursionDepth) continue; if (isKnownNonZero(GTI.getOperand(), Depth, Q)) @@ -2371,7 +2368,7 @@ bool isKnownNonZero(const Value *V, const APInt &DemandedElts, unsigned Depth, return true; // Some of the tests below are recursive, so bail out if we hit the limit. - if (Depth++ >= MaxDepth) + if (Depth++ >= MaxAnalysisRecursionDepth) return false; // Check for pointer simplifications. @@ -2736,7 +2733,7 @@ static unsigned ComputeNumSignBitsImpl(const Value *V, return 1; #ifndef NDEBUG - assert(Depth <= MaxDepth && "Limit Search Depth"); + assert(Depth <= MaxAnalysisRecursionDepth && "Limit Search Depth"); if (auto *FVTy = dyn_cast(Ty)) { assert( @@ -2763,8 +2760,8 @@ static unsigned ComputeNumSignBitsImpl(const Value *V, // Note that ConstantInt is handled by the general computeKnownBits case // below. - if (Depth == MaxDepth) - return 1; // Limit search depth. + if (Depth == MaxAnalysisRecursionDepth) + return 1; if (auto *U = dyn_cast(V)) { switch (Operator::getOpcode(V)) { @@ -3052,7 +3049,7 @@ static unsigned ComputeNumSignBitsImpl(const Value *V, bool llvm::ComputeMultiple(Value *V, unsigned Base, Value *&Multiple, bool LookThroughSExt, unsigned Depth) { assert(V && "No Value?"); - assert(Depth <= MaxDepth && "Limit Search Depth"); + assert(Depth <= MaxAnalysisRecursionDepth && "Limit Search Depth"); assert(V->getType()->isIntegerTy() && "Not integer or pointer type!"); Type *T = V->getType(); @@ -3080,7 +3077,7 @@ bool llvm::ComputeMultiple(Value *V, unsigned Base, Value *&Multiple, return true; } - if (Depth == MaxDepth) return false; // Limit search depth. + if (Depth == MaxAnalysisRecursionDepth) return false; Operator *I = dyn_cast(V); if (!I) return false; @@ -3282,8 +3279,7 @@ bool llvm::CannotBeNegativeZero(const Value *V, const TargetLibraryInfo *TLI, if (auto *CFP = dyn_cast(V)) return !CFP->getValueAPF().isNegZero(); - // Limit search depth. - if (Depth == MaxDepth) + if (Depth == MaxAnalysisRecursionDepth) return false; auto *Op = dyn_cast(V); @@ -3351,8 +3347,8 @@ static bool cannotBeOrderedLessThanZeroImpl(const Value *V, } } - if (Depth == MaxDepth) - return false; // Limit search depth. + if (Depth == MaxAnalysisRecursionDepth) + return false; const Operator *I = dyn_cast(V); if (!I) @@ -3504,7 +3500,7 @@ bool llvm::isKnownNeverInfinity(const Value *V, const TargetLibraryInfo *TLI, if (auto *CFP = dyn_cast(V)) return !CFP->isInfinity(); - if (Depth == MaxDepth) + if (Depth == MaxAnalysisRecursionDepth) return false; if (auto *Inst = dyn_cast(V)) { @@ -3559,7 +3555,7 @@ bool llvm::isKnownNeverNaN(const Value *V, const TargetLibraryInfo *TLI, if (auto *CFP = dyn_cast(V)) return !CFP->isNaN(); - if (Depth == MaxDepth) + if (Depth == MaxAnalysisRecursionDepth) return false; if (auto *Inst = dyn_cast(V)) { @@ -4864,7 +4860,7 @@ bool llvm::isGuaranteedNotToBeUndefOrPoison(const Value *V, const Instruction *CtxI, const DominatorTree *DT, unsigned Depth) { - if (Depth >= MaxDepth) + if (Depth >= MaxAnalysisRecursionDepth) return false; if (const auto *A = dyn_cast(V)) { @@ -5132,7 +5128,7 @@ bool llvm::programUndefinedIfPoison(const Instruction *PoisonI) { BasicBlock::const_iterator Begin = PoisonI->getIterator(), End = BB->end(); unsigned Iter = 0; - while (Iter++ < MaxDepth) { + while (Iter++ < MaxAnalysisRecursionDepth) { for (auto &I : make_range(Begin, End)) { if (&I != PoisonI) { if (mustTriggerUB(&I, YieldsPoison)) @@ -5807,7 +5803,7 @@ static Value *lookThroughCast(CmpInst *CmpI, Value *V1, Value *V2, SelectPatternResult llvm::matchSelectPattern(Value *V, Value *&LHS, Value *&RHS, Instruction::CastOps *CastOp, unsigned Depth) { - if (Depth >= MaxDepth) + if (Depth >= MaxAnalysisRecursionDepth) return {SPF_UNKNOWN, SPNB_NA, false}; SelectInst *SI = dyn_cast(V); @@ -6076,7 +6072,7 @@ isImpliedCondAndOr(const BinaryOperator *LHS, CmpInst::Predicate RHSPred, LHS->getOpcode() == Instruction::Or) && "Expected LHS to be 'and' or 'or'."); - assert(Depth <= MaxDepth && "Hit recursion limit"); + assert(Depth <= MaxAnalysisRecursionDepth && "Hit recursion limit"); // If the result of an 'or' is false, then we know both legs of the 'or' are // false. Similarly, if the result of an 'and' is true, then we know both @@ -6101,7 +6097,7 @@ llvm::isImpliedCondition(const Value *LHS, CmpInst::Predicate RHSPred, const Value *RHSOp0, const Value *RHSOp1, const DataLayout &DL, bool LHSIsTrue, unsigned Depth) { // Bail out when we hit the limit. - if (Depth == MaxDepth) + if (Depth == MaxAnalysisRecursionDepth) return None; // A mismatch occurs when we compare a scalar cmp to a vector cmp, for @@ -6513,7 +6509,7 @@ ConstantRange llvm::computeConstantRange(const Value *V, bool UseInstrInfo, unsigned Depth) { assert(V->getType()->isIntOrIntVectorTy() && "Expected integer instruction"); - if (Depth == MaxDepth) + if (Depth == MaxAnalysisRecursionDepth) return ConstantRange::getFull(V->getType()->getScalarSizeInBits()); const APInt *C; diff --git a/llvm/lib/Analysis/VectorUtils.cpp b/llvm/lib/Analysis/VectorUtils.cpp index cdcbd15..0bc8b72 100644 --- a/llvm/lib/Analysis/VectorUtils.cpp +++ b/llvm/lib/Analysis/VectorUtils.cpp @@ -357,12 +357,8 @@ const llvm::Value *llvm::getSplatValue(const Value *V) { return nullptr; } -// This setting is based on its counterpart in value tracking, but it could be -// adjusted if needed. -const unsigned MaxDepth = 6; - bool llvm::isSplatValue(const Value *V, int Index, unsigned Depth) { - assert(Depth <= MaxDepth && "Limit Search Depth"); + assert(Depth <= MaxAnalysisRecursionDepth && "Limit Search Depth"); if (isa(V->getType())) { if (isa(V)) @@ -389,7 +385,7 @@ bool llvm::isSplatValue(const Value *V, int Index, unsigned Depth) { } // The remaining tests are all recursive, so bail out if we hit the limit. - if (Depth++ == MaxDepth) + if (Depth++ == MaxAnalysisRecursionDepth) return false; // If both operands of a binop are splats, the result is a splat. diff --git a/llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp b/llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp index 72be605..382db79 100644 --- a/llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp +++ b/llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp @@ -110,7 +110,7 @@ Value *InstCombinerImpl::SimplifyDemandedUseBits(Value *V, APInt DemandedMask, unsigned Depth, Instruction *CxtI) { assert(V != nullptr && "Null pointer of Value???"); - assert(Depth <= 6 && "Limit Search Depth"); + assert(Depth <= MaxAnalysisRecursionDepth && "Limit Search Depth"); uint32_t BitWidth = DemandedMask.getBitWidth(); Type *VTy = V->getType(); assert( @@ -127,7 +127,7 @@ Value *InstCombinerImpl::SimplifyDemandedUseBits(Value *V, APInt DemandedMask, if (DemandedMask.isNullValue()) // Not demanding any bits from V. return UndefValue::get(VTy); - if (Depth == 6) // Limit search depth. + if (Depth == MaxAnalysisRecursionDepth) return nullptr; Instruction *I = dyn_cast(V); -- 2.7.4