Teach ScalarEvolution to sharpen range information.

[sanjoy]

Summary

This change is dependent on http://reviews.llvm.org/D5638

If x is known to have the range [a, b), in a loop predicated by (icmp ne x, a) its range can be sharpened to [a + 1, b). Get ScalarEvolution and hence IndVars to exploit this fact.

[hfinkel]

Full context here too please.

[sanjoy]

Added full context and fixed a typo in a comment.

[hfinkel]

lib/Analysis/ScalarEvolution.cpp

6539

Don't need {} here.

[sanjoy]

Address Hal's review.

[atrick]

There are a couple obvious typos. Please make sure those are fixed to match your intentions.

Otherwise, I think this is fine. I have to admit I had to stare at it for quite some time to understand what's going on, but it does seem like a decent fix for your reasonable test case.

[off the subject of the review a bit]
In general, as we continue piling logic into SCEV I would encourage you to at least run some basic compile-time measurements. One way to do this is to link a bunch of IR files together and run opt -O2 -time-passes.

lib/Analysis/ScalarEvolution.cpp

6531

You mean "not equal to a"?

6552

Why is this line pasted twice?

[sanjoy]

In D5639#12, @atrick wrote:

There are a couple obvious typos. Please make sure those are fixed to match your intentions.

Will fix, thanks! Just to be clear -- is this okay to check in after those changes or should I re-upload for review?

Otherwise, I think this is fine. I have to admit I had to stare at it for quite some time to understand what's going on, but it does seem like a decent fix for your reasonable test case.

An interesting thing related to the test case: if you change the entry block to

entry:
  %length = load i32* %buffer ;; this line changed (!range removed)
  %entry.pred = icmp slt i32 %length, 1 ;; this line changed (eq => slt)
  br i1 %entry.pred, label %abort, label %loop.preheader

llvm TOT at -O3 will optimize away %oob.pred just fine. But adding the !range metadata makes -instcombine kick in and optimize %length slt 1 to %length eq 0 (the two are equivalent if the msb of %length is 0) clobbering the -indvars optimization. So, on llvm TOT, there is at least one case where adding a !range annotation regresses performance at -O3. This patch fixes that issue too.

[off the subject of the review a bit]
In general, as we continue piling logic into SCEV I would encourage you to at least run some basic compile-time measurements. One way to do this is to link a bunch of IR files together and run opt -O2 -time-passes.

Thanks, will keep that in mind.

[atrick]

LGTM once the typos are fixed.

[sanjoy]

This change broke the PushAndPopWithPoisoningTest asan unit test, so I reverted it. I'm looking into why it broke.

[sanjoy]

lib/Analysis/ScalarEvolution.cpp

6541

This line is incorrect -- below in the switch I've assumed that Min is the unsharpened minimum value.

[sanjoy]

The bug was that the code in the switch...case invoking isImpliedCondOperands assumed Min was the unsharpened minimum. This version of the patch fixes the issue and adds a regression test that would've caught the bug.

The earlier patch was also needlessly complex -- I've simplified the code structure in this revision.

Sorry for the confusion!

[sanjoy]

Ping!

Is this revised version of the change okay to land?

[atrick]

LGTM, again.

lib/Analysis/ScalarEvolution.cpp

