Re-enable "[IndVars] Canonicalize comparisons between non-negative values and indvars"

[mkazantsev]

Summary

The patch was reverted due to a bug. The bug was that if the IV is the 2nd operand of the icmp
instruction, then the "Pred" variable gets swapped and differs from the instruction's predicate.
In this patch we use the original predicate to do the transformation.

Also added a test case that exercises this situation.

[chapuni]

It works. I could approve but I will wait for 3rd person.

FYI, you may reopen D34979 for it.

[anna]

LGTM.

lib/Transforms/Utils/SimplifyIndVar.cpp

268

Could you please add a comment here why you're using the OriginalPred.
It seems useful to state it.

Also,IIUC, doing this transform when Pred is swapped version of OriginalPred is error prone. We also need to check that IV is the second operand to avoid breaking canonicalization -- IV is always on the left.

[mkazantsev]

lib/Transforms/Utils/SimplifyIndVar.cpp

268

That's what actually what the bug was. I used to use Pred here, which was wrong in the situation:

sgt 100, iv

We wanted to operate with "slt iv, 100" within the method, but the tricky thing is that the instruction remained unchanged, we only replace the Pred variable and not operate in terms of left and right operand, but use this thing:

const SCEV *S = SE->getSCEV(ICmp->getOperand(IVOperIdx));
const SCEV *X = SE->getSCEV(ICmp->getOperand(1 - IVOperIdx));

So in the described situation the actual instruction is "sgt 100, iv", but the Pred variable is "slt". What we want to have in the end is "ugt 100, iv", that's why we need the original pred (or alternatively swap Pred twice in this case).

I will add a comment on that.

[mkazantsev]

Added a comment explaining why we use OriginalPred.

[anna]

lib/Transforms/Utils/SimplifyIndVar.cpp

268

