From 34fd05d8b58f3d4b20793a5656db8557bab3ecc2 Mon Sep 17 00:00:00 2001 From: Sanjoy Das Date: Fri, 25 Sep 2015 21:16:50 +0000 Subject: [PATCH] Revert two SCEV changes that caused test failures in clang. r248606: "[SCEV] Exploit A < B => (A+K) < (B+K) when possible" r248608: "[SCEV] Teach isLoopBackedgeGuardedByCond to exploit trip counts." git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@248614 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/ScalarEvolution.h | 11 -- lib/Analysis/ScalarEvolution.cpp | 159 --------------- test/Analysis/ScalarEvolution/zext-wrap.ll | 2 +- .../IndVarSimplify/eliminate-comparison.ll | 186 ------------------ 4 files changed, 1 insertion(+), 357 deletions(-) diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h index 62d66c246d7..72975d423a7 100644 --- a/include/llvm/Analysis/ScalarEvolution.h +++ b/include/llvm/Analysis/ScalarEvolution.h @@ -536,17 +536,6 @@ namespace llvm { const SCEV *FoundLHS, const SCEV *FoundRHS); - /// Test whether the condition described by Pred, LHS, and RHS is true - /// whenever the condition described by Pred, FoundLHS, and FoundRHS is - /// true. - /// - /// This routine tries to rule out certain kinds of integer overflow, and - /// then tries to reason about arithmetic properties of the predicates. - bool isImpliedCondOperandsViaNoOverflow(ICmpInst::Predicate Pred, - const SCEV *LHS, const SCEV *RHS, - const SCEV *FoundLHS, - const SCEV *FoundRHS); - /// If we know that the specified Phi is in the header of its containing /// loop, we know the loop executes a constant number of times, and the PHI /// node is just a recurrence involving constants, fold it. diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp index 32d3d36c739..c8cd4ec8ae1 100644 --- a/lib/Analysis/ScalarEvolution.cpp +++ b/lib/Analysis/ScalarEvolution.cpp @@ -6994,22 +6994,6 @@ ScalarEvolution::isLoopBackedgeGuardedByCond(const Loop *L, SaveAndRestore ClearOnExit(WalkingBEDominatingConds, true); - // See if we can exploit a trip count to prove the predicate. - const auto &BETakenInfo = getBackedgeTakenInfo(L); - const SCEV *LatchBECount = BETakenInfo.getExact(Latch, this); - if (LatchBECount != getCouldNotCompute()) { - // We know that Latch branches back to the loop header exactly - // LatchBECount times. This means the backdege condition at Latch is - // equivalent to "{0,+,1} u< LatchBECount". - Type *Ty = LatchBECount->getType(); - auto NoWrapFlags = SCEV::NoWrapFlags(SCEV::FlagNUW | SCEV::FlagNW); - const SCEV *LoopCounter = - getAddRecExpr(getZero(Ty), getOne(Ty), L, NoWrapFlags); - if (isImpliedCond(Pred, LHS, RHS, ICmpInst::ICMP_ULT, LoopCounter, - LatchBECount)) - return true; - } - // Check conditions due to any @llvm.assume intrinsics. for (auto &AssumeVH : AC.assumptions()) { if (!AssumeVH) @@ -7304,146 +7288,6 @@ bool ScalarEvolution::isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS, return false; } -// Return true if More == (Less + C), where C is a constant. -static bool IsConstDiff(ScalarEvolution &SE, const SCEV *Less, const SCEV *More, - APInt &C) { - // We avoid subtracting expressions here because this function is usually - // fairly deep in the call stack (i.e. is called many times). - - auto SplitBinaryAdd = [](const SCEV *Expr, const SCEV *&L, const SCEV *&R) { - const auto *AE = dyn_cast(Expr); - if (!AE || AE->getNumOperands() != 2) - return false; - - L = AE->getOperand(0); - R = AE->getOperand(1); - return true; - }; - - if (isa(Less) && isa(More)) { - const auto *LAR = cast(Less); - const auto *MAR = cast(More); - - if (LAR->getLoop() != MAR->getLoop()) - return false; - - // We look at affine expressions only; not for correctness but to keep - // getStepRecurrence cheap. - if (!LAR->isAffine() || !MAR->isAffine()) - return false; - - if (LAR->getStepRecurrence(SE) != MAR->getStepRecurrence(SE)) - return false; - - Less = LAR->getStart(); - More = MAR->getStart(); - - // fall through - } - - if (isa(Less) && isa(More)) { - const auto &M = cast(More)->getValue()->getValue(); - const auto &L = cast(Less)->getValue()->getValue(); - C = M - L; - return true; - } - - const SCEV *L, *R; - if (SplitBinaryAdd(Less, L, R)) - if (const auto *LC = dyn_cast(L)) - if (R == More) { - C = -(LC->getValue()->getValue()); - return true; - } - - if (SplitBinaryAdd(More, L, R)) - if (const auto *LC = dyn_cast(L)) - if (R == Less) { - C = LC->getValue()->getValue(); - return true; - } - - return false; -} - -bool ScalarEvolution::isImpliedCondOperandsViaNoOverflow( - ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, - const SCEV *FoundLHS, const SCEV *FoundRHS) { - if (Pred != CmpInst::ICMP_SLT && Pred != CmpInst::ICMP_ULT) - return false; - - const auto *AddRecLHS = dyn_cast(LHS); - if (!AddRecLHS) - return false; - - const auto *AddRecFoundLHS = dyn_cast(FoundLHS); - if (!AddRecFoundLHS) - return false; - - // We'd like to let SCEV reason about control dependencies, so we constrain - // both the inequalities to be about add recurrences on the same loop. This - // way we can use isLoopEntryGuardedByCond later. - - const Loop *L = AddRecFoundLHS->getLoop(); - if (L != AddRecLHS->getLoop()) - return false; - - // FoundLHS u< FoundRHS u< -C => (FoundLHS + C) u< (FoundRHS + C) ... (1) - // - // FoundLHS s< FoundRHS s< INT_MIN - C => (FoundLHS + C) s< (FoundRHS + C) - // ... (2) - // - // Informal proof for (2), assuming (1) [*]: - // - // We'll also assume (A s< B) <=> ((A + INT_MIN) u< (B + INT_MIN)) ... (3)[**] - // - // Then - // - // FoundLHS s< FoundRHS s< INT_MIN - C - // <=> (FoundLHS + INT_MIN) u< (FoundRHS + INT_MIN) u< -C [ using (3) ] - // <=> (FoundLHS + INT_MIN + C) u< (FoundRHS + INT_MIN + C) [ using (1) ] - // <=> (FoundLHS + INT_MIN + C + INT_MIN) s< - // (FoundRHS + INT_MIN + C + INT_MIN) [ using (3) ] - // <=> FoundLHS + C s< FoundRHS + C - // - // [*]: (1) can be proved by ruling out overflow. - // - // [**]: This can be proved by analyzing all the four possibilities: - // (A s< 0, B s< 0), (A s< 0, B s>= 0), (A s>= 0, B s< 0) and - // (A s>= 0, B s>= 0). - // - // Note: - // Despite (2), "FoundRHS s< INT_MIN - C" does not mean that "FoundRHS + C" - // will not sign underflow. For instance, say FoundLHS = (i8 -128), FoundRHS - // = (i8 -127) and C = (i8 -100). Then INT_MIN - C = (i8 -28), and FoundRHS - // s< (INT_MIN - C). Lack of sign overflow / underflow in "FoundRHS + C" is - // neither necessary nor sufficient to prove "(FoundLHS + C) s< (FoundRHS + - // C)". - - APInt LDiff, RDiff; - if (!IsConstDiff(*this, FoundLHS, LHS, LDiff) || - !IsConstDiff(*this, FoundRHS, RHS, RDiff) || - LDiff != RDiff) - return false; - - if (LDiff == 0) - return true; - - unsigned Width = cast(RHS->getType())->getBitWidth(); - APInt FoundRHSLimit; - - if (Pred == CmpInst::ICMP_ULT) { - FoundRHSLimit = -RDiff; - } else { - assert(Pred == CmpInst::ICMP_SLT && "Checked above!"); - FoundRHSLimit = APInt::getSignedMinValue(Width) - RDiff; - } - - // Try to prove (1) or (2), as needed. - return isLoopEntryGuardedByCond(L, Pred, FoundRHS, - getConstant(FoundRHSLimit)); -} - /// isImpliedCondOperands - Test whether the condition described by Pred, /// LHS, and RHS is true whenever the condition described by Pred, FoundLHS, /// and FoundRHS is true. @@ -7454,9 +7298,6 @@ bool ScalarEvolution::isImpliedCondOperands(ICmpInst::Predicate Pred, if (isImpliedCondOperandsViaRanges(Pred, LHS, RHS, FoundLHS, FoundRHS)) return true; - if (isImpliedCondOperandsViaNoOverflow(Pred, LHS, RHS, FoundLHS, FoundRHS)) - return true; - return isImpliedCondOperandsHelper(Pred, LHS, RHS, FoundLHS, FoundRHS) || // ~x < ~y --> x > y diff --git a/test/Analysis/ScalarEvolution/zext-wrap.ll b/test/Analysis/ScalarEvolution/zext-wrap.ll index 5bc149e2309..f56e4556c69 100644 --- a/test/Analysis/ScalarEvolution/zext-wrap.ll +++ b/test/Analysis/ScalarEvolution/zext-wrap.ll @@ -10,7 +10,7 @@ bb.i: ; preds = %bb1.i, %bb.nph ; This cast shouldn't be folded into the addrec. ; CHECK: %tmp = zext i8 %l_95.0.i1 to i16 -; CHECK: --> (zext i8 {0,+,-1}<%bb.i> to i16){{ U: [^ ]+ S: [^ ]+}}{{ *}}Exits: 2 +; CHECK: --> (zext i8 {0,+,-1}<%bb.i> to i16){{ U: [^ ]+ S: [^ ]+}}{{ *}}Exits: 2 %tmp = zext i8 %l_95.0.i1 to i16 diff --git a/test/Transforms/IndVarSimplify/eliminate-comparison.ll b/test/Transforms/IndVarSimplify/eliminate-comparison.ll index 957ebb7cfbf..4d14b3681c5 100644 --- a/test/Transforms/IndVarSimplify/eliminate-comparison.ll +++ b/test/Transforms/IndVarSimplify/eliminate-comparison.ll @@ -209,189 +209,3 @@ assert77: ; preds = %noassert68 unrolledend: ; preds = %forcond38 ret i32 0 } - -declare void @side_effect() - -define void @func_13(i32* %len.ptr) { -; CHECK-LABEL: @func_13( - entry: - %len = load i32, i32* %len.ptr, !range !0 - %len.sub.1 = add i32 %len, -1 - %len.is.zero = icmp eq i32 %len, 0 - br i1 %len.is.zero, label %leave, label %loop - - loop: -; CHECK: loop: - %iv = phi i32 [ 0, %entry ], [ %iv.inc, %be ] - call void @side_effect() - %iv.inc = add i32 %iv, 1 - %iv.cmp = icmp ult i32 %iv, %len - br i1 %iv.cmp, label %be, label %leave -; CHECK: br i1 true, label %be, label %leave - - be: - call void @side_effect() - %be.cond = icmp ult i32 %iv, %len.sub.1 - br i1 %be.cond, label %loop, label %leave - - leave: - ret void -} - -define void @func_14(i32* %len.ptr) { -; CHECK-LABEL: @func_14( - entry: - %len = load i32, i32* %len.ptr, !range !0 - %len.sub.1 = add i32 %len, -1 - %len.is.zero = icmp eq i32 %len, 0 - %len.is.int_min = icmp eq i32 %len, 2147483648 - %no.entry = or i1 %len.is.zero, %len.is.int_min - br i1 %no.entry, label %leave, label %loop - - loop: -; CHECK: loop: - %iv = phi i32 [ 0, %entry ], [ %iv.inc, %be ] - call void @side_effect() - %iv.inc = add i32 %iv, 1 - %iv.cmp = icmp slt i32 %iv, %len - br i1 %iv.cmp, label %be, label %leave -; CHECK: br i1 true, label %be, label %leave - - be: - call void @side_effect() - %be.cond = icmp slt i32 %iv, %len.sub.1 - br i1 %be.cond, label %loop, label %leave - - leave: - ret void -} - -define void @func_15(i32* %len.ptr) { -; CHECK-LABEL: @func_15( - entry: - %len = load i32, i32* %len.ptr, !range !0 - %len.add.1 = add i32 %len, 1 - %len.add.1.is.zero = icmp eq i32 %len.add.1, 0 - br i1 %len.add.1.is.zero, label %leave, label %loop - - loop: -; CHECK: loop: - %iv = phi i32 [ 0, %entry ], [ %iv.inc, %be ] - call void @side_effect() - %iv.inc = add i32 %iv, 1 - %iv.cmp = icmp ult i32 %iv, %len.add.1 - br i1 %iv.cmp, label %be, label %leave -; CHECK: br i1 true, label %be, label %leave - - be: - call void @side_effect() - %be.cond = icmp ult i32 %iv, %len - br i1 %be.cond, label %loop, label %leave - - leave: - ret void -} - -define void @func_16(i32* %len.ptr) { -; CHECK-LABEL: @func_16( - entry: - %len = load i32, i32* %len.ptr, !range !0 - %len.add.5 = add i32 %len, 5 - %entry.cond.0 = icmp slt i32 %len, 2147483643 - %entry.cond.1 = icmp slt i32 4, %len.add.5 - %entry.cond = and i1 %entry.cond.0, %entry.cond.1 - br i1 %entry.cond, label %loop, label %leave - - loop: -; CHECK: loop: - %iv = phi i32 [ 0, %entry ], [ %iv.inc, %be ] - call void @side_effect() - %iv.inc = add i32 %iv, 1 - %iv.add.4 = add i32 %iv, 4 - %iv.cmp = icmp slt i32 %iv.add.4, %len.add.5 - br i1 %iv.cmp, label %be, label %leave -; CHECK: br i1 true, label %be, label %leave - - be: - call void @side_effect() - %be.cond = icmp slt i32 %iv, %len - br i1 %be.cond, label %loop, label %leave - - leave: - ret void -} - -define void @func_17(i32* %len.ptr) { -; CHECK-LABEL: @func_17( - entry: - %len = load i32, i32* %len.ptr - %len.add.5 = add i32 %len, -5 - %entry.cond.0 = icmp slt i32 %len, 2147483653 ;; 2147483653 == INT_MIN - (-5) - %entry.cond.1 = icmp slt i32 -6, %len.add.5 - %entry.cond = and i1 %entry.cond.0, %entry.cond.1 - br i1 %entry.cond, label %loop, label %leave - - loop: -; CHECK: loop: - %iv.2 = phi i32 [ 0, %entry ], [ %iv.2.inc, %be ] - %iv = phi i32 [ -6, %entry ], [ %iv.inc, %be ] - call void @side_effect() - %iv.inc = add i32 %iv, 1 - %iv.2.inc = add i32 %iv.2, 1 - %iv.cmp = icmp slt i32 %iv, %len.add.5 - -; Deduces {-5,+,1} s< (-5 + %len) from {0,+,1} < %len -; since %len s< INT_MIN - (-5) from the entry condition - -; CHECK: br i1 true, label %be, label %leave - br i1 %iv.cmp, label %be, label %leave - - be: -; CHECK: be: - call void @side_effect() - %be.cond = icmp slt i32 %iv.2, %len - br i1 %be.cond, label %loop, label %leave - - leave: - ret void -} - -define i1 @func_18(i16* %tmp20, i32* %len.addr) { -; CHECK-LABEL: @func_18( -entry: - %len = load i32, i32* %len.addr, !range !0 - %tmp18 = icmp eq i32 %len, 0 - br i1 %tmp18, label %bb2, label %bb0.preheader - -bb0.preheader: - br label %bb0 - -bb0: -; CHECK: bb0: - %var_0.in = phi i32 [ %var_0, %bb1 ], [ %len, %bb0.preheader ] - %var_1 = phi i32 [ %tmp30, %bb1 ], [ 0, %bb0.preheader ] - %var_0 = add nsw i32 %var_0.in, -1 - %tmp23 = icmp ult i32 %var_1, %len -; CHECK: br i1 true, label %stay, label %bb2.loopexit - br i1 %tmp23, label %stay, label %bb2 - -stay: -; CHECK: stay: - %tmp25 = getelementptr inbounds i16, i16* %tmp20, i32 %var_1 - %tmp26 = load i16, i16* %tmp25 - %tmp29 = icmp eq i16 %tmp26, 0 - br i1 %tmp29, label %bb1, label %bb2 - -bb1: - %tmp30 = add i32 %var_1, 1 - %tmp31 = icmp eq i32 %var_0, 0 - br i1 %tmp31, label %bb3, label %bb0 - -bb2: - ret i1 false - -bb3: - ret i1 true -} - -!0 = !{i32 0, i32 2147483647} -- 2.34.1