Index: llvm/trunk/lib/Analysis/LazyValueInfo.cpp
===================================================================
--- llvm/trunk/lib/Analysis/LazyValueInfo.cpp
+++ llvm/trunk/lib/Analysis/LazyValueInfo.cpp
@@ -354,6 +354,8 @@
       if (!BlockValueSet.insert(BV).second)
         return false;  // It's already in the stack.
 
+      DEBUG(dbgs() << "PUSH: " << *BV.second << " in " << BV.first->getName()
+                   << "\n");
       BlockValueStack.push(BV);
       return true;
     }
@@ -510,6 +512,9 @@
       assert(hasCachedValueInfo(e.second, e.first) &&
              "Result should be in cache!");
 
+      DEBUG(dbgs() << "POP " << *e.second << " in " << e.first->getName()
+                   << " = " << lookup(e.second)[e.first] << "\n");
+
       BlockValueStack.pop();
       BlockValueSet.erase(e);
     } else {
@@ -1040,6 +1045,69 @@
   return false;
 }
 
+/// Returns true if this lattice value represents at most one possible value.
+/// This is as precise as any lattice value can get while still representing
+/// reachable code.
+static bool hasSingleValue(LVILatticeVal Val) {
+  if (Val.isConstantRange() &&
+      Val.getConstantRange().isSingleElement())
+    // Integer constants are single element ranges
+    return true;
+  if (Val.isConstant())
+    // Non integer constants
+    return true;
+  return false;
+}
+
+/// Combine two sets of facts about the same value into a single set of
+/// facts.  Note that this method is not suitable for merging facts along
+/// different paths in a CFG; that's what the mergeIn function is for.  This
+/// is for merging facts gathered about the same value at the same location
+/// through two independent means.
+/// Notes:
+/// * This method does not promise to return the most precise possible lattice
+///   value implied by A and B.  It is allowed to return any lattice element
+///   which is at least as strong as *either* A or B (unless our facts
+///   conflict, see below).  
+/// * Due to unreachable code, the intersection of two lattice values could be
+///   contradictory.  If this happens, we return some valid lattice value so as
+///   not confuse the rest of LVI.  Ideally, we'd always return Undefined, but
+///   we do not make this guarantee.  TODO: This would be a useful enhancement.
+static LVILatticeVal intersect(LVILatticeVal A, LVILatticeVal B) {
+  // Undefined is the strongest state.  It means the value is known to be along
+  // an unreachable path.
+  if (A.isUndefined())
+    return A;
+  if (B.isUndefined())
+    return B;
+
+  // If we gave up for one, but got a useable fact from the other, use it.
+  if (A.isOverdefined())
+    return B;
+  if (B.isOverdefined())
+    return A;
+
+  // Can't get any more precise than constants.
+  if (hasSingleValue(A))
+    return A;
+  if (hasSingleValue(B))
+    return B;
+
+  // Could be either constant range or not constant here.
+  if (!A.isConstantRange() || !B.isConstantRange()) {
+    // TODO: Arbitrary choice, could be improved
+    return A;
+  }
+
+  // Intersect two constant ranges
+  ConstantRange Range =
+    A.getConstantRange().intersectWith(B.getConstantRange());
+  // Note: An empty range is implicitly converted to overdefined internally.
+  // TODO: We could instead use Undefined here since we've proven a conflict
+  // and thus know this path must be unreachable. 
+  return LVILatticeVal::getRange(Range);
+}
+
 /// \brief Compute the value of Val on the edge BBFrom -> BBTo or the value at
 /// the basic block if the edge does not constrain Val.
 bool LazyValueInfoCache::getEdgeValue(Value *Val, BasicBlock *BBFrom,
@@ -1051,46 +1119,29 @@
     return true;
   }
 
