Index: lib/Analysis/LazyValueInfo.cpp
===================================================================
--- lib/Analysis/LazyValueInfo.cpp
+++ lib/Analysis/LazyValueInfo.cpp
@@ -17,6 +17,7 @@
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/ConstantFolding.h"
+#include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/AssemblyAnnotationWriter.h"
@@ -148,6 +149,15 @@
     return Range;
   }
 
+  Optional<APInt> asConstantInteger() const {
+    if (isConstant() && isa<ConstantInt>(Val)) {
+      return Val->getUniqueInteger();
+    } else if (isConstantRange() && Range.isSingleElement()) {
+      return *Range.getSingleElement();
+    }
+    return None;
+  }
+
 private:
   void markOverdefined() {
     if (isOverdefined())
@@ -1355,6 +1365,42 @@
   return getValueFromCondition(Val, Cond, isTrueDest, Visited);
 }
 
+// Return true if Usr has Op as an operand, otherwise false.
+static bool usesOperand(User *Usr, Value *Op) {
+  return find(Usr->operands(), Op) != Usr->op_end();
+}
+
+// Check if Val can be simplified to an integer constant when the value of one
+// of its operands Op is an integer constant OpConstVal. If so, return it as an
+// lattice value range with a single element or otherwise return an overdefined
+// lattice value.
+static LVILatticeVal constantFoldUser(Value *Val, Value *Op,
+                                      const APInt &OpConstVal,
+                                      const DataLayout &DL) {
+  Constant* OpConst = Constant::getIntegerValue(Op->getType(), OpConstVal);
+  // Check if Val can be simplified to a constant.
+  if (auto *CI = dyn_cast<CastInst>(Val)) {
+    assert(CI->getOperand(0) == Op && "Operand 0 isn't Op");
+    if (auto *C = dyn_cast_or_null<ConstantInt>(
+            SimplifyCastInst(CI->getOpcode(), OpConst,
+                             CI->getDestTy(), DL))) {
+      return LVILatticeVal::getRange(ConstantRange(C->getUniqueInteger()));
+    }
+  } else if (auto *BO = dyn_cast<BinaryOperator>(Val)) {
+    bool Op0Match = BO->getOperand(0) == Op;
+    bool Op1Match = BO->getOperand(1) == Op;
+    assert((Op0Match || Op1Match) &&
+           "Operand 0 nor Operand 1 isn't a match");
+    Value *LHS = Op0Match ? OpConst : BO->getOperand(0);
+    Value *RHS = Op1Match ? OpConst : BO->getOperand(1);
+    if (auto *C = dyn_cast_or_null<ConstantInt>(
+            SimplifyBinOp(BO->getOpcode(), LHS, RHS, DL))) {
+      return LVILatticeVal::getRange(ConstantRange(C->getUniqueInteger()));
+    }
+  }
+  return LVILatticeVal::getOverdefined();
+}
+
 /// \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.
@@ -1370,10 +1416,11 @@
       bool isTrueDest = BI->getSuccessor(0) == BBTo;
       assert(BI->getSuccessor(!isTrueDest) == BBTo &&
              "BBTo isn't a successor of BBFrom");
+      Value *Condition = BI->getCondition();
 
       // If V is the condition of the branch itself, then we know exactly what
       // it is.
