[InstCombine] Optimize shl+lshr+and conversion pattern

[bcl5980]

Summary

if C1 and C3 are pow2 and Log2(C3)+C2 < BitWidth:

((C1 << X) >> C2) & C3 -> X == (Log2(C3)+C2-Log2(C1)) ? C3 : 0;

https://alive2.llvm.org/ce/z/Pus5bd

Fix issue https://github.com/llvm/llvm-project/issues/55739

[bcl5980]

rebase with more tests diff

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1916

This pattern with 2 shifts in the same direction should not exist after:
a0c3c60728ee5bc7

llvm/test/Transforms/InstCombine/and.ll

1731–1732

We had not reduced shifts as much as possible in this test and several others:

[bcl5980]

1. rebase code
2. remove lshr+lshr pattern
3. add a new transform to make shift+and have higher priority

[bcl5980]

update comments

[spatel]

I still think we should split this patch up as 2 independent transforms.

The opposite shifts transform doesn't seem like it should be a power-of-2-mask transform. Can we handle that using demanded bits instead? Double-check (you can pre-commit more tests as needed), but I don't think this patch will handle these related folds:
https://alive2.llvm.org/ce/z/SNmj5M

[bcl5980]

In D126617#3547120, @spatel wrote:

I still think we should split this patch up as 2 independent transforms.

The opposite shifts transform doesn't seem like it should be a power-of-2-mask transform. Can we handle that using demanded bits instead? Double-check (you can pre-commit more tests as needed), but I don't think this patch will handle these related folds:
https://alive2.llvm.org/ce/z/SNmj5M

Thanks for the mention. Is this transform you want ?
https://alive2.llvm.org/ce/z/-C8L9U
If yes, I will send a new patch to do this.

[spatel]

In D126617#3547436, @bcl5980 wrote:

In D126617#3547120, @spatel wrote:

I still think we should split this patch up as 2 independent transforms.

The opposite shifts transform doesn't seem like it should be a power-of-2-mask transform. Can we handle that using demanded bits instead? Double-check (you can pre-commit more tests as needed), but I don't think this patch will handle these related folds:
https://alive2.llvm.org/ce/z/SNmj5M

Thanks for the mention. Is this transform you want ?
https://alive2.llvm.org/ce/z/-C8L9U
If yes, I will send a new patch to do this.

Yes, the first pre-condition looks correct. We don't actually care what the final instruction in the sequence is - it just has to remove demand of the high bits. The last instruction could be a trunc for example, so we should have tests with that too:
https://alive2.llvm.org/ce/z/ZCgqj5

We already look for that pattern in InstCombine's demanded bits. So I think we just need to add a transform like this:

diff --git a/llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp b/llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp
index 278db05f65d1..c0d92fc27bb6 100644
--- a/llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp
+++ b/llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp
@@ -630,6 +630,18 @@ Value *InstCombinerImpl::SimplifyDemandedUseBits(Value *V, APInt DemandedMask,
             ComputeNumSignBits(I->getOperand(0), Depth + 1, CxtI);
         if (SignBits >= NumHiDemandedBits)
           return I->getOperand(0);
+
+        // If we can pre-shift a left-shifted constant to the right without
+        // losing any low bits (we already know we don't demand the high bits):
+        // (C << X) >> SA --> (C >> SA) << X
+        Value *X;
+        const APInt *C;
+        if (match(I->getOperand(0), m_Shl(m_APInt(C), m_Value(X))) &&
+            C->countTrailingZeros() >= ShiftAmt) {
+          Constant *ShiftC = ConstantInt::get(I->getType(), C->lshr(ShiftAmt));
+          Instruction *Shl = BinaryOperator::CreateShl(ShiftC, X);
+          return InsertNewInstWith(Shl, *I);
+        }
       }
 
       // Unsigned shift right.

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1892–1894

What happens if we reduce the pattern to:
https://alive2.llvm.org/ce/z/7snGRd

That's the same transform that I suggested in D126591, but invert the shift direction (lshr instead of shl).

[bcl5980]

In D126617#3547933, @spatel wrote:

In D126617#3547436, @bcl5980 wrote:

In D126617#3547120, @spatel wrote:

I still think we should split this patch up as 2 independent transforms.

