diff --git a/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp b/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
--- a/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
+++ b/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
@@ -63,6 +63,7 @@
 STATISTIC(NumAShrs,     "Number of ashr converted to lshr");
 STATISTIC(NumSRems,     "Number of srem converted to urem");
 STATISTIC(NumSExt,      "Number of sext converted to zext");
+STATISTIC(NumAnd,       "Number of ands removed");
 STATISTIC(NumOverflows, "Number of overflow checks removed");
 STATISTIC(NumSaturating,
     "Number of saturating arithmetics converted to normal arithmetics");
@@ -700,6 +701,29 @@
   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();
+  NumAnd++;
+  return true;
+}
+
+
 static Constant *getConstantAt(Value *V, Instruction *At, LazyValueInfo *LVI) {
   if (Constant *C = LVI->getConstant(V, At->getParent(), At))
     return C;
@@ -774,6 +798,9 @@
       case Instruction::Sub:
         BBChanged |= processBinOp(cast<BinaryOperator>(II), LVI);
         break;
+      case Instruction::And:
+        BBChanged |= processAnd(cast<BinaryOperator>(II), LVI);
+        break;
       }
     }
 
diff --git a/llvm/test/Transforms/CorrelatedValuePropagation/and.ll b/llvm/test/Transforms/CorrelatedValuePropagation/and.ll
new file mode 100644
--- /dev/null
+++ b/llvm/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
+}
+
diff --git a/llvm/test/Transforms/CorrelatedValuePropagation/overflows.ll b/llvm/test/Transforms/CorrelatedValuePropagation/overflows.ll
--- a/llvm/test/Transforms/CorrelatedValuePropagation/overflows.ll
+++ b/llvm/test/Transforms/CorrelatedValuePropagation/overflows.ll
@@ -1023,7 +1023,6 @@
 ; CHECK-NEXT:    [[MUL:%.*]] = extractvalue { i32, i1 } [[TMP0]], 0
 ; CHECK-NEXT:    br label [[CONT3:%.*]]
 ; CHECK:       cont3:
-; CHECK-NEXT:    [[CMP5:%.*]] = and i1 true, true
 ; CHECK-NEXT:    br label [[OUT]]
 ; CHECK:       out:
 ; CHECK-NEXT:    ret i1 true
diff --git a/llvm/test/Transforms/CorrelatedValuePropagation/range.ll b/llvm/test/Transforms/CorrelatedValuePropagation/range.ll
--- a/llvm/test/Transforms/CorrelatedValuePropagation/range.ll
+++ b/llvm/test/Transforms/CorrelatedValuePropagation/range.ll
@@ -745,10 +745,9 @@
 define i1 @test17_i1(i1 %a) {
 ; CHECK-LABEL: @test17_i1(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[C:%.*]] = and i1 [[A:%.*]], true
 ; CHECK-NEXT:    br label [[DISPATCH:%.*]]
 ; CHECK:       dispatch:
-; CHECK-NEXT:    br i1 [[A]], label [[TRUE:%.*]], label [[DISPATCH]]
+; CHECK-NEXT:    br i1 [[A:%.*]], label [[TRUE:%.*]], label [[DISPATCH]]
 ; CHECK:       true:
 ; CHECK-NEXT:    ret i1 true
 ;