Index: lib/Analysis/LazyValueInfo.cpp
===================================================================
--- lib/Analysis/LazyValueInfo.cpp
+++ lib/Analysis/LazyValueInfo.cpp
@@ -1155,10 +1155,23 @@
         << BB->getName() << "'\n");
 
   assert(BlockValueStack.empty() && BlockValueSet.empty());
-  if (!hasBlockValue(V, BB)) {
-    pushBlockValue(std::make_pair(BB, V)); 
-    solve();
-  }
+
+  if (!hasBlockValue(V, BB))
+    // To detect cyles, we only ever push any particular item on the stack at
+    // most once.  This bit of code is essentially special casing the item
+    // being queried so that it can be visited twice rather than once while
+    // still preventing infinite recursion.  The motivation here is that the
+    // value may have locally obvious facts (due to edge constraints on phis,
+    // or nsw flags for instance), that we want to be able to exploit before
+    // giving up.  In practice, this gives us substaintially more precise
+    // results when analyzing induction variables in loops and enables us to
+    // prove many inductive invariants.
+    if (!solveBlockValue(V, BB)) {
+      solve();
+      bool WasFastQuery = solveBlockValue(V, BB);
+      (void)WasFastQuery;
+      assert(WasFastQuery && "More work to do after problem solved?");
+    }
   LVILatticeVal Result = getBlockValue(V, BB);
   intersectAssumeBlockValueConstantRange(V, Result, CxtI);
 
@@ -1173,9 +1186,13 @@
   if (auto *C = dyn_cast<Constant>(V))
     return LVILatticeVal::get(C);
 
-  LVILatticeVal Result = LVILatticeVal::getOverdefined();
+  // Since the end of the block post-dominates instructions within it, we can
+  // use the value at the end of the block to infer facts about instructions
+  // both within the block and dominating the block.  Note that the context
+  // instruction may contribute facts known part way through the block.
+  LVILatticeVal Result = getValueInBlock(V, CxtI->getParent(), CxtI);
   if (auto *I = dyn_cast<Instruction>(V))
-    Result = getFromRangeMetadata(I);
+    Result = intersect(Result, getFromRangeMetadata(I));
   intersectAssumeBlockValueConstantRange(V, Result, CxtI);
 
   DEBUG(dbgs() << "  Result = " << Result << "\n");
Index: test/Transforms/JumpThreading/induction.ll
===================================================================
--- test/Transforms/JumpThreading/induction.ll
+++ test/Transforms/JumpThreading/induction.ll
@@ -23,3 +23,73 @@
   ret i8 0
 }
 
+;; Same as above, but without the nsw to act as a crutch
+define i8 @test2(i32 %a, i32 %length) {
+; CHECK-LABEL: @test2
+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 i32 %iv, 1
+  %cont = icmp slt i32 %iv.next, 400
+  br i1 %cont, label %loop, label %exit
+exit:
+  ret i8 0
+}
+
+define i8 @test3(i32 %a, i32 %length) {
+; CHECK-LABEL: @test3
+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 [1, %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 = shl i32 %iv, 1
+  %cont = icmp slt i32 %iv.next, 400
+  br i1 %cont, label %loop, label %exit
+exit:
+  ret i8 0
+}
+
+define i8 @test4(i32 %a, i32 %length) {
+; CHECK-LABEL: @test4
+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 [1, %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 = mul i32 %iv, 3
+  %cont = icmp slt i32 %iv.next, 400
+  br i1 %cont, label %loop, label %exit
+exit:
+  ret i8 0
+}
+