Index: llvm/trunk/lib/Analysis/LazyValueInfo.cpp
===================================================================
--- llvm/trunk/lib/Analysis/LazyValueInfo.cpp
+++ llvm/trunk/lib/Analysis/LazyValueInfo.cpp
@@ -1197,30 +1197,47 @@
         Result = LVILatticeVal::getNot(cast<Constant>(RHS));
       return true;
     }
+  }
 
-    // Recognize the range checking idiom that InstCombine produces.
-    // (X+C1) u< C2 --> [-C1, C2-C1)
-    ConstantInt *Offset = nullptr;
-    if (Predicate == ICmpInst::ICMP_ULT)
-      match(LHS, m_Add(m_Specific(Val), m_ConstantInt(Offset)));
-
-    ConstantInt *CI = dyn_cast<ConstantInt>(RHS);
-    if (CI && (LHS == Val || Offset)) {
-      // Calculate the range of values that are allowed by the comparison
-      ConstantRange CmpRange(CI->getValue());
-
-      // If we're interested in the false dest, invert the condition
-      CmpInst::Predicate Pred =
-          isTrueDest ? Predicate : CmpInst::getInversePredicate(Predicate);
-      ConstantRange TrueValues =
-          ConstantRange::makeAllowedICmpRegion(Pred, CmpRange);
+  if (!Val->getType()->isIntegerTy())
+    return false;
 
-      if (Offset) // Apply the offset from above.
-        TrueValues = TrueValues.subtract(Offset->getValue());
+  // Use ConstantRange::makeAllowedICmpRegion in order to determine the possible
+  // range of Val guaranteed by the condition. Recognize comparisons in the from
+  // of:
+  //  icmp <pred> Val, ...
+  //  icmp ult (add Val, Offset), ...
+  // The latter is the range checking idiom that InstCombine produces. Subtract
+  // the offset from the allowed range for RHS in this case.
+
+  // Val or (add Val, Offset) can be on either hand of the comparison
+  if (LHS != Val && !match(LHS, m_Add(m_Specific(Val), m_ConstantInt()))) {
+    std::swap(LHS, RHS);
+    Predicate = CmpInst::getSwappedPredicate(Predicate);
+  }
+
+  ConstantInt *Offset = nullptr;
+  if (Predicate == ICmpInst::ICMP_ULT)
+    match(LHS, m_Add(m_Specific(Val), m_ConstantInt(Offset)));
+
+  if (LHS == Val || Offset) {
+    // Calculate the range of values that are allowed by the comparison
+    ConstantRange RHSRange(RHS->getType()->getIntegerBitWidth(),
+                           /*isFullSet=*/true);
+    if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS))
+      RHSRange = ConstantRange(CI->getValue());
+
+    // If we're interested in the false dest, invert the condition
+    CmpInst::Predicate Pred =
+            isTrueDest ? Predicate : CmpInst::getInversePredicate(Predicate);
+    ConstantRange TrueValues =
+            ConstantRange::makeAllowedICmpRegion(Pred, RHSRange);
 
-      Result = LVILatticeVal::getRange(std::move(TrueValues));
-      return true;
-    }
+    if (Offset) // Apply the offset from above.
+      TrueValues = TrueValues.subtract(Offset->getValue());
+
+    Result = LVILatticeVal::getRange(std::move(TrueValues));
+    return true;
   }
 
   return false;
Index: llvm/trunk/test/Transforms/CorrelatedValuePropagation/range.ll
===================================================================
--- llvm/trunk/test/Transforms/CorrelatedValuePropagation/range.ll
+++ llvm/trunk/test/Transforms/CorrelatedValuePropagation/range.ll
@@ -203,3 +203,115 @@
 next:
   ret i1 %test
 }
+
+define i32 @test12(i32 %a, i32 %b) {
+; CHECK-LABEL: @test12(
+; CHECK: then:
+; CHECK-NEXT: br i1 false, label %end, label %else
+  %cmp = icmp ult i32 %a, %b
+  br i1 %cmp, label %then, label %else
+
+then:
+  %dead = icmp eq i32 %a, -1
+  br i1 %dead, label %end, label %else
+
+else:
+  ret i32 1
+
+end:
+  ret i32 2
+}
+
+define i32 @test12_swap(i32 %a, i32 %b) {
+; CHECK-LABEL: @test12_swap(
+; CHECK: then:
+; CHECK-NEXT: br i1 false, label %end, label %else
+  %cmp = icmp ugt i32 %b, %a
+  br i1 %cmp, label %then, label %else
+
+then:
+  %dead = icmp eq i32 %a, -1
+  br i1 %dead, label %end, label %else
+
+else:
+  ret i32 1
+
+end:
+  ret i32 2
+}
+
+define i32 @test12_neg(i32 %a, i32 %b) {
+; The same as @test12 but the second check is on the false path
+; CHECK-LABEL: @test12_neg(
+; CHECK: else:
+; CHECK-NEXT: %alive = icmp eq i32 %a, -1
+  %cmp = icmp ult i32 %a, %b
+  br i1 %cmp, label %then, label %else
+
+else:
+  %alive = icmp eq i32 %a, -1
+  br i1 %alive, label %end, label %then
+
+then:
+  ret i32 1
+
+end:
+  ret i32 2
+}
+
+define i32 @test12_signed(i32 %a, i32 %b) {
+; The same as @test12 but with signed comparison
+; CHECK-LABEL: @test12_signed(
+; CHECK: then:
+; CHECK-NEXT: br i1 false, label %end, label %else
+  %cmp = icmp slt i32 %a, %b
+  br i1 %cmp, label %then, label %else
+
+then:
+  %dead = icmp eq i32 %a, 2147483647
+  br i1 %dead, label %end, label %else
+
+else:
+  ret i32 1
+
+end:
+  ret i32 2
+}
+
+define i32 @test13(i32 %a, i32 %b) {
+; CHECK-LABEL: @test13(
+; CHECK: then:
+; CHECK-NEXT: br i1 false, label %end, label %else
+  %a.off = add i32 %a, -8
+  %cmp = icmp ult i32 %a.off, %b
+  br i1 %cmp, label %then, label %else
+
+then:
+  %dead = icmp eq i32 %a, 7
+  br i1 %dead, label %end, label %else
+
+else:
+  ret i32 1
+
+end:
+  ret i32 2
+}
+
+define i32 @test13_swap(i32 %a, i32 %b) {
+; CHECK-LABEL: @test13_swap(
+; CHECK: then:
+; CHECK-NEXT: br i1 false, label %end, label %else
+  %a.off = add i32 %a, -8
+  %cmp = icmp ugt i32 %b, %a.off
+  br i1 %cmp, label %then, label %else
+
+then:
+  %dead = icmp eq i32 %a, 7
+  br i1 %dead, label %end, label %else
+
+else:
+  ret i32 1
+
+end:
+  ret i32 2
+}