Add handling for range metadata in ValueTracking isKnownNonZero

[reames]

Summary

Teach isKnownNonZero to look at range metadata

If we load from a location with range metadata, we can use information about the ranges of the loaded value for optimization purposes. This helps to remove redundant checks and canonicalize checks for other optimization passes.

Currently, these tests are against InstCombine. In theory, all of these should be InstSimplify since we're not inserting any new instructions. Moving the code may follow in a separate change.

[hfinkel]

lib/Analysis/ValueTracking.cpp

1534

space after if; no spaces after ( and before ).

1535

Don't return here... there are other checks below that still might provide information.

[reames]

Addressing Hal's review comments.

Thanks (in particular) for catching the early return issue.

[hfinkel]

Accounting for comments below, LGTM.

lib/Analysis/ValueTracking.cpp

1525

Let's make this a little future-proof. At some point we'll likely support this range metadata on vectors, etc. So let's make this an if and a dyn_cast.

1527

We don't need to construct the ZeroConstant here, just using something like this should work:

const APInt ZeroValue(Ty->getBitWidth(), 0);

[reames]

Closed by commit rL220925 (authored by @reames).

lib/Analysis/ValueTracking.cpp

if (C->isNullValue())
       return false;
     if (isa<ConstantInt>(C))
       // Must be non-zero due to null test above.
       return true;
     // TODO: Handle vectors
     return false;
   }
 
+  if (Instruction* I = dyn_cast<Instruction>(V)) {
+    if (MDNode *Ranges = I->getMetadata(LLVMContext::MD_range)) {
+      // If the possible ranges don't contain zero, then the value is
+      // definitely non-zero.
+      const unsigned NumRanges = Ranges->getNumOperands() / 2;
+      assert(NumRanges >= 1);
+      IntegerType* Ty = cast<IntegerType>(V->getType());
+      ConstantInt* ZeroConstant = ConstantInt::get(Ty, 0);
+      const APInt ZeroValue = ZeroConstant->getValue();
+      for (unsigned i = 0; i < NumRanges; ++i) {
+        ConstantInt *Lower = cast<ConstantInt>(Ranges->getOperand(2*i + 0));
+        ConstantInt *Upper = cast<ConstantInt>(Ranges->getOperand(2*i + 1));
+        ConstantRange Range(Lower->getValue(), Upper->getValue());
+        if( Range.contains(ZeroValue) )
+          return false;
+      }
+      return true;
+    }
+  }
+
   // The remaining tests are all recursive, so bail out if we hit the limit.
   if (Depth++ >= MaxDepth)
     return false;
 
   // Check for pointer simplifications.
   if (V->getType()->isPointerTy()) {
     if (isKnownNonNull(V))
       return true; 

test/Transforms/InstCombine/icmp-range.ll

+; RUN: opt < %s -instcombine -S | FileCheck %s
+; These should be InstSimplify checks, but most of the code
+; is currently only in InstCombine.  TODO: move supporting code
+
+; Definitely out of range
+define i1 @test_nonzero(i32* nocapture readonly %arg) {
+; CHECK-LABEL:test_nonzero
+; CHECK: ret i1 true
+  %val = load i32* %arg, !range !0
+  %rval = icmp ne i32 %val, 0
+  ret i1 %rval
+}
+define i1 @test_nonzero2(i32* nocapture readonly %arg) {
+; CHECK-LABEL:test_nonzero2
+; CHECK: ret i1 false
+  %val = load i32* %arg, !range !0
+  %rval = icmp eq i32 %val, 0
+  ret i1 %rval
+}
+
+; Potentially in range
+define i1 @test_nonzero3(i32* nocapture readonly %arg) {
+; CHECK-LABEL: test_nonzero3
+; Check that this does not trigger - it wouldn't be legal
+; CHECK: icmp
+  %val = load i32* %arg, !range !1
+  %rval = icmp ne i32 %val, 0
+  ret i1 %rval
+}
+
+; Definitely in range
+define i1 @test_nonzero4(i8* nocapture readonly %arg) {
+; CHECK-LABEL: test_nonzero4
+; CHECK: ret i1 false
+  %val = load i8* %arg, !range !2
+  %rval = icmp ne i8 %val, 0
+  ret i1 %rval
+}
+
+define i1 @test_nonzero5(i8* nocapture readonly %arg) {
+; CHECK-LABEL: test_nonzero5
+; CHECK: ret i1 false
+  %val = load i8* %arg, !range !2
+  %rval = icmp ugt i8 %val, 0
+  ret i1 %rval
+}
+
+; Cheaper checks (most values in range meet requirements)
+define i1 @test_nonzero6(i8* %argw) {
+; CHECK-LABEL: test_nonzero6
+; CHECK: icmp ne i8 %val, 0
+  %val = load i8* %argw, !range !3
+  %rval = icmp sgt i8 %val, 0
+  ret i1 %rval
+}
+
+
+!0 = metadata !{i32 1, i32 6} 
+!1 = metadata !{i32 0, i32 6} 
+!2 = metadata !{i8 0, i8 1} 
+!3 = metadata !{i8 0, i8 6}