Index: lib/Analysis/LazyValueInfo.cpp
===================================================================
--- lib/Analysis/LazyValueInfo.cpp
+++ lib/Analysis/LazyValueInfo.cpp
@@ -460,6 +460,9 @@
                            BasicBlock *BB);
   void intersectAssumeBlockValueConstantRange(Value *Val, LVILatticeVal &BBLV,
                                               Instruction *BBI);
+  bool getRecurringEdgeValue(Value *RecurVal, BasicBlock *F, BasicBlock *T,
+                             LVILatticeVal &EdgeResult,
+                             const LVILatticeVal &ResultSoFar, PHINode *PN);
 
   void solve();
 
@@ -809,18 +812,35 @@
 bool LazyValueInfoCache::solveBlockValuePHINode(LVILatticeVal &BBLV,
                                                 PHINode *PN, BasicBlock *BB) {
   LVILatticeVal Result;  // Start Undefined.
+  auto *PNParent = PN->getParent();
+
+  SmallVector<BasicBlock *, 4> Blocks(PN->blocks());
+  if (DT) {
+    // Sort the blocks such that we visit the backedge last
+    std::partition(Blocks.begin(), Blocks.end(),
+                   [this, PNParent](BasicBlock *IncomingBB) {
+                     return !DT->dominates(PNParent, IncomingBB);
+                   });
+  }
 
   // Loop over all of our predecessors, merging what we know from them into
   // result.
   bool EdgesMissing = false;
-  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
-    BasicBlock *PhiBB = PN->getIncomingBlock(i);
-    Value *PhiVal = PN->getIncomingValue(i);
+  for (auto *PhiBB : Blocks) {
+    Value *PhiVal = PN->getIncomingValueForBlock(PhiBB);
     LVILatticeVal EdgeResult;
     // Note that we can provide PN as the context value to getEdgeValue, even
     // though the results will be cached, because PN is the value being used as
     // the cache key in the caller.
-    EdgesMissing |= !getEdgeValue(PhiVal, PhiBB, BB, EdgeResult, PN);
+    if (DT && DT->dominates(PNParent, PhiBB))
+      // Try to calculate a more precise LVILatticeVal on the recurring edge
+      // based on mathematical fix-point. This function will fallback to
+      // getEdgeValue if we cannot handle the edge.
+      // Currently getRecurringEdgeValue only handle a few patterns
+      EdgesMissing |=
+          !getRecurringEdgeValue(PhiVal, PhiBB, BB, EdgeResult, Result, PN);
+    else
+      EdgesMissing |= !getEdgeValue(PhiVal, PhiBB, BB, EdgeResult, PN);
     if (EdgesMissing)
       continue;
 
@@ -1265,6 +1285,105 @@
   return false;
 }
 
+static bool MatchIncreasedByOne(PHINode *PN, Instruction *Update) {
+  return match(Update, m_CombineOr(m_Add(m_One(), m_Specific(PN)),
+                                   m_Add(m_Specific(PN), m_One())));
+}
+
+static bool MatchSelectRecurrence(PHINode *PN, SelectInst *Sel,
+                                  Value *&Incoming) {
+  if (isa<Constant>(Sel->getCondition()))
+    return false;
+
+  if (Sel->getTrueValue() == PN) {
+    Incoming = Sel->getFalseValue();
+    return true;
+  }
+
+  if (Sel->getFalseValue() == PN) {
+    Incoming = Sel->getTrueValue();
+    return true;
+  }
+
+  return false;
+}
+
+/// \brief Compute the value of PHINode recurring edge based on mathematical
+/// fixed-point. Fall back to getEdgeValue if we cannot handle the edge
+/// return false if the edge is missing
+bool LazyValueInfoCache::getRecurringEdgeValue(
+    Value *RecurVal, BasicBlock *BBFrom, BasicBlock *BBTo,
+    LVILatticeVal &EdgeResult, const LVILatticeVal &ResultSoFar, PHINode *PN) {
+  // If already a constant, there is nothing to compute.
+  if (Constant *VC = dyn_cast<Constant>(RecurVal)) {
+    EdgeResult = LVILatticeVal::get(VC);
+    return true;
+  }
+
+  // Only simple PHINode with 1 recurring edge and 1 entry
+  if (PN->getNumIncomingValues() != 2)
+    return getEdgeValue(RecurVal, BBFrom, BBTo, EdgeResult, PN);
+
+  auto *RecurInst = dyn_cast<Instruction>(RecurVal);
+  if (!RecurInst)
+    return getEdgeValue(RecurVal, BBFrom, BBTo, EdgeResult, PN);
+
+  // Skip if the range for initalization is not knwon
+  if (!ResultSoFar.isConstantRange())
+    return getEdgeValue(RecurVal, BBFrom, BBTo, EdgeResult, PN);
+
+  switch (RecurInst->getOpcode()) {
+  default:
+    return getEdgeValue(RecurVal, BBFrom, BBTo, EdgeResult, PN);
+  case Instruction::Add: {
+    // Calculate the local result without poluting the cache, we want to get a
+    // upper bound based on the the branch condition
+    LVILatticeVal LocalResult;
+    if (!getEdgeValueLocal(RecurInst, BBFrom, BBTo, LocalResult))
+      return getEdgeValue(RecurVal, BBFrom, BBTo, EdgeResult, PN);
+
+    if (!LocalResult.isConstantRange() || !MatchIncreasedByOne(PN, RecurInst))
+      return getEdgeValue(RecurVal, BBFrom, BBTo, EdgeResult, PN);
+
+    auto EdgeRange = LocalResult.getConstantRange();
+    auto InitRange = ResultSoFar.getConstantRange();
+    if (!EdgeRange.contains(InitRange))
+      return getEdgeValue(RecurVal, BBFrom, BBTo, EdgeResult, PN);
+
+    // This is correct even if the set wrap around
+    EdgeResult = LVILatticeVal::getRange(
+        ConstantRange(InitRange.getLower(), EdgeRange.getUpper()));
+
+    return true;
+  }
+  case Instruction::Select: {
+    // Handle recurrence with select for linear search pattern:
+    // %tmp86 = phi i32[1, %bb73], [%tmp95, %bb85]
+    // %tmp87 = phi i32[0, %bb73], [%tmp94, %bb85]
+    // %tmp94 = select i1 %tmp91, i32 %tmp86, i32 %tmp87
+    // %tmp95 = add nsw i32 %tmp86, 1
+    // % tmp96 = icmp slt i32 %tmp95, 20
+    // br i1 %tmp96, label %bb85, label %bb97
+    //
+    // In this case, R(%tmp94) = R(%tmp86) U R(%tmp87)
+    // =>  R(%tmp94) = R(%tmp86) U R(%tmp94) U R(0)
+    // =>  R(%tmp94) = R(%tmp86) U R(%tmp86) U R(%tmp87) U R(0)
+    // =>  R(%tmp94) = R(%tmp86) U R(%tmp86) U ... U R(0)
+    //
+
+    Value *Incoming;
+    if (!MatchSelectRecurrence(PN, cast<SelectInst>(RecurInst), Incoming))
+      return getEdgeValue(RecurVal, BBFrom, BBTo, EdgeResult, PN);
+
+    if (!getEdgeValue(Incoming, BBFrom, BBTo, EdgeResult, PN))
+      return false;
+
+    EdgeResult.mergeIn(ResultSoFar, DL);
+    return true;
+  }
+  }
+}
+
 /// \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,
@@ -1455,6 +1574,7 @@
   AU.setPreservesAll();
   AU.addRequired<AssumptionCacheTracker>();
   AU.addRequired<TargetLibraryInfoWrapperPass>();
+  AU.addUsedIfAvailable<DominatorTreeWrapperPass>();
 }
 
 LazyValueInfo &LazyValueInfoWrapperPass::getLVI() { return Info; }