[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

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

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

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

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

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

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

Why not ConstantRange CR(BitWidth, false);?

2140

[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

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

2378

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

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

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

2133

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.

lib/Analysis/InstructionSimplify.cpp

if ((IsNAC(LHSUObjs) && IsAllocDisjoint(RHSUObjs)) ||
         return ConstantInt::get(GetCompareTy(LHS),
                                 !CmpInst::isTrueWhenEqual(Pred));
   }
 
   // Otherwise, fail.
   return nullptr;
 }
 
+static Value *FirstRangeContainsSecond(ConstantRange &FirstCR, ConstantRange &SecondCR, LLVMContext &Context) {
+  if (FirstCR.contains(SecondCR))
+    return ConstantInt::getTrue(Context);
+  if (FirstCR.inverse().contains(SecondCR))
+    return ConstantInt::getFalse(Context);
+
+  return nullptr;
+}
+
 /// 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 (Constant *CRHS = dyn_cast<Constant>(RHS))
       return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, Q.DL, Q.TLI);
 
     // If we have a constant, make sure it is on the RHS.
     std::swap(LHS, RHS);
     Pred = CmpInst::getSwappedPredicate(Pred);
   }
if (match(LHS, m_URem(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);
-      if (RHS_CR.contains(LHS_CR))
-        return ConstantInt::getTrue(RHS->getContext());
-      if (RHS_CR.inverse().contains(LHS_CR))
-        return ConstantInt::getFalse(RHS->getContext());
+
+      if (Value *RetVal =
+          FirstRangeContainsSecond(RHS_CR, LHS_CR, RHS->getContext())) {
+        return RetVal;
+      }
+    }
+
+    // Try to fold the comparison with range metadata if available.
+    if (Instruction* I = dyn_cast<Instruction>(LHS)) {
+      if (MDNode *Ranges = I->getMetadata(LLVMContext::MD_range)) {
+        const unsigned NumRanges = Ranges->getNumOperands() / 2;
+        assert(NumRanges >= 1);
+        for (unsigned i = 0; i < NumRanges; ++i) {
+          ConstantInt *LowerBound =
+              mdconst::extract<ConstantInt>(Ranges->getOperand(2 * i + 0));
+          ConstantInt *UpperBound =
+              mdconst::extract<ConstantInt>(Ranges->getOperand(2 * i + 1));
+          ConstantRange Range(LowerBound->getValue(), UpperBound->getValue());
+
+          if (Value *RetVal =
+              FirstRangeContainsSecond(RHS_CR, Range, RHS->getContext())) {
+            return RetVal;
+          }
+        }
+      }
     }
   }
 
   // Compare of cast, for example (zext X) != 0 -> X != 0
   if (isa<CastInst>(LHS) && (isa<Constant>(RHS) || isa<CastInst>(RHS))) {
     Instruction *LI = cast<CastInst>(LHS);
     Value *SrcOp = LI->getOperand(0);
     Type *SrcTy = SrcOp->getType();

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 !1
+  %rval = icmp ne i32 %val, 6
+  ret i1 %rval
+}
 
 !0 = !{i32 1, i32 6} 
 !1 = !{i32 0, i32 6} 
 !2 = !{i8 0, i8 1} 
 !3 = !{i8 0, i8 6}