[InstCombine] Transform `icmp eq/ne ({su}div exact X,Y),C` -> `icmp eq/ne X, Y*C`

[goldstein.w.n]

Summary

We can do this if Y*C doesn't overflow. This is trivial if C is
0/1. Otherwise we actually generate a mul instruction iff the div
has one use.

Alive2 Links:

udiv: https://alive2.llvm.org/ce/z/GWPW67
sdiv: https://alive2.llvm.org/ce/z/bUoX9h

[goldstein.w.n]

ping.

[nikic]

LGTM

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

3331–3332

Drop this part of the comment, it does not reflect the implementation.

3339

Check hasOneUse() first here.

[nikic]

I'd also suggest to update the proofs to match what you are actually implementing. The current ones are rather roundabout.

[goldstein.w.n]

Fixup some nits

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

if (match(BOp1, m_APInt(BOC)) && BO->hasOneUse() && RHS->isAllOnesValue()) {
       // This removes the -1 constant.
       Constant *NotBOC = ConstantExpr::getNot(cast<Constant>(BOp1));
       Value *And = Builder.CreateAnd(BOp0, NotBOC);
       return new ICmpInst(Pred, And, NotBOC);
     }
     break;
   }
   case Instruction::UDiv:
-    if (C.isZero()) {
+  case Instruction::SDiv:
+    if (BO->isExact()) {
+      // div exact X, Y eq/ne 0 -> X eq/ne 0
+      // div exact X, Y eq/ne 1 -> X eq/ne Y
+      // div exact X, Y eq/ne C ->
+      //    if Y * C never-overflow && OneUse:
+      //      -> Y * C eq/ne X
+      if (C.isZero())
+        return new ICmpInst(Pred, BOp0, Constant::getNullValue(BO->getType()));
+      else if (C.isOne())
+        return new ICmpInst(Pred, BOp0, BOp1);
+      else if (BO->hasOneUse()) {
+        OverflowResult OR = computeOverflow(
+            Instruction::Mul, BO->getOpcode() == Instruction::SDiv, BOp1,
+            Cmp.getOperand(1), BO);
+        if (OR == OverflowResult::NeverOverflows) {
+          Value *YC =
+              Builder.CreateMul(BOp1, ConstantInt::get(BO->getType(), C));
+          return new ICmpInst(Pred, YC, BOp0);
+        }
+      }
+    }
+    if (BO->getOpcode() == Instruction::UDiv && C.isZero()) {
       // (icmp eq/ne (udiv A, B), 0) -> (icmp ugt/ule i32 B, A)
       auto NewPred = isICMP_NE ? ICmpInst::ICMP_ULE : ICmpInst::ICMP_UGT;
       return new ICmpInst(NewPred, BOp1, BOp0);
     }
     break;
   default:
     break;
   }

llvm/test/Transforms/InstCombine/sdiv-icmp.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -passes=instcombine -S | FileCheck %s
 
 declare void @use.i8(i8)
 define i1 @sdiv_exact_eq_0(i8 %x, i8 %y) {
 ; CHECK-LABEL: @sdiv_exact_eq_0(
-; CHECK-NEXT:    [[D:%.*]] = sdiv exact i8 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[D]], 0
+; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[X:%.*]], 0
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %d = sdiv exact i8 %x, %y
   %r = icmp eq i8 %d, 0
   ret i1 %r
 }
 
 define i1 @udiv_exact_ne_0(i8 %x, i8 %y) {
 ; CHECK-LABEL: @udiv_exact_ne_0(
-; CHECK-NEXT:    [[R:%.*]] = icmp ule i8 [[Y:%.*]], [[X:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ne i8 [[X:%.*]], 0
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %d = udiv exact i8 %x, %y
   %r = icmp ne i8 %d, 0
   ret i1 %r
 }
 
 define i1 @sdiv_exact_ne_1(i8 %x, i8 %y) {
 ; CHECK-LABEL: @sdiv_exact_ne_1(
-; CHECK-NEXT:    [[D:%.*]] = sdiv exact i8 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[D]], 0
+; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[X:%.*]], 0
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %d = sdiv exact i8 %x, %y
   %r = icmp eq i8 %d, 0
   ret i1 %r
 }
 
 define i1 @udiv_exact_eq_1(i8 %x, i8 %y) {
 ; CHECK-LABEL: @udiv_exact_eq_1(
-; CHECK-NEXT:    [[D:%.*]] = udiv exact i8 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp ne i8 [[D]], 1
+; CHECK-NEXT:    [[R:%.*]] = icmp ne i8 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %d = udiv exact i8 %x, %y
   %r = icmp ne i8 %d, 1
   ret i1 %r
 }
 
 define i1 @sdiv_exact_eq_9_no_of(i8 %x, i8 %y) {
 ; CHECK-LABEL: @sdiv_exact_eq_9_no_of(
 ; CHECK-NEXT:    [[YY:%.*]] = and i8 [[Y:%.*]], 7
-; CHECK-NEXT:    [[D:%.*]] = sdiv exact i8 [[X:%.*]], [[YY]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[D]], 9
+; CHECK-NEXT:    [[TMP1:%.*]] = mul nuw nsw i8 [[YY]], 9
+; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[TMP1]], [[X:%.*]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %yy = and i8 %y, 7
   %d = sdiv exact i8 %x, %yy
   %r = icmp eq i8 %d, 9
   ret i1 %r
 }
 
;
   %d = sdiv exact i8 %x, %yy
   %r = icmp eq i8 %d, 9
   ret i1 %r
 }
 
 define i1 @udiv_exact_ne_30_no_of(i8 %x, i8 %y) {
 ; CHECK-LABEL: @udiv_exact_ne_30_no_of(
 ; CHECK-NEXT:    [[YY:%.*]] = and i8 [[Y:%.*]], 7
-; CHECK-NEXT:    [[D:%.*]] = udiv exact i8 [[X:%.*]], [[YY]]
-; CHECK-NEXT:    [[R:%.*]] = icmp ne i8 [[D]], 30
+; CHECK-NEXT:    [[TMP1:%.*]] = mul nuw i8 [[YY]], 30
+; CHECK-NEXT:    [[R:%.*]] = icmp ne i8 [[TMP1]], [[X:%.*]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %yy = and i8 %y, 7
   %d = udiv exact i8 %x, %yy
   %r = icmp ne i8 %d, 30
   ret i1 %r
 }