-      if (BI->getCondition() == Val) {
+      if (Condition == Val) {
         Result = LVILatticeVal::get(ConstantInt::get(
                               Type::getInt1Ty(Val->getContext()), isTrueDest));
         return true;
@@ -1381,7 +1428,44 @@
 
       // If the condition of the branch is an equality comparison, we may be
       // able to infer the value.
-      Result = getValueFromCondition(Val, BI->getCondition(), isTrueDest);
+      Result = getValueFromCondition(Val, Condition, isTrueDest);
+      if (!Result.isOverdefined())
+        return true;
+
+      if (User *Usr = dyn_cast<User>(Val)) {
+        assert(Result.isOverdefined() && "Result isn't overdefined");
+        if (isa<IntegerType>(Val->getType())) {
+          const DataLayout &DL = BBTo->getModule()->getDataLayout();
+          if (usesOperand(Usr, Condition)) {
+            // If Val has Condition as an operand and Val can be folded into a
+            // constant with either Condition == true or Condition == false,
+            // propagate the constant.
+            // eg.
+            //   ; %Val is true on the edge to %then.
+            //   %Val = and i1 %Condition, true.
+            //   br %Condition, label %then, label %else
+            APInt ConditionVal(1, isTrueDest ? 1 : 0);
+            Result = constantFoldUser(Val, Condition, ConditionVal, DL);
+          } else {
+            // If one of Val's operand has an inferred value, we may be able to
+            // infer the value of Val.
+            // eg.
+            //    ; %Val is 94 on the edge to %then.
+            //    %Val = add i8 %Op, 1
+            //    %Condition = icmp eq i8 %Op, 93
+            //    br i1 %Condition, label %then, label %else
+            for (unsigned i = 0; i < Usr->getNumOperands(); ++i) {
+              Value *Op = Usr->getOperand(i);
+              LVILatticeVal OpLatticeVal =
+                  getValueFromCondition(Op, Condition, isTrueDest);
+              if (Optional<APInt> OpConst = OpLatticeVal.asConstantInteger()) {
+                Result = constantFoldUser(Val, Op, OpConst.getValue(), DL);
+                break;
+              }
+            }
+          }
+        }
+      }
       if (!Result.isOverdefined())
         return true;
     }
@@ -1390,19 +1474,43 @@
   // If the edge was formed by a switch on the value, then we may know exactly
   // what it is.
   if (SwitchInst *SI = dyn_cast<SwitchInst>(BBFrom->getTerminator())) {
-    if (SI->getCondition() != Val)
+    Value *Condition = SI->getCondition();
+    if (!isa<IntegerType>(Val->getType()))
       return false;
+    bool ValUsesCondition = false;
+    if (Condition != Val) {
+      // Check if Val has Condition as an operand.
+      if (User *Usr = dyn_cast<User>(Val))
+        ValUsesCondition = usesOperand(Usr, Condition);
+      if (!ValUsesCondition)
+        return false;
+    }
+    assert((Condition == Val || ValUsesCondition) &&
+           "Condition != Val nor Val doesn't use Condition");
 
     bool DefaultCase = SI->getDefaultDest() == BBTo;
     unsigned BitWidth = Val->getType()->getIntegerBitWidth();
     ConstantRange EdgesVals(BitWidth, DefaultCase/*isFullSet*/);
 
     for (auto Case : SI->cases()) {
-      ConstantRange EdgeVal(Case.getCaseValue()->getValue());
+      APInt CaseValue = Case.getCaseValue()->getValue();
+      ConstantRange EdgeVal(CaseValue);
+      if (ValUsesCondition) {
+        const DataLayout &DL = BBTo->getModule()->getDataLayout();
+        LVILatticeVal EdgeLatticeVal =
+            constantFoldUser(Val, Condition, CaseValue, DL);
+        if (EdgeLatticeVal.isOverdefined())
+          return false;
+        EdgeVal = EdgeLatticeVal.getConstantRange();
+      }
       if (DefaultCase) {
         // It is possible that the default destination is the destination of
-        // some cases. There is no need to perform difference for those cases.
-        if (Case.getCaseSuccessor() != BBTo)
+        // some cases. We cannot perform difference for those cases.
+        // We know Condition != CaseValue in BBTo.  In some cases we can use
+        // this to infer Val == f(Condition) is != f(CaseValue).  For now, we
+        // only do this when f is identity (i.e. Val == Condition), but we
+        // should be able to do this for any injective f.
+        if (Case.getCaseSuccessor() != BBTo && Condition == Val)
           EdgesVals = EdgesVals.difference(EdgeVal);
       } else if (Case.getCaseSuccessor() == BBTo)
         EdgesVals = EdgesVals.unionWith(EdgeVal);
Index: test/Transforms/CorrelatedValuePropagation/range.ll
===================================================================
--- test/Transforms/CorrelatedValuePropagation/range.ll
+++ test/Transforms/CorrelatedValuePropagation/range.ll
@@ -462,3 +462,144 @@
 else:
   ret i1 false
 }
+
+define i32 @test16(i8 %a) {
+entry:
+  %b = zext i8 %a to i32
+  br label %dispatch
+
+dispatch:
+  %cmp = icmp eq i8 %a, 93
+  br i1 %cmp, label %target93, label %dispatch
+
+; CHECK-LABEL: @test16(
+; CHECK: target93:
+; CHECK-NEXT: ret i32 93
+target93:
+  ret i32 %b
+}
+
+define i32 @test16_i1(i1 %a) {
+entry:
+  %b = zext i1 %a to i32
+  br label %dispatch
+
+dispatch:
+  br i1 %a, label %true, label %dispatch
+
+; CHECK-LABEL: @test16_i1(
+; CHECK: true:
+; CHECK-NEXT: ret i32 1
+true:
+  ret i32 %b
+}
+
+define i8 @test17(i8 %a) {
+entry:
+  %c = add i8 %a, 3
+  br label %dispatch
+
+dispatch:
+  %cmp = icmp eq i8 %a, 93
+  br i1 %cmp, label %target93, label %dispatch
+
+; CHECK-LABEL: @test17(
+; CHECK: target93:
+; CHECK-NEXT: ret i8 96
+target93:
+  ret i8 %c
+}
+
+define i8 @test17_2(i8 %a) {
+entry:
+  %c = add i8 %a, %a
+  br label %dispatch
+
+dispatch:
+  %cmp = icmp eq i8 %a, 93
+  br i1 %cmp, label %target93, label %dispatch
+
+; CHECK-LABEL: @test17_2(
+; CHECK: target93:
+; CHECK-NEXT: ret i8 -70
+target93:
+  ret i8 %c
+}
+
+define i1 @test17_i1(i1 %a) {
+entry:
+  %c = and i1 %a, true
+  br label %dispatch
+
+dispatch:
+  br i1 %a, label %true, label %dispatch
+
+; CHECK-LABEL: @test17_i1(
+; CHECK: true:
+; CHECK-NEXT: ret i1 true
+true:
+  ret i1 %c
+}
+
+define i32 @test18(i8 %a) {
+entry:
+  %b = zext i8 %a to i32
+  br label %dispatch
+
+dispatch:
+  switch i8 %a, label %dispatch [
+    i8 93, label %target93
+    i8 -111, label %dispatch
+  ]
+
+; CHECK-LABEL: @test18(
+; CHECK: target93:
+; CHECK-NEXT: ret i32 93
+target93:
+  ret i32 %b
+}
+
+define i8 @test19(i8 %a) {
+entry:
+  %c = add i8 %a, 3
+  br label %dispatch
+
+dispatch:
+  switch i8 %a, label %dispatch [
+    i8 93, label %target93
+    i8 -111, label %dispatch
+  ]
+
+; CHECK-LABEL: @test19(
+; CHECK: target93:
+; CHECK-NEXT: ret i8 96
+target93:
+  ret i8 %c
+}
+
+define i1 @test20(i64 %a) {
+entry:
+  %b = and i64 %a, 7
+  br label %dispatch
+
+dispatch:
+  switch i64 %a, label %default [
+    i64 0, label %exit2
+    i64 -2147483647, label %exit2
+  ]
+
+default:
+  %c = icmp eq i64 %b, 0
+  br label %exit
+
+exit:
+; Negative test. Shouldn't be incorrectly optimized to "ret i1 false".
+; CHECK-LABEL: @test20(
+; CHECK: exit:
+; CHECK-NOT: ret i1 false
+; CHECK: exit2:
+  ret i1 %c
+
+exit2:
+  ret i1 false
+}