bool ScalarEvolution::isImpliedCond(ICmpInst::Predicate Pred,
   if (ICmpInst::getSwappedPredicate(FoundPred) == Pred) {
     if (isa<SCEVConstant>(RHS))
       return isImpliedCondOperands(Pred, LHS, RHS, FoundRHS, FoundLHS);
     else
       return isImpliedCondOperands(ICmpInst::getSwappedPredicate(Pred),
                                    RHS, LHS, FoundLHS, FoundRHS);
   }
 
+  if (FoundPred == ICmpInst::ICMP_NE) {
+    // If we are predicated on something with range [a, b) and known
+    // not equal to a or b, our range effectively is [a + 1, b).  Use
+    // this fact.
+    auto CheckRange = [this, Pred, LHS, RHS](const SCEV *C, const SCEV *V) {
+      if (!isa<SCEVConstant>(C)) return false;
+
+      ConstantInt *CI = cast<SCEVConstant>(C)->getValue();
+      APInt Min = ICmpInst::isSigned(Pred) ?
+        getSignedRange(V).getSignedMin() : getUnsignedRange(V).getUnsignedMin();
+
+      if (Min!= CI->getValue()) return false; // nothing to sharpen
+      Min++;
+
+      // We know V >= Min, in the same signedness as in Pred.  We can
+      // use this to simplify slt and ult.  If the range had a single
+      // value, Min, we now know that FoundValue can never be true;
+      // and any answer is a correct answer.
+
+      switch (Pred) {
+        case ICmpInst::ICMP_SGT:
+        case ICmpInst::ICMP_UGT:
+          return isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(Min));
+          return isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(Min));
+
+        default:
+          llvm_unreachable("don't call with predicates other than ICMP_SGT "
+                           "and ICMP_UGT");
+      }
+    };
+
+    if ((Pred == ICmpInst::ICMP_SGT) || (Pred == ICmpInst::ICMP_UGT)) {
+      // Inequality is reflexive -- check both the combinations.
+      if (CheckRange(FoundLHS, FoundRHS) || CheckRange(FoundRHS, FoundLHS)) {
+        return true;
+      }
+    }
+  }
+
   // Check whether the actual condition is beyond sufficient.
   if (FoundPred == ICmpInst::ICMP_EQ)
     if (ICmpInst::isTrueWhenEqual(Pred))
       if (isImpliedCondOperands(Pred, LHS, RHS, FoundLHS, FoundRHS))
         return true;
   if (Pred == ICmpInst::ICMP_NE)
     if (!ICmpInst::isTrueWhenEqual(FoundPred))
       if (isImpliedCondOperands(FoundPred, LHS, RHS, FoundLHS, FoundRHS))

test/Transforms/IndVarSimplify/sharpen-range-metadata.ll

+;; RUN: opt -S < %s -indvars | FileCheck %s
+
+;; Check if llvm can narrow !range metadata based on loop entry
+;; predicates.
+
+declare void @abort()
+
+define i1 @bounded_below(i32* nocapture readonly %buffer) {
+entry:
+  %length = load i32* %buffer, !range !0
+  %entry.pred = icmp eq i32 %length, 0
+  br i1 %entry.pred, label %abort, label %loop.preheader
+
+loop.preheader:
+  br label %loop
+
+loop:
+  %idx = phi i32 [ %idx.inc, %loop.next ], [ 0, %loop.preheader ]
+  %oob.pred = icmp slt i32 %idx, %length
+  br i1 %oob.pred, label %loop.next, label %oob
+; CHECK: br i1 true, label %loop.next, label %oob
+
+loop.next:
+  %idx.inc = add i32 %idx, 1
+  %exit.pred = icmp slt i32 %idx.inc, %length
+  br i1 %exit.pred, label %loop, label %abort.loopexit
+
+abort.loopexit:
+  br label %abort
+
+abort:
+  ret i1 false
+
+oob:
+  tail call void @abort()
+  ret i1 false
+}
+
+!0 = metadata !{i32 0, i32 100}

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

 ; CHECK: %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
 ; CHECK: %cmp2.us = icmp slt 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
-  %cmp23 = icmp eq i8 %limit, 0
-  br i1 %cmp23, label %for.cond1.preheader, label %for.cond1.preheader.us
+  br i1 undef, label %for.cond1.preheader, label %for.cond1.preheader.us
 
 for.cond1.preheader.us:
   %storemerge5.us = phi i32 [ 0, %entry ], [ %inc14.us, %for.inc13.us ]
   br i1 true, label %for.body4.lr.ph.us, label %for.inc13.us
 
 for.inc13.us:
   %inc14.us = add nsw i32 %storemerge5.us, 1
   %cmp.us = icmp slt i32 %inc14.us, 4