[InstCombine] refine select-of-constants to bitwise ops

[spatel]

Summary

This is an enhancement to the proposal at D45862 where we add logic for the special case when a cmp+select can clearly be reduced to just a bitwise logic instruction. The goal is to remove cases where we are not improving the IR instruction count when doing these select transforms, and in all cases here that is true.

I think this will have the same results on the 3-way compare tests that are proposed in the other patch. We should commit those first, so we can see the diffs here or in the other patch.

I looked some at x86 and AArch64 codegen with this change, and we're going to get more cmov/vblend and csel/bsl because the DAG doesn't have replacements for all of these folds. In some cases, the changes look better and others it seems worse, but I suspect we'll have to run detailed perf tests per uarch to know the true perf outcome.

[spatel]

The bit hackery isn't clear to me even after staring at this all day. Here's the Alive link I posted earlier in case it helps:
https://rise4fun.com/Alive/XG7
Suggestions to improve the comments and code welcome.

Also, the tests reveal a couple of simpler but non-obvious folds that we seem to be missing:
https://rise4fun.com/Alive/AeL

Name: add_to_xor
%a = and i8 %x, 128
%r = add i8 %a, 131
=>
%r = xor i8 %a, 131

Name: orxor
%a = or i8 %x, -9
%r = xor i8 %a, 8
=>
%a1 = xor i8 %x, -1
%r = or i8 %a1, -9

[spatel]

Patch updated:
Rebased to include 3-way compare tests added at rL331100.

[spatel]

Ping.

This patch improves the motivating cases (3-way-compare) without the regressions in D45862.

This doesn't preclude more canonicalization to select, but if we want any more select IR than this, then I think we must add folds to the DAGCombiner first.

[mkazantsev]

LGTM

lib/Transforms/InstCombine/InstCombineSelect.cpp

if (ICmpInst::isEquality(Pred)) {
     if (!AndMask.isPowerOf2())
       return nullptr;
 
     CreateAnd = true;
   } else {
     return nullptr;
   }
 
-  // If both select arms are non-zero see if we have a select of the form
-  // 'x ? 2^n + TC : FC'. Then we can offset both arms by C, use the logic
-  // for 'x ? 2^n : 0' and fix the thing up at the end.
+  // In general, when both constants are non-zero, we would need an offset to
+  // replace the select. This would require more instructions than we started
+  // with. But there's one special-case that we handle here because it can
+  // simplify/reduce the instructions.
   APInt TC = *SelTC;
   APInt FC = *SelFC;
-  APInt Offset(TC.getBitWidth(), 0);
   if (!TC.isNullValue() && !FC.isNullValue()) {
-    if ((TC - FC).isPowerOf2())
-      Offset = FC;
-    else if ((FC - TC).isPowerOf2())
-      Offset = TC;
-    else
-      return nullptr;
-
-    // Adjust TC and FC by the offset.
-    TC -= Offset;
-    FC -= Offset;
+    // If the select constants differ by exactly one bit and that's the same
+    // bit that is masked and checked by the select condition, the select can
+    // be replaced by bitwise logic to set/clear one bit of the constant result.
+    if (TC.getBitWidth() != AndMask.getBitWidth() || (TC ^ FC) != AndMask)
+      return nullptr;
+    if (CreateAnd) {
+      // If we have to create an 'and', then we must kill the cmp to not
+      // increase the instruction count.
+      if (!Cmp->hasOneUse())
+        return nullptr;
+      V = Builder.CreateAnd(V, ConstantInt::get(SelType, AndMask));
+    }
+    bool ExtraBitInTC = TC.ugt(FC);
+    if (Pred == ICmpInst::ICMP_EQ) {
+      // If the masked bit in V is clear, clear or set the bit in the result:
+      // (V & AndMaskC) == 0 ? TC : FC --> (V & AndMaskC) ^ TC
+      // (V & AndMaskC) == 0 ? TC : FC --> (V & AndMaskC) | TC
+      Constant *C = ConstantInt::get(SelType, TC);
+      return ExtraBitInTC ? Builder.CreateXor(V, C) : Builder.CreateOr(V, C);
+    }
+    if (Pred == ICmpInst::ICMP_NE) {
+      // If the masked bit in V is set, set or clear the bit in the result:
+      // (V & AndMaskC) != 0 ? TC : FC --> (V & AndMaskC) | FC
+      // (V & AndMaskC) != 0 ? TC : FC --> (V & AndMaskC) ^ FC
+      Constant *C = ConstantInt::get(SelType, FC);
+      return ExtraBitInTC ? Builder.CreateOr(V, C) : Builder.CreateXor(V, C);
+    }
+    llvm_unreachable("Only expecting equality predicates");
   }
 
   // Make sure one of the select arms is a power-of-2.
   if (!TC.isPowerOf2() && !FC.isPowerOf2())
     return nullptr;
 
   // Determine which shift is needed to transform result of the 'and' into the
   // desired result.
static Value *foldSelectICmpAnd(SelectInst &Sel, ICmpInst *Cmp,
 
   // Okay, now we know that everything is set up, we just don't know whether we
   // have a icmp_ne or icmp_eq and whether the true or false val is the zero.
   bool ShouldNotVal = !TC.isNullValue();
   ShouldNotVal ^= Pred == ICmpInst::ICMP_NE;
   if (ShouldNotVal)
     V = Builder.CreateXor(V, ValC);
 
-  // Apply an offset if needed.
-  if (!Offset.isNullValue())
-    V = Builder.CreateAdd(V, ConstantInt::get(V->getType(), Offset));
   return V;
 }
 
 /// We want to turn code that looks like this:
 ///   %C = or %A, %B
 ///   %D = select %cond, %C, %A
 /// into:
 ///   %C = select %cond, %B, 0
