[InstCombine] Get rid of select of bittest (PR36950 / PR17564)

[lebedev.ri]

Summary

See PR36950, PR17564, D45065, D45107

This is complementary to D45065, either one will solve PR17564,
but this one will add one more fold pattern, which may be useful.

Notes:

• I don't actually check that C is < 32, some other fold already happens by then. Should i check anyway?
• Am i missing some has-one-use checks?

Please review carefully.

Alive proof: https://rise4fun.com/Alive/uiH

Testing: ninja check-llvm

[lebedev.ri]

Hmm yeah, as expected, not fully correct.
https://rise4fun.com/Alive/rD0 (should be 341, not 21760)

[lebedev.ri]

• Rebased ontop of updated tests
• Fixed nasty bug when accidentally using m_Value() instead of m_Specific() (test included)

[lebedev.ri]

Fix vector handling, too.

[lebedev.ri]

• Rebased ontop of revised tests.
• Handle non-splat constant vectors too.

[lebedev.ri]

lib/Transforms/InstCombine/InstCombineSelect.cpp

1542

Hmm, or should this be separated into two(?) different folds,
one to get rid of lshr, and another to get rid of select (i.e. the first ^ variant only, without lshr)?

[lebedev.ri]

In D45065#1054271, @spatel wrote:

I think we should solve this using something like D45108 instead, but I need to look closer at how the case in the bug report escaped the matching that we already have in foldSelectInstWithICmp() and foldSelectICmpAnd().

Ok, so let's look at those functions

• foldSelectICmpAnd() is only called when the select has constants as both true and false values https://github.com/llvm-mirror/llvm/blob/0b1a72a7a6069b674f1859ec859e846e6dc63594/lib/Transforms/InstCombine/InstCombineSelect.cpp#L794-L800 This isn't the case in these tests, only the false-value is constant.
• Same with the fold before that call https://github.com/llvm-mirror/llvm/blob/0b1a72a7a6069b674f1859ec859e846e6dc63594/lib/Transforms/InstCombine/InstCombineSelect.cpp#L757-L791 Only works on constants.

So while i don't have any particular expirience with InstCombine,
i don't see anything that would suggest that foldSelectInstWithICmp()
is already supposed to handle that case. Am i wrong?

But yes, i should at the very least move the code into that function.

[spatel]

In D45108#1057522, @lebedev.ri wrote:

In D45065#1054271, @spatel wrote:

I think we should solve this using something like D45108 instead, but I need to look closer at how the case in the bug report escaped the matching that we already have in foldSelectInstWithICmp() and foldSelectICmpAnd().

Ok, so let's look at those functions

• foldSelectICmpAnd() is only called when the select has constants as both true and false values https://github.com/llvm-mirror/llvm/blob/0b1a72a7a6069b674f1859ec859e846e6dc63594/lib/Transforms/InstCombine/InstCombineSelect.cpp#L794-L800 This isn't the case in these tests, only the false-value is constant.
• Same with the fold before that call https://github.com/llvm-mirror/llvm/blob/0b1a72a7a6069b674f1859ec859e846e6dc63594/lib/Transforms/InstCombine/InstCombineSelect.cpp#L757-L791 Only works on constants.

So while i don't have any particular expirience with InstCombine,
i don't see anything that would suggest that foldSelectInstWithICmp()
is already supposed to handle that case. Am i wrong?

But yes, i should at the very least move the code into that function.

Ok, if there's no easy way to meld these together, then just move it over. I wasn't sure; just seemed like there was similarity with the existing code.
A couple of things to change while doing that:

1. We should separate the case with a shift into its own block. Creating a shift-by-zero and then deleting it isn't efficient. Code readability will also improve.
2. We need to check 'm_OneUse' to make sure we're not creating more instructions than we're removing. There should also be some negative tests to exercise that. Example:

declare void @use32(i32)
declare void @use1(i1)

define i32 @f_var1(i32 %x, i32 %y) {
  %t3 = and i32 %x, %y
  %t4 = icmp eq i32 %t3, 0
  %t5 = and i32 %x, 1
  %t6 = select i1 %t4, i32 %t5, i32 1
  call void @use32(i32 %t3)
  call void @use32(i32 %t5)
  call void @use1(i1 %t4)
  ret i32 %t6
}

We shouldn't have 3 extra instructions here.

[lebedev.ri]

In D45108#1057766, @spatel wrote:

In D45108#1057522, @lebedev.ri wrote:

In D45065#1054271, @spatel wrote:

I think we should solve this using something like D45108 instead, but I need to look closer at how the case in the bug report escaped the matching that we already have in foldSelectInstWithICmp() and foldSelectICmpAnd().

Ok, so let's look at those functions

• foldSelectICmpAnd() is only called when the select has constants as both true and false values https://github.com/llvm-mirror/llvm/blob/0b1a72a7a6069b674f1859ec859e846e6dc63594/lib/Transforms/InstCombine/InstCombineSelect.cpp#L794-L800 This isn't the case in these tests, only the false-value is constant.
• Same with the fold before that call https://github.com/llvm-mirror/llvm/blob/0b1a72a7a6069b674f1859ec859e846e6dc63594/lib/Transforms/InstCombine/InstCombineSelect.cpp#L757-L791 Only works on constants.

So while i don't have any particular expirience with InstCombine,
i don't see anything that would suggest that foldSelectInstWithICmp()
is already supposed to handle that case. Am i wrong?

But yes, i should at the very least move the code into that function.

Ok, if there's no easy way to meld these together, then just move it over.

I wasn't sure; just seemed like there was similarity with the existing code.

