[SCEV] Compute exit count from overflow check expressed w/ x.with.overflow intrinsics

This ports the logic we generate in instcombine for a single use x.with.overflow check for use in SCEV's analysis. The result is that we can prove trip counts for many checks, and (through existing logic) often discharge them.

Motivation comes from compiling a simple example with -ftrapv.

Differential Revision: https://reviews.llvm.org/D116499

3 files changed, 51 insertions, 22 deletions

diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp
index d48e81f28af9..513b2c0e5da1 100644
--- a/llvm/lib/Analysis/ScalarEvolution.cpp
+++ b/llvm/lib/Analysis/ScalarEvolution.cpp
@@ -8093,6 +8093,29 @@ ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondImpl(
       return getZero(CI->getType());
   }
 
+  // If we're exiting based on the overflow flag of an x.with.overflow intrinsic
+  // with a constant step, we can form an equivalent icmp predicate and figure
+  // out how many iterations will be taken before we exit.
+  const WithOverflowInst *WO;
+  const APInt *C;
+  if (match(ExitCond, m_ExtractValue<1>(m_WithOverflowInst(WO))) &&
+      match(WO->getRHS(), m_APInt(C))) {
+    ConstantRange NWR =
+      ConstantRange::makeExactNoWrapRegion(WO->getBinaryOp(), *C,
+                                           WO->getNoWrapKind());
+    CmpInst::Predicate Pred;
+    APInt NewRHSC, Offset;
+    NWR.getEquivalentICmp(Pred, NewRHSC, Offset);
+    if (!ExitIfTrue)
+      Pred = ICmpInst::getInversePredicate(Pred);
+    auto *LHS = getSCEV(WO->getLHS());
+    if (Offset != 0)
+      LHS = getAddExpr(LHS, getConstant(Offset));
+    auto EL = computeExitLimitFromICmp(L, Pred, LHS, getConstant(NewRHSC),
+                                       ControlsExit, AllowPredicates);
+    if (EL.hasAnyInfo()) return EL;
+  }
+
   // If it's not an integer or pointer comparison then compute it the hard way.
   return computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
 }
