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

6795

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

6787

You mean "not equal to a"?

6808

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

6797

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);
   }
 
+  // Check if we can make progress by sharpening ranges.
+  if (FoundPred == ICmpInst::ICMP_NE &&
+      (isa<SCEVConstant>(FoundLHS) || isa<SCEVConstant>(FoundRHS))) {
+
+    const SCEVConstant *C = nullptr;
+    const SCEV *V = nullptr;
+
+    if (isa<SCEVConstant>(FoundLHS)) {
+      C = cast<SCEVConstant>(FoundLHS);
+      V = FoundRHS;
+    } else {
+      C = cast<SCEVConstant>(FoundRHS);
+      V = FoundLHS;
+    }
+
+    // The guarding predicate tells us that C != V. If the known range
+    // of V is [C, t), we can sharpen the range to [C + 1, t).  The
+    // range we consider has to correspond to same signedness as the
+    // predicate we're interested in folding.
+
+    APInt Min = ICmpInst::isSigned(Pred) ?
+        getSignedRange(V).getSignedMin() : getUnsignedRange(V).getUnsignedMin();
+
+    if (Min == C->getValue()->getValue()) {
+      // Given (V >= Min && V != Min) we conclude V >= (Min + 1).
+      // This is true even if (Min + 1) wraps around -- in case of
+      // wraparound, (Min + 1) < Min, so (V >= Min => V >= (Min + 1)).
+
+      APInt SharperMin = Min + 1;
+
+      switch (Pred) {
+        case ICmpInst::ICMP_SGE:
+        case ICmpInst::ICMP_UGE:
+          // We know V `Pred` SharperMin.  If this implies LHS `Pred`
+          // RHS, we're done.
+          if (isImpliedCondOperands(Pred, LHS, RHS, V,
+                                    getConstant(SharperMin)))
+            return true;
+
+        case ICmpInst::ICMP_SGT:
+        case ICmpInst::ICMP_UGT:
+          // We know from the range information that (V `Pred` Min ||
+          // V == Min).  We know from the guarding condition that !(V
+          // == Min).  This gives us
+          //
+          //       V `Pred` Min || V == Min && !(V == Min)
+          //   =>  V `Pred` Min
+          //
+          // If V `Pred` Min implies LHS `Pred` RHS, we're done.
+
+          if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(Min)))
+            return true;
+
+        default:
+          // No change
+          break;
+      }
+    }
+  }
+
   // 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.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_slt(i32* nocapture readonly %buffer) {
+; CHECK-LABEL: bounded_below_slt
+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:
+; CHECK: 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:
+; CHECK: 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
+}
+
+define i1 @bounded_below_sle(i32* nocapture readonly %buffer) {
+; CHECK-LABEL: bounded_below_sle
+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:
+; CHECK: loop
+  %idx = phi i32 [ %idx.inc, %loop.next ], [ 0, %loop.preheader ]
+  %oob.pred = icmp sle i32 %idx, %length
+  br i1 %oob.pred, label %loop.next, label %oob
+; CHECK: br i1 true, label %loop.next, label %oob
+
+loop.next:
+; CHECK: loop.next
+  %idx.inc = add i32 %idx, 1
+  %exit.pred = icmp sle 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
+}
+
+;; Assert that we're not making an incorrect transform.
+
+declare i32 @check(i8*)
+
+define void @NoChange() {
+; CHECK-LABEL: NoChange
+entry:
+  br label %loop.begin
+
+loop.begin:
+; CHECK: loop.begin:
+  %i.01 = phi i64 [ 2, %entry ], [ %add, %loop.end ]
+  %cmp = icmp ugt i64 %i.01, 1
+; CHECK: %cmp = icmp ugt i64 %i.01, 1
+  br i1 %cmp, label %loop, label %loop.end
+
+loop:
+; CHECK: loop
+  %.sum = add i64 %i.01, -2
+  %v = getelementptr inbounds i8* null, i64 %.sum
+  %r = tail call i32 @check(i8* %v)
+  %c = icmp eq i32 %r, 0
+  br i1 %c, label %loop.end, label %abort.now
+
+abort.now:
+  tail call void @abort()
+  unreachable
+
+loop.end:
+  %add = add i64 %i.01, -1
+  %eq = icmp eq i64 %add, 0
+  br i1 %eq, label %exit, label %loop.begin
+
+exit:
+  ret void
+}
+
+!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