From ededc9899f128d2ddd70aea2117fa062820825f3 Mon Sep 17 00:00:00 2001 From: Sanjay Patel Date: Thu, 26 Jul 2018 19:22:41 +0000 Subject: [PATCH] [InstCombine] fold udiv with common factor from muls with nuw Unfortunately, sdiv isn't as simple because of UB due to overflow. This fold is mentioned in PR38239: https://bugs.llvm.org/show_bug.cgi?id=38239 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@338059 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/InstCombine/InstCombineMulDivRem.cpp | 15 +++++++++++++++ test/Transforms/InstCombine/div.ll | 16 ++++------------ 2 files changed, 19 insertions(+), 12 deletions(-) diff --git a/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp b/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp index d6adbec02ac..63761d42723 100644 --- a/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp +++ b/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp @@ -973,6 +973,21 @@ Instruction *InstCombiner::visitUDiv(BinaryOperator &I) { if (Instruction *NarrowDiv = narrowUDivURem(I, Builder)) return NarrowDiv; + // If the udiv operands are non-overflowing multiplies with a common operand, + // then eliminate the common factor: + // (A * B) / (A * X) --> B / X (and commuted variants) + // TODO: The code would be reduced if we had m_c_NUWMul pattern matching. + // TODO: If -reassociation handled this generally, we could remove this. + Value *A, *B; + if (match(Op0, m_NUWMul(m_Value(A), m_Value(B)))) { + if (match(Op1, m_NUWMul(m_Specific(A), m_Value(X))) || + match(Op1, m_NUWMul(m_Value(X), m_Specific(A)))) + return BinaryOperator::CreateUDiv(B, X); + if (match(Op1, m_NUWMul(m_Specific(B), m_Value(X))) || + match(Op1, m_NUWMul(m_Value(X), m_Specific(B)))) + return BinaryOperator::CreateUDiv(A, X); + } + // (LHS udiv (select (select (...)))) -> (LHS >> (select (select (...)))) SmallVector UDivActions; if (visitUDivOperand(Op0, Op1, I, UDivActions)) diff --git a/test/Transforms/InstCombine/div.ll b/test/Transforms/InstCombine/div.ll index a35ebed319a..2bfa549d35a 100644 --- a/test/Transforms/InstCombine/div.ll +++ b/test/Transforms/InstCombine/div.ll @@ -688,9 +688,7 @@ define <2 x i8> @div_factor_unsigned_vec(<2 x i8> %x, <2 x i8> %y) { define i8 @udiv_common_factor(i8 %x, i8 %y, i8 %z) { ; CHECK-LABEL: @udiv_common_factor( -; CHECK-NEXT: [[A:%.*]] = mul nuw i8 [[Z:%.*]], [[X:%.*]] -; CHECK-NEXT: [[B:%.*]] = mul nuw i8 [[Z]], [[Y:%.*]] -; CHECK-NEXT: [[C:%.*]] = udiv i8 [[A]], [[B]] +; CHECK-NEXT: [[C:%.*]] = udiv i8 [[X:%.*]], [[Y:%.*]] ; CHECK-NEXT: ret i8 [[C]] ; %a = mul nuw i8 %z, %x @@ -701,9 +699,7 @@ define i8 @udiv_common_factor(i8 %x, i8 %y, i8 %z) { define <2 x i8> @udiv_common_factor_commute1_vec(<2 x i8> %x, <2 x i8> %y, <2 x i8> %z) { ; CHECK-LABEL: @udiv_common_factor_commute1_vec( -; CHECK-NEXT: [[A:%.*]] = mul nuw <2 x i8> [[X:%.*]], [[Z:%.*]] -; CHECK-NEXT: [[B:%.*]] = mul nuw <2 x i8> [[Z]], [[Y:%.*]] -; CHECK-NEXT: [[C:%.*]] = udiv <2 x i8> [[A]], [[B]] +; CHECK-NEXT: [[C:%.*]] = udiv <2 x i8> [[X:%.*]], [[Y:%.*]] ; CHECK-NEXT: ret <2 x i8> [[C]] ; %a = mul nuw <2 x i8> %x, %z @@ -714,9 +710,7 @@ define <2 x i8> @udiv_common_factor_commute1_vec(<2 x i8> %x, <2 x i8> %y, <2 x define i8 @udiv_common_factor_commute2(i8 %x, i8 %y, i8 %z) { ; CHECK-LABEL: @udiv_common_factor_commute2( -; CHECK-NEXT: [[A:%.*]] = mul nuw i8 [[X:%.*]], [[Z:%.*]] -; CHECK-NEXT: [[B:%.*]] = mul nuw i8 [[Y:%.*]], [[Z]] -; CHECK-NEXT: [[C:%.*]] = udiv i8 [[A]], [[B]] +; CHECK-NEXT: [[C:%.*]] = udiv i8 [[X:%.*]], [[Y:%.*]] ; CHECK-NEXT: ret i8 [[C]] ; %a = mul nuw i8 %x, %z @@ -727,9 +721,7 @@ define i8 @udiv_common_factor_commute2(i8 %x, i8 %y, i8 %z) { define i8 @udiv_common_factor_commute3(i8 %x, i8 %y, i8 %z) { ; CHECK-LABEL: @udiv_common_factor_commute3( -; CHECK-NEXT: [[A:%.*]] = mul nuw i8 [[Z:%.*]], [[X:%.*]] -; CHECK-NEXT: [[B:%.*]] = mul nuw i8 [[Y:%.*]], [[Z]] -; CHECK-NEXT: [[C:%.*]] = udiv i8 [[A]], [[B]] +; CHECK-NEXT: [[C:%.*]] = udiv i8 [[X:%.*]], [[Y:%.*]] ; CHECK-NEXT: ret i8 [[C]] ; %a = mul nuw i8 %z, %x -- 2.11.0