diff --git a/llvm/test/Analysis/ScalarEvolution/overflow-intrinsics-trip-count.ll b/llvm/test/Analysis/ScalarEvolution/overflow-intrinsics-trip-count.ll
index 942f312599da..38372c94e3ea 100644
--- a/llvm/test/Analysis/ScalarEvolution/overflow-intrinsics-trip-count.ll
+++ b/llvm/test/Analysis/ScalarEvolution/overflow-intrinsics-trip-count.ll
@@ -167,9 +167,11 @@ for.end:                                          ; preds = %for.body, %entry
 define void @uadd_symbolic_start(i16 %start) {
 ; CHECK-LABEL: 'uadd_symbolic_start'
 ; CHECK-NEXT:  Determining loop execution counts for: @uadd_symbolic_start
-; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
-; CHECK-NEXT:  Loop %for.body: Unpredictable max backedge-taken count.
-; CHECK-NEXT:  Loop %for.body: Unpredictable predicated backedge-taken count.
+; CHECK-NEXT:  Loop %for.body: backedge-taken count is (-1 + (-1 * %start))
+; CHECK-NEXT:  Loop %for.body: max backedge-taken count is -1
+; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (-1 + (-1 * %start))
+; CHECK-NEXT:   Predicates:
+; CHECK:       Loop %for.body: Trip multiple is 1
 ;
 entry:
   br i1 undef, label %for.end, label %for.body.preheader
@@ -191,9 +193,11 @@ for.end:                                          ; preds = %for.body, %entry
 define void @sadd_symbolic_start(i16 %start) {
 ; CHECK-LABEL: 'sadd_symbolic_start'
 ; CHECK-NEXT:  Determining loop execution counts for: @sadd_symbolic_start
-; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
-; CHECK-NEXT:  Loop %for.body: Unpredictable max backedge-taken count.
-; CHECK-NEXT:  Loop %for.body: Unpredictable predicated backedge-taken count.
+; CHECK-NEXT:  Loop %for.body: backedge-taken count is (32767 + (-1 * %start))
+; CHECK-NEXT:  Loop %for.body: max backedge-taken count is -1
+; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (32767 + (-1 * %start))
+; CHECK-NEXT:   Predicates:
+; CHECK:       Loop %for.body: Trip multiple is 1
 ;
 entry:
   br i1 undef, label %for.end, label %for.body.preheader
@@ -264,9 +268,11 @@ for.end:                                          ; preds = %for.body, %entry
 define void @usub_symbolic_start(i16 %start) {
 ; CHECK-LABEL: 'usub_symbolic_start'
 ; CHECK-NEXT:  Determining loop execution counts for: @usub_symbolic_start
-; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
-; CHECK-NEXT:  Loop %for.body: Unpredictable max backedge-taken count.
-; CHECK-NEXT:  Loop %for.body: Unpredictable predicated backedge-taken count.
+; CHECK-NEXT:  Loop %for.body: backedge-taken count is %start
+; CHECK-NEXT:  Loop %for.body: max backedge-taken count is -1
+; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is %start
+; CHECK-NEXT:   Predicates:
+; CHECK:       Loop %for.body: Trip multiple is 1
 ;
 entry:
   br i1 undef, label %for.end, label %for.body.preheader
@@ -288,9 +294,11 @@ for.end:                                          ; preds = %for.body, %entry
 define void @ssub_symbolic_start(i16 %start) {
 ; CHECK-LABEL: 'ssub_symbolic_start'
 ; CHECK-NEXT:  Determining loop execution counts for: @ssub_symbolic_start
-; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
-; CHECK-NEXT:  Loop %for.body: Unpredictable max backedge-taken count.
-; CHECK-NEXT:  Loop %for.body: Unpredictable predicated backedge-taken count.
+; CHECK-NEXT:  Loop %for.body: backedge-taken count is (-32768 + %start)
+; CHECK-NEXT:  Loop %for.body: max backedge-taken count is -1
+; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (-32768 + %start)
+; CHECK-NEXT:   Predicates:
+; CHECK:       Loop %for.body: Trip multiple is 1
 ;
 entry:
   br i1 undef, label %for.end, label %for.body.preheader
@@ -360,11 +368,13 @@ for.end:                                          ; preds = %for.body, %entry
 define void @sadd_symbolic_non_latch(i16 %start) {
 ; CHECK-LABEL: 'sadd_symbolic_non_latch'
 ; CHECK-NEXT:  Determining loop execution counts for: @sadd_symbolic_non_latch
-; CHECK-NEXT:  Loop %for.body: <multiple exits> Unpredictable backedge-taken count.
-; CHECK-NEXT:    exit count for for.body: ***COULDNOTCOMPUTE***
+; CHECK-NEXT:  Loop %for.body: <multiple exits> backedge-taken count is ((230 + (-1 * %start)) umin (32767 + (-1 * %start)))
+; CHECK-NEXT:    exit count for for.body: (32767 + (-1 * %start))
 ; CHECK-NEXT:    exit count for for.latch: (230 + (-1 * %start))
 ; CHECK-NEXT:  Loop %for.body: max backedge-taken count is -1
-; CHECK-NEXT:  Loop %for.body: Unpredictable predicated backedge-taken count.
+; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is ((230 + (-1 * %start)) umin (32767 + (-1 * %start)))
+; CHECK-NEXT:   Predicates:
+; CHECK:       Loop %for.body: Trip multiple is 1
 ;
 entry:
   br i1 undef, label %for.end, label %for.body.preheader
diff --git a/llvm/test/CodeGen/PowerPC/negctr.ll b/llvm/test/CodeGen/PowerPC/negctr.ll
index 93c7daed64f6..38664b058b87 100644
--- a/llvm/test/CodeGen/PowerPC/negctr.ll
+++ b/llvm/test/CodeGen/PowerPC/negctr.ll
@@ -34,14 +34,10 @@ for.body:                                         ; preds = %for.body, %entry
   %exitcond = icmp eq i64 %indvars.iv.next, 0
   br i1 %exitcond, label %for.end, label %for.body
 
-; FIXME: This should be a hardware loop.
-; cmp is optimized to uadd intrinsic in CGP pass which can not be recognized in
-; later HardwareLoops Pass.
 ; CHECK: @main1
-; CHECK: li [[REG:[0-9]+]], 1
-; CHECK: addi [[REG2:[0-9]+]], [[REG]], 1
-; CHECK: cmpld
-; CHECK: bge
+; CHECK: li [[REG:[0-9]+]], -1
+; CHECK: mtctr [[REG]]
+; CHECK: bdnz
 
 for.end:                                          ; preds = %for.body, %entry
   ret void