[InstCombine] Fold icmp ugt/ult (udiv i32 C2, X), C1

[mcrosier]

Summary

Please take a look,
Chad

[majnemer]

lib/Transforms/InstCombine/InstCombineCompares.cpp

2103–2106

What if C1 is -1? Won't this divide by zero?

[majnemer]

LGTM with nits.

lib/Transforms/InstCombine/InstCombineCompares.cpp

2103–2106

Ah, you have a test for this case, it is handled by InstSimplify.

Please add an assertion for this like you do for C1 != 0 below.

lib/Transforms/InstCombine/InstCombineCompares.cpp

case Instruction::AShr: {
     // Handle exact shr's.
     if (ICI.isEquality() && BO->isExact() && BO->hasOneUse()) {
       if (RHSV.isMinValue())
         return new ICmpInst(ICI.getPredicate(), BO->getOperand(0), RHS);
     }
     break;
   }
 
-  case Instruction::SDiv:
   case Instruction::UDiv:
+    if (ConstantInt *DivLHS = dyn_cast<ConstantInt>(LHSI->getOperand(0))) {
+      Value *X = LHSI->getOperand(1);
+      ICmpInst::Predicate Pred = ICI.getPredicate();
+      APInt C1 = RHS->getValue();
+      APInt C2 = DivLHS->getValue();
+      assert(C2 != 0 && "udiv 0, X should have been simplified already.");
+      // (icmp ugt (udiv C2, X), C1) -> (icmp ule X, C2/(C1+1))
+      if (Pred == ICmpInst::ICMP_UGT)
+        return new ICmpInst(ICmpInst::ICMP_ULE, X,
+                            ConstantInt::get(X->getType(), C2.udiv(C1 + 1)));
+      // (icmp ult (udiv C2, X), C1) -> (icmp ugt X, C2/C1)
+      if (Pred == ICmpInst::ICMP_ULT) {
+        assert(C1 != 0 && "icmp ult X, 0 should have been simplified already.");
+        return new ICmpInst(ICmpInst::ICMP_UGT, X,
+                            ConstantInt::get(X->getType(), C2.udiv(C1)));
+      }
+    }
+  // fall-through
+  case Instruction::SDiv:
     // Fold: icmp pred ([us]div X, C1), C2 -> range test
     // Fold this div into the comparison, producing a range check.
     // Determine, based on the divide type, what the range is being
     // checked.  If there is an overflow on the low or high side, remember
     // it, otherwise compute the range [low, hi) bounding the new value.
     // See: InsertRangeTest above for the kinds of replacements possible.
     if (ConstantInt *DivRHS = dyn_cast<ConstantInt>(LHSI->getOperand(1)))
       if (Instruction *R = FoldICmpDivCst(ICI, cast<BinaryOperator>(LHSI),
                                           DivRHS))
         return R;
-    // FIXME: Handle (icmp ugt (udiv i32 CI2, A), CI) and
-    // (icmp ult (udiv i32 CI2, A), CI).
     break;
 
   case Instruction::Sub: {
     ConstantInt *LHSC = dyn_cast<ConstantInt>(LHSI->getOperand(0));
     if (!LHSC) break;
     const APInt &LHSV = LHSC->getValue();
 
     // C1-X <u C2 -> (X|(C2-1)) == C1

test/Transforms/InstCombine/compare-udiv.ll

 
 ; CHECK-LABEL: @test5
 ; CHECK: ret i1 true
 define i1 @test5(i32 %d) {
   %div = udiv i32 -1, %d
   %cmp1 = icmp ne i32 %div, 0
   ret i1 %cmp1
 }
+
+; CHECK-LABEL: @test6
+; CHECK: %cmp1 = icmp ult i32 %d, 6
+define i1 @test6(i32 %d) {
+  %div = udiv i32 5, %d
+  %cmp1 = icmp ugt i32 %div, 0
+  ret i1 %cmp1
+}
+
+; (icmp ugt (udiv C1, X), C1) -> false.
+; CHECK-LABEL: @test7
+; CHECK: ret i1 false
+define i1 @test7(i32 %d) {
+  %div = udiv i32 8, %d
+  %cmp1 = icmp ugt i32 %div, 8
+  ret i1 %cmp1
+}
+
+; CHECK-LABEL: @test8
+; CHECK: %cmp1 = icmp ult i32 %d, 2
+define i1 @test8(i32 %d) {
+  %div = udiv i32 4, %d
+  %cmp1 = icmp ugt i32 %div, 3
+  ret i1 %cmp1
+}
+
+; CHECK-LABEL: @test9
+; CHECK: %cmp1 = icmp ult i32 %d, 2
+define i1 @test9(i32 %d) {
+  %div = udiv i32 4, %d
+  %cmp1 = icmp ugt i32 %div, 2
+  ret i1 %cmp1
+}
+
+; CHECK-LABEL: @test10
+; CHECK: %cmp1 = icmp ult i32 %d, 3
+define i1 @test10(i32 %d) {
+  %div = udiv i32 4, %d
+  %cmp1 = icmp ugt i32 %div, 1
+  ret i1 %cmp1
+}
+
+; CHECK-LABEL: @test11
+; CHECK: %cmp1 = icmp ugt i32 %d, 4
+define i1 @test11(i32 %d) {
+  %div = udiv i32 4, %d
+  %cmp1 = icmp ult i32 %div, 1
+  ret i1 %cmp1
+}
+
+; CHECK-LABEL: @test12
+; CHECK: %cmp1 = icmp ugt i32 %d, 2
+define i1 @test12(i32 %d) {
+  %div = udiv i32 4, %d
+  %cmp1 = icmp ult i32 %div, 2
+  ret i1 %cmp1
+}
+
+; CHECK-LABEL: @test13
+; CHECK: %cmp1 = icmp ugt i32 %d, 1
+define i1 @test13(i32 %d) {
+  %div = udiv i32 4, %d
+  %cmp1 = icmp ult i32 %div, 3
+  ret i1 %cmp1
+}
+
+; CHECK-LABEL: @test14
+; CHECK: %cmp1 = icmp ugt i32 %d, 1
+define i1 @test14(i32 %d) {
+  %div = udiv i32 4, %d
+  %cmp1 = icmp ult i32 %div, 4
+  ret i1 %cmp1
+}
+
+; icmp ugt X, UINT_MAX -> false.
+; CHECK-LABEL: @test15
+; CHECK: ret i1 false
+define i1 @test15(i32 %d) {
+  %div = udiv i32 4, %d
+  %cmp1 = icmp ugt i32 %div, -1
+  ret i1 %cmp1
+}
+
+; icmp ult X, UINT_MAX -> true.
+; CHECK-LABEL: @test16
+; CHECK: ret i1 true
+define i1 @test16(i32 %d) {
+  %div = udiv i32 4, %d
+  %cmp1 = icmp ult i32 %div, -1
+  ret i1 %cmp1
+}