[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

9805 ↗

(On Diff #135879)

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

[mkazantsev]

lib/Analysis/ScalarEvolution.cpp

9455 ↗

(On Diff #135879)

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

[sanjoy]

lib/Analysis/ScalarEvolution.cpp

9396 ↗

(On Diff #135879)

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.

9455 ↗

(On Diff #135879)

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

9455 ↗

(On Diff #135879)

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

9396 ↗

(On Diff #135879)

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

9396 ↗

(On Diff #135879)

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 ↗

(On Diff #137975)

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 ↗

(On Diff #137975)

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!

llvm/trunk/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)

llvm/trunk/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}