-  if (getEdgeValueLocal(Val, BBFrom, BBTo, Result)) {
-    if (!Result.isConstantRange() ||
-        Result.getConstantRange().getSingleElement())
-      return true;
-
-    // FIXME: this check should be moved to the beginning of the function when
-    // LVI better supports recursive values. Even for the single value case, we
-    // can intersect to detect dead code (an empty range).
-    if (!hasBlockValue(Val, BBFrom)) {
-      if (pushBlockValue(std::make_pair(BBFrom, Val)))
-        return false;
-      Result.markOverdefined();
-      return true;
-    }
-
-    // Try to intersect ranges of the BB and the constraint on the edge.
-    LVILatticeVal InBlock = getBlockValue(Val, BBFrom);
-    mergeAssumeBlockValueConstantRange(Val, InBlock, BBFrom->getTerminator());
-    // See note on the use of the CxtI with mergeAssumeBlockValueConstantRange,
-    // and caching, below.
-    mergeAssumeBlockValueConstantRange(Val, InBlock, CxtI);
-    if (!InBlock.isConstantRange())
-      return true;
-
-    ConstantRange Range =
-      Result.getConstantRange().intersectWith(InBlock.getConstantRange());
-    Result = LVILatticeVal::getRange(Range);
+  LVILatticeVal LocalResult;
+  if (!getEdgeValueLocal(Val, BBFrom, BBTo, LocalResult))
+    // If we couldn't constrain the value on the edge, LocalResult doesn't
+    // provide any information.
+    LocalResult.markOverdefined();
+  
+  if (hasSingleValue(LocalResult)) {
+    // Can't get any more precise here
+    Result = LocalResult;
     return true;
   }
 
   if (!hasBlockValue(Val, BBFrom)) {
     if (pushBlockValue(std::make_pair(BBFrom, Val)))
       return false;
-    Result.markOverdefined();
+    // No new information.
+    Result = LocalResult;
     return true;
   }
 
-  // If we couldn't compute the value on the edge, use the value from the BB.
-  Result = getBlockValue(Val, BBFrom);
-  mergeAssumeBlockValueConstantRange(Val, Result, BBFrom->getTerminator());
+  // Try to intersect ranges of the BB and the constraint on the edge.
+  LVILatticeVal InBlock = getBlockValue(Val, BBFrom);
+  mergeAssumeBlockValueConstantRange(Val, InBlock, BBFrom->getTerminator());
   // We can use the context instruction (generically the ultimate instruction
   // the calling pass is trying to simplify) here, even though the result of
   // this function is generally cached when called from the solve* functions
@@ -1099,7 +1150,9 @@
   // functions, the context instruction is not provided. When called from
   // LazyValueInfoCache::getValueOnEdge, the context instruction is provided,
   // but then the result is not cached.
-  mergeAssumeBlockValueConstantRange(Val, Result, CxtI);
+  mergeAssumeBlockValueConstantRange(Val, InBlock, CxtI);
+
+  Result = intersect(LocalResult, InBlock);
   return true;
 }
 
Index: llvm/trunk/test/Transforms/CorrelatedValuePropagation/conflict.ll
===================================================================
--- llvm/trunk/test/Transforms/CorrelatedValuePropagation/conflict.ll
+++ llvm/trunk/test/Transforms/CorrelatedValuePropagation/conflict.ll
@@ -0,0 +1,50 @@
+; RUN: opt -correlated-propagation -S < %s | FileCheck %s
+; Checks that we don't crash on conflicting facts about a value 
+; (i.e. unreachable code)
+
+; Test that we can handle conflict edge facts
+define i8 @test(i8 %a) {
+; CHECK-LABEL: @test
+  %cmp1 = icmp eq i8 %a, 5
+  br i1 %cmp1, label %next, label %exit
+next:
+  %cmp2 = icmp eq i8 %a, 3
+; CHECK: br i1 false, label %dead, label %exit
+  br i1 %cmp2, label %dead, label %exit
+dead:
+; CHECK-LABEL: dead:
+; CHECK: ret i8 5
+; NOTE: undef, or 3 would be equal valid
+  ret i8 %a
+exit:
+  ret i8 0
+}
+
+declare void @llvm.assume(i1)
+
+; Test that we can handle conflicting assume vs edge facts
+define i8 @test2(i8 %a) {
+; CHECK-LABEL: @test2
+  %cmp1 = icmp eq i8 %a, 5
+  call void @llvm.assume(i1 %cmp1)
+  %cmp2 = icmp eq i8 %a, 3
+; CHECK: br i1 false, label %dead, label %exit
+  br i1 %cmp2, label %dead, label %exit
+dead:
+  ret i8 %a
+exit:
+  ret i8 0
+}
+
+define i8 @test3(i8 %a) {
+; CHECK-LABEL: @test3
+  %cmp1 = icmp eq i8 %a, 5
+  br i1 %cmp1, label %dead, label %exit
+dead:
+  %cmp2 = icmp eq i8 %a, 3
+; CHECK: call void @llvm.assume(i1 false)
+  call void @llvm.assume(i1 %cmp2)
+  ret i8 %a
+exit:
+  ret i8 0
+}
Index: llvm/trunk/test/Transforms/JumpThreading/induction.ll
===================================================================
--- llvm/trunk/test/Transforms/JumpThreading/induction.ll
+++ llvm/trunk/test/Transforms/JumpThreading/induction.ll
@@ -0,0 +1,25 @@
+; RUN: opt -S -jump-threading < %s | FileCheck %s
+
+define i8 @test(i32 %a, i32 %length) {
+; CHECK-LABEL: @test
+entry:
+; CHECK: br label %backedge
+  br label %loop
+
+loop:
+; CHECK-LABEL: backedge:
+; CHECK: phi i32
+; CHECK: br i1 %cont, label %backedge, label %exit
+  %iv = phi i32 [0, %entry], [%iv.next, %backedge]
+  ;; We can use an inductive argument to prove %iv is always positive
+  %cnd = icmp sge i32 %iv, 0
+  br i1 %cnd, label %backedge, label %exit
+
+backedge:
+  %iv.next = add nsw i32 %iv, 1
+  %cont = icmp slt i32 %iv.next, 400
+  br i1 %cont, label %loop, label %exit
+exit:
+  ret i8 0
+}
+