Index: lib/Analysis/InstructionSimplify.cpp
===================================================================
--- lib/Analysis/InstructionSimplify.cpp
+++ lib/Analysis/InstructionSimplify.cpp
@@ -3422,6 +3422,64 @@
   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,
@@ -3446,11 +3504,11 @@
     //   %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) {
@@ -3475,6 +3533,17 @@
     }
   }
 
+  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
Index: lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
===================================================================
--- lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
+++ lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
@@ -1212,6 +1212,13 @@
       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)))) ||
@@ -1420,11 +1427,13 @@
   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;
Index: lib/Transforms/InstCombine/InstCombineShifts.cpp
===================================================================
--- lib/Transforms/InstCombine/InstCombineShifts.cpp
+++ lib/Transforms/InstCombine/InstCombineShifts.cpp
@@ -505,7 +505,8 @@
       // 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);
Index: test/Transforms/InstCombine/2010-11-01-lshr-mask.ll
===================================================================
--- test/Transforms/InstCombine/2010-11-01-lshr-mask.ll
+++ test/Transforms/InstCombine/2010-11-01-lshr-mask.ll
@@ -4,8 +4,9 @@
 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]]
Index: test/Transforms/InstCombine/cast.ll
===================================================================
--- test/Transforms/InstCombine/cast.ll
+++ test/Transforms/InstCombine/cast.ll
@@ -589,8 +589,8 @@
 
 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
@@ -602,8 +602,8 @@
 
 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>
@@ -811,13 +811,12 @@
 
 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
@@ -1277,8 +1276,8 @@
 
 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
Index: test/Transforms/InstCombine/or-shifted-masks.ll
===================================================================
--- test/Transforms/InstCombine/or-shifted-masks.ll
+++ test/Transforms/InstCombine/or-shifted-masks.ll
@@ -2,10 +2,10 @@
 
 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]]
 ;
@@ -19,8 +19,8 @@
 
 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]]
@@ -36,10 +36,10 @@
 
 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]]
 ;
@@ -53,8 +53,8 @@
 
 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]]
@@ -74,18 +74,12 @@
 
 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
@@ -106,17 +100,15 @@
 
 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
@@ -182,14 +174,14 @@
 ; 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{{.*}}
Index: test/Transforms/InstCombine/pr17827.ll
===================================================================
--- test/Transforms/InstCombine/pr17827.ll
+++ test/Transforms/InstCombine/pr17827.ll
@@ -4,8 +4,8 @@
 ; 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]]
 ;
@@ -33,8 +33,8 @@
 ; 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]]
 ;
@@ -49,8 +49,8 @@
 
 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]]
 ;
@@ -66,8 +66,8 @@
 ; 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
@@ -91,8 +91,8 @@
 ; 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]]
 ;
Index: test/Transforms/InstCombine/rem.ll
===================================================================
--- test/Transforms/InstCombine/rem.ll
+++ test/Transforms/InstCombine/rem.ll
@@ -362,8 +362,8 @@
 
 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
Index: test/Transforms/InstCombine/select-bitext-bitwise-ops.ll
===================================================================
--- test/Transforms/InstCombine/select-bitext-bitwise-ops.ll
+++ test/Transforms/InstCombine/select-bitext-bitwise-ops.ll
@@ -2,13 +2,11 @@
 
 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
@@ -21,8 +19,8 @@
 
 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]]
@@ -38,13 +36,11 @@
 
 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
@@ -74,13 +70,11 @@
 
 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
Index: test/Transforms/InstCombine/select-with-bitwise-ops.ll
===================================================================
--- test/Transforms/InstCombine/select-with-bitwise-ops.ll
+++ test/Transforms/InstCombine/select-with-bitwise-ops.ll
@@ -5,8 +5,8 @@
 
 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]]
 ;
@@ -19,8 +19,8 @@
 
 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]]
 ;
@@ -337,8 +337,8 @@
 
 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]]
@@ -352,8 +352,8 @@
 
 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]]
@@ -970,10 +970,10 @@
 
 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]]
 ;
Index: test/Transforms/InstCombine/select.ll
===================================================================
--- test/Transforms/InstCombine/select.ll
+++ test/Transforms/InstCombine/select.ll
@@ -385,8 +385,8 @@
         %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
 }
 
@@ -397,8 +397,8 @@
         %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
 }
@@ -433,8 +433,8 @@
         %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
@@ -447,8 +447,8 @@
         %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
 }
Index: test/Transforms/InstCombine/shift-shift.ll
===================================================================
--- test/Transforms/InstCombine/shift-shift.ll
+++ test/Transforms/InstCombine/shift-shift.ll
@@ -51,11 +51,11 @@
 ; 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:
Index: test/Transforms/InstCombine/shift.ll
===================================================================
--- test/Transforms/InstCombine/shift.ll
+++ test/Transforms/InstCombine/shift.ll
@@ -708,11 +708,12 @@
 ; 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]]
 ;
@@ -1055,8 +1056,8 @@
 
 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
@@ -1068,8 +1069,8 @@
 
 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>
@@ -1079,8 +1080,8 @@
 
 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
@@ -1091,8 +1092,8 @@
 
 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>