shl Optimization InstCombine

[sonamkumari]

Summary

This patch handles
(icmp eq/ne (shl const2, A), const1) -> (icmp eq/ne A, log2(const1) - log2(const2)).
I wrote this patch for the equality comparison.
For other comparison operators, it needs to handled.
In the test cases I considered all the boundary conditions for the 32 bit integer and handled them.

Please help in reviewing this patch.
Any comments/suggestions are most welcomed.

Thanks,
Sonam.

[sonamkumari]

Hi Duncan,

Thanks for reviewing and providing valuable comments.
I will work on those comments and get back to you.

Thanks,
Sonam.

lib/Transforms/InstCombine/InstCombineCompares.cpp

if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
 
     // (icmp ne/eq (sub A B) 0) -> (icmp ne/eq A, B)
     if (I.isEquality() && CI->isZero() &&
         match(Op0, m_Sub(m_Value(A), m_Value(B)))) {
       // (icmp cond A B) if cond is equality
       return new ICmpInst(I.getPredicate(), A, B);
     }
 
+// FoldICmpCstShlCst - Handle "(icmp eq/ne (shl const2, A), const1)" ->
+// (icmp eq/ne A, Log2(const1) - Log2(const2))
+
+if(I.isEquality())
+    {
+        ConstantInt *CI2;
+        if(match(Op0,m_Shl(m_ConstantInt(CI2),m_Value(A))))
+        {
+
+         APInt AP1 = CI->getValue();
+         APInt AP2 = CI2->getValue();
+         int shift;
+
+         // If both AP1 and AP2 are positive,then AP2 needs to be even.
+         if(!AP1.isNegative() && !AP2.isNegative())
+         {
+             unsigned count_zero = AP1.countTrailingZeros();
+             if(!count_zero)
+             {
+                 if(I.getPredicate() == I.ICMP_EQ)
+             return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getType()));
+                 if(I.getPredicate() == I.ICMP_NE)
+             return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getType()));
+             }
+         }
+
+         // When AP2 is 32 bit max number and AP1 is negative
+         if(AP2 == 2147483647 && AP1.isNegative())
+         {
+             AP1 = -AP1;
+             shift = AP1.logBase2();
+             return new ICmpInst(I.getPredicate(), A, ConstantInt::get(A->getType(), shift));
+         }
+
+         if(AP1.isNegative())
+             AP1 = -AP1;
+         if(AP2.isNegative())
+             AP2 = -AP2;
+
+         // When AP1 is equal to 0
+         if(AP1 == 0)
+         {
+             shift = 32 - AP2.logBase2();
+             return new ICmpInst(I.getPredicate(), A, ConstantInt::get(A->getType(), shift));
+         }
+
+         // When AP1 is 32 bit max number
+         if(AP1 == 2147483647)
+             return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getType()));
+
+         // To deal with all the other different possibilities
+         shift = AP1.logBase2() - AP2.logBase2();
+         return new ICmpInst(I.getPredicate(), A, ConstantInt::get(A->getType(), shift));
+        }
+      }
+
     // If we have an icmp le or icmp ge instruction, turn it into the
     // appropriate icmp lt or icmp gt instruction.  This allows us to rely on
     // them being folded in the code below.  The SimplifyICmpInst code has
     // already handled the edge cases for us, so we just assert on them.
     switch (I.getPredicate()) {
     default: break;
     case ICmpInst::ICMP_ULE:
       assert(!CI->isMaxValue(false));                 // A <=u MAX -> TRUE

test/Transforms/InstCombine/icmp.ll

 ; CHECK: %z.unshifted = xor i32 %a, %b
 ; CHECK: %z = icmp ugt i32 %z.unshifted, 255
 define i1 @icmp_ashr_ashr_ne(i32 %a, i32 %b) nounwind {
  %x = ashr i32 %a, 8
  %y = ashr i32 %b, 8
  %z = icmp ne i32 %x, %y
  ret i1 %z
 }
+
+; CHECK-LABEL: @exact_shl_eq
+; CHECK-NEXT: ret i1 false
+define i1 @exact_shl_eq(i32 %a) {
+ %shr = shl i32 0, %a
+ %cmp = icmp eq i32 %shr, 16
+ ret i1 %cmp
+}
+
+; CHECK-LABEL: @exact_shl_1_eq
+; CHECK-NEXT: ret i1 false
+define i1 @exact_shl_1_eq(i32 %a) {
+ %shr = shl i32 0, %a
+ %cmp = icmp eq i32 %shr, -16
+ ret i1 %cmp
+}
+
+; CHECK-LABEL: @exact_shl_2_eq
+; CHECK-NEXT: ret i1 true
+define i1 @exact_shl_2_eq(i32 %a) {
+ %shr = shl i32 0, %a
+ %cmp = icmp eq i32 %shr, 0
+ ret i1 %cmp
+}
+
+; CHECK-LABEL: @exact_shl_3_eq
+; CHECK-NEXT: %cmp = icmp eq i32 %a, 28 
+define i1 @exact_shl_3_eq(i32 %a) {
+ %shr = shl i32 16, %a
+ %cmp = icmp eq i32 %shr, 0
+ ret i1 %cmp
+}
+
+; CHECK-LABEL: @exact_shl_4_eq
+; CHECK-NEXT: %cmp = icmp eq i32 %a, 28 
+define i1 @exact_shl_4_eq(i32 %a) {
+ %shr = shl i32 -16, %a
+ %cmp = icmp eq i32 %shr, 0
+ ret i1 %cmp
+}
+
+; CHECK-LABEL: @exact_shl_5_eq
+; CHECK-NEXT: %cmp = icmp eq i32 %a, -25
+define i1 @exact_shl_5_eq(i32 %a) {
+ %shr = shl i32 2147483647, %a
+ %cmp = icmp eq i32 %shr, 40
+ ret i1 %cmp
+}
+
+; CHECK-LABEL: @exact_shl_6_eq
+; CHECK-NEXT: ret i1 false
+define i1 @exact_shl_6_eq(i32 %a) {
+ %shr = shl i32 16, %a
+ %cmp = icmp eq i32 %shr, 2147483647
+ ret i1 %cmp
+}
+
+; CHECK-LABEL: @exact_shl_7_eq
+; CHECK-NEXT: ret i1 false
+define i1 @exact_shl_7_eq(i32 %a) {
+ %shr = shl i32 2147483647, %a
+ %cmp = icmp eq i32 %shr, 2147483647
+ ret i1 %cmp
+}
+
+; CHECK-LABEL: @exact_shl_8_eq
+; CHECK-NEXT: %cmp = icmp eq i32 %a, -27
+define i1 @exact_shl_8_eq(i32 %a) {
+ %shr = shl i32 -2147483648, %a
+ %cmp = icmp eq i32 %shr, -16
+ ret i1 %cmp
+}
+
+; CHECK-LABEL: @exact_shl_9_eq
+; CHECK-NEXT: %cmp = icmp eq i32 %a, 27
+define i1 @exact_shl_9_eq(i32 %a) {
+ %shr = shl i32 -16, %a
+ %cmp = icmp eq i32 %shr, -2147483648
+ ret i1 %cmp
+}
+
+; CHECK-LABEL: @exact_shl_10_eq
+; CHECK-NEXT: %cmp = icmp eq i32 %a, 0
+define i1 @exact_shl_10_eq(i32 %a) {
+ %shr = shl i32 -2147483648, %a
+ %cmp = icmp eq i32 %shr, -2147483648
+ ret i1 %cmp
+}
+
+; CHECK-LABEL: @exact_shl_11_eq
+; CHECK-NEXT: %cmp = icmp eq i32 %a, 1
+define i1 @exact_shl_11_eq(i32 %a) {
+ %shr = shl i32 2147483647, %a
+ %cmp = icmp eq i32 %shr, -2
+ ret i1 %cmp
+}
+
+; CHECK-LABEL: @exact_shl_12_eq
+; CHECK-NEXT: %cmp = icmp eq i32 %a, 27 
+define i1 @exact_shl_12_eq(i32 %a) {
+ %shr = shl i32 16, %a
+ %cmp = icmp eq i32 %shr, -2147483648
+ ret i1 %cmp
+}
+
+; CHECK-LABEL: @exact_shl_13_eq
+; CHECK-NEXT: %cmp = icmp eq i32 %a, 31
+define i1 @exact_shl_13_eq(i32 %a) {
+ %shr = shl i32 2147483647, %a
+ %cmp = icmp eq i32 %shr, -2147483648
+ ret i1 %cmp
+}
+
+; CHECK-LABEL: @exact_shl_15_eq
+; CHECK-NEXT: %cmp = icmp eq i32 %a, -28
+define i1 @exact_shl_15_eq(i32 %a) {
+ %shr = shl i32 -2147483648, %a
+ %cmp = icmp eq i32 %shr, 8
+ ret i1 %cmp
+}
+
+; CHECK-LABEL: @exact_shl_16_eq
+; CHECK-NEXT: ret i1 false
+define i1 @exact_shl_16_eq(i32 %a) {
+ %shr = shl i32 -32, %a
+ %cmp = icmp eq i32 %shr, 2147483647
+ ret i1 %cmp
+}
+
+; CHECK-LABEL: @exact_shl_17_eq
+; CHECK-NEXT: ret i1 false
+define i1 @exact_shl_17_eq(i32 %a) {
+ %shr = shl i32 -2147483648, %a
+ %cmp = icmp eq i32 %shr, 2147483647
+ ret i1 %cmp
+}
+
+; CHECK-LABEL: @exact_shl_18_eq
+; CHECK-NEXT: %cmp = icmp eq i32 %a, -1
+define i1 @exact_shl_18_eq(i32 %a) {
+ %shr = shl i32 -16, %a
+ %cmp = icmp eq i32 %shr, 8
+ ret i1 %cmp
+}
+
+; CHECK-LABEL: @exact_shl_19_eq
+; CHECK-NEXT: %cmp = icmp eq i32 %a, 1
+define i1 @exact_shl_19_eq(i32 %a) {
+ %shr = shl i32 -2147483648, %a
+ %cmp = icmp eq i32 %shr, 0
+ ret i1 %cmp
+}
+
+; CHECK-LABEL: @exact_shl_20_eq
+; CHECK-NEXT: ret i1 false
+define i1 @exact_shl_20_eq(i32 %a) {
+ %shr = shl i32 2147483647, %a
+ %cmp = icmp eq i32 %shr, 0
+ ret i1 %cmp
+}