[SCEV] Add one more case in computeConstantDifference

[mkazantsev]

Summary

This patch teaches computeConstantDifference handle calculation of constant
difference between (X + C1) and (X + C2) which is (C2 - C1).

[mkazantsev]

lib/Analysis/ScalarEvolution.cpp

9879

This is incorrect. LHS and FoundLHS can have different types. I will fix this before merging this patch.

[mkazantsev]

lib/Analysis/ScalarEvolution.cpp

9529

Also incorrect, because types of LHS and FoundLHS doesn't have to match.

[sanjoy]

lib/Analysis/ScalarEvolution.cpp

9474

I'd much rather not put all of this (albeit non-recursive) work here when it is possible to easily extend the existing code to handle your pattern.

9529

Do you have a test case for this? ScalarEvolution::isImpliedCond should be zero/sign extending LHS/FoundLHS to make both of them have the same type before calling ScalarEvolution::isImpliedCondOperands. If there are other callsites that don't respect this invariant they should zero/sign extend as well.

[mkazantsev]

lib/Analysis/ScalarEvolution.cpp

9529

Never mind, it seems that I saw this failing due to a bug in another patch I'm working on. False alarm, most likely.

[mkazantsev]

lib/Analysis/ScalarEvolution.cpp

9474

Do we really want to add every easy pattern we find here in future just because it is easy? It looks counter-general. And we don't know how many other relatively simple cases we do not handle.

[sanjoy]

lib/Analysis/ScalarEvolution.cpp

9474

Do we really want to add every easy pattern we find here in future just because it is easy?

If this function starts growing too much with a lot of ad-hoc strategies, we need some other way to handle the kinds of cases you're trying to handle (perhaps by making code higher up the stack smarter).

But for now you should be able to easily handle LHS = {X + C1,+,step}, RHS = {X + C2,+,step},

[mkazantsev]

Allright, let's do it without getAddExpr.

[anna]

test/Transforms/IndVarSimplify/promote-iv-to-eliminate-casts.ll

105

