[SCEV] simplify more icmps with pred sle/ule to pred slt/ult

[shchenz]

Summary

define void @sle(i8* %p, i32 %a, i32 %b) {
...
for.body: 
%i.04 = phi i32 [ %a, %for.body.lr.ph ], [ %inc, %for.body ]
%inc = add nsw i32 %i.04, 1
%cmp = icmp sle i32 %inc, %b
br i1 %cmp, label %for.body, label %for.end
...
}

SCEV for %i.04 is {%a, +, 1}, SCEV for icmp LHS(%inc) is {(%a + 1) <nsw>, + , 1}. Currently, the range for LHS is full-set.

In patch https://reviews.llvm.org/D64869, the range for LHS is corrected to [INT32_MIN+1, INT32_MIN).

This patch is based on the fixed range in https://reviews.llvm.org/D64869 to get backedge-taken for more loops. We can convert more sle/ule to slt/ult.

[shchenz]

https://reviews.llvm.org/D64868 is reverted, need to fix that firstly.

[shchenz]

Right solution should be https://reviews.llvm.org/D71690. We can convert sle to slt if get(Signed|Unsigned)RangeMin(LHS) is not min value. In https://reviews.llvm.org/D71690, we can get a more accurate min value for AddRec with flag nsw|nuw.

llvm/lib/Analysis/ScalarEvolution.cpp