The opposite shifts transform doesn't seem like it should be a power-of-2-mask transform. Can we handle that using demanded bits instead? Double-check (you can pre-commit more tests as needed), but I don't think this patch will handle these related folds:
https://alive2.llvm.org/ce/z/SNmj5M

Thanks for the mention. Is this transform you want ?
https://alive2.llvm.org/ce/z/-C8L9U
If yes, I will send a new patch to do this.

Yes, the first pre-condition looks correct. We don't actually care what the final instruction in the sequence is - it just has to remove demand of the high bits. The last instruction could be a trunc for example, so we should have tests with that too:
https://alive2.llvm.org/ce/z/ZCgqj5

We already look for that pattern in InstCombine's demanded bits. So I think we just need to add a transform like this:

diff --git a/llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp b/llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp
index 278db05f65d1..c0d92fc27bb6 100644
--- a/llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp
+++ b/llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp
@@ -630,6 +630,18 @@ Value *InstCombinerImpl::SimplifyDemandedUseBits(Value *V, APInt DemandedMask,
             ComputeNumSignBits(I->getOperand(0), Depth + 1, CxtI);
         if (SignBits >= NumHiDemandedBits)
           return I->getOperand(0);
+
+        // If we can pre-shift a left-shifted constant to the right without
+        // losing any low bits (we already know we don't demand the high bits):
+        // (C << X) >> SA --> (C >> SA) << X
+        Value *X;
+        const APInt *C;
+        if (match(I->getOperand(0), m_Shl(m_APInt(C), m_Value(X))) &&
+            C->countTrailingZeros() >= ShiftAmt) {
+          Constant *ShiftC = ConstantInt::get(I->getType(), C->lshr(ShiftAmt));
+          Instruction *Shl = BinaryOperator::CreateShl(ShiftC, X);
+          return InsertNewInstWith(Shl, *I);
+        }
       }
 
       // Unsigned shift right.

Wow, that's cool. A very general solution.

[bcl5980]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1892–1894

The latest version is based on your suggetion:
https://alive2.llvm.org/ce/z/7snGRd
https://alive2.llvm.org/ce/z/jA_tNb

I'm still worry if we can transform shift+and to cmp+select.
Generally most highend cpu should prefer shift+and because the cmp instruction ports is less than shift/and.
But in cmp instruction the immediate value can be imm operation but shift may need extra mov instruction on some mainstream backend.
One other question is this transform can fix the case @shl_lshr_pow2_const.
Can you help to review which way should I do ?

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1892–1894

Codegen for any particular target is not the main concern here. The backend should be able to invert the transforms that we make here if that is profitable.

We partially demonstrated that with the assembly examples in the other patch. You can try similar experiments for these patterns.

I looked at @shl_lshr_pow2_const for a while, and I don't see a very good generalization. We can add the larger pattern match for and(shift(shift)), or we can treat that as a special-case of demanding one bit only.

If we view it as another demanded bits problem, then we could improve something like this:
https://alive2.llvm.org/ce/z/3oDagP
(but I don't have any evidence of that being important)

llvm/test/Transforms/InstCombine/and.ll

1625

This diff does not exist with the current test on "main", right? Is this review baselined against another patch?

[bcl5980]

Sorry for the late response. Based on the discussion I have some questions:

1. the demanded bits fix. I think it is a safe and independent change. Should I check in this part first ? Or @spatel can you help to do this as the author is you.

diff --git a/llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp b/llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp
index 278db05f65d1..c0d92fc27bb6 100644
--- a/llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp
+++ b/llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp
@@ -630,6 +630,18 @@ Value *InstCombinerImpl::SimplifyDemandedUseBits(Value *V, APInt DemandedMask,
             ComputeNumSignBits(I->getOperand(0), Depth + 1, CxtI);
         if (SignBits >= NumHiDemandedBits)
           return I->getOperand(0);
+
+        // If we can pre-shift a left-shifted constant to the right without
+        // losing any low bits (we already know we don't demand the high bits):
+        // (C << X) >> SA --> (C >> SA) << X
+        Value *X;
+        const APInt *C;
+        if (match(I->getOperand(0), m_Shl(m_APInt(C), m_Value(X))) &&
+            C->countTrailingZeros() >= ShiftAmt) {
+          Constant *ShiftC = ConstantInt::get(I->getType(), C->lshr(ShiftAmt));
+          Instruction *Shl = BinaryOperator::CreateShl(ShiftC, X);
+          return InsertNewInstWith(Shl, *I);
+        }
       }

2. Should we transform 'shift+and' to 'icmp+select'? I think backend is not easy to invert the transform. We need to make sure input value is less than BitWidth then can invert. So I prefer to do this only when we can save instructions.

3. How to fix @shl_lshr_pow2_const? I think current review is add the larger pattern match for and(shift(shift)). I'm sorry I don't know how to fix based on demanded bits? It will be grateful if you can help to teach me the detail solution?

4. Do we need D126591 after we fix @shl_lshr_pow2_const? There are still have some patterns we can't cover. For example the pattern:

 iff (C1 is pow2) & ((C2 & ~(C1-1)) + C1) is pow2) & (C1 < C2):
