Added InstCombine for ((1 << X) & C) pattern

[dinesh.d]

Summary

Basically this patch transforms
(1 << X) & C -> (X == lg(C)) ? (1 << X) : 0, if C is Power of 2
(1 << X) & C -> (X < lg(C+1)) ? (1 << X) : 0, if C + 1 is Power of 2

This patch can handles following cases from http://nondot.org/sabre/LLVMNotes/InstCombine.txt

if (!((1 << which_alternative) & 0x3)) --> if (which_alternative >= 2)

if (((1 << which_alternative) & 0x7)) --> if (which_alternative < 3)

I need suggestion regarding this

1. Names for comp and select instruction, for now, it is getting set automatically.
2. Do we have to have check if X is not greater than the bit-width
3. If check for the last of added test-case is ok.

[dinesh.d]

I have written smt-lib program to verify these transformations.

http://rise4fun.com/Z3/Skhom (verifies ((1 << x) & c) => (x == lg(c))? c : 0, if c is power of 2)
http://rise4fun.com/Z3/p4BF (verifies ((1 << x) & c) => (x == lg(c+1))? (1 << x) : 0, if c+1 is power of 2)

This verification assumes:

1. c > 0, this case is ensured by existing code, => x & 0 = 0
2. (1 << x) does not overflow, assumed handled in existing code, (http://reviews.llvm.org/D3371)

Update patch to use c in place of (1 << x) in ICmp in new SelectInst.
Updated test case for (1 << x) & 8, to non 'if' version as there are similar test case in icmp.ll (test17, test19)

[bkramer]

Getting the cases from Chris' note right is great. However, I don't think

(X == lg(C)) ? (1 << X) : 0

is preferable to

(1 << X) & C

in the general case. You're trading a shift + and for icmp + shift + select here. That's more complex and select tends to be an expensive operation. Can you try a more direct way, for example by starting at the icmp operation in instcombine and matching the operands?

[dinesh.d]

Thanks for review. I have tested it for test cases with if(..) and saw that select instruction I introduced is getting combined with select instruction from if statement and resulted code had less instructions.

I agree with you point and will update patch accordingly.

[dinesh.d]

Updated as per comment

[dinesh.d]

Gentle Ping

[dinesh.d]

gentle ping

[bkramer]

This is going into the right direction, thanks. One minor tweak left.

lib/Transforms/InstCombine/InstCombineCompares.cpp

2542–2550 ↗

(On Diff #9286)

I think it would be better to generate an ICMP_UGT directly instead of emitting an ICMP_UGE which is turned into ugt later on.

2589–2597 ↗

(On Diff #9286)

Same here.

[dinesh.d]

Update as per comments.

lib/Transforms/InstCombine/InstCombineCompares.cpp

2542–2550 ↗

(On Diff #9286)

done

2589–2597 ↗

(On Diff #9286)

This is already using ULT. Updated code to have symmetry with ICMP_EQ case.

[bkramer]

LGTM

[dinesh.d]

Closed by commit rL210007 (authored by dinesh).

llvm/trunk/lib/Transforms/InstCombine/InstCombineCompares.cpp

if (BitWidth != 0) {
     case ICmpInst::ICMP_EQ: {
       if (Op0Max.ult(Op1Min) || Op0Min.ugt(Op1Max))
         return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getType()));
 
       // If all bits are known zero except for one, then we know at most one
       // bit is set.   If the comparison is against zero, then this is a check
       // to see if *that* bit is set.
       APInt Op0KnownZeroInverted = ~Op0KnownZero;
-      if (~Op1KnownZero == 0 && Op0KnownZeroInverted.isPowerOf2()) {
+      if (~Op1KnownZero == 0) {
         // If the LHS is an AND with the same constant, look through it.
         Value *LHS = nullptr;
         ConstantInt *LHSC = nullptr;
         if (!match(Op0, m_And(m_Value(LHS), m_ConstantInt(LHSC))) ||
             LHSC->getValue() != Op0KnownZeroInverted)
           LHS = Op0;
 
         // If the LHS is 1 << x, and we know the result is a power of 2 like 8,
         // then turn "((1 << x)&8) == 0" into "x != 3".
+        // or turn "((1 << x)&7) == 0" into "x > 2".
         Value *X = nullptr;
         if (match(LHS, m_Shl(m_One(), m_Value(X)))) {
-          unsigned CmpVal = Op0KnownZeroInverted.countTrailingZeros();
+          APInt ValToCheck = Op0KnownZeroInverted;
+          if (ValToCheck.isPowerOf2()) {
+            unsigned CmpVal = ValToCheck.countTrailingZeros();
             return new ICmpInst(ICmpInst::ICMP_NE, X,
                                 ConstantInt::get(X->getType(), CmpVal));
+          } else if ((++ValToCheck).isPowerOf2()) {
+            unsigned CmpVal = ValToCheck.countTrailingZeros() - 1;
+            return new ICmpInst(ICmpInst::ICMP_UGT, X,
+                                ConstantInt::get(X->getType(), CmpVal));
+          }
         }
 
         // If the LHS is 8 >>u x, and we know the result is a power of 2 like 1,
         // then turn "((8 >>u x)&1) == 0" into "x != 3".
         const APInt *CI;
         if (Op0KnownZeroInverted == 1 &&
             match(LHS, m_LShr(m_Power2(CI), m_Value(X))))
           return new ICmpInst(ICmpInst::ICMP_NE, X,
                               ConstantInt::get(X->getType(),
                                                CI->countTrailingZeros()));
       }
 
       break;
     }
     case ICmpInst::ICMP_NE: {
       if (Op0Max.ult(Op1Min) || Op0Min.ugt(Op1Max))
         return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getType()));
 
       // If all bits are known zero except for one, then we know at most one
       // bit is set.   If the comparison is against zero, then this is a check
       // to see if *that* bit is set.
       APInt Op0KnownZeroInverted = ~Op0KnownZero;
-      if (~Op1KnownZero == 0 && Op0KnownZeroInverted.isPowerOf2()) {
+      if (~Op1KnownZero == 0) {
         // If the LHS is an AND with the same constant, look through it.
         Value *LHS = nullptr;
         ConstantInt *LHSC = nullptr;
         if (!match(Op0, m_And(m_Value(LHS), m_ConstantInt(LHSC))) ||
             LHSC->getValue() != Op0KnownZeroInverted)
           LHS = Op0;
 
         // If the LHS is 1 << x, and we know the result is a power of 2 like 8,
         // then turn "((1 << x)&8) != 0" into "x == 3".
+        // or turn "((1 << x)&7) != 0" into "x < 3".
         Value *X = nullptr;
         if (match(LHS, m_Shl(m_One(), m_Value(X)))) {
-          unsigned CmpVal = Op0KnownZeroInverted.countTrailingZeros();
+          APInt ValToCheck = Op0KnownZeroInverted;
+          if (ValToCheck.isPowerOf2()) {
+            unsigned CmpVal = ValToCheck.countTrailingZeros();
             return new ICmpInst(ICmpInst::ICMP_EQ, X,
                                 ConstantInt::get(X->getType(), CmpVal));
+          } else if ((++ValToCheck).isPowerOf2()) {
+            unsigned CmpVal = ValToCheck.countTrailingZeros();
+            return new ICmpInst(ICmpInst::ICMP_ULT, X,
+                                ConstantInt::get(X->getType(), CmpVal));
+          }
         }
 
         // If the LHS is 8 >>u x, and we know the result is a power of 2 like 1,
         // then turn "((8 >>u x)&1) != 0" into "x == 3".
         const APInt *CI;
         if (Op0KnownZeroInverted == 1 &&
             match(LHS, m_LShr(m_Power2(CI), m_Value(X))))
           return new ICmpInst(ICmpInst::ICMP_EQ, X,

llvm/trunk/test/Transforms/InstCombine/icmp.ll

define i1 @test17(i32 %x) nounwind {
   %shl = shl i32 1, %x
   %and = and i32 %shl, 8
   %cmp = icmp eq i32 %and, 0
   ret i1 %cmp
 ; CHECK-LABEL: @test17(
 ; CHECK-NEXT: %cmp = icmp ne i32 %x, 3
 }
 
+define i1 @test17a(i32 %x) nounwind {
+  %shl = shl i32 1, %x
+  %and = and i32 %shl, 7
+  %cmp = icmp eq i32 %and, 0
+  ret i1 %cmp
+; CHECK-LABEL: @test17a(
+; CHECK-NEXT: %cmp = icmp ugt i32 %x, 2
+}
 
 define i1 @test18(i32 %x) nounwind {
   %sh = lshr i32 8, %x
   %and = and i32 %sh, 1
   %cmp = icmp eq i32 %and, 0
   ret i1 %cmp
 ; CHECK-LABEL: @test18(
 ; CHECK-NEXT: %cmp = icmp ne i32 %x, 3
define i1 @test20(i32 %x) nounwind {
   %shl = shl i32 1, %x
   %and = and i32 %shl, 8
   %cmp = icmp ne i32 %and, 0
   ret i1 %cmp
 ; CHECK-LABEL: @test20(
 ; CHECK-NEXT: %cmp = icmp eq i32 %x, 3
 }
 
+define i1 @test20a(i32 %x) nounwind {
+  %shl = shl i32 1, %x
+  %and = and i32 %shl, 7
+  %cmp = icmp ne i32 %and, 0
+  ret i1 %cmp
+; CHECK-LABEL: @test20a(
+; CHECK-NEXT: %cmp = icmp ult i32 %x, 3
+}
+
 define i1 @test21(i8 %x, i8 %y) {
 ; CHECK-LABEL: @test21(
 ; CHECK-NOT: or i8
 ; CHECK: icmp ugt
   %A = or i8 %x, 1
   %B = icmp ugt i8 %A, 3
   ret i1 %B
 }