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

2 files changed, 176 insertions, 2 deletions

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 @@ Instruction *InstCombiner::visitICmpInstWithInstAndIntCst(ICmpInst &ICI,
   }
 
   case Instruction::Shl: {       // (icmp pred (shl X, ShAmt), CI)
+    uint32_t TypeBits = RHSV.getBitWidth();
     ConstantInt *ShAmt = dyn_cast<ConstantInt>(LHSI->getOperand(1));
-    if (!ShAmt) break;
+    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;
+          }
 
-    uint32_t TypeBits = RHSV.getBitWidth();
+          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
diff --git a/test/Transforms/InstCombine/icmp.ll b/test/Transforms/InstCombine/icmp.ll
index 5248a89..0026b20 100644
--- a/test/Transforms/InstCombine/icmp.ll
+++ b/test/Transforms/InstCombine/icmp.ll
@@ -998,3 +998,107 @@ define i1 @test71(i8* %x) {
   %c = icmp ugt i8* %a, %b
   ret i1 %c
 }
+
+; CHECK: @icmp_shl_1_V_ult_32
+; CHECK-NEXT: [[CMP:%[a-z0-9]+]] = icmp ult i32 %V, 5
+; CHECK-NEXT: ret i1 [[CMP]]
+define i1 @icmp_shl_1_V_ult_32(i32 %V) {
+  %shl = shl i32 1, %V
+  %cmp = icmp ult i32 %shl, 32
+  ret i1 %cmp
+}
+
+; CHECK: @icmp_shl_1_V_eq_32
+; CHECK-NEXT: [[CMP:%[a-z0-9]+]] = icmp eq i32 %V, 5
+; CHECK-NEXT: ret i1 [[CMP]]
+define i1 @icmp_shl_1_V_eq_32(i32 %V) {
+  %shl = shl i32 1, %V
+  %cmp = icmp eq i32 %shl, 32
+  ret i1 %cmp
+}
+
+; CHECK: @icmp_shl_1_V_eq_31
+; CHECK-NEXT: ret i1 false
+define i1 @icmp_shl_1_V_eq_31(i32 %V) {
+  %shl = shl i32 1, %V
+  %cmp = icmp eq i32 %shl, 31
+  ret i1 %cmp
+}
+
+; CHECK: @icmp_shl_1_V_ne_31
+; CHECK-NEXT: ret i1 true
+define i1 @icmp_shl_1_V_ne_31(i32 %V) {
+  %shl = shl i32 1, %V
+  %cmp = icmp ne i32 %shl, 31
+  ret i1 %cmp
+}
+
+; CHECK: @icmp_shl_1_V_ult_30
+; CHECK-NEXT: [[CMP:%[a-z0-9]+]] = icmp ult i32 %V, 5
+; CHECK-NEXT: ret i1 [[CMP]]
+define i1 @icmp_shl_1_V_ult_30(i32 %V) {
+  %shl = shl i32 1, %V
+  %cmp = icmp ult i32 %shl, 30
+  ret i1 %cmp
+}
+
+; CHECK: @icmp_shl_1_V_ugt_30
+; CHECK-NEXT: [[CMP:%[a-z0-9]+]] = icmp ugt i32 %V, 4
+; CHECK-NEXT: ret i1 [[CMP]]
+define i1 @icmp_shl_1_V_ugt_30(i32 %V) {
+  %shl = shl i32 1, %V
+  %cmp = icmp ugt i32 %shl, 30
+  ret i1 %cmp
+}
+
+; CHECK: @icmp_shl_1_V_ule_30
+; CHECK-NEXT: [[CMP:%[a-z0-9]+]] = icmp ult i32 %V, 5
+; CHECK-NEXT: ret i1 [[CMP]]
+define i1 @icmp_shl_1_V_ule_30(i32 %V) {
+  %shl = shl i32 1, %V
+  %cmp = icmp ule i32 %shl, 30
+  ret i1 %cmp
+}
+
+; CHECK: @icmp_shl_1_V_uge_30
+; CHECK-NEXT: [[CMP:%[a-z0-9]+]] = icmp ugt i32 %V, 4
+; CHECK-NEXT: ret i1 [[CMP]]
+define i1 @icmp_shl_1_V_uge_30(i32 %V) {
+  %shl = shl i32 1, %V
+  %cmp = icmp uge i32 %shl, 30
+  ret i1 %cmp
+}
+
+; CHECK: @icmp_shl_1_V_uge_2147483648
+; CHECK-NEXT: [[CMP:%[a-z0-9]+]] = icmp eq i32 %V, 31
+; CHECK-NEXT: ret i1 [[CMP]]
+define i1 @icmp_shl_1_V_uge_2147483648(i32 %V) {
+  %shl = shl i32 1, %V
+  %cmp = icmp uge i32 %shl, 2147483648
+  ret i1 %cmp
+}
+
+; CHECK: @icmp_shl_1_V_ugt_2147483648
+; CHECK-NEXT: ret i1 false
+define i1 @icmp_shl_1_V_ugt_2147483648(i32 %V) {
+  %shl = shl i32 1, %V
+  %cmp = icmp ugt i32 %shl, 2147483648
+  ret i1 %cmp
+}
+
+; CHECK: @icmp_shl_1_V_ule_2147483648
+; CHECK-NEXT: ret i1 true
+define i1 @icmp_shl_1_V_ule_2147483648(i32 %V) {
+  %shl = shl i32 1, %V
+  %cmp = icmp ule i32 %shl, 2147483648
+  ret i1 %cmp
+}
+
+; CHECK: @icmp_shl_1_V_ult_2147483648
+; CHECK-NEXT: [[CMP:%[a-z0-9]+]] = icmp ne i32 %V, 31
+; CHECK-NEXT: ret i1 [[CMP]]
+define i1 @icmp_shl_1_V_ult_2147483648(i32 %V) {
+  %shl = shl i32 1, %V
+  %cmp = icmp ult i32 %shl, 2147483648
+  ret i1 %cmp
+}