Index: llvm/trunk/lib/Analysis/LazyValueInfo.cpp
===================================================================
--- llvm/trunk/lib/Analysis/LazyValueInfo.cpp
+++ llvm/trunk/lib/Analysis/LazyValueInfo.cpp
@@ -1167,14 +1167,8 @@
   return true;
 }
 
-LVILatticeVal getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest) {
-  assert(Cond && "precondition");
-
-  // For now we only support ICmpInst conditions
-  ICmpInst *ICI = dyn_cast<ICmpInst>(Cond);
-  if (!ICI)
-    return LVILatticeVal::getOverdefined();
-
+static LVILatticeVal getValueFromICmpCondition(Value *Val, ICmpInst *ICI,
+                                               bool isTrueDest) {
   Value *LHS = ICI->getOperand(0);
   Value *RHS = ICI->getOperand(1);
   CmpInst::Predicate Predicate = ICI->getPredicate();
@@ -1233,6 +1227,46 @@
   return LVILatticeVal::getOverdefined();
 }
 
+static LVILatticeVal
+getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest,
+                      DenseMap<Value*, LVILatticeVal> &Visited);
+
+static LVILatticeVal
+getValueFromConditionImpl(Value *Val, Value *Cond, bool isTrueDest,
+                          DenseMap<Value*, LVILatticeVal> &Visited) {
+  if (ICmpInst *ICI = dyn_cast<ICmpInst>(Cond))
+    return getValueFromICmpCondition(Val, ICI, 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 LVILatticeVal::getOverdefined();
+
+  BinaryOperator *BO = dyn_cast<BinaryOperator>(Cond);
+  if (!BO || BO->getOpcode() != BinaryOperator::And)
+    return LVILatticeVal::getOverdefined();
+
+  auto RHS = getValueFromCondition(Val, BO->getOperand(0), isTrueDest, Visited);
+  auto LHS = getValueFromCondition(Val, BO->getOperand(1), isTrueDest, Visited);
+  return intersect(RHS, LHS);
+}
+
+static LVILatticeVal
+getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest,
+                      DenseMap<Value*, LVILatticeVal> &Visited) {
+  auto I = Visited.find(Cond);
+  if (I != Visited.end())
+    return I->second;
+  return Visited[Cond] = getValueFromConditionImpl(Val, Cond, isTrueDest,
+                                                   Visited);
+}
+
+LVILatticeVal getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest) {
+  assert(Cond && "precondition");
+  DenseMap<Value*, LVILatticeVal> Visited;
+  return getValueFromCondition(Val, Cond, isTrueDest, Visited);
+}
+
 /// \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: llvm/trunk/test/Transforms/CorrelatedValuePropagation/add.ll
===================================================================
--- llvm/trunk/test/Transforms/CorrelatedValuePropagation/add.ll
+++ llvm/trunk/test/Transforms/CorrelatedValuePropagation/add.ll
@@ -99,3 +99,97 @@
   %add = add i32 %a, ptrtoint (i32* @b to i32)
   ret void
 }
+
+; Check that we can gather information for conditions is the form of
+;   and ( i s< 100, Unknown )
+; CHECK-LABEL: @test7(
+define void @test7(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: @test8(
+define void @test8(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: @test8_neg(
+define void @test8_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, Unknown )
+; CHECK-LABEL: @test9(
+define void @test9(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
+}
+
+; Check that we can gather information for conditions is the form of
+;   and ( i s< Unknown, ... )
+; CHECK-LABEL: @test10(
+define void @test10(i32 %a, i32 %b, i1 %flag) {
+entry:
+  %cmp.1 = icmp slt i32 %a, %b
+  %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
+}