IIUC, this test uses the logic in computeConstantDifference for (X + C2) - (X + C1)`.
Is it possible to add tests for the other rules that you've added:
X - (X+ C1).
That should just be setting iv to len (instead of len.minus.1). That's an out of bounds, but something along these lines should work as a test right?

[mkazantsev]

test/Transforms/IndVarSimplify/promote-iv-to-eliminate-casts.ll

105

I haven't added these cases for X - (X + C1), they were here before, I've just refactored and commented the code slightly. :) But OK, I will add some tests on these situations.

[mkazantsev]

Added some tests.

[anna]

lgtm!

lib/Analysis/ScalarEvolution.cpp

Optional<APInt> ScalarEvolution::computeConstantDifference(const SCEV *More,
   }
 
   if (isa<SCEVConstant>(Less) && isa<SCEVConstant>(More)) {
     const auto &M = cast<SCEVConstant>(More)->getAPInt();
     const auto &L = cast<SCEVConstant>(Less)->getAPInt();
     return M - L;
   }
 
-  const SCEV *L, *R;
   SCEV::NoWrapFlags Flags;
-  if (splitBinaryAdd(Less, L, R, Flags))
-    if (const auto *LC = dyn_cast<SCEVConstant>(L))
-      if (R == More)
-        return -(LC->getAPInt());
-
-  if (splitBinaryAdd(More, L, R, Flags))
-    if (const auto *LC = dyn_cast<SCEVConstant>(L))
-      if (R == Less)
-        return LC->getAPInt();
+  const SCEV *LLess = nullptr, *RLess = nullptr;
+  const SCEV *LMore = nullptr, *RMore = nullptr;
+  const SCEVConstant *C1 = nullptr, *C2 = nullptr;
+  // Compare (X + C1) vs X.
+  if (splitBinaryAdd(Less, LLess, RLess, Flags))
+    if ((C1 = dyn_cast<SCEVConstant>(LLess)))
+      if (RLess == More)
+        return -(C1->getAPInt());
+
+  // Compare X vs (X + C2).
+  if (splitBinaryAdd(More, LMore, RMore, Flags))
+    if ((C2 = dyn_cast<SCEVConstant>(LMore)))
+      if (RMore == Less)
+        return C2->getAPInt();
+
+  // Compare (X + C1) vs (X + C2).
+  if (C1 && C2 && RLess == RMore)
+    return C2->getAPInt() - C1->getAPInt();
 
   return None;
 }
 
 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<SCEVAddRecExpr>(LHS);
   if (!AddRecLHS)
bool ScalarEvolution::isImpliedCondOperandsViaNoOverflow(
   // 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)".
 
   Optional<APInt> LDiff = computeConstantDifference(LHS, FoundLHS);
   Optional<APInt> RDiff = computeConstantDifference(RHS, FoundRHS);
   if (!LDiff || !RDiff || *LDiff != *RDiff)
     return false;
 
   if (LDiff->isMinValue())
     return true;
 
   APInt FoundRHSLimit;
bool ScalarEvolution::isImpliedCondOperandsViaRanges(ICmpInst::Predicate Pred,
                                                      const SCEV *RHS,
                                                      const SCEV *FoundLHS,
                                                      const SCEV *FoundRHS) {
   if (!isa<SCEVConstant>(RHS) || !isa<SCEVConstant>(FoundRHS))
     // The restriction on `FoundRHS` be lifted easily -- it exists only to
     // reduce the compile time impact of this optimization.
     return false;
 
   Optional<APInt> Addend = computeConstantDifference(LHS, FoundLHS);
   if (!Addend)
     return false;
 
   const APInt &ConstFoundRHS = cast<SCEVConstant>(FoundRHS)->getAPInt();
 
   // `FoundLHSRange` is the range we know `FoundLHS` to be in by virtue of the
   // antecedent "`FoundLHS` `Pred` `FoundRHS`".
   ConstantRange FoundLHSRange =

test/Transforms/IndVarSimplify/promote-iv-to-eliminate-casts.ll

bb:             ; preds = %bb, %bb.thread
   store i32 0, i32* %tmp5
   %tmp7 = add i8 %i.0.reg2mem.0, 1              ; <i8> [#uses=2]
   %0 = icmp sgt i8 %tmp7, 30            ; <i1> [#uses=1]
   br i1 %0, label %return, label %bb
 
 return:         ; preds = %bb
   ret void
 }
+
+define void @promote_latch_condition_decrementing_loop_01(i32* %p, i32* %a) {
+
+; CHECK-LABEL: @promote_latch_condition_decrementing_loop_01(
+; CHECK-NOT:     trunc
+
+entry:
+  %len = load i32, i32* %p, align 4, !range !0
+  %len.minus.1 = add nsw i32 %len, -1
+  %zero_check = icmp eq i32 %len, 0
+  br i1 %zero_check, label %loopexit, label %preheader
+
+preheader:
+  br label %loop
+
+loopexit:
+  ret void
+
+loop:
+  %iv = phi i32 [ %iv.next, %loop ], [ %len.minus.1, %preheader ]
+  ; CHECK: %indvars.iv = phi i64
+  %iv.wide = zext i32 %iv to i64
+  %el = getelementptr inbounds i32, i32* %a, i64 %iv.wide
+  store atomic i32 0, i32* %el unordered, align 4
+  %iv.next = add nsw i32 %iv, -1
+  ; CHECK: %loopcond = icmp slt i64 %indvars.iv, 1
+  %loopcond = icmp slt i32 %iv, 1
+  br i1 %loopcond, label %loopexit, label %loop
+}
+
+define void @promote_latch_condition_decrementing_loop_02(i32* %p, i32* %a) {
+
+; CHECK-LABEL: @promote_latch_condition_decrementing_loop_02(
+; CHECK-NOT:     trunc
+
+entry:
+  %len = load i32, i32* %p, align 4, !range !0
+  %zero_check = icmp eq i32 %len, 0
+  br i1 %zero_check, label %loopexit, label %preheader
+
+preheader:
+  br label %loop
+
+loopexit:
+  ret void
+
+loop:
+  %iv = phi i32 [ %iv.next, %loop ], [ %len, %preheader ]
+  ; CHECK: %indvars.iv = phi i64
+  %iv.wide = zext i32 %iv to i64
+  %el = getelementptr inbounds i32, i32* %a, i64 %iv.wide
+  store atomic i32 0, i32* %el unordered, align 4
+  %iv.next = add nsw i32 %iv, -1
+  ; CHECK: %loopcond = icmp slt i64 %indvars.iv, 1
+  %loopcond = icmp slt i32 %iv, 1
+  br i1 %loopcond, label %loopexit, label %loop
+}
+
+define void @promote_latch_condition_decrementing_loop_03(i32* %p, i32* %a) {
+
+; CHECK-LABEL: @promote_latch_condition_decrementing_loop_03(
+; CHECK-NOT:     trunc
+
+entry:
+  %len = load i32, i32* %p, align 4, !range !0
+  %len.plus.1 = add i32 %len, 1
+  %zero_check = icmp eq i32 %len, 0
+  br i1 %zero_check, label %loopexit, label %preheader
+
+preheader:
+  br label %loop
+
+loopexit:
+  ret void
+
+loop:
+  %iv = phi i32 [ %iv.next, %loop ], [ %len.plus.1, %preheader ]
+  ; CHECK: %indvars.iv = phi i64
+  %iv.wide = zext i32 %iv to i64
+  %el = getelementptr inbounds i32, i32* %a, i64 %iv.wide
+  store atomic i32 0, i32* %el unordered, align 4
+  %iv.next = add nsw i32 %iv, -1
+  ; CHECK: %loopcond = icmp slt i64 %indvars.iv, 1
+  %loopcond = icmp slt i32 %iv, 1
+  br i1 %loopcond, label %loopexit, label %loop
+}
+
+
+!0 = !{i32 0, i32 2147483647}