[InstCombine] Fold icmp eq/ne (udiv i32 A, B), 0 -> icmp ugt/ule B, A

[mcrosier]

Summary

Please take a look,
Chad

[mcrosier]

Add full context.

[majnemer]

lib/Transforms/InstCombine/InstCombineCompares.cpp

1549 ↗

(On Diff #56475)

Why do you need to do this ConstantInt::get call? Shouldn't A and CI2 have the same type?

[majnemer]

lib/Transforms/InstCombine/InstCombineCompares.cpp

1543–1550 ↗

(On Diff #56475)

This transform is valid regardless of what value CI2 holds. We should require it to be a ConstantInt.

test/Transforms/InstCombine/compare-udiv.ll

3–9 ↗

(On Diff #56475)

This transform is valid, regardless of what value the numerator is. We shouldn't require a constant here.

11–17 ↗

(On Diff #56475)

It'd be good to have a version of this test where the numerator is -1.

[mcrosier]

Address David's comments:
-Handle both constant and non-constant numerator.
-Add test with -1 numerator.

[majnemer]

LGTM

[mcrosier]

Committed in r268960. I did have to move the optimizations after visitICmpInstWithInstAndIntCst() in order to not regress udiv_icmp1 in exact.ll. Also, I added an additional test case, udiv_icmp2, to provide more context and to improve coverage.

llvm/trunk/lib/Transforms/InstCombine/InstCombineCompares.cpp

case Instruction::UDiv:
     // 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
if (I.hasOneUse())
     if (SelectInst *SI = dyn_cast<SelectInst>(*I.user_begin()))
       if ((SI->getOperand(1) == Op0 && SI->getOperand(2) == Op1) ||
           (SI->getOperand(2) == Op0 && SI->getOperand(1) == Op1))
         return nullptr;
 
   // See if we are doing a comparison between a constant and an instruction that
   // can be folded into the comparison.
   if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
+    Value *A = nullptr, *B = nullptr;
     // Since the RHS is a ConstantInt (CI), if the left hand side is an
     // instruction, see if that instruction also has constants so that the
     // instruction can be folded into the icmp
     if (Instruction *LHSI = dyn_cast<Instruction>(Op0))
       if (Instruction *Res = visitICmpInstWithInstAndIntCst(I, LHSI, CI))
         return Res;
+
+    // (icmp eq/ne (udiv A, B), 0) -> (icmp ugt/ule i32 B, A)
+    if (I.isEquality() && CI->isZero() &&
+        match(Op0, m_UDiv(m_Value(A), m_Value(B)))) {
+      ICmpInst::Predicate Pred = I.getPredicate() == ICmpInst::ICMP_EQ
+                                     ? ICmpInst::ICMP_UGT
+                                     : ICmpInst::ICMP_ULE;
+      return new ICmpInst(Pred, B, A);
+    }
   }
 
   // Handle icmp with constant (but not simple integer constant) RHS
   if (Constant *RHSC = dyn_cast<Constant>(Op1)) {
     if (Instruction *LHSI = dyn_cast<Instruction>(Op0))
       switch (LHSI->getOpcode()) {
       case Instruction::GetElementPtr:
           // icmp pred GEP (P, int 0, int 0, int 0), null -> icmp pred P, null

llvm/trunk/test/Transforms/InstCombine/compare-udiv.ll

+; RUN: opt -instcombine -S < %s | FileCheck %s
+
+; CHECK-LABEL: @test1
+; CHECK: %cmp1 = icmp ugt i32 %d, %n
+define i1 @test1(i32 %n, i32 %d) {
+  %div = udiv i32 %n, %d
+  %cmp1 = icmp eq i32 %div, 0
+  ret i1 %cmp1
+}
+
+; CHECK-LABEL: @test2
+; CHECK: %cmp1 = icmp ugt i32 %d, 64
+define i1 @test2(i32 %d) {
+  %div = udiv i32 64, %d
+  %cmp1 = icmp eq i32 %div, 0
+  ret i1 %cmp1
+}
+
+; CHECK-LABEL: @test3
+; CHECK: %cmp1 = icmp ule i32 %d, %n
+define i1 @test3(i32 %n, i32 %d) {
+  %div = udiv i32 %n, %d
+  %cmp1 = icmp ne i32 %div, 0
+  ret i1 %cmp1
+}
+
+; CHECK-LABEL: @test4
+; CHECK: %cmp1 = icmp ult i32 %d, 65
+define i1 @test4(i32 %d) {
+  %div = udiv i32 64, %d
+  %cmp1 = icmp ne i32 %div, 0
+  ret i1 %cmp1
+}
+
+; 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
+}

llvm/trunk/test/Transforms/InstCombine/exact.ll

 ; CHECK-LABEL: @udiv_icmp1(
 ; CHECK: icmp ne i64 %X, 0
 define i1 @udiv_icmp1(i64 %X) nounwind {
   %A = udiv exact i64 %X, 5   ; X/5
   %B = icmp ne i64 %A, 0
   ret i1 %B
 }
 
+; CHECK-LABEL: @udiv_icmp2(
+; CHECK: icmp eq i64 %X, 0
+define i1 @udiv_icmp2(i64 %X) nounwind {
+  %A = udiv exact i64 %X, 5   ; X/5 == 0 --> x == 0
+  %B = icmp eq i64 %A, 0
+  ret i1 %B
+}
+
 ; CHECK-LABEL: @sdiv_icmp1(
 ; CHECK: icmp eq i64 %X, 0
 define i1 @sdiv_icmp1(i64 %X) nounwind {
   %A = sdiv exact i64 %X, 5   ; X/5 == 0 --> x == 0
   %B = icmp eq i64 %A, 0
   ret i1 %B
 }