diff --git a/llvm/lib/Analysis/LazyValueInfo.cpp b/llvm/lib/Analysis/LazyValueInfo.cpp
--- a/llvm/lib/Analysis/LazyValueInfo.cpp
+++ b/llvm/lib/Analysis/LazyValueInfo.cpp
@@ -1093,7 +1093,8 @@
   return ValueLatticeElement::getOverdefined();
 }
 
-static bool matchICmpOperand(const APInt *&Offset, Value *LHS, Value *Val) {
+static bool matchICmpOperand(const APInt *&Offset, Value *LHS, Value *Val,
+                             ICmpInst::Predicate Pred) {
   if (LHS == Val)
     return true;
 
@@ -1102,6 +1103,16 @@
   if (match(LHS, m_Add(m_Specific(Val), m_APInt(Offset))))
     return true;
 
+  // If (x | y) < C, then (x < C) && (y < C).
+  if (match(LHS, m_c_Or(m_Specific(Val), m_Value())) &&
+      (Pred == ICmpInst::ICMP_ULT || Pred == ICmpInst::ICMP_ULE))
+    return true;
+
+  // If (x & y) > C, then (x > C) && (y > C).
+  if (match(LHS, m_c_And(m_Specific(Val), m_Value())) &&
+      (Pred == ICmpInst::ICMP_UGT || Pred == ICmpInst::ICMP_UGE))
+    return true;
+
   return false;
 }
 
@@ -1127,10 +1138,10 @@
     return ValueLatticeElement::getOverdefined();
 
   const APInt *Offset = nullptr;
-  if (!matchICmpOperand(Offset, LHS, Val)) {
+  if (!matchICmpOperand(Offset, LHS, Val, EdgePred)) {
     std::swap(LHS, RHS);
     EdgePred = CmpInst::getSwappedPredicate(EdgePred);
-    if (!matchICmpOperand(Offset, LHS, Val))
+    if (!matchICmpOperand(Offset, LHS, Val, EdgePred))
       return ValueLatticeElement::getOverdefined();
   }
 
diff --git a/llvm/test/Transforms/CorrelatedValuePropagation/icmp.ll b/llvm/test/Transforms/CorrelatedValuePropagation/icmp.ll
--- a/llvm/test/Transforms/CorrelatedValuePropagation/icmp.ll
+++ b/llvm/test/Transforms/CorrelatedValuePropagation/icmp.ll
@@ -659,10 +659,8 @@
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[OR]], 42
 ; CHECK-NEXT:    br i1 [[CMP]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
 ; CHECK:       if.true:
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i32 [[A]], 42
-; CHECK-NEXT:    call void @check1(i1 [[CMP2]])
-; CHECK-NEXT:    [[CMP3:%.*]] = icmp ult i32 [[B]], 42
-; CHECK-NEXT:    call void @check1(i1 [[CMP3]])
+; CHECK-NEXT:    call void @check1(i1 true)
+; CHECK-NEXT:    call void @check1(i1 true)
 ; CHECK-NEXT:    ret void
 ; CHECK:       if.false:
 ; CHECK-NEXT:    [[CMP4:%.*]] = icmp uge i32 [[A]], 42
@@ -698,10 +696,8 @@
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ule i32 [[OR]], 42
 ; CHECK-NEXT:    br i1 [[CMP]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
 ; CHECK:       if.true:
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp ule i32 [[A]], 42
-; CHECK-NEXT:    call void @check1(i1 [[CMP2]])
-; CHECK-NEXT:    [[CMP3:%.*]] = icmp ule i32 [[B]], 42
-; CHECK-NEXT:    call void @check1(i1 [[CMP3]])
+; CHECK-NEXT:    call void @check1(i1 true)
+; CHECK-NEXT:    call void @check1(i1 true)
 ; CHECK-NEXT:    ret void
 ; CHECK:       if.false:
 ; CHECK-NEXT:    [[CMP4:%.*]] = icmp ugt i32 [[A]], 42
@@ -743,10 +739,8 @@
 ; CHECK-NEXT:    call void @check1(i1 [[CMP3]])
 ; CHECK-NEXT:    ret void
 ; CHECK:       if.false:
-; CHECK-NEXT:    [[CMP4:%.*]] = icmp ule i32 [[A]], 42
-; CHECK-NEXT:    call void @check1(i1 [[CMP4]])
-; CHECK-NEXT:    [[CMP5:%.*]] = icmp ule i32 [[B]], 42
-; CHECK-NEXT:    call void @check1(i1 [[CMP5]])
+; CHECK-NEXT:    call void @check1(i1 true)
+; CHECK-NEXT:    call void @check1(i1 true)
 ; CHECK-NEXT:    ret void
 ;
 entry:
@@ -782,10 +776,8 @@
 ; CHECK-NEXT:    call void @check1(i1 [[CMP3]])
 ; CHECK-NEXT:    ret void
 ; CHECK:       if.false:
-; CHECK-NEXT:    [[CMP4:%.*]] = icmp ult i32 [[A]], 42
-; CHECK-NEXT:    call void @check1(i1 [[CMP4]])
-; CHECK-NEXT:    [[CMP5:%.*]] = icmp ult i32 [[B]], 42
-; CHECK-NEXT:    call void @check1(i1 [[CMP5]])
+; CHECK-NEXT:    call void @check1(i1 true)
+; CHECK-NEXT:    call void @check1(i1 true)
 ; CHECK-NEXT:    ret void
 ;
 entry:
@@ -854,10 +846,8 @@
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i32 [[AND]], 42
 ; CHECK-NEXT:    br i1 [[CMP]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
 ; CHECK:       if.true:
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp ugt i32 [[A]], 42
-; CHECK-NEXT:    call void @check1(i1 [[CMP2]])
-; CHECK-NEXT:    [[CMP3:%.*]] = icmp ugt i32 [[B]], 42
-; CHECK-NEXT:    call void @check1(i1 [[CMP3]])
+; CHECK-NEXT:    call void @check1(i1 true)
+; CHECK-NEXT:    call void @check1(i1 true)
 ; CHECK-NEXT:    ret void
 ; CHECK:       if.false:
 ; CHECK-NEXT:    [[CMP4:%.*]] = icmp ule i32 [[A]], 42
@@ -893,10 +883,8 @@
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp uge i32 [[AND]], 42
 ; CHECK-NEXT:    br i1 [[CMP]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
 ; CHECK:       if.true:
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp uge i32 [[A]], 42
-; CHECK-NEXT:    call void @check1(i1 [[CMP2]])
-; CHECK-NEXT:    [[CMP3:%.*]] = icmp uge i32 [[B]], 42
-; CHECK-NEXT:    call void @check1(i1 [[CMP3]])
+; CHECK-NEXT:    call void @check1(i1 true)
+; CHECK-NEXT:    call void @check1(i1 true)
 ; CHECK-NEXT:    ret void
 ; CHECK:       if.false:
 ; CHECK-NEXT:    [[CMP4:%.*]] = icmp ult i32 [[A]], 42
@@ -938,10 +926,8 @@
 ; CHECK-NEXT:    call void @check1(i1 [[CMP3]])
 ; CHECK-NEXT:    ret void
 ; CHECK:       if.false:
-; CHECK-NEXT:    [[CMP4:%.*]] = icmp uge i32 [[A]], 42
-; CHECK-NEXT:    call void @check1(i1 [[CMP4]])
-; CHECK-NEXT:    [[CMP5:%.*]] = icmp uge i32 [[B]], 42
-; CHECK-NEXT:    call void @check1(i1 [[CMP5]])
+; CHECK-NEXT:    call void @check1(i1 true)
+; CHECK-NEXT:    call void @check1(i1 true)
 ; CHECK-NEXT:    ret void
 ;
 entry: