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

[• chenli]

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.

[sanjoy]

lib/Analysis/InstructionSimplify.cpp

2392 ↗

(On Diff #35146)

I don't think this is correct. When an instruction has a !range like [a,b) [c,d), the set of possible values is the union of all of these ranges.

For instance, I think you'll constant fold x slt 10 to true here if the range of x is [0,9) [100,200), even though x can be 120.

I also don't think FirstRangeContainsSecond is a good abstraction, and its name is misleading.

I'd structure this bit of code as:

instead of

if (Lower != Upper) {
  ConstantRange LHS_CR = ConstantRange(Lower, Upper);

  if (Value *RetVal =
      FirstRangeContainsSecond(RHS_CR, LHS_CR, RHS->getContext())) {
    return RetVal;
  }
}

ConstantRange LHS_CR = Lower == Upper ? ConstantRange::getFullSet() : ConstantRange(Lower, Upper);
if (Instruction has !range MD) {
  ConstantRange CR = NullSet;
  for (auto Range : Inst->Ranges) {
    CR = CR.union(RangeMD)
  }
  LHS_CR = LHS_CR.intersect(CR);
}

if (!LHS_CR.isFullSet()) {
  if (RHS_CR.contains(LHS_CR))
  ... // the code as it is today
}

[• chenli]

lib/Analysis/InstructionSimplify.cpp

2392 ↗

(On Diff #35146)

Yes, you are correct. It should check the union of all the ranges here. I will fix it and update the patch.

[• chenli]

lib/Analysis/InstructionSimplify.cpp

2392 ↗

(On Diff #35146)

ConstantRange LHS_CR = Lower == Upper ? ConstantRange::getFullSet() : ConstantRange(Lower, Upper);
if (Instruction has !range MD) {
  ConstantRange CR = NullSet;
  for (auto Range : Inst->Ranges) {
    CR = CR.union(RangeMD)
  }
  LHS_CR = LHS_CR.intersect(CR);
}

The union part will actually give you false positive result. Consider you have a value of ranges [0, 3), [5, 7), and it is compared with == 4. Union the two ranges result a new range [0, 7), which can not be proven not equal to 4, while the original ranges can fold it. So instead of taking the union, it might be better to check each range separately, and return true if RHS_CR contains all ranges and false if RHS_CR.inverse() contains all.

[sanjoy]

lib/Analysis/InstructionSimplify.cpp

2392 ↗

(On Diff #35146)

Agreed. If you can prove some fact about each of the individual ranges separately, then you can assume the fact to be true for the union of the ranges.

However, I suspect in most cases the !range metadata will contain exactly one range (in which case there is no loss of precision when taking the union of all the ranges) so the additional complexity may not be worth it. I'll leave it to you to make the final decision on this.

[• chenli]

lib/Analysis/InstructionSimplify.cpp

2392 ↗

(On Diff #35146)

I think that makes sense. I will take the general approach (union) first, and improve it if it shows profitable in practice in the future.

[• chenli]

Update patch w.r.t Sanjoy's comments.

[sanjoy]

lib/Analysis/InstructionSimplify.cpp

2131 ↗

(On Diff #35163)

I'm still not very happy with the interface here -- I'd rather have this function do *just* the metadata parsing; and have the dyn_cast<Instruction>(..) logic in its caller. I'd also rename this GetConstantRangeFromMetadata (and not repeat "Range" in the CR bit and RangeMetadata):

static ConstantRange GetConstantRangeFromMetadata(MDNode *RangeMD, unsigned BitWidth) {
  ...
}

and in its caller

if (auto *I = dyn_cast<Instruction>(Val))
  if (auto *Ranges = I->getMetadata(LLVMContext::MD_range))
    LHS_CR.intersectWith(GetConstantRangeFromMetadata(Ranges, LHS_BitWidth));

2137 ↗

(On Diff #35163)

Why not ConstantRange CR(BitWidth, false);?

2140 ↗

(On Diff #35163)

[Optional]
This is a matter of style, but I'd have written these as

auto *Low = ...
auto *High = ...

since the types are obvious, and Low, High are briefer.

2146 ↗

(On Diff #35163)

[Optional]
Why not CR.unionWith({Lower->getValue(), Upper->getValue()})? Alternatively, if that does not work, CR.unionWith(ConstantRange(Lower->getValue(), Upper->getValue()))?

2394 ↗

(On Diff #35163)

Can the Width declared in line 2286 be used here? I can't tell if it is out of scope easily from phabricator.

test/Transforms/InstCombine/icmp-range.ll

57 ↗

(On Diff #35163)

Please add a few more test cases. At the very least, add

• one that does not constant fold
• one that folds to false
• one that has a multiple sub ranges in the !range metadata

[• chenli]

Update patch w.r.t Sanjoy's request.

[sanjoy]

I think this looks ready to go in. @hfinkel WDYT?

lib/Analysis/InstructionSimplify.cpp

2131 ↗

(On Diff #35299)

There is also a similar GetRangeFromMetadata function in ScalarEvolution. As a later patch you might want to common the two (totally optional).

2133 ↗

(On Diff #35299)

Since you're asserting here anyway, I'd make this stronger: assert(NumRanges >= 1 && Ranges->getNumOperands() % 2 == 0 && "Ill formed IR!");

[hfinkel]

In D12988#250239, @sanjoy wrote:

I think this looks ready to go in. @hfinkel WDYT?

LGTM too. There is obviously more than can be done here (where we propagate ranges through expressions), but that likely belongs in LVI.

[• chenli]

In D12988#251593, @hfinkel wrote:

In D12988#250239, @sanjoy wrote:

I think this looks ready to go in. @hfinkel WDYT?

LGTM too. There is obviously more than can be done here (where we propagate ranges through expressions), but that likely belongs in LVI.

Thanks! I plan to do some more improvements on LVI after this patch.

llvm/trunk/lib/Analysis/InstructionSimplify.cpp

if ((IsNAC(LHSUObjs) && IsAllocDisjoint(RHSUObjs)) ||
         return ConstantInt::get(GetCompareTy(LHS),
                                 !CmpInst::isTrueWhenEqual(Pred));
   }
 
   // Otherwise, fail.
   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,
                                const Query &Q, unsigned MaxRecurse) {
   CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
   assert(CmpInst::isIntPredicate(Pred) && "Not an integer compare!");
 
   if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
if (match(LHS, m_URem(m_Value(), m_ConstantInt(CI2)))) {
       Lower = CI2->getValue();
     } else if (match(LHS, m_And(m_Value(), m_ConstantInt(CI2)))) {
       // 'and x, CI2' produces [0, CI2].
       Upper = CI2->getValue() + 1;
     } else if (match(LHS, m_NUWAdd(m_Value(), m_ConstantInt(CI2)))) {
       // '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))
         return ConstantInt::getFalse(RHS->getContext());
     }
   }
 
   // Compare of cast, for example (zext X) != 0 -> X != 0

llvm/trunk/test/Transforms/InstCombine/icmp-range.ll

 define i1 @test_nonzero6(i8* %argw) {
 ; CHECK-LABEL: test_nonzero6
 ; CHECK: icmp ne i8 %val, 0
   %val = load i8, i8* %argw, !range !3
   %rval = icmp sgt i8 %val, 0
   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}