[SCEV] Favor isKnownViaSimpleReasoning over constant ranges check

[mkazantsev]

Summary

There is a more powerful but still simple function isKnownViaSimpleReasoning that
does constant range check and few more additional checks. We use it some places (e.g.
when proving implications) and in some other places we only check constant ranges.

Currently, indvar simplifier fails to remove the check in following loop:

int inc = ...;
for (int i = inc, j = inc - 1; i < 200; ++i, ++j)
  if (i > j) { ... }

This patch replaces all usages of isKnownPredicateViaConstantRanges with
isKnownViaSimpleReasoning to have smarter proofs. In particular, it fixes the
case above.

[sanjoy]

lgtm.

You may want to indicate the range of inc in the commit message; otherwise it looks like we're introducing a miscompile. :)

lib/Analysis/ScalarEvolution.cpp

8962

I think it is better to call this isKnownViaNonRecursiveReasoning since "simple" is not very descriptive (if you agree can you please directly land that in a subsequent change?).

test/Transforms/IndVarSimplify/loop-invariant-conditions.ll

144

Let's move this to the bottom of the file.

[mkazantsev]

lib/Analysis/ScalarEvolution.cpp

8962

Will do as follow-up NFC.

test/Transforms/IndVarSimplify/loop-invariant-conditions.ll

144

Will do as follow-up.

lib/Analysis/ScalarEvolution.cpp

if (RAR) {
     }
   }
   if (LeftGuarded && RightGuarded)
     return true;
 
   if (isKnownPredicateViaSplitting(Pred, LHS, RHS))
     return true;
 
-  // Otherwise see what can be done with known constant ranges.
-  return isKnownPredicateViaConstantRanges(Pred, LHS, RHS);
+  // Otherwise see what can be done with some simple reasoning.
+  return isKnownViaSimpleReasoning(Pred, LHS, RHS);
 }
 
 bool ScalarEvolution::isMonotonicPredicate(const SCEVAddRecExpr *LHS,
                                            ICmpInst::Predicate Pred,
                                            bool &Increasing) {
   bool Result = isMonotonicPredicateImpl(LHS, Pred, Increasing);
 
 #ifndef NDEBUG

 bool
 ScalarEvolution::isLoopBackedgeGuardedByCond(const Loop *L,
                                              ICmpInst::Predicate Pred,
                                              const SCEV *LHS, const SCEV *RHS) {
   // Interpret a null as meaning no loop, where there is obviously no guard
   // (interprocedural conditions notwithstanding).
   if (!L) return true;
 
-  if (isKnownPredicateViaConstantRanges(Pred, LHS, RHS))
+  if (isKnownViaSimpleReasoning(Pred, LHS, RHS))
     return true;
 
   BasicBlock *Latch = L->getLoopLatch();
   if (!Latch)
     return false;
 
   BranchInst *LoopContinuePredicate =
     dyn_cast<BranchInst>(Latch->getTerminator());
ScalarEvolution::isLoopEntryGuardedByCond(const Loop *L,
   if (!L) return false;
 
   // Both LHS and RHS must be available at loop entry.
   assert(isAvailableAtLoopEntry(LHS, L) &&
          "LHS is not available at Loop Entry");
   assert(isAvailableAtLoopEntry(RHS, L) &&
          "RHS is not available at Loop Entry");
 
-  if (isKnownPredicateViaConstantRanges(Pred, LHS, RHS))
+  if (isKnownViaSimpleReasoning(Pred, LHS, RHS))
     return true;
 
   // If we cannot prove strict comparison (e.g. a > b), maybe we can prove
   // the facts (a >= b && a != b) separately. A typical situation is when the
   // non-strict comparison is known from ranges and non-equality is known from
   // dominating predicates. If we are proving strict comparison, we always try
   // to prove non-equality and non-strict comparison separately.
   auto NonStrictPredicate = ICmpInst::getNonStrictPredicate(Pred);
   const bool ProvingStrictComparison = (Pred != NonStrictPredicate);
   bool ProvedNonStrictComparison = false;
   bool ProvedNonEquality = false;
 
   if (ProvingStrictComparison) {
     ProvedNonStrictComparison =
-        isKnownPredicateViaConstantRanges(NonStrictPredicate, LHS, RHS);
+        isKnownViaSimpleReasoning(NonStrictPredicate, LHS, RHS);
     ProvedNonEquality =
-        isKnownPredicateViaConstantRanges(ICmpInst::ICMP_NE, LHS, RHS);
+        isKnownViaSimpleReasoning(ICmpInst::ICMP_NE, LHS, RHS);
     if (ProvedNonStrictComparison && ProvedNonEquality)
       return true;
   }
 
   // Try to prove (Pred, LHS, RHS) using isImpliedViaGuard.
   auto ProveViaGuard = [&](BasicBlock *Block) {
     if (isImpliedViaGuard(Block, Pred, LHS, RHS))
       return true;

test/Transforms/IndVarSimplify/loop-invariant-conditions.ll

 ; CHECK: %cmp1 = icmp slt i64 %start, -1
   %cmp1 = icmp slt i64 %indvars.iv, -1
   br i1 %cmp1, label %for.end, label %loop
 
 for.end:                                          ; preds = %if.end, %entry
   ret void
 }
 
 !0 = !{i64 0, i64 100}
 
 ; Negative test - we can't show that the internal branch executes, so we can't
 ; fold the test to a loop invariant one.
 define void @test1_neg(i64 %start) {
 ; CHECK-LABEL: @test1_neg
 entry:
   br label %loop
 

 backedge:
   %loopcond = icmp slt i64 %iv, 200
   br i1 %loopcond, label %loop, label %exit
 
 exit:
   ret void
 }
 
+; check that we can prove that a recurrency is greater than another recurrency
+; in the same loop, with the same step, and with smaller starting value.
+define void @test12(i64* %inc_ptr) {
+; CHECK-LABEL: @test12
+entry:
+  %inc = load i64, i64* %inc_ptr, !range !0
+  %inc.minus.1 = sub i64 %inc, 1
+  br label %loop
+
+loop:
+  %iv = phi i64 [ %inc, %entry ], [ %iv.next, %backedge ]
+  %iv.minus.1 = phi i64 [ %inc.minus.1, %entry ], [ %iv.minus.1.next, %backedge ]
+  %iv.next = add i64 %iv, 1
+  %iv.minus.1.next = add i64 %iv.minus.1, 1
+  %brcond = icmp sgt i64 %iv.next, %iv.minus.1.next
+  ; CHECK: br i1 true, label %if.true, label %if.false
+  br i1 %brcond, label %if.true, label %if.false
+
+if.true:
+  br label %backedge
+
+if.false:
+  br label %backedge
+
+backedge:
+  %loopcond = icmp slt i64 %iv, 200
+  br i1 %loopcond, label %loop, label %exit
+
+exit:
+  ret void
+}
+
 !1 = !{i64 -1, i64 100}
 
 
 declare void @foo()