From fab575cbcb0351ff40475853b3235d21b63de6e7 Mon Sep 17 00:00:00 2001
From: Sanjay Patel <spatel@rotateright.com>
Date: Sun, 11 Feb 2018 17:20:32 +0000
Subject: [PATCH] [InstCombine] X / (X * Y) -> 1 / Y if the multiplication does
 not overflow

The related cases for (X * Y) / X were handled in rL124487.

https://rise4fun.com/Alive/6k9

The division in these tests is subsequently eliminated by existing instcombines
for 1/X.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@324843 91177308-0d34-0410-b5e6-96231b3b80d8
---
 .../InstCombine/InstCombineMulDivRem.cpp           | 11 +++++++++
 test/Transforms/InstCombine/div.ll                 | 26 ++++++++++++----------
 2 files changed, 25 insertions(+), 12 deletions(-)

diff --git a/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp b/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
index b9d8e8fdc4d..9770e302b7f 100644
--- a/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
+++ b/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
@@ -1016,6 +1016,17 @@ Instruction *InstCombiner::commonIDivTransforms(BinaryOperator &I) {
   if (!IsSigned && match(Op0, m_NUWShl(m_Specific(Op1), m_Value(Y))))
     return BinaryOperator::CreateNUWShl(ConstantInt::get(I.getType(), 1), Y);
 
+  // X / (X * Y) -> 1 / Y if the multiplication does not overflow.
+  if (match(Op1, m_c_Mul(m_Specific(Op0), m_Value(Y)))) {
+    bool HasNSW = cast<OverflowingBinaryOperator>(Op1)->hasNoSignedWrap();
+    bool HasNUW = cast<OverflowingBinaryOperator>(Op1)->hasNoUnsignedWrap();
+    if ((IsSigned && HasNSW) || (!IsSigned && HasNUW)) {
+      I.setOperand(0, ConstantInt::get(I.getType(), 1));
+      I.setOperand(1, Y);
+      return &I;
+    }
+  }
+
   return nullptr;
 }
 
diff --git a/test/Transforms/InstCombine/div.ll b/test/Transforms/InstCombine/div.ll
index a94b29fdb3f..a3b95cb0ed9 100644
--- a/test/Transforms/InstCombine/div.ll
+++ b/test/Transforms/InstCombine/div.ll
@@ -563,12 +563,13 @@ define <2 x i8> @PR34841(<2 x i8> %x) {
   ret <2 x i8> %div
 }
 
-; (X / (X * Y) -> 1 / Y if the multiplication does not overflow
+; X / (X * Y) -> 1 / Y if the multiplication does not overflow
 
 define i8 @div_factor_signed(i8 %x, i8 %y) {
 ; CHECK-LABEL: @div_factor_signed(
-; CHECK-NEXT:    [[A:%.*]] = mul nsw i8 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = sdiv i8 [[X]], [[A]]
+; CHECK-NEXT:    [[TMP1:%.*]] = add i8 [[Y:%.*]], 1
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp ult i8 [[TMP1]], 3
+; CHECK-NEXT:    [[R:%.*]] = select i1 [[TMP2]], i8 [[Y]], i8 0
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %a = mul nsw i8 %x, %y
@@ -576,12 +577,13 @@ define i8 @div_factor_signed(i8 %x, i8 %y) {
   ret i8 %r
 }
 
-; (X / (Y * X) -> 1 / Y if the multiplication does not overflow
+; X / (Y * X) -> 1 / Y if the multiplication does not overflow
 
 define <2 x i8> @div_factor_signed_vec(<2 x i8> %x, <2 x i8> %y) {
 ; CHECK-LABEL: @div_factor_signed_vec(
-; CHECK-NEXT:    [[A:%.*]] = mul nsw <2 x i8> [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = sdiv <2 x i8> [[X]], [[A]]
+; CHECK-NEXT:    [[TMP1:%.*]] = add <2 x i8> [[Y:%.*]], <i8 1, i8 1>
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp ult <2 x i8> [[TMP1]], <i8 3, i8 3>
+; CHECK-NEXT:    [[R:%.*]] = select <2 x i1> [[TMP2]], <2 x i8> [[Y]], <2 x i8> zeroinitializer
 ; CHECK-NEXT:    ret <2 x i8> [[R]]
 ;
   %a = mul nsw <2 x i8> %y, %x
@@ -589,12 +591,12 @@ define <2 x i8> @div_factor_signed_vec(<2 x i8> %x, <2 x i8> %y) {
   ret <2 x i8> %r
 }
 
-; (X / (Y * X) -> 1 / Y if the multiplication does not overflow
+; X / (Y * X) -> 1 / Y if the multiplication does not overflow
 
 define i8 @div_factor_unsigned(i8 %x, i8 %y) {
 ; CHECK-LABEL: @div_factor_unsigned(
-; CHECK-NEXT:    [[A:%.*]] = mul nuw i8 [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = udiv i8 [[X]], [[A]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i8 [[Y:%.*]], 1
+; CHECK-NEXT:    [[R:%.*]] = zext i1 [[TMP1]] to i8
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %a = mul nuw i8 %y, %x
@@ -602,12 +604,12 @@ define i8 @div_factor_unsigned(i8 %x, i8 %y) {
   ret i8 %r
 }
 
-; (X / (X * Y) -> 1 / Y if the multiplication does not overflow
+; X / (X * Y) -> 1 / Y if the multiplication does not overflow
 
 define <2 x i8> @div_factor_unsigned_vec(<2 x i8> %x, <2 x i8> %y) {
 ; CHECK-LABEL: @div_factor_unsigned_vec(
-; CHECK-NEXT:    [[A:%.*]] = mul nuw <2 x i8> [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = udiv <2 x i8> [[X]], [[A]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq <2 x i8> [[Y:%.*]], <i8 1, i8 1>
+; CHECK-NEXT:    [[R:%.*]] = zext <2 x i1> [[TMP1]] to <2 x i8>
 ; CHECK-NEXT:    ret <2 x i8> [[R]]
 ;
   %a = mul nuw <2 x i8> %x, %y
-- 
2.11.0