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

[• chenli]

Summary

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

If both operands of a comparison have range metadata, they should be used to constant fold the comparison.

[hfinkel]

Minor request below, otherwise, LGTM.

lib/Analysis/InstructionSimplify.cpp

2422

Move this below the check for Satisfied_CR.contains. No need to construct an object we'll never use.

[sanjoy]

lib/Analysis/InstructionSimplify.cpp

2427

I don't think this second is correct. makeSatisfiedRegion returns the range of LHS values that is *guaranteed* to satisfy the predicate "Pred RHS". So if RHS's range is [2, 5) and Pred is ULT, then Satisfied_CR is [0, 2). InversedSatisfied_CR will then be [2, 0) (i.e. all integers unsigned greater than or equal to 2) and so you'll fold the equality to false if LHS_CR is [3,4), even though in that case there is a value of LHS = 3 for which the equality is true.

I think for the negative check you need to do InverseAllowed_CR.contains(LHS_CR) where InverseAllowed_CR is the inverse of what is returned by makeAllowedRegion.

[hfinkel]

lib/Analysis/InstructionSimplify.cpp

2427

I don't understand your example. If we have:

x <u 2

then Satisfied_CR is indeed [0, 2), and the inverse (x >=u 2) should indeed be [2, 0). But if LHS_CR is [3, 4), then the original predicate is false, because 3 is not less than 2.

[sanjoy]

lib/Analysis/InstructionSimplify.cpp

2427

I'm talking about a case where X u< Y and X's range is [3, 4), and Y's range is [2, 5). Then the code as it is now will fold the condition to false (because [3,4) is contained in [2, 0)) when it could be true if X is 3 and Y is 4.

This code is basically checking no X is *guaranteed* to satisfy Pred Y, i.e. there is no such X such that X Pred Y is true for *all* Y, when it should be trying to prove that there is no such X such that X Pred Y for *some* Y.

[hfinkel]

lib/Analysis/InstructionSimplify.cpp

2427

My thought had been that in this case, we have X <u Y, so the Satisfied_CR is [0, 2), and the inverse X >=u Y, has InversedSatisfied_CR of [4, 0), because only if X is >= 4 do we know it satisfies the inequality for all possible values of Y. If X is [3, 4), then it is not contained in either set.

[sanjoy]

lib/Analysis/InstructionSimplify.cpp

2427

I was misreading the code. :/ Sorry for the noise. What's here is fine.

[• chenli]

lib/Analysis/InstructionSimplify.cpp

2427

@hfinkel - Thanks for explaining that for me :)

lib/Analysis/InstructionSimplify.cpp

if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
     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());
     }
   }
 
+  // If both operands have range metadata, use the metadata
+  // to simplify the comparison.
+  if (isa<Instruction>(RHS) && isa<Instruction>(LHS)) {
+    auto RHS_Instr = dyn_cast<Instruction>(RHS);
+    auto LHS_Instr = dyn_cast<Instruction>(LHS);
+
+    if (RHS_Instr->getMetadata(LLVMContext::MD_range) &&
+        LHS_Instr->getMetadata(LLVMContext::MD_range)) {
+      uint32_t BitWidth = Q.DL.getTypeSizeInBits(RHS->getType());
+
+      auto RHS_CR = GetConstantRangeFromMetadata(
+          RHS_Instr->getMetadata(LLVMContext::MD_range), BitWidth);
+      auto LHS_CR = GetConstantRangeFromMetadata(
+          LHS_Instr->getMetadata(LLVMContext::MD_range), BitWidth);
+
+      auto Satisfied_CR = ConstantRange::makeSatisfyingICmpRegion(Pred, RHS_CR);
+      auto InversedSatisfied_CR = ConstantRange::makeSatisfyingICmpRegion(
+          CmpInst::getInversePredicate(Pred), RHS_CR);
+
+      if (Satisfied_CR.contains(LHS_CR))
+        return ConstantInt::getTrue(RHS->getContext());
+      if (InversedSatisfied_CR.contains(LHS_CR))
+        return ConstantInt::getFalse(RHS->getContext());
+    }
+  }
+
   // 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();
     Type *DstTy = LI->getType();
 
     // Turn icmp (ptrtoint x), (ptrtoint/constant) into a compare of the input

test/Transforms/InstCombine/icmp-range.ll

 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
 }
 
+; Values' ranges overlap each other, so it can not be simplified.
+define i1 @test_two_ranges(i32* nocapture readonly %arg1, i32* nocapture readonly %arg2) {
+; CHECK-LABEL: test_two_ranges
+; CHECK: icmp ult i32 %val2, %val1
+  %val1 = load i32, i32* %arg1, !range !5
+  %val2 = load i32, i32* %arg2, !range !6
+  %rval = icmp ult i32 %val2, %val1
+  ret i1 %rval
+}
+
+; Values' ranges do not overlap each other, so it can simplified to false.
+define i1 @test_two_ranges2(i32* nocapture readonly %arg1, i32* nocapture readonly %arg2) {
+; CHECK-LABEL: test_two_ranges2
+; CHECK: ret i1 false
+  %val1 = load i32, i32* %arg1, !range !0
+  %val2 = load i32, i32* %arg2, !range !6
+  %rval = icmp ult i32 %val2, %val1
+  ret i1 %rval
+}
+
+; Values' ranges do not overlap each other, so it can simplified to true.
+define i1 @test_two_ranges3(i32* nocapture readonly %arg1, i32* nocapture readonly %arg2) {
+; CHECK-LABEL: test_two_ranges3
+; CHECK: ret i1 true
+  %val1 = load i32, i32* %arg1, !range !0
+  %val2 = load i32, i32* %arg2, !range !6
+  %rval = icmp ugt i32 %val2, %val1
+  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}
+!5 = !{i32 5, i32 10} 
+!6 = !{i32 8, i32 16}