I agree that the code is *similar*.
But right now i'm not seeing enough similarities yet to combine them.

A couple of things to change while doing that:

1. We should separate the case with a shift into its own block. Creating a shift-by-zero and then deleting it isn't efficient. Code readability will also improve.

Ok, sure.

2. We need to check 'm_OneUse' to make sure we're not creating more instructions than we're removing. There should also be some negative tests to exercise that. Example:

declare void @use32(i32)
declare void @use1(i1)

define i32 @f_var1(i32 %x, i32 %y) {
  %t3 = and i32 %x, %y
  %t4 = icmp eq i32 %t3, 0
  %t5 = and i32 %x, 1
  %t6 = select i1 %t4, i32 %t5, i32 1
  call void @use32(i32 %t3)
  call void @use32(i32 %t5)
  call void @use1(i1 %t4)
  ret i32 %t6
}

We shouldn't have 3 extra instructions here.

Thank you for the test! I was wondering about that (in the differential's description)

[lebedev.ri]

• Refactored into a function
• Flattened the nesting
• Added some one-use checks
• Do not create shl if it is to be removed immediately.

FIXME: do we want to allow the shift amount to be a value (not a constant), too?

[spatel]

In D45108#1058459, @lebedev.ri wrote:

FIXME: do we want to allow the shift amount to be a value (not a constant), too?

You've already coded it to allow that case, right? Just remove the m_NonNegative() check and add a test?

[lebedev.ri]

In D45108#1058593, @spatel wrote:

In D45108#1058459, @lebedev.ri wrote:

FIXME: do we want to allow the shift amount to be a value (not a constant), too?

You've already coded it to allow that case, right?

Yes, but not intentionally.

Just remove the m_NonNegative() check and add a test?

Doing that already right now :)

[lebedev.ri]

• Rebased ontop of more tests (D45329)
• Allow shift to be a variable, too

[lebedev.ri]

Rebased.

[spatel]

lib/Transforms/InstCombine/InstCombineSelect.cpp

407

IIRC, we don't want Alive links in the LLVM source (but Alive links in commit messages and bug reports are fine) - avoid any potential legal/licensing problems.

[lebedev.ri]

lib/Transforms/InstCombine/InstCombineSelect.cpp

407

First time i'm reading about this, will remove.
Source only, it's ok in tests?

[spatel]

lib/Transforms/InstCombine/InstCombineSelect.cpp

407

No, we don't want the links in tests either because those are included in the greater body of 'LLVM source'.
So you should remove the existing link from the test file too. It's fine to paste the Alive proof text if you want though.

There's no official guideline about this AFAIK, but there probably should be. I'm certain that I also wanted to include an Alive link in some patch long ago and was told not to, but I can't find that thread.

I'm not an expert, so if you want better answers, it's best to ask on llvm-dev.

[lebedev.ri]

The fact that comments-that-are-marked-as-done are submitted by the diff update, but not the new comments i added, always catches me off guard.

lib/Transforms/InstCombine/InstCombineSelect.cpp

407

... Ok, good to know.

[spatel]

LGTM.

[lebedev.ri]

In D45108#1060240, @spatel wrote:

LGTM.

Thank you for the review!

lib/Transforms/InstCombine/InstCombineSelect.cpp

if (FVI->hasOneUse() && !isa<Constant>(TrueVal)) {
       }
     }
   }
 
   return nullptr;
 }
 
 /// We want to turn:
+///   (select (icmp eq (and X, Y), 0), (and (lshr X, Z), 1), 1)
+/// into:
+///   zext (icmp ne i32 (and X, (or Y, (shl 1, Z))), 0)
+/// Note:
+///   Z may be 0 if lshr is missing.
+/// Worst case scenario is that we will replace 5 instructions with 5 different
+/// instructions, but we got rid of select.
+/// https://rise4fun.com/Alive/uiH
+static Instruction *foldSelectICmpAndAnd(Type *SelType, const ICmpInst *IC,
+                                         Value *TrueVal, Value *FalseVal,
+                                         InstCombiner::BuilderTy &Builder) {
+  if (!(IC->hasOneUse() && IC->getOperand(0)->hasOneUse()))
+    return nullptr;
+
+  Value *X, *Y;
+  ICmpInst::Predicate EqPred;
+  if (!(match(IC, m_ICmp(EqPred, m_And(m_Value(X), m_Value(Y)), m_Zero())) &&
+        ICmpInst::Predicate::ICMP_EQ == EqPred && match(FalseVal, m_One())))
+    return nullptr;
+
+  // The TrueVal has general form of:
+  //   and %B, 1
+  Value *B;
+  if (!match(TrueVal, m_OneUse(m_And(m_Value(B), m_One()))))
+    return nullptr;
+
+  // Where %B can be one of:
+  //        %X
+  // or
+  //   lshr %X, %Z
+  // Where %Z may or may not be a constant.
+  Value *MaskB, *Z;
+  if (match(B, m_Specific(X))) {
+    MaskB = ConstantInt::get(SelType, 1);
+  } else if (match(B, m_OneUse(m_LShr(m_Specific(X), m_Value(Z))))) {
+    MaskB = Builder.CreateShl(ConstantInt::get(SelType, 1), Z);
+  } else
+    return nullptr;
+
+  Value *FullMask = Builder.CreateOr(Y, MaskB);
+  Value *MaskedX = Builder.CreateAnd(X, FullMask);
+  Value *ICmpNeZero = Builder.CreateIsNotNull(MaskedX);
+  return new ZExtInst(ICmpNeZero, SelType);
+}
+
+/// We want to turn:
 ///   (select (icmp eq (and X, C1), 0), Y, (or Y, C2))
 /// into:
 ///   (or (shl (and X, C1), C3), Y)
 /// iff:
 ///   C1 and C2 are both powers of 2
 /// where:
 ///   C3 = Log(C2) - Log(C1)
 ///
