[InstCombine] Canonizing 'and' before 'shl'

[opaparo]

Summary

Following a debate that aroused here, a new canonical form to a masked shl is introduced. The canonical form will now be:

define i8 @andshl(i8 %x) {
  %and = and i8 %x, 1
  %shl = shl nuw nsw i8 %and, 3
  ret i8 %shl
}

instead of:

define i8 @andshl(i8 %x) {
  %and = shl i8 %x, 3
  %shl = and i8 %and, 8
  ret i8 %shl
}

Which will result, first and foremost, in smaller constants used by the 'and' instructions.

Some complementary changes are also introduced:

1. InstCombiner::MatchBSwap (under lib/Transforms/InstCombine/InstCombineAndOrXor.cpp) was changed to recognize both the old and new patterns (tests will fail if only one the new pattern is recognized).
2. New features and fine tuning were introduced to InstructionSimplify in order to continue supporting existing test cases as well as enhancing other similar test cases. Those are specified in test/Transforms/InstCombine/select-bitext-bitwise-ops.ll

[craig.topper]

test/Transforms/InstCombine/2010-11-01-lshr-mask.ll

7

This looks like a regression.

test/Transforms/InstCombine/cast.ll

814

Any idea why were weren't simplifying this before this change?

[spatel]

At least the bswap part of this (and probably handling the regression that @craig.topper pointed out) should be split into independent patches. I don't know what the InstSimplify part is doing yet, but that seems like it should be an independent patch too.

You can see the bswap limitation with a small test like this:

declare void @extra_use(i32)
  
define i32 @test7_and_first(i32 %x) {
  %shl = shl i32 %x, 16
  %shr = lshr i32 %x, 16
  %or = or i32 %shl, %shr
  %t1 = and i32 %or, 16711935
  %shl3 = shl nuw i32 %t1, 8
  %and4 = lshr i32 %or, 8
  %shr5 = and i32 %and4, 16711935
  %or6 = or i32 %shl3, %shr5
  ret i32 %or6
}

define i32 @test7_and_first_extra_use(i32 %x) {
  %shl = shl i32 %x, 16
  %shr = lshr i32 %x, 16
  %or = or i32 %shl, %shr
  %t1 = and i32 %or, 16711935
  %shl3 = shl nuw i32 %t1, 8
  %and4 = lshr i32 %or, 8
  %shr5 = and i32 %and4, 16711935
  %or6 = or i32 %shl3, %shr5
  call void @extra_use(i32 %t1)
  ret i32 %or6
}


define i32 @test7_shl_first(i32 %x) {
  %shl = shl i32 %x, 16
  %shr = lshr i32 %x, 16
  %or = or i32 %shl, %shr
  %and2 = shl i32 %or, 8
  %shl3 = and i32 %and2, -16711936
  %and4 = lshr i32 %or, 8
  %shr5 = and i32 %and4, 16711935
  %or6 = or i32 %shl3, %shr5
  ret i32 %or6
}

$ ./opt -instcombine -S bswap.ll 

declare void @extra_use(i32)

define i32 @test7_and_first(i32 %x) {
  %or6 = call i32 @llvm.bswap.i32(i32 %x)
  ret i32 %or6
}

define i32 @test7_and_first_extra_use(i32 %x) {
  %shl = shl i32 %x, 16
  %shr = lshr i32 %x, 16
  %or = or i32 %shl, %shr
  %t1 = and i32 %or, 16711935
  %shl3 = shl nuw i32 %t1, 8
  %and4 = lshr i32 %or, 8
  %shr5 = and i32 %and4, 16711935
  %or6 = or i32 %shl3, %shr5
  call void @extra_use(i32 %t1)
  ret i32 %or6
}

define i32 @test7_shl_first(i32 %x) {
  %or6 = call i32 @llvm.bswap.i32(i32 %x)
  ret i32 %or6
}

[opaparo]

1. Relaxing the canonization condition: the masked shl will be canonized to the new form only if the 'shl''s 0th operand is not a shift instruction. This is due to other, better optimization that will be able to kick in.
2. Reverted the InstructionSimplify and bswap changes. Those will be added in two different reviews.

[opaparo]

test/Transforms/InstCombine/cast.ll

814

I've looked into it.
The key here is the first three instructions. Consider the old version:

%C = zext i8 %A to i32
%D = shl i32 %C, 4
%E = and i32 %D, 48

vs the new version:

%C = zext i8 %A to i32
%E = and i32 %C, 3
%D = shl i32 %E, 4

In the old version, 'shl' of 'zext' could not be transformed into 'zext' of 'shl' as in the general case they are not identical due to bits 8 and above of the result of the 'shl' that will be zeroed out. On the other hand, in the new version 'and' of 'zext' could be transformed to 'zext' of 'and'. Afterwards, since bits 8 and above of the 'shl' result are promised to be zeroes, 'shl' of 'zext' can now be transformed into 'zext' of 'shl'. This caused a chain reaction in which the 'zext' kept "sinking" down, eventually merging with the other 'zext'.
Note that, in the new version, if the RHS operand of the 'and' was greater or equal to 16 this transformation would again not be possible as there would again be a chance of losing bits. 'and' of 'zext' will still be transformed into 'zext' of 'and', but it will stop there.

[opaparo]

Ping

[craig.topper]

I know smaller constants is meaningful to X86. But do other targets have different immediate sizes for And instructions. ARM encodes immediates with a shift amount applied to them I think? Not sure about others.

lib/Transforms/InstCombine/InstCombineShifts.cpp

552

This transform is very similar to the one above, but the binop here is conditional. Should we be avoid pulling shifts above a conditional and?

[spatel]

In D41233#977634, @craig.topper wrote:

I know smaller constants is meaningful to X86. But do other targets have different immediate sizes for And instructions. ARM encodes immediates with a shift amount applied to them I think? Not sure about others.

This might be a stretch, but we could argue that smaller constants also increase the likelihood of CSE (smaller range means more potential equivalences?).

D48278 is an ARM-motivated patch that looks like it would benefit from this change.

I can't tell where we left off on this patch. Did we eliminate all of the roadblocks?

lib/Analysis/InstructionSimplify.cpp

static Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
   return nullptr;
 }
 
 Value *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
                               FastMathFlags FMF, const SimplifyQuery &Q) {
   return ::SimplifyFCmpInst(Predicate, LHS, RHS, FMF, Q, RecursionLimit);
 }
 