Instruction *InstCombiner::foldSelectInstWithICmp(SelectInst &SI,
   Value *TrueVal = SI.getTrueValue();
   Value *FalseVal = SI.getFalseValue();
 
   if (Instruction *NewSel = canonicalizeMinMaxWithConstant(SI, *ICI, Builder))
     return NewSel;
 
   bool Changed = adjustMinMax(SI, *ICI);
 
-  ICmpInst::Predicate Pred = ICI->getPredicate();
-  Value *CmpLHS = ICI->getOperand(0);
-  Value *CmpRHS = ICI->getOperand(1);
-
-  // Transform (X >s -1) ? C1 : C2 --> ((X >>s 31) & (C2 - C1)) + C1
-  // and       (X <s  0) ? C2 : C1 --> ((X >>s 31) & (C2 - C1)) + C1
-  // FIXME: Type and constness constraints could be lifted, but we have to
-  //        watch code size carefully. We should consider xor instead of
-  //        sub/add when we decide to do that.
-  // TODO: Merge this with foldSelectICmpAnd somehow.
-  if (CmpLHS->getType()->isIntOrIntVectorTy() &&
-      CmpLHS->getType() == TrueVal->getType()) {
-    const APInt *C1, *C2;
-    if (match(TrueVal, m_APInt(C1)) && match(FalseVal, m_APInt(C2))) {
-      ICmpInst::Predicate Pred = ICI->getPredicate();
-      Value *X;
-      APInt Mask;
-      if (decomposeBitTestICmp(CmpLHS, CmpRHS, Pred, X, Mask, false)) {
-        if (Mask.isSignMask()) {
-          assert(X == CmpLHS && "Expected to use the compare input directly");
-          assert(ICmpInst::isEquality(Pred) && "Expected equality predicate");
-
-          if (Pred == ICmpInst::ICMP_NE)
-            std::swap(C1, C2);
-
-          // This shift results in either -1 or 0.
-          Value *AShr = Builder.CreateAShr(X, Mask.getBitWidth() - 1);
-
-          // Check if we can express the operation with a single or.
-          if (C2->isAllOnesValue())
-            return replaceInstUsesWith(SI, Builder.CreateOr(AShr, *C1));
-
-          Value *And = Builder.CreateAnd(AShr, *C2 - *C1);
-          return replaceInstUsesWith(SI, Builder.CreateAdd(And,
-                                        ConstantInt::get(And->getType(), *C1)));
-        }
-      }
-    }
-  }
-
   if (Value *V = foldSelectICmpAnd(SI, ICI, Builder))
     return replaceInstUsesWith(SI, V);
 
   // NOTE: if we wanted to, this is where to detect integer MIN/MAX
-
+  ICmpInst::Predicate Pred = ICI->getPredicate();
+  Value *CmpLHS = ICI->getOperand(0);
+  Value *CmpRHS = ICI->getOperand(1);
   if (CmpRHS != CmpLHS && isa<Constant>(CmpRHS)) {
     if (CmpLHS == TrueVal && Pred == ICmpInst::ICMP_EQ) {
       // Transform (X == C) ? X : Y -> (X == C) ? C : Y
       SI.setOperand(1, CmpRHS);
       Changed = true;
     } else if (CmpLHS == FalseVal && Pred == ICmpInst::ICMP_NE) {
       // Transform (X != C) ? Y : X -> (X != C) ? Y : C
       SI.setOperand(2, CmpRHS);

test/Transforms/InstCombine/rem.ll

 ; CHECK-NEXT:    ret i32 [[TMP2]]
 ;
   %A = urem i32 1, %X
   ret i32 %A
 }
 
 define i32 @test18(i16 %x, i32 %y) {
 ; CHECK-LABEL: @test18(
-; CHECK-NEXT:    [[TMP1:%.*]] = shl i16 %x, 3
-; CHECK-NEXT:    [[TMP2:%.*]] = and i16 [[TMP1]], 32
-; CHECK-NEXT:    [[TMP3:%.*]] = xor i16 [[TMP2]], 63
-; CHECK-NEXT:    [[TMP4:%.*]] = zext i16 [[TMP3]] to i32
-; CHECK-NEXT:    [[TMP5:%.*]] = and i32 [[TMP4]], %y
-; CHECK-NEXT:    ret i32 [[TMP5]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i16 [[X:%.*]], 4
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i16 [[TMP1]], 0
+; CHECK-NEXT:    [[TMP3:%.*]] = select i1 [[TMP2]], i32 63, i32 31
+; CHECK-NEXT:    [[TMP4:%.*]] = and i32 [[TMP3]], [[Y:%.*]]
+; CHECK-NEXT:    ret i32 [[TMP4]]
 ;
   %1 = and i16 %x, 4
   %2 = icmp ne i16 %1, 0
   %3 = select i1 %2, i32 32, i32 64
   %4 = urem i32 %y, %3
   ret i32 %4
 }
 

test/Transforms/InstCombine/select-icmp-and.ll

;
   %Y = and i1023 %X, 64
   %t = icmp ne i1023 %Y, 0
   %V = select i1 %t, i1023 64, i1023 0
   ret i1023 %V
 }
 
 define i32 @test35(i32 %x) {
 ; CHECK-LABEL: @test35(
-; CHECK-NEXT:    [[TMP1:%.*]] = ashr i32 [[X:%.*]], 31
-; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], 40
-; CHECK-NEXT:    [[TMP3:%.*]] = add nuw nsw i32 [[TMP2]], 60
-; CHECK-NEXT:    ret i32 [[TMP3]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[X:%.*]], -1
+; CHECK-NEXT:    [[COND:%.*]] = select i1 [[CMP]], i32 60, i32 100
+; CHECK-NEXT:    ret i32 [[COND]]
 ;
   %cmp = icmp sge i32 %x, 0
   %cond = select i1 %cmp, i32 60, i32 100
   ret i32 %cond
 }
 
 define <2 x i32> @test35vec(<2 x i32> %x) {
 ; CHECK-LABEL: @test35vec(
-; CHECK-NEXT:    [[TMP1:%.*]] = ashr <2 x i32> [[X:%.*]], <i32 31, i32 31>
-; CHECK-NEXT:    [[TMP2:%.*]] = and <2 x i32> [[TMP1]], <i32 40, i32 40>
-; CHECK-NEXT:    [[TMP3:%.*]] = add nuw nsw <2 x i32> [[TMP2]], <i32 60, i32 60>
-; CHECK-NEXT:    ret <2 x i32> [[TMP3]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt <2 x i32> [[X:%.*]], <i32 -1, i32 -1>
+; CHECK-NEXT:    [[COND:%.*]] = select <2 x i1> [[CMP]], <2 x i32> <i32 60, i32 60>, <2 x i32> <i32 100, i32 100>
+; CHECK-NEXT:    ret <2 x i32> [[COND]]
 ;
   %cmp = icmp sge <2 x i32> %x, <i32 0, i32 0>
   %cond = select <2 x i1> %cmp, <2 x i32> <i32 60, i32 60>, <2 x i32> <i32 100, i32 100>
   ret <2 x i32> %cond
 }
 
 ; Make sure we can still perform this optimization with a truncate present
 define i32 @test35_with_trunc(i64 %x) {
 ; CHECK-LABEL: @test35_with_trunc(
 ; CHECK-NEXT:    [[X1:%.*]] = trunc i64 [[X:%.*]] to i32
-; CHECK-NEXT:    [[TMP1:%.*]] = ashr i32 [[X1]], 31
-; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], 40
-; CHECK-NEXT:    [[TMP3:%.*]] = add nuw nsw i32 [[TMP2]], 60
-; CHECK-NEXT:    ret i32 [[TMP3]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[X1]], -1
+; CHECK-NEXT:    [[COND:%.*]] = select i1 [[CMP]], i32 60, i32 100
+; CHECK-NEXT:    ret i32 [[COND]]
 ;
   %x1 = trunc i64 %x to i32
   %cmp = icmp sge i32 %x1, 0
   %cond = select i1 %cmp, i32 60, i32 100
   ret i32 %cond
 }
 
 define i32 @test36(i32 %x) {
 ; CHECK-LABEL: @test36(
-; CHECK-NEXT:    [[TMP1:%.*]] = ashr i32 [[X:%.*]], 31
-; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], -40
-; CHECK-NEXT:    [[TMP3:%.*]] = add nsw i32 [[TMP2]], 100
-; CHECK-NEXT:    ret i32 [[TMP3]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[X:%.*]], 0
+; CHECK-NEXT:    [[COND:%.*]] = select i1 [[CMP]], i32 60, i32 100
+; CHECK-NEXT:    ret i32 [[COND]]
 ;
   %cmp = icmp slt i32 %x, 0
   %cond = select i1 %cmp, i32 60, i32 100
   ret i32 %cond
 }
 
 define <2 x i32> @test36vec(<2 x i32> %x) {
 ; CHECK-LABEL: @test36vec(
-; CHECK-NEXT:    [[TMP1:%.*]] = ashr <2 x i32> [[X:%.*]], <i32 31, i32 31>
-; CHECK-NEXT:    [[TMP2:%.*]] = and <2 x i32> [[TMP1]], <i32 -40, i32 -40>
-; CHECK-NEXT:    [[TMP3:%.*]] = add nsw <2 x i32> [[TMP2]], <i32 100, i32 100>
-; CHECK-NEXT:    ret <2 x i32> [[TMP3]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt <2 x i32> [[X:%.*]], zeroinitializer
+; CHECK-NEXT:    [[COND:%.*]] = select <2 x i1> [[CMP]], <2 x i32> <i32 60, i32 60>, <2 x i32> <i32 100, i32 100>
+; CHECK-NEXT:    ret <2 x i32> [[COND]]
 ;
   %cmp = icmp slt <2 x i32> %x, <i32 0, i32 0>
   %cond = select <2 x i1> %cmp, <2 x i32> <i32 60, i32 60>, <2 x i32> <i32 100, i32 100>
   ret <2 x i32> %cond
 }
 
 define i32 @test37(i32 %x) {
 ; CHECK-LABEL: @test37(
-; CHECK-NEXT:    [[TMP1:%.*]] = ashr i32 [[X:%.*]], 31
-; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], 1
-; CHECK-NEXT:    ret i32 [[TMP2]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[X:%.*]], -1
+; CHECK-NEXT:    [[COND:%.*]] = select i1 [[CMP]], i32 1, i32 -1
+; CHECK-NEXT:    ret i32 [[COND]]
 ;
   %cmp = icmp sgt i32 %x, -1
   %cond = select i1 %cmp, i32 1, i32 -1
   ret i32 %cond
 }
 
 define <2 x i32> @test37vec(<2 x i32> %x) {
 ; CHECK-LABEL: @test37vec(
-; CHECK-NEXT:    [[TMP1:%.*]] = ashr <2 x i32> [[X:%.*]], <i32 31, i32 31>
-; CHECK-NEXT:    [[TMP2:%.*]] = or <2 x i32> [[TMP1]], <i32 1, i32 1>
-; CHECK-NEXT:    ret <2 x i32> [[TMP2]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt <2 x i32> [[X:%.*]], <i32 -1, i32 -1>
+; CHECK-NEXT:    [[COND:%.*]] = select <2 x i1> [[CMP]], <2 x i32> <i32 1, i32 1>, <2 x i32> <i32 -1, i32 -1>
+; CHECK-NEXT:    ret <2 x i32> [[COND]]
 ;
   %cmp = icmp sgt <2 x i32> %x, <i32 -1, i32 -1>
   %cond = select <2 x i1> %cmp, <2 x i32> <i32 1, i32 1>, <2 x i32> <i32 -1, i32 -1>
   ret <2 x i32> %cond
 }
 
 define i32 @test65(i64 %x) {
 ; CHECK-LABEL: @test65(
-; CHECK-NEXT:    [[TMP1:%.*]] = lshr i64 [[X:%.*]], 3
-; CHECK-NEXT:    [[TMP2:%.*]] = trunc i64 [[TMP1]] to i32
-; CHECK-NEXT:    [[TMP3:%.*]] = and i32 [[TMP2]], 2
-; CHECK-NEXT:    [[TMP4:%.*]] = xor i32 [[TMP3]], 42
-; CHECK-NEXT:    ret i32 [[TMP4]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i64 [[X:%.*]], 16
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i64 [[TMP1]], 0
+; CHECK-NEXT:    [[TMP3:%.*]] = select i1 [[TMP2]], i32 42, i32 40
+; CHECK-NEXT:    ret i32 [[TMP3]]
 ;
   %1 = and i64 %x, 16
   %2 = icmp ne i64 %1, 0
   %3 = select i1 %2, i32 40, i32 42
   ret i32 %3
 }
 
 define <2 x i32> @test65vec(<2 x i64> %x) {
 ; CHECK-LABEL: @test65vec(
-; CHECK-NEXT:    [[TMP1:%.*]] = lshr <2 x i64> [[X:%.*]], <i64 3, i64 3>
-; CHECK-NEXT:    [[TMP2:%.*]] = trunc <2 x i64> [[TMP1]] to <2 x i32>
-; CHECK-NEXT:    [[TMP3:%.*]] = and <2 x i32> [[TMP2]], <i32 2, i32 2>
-; CHECK-NEXT:    [[TMP4:%.*]] = xor <2 x i32> [[TMP3]], <i32 42, i32 42>
-; CHECK-NEXT:    ret <2 x i32> [[TMP4]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i64> [[X:%.*]], <i64 16, i64 16>
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq <2 x i64> [[TMP1]], zeroinitializer
+; CHECK-NEXT:    [[TMP3:%.*]] = select <2 x i1> [[TMP2]], <2 x i32> <i32 42, i32 42>, <2 x i32> <i32 40, i32 40>
+; CHECK-NEXT:    ret <2 x i32> [[TMP3]]
 ;
   %1 = and <2 x i64> %x, <i64 16, i64 16>
   %2 = icmp ne <2 x i64> %1, zeroinitializer
   %3 = select <2 x i1> %2, <2 x i32> <i32 40, i32 40>, <2 x i32> <i32 42, i32 42>
   ret <2 x i32> %3
 }
 
 define i32 @test66(i64 %x) {
 ; CHECK-LABEL: @test66(
-; CHECK-NEXT:    [[TMP1:%.*]] = lshr i64 [[X:%.*]], 31
-; CHECK-NEXT:    [[TMP2:%.*]] = trunc i64 [[TMP1]] to i32
-; CHECK-NEXT:    [[TMP3:%.*]] = and i32 [[TMP2]], 2
-; CHECK-NEXT:    [[TMP4:%.*]] = xor i32 [[TMP3]], 42
-; CHECK-NEXT:    ret i32 [[TMP4]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i64 [[X:%.*]], 4294967296
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i64 [[TMP1]], 0
+; CHECK-NEXT:    [[TMP3:%.*]] = select i1 [[TMP2]], i32 42, i32 40
+; CHECK-NEXT:    ret i32 [[TMP3]]
 ;
   %1 = and i64 %x, 4294967296
   %2 = icmp ne i64 %1, 0
   %3 = select i1 %2, i32 40, i32 42
   ret i32 %3
 }
 
 define <2 x i32> @test66vec(<2 x i64> %x) {
 ; CHECK-LABEL: @test66vec(
-; CHECK-NEXT:    [[TMP1:%.*]] = lshr <2 x i64> [[X:%.*]], <i64 31, i64 31>
-; CHECK-NEXT:    [[TMP2:%.*]] = trunc <2 x i64> [[TMP1]] to <2 x i32>
-; CHECK-NEXT:    [[TMP3:%.*]] = and <2 x i32> [[TMP2]], <i32 2, i32 2>
-; CHECK-NEXT:    [[TMP4:%.*]] = xor <2 x i32> [[TMP3]], <i32 42, i32 42>
-; CHECK-NEXT:    ret <2 x i32> [[TMP4]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i64> [[X:%.*]], <i64 4294967296, i64 4294967296>
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq <2 x i64> [[TMP1]], zeroinitializer
+; CHECK-NEXT:    [[TMP3:%.*]] = select <2 x i1> [[TMP2]], <2 x i32> <i32 42, i32 42>, <2 x i32> <i32 40, i32 40>
+; CHECK-NEXT:    ret <2 x i32> [[TMP3]]
 ;
   %1 = and <2 x i64> %x, <i64 4294967296, i64 4294967296>
   %2 = icmp ne <2 x i64> %1, zeroinitializer
   %3 = select <2 x i1> %2, <2 x i32> <i32 40, i32 40>, <2 x i32> <i32 42, i32 42>
   ret <2 x i32> %3
 }
 
 ; Make sure we don't try to optimize a scalar 'and' with a vector select.
 define <2 x i32> @test66vec_scalar_and(i64 %x) {
 ; CHECK-LABEL: @test66vec_scalar_and(
 ; CHECK-NEXT:    [[TMP1:%.*]] = and i64 [[X:%.*]], 4294967296
 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i64 [[TMP1]], 0
 ; CHECK-NEXT:    [[TMP3:%.*]] = select i1 [[TMP2]], <2 x i32> <i32 42, i32 42>, <2 x i32> <i32 40, i32 40>
 ; CHECK-NEXT:    ret <2 x i32> [[TMP3]]
 ;
   %1 = and i64 %x, 4294967296
   %2 = icmp ne i64 %1, 0
   %3 = select i1 %2, <2 x i32> <i32 40, i32 40>, <2 x i32> <i32 42, i32 42>
   ret <2 x i32> %3
 }
 
 define i32 @test67(i16 %x) {
 ; CHECK-LABEL: @test67(
-; CHECK-NEXT:    [[TMP1:%.*]] = lshr i16 [[X:%.*]], 1
-; CHECK-NEXT:    [[TMP2:%.*]] = and i16 [[TMP1]], 2
-; CHECK-NEXT:    [[TMP3:%.*]] = xor i16 [[TMP2]], 42
-; CHECK-NEXT:    [[TMP4:%.*]] = zext i16 [[TMP3]] to i32
-; CHECK-NEXT:    ret i32 [[TMP4]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i16 [[X:%.*]], 4
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i16 [[TMP1]], 0
+; CHECK-NEXT:    [[TMP3:%.*]] = select i1 [[TMP2]], i32 42, i32 40
+; CHECK-NEXT:    ret i32 [[TMP3]]
 ;
   %1 = and i16 %x, 4
   %2 = icmp ne i16 %1, 0
   %3 = select i1 %2, i32 40, i32 42
   ret i32 %3
 }
 
 define <2 x i32> @test67vec(<2 x i16> %x) {
 ; CHECK-LABEL: @test67vec(
-; CHECK-NEXT:    [[TMP1:%.*]] = lshr <2 x i16> [[X:%.*]], <i16 1, i16 1>
-; CHECK-NEXT:    [[TMP2:%.*]] = and <2 x i16> [[TMP1]], <i16 2, i16 2>
-; CHECK-NEXT:    [[TMP3:%.*]] = xor <2 x i16> [[TMP2]], <i16 42, i16 42>
-; CHECK-NEXT:    [[TMP4:%.*]] = zext <2 x i16> [[TMP3]] to <2 x i32>
-; CHECK-NEXT:    ret <2 x i32> [[TMP4]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i16> [[X:%.*]], <i16 4, i16 4>
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq <2 x i16> [[TMP1]], zeroinitializer
+; CHECK-NEXT:    [[TMP3:%.*]] = select <2 x i1> [[TMP2]], <2 x i32> <i32 42, i32 42>, <2 x i32> <i32 40, i32 40>
+; CHECK-NEXT:    ret <2 x i32> [[TMP3]]
 ;
   %1 = and <2 x i16> %x, <i16 4, i16 4>
   %2 = icmp ne <2 x i16> %1, zeroinitializer
   %3 = select <2 x i1> %2, <2 x i32> <i32 40, i32 40>, <2 x i32> <i32 42, i32 42>
   ret <2 x i32> %3
 }
 
 define i32 @test71(i32 %x) {
 ; CHECK-LABEL: @test71(
-; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[X:%.*]], 6
-; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], 2
-; CHECK-NEXT:    [[TMP3:%.*]] = xor i32 [[TMP2]], 42
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[X:%.*]], 128
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[TMP1]], 0
+; CHECK-NEXT:    [[TMP3:%.*]] = select i1 [[TMP2]], i32 42, i32 40
 ; CHECK-NEXT:    ret i32 [[TMP3]]
 ;
   %1 = and i32 %x, 128
   %2 = icmp ne i32 %1, 0
   %3 = select i1 %2, i32 40, i32 42
   ret i32 %3
 }
 
 define <2 x i32> @test71vec(<2 x i32> %x) {
 ; CHECK-LABEL: @test71vec(
-; CHECK-NEXT:    [[TMP1:%.*]] = lshr <2 x i32> [[X:%.*]], <i32 6, i32 6>
-; CHECK-NEXT:    [[TMP2:%.*]] = and <2 x i32> [[TMP1]], <i32 2, i32 2>
-; CHECK-NEXT:    [[TMP3:%.*]] = xor <2 x i32> [[TMP2]], <i32 42, i32 42>
+; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i32> [[X:%.*]], <i32 128, i32 128>
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq <2 x i32> [[TMP1]], zeroinitializer
+; CHECK-NEXT:    [[TMP3:%.*]] = select <2 x i1> [[TMP2]], <2 x i32> <i32 42, i32 42>, <2 x i32> <i32 40, i32 40>
 ; CHECK-NEXT:    ret <2 x i32> [[TMP3]]
 ;
   %1 = and <2 x i32> %x, <i32 128, i32 128>
   %2 = icmp ne <2 x i32> %1, <i32 0, i32 0>
   %3 = select <2 x i1> %2, <2 x i32> <i32 40, i32 40>, <2 x i32> <i32 42, i32 42>
   ret <2 x i32> %3
 }
 
 define i32 @test72(i32 %x) {
 ; CHECK-LABEL: @test72(
-; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[X:%.*]], 6
-; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], 2
-; CHECK-NEXT:    [[TMP3:%.*]] = or i32 [[TMP2]], 40
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[X:%.*]], 128
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[TMP1]], 0
+; CHECK-NEXT:    [[TMP3:%.*]] = select i1 [[TMP2]], i32 40, i32 42
 ; CHECK-NEXT:    ret i32 [[TMP3]]
 ;
   %1 = and i32 %x, 128
   %2 = icmp eq i32 %1, 0
   %3 = select i1 %2, i32 40, i32 42
   ret i32 %3
 }
 
 define <2 x i32> @test72vec(<2 x i32> %x) {
 ; CHECK-LABEL: @test72vec(
-; CHECK-NEXT:    [[TMP1:%.*]] = lshr <2 x i32> [[X:%.*]], <i32 6, i32 6>
-; CHECK-NEXT:    [[TMP2:%.*]] = and <2 x i32> [[TMP1]], <i32 2, i32 2>
-; CHECK-NEXT:    [[TMP3:%.*]] = or <2 x i32> [[TMP2]], <i32 40, i32 40>
+; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i32> [[X:%.*]], <i32 128, i32 128>
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq <2 x i32> [[TMP1]], zeroinitializer
+; CHECK-NEXT:    [[TMP3:%.*]] = select <2 x i1> [[TMP2]], <2 x i32> <i32 40, i32 40>, <2 x i32> <i32 42, i32 42>
 ; CHECK-NEXT:    ret <2 x i32> [[TMP3]]
 ;
   %1 = and <2 x i32> %x, <i32 128, i32 128>
   %2 = icmp eq <2 x i32> %1, <i32 0, i32 0>
   %3 = select <2 x i1> %2, <2 x i32> <i32 40, i32 40>, <2 x i32> <i32 42, i32 42>
   ret <2 x i32> %3
 }
 
 define i32 @test73(i32 %x) {
 ; CHECK-LABEL: @test73(
-; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[X:%.*]], 6
-; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], 2
-; CHECK-NEXT:    [[TMP3:%.*]] = or i32 [[TMP2]], 40
+; CHECK-NEXT:    [[TMP1:%.*]] = trunc i32 [[X:%.*]] to i8
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp sgt i8 [[TMP1]], -1
+; CHECK-NEXT:    [[TMP3:%.*]] = select i1 [[TMP2]], i32 40, i32 42
 ; CHECK-NEXT:    ret i32 [[TMP3]]
 ;
   %1 = trunc i32 %x to i8
   %2 = icmp sgt i8 %1, -1
   %3 = select i1 %2, i32 40, i32 42
   ret i32 %3
 }
 
 define <2 x i32> @test73vec(<2 x i32> %x) {
 ; CHECK-LABEL: @test73vec(
-; CHECK-NEXT:    [[TMP1:%.*]] = lshr <2 x i32> [[X:%.*]], <i32 6, i32 6>
-; CHECK-NEXT:    [[TMP2:%.*]] = and <2 x i32> [[TMP1]], <i32 2, i32 2>
-; CHECK-NEXT:    [[TMP3:%.*]] = or <2 x i32> [[TMP2]], <i32 40, i32 40>
+; CHECK-NEXT:    [[TMP1:%.*]] = trunc <2 x i32> [[X:%.*]] to <2 x i8>
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp sgt <2 x i8> [[TMP1]], <i8 -1, i8 -1>
+; CHECK-NEXT:    [[TMP3:%.*]] = select <2 x i1> [[TMP2]], <2 x i32> <i32 40, i32 40>, <2 x i32> <i32 42, i32 42>
 ; CHECK-NEXT:    ret <2 x i32> [[TMP3]]
 ;
   %1 = trunc <2 x i32> %x to <2 x i8>
   %2 = icmp sgt <2 x i8> %1, <i8 -1, i8 -1>
   %3 = select <2 x i1> %2, <2 x i32> <i32 40, i32 40>, <2 x i32> <i32 42, i32 42>
   ret <2 x i32> %3
 }
 
 define i32 @test74(i32 %x) {
 ; CHECK-LABEL: @test74(
-; CHECK-NEXT:    [[TMP1:%.*]] = ashr i32 [[X:%.*]], 31
-; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], 2
-; CHECK-NEXT:    [[TMP3:%.*]] = or i32 [[TMP2]], 40
-; CHECK-NEXT:    ret i32 [[TMP3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp sgt i32 [[X:%.*]], -1
+; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[TMP1]], i32 40, i32 42
+; CHECK-NEXT:    ret i32 [[TMP2]]
 ;
   %1 = icmp sgt i32 %x, -1
   %2 = select i1 %1, i32 40, i32 42
   ret i32 %2
 }
 
 define <2 x i32> @test74vec(<2 x i32> %x) {
 ; CHECK-LABEL: @test74vec(
-; CHECK-NEXT:    [[TMP1:%.*]] = ashr <2 x i32> [[X:%.*]], <i32 31, i32 31>
-; CHECK-NEXT:    [[TMP2:%.*]] = and <2 x i32> [[TMP1]], <i32 2, i32 2>
-; CHECK-NEXT:    [[TMP3:%.*]] = or <2 x i32> [[TMP2]], <i32 40, i32 40>
-; CHECK-NEXT:    ret <2 x i32> [[TMP3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp sgt <2 x i32> [[X:%.*]], <i32 -1, i32 -1>
+; CHECK-NEXT:    [[TMP2:%.*]] = select <2 x i1> [[TMP1]], <2 x i32> <i32 40, i32 40>, <2 x i32> <i32 42, i32 42>
+; CHECK-NEXT:    ret <2 x i32> [[TMP2]]
 ;
   %1 = icmp sgt <2 x i32> %x, <i32 -1, i32 -1>
   %2 = select <2 x i1> %1, <2 x i32> <i32 40, i32 40>, <2 x i32> <i32 42, i32 42>
   ret <2 x i32> %2
 }
 
 ;; Code sequence for (X & 16) ? 16 : 0
 define i32 @test15a(i32 %X) {
;
   %t2 = icmp ne i32 %t1, 0
   %t3 = select i1 %t2, i32 -1, i32 -9
   ret i32 %t3
 }
 
 ;; (a & 8) ? -9 : -1
 define i32 @test15h(i32 %X) {
 ; CHECK-LABEL: @test15h(
-; CHECK-NEXT:    [[TMP1:%.*]] = or i32 [[X:%.*]], -9
-; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[TMP1]], 8
-; CHECK-NEXT:    ret i32 [[TMP2]]
+; CHECK-NEXT:    [[T1:%.*]] = and i32 [[X:%.*]], 8
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[T1]], -1
+; CHECK-NEXT:    ret i32 [[TMP1]]
 ;
   %t1 = and i32 %X, 8
   %t2 = icmp ne i32 %t1, 0
   %t3 = select i1 %t2, i32 -9, i32 -1
   ret i32 %t3
 }
 
 ;; (a & 2) ? 577 : 1089
 define i32 @test15i(i32 %X) {
 ; CHECK-LABEL: @test15i(
-; CHECK-NEXT:    [[T1:%.*]] = shl i32 [[X:%.*]], 8
-; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[T1]], 512
-; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[TMP1]], 512
-; CHECK-NEXT:    [[TMP3:%.*]] = add nuw nsw i32 [[TMP2]], 577
-; CHECK-NEXT:    ret i32 [[TMP3]]
+; CHECK-NEXT:    [[T1:%.*]] = and i32 [[X:%.*]], 2
+; CHECK-NEXT:    [[T2:%.*]] = icmp eq i32 [[T1]], 0
+; CHECK-NEXT:    [[T3:%.*]] = select i1 [[T2]], i32 1089, i32 577
+; CHECK-NEXT:    ret i32 [[T3]]
 ;
   %t1 = and i32 %X, 2
   %t2 = icmp ne i32 %t1, 0
   %t3 = select i1 %t2, i32 577, i32 1089
   ret i32 %t3
 }
 
 ;; (a & 2) ? 1089 : 577
 define i32 @test15j(i32 %X) {
 ; CHECK-LABEL: @test15j(
-; CHECK-NEXT:    [[T1:%.*]] = shl i32 [[X:%.*]], 8
-; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[T1]], 512
-; CHECK-NEXT:    [[TMP2:%.*]] = add nuw nsw i32 [[TMP1]], 577
-; CHECK-NEXT:    ret i32 [[TMP2]]
+; CHECK-NEXT:    [[T1:%.*]] = and i32 [[X:%.*]], 2
+; CHECK-NEXT:    [[T2:%.*]] = icmp eq i32 [[T1]], 0
+; CHECK-NEXT:    [[T3:%.*]] = select i1 [[T2]], i32 577, i32 1089
+; CHECK-NEXT:    ret i32 [[T3]]
 ;
   %t1 = and i32 %X, 2
   %t2 = icmp ne i32 %t1, 0
   %t3 = select i1 %t2, i32 1089, i32 577
   ret i32 %t3
 }
 
 declare void @use1(i1)
;
   ret i32 %t3
 }
 
 ; (X & 128) == 0 ? 131 : 3 --> (X & 128) ^ 131
 
 define i8 @clear_to_set_decomposebittest(i8 %x) {
 ; CHECK-LABEL: @clear_to_set_decomposebittest(
 ; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[X:%.*]], -128
-; CHECK-NEXT:    [[TMP2:%.*]] = add i8 [[TMP1]], -125
+; CHECK-NEXT:    [[TMP2:%.*]] = xor i8 [[TMP1]], -125
 ; CHECK-NEXT:    ret i8 [[TMP2]]
 ;
   %t2 = icmp sgt i8 %x, -1
   %t3 = select i1 %t2, i8 131, i8 3
   ret i8 %t3
 }
 
 ; (X & 128) == 0 ? 3 : 131 --> (X & 128) | 3
;
   ret i8 %t3
 }
 
 ; (X & 128) != 0 ? 3 : 131 --> (X & 128) ^ 131
 
 define i8 @set_to_clear_decomposebittest(i8 %x) {
 ; CHECK-LABEL: @set_to_clear_decomposebittest(
 ; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[X:%.*]], -128
-; CHECK-NEXT:    [[TMP2:%.*]] = add i8 [[TMP1]], -125
+; CHECK-NEXT:    [[TMP2:%.*]] = xor i8 [[TMP1]], -125
 ; CHECK-NEXT:    ret i8 [[TMP2]]
 ;
   %t2 = icmp slt i8 %x, 0
   %t3 = select i1 %t2, i8 3, i8 131
   ret i8 %t3
 }
 
 ; (X & 128) == 0 ? 131 : 3 --> (X & 128) ^ 131
 ; Extra cmp use to verify that we are not creating extra instructions.
 
 define i8 @clear_to_set_decomposebittest_extra_use(i8 %x) {
 ; CHECK-LABEL: @clear_to_set_decomposebittest_extra_use(
 ; CHECK-NEXT:    [[T2:%.*]] = icmp sgt i8 [[X:%.*]], -1
-; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[X]], -128
-; CHECK-NEXT:    [[TMP2:%.*]] = add i8 [[TMP1]], -125
+; CHECK-NEXT:    [[T3:%.*]] = select i1 [[T2]], i8 -125, i8 3
 ; CHECK-NEXT:    call void @use1(i1 [[T2]])
-; CHECK-NEXT:    ret i8 [[TMP2]]
+; CHECK-NEXT:    ret i8 [[T3]]
 ;
   %t2 = icmp sgt i8 %x, -1
   %t3 = select i1 %t2, i8 131, i8 3
   call void @use1(i1 %t2)
   ret i8 %t3
 }
 
 ; (X & 128) == 0 ? 3 : 131 --> (X & 128) | 3
 ; Extra cmp use to verify that we are not creating extra instructions.
 
 define i8 @clear_to_clear_decomposebittest_extra_use(i8 %x) {
 ; CHECK-LABEL: @clear_to_clear_decomposebittest_extra_use(
 ; CHECK-NEXT:    [[T2:%.*]] = icmp sgt i8 [[X:%.*]], -1
-; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[X]], -128
-; CHECK-NEXT:    [[TMP2:%.*]] = or i8 [[TMP1]], 3
+; CHECK-NEXT:    [[T3:%.*]] = select i1 [[T2]], i8 3, i8 -125
 ; CHECK-NEXT:    call void @use1(i1 [[T2]])
-; CHECK-NEXT:    ret i8 [[TMP2]]
+; CHECK-NEXT:    ret i8 [[T3]]
 ;
   %t2 = icmp sgt i8 %x, -1
   %t3 = select i1 %t2, i8 3, i8 131
   call void @use1(i1 %t2)
   ret i8 %t3
 }
 
 ; (X & 128) != 0 ? 131 : 3 --> (X & 128) | 3
 ; Extra cmp use to verify that we are not creating extra instructions.
 
 define i8 @set_to_set_decomposebittest_extra_use(i8 %x) {
 ; CHECK-LABEL: @set_to_set_decomposebittest_extra_use(
 ; CHECK-NEXT:    [[T2:%.*]] = icmp slt i8 [[X:%.*]], 0
-; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[X]], -128
-; CHECK-NEXT:    [[TMP2:%.*]] = or i8 [[TMP1]], 3
+; CHECK-NEXT:    [[T3:%.*]] = select i1 [[T2]], i8 -125, i8 3
 ; CHECK-NEXT:    call void @use1(i1 [[T2]])
-; CHECK-NEXT:    ret i8 [[TMP2]]
+; CHECK-NEXT:    ret i8 [[T3]]
 ;
   %t2 = icmp slt i8 %x, 0
   %t3 = select i1 %t2, i8 131, i8 3
   call void @use1(i1 %t2)
   ret i8 %t3
 }
 
 ; (X & 128) != 0 ? 3 : 131 --> (X & 128) ^ 131
 ; Extra cmp use to verify that we are not creating extra instructions.
 
 define i8 @set_to_clear_decomposebittest_extra_use(i8 %x) {
 ; CHECK-LABEL: @set_to_clear_decomposebittest_extra_use(
 ; CHECK-NEXT:    [[T2:%.*]] = icmp slt i8 [[X:%.*]], 0
-; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[X]], -128
-; CHECK-NEXT:    [[TMP2:%.*]] = add i8 [[TMP1]], -125
+; CHECK-NEXT:    [[T3:%.*]] = select i1 [[T2]], i8 3, i8 -125
 ; CHECK-NEXT:    call void @use1(i1 [[T2]])
-; CHECK-NEXT:    ret i8 [[TMP2]]
+; CHECK-NEXT:    ret i8 [[T3]]
 ;
   %t2 = icmp slt i8 %x, 0
   %t3 = select i1 %t2, i8 3, i8 131
   call void @use1(i1 %t2)
   ret i8 %t3
 }