Add optimization for 'icmp slt (or A, B), A' and some related idioms based on knowledge of the sign bit for A and B.
No matter what value you OR in to A, the result of (or A, B) is going to be UGE A. When A and B are positive, it's SGE too. If A is negative, OR'ing a value into it can't make it positive, but can increase its value closer to -1, therefore (or A, B) is SGE A. Working through all possible combinations produces this truth table:
```
A is
+, -, +/-
F F F + B is
T F ? -
? F ? +/-
```
The related optimizations are flipping the 'slt' for 'sge' which always NOTs the result (if the result is known), and swapping the LHS and RHS while swapping the comparison predicate.
There are more idioms left to implement (aren't there always!) but I've stopped here because any more would risk becoming unreasonable for reviewers.
llvm-svn: 266939
diff --git a/llvm/lib/Analysis/InstructionSimplify.cpp b/llvm/lib/Analysis/InstructionSimplify.cpp
index 1e8a1dd..b34aede 100644
--- a/llvm/lib/Analysis/InstructionSimplify.cpp
+++ b/llvm/lib/Analysis/InstructionSimplify.cpp
@@ -2613,21 +2613,48 @@
}
}
- // icmp pred (or X, Y), X
- if (LBO && match(LBO, m_CombineOr(m_Or(m_Value(), m_Specific(RHS)),
- m_Or(m_Specific(RHS), m_Value())))) {
- if (Pred == ICmpInst::ICMP_ULT)
- return getFalse(ITy);
- if (Pred == ICmpInst::ICMP_UGE)
- return getTrue(ITy);
- }
- // icmp pred X, (or X, Y)
- if (RBO && match(RBO, m_CombineOr(m_Or(m_Value(), m_Specific(LHS)),
- m_Or(m_Specific(LHS), m_Value())))) {
- if (Pred == ICmpInst::ICMP_ULE)
- return getTrue(ITy);
- if (Pred == ICmpInst::ICMP_UGT)
- return getFalse(ITy);
+ {
+ Value *Y = nullptr;
+ // icmp pred (or X, Y), X
+ if (LBO && match(LBO, m_c_Or(m_Value(Y), m_Specific(RHS)))) {
+ if (Pred == ICmpInst::ICMP_ULT)
+ return getFalse(ITy);
+ if (Pred == ICmpInst::ICMP_UGE)
+ return getTrue(ITy);
+
+ if (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SGE) {
+ bool RHSKnownNonNegative, RHSKnownNegative;
+ bool YKnownNonNegative, YKnownNegative;
+ ComputeSignBit(RHS, RHSKnownNonNegative, RHSKnownNegative, Q.DL, 0,
+ Q.AC, Q.CxtI, Q.DT);
+ ComputeSignBit(Y, YKnownNonNegative, YKnownNegative, Q.DL, 0, Q.AC,
+ Q.CxtI, Q.DT);
+ if (RHSKnownNonNegative && YKnownNegative)
+ return Pred == ICmpInst::ICMP_SLT ? getTrue(ITy) : getFalse(ITy);
+ if (RHSKnownNegative || YKnownNonNegative)
+ return Pred == ICmpInst::ICMP_SLT ? getFalse(ITy) : getTrue(ITy);
+ }
+ }
+ // icmp pred X, (or X, Y)
+ if (RBO && match(RBO, m_c_Or(m_Value(Y), m_Specific(LHS)))) {
+ if (Pred == ICmpInst::ICMP_ULE)
+ return getTrue(ITy);
+ if (Pred == ICmpInst::ICMP_UGT)
+ return getFalse(ITy);
+
+ if (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_SLE) {
+ bool LHSKnownNonNegative, LHSKnownNegative;
+ bool YKnownNonNegative, YKnownNegative;
+ ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, Q.DL, 0,
+ Q.AC, Q.CxtI, Q.DT);
+ ComputeSignBit(Y, YKnownNonNegative, YKnownNegative, Q.DL, 0, Q.AC,
+ Q.CxtI, Q.DT);
+ if (LHSKnownNonNegative && YKnownNegative)
+ return Pred == ICmpInst::ICMP_SGT ? getTrue(ITy) : getFalse(ITy);
+ if (LHSKnownNegative || YKnownNonNegative)
+ return Pred == ICmpInst::ICMP_SGT ? getFalse(ITy) : getTrue(ITy);
+ }
+ }
}
// icmp pred (and X, Y), X