+static bool
+IsSafeOverflowingBinaryOperator(const OverflowingBinaryOperator *OBO,
+                                const SimplifyQuery &Q) {
+  const Instruction *I = dyn_cast_or_null<Instruction>(OBO);
+  if (!I)
+    return false;
+  if (I->getOpcode() != Instruction::Shl)
+    // TODO: Perhaps we can handle other instructions too
+    return false;
+
+  Value *Op0 = I->getOperand(0), *Op1 = I->getOperand(1);
+
+  const APInt *ShAmtAPInt;
+  if (!match(Op1, m_APInt(ShAmtAPInt)))
+    return false;
+
+  unsigned ShAmt = ShAmtAPInt->getZExtValue();
+  unsigned BitWidth = I->getType()->getScalarSizeInBits();
+
+  if (I->hasNoSignedWrap() &&
+      !MaskedValueIsZero(Op0, APInt::getHighBitsSet(BitWidth, ShAmt), Q.DL, 0,
+                         Q.AC, I, Q.DT))
+    return false;
+
+  if (I->hasNoSignedWrap() &&
+      ComputeNumSignBits(Op0, Q.DL, 0, Q.AC, I, Q.DT) <= ShAmt)
+    return false;
+
+  return true;
+}
+
+static bool IsSafePossiblyExactOperator(const PossiblyExactOperator *PEO,
+                                        const SimplifyQuery &Q) {
+  const Instruction *I = dyn_cast_or_null<Instruction>(PEO);
+  if (!I)
+    return false;
+  if (I->getOpcode() != Instruction::LShr &&
+      I->getOpcode() != Instruction::AShr)
+    // TODO: Perhaps we can handle other instructions too
+    return false;
+
+  Value *Op0 = I->getOperand(0), *Op1 = I->getOperand(1);
+
+  const APInt *ShAmtAPInt;
+  if (!match(Op1, m_APInt(ShAmtAPInt)))
+    return false;
+
+  unsigned ShAmt = ShAmtAPInt->getZExtValue();
+  unsigned BitWidth = I->getType()->getScalarSizeInBits();
+
+  if (I->isExact() &&
+      !MaskedValueIsZero(Op0, APInt::getLowBitsSet(BitWidth, ShAmt), Q.DL, 0,
+                         Q.AC, I, Q.DT))
+    return false;
+
+  return true;
+}
+
 /// See if V simplifies when its operand Op is replaced with RepOp.
 static const Value *SimplifyWithOpReplaced(Value *V, Value *Op, Value *RepOp,
                                            const SimplifyQuery &Q,
                                            unsigned MaxRecurse) {
   // Trivial replacement.
   if (V == Op)
     return RepOp;
 
   // We cannot replace a constant, and shouldn't even try.
   if (isa<Constant>(Op))
     return nullptr;
 
   auto *I = dyn_cast<Instruction>(V);
   if (!I)
     return nullptr;
 
   // If this is a binary operator, try to simplify it with the replaced op.
   if (auto *B = dyn_cast<BinaryOperator>(I)) {
     // Consider:
     //   %cmp = icmp eq i32 %x, 2147483647
     //   %add = add nsw i32 %x, 1
     //   %sel = select i1 %cmp, i32 -2147483648, i32 %add
     //
     // We can't replace %sel with %add unless we strip away the flags.
-    if (isa<OverflowingBinaryOperator>(B))
-      if (B->hasNoSignedWrap() || B->hasNoUnsignedWrap())
+    if (OverflowingBinaryOperator *OBO = dyn_cast<OverflowingBinaryOperator>(B))
+      if (!IsSafeOverflowingBinaryOperator(OBO, Q))
         return nullptr;
-    if (isa<PossiblyExactOperator>(B))
-      if (B->isExact())
+    if (PossiblyExactOperator *PEO = dyn_cast<PossiblyExactOperator>(B))
+      if (!IsSafePossiblyExactOperator(PEO, Q))
         return nullptr;
 
     if (MaxRecurse) {
       if (B->getOperand(0) == Op)
         return SimplifyBinOp(B->getOpcode(), RepOp, B->getOperand(1), Q,
                              MaxRecurse - 1);
       if (B->getOperand(1) == Op)
         return SimplifyBinOp(B->getOpcode(), B->getOperand(0), RepOp, Q,
                              MaxRecurse - 1);
     }
   }
 
   // Same for CmpInsts.
   if (CmpInst *C = dyn_cast<CmpInst>(I)) {
     if (MaxRecurse) {
       if (C->getOperand(0) == Op)
         return SimplifyCmpInst(C->getPredicate(), RepOp, C->getOperand(1), Q,
                                MaxRecurse - 1);
       if (C->getOperand(1) == Op)
         return SimplifyCmpInst(C->getPredicate(), C->getOperand(0), RepOp, Q,
                                MaxRecurse - 1);
     }
   }
 
+  if (CastInst *C = dyn_cast<CastInst>(I)) {
+    if (MaxRecurse) {
+      const Value *CastInstWithReplacement = SimplifyWithOpReplaced(
+          I->getOperand(0), Op, RepOp, Q, MaxRecurse - 1);
+      if (const Constant *Const =
+              dyn_cast_or_null<Constant>(CastInstWithReplacement))
+        return ConstantExpr::getCast(
+            C->getOpcode(), const_cast<Constant *>(Const), C->getType());
+    }
+  }
+
   // TODO: We could hand off more cases to instsimplify here.
 
   // If all operands are constant after substituting Op for RepOp then we can
   // constant fold the instruction.
   if (Constant *CRepOp = dyn_cast<Constant>(RepOp)) {
     // Build a list of all constant operands.
     SmallVector<Constant *, 8> ConstOps;
     for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

if (match(Op0, m_OneUse(m_Or(m_Value(X), m_APInt(OrC))))) {
       // above, but this feels safer.
       APInt Together = *C & *OrC;
       Value *And = Builder.CreateAnd(X, ConstantInt::get(I.getType(),
                                                          Together ^ *C));
       And->takeName(Op0);
       return BinaryOperator::CreateOr(And, ConstantInt::get(I.getType(),
                                                             Together));
     }
+    const APInt *ShlC;
+    if (match(Op0, m_OneUse(m_Shl(m_Value(X), m_APInt(ShlC))))) {
+      Constant *NewMask = ConstantInt::get(I.getType(), C->lshr(*ShlC));
+      Value *NewAnd = Builder.CreateAnd(X, NewMask);
+      return BinaryOperator::CreateShl(NewAnd, ConstantInt::get(I.getType(),
+                                                                *ShlC));
+    }
 
     // If the mask is only needed on one incoming arm, push the 'and' op up.
     if (match(Op0, m_OneUse(m_Xor(m_Value(X), m_Value(Y)))) ||
         match(Op0, m_OneUse(m_Or(m_Value(X), m_Value(Y))))) {
       APInt NotAndMask(~(*C));
       BinaryOperator::BinaryOps BinOp = cast<BinaryOperator>(Op0)->getOpcode();
       if (MaskedValueIsZero(X, NotAndMask, 0, &I)) {
         // Not masking anything out for the LHS, move mask to RHS.
Instruction *InstCombiner::MatchBSwap(BinaryOperator &I) {
   // (A | B) | C  and  A | (B | C)                  -> bswap if possible.
   bool OrOfOrs = match(Op0, m_Or(m_Value(), m_Value())) ||
                  match(Op1, m_Or(m_Value(), m_Value()));
 
   // (A >> B) | (C << D)  and  (A << B) | (B >> C)  -> bswap if possible.
   bool OrOfShifts = match(Op0, m_LogicalShift(m_Value(), m_Value())) &&
                     match(Op1, m_LogicalShift(m_Value(), m_Value()));
 
-  // (A & B) | (C & D)                              -> bswap if possible.
-  bool OrOfAnds = match(Op0, m_And(m_Value(), m_Value())) &&
-                  match(Op1, m_And(m_Value(), m_Value()));
+  // (A << B) | (C & D)                              -> bswap if possible.
+  bool OrOfShiftAndAnd = (match(Op0, m_And(m_Value(), m_Value())) &&
+                          match(Op1, m_LogicalShift(m_Value(), m_Value()))) ||
+                         (match(Op0, m_LogicalShift(m_Value(), m_Value())) &&
+                          match(Op1, m_And(m_Value(), m_Value())));
 
-  if (!OrOfOrs && !OrOfShifts && !OrOfAnds)
+  if (!OrOfOrs && !OrOfShifts && !OrOfShiftAndAnd)
     return nullptr;
 
   SmallVector<Instruction*, 4> Insts;
   if (!recognizeBSwapOrBitReverseIdiom(&I, true, false, Insts))
     return nullptr;
   Instruction *LastInst = Insts.pop_back_val();
   LastInst->removeFromParent();
 

lib/Transforms/InstCombine/InstCombineShifts.cpp

if (BinaryOperator *Op0BO = dyn_cast<BinaryOperator>(Op0)) {
         break;
       }
       }
 
 
       // If the operand is a bitwise operator with a constant RHS, and the
       // shift is the only use, we can pull it out of the shift.
       const APInt *Op0C;
-      if (match(Op0BO->getOperand(1), m_APInt(Op0C))) {
+      if (match(Op0BO->getOperand(1), m_APInt(Op0C)) &&
+          (!isLeftShift || Op0BO->getOpcode() != Instruction::And)) {
         if (canShiftBinOpWithConstantRHS(I, Op0BO, *Op0C)) {
           Constant *NewRHS = ConstantExpr::get(I.getOpcode(),
                                      cast<Constant>(Op0BO->getOperand(1)), Op1);
 
           Value *NewShift =
             Builder.CreateBinOp(I.getOpcode(), Op0BO->getOperand(0), Op1);
           NewShift->takeName(Op0BO);
 
if (Op0->hasOneUse()) {
     //   Y = shl X, C2
     //   select C, (add Y, C1 << C2), Y
     Value *Cond;
     BinaryOperator *TBO;
     Value *FalseVal;
     if (match(Op0, m_Select(m_Value(Cond), m_OneUse(m_BinOp(TBO)),
                             m_Value(FalseVal)))) {
       const APInt *C;
       if (!isa<Constant>(FalseVal) && TBO->getOperand(0) == FalseVal &&
           match(TBO->getOperand(1), m_APInt(C)) &&
           canShiftBinOpWithConstantRHS(I, TBO, *C)) {
         Constant *NewRHS = ConstantExpr::get(I.getOpcode(),
                                        cast<Constant>(TBO->getOperand(1)), Op1);
 
         Value *NewShift =
           Builder.CreateBinOp(I.getOpcode(), FalseVal, Op1);
         Value *NewOp = Builder.CreateBinOp(TBO->getOpcode(), NewShift,

test/Transforms/InstCombine/2010-11-01-lshr-mask.ll

 ; RUN: opt -instcombine -S < %s | FileCheck %s
 
 ; <rdar://problem/8606771>
 define i32 @main(i32 %argc) {
 ; CHECK-LABEL: @main(
 ; CHECK-NEXT:    [[TMP3151:%.*]] = trunc i32 %argc to i8
-; CHECK-NEXT:    [[TMP1:%.*]] = shl i8 [[TMP3151]], 5
-; CHECK-NEXT:    [[TMP4126:%.*]] = and i8 [[TMP1]], 64
+; CHECK-NEXT:    [[TMP1:%.*]] = lshr i8 [[TMP3151]], 1
+; CHECK-NEXT:    [[TMP4120:%.*]] = and i8 [[TMP1]], 1
+; CHECK-NEXT:    [[TMP4126:%.*]] = shl nuw nsw i8 [[TMP4120]], 6
 ; CHECK-NEXT:    [[TMP4127:%.*]] = xor i8 [[TMP4126]], 64
 ; CHECK-NEXT:    [[TMP4086:%.*]] = zext i8 [[TMP4127]] to i32
 ; CHECK-NEXT:    ret i32 [[TMP4086]]
 ;
   %tmp3151 = trunc i32 %argc to i8
   %tmp3161 = or i8 %tmp3151, -17
   %tmp3162 = and i8 %tmp3151, 122
   %tmp3163 = xor i8 %tmp3162, -17

test/Transforms/InstCombine/cast.ll

;
   %C = or i32 %B, %D
   %E = zext i32 %C to i64
   ret i64 %E
 }
 
 
 define i64 @test46(i64 %A) {
 ; CHECK-LABEL: @test46(
-; CHECK-NEXT:    [[C:%.*]] = shl i64 %A, 8
-; CHECK-NEXT:    [[D:%.*]] = and i64 [[C]], 10752
+; CHECK-NEXT:    [[C:%.*]] = and i64 %A, 42
+; CHECK-NEXT:    [[D:%.*]] = shl nuw nsw i64 [[C]], 8
 ; CHECK-NEXT:    ret i64 [[D]]
 ;
   %B = trunc i64 %A to i32
   %C = and i32 %B, 42
   %D = shl i32 %C, 8
   %E = zext i32 %D to i64
   ret i64 %E
 }
 
 define <2 x i64> @test46vec(<2 x i64> %A) {
 ; CHECK-LABEL: @test46vec(
-; CHECK-NEXT:    [[C:%.*]] = shl <2 x i64> [[A:%.*]], <i64 8, i64 8>
-; CHECK-NEXT:    [[D:%.*]] = and <2 x i64> [[C]], <i64 10752, i64 10752>
+; CHECK-NEXT:    [[C:%.*]] = and <2 x i64> %A, <i64 42, i64 42>
+; CHECK-NEXT:    [[D:%.*]] = shl nuw nsw <2 x i64> [[C]], <i64 8, i64 8>
 ; CHECK-NEXT:    ret <2 x i64> [[D]]
 ;
   %B = trunc <2 x i64> %A to <2 x i32>
   %C = and <2 x i32> %B, <i32 42, i32 42>
   %D = shl <2 x i32> %C, <i32 8, i32 8>
   %E = zext <2 x i32> %D to <2 x i64>
   ret <2 x i64> %E
 }
;
   %D = or i32 %C, 128
   %E = zext i32 %D to i64
   ret i64 %E
 
 }
 
 define i64 @test59(i8 %A, i8 %B) nounwind {
 ; CHECK-LABEL: @test59(
-; CHECK-NEXT:    [[C:%.*]] = zext i8 %A to i64
-; CHECK-NEXT:    [[D:%.*]] = shl nuw nsw i64 [[C]], 4
-; CHECK-NEXT:    [[E:%.*]] = and i64 [[D]], 48
-; CHECK-NEXT:    [[TMP1:%.*]] = lshr i8 %B, 4
-; CHECK-NEXT:    [[G:%.*]] = zext i8 [[TMP1]] to i64
-; CHECK-NEXT:    [[H:%.*]] = or i64 [[E]], [[G]]
-; CHECK-NEXT:    ret i64 [[H]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i8 %A, 3
+; CHECK-NEXT:    [[TMP2:%.*]] = shl nuw nsw i8 [[TMP1]], 4
+; CHECK-NEXT:    [[TMP3:%.*]] = lshr i8 %B, 4
+; CHECK-NEXT:    [[H:%.*]] = or i8 [[TMP3]], [[TMP2]]
+; CHECK-NEXT:    [[I:%.*]] = zext i8 [[H]] to i64
+; CHECK-NEXT:    ret i64 [[I]]
 ;
   %C = zext i8 %A to i32
   %D = shl i32 %C, 4
   %E = and i32 %D, 48
   %F = zext i8 %B to i32
   %G = lshr i32 %F, 4
   %H = or i32 %G, %E
   %I = zext i32 %H to i64
;
   %pp = getelementptr i8, i8* %q, i64 %i
   %r = bitcast i8* %pp to double*
   %l = load double, double* %r
   ret double %l
 }
 
 define i64 @test82(i64 %A) nounwind {
 ; CHECK-LABEL: @test82(
-; CHECK-NEXT:    [[TMP1:%.*]] = shl i64 %A, 1
-; CHECK-NEXT:    [[E:%.*]] = and i64 [[TMP1]], 4294966784
+; CHECK-NEXT:    [[TMP1:%.*]] = and i64 %A, 2147483392
+; CHECK-NEXT:    [[E:%.*]] = shl nuw nsw i64 %1, 1
 ; CHECK-NEXT:    ret i64 [[E]]
 ;
   %B = trunc i64 %A to i32
   %C = lshr i32 %B, 8
   %D = shl i32 %C, 9
   %E = zext i32 %D to i64
   ret i64 %E
 }

test/Transforms/InstCombine/or-shifted-masks.ll

 ; RUN: opt -S -instcombine < %s | FileCheck %s
 
 define i32 @or_and_shifts1(i32 %x) {
 ; CHECK-LABEL: @or_and_shifts1(
-; CHECK-NEXT:    [[TMP1:%.*]] = shl i32 %x, 3
-; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], 8
-; CHECK-NEXT:    [[TMP3:%.*]] = shl i32 %x, 5
-; CHECK-NEXT:    [[TMP4:%.*]] = and i32 [[TMP3]], 32
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 %x, 1
+; CHECK-NEXT:    [[TMP2:%.*]] = shl nuw nsw i32 [[TMP1]], 3
+; CHECK-NEXT:    [[TMP3:%.*]] = and i32 %x, 1
+; CHECK-NEXT:    [[TMP4:%.*]] = shl nuw nsw i32 [[TMP3]], 5
 ; CHECK-NEXT:    [[TMP5:%.*]] = or i32 [[TMP2]], [[TMP4]]
 ; CHECK-NEXT:    ret i32 [[TMP5]]
 ;
   %1 = shl i32 %x, 3
   %2 = and i32 %1, 15
   %3 = shl i32 %x, 5
   %4 = and i32 %3, 60
   %5 = or i32 %2, %4
   ret i32 %5
 }
 
 define i32 @or_and_shifts2(i32 %x) {
 ; CHECK-LABEL: @or_and_shifts2(
-; CHECK-NEXT:    [[TMP1:%.*]] = shl i32 %x, 3
-; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], 896
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 %x, 112
+; CHECK-NEXT:    [[TMP2:%.*]] = shl nuw nsw i32 [[TMP1]], 3
 ; CHECK-NEXT:    [[TMP3:%.*]] = lshr i32 %x, 4
 ; CHECK-NEXT:    [[TMP4:%.*]] = and i32 [[TMP3]], 7
 ; CHECK-NEXT:    [[TMP5:%.*]] = or i32 [[TMP2]], [[TMP4]]
 ; CHECK-NEXT:    ret i32 [[TMP5]]
 ;
   %1 = shl i32 %x, 3
   %2 = and i32 %1, 896
   %3 = lshr i32 %x, 4
   %4 = and i32 %3, 7
   %5 = or i32 %2, %4
   ret i32 %5
 }
 
 define i32 @or_and_shift_shift_and(i32 %x) {
 ; CHECK-LABEL: @or_and_shift_shift_and(
-; CHECK-NEXT:    [[TMP1:%.*]] = shl i32 %x, 3
-; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], 56
-; CHECK-NEXT:    [[TMP3:%.*]] = shl i32 %x, 2
-; CHECK-NEXT:    [[TMP4:%.*]] = and i32 [[TMP3]], 28
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 %x, 7
+; CHECK-NEXT:    [[TMP2:%.*]] = shl nuw nsw i32 [[TMP1]], 3
+; CHECK-NEXT:    [[TMP3:%.*]] = and i32 %x, 7
+; CHECK-NEXT:    [[TMP4:%.*]] = shl nuw nsw i32 [[TMP3]], 2
 ; CHECK-NEXT:    [[TMP5:%.*]] = or i32 [[TMP2]], [[TMP4]]
 ; CHECK-NEXT:    ret i32 [[TMP5]]
 ;
   %1 = and i32 %x, 7
   %2 = shl i32 %1, 3
   %3 = shl i32 %x, 2
   %4 = and i32 %3, 28
   %5 = or i32 %2, %4
   ret i32 %5
 }
 
 define i32 @multiuse1(i32 %x) {
 ; CHECK-LABEL: @multiuse1(
-; CHECK-NEXT:    [[TMP1:%.*]] = shl i32 %x, 6
-; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], 384
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 %x, 6
+; CHECK-NEXT:    [[TMP2:%.*]] = shl nuw nsw i32 [[TMP1]], 6
 ; CHECK-NEXT:    [[TMP3:%.*]] = lshr i32 %x, 1
 ; CHECK-NEXT:    [[TMP4:%.*]] = and i32 [[TMP3]], 3
 ; CHECK-NEXT:    [[TMP5:%.*]] = or i32 [[TMP4]], [[TMP2]]
 ; CHECK-NEXT:    ret i32 [[TMP5]]
 ;
   %1 = and i32 %x, 2
   %2 = and i32 %x, 4
   %3 = shl nuw nsw i32 %1, 6
   %4 = lshr exact i32 %1, 1
   %5 = shl nuw nsw i32 %2, 6
   %6 = lshr exact i32 %2, 1
   %7 = or i32 %3, %5
   %8 = or i32 %4, %6
   %9 = or i32 %8, %7
   ret i32 %9
 }
 
 define i32 @multiuse2(i32 %x) {
 ; CHECK-LABEL: @multiuse2(
-; CHECK-NEXT:    [[TMP1:%.*]] = shl i32 %x, 1
-; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], 12
-; CHECK-NEXT:    [[TMP3:%.*]] = shl i32 %x, 8
-; CHECK-NEXT:    [[TMP4:%.*]] = and i32 [[TMP3]], 24576
-; CHECK-NEXT:    [[TMP5:%.*]] = shl i32 %x, 8
-; CHECK-NEXT:    [[TMP6:%.*]] = and i32 [[TMP5]], 7680
-; CHECK-NEXT:    [[TMP7:%.*]] = or i32 [[TMP4]], [[TMP6]]
-; CHECK-NEXT:    [[TMP8:%.*]] = shl i32 %x, 1
-; CHECK-NEXT:    [[TMP9:%.*]] = and i32 [[TMP8]], 240
-; CHECK-NEXT:    [[TMP10:%.*]] = or i32 [[TMP2]], [[TMP9]]
-; CHECK-NEXT:    [[TMP11:%.*]] = or i32 [[TMP7]], [[TMP10]]
-; CHECK-NEXT:    ret i32 [[TMP11]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 %x, 126
+; CHECK-NEXT:    [[TMP2:%.*]] = shl nuw nsw i32 [[TMP1]], 8
+; CHECK-NEXT:    [[TMP3:%.*]] = and i32 %x, 126
+; CHECK-NEXT:    [[TMP4:%.*]] = shl nuw nsw i32 [[TMP3]], 1
+; CHECK-NEXT:    [[TMP5:%.*]] = or i32 [[TMP2]], [[TMP4]]
+; CHECK-NEXT:    ret i32 [[TMP5]]
 ;
   %1 = and i32 %x, 6
   %2 = shl nuw nsw i32 %1, 8
   %3 = shl nuw nsw i32 %1, 1
   %4 = and i32 %x, 24
   %5 = shl nuw nsw i32 %4, 8
   %6 = shl nuw nsw i32 %4, 1
   %7 = and i32 %x, 96
   %8 = shl nuw nsw i32 %7, 8
   %9 = shl nuw nsw i32 %7, 1
   %10 = or i32 %2, %5
   %11 = or i32 %8, %10
   %12 = or i32 %9, %6
   %13 = or i32 %3, %12
   %14 = or i32 %11, %13
   ret i32 %14
 }
 
 define i32 @multiuse3(i32 %x) {
 ; CHECK-LABEL: @multiuse3(
-; CHECK-NEXT:    [[TMP1:%.*]] = and i32 %x, 96
-; CHECK-NEXT:    [[TMP2:%.*]] = shl nuw nsw i32 [[TMP1]], 6
-; CHECK-NEXT:    [[TMP3:%.*]] = lshr exact i32 [[TMP1]], 1
-; CHECK-NEXT:    [[TMP4:%.*]] = shl i32 %x, 6
-; CHECK-NEXT:    [[TMP5:%.*]] = and i32 [[TMP4]], 1920
-; CHECK-NEXT:    [[TMP6:%.*]] = or i32 [[TMP2]], [[TMP5]]
-; CHECK-NEXT:    [[TMP7:%.*]] = lshr i32 %x, 1
-; CHECK-NEXT:    [[TMP8:%.*]] = and i32 [[TMP7]], 15
-; CHECK-NEXT:    [[TMP9:%.*]] = or i32 [[TMP3]], [[TMP8]]
-; CHECK-NEXT:    [[TMP10:%.*]] = or i32 [[TMP9]], [[TMP6]]
-; CHECK-NEXT:    ret i32 [[TMP10]]
+; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 %x, 1
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], 48
+; CHECK-NEXT:    [[TMP3:%.*]] = and i32 %x, 126
+; CHECK-NEXT:    [[TMP4:%.*]] = shl nuw nsw i32 [[TMP3]], 6
+; CHECK-NEXT:    [[TMP5:%.*]] = lshr i32 %x, 1
+; CHECK-NEXT:    [[TMP6:%.*]] = and i32 [[TMP5]], 15
+; CHECK-NEXT:    [[TMP7:%.*]] = or i32 [[TMP2]], [[TMP6]]
+; CHECK-NEXT:    [[TMP8:%.*]] = or i32 [[TMP7]], [[TMP4]]
+; CHECK-NEXT:    ret i32 [[TMP8]]
 ;
   %1 = and i32 %x, 96
   %2 = shl nuw nsw i32 %1, 6
   %3 = lshr exact i32 %1, 1
   %4 = shl i32 %x, 6
   %5 = and i32 %4, 1920
   %6 = or i32 %2, %5
   %7 = lshr i32 %x, 1

 
 define i32 @multiuse5(i32 %x) local_unnamed_addr #0 {
 ; CHECK-LABEL: @multiuse5(
 ; CHECK-NEXT:    [[TMP1:%.*]] = shl i32 %x, 5
 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp sgt i32 %x, -1
 ; CHECK-NEXT:    br i1 [[TMP2]], label %if, label %else
 ; CHECK:         {{.*}}if:{{.*}}
 ; CHECK-NEXT:    [[TMP3:%.*]] = and i32 [[TMP1]], 21760
-; CHECK-NEXT:    [[TMP4:%.*]] = shl i32 %x, 5
-; CHECK-NEXT:    [[TMP5:%.*]] = and i32 [[TMP4]], 43520
+; CHECK-NEXT:    [[TMP4:%.*]] = and i32 %x, 1360
+; CHECK-NEXT:    [[TMP5:%.*]] = shl nuw nsw i32 [[TMP4]], 5
 ; CHECK-NEXT:    [[TMP6:%.*]] = or i32 [[TMP5]], [[TMP3]]
 ; CHECK-NEXT:    br label %end
 ; CHECK:         {{.*}}else:{{.*}}
 ; CHECK-NEXT:    [[TMP7:%.*]] = and i32 [[TMP1]], 5570560
-; CHECK-NEXT:    [[TMP8:%.*]] = shl i32 %x, 5
-; CHECK-NEXT:    [[TMP9:%.*]] = and i32 [[TMP8]], 11141120
+; CHECK-NEXT:    [[TMP8:%.*]] = and i32 %x, 348160
+; CHECK-NEXT:    [[TMP9:%.*]] = shl nuw nsw i32 [[TMP8]], 5
 ; CHECK-NEXT:    [[TMP10:%.*]] = or i32 [[TMP9]], [[TMP7]]
 ; CHECK-NEXT:    br label %end
 ; CHECK:         {{.*}}end{{.*}}
 ; CHECK-NEXT:    [[TMP11:%.*]] = phi i32 [ [[TMP6]], %if ], [ [[TMP10]], %else ]
 ; CHECK-NEXT:    ret i32 [[TMP11]]
 ;
   %1 = shl i32 %x, 5
   %2 = icmp sgt i32 %x, -1

test/Transforms/InstCombine/pr17827.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 ; With left shift, the comparison should not be modified.
 define i1 @test_shift_and_cmp_not_changed1(i8 %p) {
 ; CHECK-LABEL: @test_shift_and_cmp_not_changed1(
-; CHECK-NEXT:    [[SHLP:%.*]] = shl i8 %p, 5
-; CHECK-NEXT:    [[ANDP:%.*]] = and i8 [[SHLP]], -64
+; CHECK-NEXT:    [[TMP1:%.*]] = and i8 %p, 6
+; CHECK-NEXT:    [[ANDP:%.*]] = shl nuw i8 [[TMP1]], 5
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 [[ANDP]], 32
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %shlp = shl i8 %p, 5
   %andp = and i8 %shlp, -64
   %cmp = icmp slt i8 %andp, 32
   ret i1 %cmp
 }
;
   %cmp = icmp slt i8 %andp, 32
   ret i1 %cmp
 }
 
 ; This should simplify functionally to the left shift case.
 ; The extra input parameter should be optimized away.
 define i1 @test_shift_and_cmp_changed1(i8 %p, i8 %q) {
 ; CHECK-LABEL: @test_shift_and_cmp_changed1(
-; CHECK-NEXT:    [[ANDP:%.*]] = shl i8 %p, 5
-; CHECK-NEXT:    [[SHL:%.*]] = and i8 [[ANDP]], -64
+; CHECK-NEXT:    [[ANDP:%.*]] = and i8 %p, 6
+; CHECK-NEXT:    [[SHL:%.*]] = shl nuw i8 %andp, 5
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 [[SHL]], 32
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %andp = and i8 %p, 6
   %andq = and i8 %q, 8
   %or = or i8 %andq, %andp
   %shl = shl i8 %or, 5
   %ashr = ashr i8 %shl, 5
   %cmp = icmp slt i8 %ashr, 1
   ret i1 %cmp
 }
 
 define <2 x i1> @test_shift_and_cmp_changed1_vec(<2 x i8> %p, <2 x i8> %q) {
 ; CHECK-LABEL: @test_shift_and_cmp_changed1_vec(
-; CHECK-NEXT:    [[ANDP:%.*]] = shl <2 x i8> [[P:%.*]], <i8 5, i8 5>
-; CHECK-NEXT:    [[SHL:%.*]] = and <2 x i8> [[ANDP]], <i8 -64, i8 -64>
+; CHECK-NEXT:    [[ANDP:%.*]] = and <2 x i8> %p, <i8 6, i8 6>
+; CHECK-NEXT:    [[SHL:%.*]] = shl nuw <2 x i8> [[ANDP]], <i8 5, i8 5>
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt <2 x i8> [[SHL]], <i8 32, i8 32>
 ; CHECK-NEXT:    ret <2 x i1> [[CMP]]
 ;
   %andp = and <2 x i8> %p, <i8 6, i8 6>
   %andq = and <2 x i8> %q, <i8 8, i8 8>
   %or = or <2 x i8> %andq, %andp
   %shl = shl <2 x i8> %or, <i8 5, i8 5>
   %ashr = ashr <2 x i8> %shl, <i8 5, i8 5>
   %cmp = icmp slt <2 x i8> %ashr, <i8 1, i8 1>
   ret <2 x i1> %cmp
 }
 
 ; Unsigned compare allows a transformation to compare against 0.
 define i1 @test_shift_and_cmp_changed2(i8 %p) {
 ; CHECK-LABEL: @test_shift_and_cmp_changed2(
-; CHECK-NEXT:    [[ANDP:%.*]] = and i8 %p, 6
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[ANDP]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = and i8 %p, 6
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[TMP1]], 0
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %shlp = shl i8 %p, 5
   %andp = and i8 %shlp, -64
   %cmp = icmp ult i8 %andp, 32
   ret i1 %cmp
 }
 
 define <2 x i1> @test_shift_and_cmp_changed2_vec(<2 x i8> %p) {
 ; CHECK-LABEL: @test_shift_and_cmp_changed2_vec(
 ; CHECK-NEXT:    [[ANDP:%.*]] = and <2 x i8> %p, <i8 6, i8 6>
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq <2 x i8> [[ANDP]], zeroinitializer
 ; CHECK-NEXT:    ret <2 x i1> [[CMP]]
 ;
   %shlp = shl <2 x i8> %p, <i8 5, i8 5>
   %andp = and <2 x i8> %shlp, <i8 -64, i8 -64>
   %cmp = icmp ult <2 x i8> %andp, <i8 32, i8 32>
   ret <2 x i1> %cmp
 }
 
 ; nsw on the shift should not affect the comparison.
 define i1 @test_shift_and_cmp_changed3(i8 %p) {
 ; CHECK-LABEL: @test_shift_and_cmp_changed3(
-; CHECK-NEXT:    [[SHLP:%.*]] = shl nsw i8 %p, 5
-; CHECK-NEXT:    [[ANDP:%.*]] = and i8 [[SHLP]], -64
+; CHECK-NEXT:    [[TMP1:%.*]] = and i8 %p, 6
+; CHECK-NEXT:    [[ANDP:%.*]] = shl nuw i8 [[TMP1]], 5
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 [[ANDP]], 32
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %shlp = shl nsw i8 %p, 5
   %andp = and i8 %shlp, -64
   %cmp = icmp slt i8 %andp, 32
   ret i1 %cmp
 }

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:    [[TMP1:%.*]] = and i16 %x, 4
+; CHECK-NEXT:    [[TMP2:%.*]] = shl nuw nsw i16 [[TMP1]], 3
 ; 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]]
 ;
   %1 = and i16 %x, 4
   %2 = icmp ne i16 %1, 0
   %3 = select i1 %2, i32 32, i32 64

test/Transforms/InstCombine/select-bitext-bitwise-ops.ll

 ; RUN: opt -S -instcombine < %s | FileCheck %s
 
 define i64 @sel_false_val_is_a_masked_shl_of_true_val1(i32 %x, i64 %y) {
 ; CHECK-LABEL: @sel_false_val_is_a_masked_shl_of_true_val1(
-; CHECK-NEXT:    [[TMP1:%.*]] = and i32 %x, 15 
-; CHECK-NEXT:    [[TMP2:%.*]] = shl nuw nsw i32 [[TMP1]], 2
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 %x, 15
+; CHECK-NEXT:    [[TMP2:%.*]] = shl nuw nsw i32 %1, 2
 ; CHECK-NEXT:    [[TMP3:%.*]] = zext i32 [[TMP2]] to i64
-; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq i32 [[TMP1]], 0
-; CHECK-NEXT:    [[TMP5:%.*]] = select i1 [[TMP4]], i64 0, i64 [[TMP3]]
-; CHECK-NEXT:    [[TMP6:%.*]] = ashr i64 %y, [[TMP5]]
-; CHECK-NEXT:    ret i64 [[TMP6]]
+; CHECK-NEXT:    [[TMP4:%.*]] = ashr i64 %y, [[TMP3]]
+; CHECK-NEXT:    ret i64 [[TMP4]]
 ;
   %1 = and i32 %x, 15
   %2 = shl nuw nsw i32 %1, 2
   %3 = zext i32 %2 to i64
   %4 = icmp eq i32 %1, 0
   %5 = ashr i64 %y, %3
   %6 = select i1 %4, i64 %y, i64 %5
   ret i64 %6
 }
 
 define i64 @sel_false_val_is_a_masked_shl_of_true_val2(i32 %x, i64 %y) {
 ; CHECK-LABEL: @sel_false_val_is_a_masked_shl_of_true_val2(
-; CHECK-NEXT:    [[TMP1:%.*]] = shl i32 %x, 2
-; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], 60
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 %x, 15
+; CHECK-NEXT:    [[TMP2:%.*]] = shl nuw nsw i32 [[TMP1]], 2
 ; CHECK-NEXT:    [[TMP3:%.*]] = zext i32 [[TMP2]] to i64
 ; CHECK-NEXT:    [[TMP4:%.*]] = ashr i64 %y, [[TMP3]]
 ; CHECK-NEXT:    ret i64 [[TMP4]]
 ;
   %1 = and i32 %x, 15
   %2 = shl nuw nsw i32 %1, 2
   %3 = zext i32 %2 to i64
   %4 = icmp eq i32 %2, 0
   %5 = ashr i64 %y, %3
   %6 = select i1 %4, i64 %y, i64 %5
   ret i64 %6
 }
 
 define i64 @sel_false_val_is_a_masked_lshr_of_true_val1(i32 %x, i64 %y) {
 ; CHECK-LABEL: @sel_false_val_is_a_masked_lshr_of_true_val1(
-; CHECK-NEXT:    [[TMP1:%.*]] = and i32 %x, 60
-; CHECK-NEXT:    [[TMP2:%.*]] = lshr exact i32 [[TMP1]], 2
+; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 %x, 2
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], 15
 ; CHECK-NEXT:    [[TMP3:%.*]] = zext i32 [[TMP2]] to i64
-; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq i32 [[TMP1]], 0
-; CHECK-NEXT:    [[TMP5:%.*]] = select i1 [[TMP4]], i64 0, i64 [[TMP3]]
-; CHECK-NEXT:    [[TMP6:%.*]] = ashr i64 %y, [[TMP5]]
-; CHECK-NEXT:    ret i64 [[TMP6]]
+; CHECK-NEXT:    [[TMP4:%.*]] = ashr i64 %y, [[TMP3]]
+; CHECK-NEXT:    ret i64 [[TMP4]]
 ;
   %1 = and i32 %x, 60
   %2 = lshr i32 %1, 2
   %3 = zext i32 %2 to i64
   %4 = icmp eq i32 %1, 0
   %5 = ashr i64 %y, %3
   %6 = select i1 %4, i64 %y, i64 %5
   ret i64 %6
;
   %4 = icmp eq i32 %2, 0
   %5 = ashr i64 %y, %3
   %6 = select i1 %4, i64 %y, i64 %5
   ret i64 %6
 }
 
 define i64 @sel_false_val_is_a_masked_ashr_of_true_val1(i32 %x, i64 %y) {
 ; CHECK-LABEL: @sel_false_val_is_a_masked_ashr_of_true_val1(
-; CHECK-NEXT:    [[TMP1:%.*]] = and i32 %x, -2147483588
-; CHECK-NEXT:    [[TMP2:%.*]] = ashr exact i32 [[TMP1]], 2
+; CHECK-NEXT:    [[TMP1:%.*]] = ashr i32 %x, 2
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], -536870897
 ; CHECK-NEXT:    [[TMP3:%.*]] = zext i32 [[TMP2]] to i64
-; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq i32 [[TMP1]], 0
-; CHECK-NEXT:    [[TMP5:%.*]] = select i1 [[TMP4]], i64 0, i64 [[TMP3]]
-; CHECK-NEXT:    [[TMP6:%.*]] = ashr i64 %y, [[TMP5]]
-; CHECK-NEXT:    ret i64 [[TMP6]]
+; CHECK-NEXT:    [[TMP4:%.*]] = ashr i64 %y, [[TMP3]]
+; CHECK-NEXT:    ret i64 [[TMP4]]
 ;
   %1 = and i32 %x, -2147483588
   %2 = ashr i32 %1, 2
   %3 = zext i32 %2 to i64
   %4 = icmp eq i32 %1, 0
   %5 = ashr i64 %y, %3
   %6 = select i1 %4, i64 %y, i64 %5
   ret i64 %6

test/Transforms/InstCombine/select-with-bitwise-ops.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 target datalayout = "n8:16:32:64"
 
 define i32 @select_icmp_eq_and_1_0_or_2(i32 %x, i32 %y) {
 ; CHECK-LABEL: @select_icmp_eq_and_1_0_or_2(
-; CHECK-NEXT:    [[AND:%.*]] = shl i32 %x, 1
-; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[AND]], 2
+; CHECK-NEXT:    [[AND:%.*]] = and i32 %x, 1
+; CHECK-NEXT:    [[TMP1:%.*]] = shl nuw nsw i32 [[AND]], 1
 ; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], %y
 ; CHECK-NEXT:    ret i32 [[TMP2]]
 ;
   %and = and i32 %x, 1
   %cmp = icmp eq i32 %and, 0
   %or = or i32 %y, 2
   %select = select i1 %cmp, i32 %y, i32 %or
   ret i32 %select
 }
 
 define <2 x i32> @select_icmp_eq_and_1_0_or_2_vec(<2 x i32> %x, <2 x i32> %y) {
 ; CHECK-LABEL: @select_icmp_eq_and_1_0_or_2_vec(
-; CHECK-NEXT:    [[AND:%.*]] = shl <2 x i32> [[X:%.*]], <i32 1, i32 1>
-; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i32> [[AND]], <i32 2, i32 2>
+; CHECK-NEXT:    [[AND:%.*]] = and <2 x i32> %x, <i32 1, i32 1>
+; CHECK-NEXT:    [[TMP1:%.*]] = shl nuw nsw <2 x i32> [[AND]], <i32 1, i32 1>
 ; CHECK-NEXT:    [[TMP2:%.*]] = or <2 x i32> [[TMP1]], [[Y:%.*]]
 ; CHECK-NEXT:    ret <2 x i32> [[TMP2]]
 ;
   %and = and <2 x i32> %x, <i32 1, i32 1>
   %cmp = icmp eq <2 x i32> %and, zeroinitializer
   %or = or <2 x i32> %y, <i32 2, i32 2>
   %select = select <2 x i1> %cmp, <2 x i32> %y, <2 x i32> %or
   ret <2 x i32> %select
;
   %cmp = icmp ne i32 0, %and
   %and2 = and i32 %y, -33
   %select = select i1 %cmp, i32 %y, i32 %and2
   ret i32 %select
 }
 
 define i32 @select_icmp_ne_0_and_32_or_4096(i32 %x, i32 %y) {
 ; CHECK-LABEL: @select_icmp_ne_0_and_32_or_4096(
-; CHECK-NEXT:    [[AND:%.*]] = shl i32 %x, 7
-; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[AND]], 4096
+; CHECK-NEXT:    [[AND:%.*]] = and i32 %x, 32
+; CHECK-NEXT:    [[TMP1:%.*]] = shl nuw nsw i32 [[AND]], 7
 ; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[TMP1]], 4096
 ; CHECK-NEXT:    [[TMP3:%.*]] = or i32 [[TMP2]], %y
 ; CHECK-NEXT:    ret i32 [[TMP3]]
 ;
   %and = and i32 %x, 32
   %cmp = icmp ne i32 0, %and
   %or = or i32 %y, 4096
   %select = select i1 %cmp, i32 %y, i32 %or
   ret i32 %select
 }
 
 define <2 x i32> @select_icmp_ne_0_and_32_or_4096_vec(<2 x i32> %x, <2 x i32> %y) {
 ; CHECK-LABEL: @select_icmp_ne_0_and_32_or_4096_vec(
-; CHECK-NEXT:    [[AND:%.*]] = shl <2 x i32> [[X:%.*]], <i32 7, i32 7>
-; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i32> [[AND]], <i32 4096, i32 4096>
+; CHECK-NEXT:    [[AND:%.*]] = and <2 x i32> %x, <i32 32, i32 32>
+; CHECK-NEXT:    [[TMP1:%.*]] = shl nuw nsw <2 x i32> [[AND]], <i32 7, i32 7>
 ; CHECK-NEXT:    [[TMP2:%.*]] = xor <2 x i32> [[TMP1]], <i32 4096, i32 4096>
 ; CHECK-NEXT:    [[TMP3:%.*]] = or <2 x i32> [[TMP2]], [[Y:%.*]]
 ; CHECK-NEXT:    ret <2 x i32> [[TMP3]]
 ;
   %and = and <2 x i32> %x, <i32 32, i32 32>
   %cmp = icmp ne <2 x i32> zeroinitializer, %and
   %or = or <2 x i32> %y, <i32 4096, i32 4096>
   %select = select <2 x i1> %cmp, <2 x i32> %y, <2 x i32> %or

 ;
   %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
 }
 
 define i32 @shift_no_xor_multiuse_or(i32 %x, i32 %y) {
 ; CHECK-LABEL: @shift_no_xor_multiuse_or(
-; CHECK-NEXT:    [[OR:%.*]] = or i32 [[Y:%.*]], 2
-; CHECK-NEXT:    [[AND:%.*]] = shl i32 [[X:%.*]], 1
-; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[AND]], 2
-; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[Y]]
+; CHECK-NEXT:    [[AND:%.*]] = and i32 %x, 1
+; CHECK-NEXT:    [[OR:%.*]] = or i32 %y, 2
+; CHECK-NEXT:    [[TMP1:%.*]] = shl nuw nsw i32 [[AND]], 1
+; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], %y
 ; CHECK-NEXT:    [[RES:%.*]] = mul i32 [[TMP2]], [[OR]]
 ; CHECK-NEXT:    ret i32 [[RES]]
 ;
   %and = and i32 %x, 1
   %cmp = icmp eq i32 %and, 0
   %or = or i32 %y, 2
   %select = select i1 %cmp, i32 %y, i32 %or
   %res = mul i32 %select, %or ; to bump up use count of the Or

test/Transforms/InstCombine/select.ll

 
 ;; (a & 128) ? 256 : 0
 define i32 @test15e(i32 %X) {
         %t1 = and i32 %X, 128
         %t2 = icmp ne i32 %t1, 0
         %t3 = select i1 %t2, i32 256, i32 0
         ret i32 %t3
 ; CHECK-LABEL: @test15e(
-; CHECK: %t1 = shl i32 %X, 1
-; CHECK: and i32 %t1, 256
+; CHECK: %t1 = and i32 %X, 128
+; CHECK: shl nuw nsw i32 %t1, 1
 ; CHECK: ret i32
 }
 
 ;; (a & 128) ? 0 : 256
 define i32 @test15f(i32 %X) {
         %t1 = and i32 %X, 128
         %t2 = icmp ne i32 %t1, 0
         %t3 = select i1 %t2, i32 0, i32 256
         ret i32 %t3
 ; CHECK-LABEL: @test15f(
-; CHECK: %t1 = shl i32 %X, 1
-; CHECK: and i32 %t1, 256
+; CHECK: %t1 = and i32 %X, 128
+; CHECK: shl nuw nsw i32 %t1, 1
 ; CHECK: xor i32 %{{.*}}, 256
 ; CHECK: ret i32
 }
 
 ;; (a & 8) ? -1 : -9
 define i32 @test15g(i32 %X) {
         %t1 = and i32 %X, 8
         %t2 = icmp ne i32 %t1, 0

 
 ;; (a & 2) ? 577 : 1089
 define i32 @test15i(i32 %X) {
         %t1 = and i32 %X, 2
         %t2 = icmp ne i32 %t1, 0
         %t3 = select i1 %t2, i32 577, i32 1089
         ret i32 %t3
 ; CHECK-LABEL: @test15i(
-; CHECK-NEXT: %t1 = shl i32 %X, 8
-; CHECK-NEXT: %1 = and i32 %t1, 512
+; CHECK-NEXT: %t1 = and i32 %X, 2
+; CHECK-NEXT: %1 = shl nuw nsw i32 %t1, 8
 ; CHECK-NEXT: %2 = xor i32 %1, 512
 ; CHECK-NEXT: %3 = add nuw nsw i32 %2, 577
 ; CHECK-NEXT: ret i32 %3
 }
 
 ;; (a & 2) ? 1089 : 577
 define i32 @test15j(i32 %X) {
         %t1 = and i32 %X, 2
         %t2 = icmp ne i32 %t1, 0
         %t3 = select i1 %t2, i32 1089, i32 577
         ret i32 %t3
 ; CHECK-LABEL: @test15j(
-; CHECK-NEXT: %t1 = shl i32 %X, 8
-; CHECK-NEXT: %1 = and i32 %t1, 512
+; CHECK-NEXT: %t1 = and i32 %X, 2
+; CHECK-NEXT: %1 = shl nuw nsw i32 %t1, 8
 ; CHECK-NEXT: %2 = add nuw nsw i32 %1, 577
 ; CHECK-NEXT: ret i32 %2
 }
 
 define i32 @test16(i1 %C, i32* %P) {
         %P2 = select i1 %C, i32* %P, i32* null
         %V = load i32, i32* %P2
         ret i32 %V

test/Transforms/InstCombine/shift-shift.ll

 
 define i32 @pr8547(i32* %g) {
 ; CHECK-LABEL: @pr8547(
 ; CHECK-NEXT:  codeRepl:
 ; CHECK-NEXT:    br label %for.cond
 ; CHECK:       for.cond:
 ; CHECK-NEXT:    [[STOREMERGE:%.*]] = phi i32 [ 0, %codeRepl ], [ 5, %for.cond ]
 ; CHECK-NEXT:    store i32 [[STOREMERGE]], i32* %g, align 4
-; CHECK-NEXT:    [[TMP0:%.*]] = shl nuw nsw i32 [[STOREMERGE]], 6
-; CHECK-NEXT:    [[CONV2:%.*]] = and i32 [[TMP0]], 64
-; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i32 [[CONV2]], 0
+; CHECK-NEXT:    [[TMP0:%.*]] = and i32 [[STOREMERGE]], 1
+; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i32 [[TMP0]], 0
 ; CHECK-NEXT:    br i1 [[TOBOOL]], label %for.cond, label %codeRepl2
 ; CHECK:       codeRepl2:
+; CHECK-NEXT:    [[CONV2:%.*]] = shl nuw nsw i32 [[TMP0]], 6
 ; CHECK-NEXT:    ret i32 [[CONV2]]
 ;
 codeRepl:
   br label %for.cond
 
 for.cond:
   %storemerge = phi i32 [ 0, %codeRepl ], [ 5, %for.cond ]
   store i32 %storemerge, i32* %g, align 4

test/Transforms/InstCombine/shift.ll

 }
 
 ; <rdar://problem/8756731>
 define i8 @test39(i32 %a0) {
 ; CHECK-LABEL: @test39(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP4:%.*]] = trunc i32 %a0 to i8
 ; CHECK-NEXT:    [[TMP5:%.*]] = shl i8 [[TMP4]], 5
-; CHECK-NEXT:    [[TMP49:%.*]] = shl i8 [[TMP4]], 6
-; CHECK-NEXT:    [[TMP50:%.*]] = and i8 [[TMP49]], 64
+; CHECK-NEXT:    [[TMP49:%.*]] = and i8 [[TMP4]], 1
+; CHECK-NEXT:    [[TMP50:%.*]] = shl nuw nsw i8 [[TMP49]], 6
 ; CHECK-NEXT:    [[TMP51:%.*]] = xor i8 [[TMP50]], [[TMP5]]
-; CHECK-NEXT:    [[TMP0:%.*]] = shl i8 [[TMP4]], 2
-; CHECK-NEXT:    [[TMP54:%.*]] = and i8 [[TMP0]], 16
+; CHECK-NEXT:    [[TMP0:%.*]] = lshr i8 [[TMP4]], 2
+; CHECK-NEXT:    [[TMP53:%.*]] = and i8 [[TMP0]], 1
+; CHECK-NEXT:    [[TMP54:%.*]] = shl nuw nsw i8 [[TMP53]], 4
 ; CHECK-NEXT:    [[TMP551:%.*]] = or i8 [[TMP54]], [[TMP51]]
 ; CHECK-NEXT:    ret i8 [[TMP551]]
 ;
 entry:
   %tmp4 = trunc i32 %a0 to i8
   %tmp5 = shl i8 %tmp4, 5
   %tmp48 = and i8 %tmp5, 32
   %tmp49 = lshr i8 %tmp48, 5
;
   %B = lshr <2 x i32> %A, <i32 1, i32 1>
   ret <2 x i32> %B
 }
 
 ; (X << C1) >>u C2  --> X << (C1 - C2) & (-1 >> C2)
 
 define i8 @test53_no_nuw(i8 %x) {
 ; CHECK-LABEL: @test53_no_nuw(
-; CHECK-NEXT:    [[TMP1:%.*]] = shl i8 %x, 2
-; CHECK-NEXT:    [[B:%.*]] = and i8 [[TMP1]], 124
+; CHECK-NEXT:    [[TMP1:%.*]] = and i8 %x, 31
+; CHECK-NEXT:    [[B:%.*]] = shl nuw nsw i8 [[TMP1]], 2
 ; CHECK-NEXT:    ret i8 [[B]]
 ;
   %A = shl i8 %x, 3
   %B = lshr i8 %A, 1
   ret i8 %B
 }
 
 ; (X << C1) >>u C2  --> X << (C1 - C2) & (-1 >> C2)
 
 define <2 x i8> @test53_no_nuw_splat_vec(<2 x i8> %x) {
 ; CHECK-LABEL: @test53_no_nuw_splat_vec(
-; CHECK-NEXT:    [[TMP1:%.*]] = shl <2 x i8> %x, <i8 2, i8 2>
-; CHECK-NEXT:    [[B:%.*]] = and <2 x i8> [[TMP1]], <i8 124, i8 124>
+; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i8> %x, <i8 31, i8 31>
+; CHECK-NEXT:    [[B:%.*]] = shl nuw nsw <2 x i8> [[TMP1]], <i8 2, i8 2>
 ; CHECK-NEXT:    ret <2 x i8> [[B]]
 ;
   %A = shl <2 x i8> %x, <i8 3, i8 3>
   %B = lshr <2 x i8> %A, <i8 1, i8 1>
   ret <2 x i8> %B
 }
 
 define i32 @test54(i32 %x) {
 ; CHECK-LABEL: @test54(
-; CHECK-NEXT:    [[TMP1:%.*]] = shl i32 %x, 3
-; CHECK-NEXT:    [[AND:%.*]] = and i32 [[TMP1]], 16
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 %x, 2
+; CHECK-NEXT:    [[AND:%.*]] = shl nuw nsw i32 [[TMP1]], 3
 ; CHECK-NEXT:    ret i32 [[AND]]
 ;
   %shr2 = lshr i32 %x, 1
   %shl = shl i32 %shr2, 4
   %and = and i32 %shl, 16
   ret i32 %and
 }
 
 define <2 x i32> @test54_splat_vec(<2 x i32> %x) {
 ; CHECK-LABEL: @test54_splat_vec(
-; CHECK-NEXT:    [[TMP1:%.*]] = shl <2 x i32> %x, <i32 3, i32 3>
-; CHECK-NEXT:    [[AND:%.*]] = and <2 x i32> [[TMP1]], <i32 16, i32 16>
+; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i32> %x, <i32 2, i32 2>
+; CHECK-NEXT:    [[AND:%.*]] = shl nuw nsw <2 x i32> [[TMP1]], <i32 3, i32 3>
 ; CHECK-NEXT:    ret <2 x i32> [[AND]]
 ;
   %shr2 = lshr <2 x i32> %x, <i32 1, i32 1>
   %shl = shl <2 x i32> %shr2, <i32 4, i32 4>
   %and = and <2 x i32> %shl, <i32 16, i32 16>
   ret <2 x i32> %and
 }