InstCombine: Optimize (1 << X) Pred CstP2 to X Pred Log2(CstP2)
We may, after other optimizations, find ourselves with IR that looks
like:
%shl = shl i32 1, %y
%cmp = icmp ult i32 %shl, 32
Instead, we should just compare the shift count:
%cmp = icmp ult i32 %y, 5
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@185242 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Transforms/InstCombine/InstCombineCompares.cpp b/lib/Transforms/InstCombine/InstCombineCompares.cpp
index 617d8e7..2a87f8a 100644
--- a/lib/Transforms/InstCombine/InstCombineCompares.cpp
+++ b/lib/Transforms/InstCombine/InstCombineCompares.cpp
@@ -1319,10 +1319,80 @@
}
case Instruction::Shl: { // (icmp pred (shl X, ShAmt), CI)
- ConstantInt *ShAmt = dyn_cast<ConstantInt>(LHSI->getOperand(1));
- if (!ShAmt) break;
-
uint32_t TypeBits = RHSV.getBitWidth();
+ ConstantInt *ShAmt = dyn_cast<ConstantInt>(LHSI->getOperand(1));
+ if (!ShAmt) {
+ Value *X;
+ // (1 << X) pred P2 -> X pred Log2(P2)
+ if (match(LHSI, m_Shl(m_One(), m_Value(X)))) {
+ bool RHSVIsPowerOf2 = RHSV.isPowerOf2();
+ ICmpInst::Predicate Pred = ICI.getPredicate();
+ if (ICI.isUnsigned()) {
+ if (!RHSVIsPowerOf2) {
+ // (1 << X) < 30 -> X <= 4
+ // (1 << X) <= 30 -> X <= 4
+ // (1 << X) >= 30 -> X > 4
+ // (1 << X) > 30 -> X > 4
+ if (Pred == ICmpInst::ICMP_ULT)
+ Pred = ICmpInst::ICMP_ULE;
+ else if (Pred == ICmpInst::ICMP_UGE)
+ Pred = ICmpInst::ICMP_UGT;
+ }
+ unsigned RHSLog2 = RHSV.logBase2();
+
+ // (1 << X) >= 2147483648 -> X >= 31 -> X == 31
+ // (1 << X) > 2147483648 -> X > 31 -> false
+ // (1 << X) <= 2147483648 -> X <= 31 -> true
+ // (1 << X) < 2147483648 -> X < 31 -> X != 31
+ if (RHSLog2 == TypeBits-1) {
+ if (Pred == ICmpInst::ICMP_UGE)
+ Pred = ICmpInst::ICMP_EQ;
+ else if (Pred == ICmpInst::ICMP_UGT)
+ return ReplaceInstUsesWith(ICI, Builder->getFalse());
+ else if (Pred == ICmpInst::ICMP_ULE)
+ return ReplaceInstUsesWith(ICI, Builder->getTrue());
+ else if (Pred == ICmpInst::ICMP_ULT)
+ Pred = ICmpInst::ICMP_NE;
+ }
+
+ return new ICmpInst(Pred, X,
+ ConstantInt::get(RHS->getType(), RHSLog2));
+ } else if (ICI.isSigned()) {
+ if (RHSV.isAllOnesValue()) {
+ // (1 << X) <= -1 -> X == 31
+ if (Pred == ICmpInst::ICMP_SLE)
+ return new ICmpInst(ICmpInst::ICMP_EQ, X,
+ ConstantInt::get(RHS->getType(), TypeBits-1));
+
+ // (1 << X) > -1 -> X != 31
+ if (Pred == ICmpInst::ICMP_SGT)
+ return new ICmpInst(ICmpInst::ICMP_NE, X,
+ ConstantInt::get(RHS->getType(), TypeBits-1));
+ } else if (!RHSV) {
+ // (1 << X) < 0 -> X == 31
+ // (1 << X) <= 0 -> X == 31
+ if (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SLE)
+ return new ICmpInst(ICmpInst::ICMP_EQ, X,
+ ConstantInt::get(RHS->getType(), TypeBits-1));
+
+ // (1 << X) >= 0 -> X != 31
+ // (1 << X) > 0 -> X != 31
+ if (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_SGE)
+ return new ICmpInst(ICmpInst::ICMP_NE, X,
+ ConstantInt::get(RHS->getType(), TypeBits-1));
+ }
+ } else if (ICI.isEquality()) {
+ if (RHSVIsPowerOf2)
+ return new ICmpInst(
+ Pred, X, ConstantInt::get(RHS->getType(), RHSV.logBase2()));
+
+ return ReplaceInstUsesWith(
+ ICI, Pred == ICmpInst::ICMP_EQ ? Builder->getFalse()
+ : Builder->getTrue());
+ }
+ }
+ break;
+ }
// Check that the shift amount is in range. If not, don't perform
// undefined shifts. When the shift is visited it will be