Index: lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
===================================================================
--- lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
+++ lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
@@ -700,6 +700,28 @@
   return Changed;
 }
 
+static bool processAnd(BinaryOperator *BinOp, LazyValueInfo *LVI) {
+  if (BinOp->getType()->isVectorTy())
+    return false;
+
+  // Pattern match (and lhs, C) where C includes a superset of bits which might
+  // be set in lhs.  This is a common truncation idiom created by instcombine.
+  BasicBlock *BB = BinOp->getParent();
+  Value *LHS = BinOp->getOperand(0);
+  ConstantInt *RHS = dyn_cast<ConstantInt>(BinOp->getOperand(1));
+  if (!RHS || !RHS->getValue().isMask())
+    return false;
+
+  ConstantRange LRange = LVI->getConstantRange(LHS, BB, BinOp);
+  if (!LRange.getUnsignedMax().ule(RHS->getValue()))
+    return false;
+
+  BinOp->replaceAllUsesWith(LHS);
+  BinOp->eraseFromParent();
+  return true;
+}
+
+
 static Constant *getConstantAt(Value *V, Instruction *At, LazyValueInfo *LVI) {
   if (Constant *C = LVI->getConstant(V, At->getParent(), At))
     return C;
@@ -774,6 +796,9 @@
       case Instruction::Sub:
         BBChanged |= processBinOp(cast<BinaryOperator>(II), LVI);
         break;
+      case Instruction::And:
+        BBChanged |= processAnd(cast<BinaryOperator>(II), LVI);
+        break;
       }
     }
 
Index: test/Transforms/CorrelatedValuePropagation/and.ll
===================================================================
--- test/Transforms/CorrelatedValuePropagation/and.ll
+++ test/Transforms/CorrelatedValuePropagation/and.ll
@@ -0,0 +1,127 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -correlated-propagation -S | FileCheck %s
+
+define i32 @test(i32 %a) {
+; CHECK-LABEL: @test(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[A:%.*]], 128
+; CHECK-NEXT:    br i1 [[CMP]], label [[CONTINUE:%.*]], label [[EXIT:%.*]]
+; CHECK:       continue:
+; CHECK-NEXT:    ret i32 [[A]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret i32 -1
+;
+entry:
+  %cmp = icmp ult i32 %a, 128
+  br i1 %cmp, label %continue, label %exit
+continue:
+  %and = and i32 %a, 255
+  ret i32 %and
+exit:
+  ret i32 -1
+}
+
+define i32 @test2(i32 %a) {
+; CHECK-LABEL: @test2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[A:%.*]], 256
+; CHECK-NEXT:    br i1 [[CMP]], label [[CONTINUE:%.*]], label [[EXIT:%.*]]
+; CHECK:       continue:
+; CHECK-NEXT:    ret i32 [[A]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret i32 -1
+;
+entry:
+  %cmp = icmp ult i32 %a, 256
+  br i1 %cmp, label %continue, label %exit
+continue:
+  %and = and i32 %a, 255
+  ret i32 %and
+exit:
+  ret i32 -1
+}
+
+define i32 @test3(i32 %a) {
+; CHECK-LABEL: @test3(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[A:%.*]], 256
+; CHECK-NEXT:    br i1 [[CMP]], label [[CONTINUE:%.*]], label [[EXIT:%.*]]
+; CHECK:       continue:
+; CHECK-NEXT:    ret i32 [[A]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret i32 -1
+;
+entry:
+  %cmp = icmp ult i32 %a, 256
+  br i1 %cmp, label %continue, label %exit
+continue:
+  %and = and i32 %a, 1023
+  ret i32 %and
+exit:
+  ret i32 -1
+}
+
+
+define i32 @neg1(i32 %a) {
+; CHECK-LABEL: @neg1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ule i32 [[A:%.*]], 256
+; CHECK-NEXT:    br i1 [[CMP]], label [[CONTINUE:%.*]], label [[EXIT:%.*]]
+; CHECK:       continue:
+; CHECK-NEXT:    [[AND:%.*]] = and i32 [[A]], 255
+; CHECK-NEXT:    ret i32 [[AND]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret i32 -1
+;
+entry:
+  %cmp = icmp ule i32 %a, 256
+  br i1 %cmp, label %continue, label %exit
+continue:
+  %and = and i32 %a, 255
+  ret i32 %and
+exit:
+  ret i32 -1
+}
+
+define i32 @neg2(i32 %a) {
+; CHECK-LABEL: @neg2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[A:%.*]], 513
+; CHECK-NEXT:    br i1 [[CMP]], label [[CONTINUE:%.*]], label [[EXIT:%.*]]
+; CHECK:       continue:
+; CHECK-NEXT:    [[AND:%.*]] = and i32 [[A]], 255
+; CHECK-NEXT:    ret i32 [[AND]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret i32 -1
+;
+entry:
+  %cmp = icmp ult i32 %a, 513
+  br i1 %cmp, label %continue, label %exit
+continue:
+  %and = and i32 %a, 255
+  ret i32 %and
+exit:
+  ret i32 -1
+}
+
+define i32 @neg3(i32 %a) {
+; CHECK-LABEL: @neg3(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[A:%.*]], 256
+; CHECK-NEXT:    br i1 [[CMP]], label [[CONTINUE:%.*]], label [[EXIT:%.*]]
+; CHECK:       continue:
+; CHECK-NEXT:    [[AND:%.*]] = and i32 [[A]], 254
+; CHECK-NEXT:    ret i32 [[AND]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret i32 -1
+;
+entry:
+  %cmp = icmp ult i32 %a, 256
+  br i1 %cmp, label %continue, label %exit
+continue:
+  %and = and i32 %a, 254
+  ret i32 %and
+exit:
+  ret i32 -1
+}
+