Thanks.
Actually, what I meant was even enabling this transform *correctly* using Pred is error prone (but won't be a bug). The reason is precisely what you mentioned... we swap the predicate but not the operands. So, we need to swap the operands back, but only if Pred is swapped version of OriginalPred *and* IV is on the right. As we can see depending on Pred is highly prone to errors :)
However, what you've done here is strictly correct, since we don't depend on knowing if Pred was changed in someway.

[mkazantsev]

Merged as 307477.

lib/Transforms/Utils/SimplifyIndVar.cpp

Value *SimplifyIndvar::foldIVUser(Instruction *UseInst, Instruction *IVOperand) {
   return IVSrc;
 }
 
 /// SimplifyIVUsers helper for eliminating useless
 /// comparisons against an induction variable.
 void SimplifyIndvar::eliminateIVComparison(ICmpInst *ICmp, Value *IVOperand) {
   unsigned IVOperIdx = 0;
   ICmpInst::Predicate Pred = ICmp->getPredicate();
+  ICmpInst::Predicate OriginalPred = Pred;
   if (IVOperand != ICmp->getOperand(0)) {
     // Swapped
     assert(IVOperand == ICmp->getOperand(1) && "Can't find IVOperand");
     IVOperIdx = 1;
     Pred = ICmpInst::getSwappedPredicate(Pred);
   }
 
   // Get the SCEVs for the ICmp operands.
if (!NewLHS || !NewRHS)
       // Generating new instructions has subtler tradeoffs, so avoid doing that
       // for now.
       return;
 
     DEBUG(dbgs() << "INDVARS: Simplified comparison: " << *ICmp << '\n');
     ICmp->setPredicate(InvariantPredicate);
     ICmp->setOperand(0, NewLHS);
     ICmp->setOperand(1, NewRHS);
+  } else if (ICmpInst::isSigned(OriginalPred) &&
+             SE->isKnownNonNegative(S) && SE->isKnownNonNegative(X)) {
+    // If we were unable to make anything above, all we can is to canonicalize
+    // the comparison hoping that it will open the doors for other
+    // optimizations. If we find out that we compare two non-negative values,
+    // we turn the instruction's predicate to its unsigned version. Note that
+    // we cannot rely on Pred here unless we check if we have swapped it.
+    assert(ICmp->getPredicate() == OriginalPred && "Predicate changed?");
+    DEBUG(dbgs() << "INDVARS: Turn to unsigned comparison: " << *ICmp << '\n');
+    ICmp->setPredicate(ICmpInst::getUnsignedPredicate(OriginalPred));
   } else
     return;
 
   ++NumElimCmp;
   Changed = true;
 }
 
 bool SimplifyIndvar::eliminateSDiv(BinaryOperator *SDiv) {

test/Analysis/ScalarEvolution/guards.ll

 ; CHECK-LABEL: @test_1(
 entry:
   %len = load i32, i32* %len_buf, !range !{i32 1, i32 2147483648}
   br label %loop
 
 loop:
 ; CHECK: loop:
 ; CHECK:  call void (i1, ...) @llvm.experimental.guard(i1 true) [ "deopt"() ]
-; CHECK:  %iv.inc.cmp = icmp slt i32 %iv.inc, %len
+; CHECK:  %iv.inc.cmp = icmp ult i32 %iv.inc, %len
 ; CHECK:  call void (i1, ...) @llvm.experimental.guard(i1 %iv.inc.cmp) [ "deopt"() ]
 ; CHECK: leave:
 
   %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ]
   %iv.inc = add i32 %iv, 1
 
   %iv.cmp = icmp slt i32 %iv, %len
   call void(i1, ...) @llvm.experimental.guard(i1 %iv.cmp) [ "deopt"() ]
 
   %iv.inc.cmp = icmp slt i32 %iv.inc, %len
   call void(i1, ...) @llvm.experimental.guard(i1 %iv.inc.cmp) [ "deopt"() ]
 
   %becond = load volatile i1, i1* %cond_buf
   br i1 %becond, label %loop, label %leave
 
 leave:
   ret void
 }
 
 define void @test_2(i32 %n, i32* %len_buf) {
 ; CHECK-LABEL: @test_2(
-; CHECK:  [[LEN_SEXT:%[^ ]+]] = sext i32 %len to i64
+; CHECK:  [[LEN_ZEXT:%[^ ]+]] = zext i32 %len to i64
 ; CHECK:  br label %loop
 
 entry:
   %len = load i32, i32* %len_buf, !range !{i32 0, i32 2147483648}
   br label %loop
 
 loop:
 ; CHECK: loop:
 ; CHECK:  %indvars.iv = phi i64 [ %indvars.iv.next, %loop ], [ 0, %entry ]
 ; CHECK:  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
-; CHECK:  %iv.inc.cmp = icmp slt i64 %indvars.iv.next, [[LEN_SEXT]]
+; CHECK:  %iv.inc.cmp = icmp ult i64 %indvars.iv.next, [[LEN_ZEXT]]
 ; CHECK:  call void (i1, ...) @llvm.experimental.guard(i1 %iv.inc.cmp) [ "deopt"() ]
 ; CHECK: leave:
 
   %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ]
   %iv.inc = add i32 %iv, 1
 
   %iv.sext = sext i32 %iv to i64
 

test/Transforms/IndVarSimplify/canonicalize-cmp.ll

+; RUN: opt -S -indvars < %s | FileCheck %s
+
+; Check that we replace signed comparisons between non-negative values with
+; unsigned comparisons if we can.
+
+target datalayout = "n8:16:32:64"
+
+define i32 @test_01(i32 %a, i32 %b, i32* %p) {
+
+; CHECK-LABEL: @test_01(
+; CHECK-NOT:   icmp slt
+; CHECK:       %cmp1 = icmp ult i32 %iv, 100
+; CHECK:       %cmp2 = icmp ult i32 %iv, 100
+; CHECK-NOT:   %cmp3
+; CHECK:       %exitcond = icmp ne i32 %iv.next, 1000
+
+entry:
+  br label %loop.entry
+
+loop.entry:
+  %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop.be ]
+  %cmp1 = icmp slt i32 %iv, 100
+  br i1 %cmp1, label %b1, label %b2
+
+b1:
+  store i32 %iv, i32* %p
+  br label %merge
+
+b2:
+  store i32 %a, i32* %p
+  br label %merge
+
+merge:
+  %cmp2 = icmp ult i32 %iv, 100
+  br i1 %cmp2, label %b3, label %b4
+
+b3:
+  store i32 %iv, i32* %p
+  br label %loop.be
+
+b4:
+  store i32 %b, i32* %p
+  br label %loop.be
+
+loop.be:
+  %iv.next = add i32 %iv, 1
+  %cmp3 = icmp slt i32 %iv.next, 1000
+  br i1 %cmp3, label %loop.entry, label %exit
+
+exit:
+  ret i32 %iv
+}
+
+define i32 @test_02(i32 %a, i32 %b, i32* %p) {
+
+; CHECK-LABEL: @test_02(
+; CHECK-NOT:   icmp sgt
+; CHECK:       %cmp1 = icmp ugt i32 100, %iv
+; CHECK:       %cmp2 = icmp ugt i32 100, %iv
+; CHECK-NOT:   %cmp3
+; CHECK:       %exitcond = icmp ne i32 %iv.next, 1000
+
+entry:
+  br label %loop.entry
+
+loop.entry:
+  %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop.be ]
+  %cmp1 = icmp sgt i32 100, %iv
+  br i1 %cmp1, label %b1, label %b2
+
+b1:
+  store i32 %iv, i32* %p
+  br label %merge
+
+b2:
+  store i32 %a, i32* %p
+  br label %merge
+
+merge:
+  %cmp2 = icmp ugt i32 100, %iv
+  br i1 %cmp2, label %b3, label %b4
+
+b3:
+  store i32 %iv, i32* %p
+  br label %loop.be
+
+b4:
+  store i32 %b, i32* %p
+  br label %loop.be
+
+loop.be:
+  %iv.next = add i32 %iv, 1
+  %cmp3 = icmp sgt i32 1000, %iv.next
+  br i1 %cmp3, label %loop.entry, label %exit
+
+exit:
+  ret i32 %iv
+}

test/Transforms/IndVarSimplify/eliminate-comparison.ll

 return:
   ret void
 }
 
 ; PR14432
 ; Indvars should not turn the second loop into an infinite one.
 
 ; CHECK-LABEL: @func_11(
-; CHECK: %tmp5 = icmp slt i32 %__key6.0, 10
+; CHECK: %tmp5 = icmp ult i32 %__key6.0, 10
 ; CHECK-NOT: br i1 true, label %noassert68, label %unrolledend
 
 define i32 @func_11() nounwind uwtable {
 entry:
   br label %forcond
 
 forcond:                                          ; preds = %noassert, %entry
   %__key6.0 = phi i32 [ 2, %entry ], [ %tmp37, %noassert ]

 unrolledend:                                      ; preds = %forcond38
   ret i32 0
 }
 
 declare void @llvm.trap() noreturn nounwind
 
 ; In this case the second loop only has a single iteration, fold the header away
 ; CHECK-LABEL: @func_12(
-; CHECK: %tmp5 = icmp slt i32 %__key6.0, 10
+; CHECK: %tmp5 = icmp ult i32 %__key6.0, 10
 ; CHECK: br i1 true, label %noassert68, label %unrolledend
 define i32 @func_12() nounwind uwtable {
 entry:
   br label %forcond
 
 forcond:                                          ; preds = %noassert, %entry
   %__key6.0 = phi i32 [ 2, %entry ], [ %tmp37, %noassert ]
   %tmp5 = icmp slt i32 %__key6.0, 10

test/Transforms/IndVarSimplify/widen-loop-comp.ll

 for.end:
   %4 = load i32, i32* @idx, align 4
   ret i32 %4
 }
 
 ; CHECK-LABEL: @test2
 ; CHECK: for.body4.us
 ; CHECK: %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
-; CHECK: %cmp2.us = icmp slt i64
+; CHECK: %cmp2.us = icmp ult i64
 ; CHECK-NOT: %2 = trunc i64 %indvars.iv.next to i32
 ; CHECK-NOT: %cmp2.us = icmp slt i32
 
 define void @test2([8 x i8]* %a, i8* %b, i8 %limit) {
 entry:
   %conv = zext i8 %limit to i32
   br i1 undef, label %for.cond1.preheader, label %for.cond1.preheader.us