diff options
author | Florian Hahn <flo@fhahn.com> | 2021-02-15 17:32:11 +0000 |
---|---|---|
committer | Florian Hahn <flo@fhahn.com> | 2021-02-19 20:33:42 +0000 |
commit | ac5cc50e2598878abbeec0422ace51a020ba75c4 (patch) | |
tree | 4ad6b1a4460519cbdf1c59185f0cb6fac2eb6687 | |
parent | c1653b8cc7bd8e7e3168089b6c6dad0aa4b6fdd6 (diff) | |
download | llvm-perf/tmp.tar.gz |
[SCEV] Improve handling of pointer compares involving subtractions.perf/tmp
This patch improves handling of pointer comparisons involving
subtractions, if an offset is known to be positive.
Proof for isKnownPredicateSubIdiom: https://alive2.llvm.org/ce/z/Gfe8mS
Proof for getUDivExpr extension:a https://alive2.llvm.org/ce/z/H_G2Q0
-rw-r--r-- | llvm/include/llvm/Analysis/ScalarEvolution.h | 5 | ||||
-rw-r--r-- | llvm/lib/Analysis/ScalarEvolution.cpp | 48 | ||||
-rw-r--r-- | llvm/lib/Transforms/Scalar/IndVarSimplify.cpp | 4 |
3 files changed, 52 insertions, 5 deletions
diff --git a/llvm/include/llvm/Analysis/ScalarEvolution.h b/llvm/include/llvm/Analysis/ScalarEvolution.h index c35c1db7dfe0..1c9f9b36c94c 100644 --- a/llvm/include/llvm/Analysis/ScalarEvolution.h +++ b/llvm/include/llvm/Analysis/ScalarEvolution.h @@ -1876,6 +1876,11 @@ private: bool isKnownPredicateViaConstantRanges(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS); + /// Test if the given expression is known to satisfy the condition described + /// by Pred by decomposing a subtraction. + bool isKnownPredicateViaSubIdiom(ICmpInst::Predicate Pred, const SCEV *LHS, + const SCEV *RHS); + /// Try to prove the condition described by "LHS Pred RHS" by ruling out /// integer overflow. /// diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp index b8d55e6eb68a..d00bd8a0e2ab 100644 --- a/llvm/lib/Analysis/ScalarEvolution.cpp +++ b/llvm/lib/Analysis/ScalarEvolution.cpp @@ -1833,6 +1833,13 @@ ScalarEvolution::getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth) { } } + if (auto *SM = dyn_cast<SCEVUMaxExpr>(Op)) { + if (isa<SCEVConstant>(SM->getOperand(0)) || + isa<SCEVConstant>(SM->getOperand(1))) + return getUMaxExpr(getZeroExtendExpr(SM->getOperand(0), Ty), + getZeroExtendExpr(SM->getOperand(1), Ty)); + } + // The cast wasn't folded; create an explicit cast node. // Recompute the insert position, as it may have been invalidated. if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; @@ -3104,6 +3111,20 @@ const SCEV *ScalarEvolution::getUDivExpr(const SCEV *LHS, getEffectiveSCEVType(RHS->getType()) && "SCEVUDivExpr operand types don't match!"); + const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(LHS); + const SCEVConstant *C = dyn_cast<SCEVConstant>(RHS); + if (Add && C && Add->getNumOperands() == 2) { + unsigned MultTrailing = C->getAPInt().countTrailingZeros(); + auto *NegOp0 = getNegativeSCEV(Add->getOperand(0)); + if (GetMinTrailingZeros(Add->getOperand(0)) >= MultTrailing && + GetMinTrailingZeros(Add->getOperand(1)) >= MultTrailing && + isKnownPositive(NegOp0) && + isKnownPredicate(CmpInst::ICMP_SGE, Add->getOperand(1), NegOp0)) { + return getMinusSCEV(getUDivExactExpr(Add->getOperand(1), RHS), + getUDivExactExpr(NegOp0, RHS)); + } + } + FoldingSetNodeID ID; ID.AddInteger(scUDivExpr); ID.AddPointer(LHS); @@ -9113,7 +9134,6 @@ ScalarEvolution::howFarToZero(const SCEV *V, const Loop *L, bool ControlsExit, // First compute the unsigned distance from zero in the direction of Step. bool CountDown = StepC->getAPInt().isNegative(); const SCEV *Distance = CountDown ? Start : getNegativeSCEV(Start); - // Handle unitary steps, which cannot wraparound. // 1*N = -Start; -1*N = Start (mod 2^BW), so: // N = Distance (as unsigned) @@ -10095,7 +10115,10 @@ bool ScalarEvolution::isLoopEntryGuardedByCond(const Loop *L, "LHS is not available at Loop Entry"); assert(isAvailableAtLoopEntry(RHS, L) && "RHS is not available at Loop Entry"); - return isBasicBlockEntryGuardedByCond(L->getHeader(), Pred, LHS, RHS); + if (isBasicBlockEntryGuardedByCond(L->getHeader(), Pred, LHS, RHS)) + return true; + return isBasicBlockEntryGuardedByCond( + L->getHeader(), Pred, applyLoopGuards(LHS, L), applyLoopGuards(RHS, L)); } bool ScalarEvolution::isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS, @@ -10934,10 +10957,28 @@ static bool isKnownPredicateExtendIdiom(ICmpInst::Predicate Pred, return false; } +bool ScalarEvolution::isKnownPredicateViaSubIdiom(ICmpInst::Predicate Pred, + const SCEV *LHS, + const SCEV *RHS) { + // Handle X + Y <= Y, if X is negative and abs(X) <= Y. In that case, the + // expression won't wrap in the unsigned sense. + auto *Add = dyn_cast<SCEVAddExpr>(LHS); + if (Add && Pred == CmpInst::ICMP_ULE) { + auto *X = Add->getOperand(0); + auto *Y = Add->getOperand(1); + if (Y == RHS && isKnownNonPositive(X) && isKnownNonNegative(Y) && + isKnownPredicateViaConstantRanges(CmpInst::ICMP_UGE, Y, + getNegativeSCEV(X))) + return true; + } + return false; +} + bool ScalarEvolution::isKnownViaNonRecursiveReasoning(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS) { return isKnownPredicateExtendIdiom(Pred, LHS, RHS) || + isKnownPredicateViaSubIdiom(Pred, LHS, RHS) || isKnownPredicateViaConstantRanges(Pred, LHS, RHS) || IsKnownPredicateViaMinOrMax(*this, Pred, LHS, RHS) || IsKnownPredicateViaAddRecStart(*this, Pred, LHS, RHS) || @@ -11223,12 +11264,13 @@ ScalarEvolution::howManyLessThans(const SCEV *LHS, const SCEV *RHS, return ExitLimit(getCouldNotCompute() /* ExactNotTaken */, MaxBECount, false /*MaxOrZero*/, Predicates); } + // If the backedge is taken at least once, then it will be taken // (End-Start)/Stride times (rounded up to a multiple of Stride), where Start // is the LHS value of the less-than comparison the first time it is evaluated // and End is the RHS. const SCEV *BECountIfBackedgeTaken = - computeBECount(getMinusSCEV(End, Start), Stride, false); + computeBECount(getMinusSCEV(End, Start), Stride, false); // If the loop entry is guarded by the result of the backedge test of the // first loop iteration, then we know the backedge will be taken at least // once and so the backedge taken count is as above. If not then we use the diff --git a/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp b/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp index ae1fff0fa844..643605ff352c 100644 --- a/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp +++ b/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp @@ -1521,8 +1521,8 @@ bool IndVarSimplify::optimizeLoopExits(Loop *L, SCEVExpander &Rewriter) { // Can we prove that some other exit must be taken strictly before this // one? - if (SE->isLoopEntryGuardedByCond(L, CmpInst::ICMP_ULT, - MaxExitCount, ExitCount)) { + if (SE->isLoopEntryGuardedByCond(L, CmpInst::ICMP_ULT, MaxExitCount, + ExitCount)) { foldExit(L, ExitingBB, false, DeadInsts); Changed = true; continue; |