[Bug 24848] Use range metadata to constant fold comparisons with constant values

Summary:
This is the first part of fixing bug 24848 https://llvm.org/bugs/show_bug.cgi?id=24848.

When range metadata is provided, it should be used to constant fold comparisons with constant values.

Reviewers: sanjoy, hfinkel

Subscribers: llvm-commits

Differential Revision: http://reviews.llvm.org/D12988

llvm-svn: 248402

2 files changed, 89 insertions, 2 deletions

diff --git a/llvm/lib/Analysis/InstructionSimplify.cpp b/llvm/lib/Analysis/InstructionSimplify.cpp
index b6d4c02a9eb..7f27d8882e7 100644
--- a/llvm/lib/Analysis/InstructionSimplify.cpp
+++ b/llvm/lib/Analysis/InstructionSimplify.cpp
@@ -2128,6 +2128,29 @@ static Constant *computePointerICmp(const DataLayout &DL,
   return nullptr;
 }
 
+static ConstantRange GetConstantRangeFromMetadata(MDNode *Ranges, uint32_t BitWidth) {
+  const unsigned NumRanges = Ranges->getNumOperands() / 2;
+  assert(NumRanges >= 1);
+
+  ConstantRange CR(BitWidth, false);
+  for (unsigned i = 0; i < NumRanges; ++i) {
+    auto *Low =
+        mdconst::extract<ConstantInt>(Ranges->getOperand(2 * i + 0));
+    auto *High =
+        mdconst::extract<ConstantInt>(Ranges->getOperand(2 * i + 1));
+
+    // Union will merge two ranges to one and potentially introduce a range
+    // not covered by the original two ranges. For example, [1, 5) and [8, 10)
+    // will become [1, 10). In this case, we can not fold comparison between
+    // constant 6 and a value of the above ranges. In practice, most values
+    // have only one range, so it might not be worth handling this by
+    // introducing additional complexity.
+    CR = CR.unionWith(ConstantRange(Low->getValue(), High->getValue()));
+  }
+
+  return CR;
+}
+
 /// SimplifyICmpInst - Given operands for an ICmpInst, see if we can
 /// fold the result.  If not, this returns null.
 static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
@@ -2364,8 +2387,15 @@ static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
       // 'add nuw x, CI2' produces [CI2, UINT_MAX].
       Lower = CI2->getValue();
     }
-    if (Lower != Upper) {
-      ConstantRange LHS_CR = ConstantRange(Lower, Upper);
+
+    ConstantRange LHS_CR = Lower != Upper ? ConstantRange(Lower, Upper)
+                                          : ConstantRange(Width, true);
+
+    if (auto *I = dyn_cast<Instruction>(LHS))
+      if (auto *Ranges = I->getMetadata(LLVMContext::MD_range))
+        LHS_CR = LHS_CR.intersectWith(GetConstantRangeFromMetadata(Ranges, Width));
+
+    if (!LHS_CR.isFullSet()) {
       if (RHS_CR.contains(LHS_CR))
         return ConstantInt::getTrue(RHS->getContext());
       if (RHS_CR.inverse().contains(LHS_CR))
diff --git a/llvm/test/Transforms/InstCombine/icmp-range.ll b/llvm/test/Transforms/InstCombine/icmp-range.ll
index 041adf76b5e..effcc381697 100644
--- a/llvm/test/Transforms/InstCombine/icmp-range.ll
+++ b/llvm/test/Transforms/InstCombine/icmp-range.ll
@@ -54,8 +54,65 @@ define i1 @test_nonzero6(i8* %argw) {
   ret i1 %rval
 }
 
+; Constant not in range, should return true.
+define i1 @test_not_in_range(i32* nocapture readonly %arg) {
+; CHECK-LABEL: test_not_in_range
+; CHECK: ret i1 true
+  %val = load i32, i32* %arg, !range !0
+  %rval = icmp ne i32 %val, 6
+  ret i1 %rval
+}
+
+; Constant in range, can not fold.
+define i1 @test_in_range(i32* nocapture readonly %arg) {
+; CHECK-LABEL: test_in_range
+; CHECK: icmp ne i32 %val, 3
+  %val = load i32, i32* %arg, !range !0
+  %rval = icmp ne i32 %val, 3
+  ret i1 %rval
+}
+
+; Values in range greater than constant.
+define i1 @test_range_sgt_constant(i32* nocapture readonly %arg) {
+; CHECK-LABEL: test_range_sgt_constant
+; CHECK: ret i1 true
+  %val = load i32, i32* %arg, !range !0
+  %rval = icmp sgt i32 %val, 0
+  ret i1 %rval
+}
+
+; Values in range less than constant.
+define i1 @test_range_slt_constant(i32* nocapture readonly %arg) {
+; CHECK-LABEL: test_range_slt_constant
+; CHECK: ret i1 false
+  %val = load i32, i32* %arg, !range !0
+  %rval = icmp sgt i32 %val, 6
+  ret i1 %rval
+}
+
+; Values in union of multiple sub ranges not equal to constant.
+define i1 @test_multi_range1(i32* nocapture readonly %arg) {
+; CHECK-LABEL: test_multi_range1
+; CHECK: ret i1 true
+  %val = load i32, i32* %arg, !range !4
+  %rval = icmp ne i32 %val, 0
+  ret i1 %rval
+}
+
+; Values in multiple sub ranges not equal to constant, but in
+; union of sub ranges could possibly equal to constant. This
+; in theory could also be folded and might be implemented in 
+; the future if shown profitable in practice.
+define i1 @test_multi_range2(i32* nocapture readonly %arg) {
+; CHECK-LABEL: test_multi_range2
+; CHECK: icmp ne i32 %val, 7
+  %val = load i32, i32* %arg, !range !4
+  %rval = icmp ne i32 %val, 7
+  ret i1 %rval
+}
 
 !0 = !{i32 1, i32 6} 
 !1 = !{i32 0, i32 6} 
 !2 = !{i8 0, i8 1} 
 !3 = !{i8 0, i8 6} 
+!4 = !{i32 1, i32 6, i32 8, i32 10}