if (!getSignedRangeMax(RHS).isMaxSignedValue()) {
                        SCEV::FlagNSW);
       Pred = ICmpInst::ICMP_SLT;
       Changed = true;
     } else if (!getSignedRangeMin(LHS).isMinSignedValue()) {
       LHS = getAddExpr(getConstant(RHS->getType(), (uint64_t)-1, true), LHS,
                        SCEV::FlagNSW);
       Pred = ICmpInst::ICMP_SLT;
       Changed = true;
+    } else if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS)) {
+      const SCEV *Stride = AddRec->getStepRecurrence(*this);
+      // If Stride is positive, Start is not min signed value and LHS has
+      // FlagNSW, we can canonicalize sle to slt.
+      if (isKnownPositive(Stride) &&
+          !getSignedRangeMin(AddRec->getStart()).isMinSignedValue() &&
+          AddRec->hasNoSignedWrap()) {
+        LHS = getAddExpr(getConstant(RHS->getType(), (uint64_t)-1, true), LHS,
+                         SCEV::FlagNSW);
+        Pred = ICmpInst::ICMP_SLT;
+        Changed = true;
+      }
     }
     break;
   case ICmpInst::ICMP_SGE:
     if (!getSignedRangeMin(RHS).isMinSignedValue()) {
       RHS = getAddExpr(getConstant(RHS->getType(), (uint64_t)-1, true), RHS,
                        SCEV::FlagNSW);
       Pred = ICmpInst::ICMP_SGT;
       Changed = true;
if (!getUnsignedRangeMax(RHS).isMaxValue()) {
       RHS = getAddExpr(getConstant(RHS->getType(), 1, true), RHS,
                        SCEV::FlagNUW);
       Pred = ICmpInst::ICMP_ULT;
       Changed = true;
     } else if (!getUnsignedRangeMin(LHS).isMinValue()) {
       LHS = getAddExpr(getConstant(RHS->getType(), (uint64_t)-1, true), LHS);
       Pred = ICmpInst::ICMP_ULT;
       Changed = true;
+    } else if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS)) {
+      const SCEV *Stride = AddRec->getStepRecurrence(*this);
+      // If Stride is positive, Start is not min value and LHS has FlagNUW, we
+      // can canonicalize ule to ult.
+      if (isKnownPositive(Stride) &&
+          !getUnsignedRangeMin(AddRec->getStart()).isMinValue() &&
+          AddRec->hasNoUnsignedWrap()) {
+        LHS = getAddExpr(getConstant(RHS->getType(), (uint64_t)-1, true), LHS,
+                         SCEV::FlagNUW);
+        Pred = ICmpInst::ICMP_ULT;
+        Changed = true;
+      }
     }
     break;
   case ICmpInst::ICMP_UGE:
     if (!getUnsignedRangeMin(RHS).isMinValue()) {
       RHS = getAddExpr(getConstant(RHS->getType(), (uint64_t)-1, true), RHS);
       Pred = ICmpInst::ICMP_UGT;
       Changed = true;
     } else if (!getUnsignedRangeMax(LHS).isMaxValue()) {

llvm/test/Analysis/ScalarEvolution/trip-count15.ll

+; RUN: opt -S -analyze -scalar-evolution < %s | FileCheck %s
+
+; CHECK-LABEL: Determining loop execution counts for: @sle_nsw
+; CHECK: Loop %for.body: backedge-taken count is ((-1 * %a) + (%a smax %b))
+; CHECK: Loop %for.body: max backedge-taken count is -1
+define void @sle_nsw(i8* %p, i32 %a, i32 %b) {
+entry:
+  %cmp3 = icmp sle i32 %a, %b
+  br i1 %cmp3, label %for.body.lr.ph, label %for.end
+
+for.body.lr.ph:                                   ; preds = %entry
+  br label %for.body
+
+for.body:                                         ; preds = %for.body.lr.ph, %for.body
+  %i.04 = phi i32 [ %a, %for.body.lr.ph ], [ %inc, %for.body ]
+  %arrayidx = getelementptr inbounds i8, i8* %p, i32 %i.04
+  %0 = load i8, i8* %arrayidx, align 1
+  %conv = zext i8 %0 to i32
+  %add = add nsw i32 %conv, 1
+  %conv1 = trunc i32 %add to i8
+  store i8 %conv1, i8* %arrayidx, align 1
+  %inc = add nsw i32 %i.04, 1
+  %cmp = icmp sle i32 %inc, %b
+  br i1 %cmp, label %for.body, label %for.end
+
+for.end:                                          ; preds = %for.body, %entry
+  ret void
+}
+
+; CHECK-LABEL: Determining loop execution counts for: @sle
+; CHECK: Loop %for.body: Unpredictable backedge-taken count.
+; CHECK: Loop %for.body: Unpredictable max backedge-taken count. 
+; CHECK: Loop %for.body: Unpredictable predicated backedge-taken count. 
+define void @sle(i8* %p, i32 %a, i32 %b) {
+entry:
+  %cmp3 = icmp sle i32 %a, %b
+  br i1 %cmp3, label %for.body.lr.ph, label %for.end
+
+for.body.lr.ph:                                   ; preds = %entry
+  br label %for.body
+
+for.body:                                         ; preds = %for.body.lr.ph, %for.body
+  %i.04 = phi i32 [ %a, %for.body.lr.ph ], [ %inc, %for.body ]
+  %arrayidx = getelementptr inbounds i8, i8* %p, i32 %i.04
+  %0 = load i8, i8* %arrayidx, align 1
+  %conv = zext i8 %0 to i32
+  %add = add nsw i32 %conv, 1
+  %conv1 = trunc i32 %add to i8
+  store i8 %conv1, i8* %arrayidx, align 1
+  %inc = add i32 %i.04, 1
+  %cmp = icmp sle i32 %inc, %b
+  br i1 %cmp, label %for.body, label %for.end
+
+for.end:                                          ; preds = %for.body, %entry
+  ret void
+}
+
+; CHECK-LABEL: Determining loop execution counts for: @ule_nuw
+; CHECK: Loop %for.body: backedge-taken count is ((-1 * %a) + (%a umax %b))
+; CHECK: Loop %for.body: max backedge-taken count is -1
+; CHECK: Loop %for.body: Predicated backedge-taken count is ((-1 * %a) + (%a umax %b))
+define void @ule_nuw(i8* %p, i32 zeroext %a, i32 zeroext %b) {
+entry:
+  %cmp3 = icmp ule i32 %a, %b
+  br i1 %cmp3, label %for.body.lr.ph, label %for.end
+
+for.body.lr.ph:                                   ; preds = %entry
+  br label %for.body
+
+for.body:                                         ; preds = %for.body.lr.ph, %for.body
+  %i.04 = phi i32 [ %a, %for.body.lr.ph ], [ %inc, %for.body ]
+  %arrayidx = getelementptr inbounds i8, i8* %p, i32 %i.04
+  %0 = load i8, i8* %arrayidx, align 1
+  %conv = zext i8 %0 to i32
+  %add = add nsw i32 %conv, 1
+  %conv1 = trunc i32 %add to i8
+  store i8 %conv1, i8* %arrayidx, align 1
+  %inc = add nuw i32 %i.04, 1
+  %cmp = icmp ule i32 %inc, %b
+  br i1 %cmp, label %for.body, label %for.end
+
+for.end:                                          ; preds = %for.body, %entry
+  ret void
+}
+
+; CHECK-LABEL: Determining loop execution counts for: @ule
+; CHECK: Loop %for.body: Unpredictable backedge-taken count.
+; CHECK: Loop %for.body: Unpredictable max backedge-taken count. 
+; CHECK: Loop %for.body: Unpredictable predicated backedge-taken count. 
+define void @ule(i8* %p, i32 zeroext %a, i32 zeroext %b) {
+entry:
+  %cmp3 = icmp ule i32 %a, %b
+  br i1 %cmp3, label %for.body.lr.ph, label %for.end
+
+for.body.lr.ph:                                   ; preds = %entry
+  br label %for.body
+
+for.body:                                         ; preds = %for.body.lr.ph, %for.body
+  %i.04 = phi i32 [ %a, %for.body.lr.ph ], [ %inc, %for.body ]
+  %arrayidx = getelementptr inbounds i8, i8* %p, i32 %i.04
+  %0 = load i8, i8* %arrayidx, align 1
+  %conv = zext i8 %0 to i32
+  %add = add nsw i32 %conv, 1
+  %conv1 = trunc i32 %add to i8
+  store i8 %conv1, i8* %arrayidx, align 1
+  %inc = add i32 %i.04, 1
+  %cmp = icmp ule i32 %inc, %b
+  br i1 %cmp, label %for.body, label %for.end
+
+for.end:                                          ; preds = %for.body, %entry
+  ret void
+}

llvm/test/CodeGen/PowerPC/ctrloop-le.ll

 
 for.end:                                          ; preds = %for.body, %entry
   ret void
 }
 
 
 
 ; CHECK: test_pos1_rr_sle
