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

[reames]

Summary

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.

[nikic]

LG with some nits

llvm/lib/Analysis/ScalarEvolution.cpp

8101

I'd write these three conditions as match(ExitCond, m_ExtractValue<1>(m_WithOverflowInst(WO)).

8111

I didn't spot where this case is tested. Can you please add one where the successors are swapped? I see some tests using xor -1, but that doesn't appear to be supported by SCEV right now.

[reames]

llvm/lib/Analysis/ScalarEvolution.cpp

8101

Thanks, this is *much* cleaner.

8111

Oops, you're right. Will be covered by @sadd_symbolic_swapped once the change is pushed.

llvm/lib/Analysis/ScalarEvolution.cpp

if (ConstantInt *CI = dyn_cast<ConstantInt>(ExitCond)) {
     if (ExitIfTrue == !CI->getZExtValue())
       // The backedge is always taken.
       return getCouldNotCompute();
     else
       // The backedge is never taken.
       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);
 }
 
 Optional<ScalarEvolution::ExitLimit>
 ScalarEvolution::computeExitLimitFromCondFromBinOp(
     ExitLimitCacheTy &Cache, const Loop *L, Value *ExitCond, bool ExitIfTrue,
     bool ControlsExit, bool AllowPredicates) {

llvm/test/Analysis/ScalarEvolution/overflow-intrinsics-trip-count.ll

 
 for.end:                                          ; preds = %for.body, %entry
   ret void
 }
 
 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
 
 for.body.preheader:                               ; preds = %entry
   br label %for.body
 
 for.body:                                         ; preds = %for.body.preheader, %for.body
   %indvars.iv = phi i16 [ %math, %for.body ], [ %start, %for.body.preheader ]
   %0 = call { i16, i1 } @llvm.uadd.with.overflow.i16(i16 %indvars.iv, i16 1)
   %math = extractvalue { i16, i1 } %0, 0
   %ov = extractvalue { i16, i1 } %0, 1
   br i1 %ov, label %for.end, label %for.body
 
 for.end:                                          ; preds = %for.body, %entry
   ret void
 }
 
 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
 
 for.body.preheader:                               ; preds = %entry
   br label %for.body
 
 for.body:                                         ; preds = %for.body.preheader, %for.body

 
 for.end:                                          ; preds = %for.body, %entry
   ret void
 }
 
 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
 
 for.body.preheader:                               ; preds = %entry
   br label %for.body
 
 for.body:                                         ; preds = %for.body.preheader, %for.body
   %indvars.iv = phi i16 [ %math, %for.body ], [ %start, %for.body.preheader ]
   %0 = call { i16, i1 } @llvm.usub.with.overflow.i16(i16 %indvars.iv, i16 1)
   %math = extractvalue { i16, i1 } %0, 0
   %ov = extractvalue { i16, i1 } %0, 1
   br i1 %ov, label %for.end, label %for.body
 
 for.end:                                          ; preds = %for.body, %entry
   ret void
 }
 
 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
 
 for.body.preheader:                               ; preds = %entry
   br label %for.body
 
 for.body:                                         ; preds = %for.body.preheader, %for.body

 
 for.end:                                          ; preds = %for.body, %entry
   ret void
 }
 
 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
 
 for.body.preheader:                               ; preds = %entry
   br label %for.body
 
 for.body:                                         ; preds = %for.body.preheader, %for.body

llvm/test/CodeGen/PowerPC/negctr.ll

entry:
   br i1 undef, label %for.end, label %for.body
 
 for.body:                                         ; preds = %for.body, %entry
   %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ 1, %entry ]
   %indvars.iv.next = add i64 %indvars.iv, 1
   %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
 }
 
 define void @main2() #0 {
 entry:
   br i1 undef, label %for.end, label %for.body