[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

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

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

test/Transforms/InstCombine/compare-udiv.ll

4–10

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

12–18

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.

lib/Transforms/InstCombine/InstCombineCompares.cpp

Instruction *InstCombiner::FoldICmpCstShlCst(ICmpInst &I, Value *Op, Value *A,
 
   // Shifting const2 will never be equal to const1.
   return getConstant(false);
 }
 
 /// visitICmpInstWithInstAndIntCst - Handle "icmp (instr, intcst)".
 ///
 Instruction *InstCombiner::visitICmpInstWithInstAndIntCst(ICmpInst &ICI,
                                                           Instruction *LHSI,
                                                           ConstantInt *RHS) {
   const APInt &RHSV = RHS->getValue();
 
   switch (LHSI->getOpcode()) {
   case Instruction::Trunc:
     if (RHS->isOne() && RHSV.getBitWidth() > 1) {
       // icmp slt trunc(signum(V)) 1 --> icmp slt V, 1
       Value *V = nullptr;
       if (ICI.getPredicate() == ICmpInst::ICMP_SLT &&
           match(LHSI->getOperand(0), m_Signum(m_Value(V))))
         return new ICmpInst(ICmpInst::ICMP_SLT, V,
                             ConstantInt::get(V->getType(), 1));
     }
     if (ICI.isEquality() && LHSI->hasOneUse()) {
       // Simplify icmp eq (trunc x to i8), 42 -> icmp eq x, 42|highbits if all
if (I.isEquality()) {
         if (Instruction *Inst = FoldICmpCstShrCst(I, Op0, A, CI, CI2))
           return Inst;
       }
       if (match(Op0, m_Shl(m_ConstantInt(CI2), m_Value(A)))) {
         // (icmp eq/ne (shl const2, A), const1)
         if (Instruction *Inst = FoldICmpCstShlCst(I, Op0, A, CI, CI2))
           return Inst;
       }
+      // (icmp eq/ne (udiv A, B), 0) -> (icmp ugt/ule i32 B, A)
+      if (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);
       }
+    }
+    // FIXME: Handle (icmp ugt (udiv i32 CI2, A), CI) and
+    // (icmp ult (udiv i32 CI2, A), CI).
 
     // If this comparison is a normal comparison, it demands all
     // bits, if it is a sign bit comparison, it only demands the sign bit.
     bool UnusedBit;
     isSignBit = isSignBitCheck(I.getPredicate(), CI, UnusedBit);
 
     // Canonicalize icmp instructions based on dominating conditions.
     BasicBlock *Parent = I.getParent();

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
+}