if (IsBitTest) {
                match(FalseVal, m_Xor(m_Specific(X), m_APInt(C))) && *Y == *C)
         V = Builder.CreateOr(X, *Y);
 
       if (V)
         return replaceInstUsesWith(SI, V);
     }
   }
 
+  if (Instruction *V =
+          foldSelectICmpAndAnd(SI.getType(), ICI, TrueVal, FalseVal, Builder))
+    return V;
+
   if (Value *V = foldSelectICmpAndOr(ICI, TrueVal, FalseVal, Builder))
     return replaceInstUsesWith(SI, V);
 
   if (Value *V = foldSelectCttzCtlz(ICI, TrueVal, FalseVal, Builder))
     return replaceInstUsesWith(SI, V);
 
   if (Value *V = canonicalizeSaturatedSubtract(ICI, TrueVal, FalseVal, Builder))
     return replaceInstUsesWith(SI, V);
Instruction *InstCombiner::visitSelectInst(SelectInst &SI) {
   if (FCmpInst *FCI = dyn_cast<FCmpInst>(CondVal)) {
     if (FCI->getOperand(0) == TrueVal && FCI->getOperand(1) == FalseVal) {
       // Transform (X == Y) ? X : Y  -> Y
       if (FCI->getPredicate() == FCmpInst::FCMP_OEQ) {
         // This is not safe in general for floating point:
         // consider X== -0, Y== +0.
         // It becomes safe if either operand is a nonzero constant.
         ConstantFP *CFPt, *CFPf;
         if (((CFPt = dyn_cast<ConstantFP>(TrueVal)) &&
               !CFPt->getValueAPF().isZero()) ||
             ((CFPf = dyn_cast<ConstantFP>(FalseVal)) &&
              !CFPf->getValueAPF().isZero()))
         return replaceInstUsesWith(SI, FalseVal);
       }
       // Transform (X une Y) ? X : Y  -> X
       if (FCI->getPredicate() == FCmpInst::FCMP_UNE) {
         // This is not safe in general for floating point:

test/Transforms/InstCombine/select-of-bittest.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 ; https://bugs.llvm.org/show_bug.cgi?id=36950
 
 ; These all should be just and+icmp, there should be no select.
 ; https://rise4fun.com/Alive/uiH
 
 define i32 @and_lshr_and(i32) {
 ; CHECK-LABEL: @and_lshr_and(
-; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP0:%.*]], 1
-; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq i32 [[TMP2]], 0
-; CHECK-NEXT:    [[TMP4:%.*]] = lshr i32 [[TMP0]], 1
-; CHECK-NEXT:    [[TMP5:%.*]] = and i32 [[TMP4]], 1
-; CHECK-NEXT:    [[TMP6:%.*]] = select i1 [[TMP3]], i32 [[TMP5]], i32 1
-; CHECK-NEXT:    ret i32 [[TMP6]]
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP0:%.*]], 3
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne i32 [[TMP2]], 0
+; CHECK-NEXT:    [[TMP4:%.*]] = zext i1 [[TMP3]] to i32
+; CHECK-NEXT:    ret i32 [[TMP4]]
 ;
   %2 = and i32 %0, 1
   %3 = icmp eq i32 %2, 0
   %4 = lshr i32 %0, 1
   %5 = and i32 %4, 1
   %6 = select i1 %3, i32 %5, i32 1
   ret i32 %6
 }
 
 define <2 x i32> @and_lshr_and_splatvec(<2 x i32>) {
 ; CHECK-LABEL: @and_lshr_and_splatvec(
-; CHECK-NEXT:    [[TMP2:%.*]] = and <2 x i32> [[TMP0:%.*]], <i32 1, i32 1>
-; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq <2 x i32> [[TMP2]], zeroinitializer
-; CHECK-NEXT:    [[TMP4:%.*]] = lshr <2 x i32> [[TMP0]], <i32 1, i32 1>
-; CHECK-NEXT:    [[TMP5:%.*]] = and <2 x i32> [[TMP4]], <i32 1, i32 1>
-; CHECK-NEXT:    [[TMP6:%.*]] = select <2 x i1> [[TMP3]], <2 x i32> [[TMP5]], <2 x i32> <i32 1, i32 1>
-; CHECK-NEXT:    ret <2 x i32> [[TMP6]]
+; CHECK-NEXT:    [[TMP2:%.*]] = and <2 x i32> [[TMP0:%.*]], <i32 3, i32 3>
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne <2 x i32> [[TMP2]], zeroinitializer
+; CHECK-NEXT:    [[TMP4:%.*]] = zext <2 x i1> [[TMP3]] to <2 x i32>
+; CHECK-NEXT:    ret <2 x i32> [[TMP4]]
 ;
   %2 = and <2 x i32> %0, <i32 1, i32 1>
   %3 = icmp eq <2 x i32> %2, <i32 0, i32 0>
   %4 = lshr <2 x i32> %0, <i32 1, i32 1>
   %5 = and <2 x i32> %4, <i32 1, i32 1>
   %6 = select <2 x i1> %3, <2 x i32> %5, <2 x i32> <i32 1, i32 1>
   ret <2 x i32> %6
 }
 
 define <2 x i32> @and_lshr_and_vec_v0(<2 x i32>) {
 ; CHECK-LABEL: @and_lshr_and_vec_v0(
-; CHECK-NEXT:    [[TMP2:%.*]] = and <2 x i32> [[TMP0:%.*]], <i32 1, i32 4>
-; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq <2 x i32> [[TMP2]], zeroinitializer
-; CHECK-NEXT:    [[TMP4:%.*]] = lshr <2 x i32> [[TMP0]], <i32 1, i32 1>
-; CHECK-NEXT:    [[TMP5:%.*]] = and <2 x i32> [[TMP4]], <i32 1, i32 1>
-; CHECK-NEXT:    [[TMP6:%.*]] = select <2 x i1> [[TMP3]], <2 x i32> [[TMP5]], <2 x i32> <i32 1, i32 1>
-; CHECK-NEXT:    ret <2 x i32> [[TMP6]]
+; CHECK-NEXT:    [[TMP2:%.*]] = and <2 x i32> [[TMP0:%.*]], <i32 3, i32 6>
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne <2 x i32> [[TMP2]], zeroinitializer
+; CHECK-NEXT:    [[TMP4:%.*]] = zext <2 x i1> [[TMP3]] to <2 x i32>
+; CHECK-NEXT:    ret <2 x i32> [[TMP4]]
 ;
   %2 = and <2 x i32> %0, <i32 1, i32 4> ; mask is not splat
   %3 = icmp eq <2 x i32> %2, <i32 0, i32 0>
   %4 = lshr <2 x i32> %0, <i32 1, i32 1>
   %5 = and <2 x i32> %4, <i32 1, i32 1>
   %6 = select <2 x i1> %3, <2 x i32> %5, <2 x i32> <i32 1, i32 1>
   ret <2 x i32> %6
 }
 
 define <2 x i32> @and_lshr_and_vec_v1(<2 x i32>) {
 ; CHECK-LABEL: @and_lshr_and_vec_v1(
-; CHECK-NEXT:    [[TMP2:%.*]] = and <2 x i32> [[TMP0:%.*]], <i32 1, i32 1>
-; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq <2 x i32> [[TMP2]], zeroinitializer
-; CHECK-NEXT:    [[TMP4:%.*]] = lshr <2 x i32> [[TMP0]], <i32 1, i32 2>
-; CHECK-NEXT:    [[TMP5:%.*]] = and <2 x i32> [[TMP4]], <i32 1, i32 1>
-; CHECK-NEXT:    [[TMP6:%.*]] = select <2 x i1> [[TMP3]], <2 x i32> [[TMP5]], <2 x i32> <i32 1, i32 1>
-; CHECK-NEXT:    ret <2 x i32> [[TMP6]]
+; CHECK-NEXT:    [[TMP2:%.*]] = and <2 x i32> [[TMP0:%.*]], <i32 3, i32 5>
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne <2 x i32> [[TMP2]], zeroinitializer
+; CHECK-NEXT:    [[TMP4:%.*]] = zext <2 x i1> [[TMP3]] to <2 x i32>
+; CHECK-NEXT:    ret <2 x i32> [[TMP4]]
 ;
   %2 = and <2 x i32> %0, <i32 1, i32 1>
   %3 = icmp eq <2 x i32> %2, <i32 0, i32 0>
   %4 = lshr <2 x i32> %0, <i32 1, i32 2> ; shift is not splat
   %5 = and <2 x i32> %4, <i32 1, i32 1>
   %6 = select <2 x i1> %3, <2 x i32> %5, <2 x i32> <i32 1, i32 1>
   ret <2 x i32> %6
 }
 
 define <2 x i32> @and_lshr_and_vec_v2(<2 x i32>) {
 ; CHECK-LABEL: @and_lshr_and_vec_v2(
-; CHECK-NEXT:    [[TMP2:%.*]] = and <2 x i32> [[TMP0:%.*]], <i32 8, i32 1>
-; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq <2 x i32> [[TMP2]], zeroinitializer
-; CHECK-NEXT:    [[TMP4:%.*]] = lshr <2 x i32> [[TMP0]], <i32 2, i32 1>
-; CHECK-NEXT:    [[TMP5:%.*]] = and <2 x i32> [[TMP4]], <i32 1, i32 1>
-; CHECK-NEXT:    [[TMP6:%.*]] = select <2 x i1> [[TMP3]], <2 x i32> [[TMP5]], <2 x i32> <i32 1, i32 1>
-; CHECK-NEXT:    ret <2 x i32> [[TMP6]]
+; CHECK-NEXT:    [[TMP2:%.*]] = and <2 x i32> [[TMP0:%.*]], <i32 12, i32 3>
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne <2 x i32> [[TMP2]], zeroinitializer
+; CHECK-NEXT:    [[TMP4:%.*]] = zext <2 x i1> [[TMP3]] to <2 x i32>
+; CHECK-NEXT:    ret <2 x i32> [[TMP4]]
 ;
   %2 = and <2 x i32> %0, <i32 8, i32 1> ; mask is not splat
   %3 = icmp eq <2 x i32> %2, <i32 0, i32 0>
   %4 = lshr <2 x i32> %0, <i32 2, i32 1> ; shift is not splat
   %5 = and <2 x i32> %4, <i32 1, i32 1>
   %6 = select <2 x i1> %3, <2 x i32> %5, <2 x i32> <i32 1, i32 1>
   ret <2 x i32> %6
 }
;
   %4 = lshr <3 x i32> %0, <i32 1, i32 undef, i32 1>
   %5 = and <3 x i32> %4, <i32 1, i32 undef, i32 1>
   %6 = select <3 x i1> %3, <3 x i32> %5, <3 x i32> <i32 1, i32 undef, i32 1>
   ret <3 x i32> %6
 }
 
 define i32 @and_and(i32) {
 ; CHECK-LABEL: @and_and(
-; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP0:%.*]], 2
-; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq i32 [[TMP2]], 0
-; CHECK-NEXT:    [[TMP4:%.*]] = and i32 [[TMP0]], 1
-; CHECK-NEXT:    [[TMP5:%.*]] = select i1 [[TMP3]], i32 [[TMP4]], i32 1
-; CHECK-NEXT:    ret i32 [[TMP5]]
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP0:%.*]], 3
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne i32 [[TMP2]], 0
+; CHECK-NEXT:    [[TMP4:%.*]] = zext i1 [[TMP3]] to i32
+; CHECK-NEXT:    ret i32 [[TMP4]]
 ;
   %2 = and i32 %0, 2
   %3 = icmp eq i32 %2, 0
   %4 = and i32 %0, 1
   %5 = select i1 %3, i32 %4, i32 1
   ret i32 %5
 }
 
 define <2 x i32> @and_and_splatvec(<2 x i32>) {
 ; CHECK-LABEL: @and_and_splatvec(
-; CHECK-NEXT:    [[TMP2:%.*]] = and <2 x i32> [[TMP0:%.*]], <i32 2, i32 2>
-; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq <2 x i32> [[TMP2]], zeroinitializer
-; CHECK-NEXT:    [[TMP4:%.*]] = and <2 x i32> [[TMP0]], <i32 1, i32 1>
-; CHECK-NEXT:    [[TMP5:%.*]] = select <2 x i1> [[TMP3]], <2 x i32> [[TMP4]], <2 x i32> <i32 1, i32 1>
-; CHECK-NEXT:    ret <2 x i32> [[TMP5]]
+; CHECK-NEXT:    [[TMP2:%.*]] = and <2 x i32> [[TMP0:%.*]], <i32 3, i32 3>
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne <2 x i32> [[TMP2]], zeroinitializer
+; CHECK-NEXT:    [[TMP4:%.*]] = zext <2 x i1> [[TMP3]] to <2 x i32>
+; CHECK-NEXT:    ret <2 x i32> [[TMP4]]
 ;
   %2 = and <2 x i32> %0, <i32 2, i32 2>
   %3 = icmp eq <2 x i32> %2, <i32 0, i32 0>
   %4 = and <2 x i32> %0, <i32 1, i32 1>
   %5 = select <2 x i1> %3, <2 x i32> %4, <2 x i32> <i32 1, i32 1>
   ret <2 x i32> %5
 }
 
 define <2 x i32> @and_and_vec(<2 x i32>) {
 ; CHECK-LABEL: @and_and_vec(
-; CHECK-NEXT:    [[TMP2:%.*]] = and <2 x i32> [[TMP0:%.*]], <i32 6, i32 2>
-; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq <2 x i32> [[TMP2]], zeroinitializer
-; CHECK-NEXT:    [[TMP4:%.*]] = and <2 x i32> [[TMP0]], <i32 1, i32 1>
-; CHECK-NEXT:    [[TMP5:%.*]] = select <2 x i1> [[TMP3]], <2 x i32> [[TMP4]], <2 x i32> <i32 1, i32 1>
-; CHECK-NEXT:    ret <2 x i32> [[TMP5]]
+; CHECK-NEXT:    [[TMP2:%.*]] = and <2 x i32> [[TMP0:%.*]], <i32 7, i32 3>
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne <2 x i32> [[TMP2]], zeroinitializer
+; CHECK-NEXT:    [[TMP4:%.*]] = zext <2 x i1> [[TMP3]] to <2 x i32>
+; CHECK-NEXT:    ret <2 x i32> [[TMP4]]
 ;
   %2 = and <2 x i32> %0, <i32 6, i32 2> ; mask is not splat
   %3 = icmp eq <2 x i32> %2, <i32 0, i32 0>
   %4 = and <2 x i32> %0, <i32 1, i32 1>
   %5 = select <2 x i1> %3, <2 x i32> %4, <2 x i32> <i32 1, i32 1>
   ret <2 x i32> %5
 }
 

 }
 
 ; ============================================================================ ;
 ; Mask can be a variable, too.
 ; ============================================================================ ;
 
 define i32 @f_var0(i32, i32) {
 ; CHECK-LABEL: @f_var0(
-; CHECK-NEXT:    [[TMP3:%.*]] = and i32 [[TMP0:%.*]], [[TMP1:%.*]]
-; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq i32 [[TMP3]], 0
-; CHECK-NEXT:    [[TMP5:%.*]] = lshr i32 [[TMP0]], 1
-; CHECK-NEXT:    [[TMP6:%.*]] = and i32 [[TMP5]], 1
-; CHECK-NEXT:    [[TMP7:%.*]] = select i1 [[TMP4]], i32 [[TMP6]], i32 1
-; CHECK-NEXT:    ret i32 [[TMP7]]
+; CHECK-NEXT:    [[TMP3:%.*]] = or i32 [[TMP1:%.*]], 2
+; CHECK-NEXT:    [[TMP4:%.*]] = and i32 [[TMP3]], [[TMP0:%.*]]
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp ne i32 [[TMP4]], 0
+; CHECK-NEXT:    [[TMP6:%.*]] = zext i1 [[TMP5]] to i32
+; CHECK-NEXT:    ret i32 [[TMP6]]
 ;
   %3 = and i32 %0, %1
   %4 = icmp eq i32 %3, 0
   %5 = lshr i32 %0, 1
   %6 = and i32 %5, 1
   %7 = select i1 %4, i32 %6, i32 1
   ret i32 %7
 }
 
 define <2 x i32> @f_var0_splatvec(<2 x i32>, <2 x i32>) {
 ; CHECK-LABEL: @f_var0_splatvec(
-; CHECK-NEXT:    [[TMP3:%.*]] = and <2 x i32> [[TMP0:%.*]], [[TMP1:%.*]]
-; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq <2 x i32> [[TMP3]], zeroinitializer
-; CHECK-NEXT:    [[TMP5:%.*]] = lshr <2 x i32> [[TMP0]], <i32 1, i32 1>
-; CHECK-NEXT:    [[TMP6:%.*]] = and <2 x i32> [[TMP5]], <i32 1, i32 1>
-; CHECK-NEXT:    [[TMP7:%.*]] = select <2 x i1> [[TMP4]], <2 x i32> [[TMP6]], <2 x i32> <i32 1, i32 1>
-; CHECK-NEXT:    ret <2 x i32> [[TMP7]]
+; CHECK-NEXT:    [[TMP3:%.*]] = or <2 x i32> [[TMP1:%.*]], <i32 2, i32 2>
+; CHECK-NEXT:    [[TMP4:%.*]] = and <2 x i32> [[TMP3]], [[TMP0:%.*]]
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp ne <2 x i32> [[TMP4]], zeroinitializer
+; CHECK-NEXT:    [[TMP6:%.*]] = zext <2 x i1> [[TMP5]] to <2 x i32>
+; CHECK-NEXT:    ret <2 x i32> [[TMP6]]
 ;
   %3 = and <2 x i32> %0, %1
   %4 = icmp eq <2 x i32> %3, <i32 0, i32 0>
   %5 = lshr <2 x i32> %0, <i32 1, i32 1>
   %6 = and <2 x i32> %5, <i32 1, i32 1>
   %7 = select <2 x i1> %4, <2 x i32> %6, <2 x i32> <i32 1, i32 1>
   ret <2 x i32> %7
 }
 
 define <2 x i32> @f_var0_vec(<2 x i32>, <2 x i32>) {
 ; CHECK-LABEL: @f_var0_vec(
-; CHECK-NEXT:    [[TMP3:%.*]] = and <2 x i32> [[TMP0:%.*]], [[TMP1:%.*]]
-; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq <2 x i32> [[TMP3]], zeroinitializer
-; CHECK-NEXT:    [[TMP5:%.*]] = lshr <2 x i32> [[TMP0]], <i32 1, i32 2>
-; CHECK-NEXT:    [[TMP6:%.*]] = and <2 x i32> [[TMP5]], <i32 1, i32 1>
-; CHECK-NEXT:    [[TMP7:%.*]] = select <2 x i1> [[TMP4]], <2 x i32> [[TMP6]], <2 x i32> <i32 1, i32 1>
-; CHECK-NEXT:    ret <2 x i32> [[TMP7]]
+; CHECK-NEXT:    [[TMP3:%.*]] = or <2 x i32> [[TMP1:%.*]], <i32 2, i32 4>
+; CHECK-NEXT:    [[TMP4:%.*]] = and <2 x i32> [[TMP3]], [[TMP0:%.*]]
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp ne <2 x i32> [[TMP4]], zeroinitializer
+; CHECK-NEXT:    [[TMP6:%.*]] = zext <2 x i1> [[TMP5]] to <2 x i32>
+; CHECK-NEXT:    ret <2 x i32> [[TMP6]]
 ;
   %3 = and <2 x i32> %0, %1
   %4 = icmp eq <2 x i32> %3, <i32 0, i32 0>
   %5 = lshr <2 x i32> %0, <i32 1, i32 2> ; shift is not splat
   %6 = and <2 x i32> %5, <i32 1, i32 1>
   %7 = select <2 x i1> %4, <2 x i32> %6, <2 x i32> <i32 1, i32 1>
   ret <2 x i32> %7
 }
;
   %5 = lshr <3 x i32> %0, <i32 1, i32 undef, i32 1>
   %6 = and <3 x i32> %5, <i32 1, i32 undef, i32 1>
   %7 = select <3 x i1> %4, <3 x i32> %6, <3 x i32> <i32 1, i32 undef, i32 1>
   ret <3 x i32> %7
 }
 
 define i32 @f_var1(i32, i32) {
 ; CHECK-LABEL: @f_var1(
-; CHECK-NEXT:    [[TMP3:%.*]] = and i32 [[TMP0:%.*]], [[TMP1:%.*]]
-; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq i32 [[TMP3]], 0
-; CHECK-NEXT:    [[TMP5:%.*]] = and i32 [[TMP0]], 1
-; CHECK-NEXT:    [[TMP6:%.*]] = select i1 [[TMP4]], i32 [[TMP5]], i32 1
+; CHECK-NEXT:    [[TMP3:%.*]] = or i32 [[TMP1:%.*]], 1
+; CHECK-NEXT:    [[TMP4:%.*]] = and i32 [[TMP3]], [[TMP0:%.*]]
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp ne i32 [[TMP4]], 0
+; CHECK-NEXT:    [[TMP6:%.*]] = zext i1 [[TMP5]] to i32
 ; CHECK-NEXT:    ret i32 [[TMP6]]
 ;
   %3 = and i32 %0, %1
   %4 = icmp eq i32 %3, 0
   %5 = and i32 %0, 1
   %6 = select i1 %4, i32 %5, i32 1
   ret i32 %6
 }
 
 define <2 x i32> @f_var1_vec(<2 x i32>, <2 x i32>) {
 ; CHECK-LABEL: @f_var1_vec(
-; CHECK-NEXT:    [[TMP3:%.*]] = and <2 x i32> [[TMP0:%.*]], [[TMP1:%.*]]
-; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq <2 x i32> [[TMP3]], zeroinitializer
-; CHECK-NEXT:    [[TMP5:%.*]] = and <2 x i32> [[TMP0]], <i32 1, i32 1>
-; CHECK-NEXT:    [[TMP6:%.*]] = select <2 x i1> [[TMP4]], <2 x i32> [[TMP5]], <2 x i32> <i32 1, i32 1>
+; CHECK-NEXT:    [[TMP3:%.*]] = or <2 x i32> [[TMP1:%.*]], <i32 1, i32 1>
+; CHECK-NEXT:    [[TMP4:%.*]] = and <2 x i32> [[TMP3]], [[TMP0:%.*]]
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp ne <2 x i32> [[TMP4]], zeroinitializer
+; CHECK-NEXT:    [[TMP6:%.*]] = zext <2 x i1> [[TMP5]] to <2 x i32>
 ; CHECK-NEXT:    ret <2 x i32> [[TMP6]]
 ;
   %3 = and <2 x i32> %0, %1
   %4 = icmp eq <2 x i32> %3, <i32 0, i32 0>
   %5 = and <2 x i32> %0, <i32 1, i32 1>
   %6 = select <2 x i1> %4, <2 x i32> %5, <2 x i32> <i32 1, i32 1>
   ret <2 x i32> %6
 }

 }
 
 ; ============================================================================ ;
 ; Shift can be a variable, too.
 ; ============================================================================ ;
 
 define i32 @f_var2(i32, i32) {
 ; CHECK-LABEL: @f_var2(
-; CHECK-NEXT:    [[TMP3:%.*]] = and i32 [[TMP0:%.*]], 1
-; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq i32 [[TMP3]], 0
-; CHECK-NEXT:    [[TMP5:%.*]] = lshr i32 [[TMP0]], [[TMP1:%.*]]
-; CHECK-NEXT:    [[TMP6:%.*]] = and i32 [[TMP5]], 1
-; CHECK-NEXT:    [[TMP7:%.*]] = select i1 [[TMP4]], i32 [[TMP6]], i32 1
+; CHECK-NEXT:    [[TMP3:%.*]] = shl i32 1, [[TMP1:%.*]]
+; CHECK-NEXT:    [[TMP4:%.*]] = or i32 [[TMP3]], 1
+; CHECK-NEXT:    [[TMP5:%.*]] = and i32 [[TMP4]], [[TMP0:%.*]]
+; CHECK-NEXT:    [[TMP6:%.*]] = icmp ne i32 [[TMP5]], 0
+; CHECK-NEXT:    [[TMP7:%.*]] = zext i1 [[TMP6]] to i32
 ; CHECK-NEXT:    ret i32 [[TMP7]]
 ;
   %3 = and i32 %0, 1
   %4 = icmp eq i32 %3, 0
   %5 = lshr i32 %0, %1
   %6 = and i32 %5, 1
   %7 = select i1 %4, i32 %6, i32 1
   ret i32 %7
 }
 
 define <2 x i32> @f_var2_splatvec(<2 x i32>, <2 x i32>) {
 ; CHECK-LABEL: @f_var2_splatvec(
-; CHECK-NEXT:    [[TMP3:%.*]] = and <2 x i32> [[TMP0:%.*]], <i32 1, i32 1>
-; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq <2 x i32> [[TMP3]], zeroinitializer
-; CHECK-NEXT:    [[TMP5:%.*]] = lshr <2 x i32> [[TMP0]], [[TMP1:%.*]]
-; CHECK-NEXT:    [[TMP6:%.*]] = and <2 x i32> [[TMP5]], <i32 1, i32 1>
-; CHECK-NEXT:    [[TMP7:%.*]] = select <2 x i1> [[TMP4]], <2 x i32> [[TMP6]], <2 x i32> <i32 1, i32 1>
+; CHECK-NEXT:    [[TMP3:%.*]] = shl <2 x i32> <i32 1, i32 1>, [[TMP1:%.*]]
+; CHECK-NEXT:    [[TMP4:%.*]] = or <2 x i32> [[TMP3]], <i32 1, i32 1>
+; CHECK-NEXT:    [[TMP5:%.*]] = and <2 x i32> [[TMP4]], [[TMP0:%.*]]
+; CHECK-NEXT:    [[TMP6:%.*]] = icmp ne <2 x i32> [[TMP5]], zeroinitializer
+; CHECK-NEXT:    [[TMP7:%.*]] = zext <2 x i1> [[TMP6]] to <2 x i32>
 ; CHECK-NEXT:    ret <2 x i32> [[TMP7]]
 ;
   %3 = and <2 x i32> %0, <i32 1, i32 1>
   %4 = icmp eq <2 x i32> %3, <i32 0, i32 0>
   %5 = lshr <2 x i32> %0, %1
   %6 = and <2 x i32> %5, <i32 1, i32 1>
   %7 = select <2 x i1> %4, <2 x i32> %6, <2 x i32> <i32 1, i32 1>
   ret <2 x i32> %7
 }
 
 define <2 x i32> @f_var2_vec(<2 x i32>, <2 x i32>) {
 ; CHECK-LABEL: @f_var2_vec(
-; CHECK-NEXT:    [[TMP3:%.*]] = and <2 x i32> [[TMP0:%.*]], <i32 2, i32 1>
-; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq <2 x i32> [[TMP3]], zeroinitializer
-; CHECK-NEXT:    [[TMP5:%.*]] = lshr <2 x i32> [[TMP0]], [[TMP1:%.*]]
-; CHECK-NEXT:    [[TMP6:%.*]] = and <2 x i32> [[TMP5]], <i32 1, i32 1>
-; CHECK-NEXT:    [[TMP7:%.*]] = select <2 x i1> [[TMP4]], <2 x i32> [[TMP6]], <2 x i32> <i32 1, i32 1>
+; CHECK-NEXT:    [[TMP3:%.*]] = shl <2 x i32> <i32 1, i32 1>, [[TMP1:%.*]]
+; CHECK-NEXT:    [[TMP4:%.*]] = or <2 x i32> [[TMP3]], <i32 2, i32 1>
+; CHECK-NEXT:    [[TMP5:%.*]] = and <2 x i32> [[TMP4]], [[TMP0:%.*]]
+; CHECK-NEXT:    [[TMP6:%.*]] = icmp ne <2 x i32> [[TMP5]], zeroinitializer
+; CHECK-NEXT:    [[TMP7:%.*]] = zext <2 x i1> [[TMP6]] to <2 x i32>
 ; CHECK-NEXT:    ret <2 x i32> [[TMP7]]
 ;
   %3 = and <2 x i32> %0, <i32 2, i32 1> ; mask is not splat
   %4 = icmp eq <2 x i32> %3, <i32 0, i32 0>
   %5 = lshr <2 x i32> %0, %1
   %6 = and <2 x i32> %5, <i32 1, i32 1>
   %7 = select <2 x i1> %4, <2 x i32> %6, <2 x i32> <i32 1, i32 1>
   ret <2 x i32> %7

 }
 
 ; ============================================================================ ;
 ; The worst case: both Mask and Shift are variables
 ; ============================================================================ ;
 
 define i32 @f_var3(i32, i32, i32) {
 ; CHECK-LABEL: @f_var3(
-; CHECK-NEXT:    [[TMP4:%.*]] = and i32 [[TMP0:%.*]], [[TMP1:%.*]]
-; CHECK-NEXT:    [[TMP5:%.*]] = icmp eq i32 [[TMP4]], 0
-; CHECK-NEXT:    [[TMP6:%.*]] = lshr i32 [[TMP0]], [[TMP2:%.*]]
-; CHECK-NEXT:    [[TMP7:%.*]] = and i32 [[TMP6]], 1
-; CHECK-NEXT:    [[TMP8:%.*]] = select i1 [[TMP5]], i32 [[TMP7]], i32 1
+; CHECK-NEXT:    [[TMP4:%.*]] = shl i32 1, [[TMP2:%.*]]
+; CHECK-NEXT:    [[TMP5:%.*]] = or i32 [[TMP4]], [[TMP1:%.*]]
+; CHECK-NEXT:    [[TMP6:%.*]] = and i32 [[TMP5]], [[TMP0:%.*]]
+; CHECK-NEXT:    [[TMP7:%.*]] = icmp ne i32 [[TMP6]], 0
+; CHECK-NEXT:    [[TMP8:%.*]] = zext i1 [[TMP7]] to i32
 ; CHECK-NEXT:    ret i32 [[TMP8]]
 ;
   %4 = and i32 %0, %1
   %5 = icmp eq i32 %4, 0
   %6 = lshr i32 %0, %2
   %7 = and i32 %6, 1
   %8 = select i1 %5, i32 %7, i32 1
   ret i32 %8
 }
 
 define <2 x i32> @f_var3_splatvec(<2 x i32>, <2 x i32>, <2 x i32>) {
 ; CHECK-LABEL: @f_var3_splatvec(
-; CHECK-NEXT:    [[TMP4:%.*]] = and <2 x i32> [[TMP0:%.*]], [[TMP1:%.*]]
-; CHECK-NEXT:    [[TMP5:%.*]] = icmp eq <2 x i32> [[TMP4]], zeroinitializer
-; CHECK-NEXT:    [[TMP6:%.*]] = lshr <2 x i32> [[TMP0]], [[TMP2:%.*]]
-; CHECK-NEXT:    [[TMP7:%.*]] = and <2 x i32> [[TMP6]], <i32 1, i32 1>
-; CHECK-NEXT:    [[TMP8:%.*]] = select <2 x i1> [[TMP5]], <2 x i32> [[TMP7]], <2 x i32> <i32 1, i32 1>
+; CHECK-NEXT:    [[TMP4:%.*]] = shl <2 x i32> <i32 1, i32 1>, [[TMP2:%.*]]
+; CHECK-NEXT:    [[TMP5:%.*]] = or <2 x i32> [[TMP4]], [[TMP1:%.*]]
+; CHECK-NEXT:    [[TMP6:%.*]] = and <2 x i32> [[TMP5]], [[TMP0:%.*]]
+; CHECK-NEXT:    [[TMP7:%.*]] = icmp ne <2 x i32> [[TMP6]], zeroinitializer
+; CHECK-NEXT:    [[TMP8:%.*]] = zext <2 x i1> [[TMP7]] to <2 x i32>
 ; CHECK-NEXT:    ret <2 x i32> [[TMP8]]
 ;
   %4 = and <2 x i32> %0, %1
   %5 = icmp eq <2 x i32> %4, <i32 0, i32 0>
   %6 = lshr <2 x i32> %0, %2
   %7 = and <2 x i32> %6, <i32 1, i32 1>
   %8 = select <2 x i1> %5, <2 x i32> %7, <2 x i32> <i32 1, i32 1>
   ret <2 x i32> %8