((C1 << X) & C2) == 0 -> X >= (Log2(C2+C1) - Log2(C1)); https://alive2.llvm.org/ce/z/JQYFnn
((C1 << X) & C2) != 0 -> X  < (Log2(C2+C1) - Log2(C1)); https://alive2.llvm.org/ce/z/BnyEmk

llvm/test/Transforms/InstCombine/and.ll

1625

I'm sorry this is based on Diff3. I will rebase the review based on main.

[bcl5980]

update based on main branch and revert the code back to diff5

[spatel]

In D126617#3559375, @bcl5980 wrote:

1. the demanded bits fix. I think it is a safe and independent change.

Ok, let's try to make improvements in small steps; one part for demanded bits is here:
D127122

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1895

Use m_Power2(C1) ?

1899

Do we really need both conditions? I removed one assumption, and it still shows as correct:
https://alive2.llvm.org/ce/z/nUAXL9

[bcl5980]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1899

Yeah, we can remove the condition cttz(C1) < cttz(C)+C2.
Actually if cttz(C1) >= cttz(C)+C2, it will fall into D127122.
So still the question which pattern we should use by default, 'shift+and' or 'icmp+select'?
'shift+and' pattern can remain the information x is limited by bit width.
'icmp+select' can help to handle shift+and+xor case, and icmp can handle lshr, shl at the same time.
For now what I do is keep 'shift+and' ASAP but if we prefer icmp+select I can remove the condition.

[bcl5980]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1899

Yeah, we can remove the condition cttz(C1) < cttz(C)+C2.
Actually if cttz(C1) >= cttz(C)+C2, it will fall into D127122.

Sorry for the wrong comments, actually if cttz(C1) >= cttz(C)+C2 it will always return 0.
Last comment works when C2 <= cttz(C1) < cttz(C)+C2.
I will remove cttz(C1) < cttz(C)+C2 to make the code easier.

[bcl5980]

1. Use m_Power2 to match C1
2. Remove condition Log2(C1) < Log2(C3)+C2
3. Add one more test case when C2 < Log2(C1) < Log2(C3)+C2

[spatel]

In D126617#3565340, @bcl5980 wrote:

1. Use m_Power2 to match C1
2. Remove condition Log2(C1) < Log2(C3)+C2

Update the Alive2 proof in the patch description, so it matches the new code.
Will you add the pattern where the shift order is reversed in another patch? ( https://alive2.llvm.org/ce/z/fNdbfZ )
You can put a TODO comment with the code in this patch, so we know it is should be added for symmetry.

llvm/test/Transforms/InstCombine/and.ll

1625

Do we have a negative test with "cttz(ShlC) > LShrC"? If not, please add that. If the test is already here, then add a comment like that, so we know the purpose of the test.

1638

This test is already optimized with D127122 ? It's fine to add another test, but please pre-commit before this patch, so we know how this patch alone is changing the tests.

[bcl5980]

rebase with new tests.

[bcl5980]

add to do for Symmetrical case

[bcl5980]

try support non-uniform case.

[spatel]

LGTM

If I'm seeing it correctly, this will alter D126591 or possibly make it unnecessary. I recommend implementing the symmetric TODO pattern for this patch as the next patch, and then we can see what remains.

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

if (match(Op0, m_OneUse(m_BinOp(BO))) && isSuitableBinOpcode(BO)) {
         Value *BinOp = isa<ZExtInst>(BO->getOperand(0))
                            ? Builder.CreateBinOp(BO->getOpcode(), X, TruncC1)
                            : Builder.CreateBinOp(BO->getOpcode(), TruncC1, X);
         Constant *TruncC = ConstantInt::get(X->getType(), C->trunc(XWidth));
         Value *And = Builder.CreateAnd(BinOp, TruncC);
         return new ZExtInst(And, Ty);
       }
     }
+
+    const APInt *C1;
+    const APInt *C2;
+    Value *X;
+    if (C->isPowerOf2() &&
+        match(Op0,
+              m_OneUse(m_LShr(m_Shl(m_APInt(C1), m_Value(X)), m_APInt(C2))))) {
+      unsigned Log2C1 = C1->countTrailingZeros();
+      unsigned Log2C = C->countTrailingZeros();
+      unsigned LShrEqBits = Log2C + C2->getZExtValue();
+      if (LShrEqBits < Width) {
+        if (Log2C1 >= C2->getZExtValue()) {
+          // iff C is pow2 and cttz(C1) >= C2 && cttz(C)+C2 < BitWidth
+          // ((C1 << X) >> C2) & C -> X == ((C1 >> C2) << X) & C
+          Constant *ShlC = ConstantInt::get(Ty, C1->lshr(*C2));
+          Value *Shl = Builder.CreateShl(ShlC, X);
+          return BinaryOperator::CreateAnd(Shl, ConstantInt::get(Ty, *C));
+        } else if (C1->isPowerOf2() && LShrEqBits >= Log2C1) {
+          // iff C,C1 is pow2 and cttz(C1) < cttz(C)+C2 < BitWidth:
+          // ((C1 << X) >> C2) & C -> X == (cttz(C)+C2-cttz(C1)) ? C : 0
+          unsigned CmpC = LShrEqBits - Log2C1;
+          Value *Cmp = Builder.CreateICmpEQ(X, ConstantInt::get(Ty, CmpC));
+          return SelectInst::Create(Cmp, ConstantInt::get(Ty, *C),
+                                    ConstantInt::getNullValue(Ty));
+        }
+      }
+    }
   }
 
   if (match(&I, m_And(m_OneUse(m_Shl(m_ZExt(m_Value(X)), m_Value(Y))),
                       m_SignMask())) &&
       match(Y, m_SpecificInt_ICMP(
                    ICmpInst::Predicate::ICMP_EQ,
                    APInt(Ty->getScalarSizeInBits(),
                          Ty->getScalarSizeInBits() -
                              X->getType()->getScalarSizeInBits())))) {
     auto *SExt = Builder.CreateSExt(X, Ty, X->getName() + ".signext");

llvm/test/Transforms/InstCombine/and.ll

 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %sign = lshr i8 %x, 7
   %not = xor i8 %sign, -1
   %r = and i8 %not, %y
   ret i8 %r
 }
 
 define i16 @shl_lshr_pow2_const(i16 %x) {
 ; CHECK-LABEL: @shl_lshr_pow2_const(
-; CHECK-NEXT:    [[SHL:%.*]] = shl i16 4, [[X:%.*]]
-; CHECK-NEXT:    [[LSHR:%.*]] = lshr i16 [[SHL]], 6
-; CHECK-NEXT:    [[R:%.*]] = and i16 [[LSHR]], 8
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i16 [[X:%.*]], 7
+; CHECK-NEXT:    [[R:%.*]] = select i1 [[TMP1]], i16 8, i16 0
 ; CHECK-NEXT:    ret i16 [[R]]
 ;
   %shl = shl i16 4, %x
   %lshr = lshr i16 %shl, 6
   %r = and i16 %lshr, 8
   ret i16 %r
 }
 
+define i16 @shl_lshr_pow2_const_case2(i16 %x) {
+; CHECK-LABEL: @shl_lshr_pow2_const_case2(
+; CHECK-NEXT:    [[TMP1:%.*]] = shl i16 6, [[X:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = and i16 [[TMP1]], 8
+; CHECK-NEXT:    ret i16 [[R]]
+;
+  %shl = shl i16 48, %x
+  %lshr = lshr i16 %shl, 3
+  %r = and i16 %lshr, 8
+  ret i16 %r
+}
+
 define i16 @shl_lshr_pow2_const_negative_oneuse(i16 %x) {
 ; CHECK-LABEL: @shl_lshr_pow2_const_negative_oneuse(
 ; CHECK-NEXT:    [[SHL:%.*]] = shl i16 4, [[X:%.*]]
 ; CHECK-NEXT:    [[LSHR:%.*]] = lshr i16 [[SHL]], 6
 ; CHECK-NEXT:    call void @use16(i16 [[LSHR]])
 ; CHECK-NEXT:    [[R:%.*]] = and i16 [[LSHR]], 8
 ; CHECK-NEXT:    ret i16 [[R]]
 ;
   %shl = shl i16 4, %x
   %lshr = lshr i16 %shl, 6
   call void @use16(i16 %lshr)
   %r = and i16 %lshr, 8
   ret i16 %r
 }
 
+define i16 @shl_lshr_pow2_const_negative_oneuse2(i16 %x) {
+; CHECK-LABEL: @shl_lshr_pow2_const_negative_oneuse2(
+; CHECK-NEXT:    [[SHL:%.*]] = shl i16 48, [[X:%.*]]
+; CHECK-NEXT:    [[LSHR:%.*]] = lshr exact i16 [[SHL]], 3
+; CHECK-NEXT:    call void @use16(i16 [[LSHR]])
+; CHECK-NEXT:    [[R:%.*]] = and i16 [[LSHR]], 8
+; CHECK-NEXT:    ret i16 [[R]]
+;
+  %shl = shl i16 48, %x
+  %lshr = lshr i16 %shl, 3
+  call void @use16(i16 %lshr)
+  %r = and i16 %lshr, 8
+  ret i16 %r
+}
 
 define i16 @shl_lshr_pow2_const_negative_nopow2_1(i16 %x) {
 ; CHECK-LABEL: @shl_lshr_pow2_const_negative_nopow2_1(
 ; CHECK-NEXT:    [[SHL:%.*]] = shl i16 3, [[X:%.*]]
 ; CHECK-NEXT:    [[LSHR:%.*]] = lshr i16 [[SHL]], 6
 ; CHECK-NEXT:    [[R:%.*]] = and i16 [[LSHR]], 8
 ; CHECK-NEXT:    ret i16 [[R]]
 ;

 }
 
 define i16 @lshr_lshr_pow2_const(i16 %x) {
 ; CHECK-LABEL: @lshr_lshr_pow2_const(
 ; CHECK-NEXT:    [[LSHR2:%.*]] = lshr i16 32, [[X:%.*]]
 ; CHECK-NEXT:    [[R:%.*]] = and i16 [[LSHR2]], 4
 ; CHECK-NEXT:    ret i16 [[R]]
 ;
   %lshr1 = lshr i16 2048, %x
   %lshr2 = lshr i16 %lshr1, 6
   %r = and i16 %lshr2, 4
   ret i16 %r
 }
 
 define i16 @lshr_lshr_pow2_const_negative_oneuse(i16 %x) {
 ; CHECK-LABEL: @lshr_lshr_pow2_const_negative_oneuse(
 ; CHECK-NEXT:    [[LSHR2:%.*]] = lshr i16 32, [[X:%.*]]
 ; CHECK-NEXT:    call void @use16(i16 [[LSHR2]])

llvm/test/Transforms/InstCombine/icmp-and-shift.ll

;
   %and = and <2 x i32> %shl, <i32 16, i32 16>
   %cmp = icmp ne <2 x i32> %and, <i32 0, i32 0>
   %conv = zext <2 x i1> %cmp to <2 x i32>
   ret <2 x i32> %conv
 }
 
 define i32 @icmp_eq_and_pow2_shl_pow2(i32 %0) {
 ; CHECK-LABEL: @icmp_eq_and_pow2_shl_pow2(
-; CHECK-NEXT:    [[SHL:%.*]] = shl i32 2, [[TMP0:%.*]]
-; CHECK-NEXT:    [[AND:%.*]] = lshr i32 [[SHL]], 4
-; CHECK-NEXT:    [[AND_LOBIT:%.*]] = and i32 [[AND]], 1
-; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[AND_LOBIT]], 1
-; CHECK-NEXT:    ret i32 [[TMP2]]
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp ne i32 [[TMP0:%.*]], 3
+; CHECK-NEXT:    [[TMP3:%.*]] = zext i1 [[TMP2]] to i32
+; CHECK-NEXT:    ret i32 [[TMP3]]
 ;
   %shl = shl i32 2, %0
   %and = and i32 %shl, 16
   %cmp = icmp eq i32 %and, 0
   %conv = zext i1 %cmp to i32
   ret i32 %conv
 }
 
 define <2 x i32> @icmp_eq_and_pow2_shl_pow2_vec(<2 x i32> %0) {
 ; CHECK-LABEL: @icmp_eq_and_pow2_shl_pow2_vec(
-; CHECK-NEXT:    [[SHL:%.*]] = shl <2 x i32> <i32 4, i32 4>, [[TMP0:%.*]]
-; CHECK-NEXT:    [[AND:%.*]] = lshr <2 x i32> [[SHL]], <i32 4, i32 4>
-; CHECK-NEXT:    [[AND_LOBIT:%.*]] = and <2 x i32> [[AND]], <i32 1, i32 1>
-; CHECK-NEXT:    [[TMP2:%.*]] = xor <2 x i32> [[AND_LOBIT]], <i32 1, i32 1>
-; CHECK-NEXT:    ret <2 x i32> [[TMP2]]
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp ne <2 x i32> [[TMP0:%.*]], <i32 2, i32 2>
+; CHECK-NEXT:    [[TMP3:%.*]] = zext <2 x i1> [[TMP2]] to <2 x i32>
+; CHECK-NEXT:    ret <2 x i32> [[TMP3]]
 ;
   %shl = shl <2 x i32> <i32 4, i32 4>, %0
   %and = and <2 x i32> %shl, <i32 16, i32 16>
   %cmp = icmp eq <2 x i32> %and, <i32 0, i32 0>
   %conv = zext <2 x i1> %cmp to <2 x i32>
   ret <2 x i32> %conv
 }
 
 define i32 @icmp_ne_and_pow2_shl_pow2(i32 %0) {
 ; CHECK-LABEL: @icmp_ne_and_pow2_shl_pow2(
-; CHECK-NEXT:    [[SHL:%.*]] = shl i32 2, [[TMP0:%.*]]
-; CHECK-NEXT:    [[AND:%.*]] = lshr i32 [[SHL]], 4
-; CHECK-NEXT:    [[AND_LOBIT:%.*]] = and i32 [[AND]], 1
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[TMP0:%.*]], 3
+; CHECK-NEXT:    [[AND_LOBIT:%.*]] = zext i1 [[TMP2]] to i32
 ; CHECK-NEXT:    ret i32 [[AND_LOBIT]]
 ;
   %shl = shl i32 2, %0
   %and = and i32 %shl, 16
   %cmp = icmp ne i32 %and, 0
   %conv = zext i1 %cmp to i32
   ret i32 %conv
 }
 
 define <2 x i32> @icmp_ne_and_pow2_shl_pow2_vec(<2 x i32> %0) {
 ; CHECK-LABEL: @icmp_ne_and_pow2_shl_pow2_vec(
-; CHECK-NEXT:    [[SHL:%.*]] = shl <2 x i32> <i32 4, i32 4>, [[TMP0:%.*]]
-; CHECK-NEXT:    [[AND:%.*]] = lshr <2 x i32> [[SHL]], <i32 4, i32 4>
-; CHECK-NEXT:    [[AND_LOBIT:%.*]] = and <2 x i32> [[AND]], <i32 1, i32 1>
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq <2 x i32> [[TMP0:%.*]], <i32 2, i32 2>
+; CHECK-NEXT:    [[AND_LOBIT:%.*]] = zext <2 x i1> [[TMP2]] to <2 x i32>
 ; CHECK-NEXT:    ret <2 x i32> [[AND_LOBIT]]
 ;
   %shl = shl <2 x i32> <i32 4, i32 4>, %0
   %and = and <2 x i32> %shl, <i32 16, i32 16>
   %cmp = icmp ne <2 x i32> %and, <i32 0, i32 0>
   %conv = zext <2 x i1> %cmp to <2 x i32>
   ret <2 x i32> %conv
 }

 ;
   %shl = shl <2 x i32> <i32 1, i32 1>, %0
   %and = and <2 x i32> %shl, <i32 15, i32 15>
   %cmp = icmp ne <2 x i32> %and, <i32 0, i32 0>
   %conv = zext <2 x i1> %cmp to <2 x i32>
   ret <2 x i32> %conv
 }
 
+; TODO: can be transform to icmp uge
 define i32 @icmp_eq_and_pow2_minus1_shl_pow2(i32 %0) {
 ; CHECK-LABEL: @icmp_eq_and_pow2_minus1_shl_pow2(
 ; CHECK-NEXT:    [[SHL:%.*]] = shl i32 2, [[TMP0:%.*]]
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[SHL]], 14
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[AND]], 0
 ; CHECK-NEXT:    [[CONV:%.*]] = zext i1 [[CMP]] to i32
 ; CHECK-NEXT:    ret i32 [[CONV]]
 ;
   %shl = shl i32 2, %0
   %and = and i32 %shl, 15
   %cmp = icmp eq i32 %and, 0
   %conv = zext i1 %cmp to i32
   ret i32 %conv
 }
 
+; TODO: can be transform to icmp uge
 define <2 x i32> @icmp_eq_and_pow2_minus1_shl_pow2_vec(<2 x i32> %0) {
 ; CHECK-LABEL: @icmp_eq_and_pow2_minus1_shl_pow2_vec(
 ; CHECK-NEXT:    [[SHL:%.*]] = shl <2 x i32> <i32 4, i32 4>, [[TMP0:%.*]]
 ; CHECK-NEXT:    [[AND:%.*]] = and <2 x i32> [[SHL]], <i32 12, i32 12>
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq <2 x i32> [[AND]], zeroinitializer
 ; CHECK-NEXT:    [[CONV:%.*]] = zext <2 x i1> [[CMP]] to <2 x i32>
 ; CHECK-NEXT:    ret <2 x i32> [[CONV]]
 ;
   %shl = shl <2 x i32> <i32 4, i32 4>, %0
   %and = and <2 x i32> %shl, <i32 15, i32 15>
   %cmp = icmp eq <2 x i32> %and, <i32 0, i32 0>
   %conv = zext <2 x i1> %cmp to <2 x i32>
   ret <2 x i32> %conv
 }
 
+; TODO: can be transform to icmp ult
 define i32 @icmp_ne_and_pow2_minus1_shl_pow2(i32 %0) {
 ; CHECK-LABEL: @icmp_ne_and_pow2_minus1_shl_pow2(
 ; CHECK-NEXT:    [[SHL:%.*]] = shl i32 2, [[TMP0:%.*]]
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[SHL]], 14
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[AND]], 0
 ; CHECK-NEXT:    [[CONV:%.*]] = zext i1 [[CMP]] to i32
 ; CHECK-NEXT:    ret i32 [[CONV]]
 ;
   %shl = shl i32 2, %0
   %and = and i32 %shl, 15
   %cmp = icmp ne i32 %and, 0
   %conv = zext i1 %cmp to i32
   ret i32 %conv
 }
 
+; TODO: can be transform to icmp ult
 define <2 x i32> @icmp_ne_and_pow2_minus1_shl_pow2_vec(<2 x i32> %0) {
 ; CHECK-LABEL: @icmp_ne_and_pow2_minus1_shl_pow2_vec(
 ; CHECK-NEXT:    [[SHL:%.*]] = shl <2 x i32> <i32 4, i32 4>, [[TMP0:%.*]]
 ; CHECK-NEXT:    [[AND:%.*]] = and <2 x i32> [[SHL]], <i32 12, i32 12>
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne <2 x i32> [[AND]], zeroinitializer
 ; CHECK-NEXT:    [[CONV:%.*]] = zext <2 x i1> [[CMP]] to <2 x i32>
 ; CHECK-NEXT:    ret <2 x i32> [[CONV]]
 ;