[InstCombine] Fold '(-1 u/ %x) u< %y' to '@llvm.umul.with.overflow' + overflow bit extraction
Summary:
`(-1 u/ %x) u< %y` is one of (3?) common ways to check that
some unsigned multiplication (will not) overflow.
Currently, we don't catch it. We could:
```
----------------------------------------
Name: no overflow
%o0 = udiv i4 -1, %x
%r = icmp ult i4 %o0, %y
=>
%o0 = udiv i4 -1, %x
%n0 = umul_overflow i4 %x, %y
%r = extractvalue {i4, i1} %n0, 1
Done: 1
Optimization is correct!
----------------------------------------
Name: no overflow, swapped
%o0 = udiv i4 -1, %x
%r = icmp ugt i4 %y, %o0
=>
%o0 = udiv i4 -1, %x
%n0 = umul_overflow i4 %x, %y
%r = extractvalue {i4, i1} %n0, 1
Done: 1
Optimization is correct!
----------------------------------------
Name: overflow
%o0 = udiv i4 -1, %x
%r = icmp uge i4 %o0, %y
=>
%o0 = udiv i4 -1, %x
%n0 = umul_overflow i4 %x, %y
%n1 = extractvalue {i4, i1} %n0, 1
%r = xor %n1, -1
Done: 1
Optimization is correct!
----------------------------------------
Name: overflow
%o0 = udiv i4 -1, %x
%r = icmp ule i4 %y, %o0
=>
%o0 = udiv i4 -1, %x
%n0 = umul_overflow i4 %x, %y
%n1 = extractvalue {i4, i1} %n0, 1
%r = xor %n1, -1
Done: 1
Optimization is correct!
```
As it can be observed from tests, while simply forming the `@llvm.umul.with.overflow`
is easy, if we were looking for the inverted answer, then more work needs to be done
to cleanup the now-pointless control-flow that was guarding against division-by-zero.
This is being addressed in follow-up patches.
Reviewers: nikic, spatel, efriedma, xbolva00, RKSimon
Reviewed By: nikic, xbolva00
Subscribers: hiraditya, llvm-commits
Tags: #llvm
Differential Revision: https://reviews.llvm.org/D65143
llvm-svn: 370347
diff --git a/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp b/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
index 1117586..955886c 100644
--- a/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
+++ b/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
@@ -3525,6 +3525,50 @@
Constant::getNullValue(WidestTy));
}
+/// Fold
+/// (-1 u/ x) u< y
+/// to
+/// @llvm.umul.with.overflow(x, y) plus extraction of overflow bit
+/// Note that the comparison is commutative, while inverted (u>=) predicate
+/// will mean that we are looking for the opposite answer.
+static Value *
+foldUnsignedMultiplicationOverflowCheck(ICmpInst &I,
+ InstCombiner::BuilderTy &Builder) {
+ ICmpInst::Predicate Pred;
+ Value *X, *Y;
+ bool NeedNegation;
+ // Look for: (-1 u/ x) u</u>= y
+ if (!I.isEquality() &&
+ match(&I, m_c_ICmp(Pred, m_OneUse(m_UDiv(m_AllOnes(), m_Value(X))),
+ m_Value(Y)))) {
+ // Canonicalize as-if y was on RHS.
+ if (I.getOperand(1) != Y)
+ Pred = I.getSwappedPredicate();
+
+ // Are we checking that overflow does not happen, or does happen?
+ switch (Pred) {
+ case ICmpInst::Predicate::ICMP_ULT:
+ NeedNegation = false;
+ break; // OK
+ case ICmpInst::Predicate::ICMP_UGE:
+ NeedNegation = true;
+ break; // OK
+ default:
+ return nullptr; // Wrong predicate.
+ }
+ } else
+ return nullptr;
+
+ Function *F = Intrinsic::getDeclaration(
+ I.getModule(), Intrinsic::umul_with_overflow, X->getType());
+ CallInst *Call = Builder.CreateCall(F, {X, Y}, "umul");
+ Value *Res = Builder.CreateExtractValue(Call, 1, "umul.ov");
+ if (NeedNegation) // This technically increases instruction count.
+ Res = Builder.CreateNot(Res, "umul.not.ov");
+
+ return Res;
+}
+
/// Try to fold icmp (binop), X or icmp X, (binop).
/// TODO: A large part of this logic is duplicated in InstSimplify's
/// simplifyICmpWithBinOp(). We should be able to share that and avoid the code
@@ -3874,6 +3918,9 @@
}
}
+ if (Value *V = foldUnsignedMultiplicationOverflowCheck(I, Builder))
+ return replaceInstUsesWith(I, V);
+
if (Value *V = foldICmpWithLowBitMaskedVal(I, Builder))
return replaceInstUsesWith(I, V);