Index: lib/Analysis/LazyValueInfo.cpp
===================================================================
--- lib/Analysis/LazyValueInfo.cpp
+++ lib/Analysis/LazyValueInfo.cpp
@@ -1174,14 +1174,9 @@
   return true;
 }
 
-bool getValueFromCondition(Value *Val, Value *Cond, LVILatticeVal &Result,
-                           bool isTrueDest) {
-  assert(Cond && "precondition");
-
-  // For now we only support ICmpInst conditions
-  ICmpInst *ICI = dyn_cast<ICmpInst>(Cond);
-  if (!ICI)
-    return false;
+bool getValueFromICmpCondition(Value *Val, ICmpInst *ICI, LVILatticeVal &Result,
+                               bool isTrueDest) {
+  assert(ICI && "precondition");
 
   if (isa<Constant>(ICI->getOperand(1))) {
     if (ICI->isEquality() && ICI->getOperand(0) == Val) {
@@ -1222,6 +1217,39 @@
   return false;
 }
 
+bool getValueFromCondition(Value *Val, Value *Cond, LVILatticeVal &Result,
+                           bool isTrueDest) {
+  assert(Cond && "precondition");
+
+  if (ICmpInst *ICI = dyn_cast<ICmpInst>(Cond))
+    return getValueFromICmpCondition(Val, ICI, Result, isTrueDest);
+
+  // Handle conditions in the form of (cond1 && cond2), we know that on the
+  // true dest path both of the conditions hold.
+  if (!isTrueDest)
+    return false;
+
+  BinaryOperator *BO = dyn_cast<BinaryOperator>(Cond);
+  if (!BO || BO->getOpcode() != BinaryOperator::And)
+    return false;
+
+  auto GetFromCondition = [&] (Value *C, LVILatticeVal &LV) {
+      bool Res = getValueFromCondition(Val, C, LV, isTrueDest);
+      if (!Res)
+        LV.markOverdefined();
+      return Res;
+  };
+
+  LVILatticeVal LHS, RHS;
+  bool LHSResult = GetFromCondition(BO->getOperand(0), LHS);
+  bool RHSResult = GetFromCondition(BO->getOperand(1), RHS);
+  if (!LHSResult && !RHSResult)
+    return false;
+
+  Result = intersect(LHS, RHS);
+  return true;
+}
+
 /// \brief Compute the value of Val on the edge BBFrom -> BBTo. Returns false if
 /// Val is not constrained on the edge.  Result is unspecified if return value
 /// is false.
Index: test/Transforms/CorrelatedValuePropagation/add.ll
===================================================================
--- test/Transforms/CorrelatedValuePropagation/add.ll
+++ test/Transforms/CorrelatedValuePropagation/add.ll
@@ -89,3 +89,79 @@
 exit:
   ret void
 }
+
+; Check that we can gather information for conditions is the form of
+;   and ( i s< 100, ... )
+; CHECK-LABEL: @test6(
+define void @test6(i32 %a, i1 %flag) {
+entry:
+  %cmp.1 = icmp slt i32 %a, 100
+  %cmp = and i1 %cmp.1, %flag
+  br i1 %cmp, label %bb, label %exit
+
+bb:
+; CHECK: %add = add nsw i32 %a, 1
+  %add = add i32 %a, 1
+  br label %exit
+
+exit:
+  ret void
+}
+
+; Check that we can gather information for conditions is the form of
+;   and ( i s< 100, i s> 0 )
+; CHECK-LABEL: @test7(
+define void @test7(i32 %a) {
+entry:
+  %cmp.1 = icmp slt i32 %a, 100
+  %cmp.2 = icmp sgt i32 %a, 0
+  %cmp = and i1 %cmp.1, %cmp.2
+  br i1 %cmp, label %bb, label %exit
+
+bb:
+; CHECK: %add = add nuw nsw i32 %a, 1
+  %add = add i32 %a, 1
+  br label %exit
+
+exit:
+  ret void
+}
+
+; Check that for conditions is the form of cond1 && cond2 we don't mistakenly
+; assume that !cond1 && !cond2 holds down to false path.
+; CHECK-LABEL: @test7_neg(
+define void @test7_neg(i32 %a) {
+entry:
+  %cmp.1 = icmp sge i32 %a, 100
+  %cmp.2 = icmp sle i32 %a, 0
+  %cmp = and i1 %cmp.1, %cmp.2
+  br i1 %cmp, label %exit, label %bb
+
+bb:
+; CHECK: %add = add i32 %a, 1
+  %add = add i32 %a, 1
+  br label %exit
+
+exit:
+  ret void
+}
+
+; Check that we can gather information for conditions is the form of
+;   and ( i s< 100, and (i s> 0, ... )
+; CHECK-LABEL: @test8(
+define void @test8(i32 %a, i1 %flag) {
+entry:
+  %cmp.1 = icmp slt i32 %a, 100
+  %cmp.2 = icmp sgt i32 %a, 0
+  %cmp.3 = and i1 %cmp.2, %flag
+  %cmp = and i1 %cmp.1, %cmp.3
+  br i1 %cmp, label %bb, label %exit
+
+bb:
+; CHECK: %add = add nuw nsw i32 %a, 1
+  %add = add i32 %a, 1
+  br label %exit
+
+exit:
+  ret void
+}