-; FIXME: Support this loop!
-; CHECK-NOT: bdnz
+; CHECK: bdnz
 ; a < b
 define void @test_pos1_rr_sle(i8* nocapture %p, i32 %a, i32 %b) nounwind {
 entry:
   %cmp3 = icmp sle i32 %a, %b
   br i1 %cmp3, label %for.body.lr.ph, label %for.end
 
 for.body.lr.ph:                                   ; preds = %entry
   br label %for.body

 
 for.end:                                          ; preds = %for.body, %entry
   ret void
 }
 
 
 
 ; CHECK: test_pos2_rr_sle
-; FIXME: Support this loop!
-; CHECK-NOT: bdnz
+; CHECK: bdnz
 ; a < b
 define void @test_pos2_rr_sle(i8* nocapture %p, i32 %a, i32 %b) nounwind {
 entry:
   %cmp3 = icmp sle i32 %a, %b
   br i1 %cmp3, label %for.body.lr.ph, label %for.end
 
 for.body.lr.ph:                                   ; preds = %entry
   br label %for.body

 
 for.end:                                          ; preds = %for.body, %entry
   ret void
 }
 
 
 
 ; CHECK: test_pos4_rr_sle
-; FIXME: Support this loop!
-; CHECK-NOT: bdnz
+; CHECK: bdnz
 ; a < b
 define void @test_pos4_rr_sle(i8* nocapture %p, i32 %a, i32 %b) nounwind {
 entry:
   %cmp3 = icmp sle i32 %a, %b
   br i1 %cmp3, label %for.body.lr.ph, label %for.end
 
 for.body.lr.ph:                                   ; preds = %entry
   br label %for.body

 
 for.end:                                          ; preds = %for.body, %entry
   ret void
 }
 
 
 
 ; CHECK: test_pos8_rr_sle
-; FIXME: Support this loop!
-; CHECK-NOT: bdnz
+; CHECK: bdnz
 ; a < b
 define void @test_pos8_rr_sle(i8* nocapture %p, i32 %a, i32 %b) nounwind {
 entry:
   %cmp3 = icmp sle i32 %a, %b
   br i1 %cmp3, label %for.body.lr.ph, label %for.end
 
 for.body.lr.ph:                                   ; preds = %entry
   br label %for.body

 
 for.end:                                          ; preds = %for.body, %entry
   ret void
 }
 
 
 
 ; CHECK: test_pos16_rr_sle
-; FIXME: Support this loop!
-; CHECK-NOT: bdnz
+; CHECK: bdnz
 ; a < b
 define void @test_pos16_rr_sle(i8* nocapture %p, i32 %a, i32 %b) nounwind {
 entry:
   %cmp3 = icmp sle i32 %a, %b
   br i1 %cmp3, label %for.body.lr.ph, label %for.end
 
 for.body.lr.ph:                                   ; preds = %entry
   br label %for.body