[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
llvm-svn: 338059
diff --git a/llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp b/llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
index d6adbec..63761d42 100644
--- a/llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
+++ b/llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
@@ -973,6 +973,21 @@
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<UDivFoldAction, 6> UDivActions;
if (visitUDivOperand(Op0, Op1, I, UDivActions))