Index: include/llvm/CodeGen/FunctionLoweringInfo.h
===================================================================
--- include/llvm/CodeGen/FunctionLoweringInfo.h
+++ include/llvm/CodeGen/FunctionLoweringInfo.h
@@ -184,6 +184,9 @@
   /// selection.
   SmallPtrSet<const BasicBlock*, 4> VisitedBBs;
 
+  /// Record PHIs invalidated for computing LiveOutRegInfo.
+  SmallPtrSet<const PHINode *, 4> InvalidatedPHIs;
+
   /// PHINodesToUpdate - A list of phi instructions whose operand list will
   /// be updated after processing the current basic block.
   /// TODO: This isn't per-function state, it's per-basic-block state. But
@@ -263,6 +266,10 @@
   /// register based on the LiveOutInfo of its operands.
   void ComputePHILiveOutRegInfo(const PHINode*);
 
+  /// Try to recompute LiveOutInfo for a PHI which was invalidated before.
+  const LiveOutInfo *tryToRecomputePHILiveOutRegInfo(Value *V,
+                                                     unsigned BitWidth);
+
   /// InvalidatePHILiveOutRegInfo - Invalidates a PHI's LiveOutInfo, to be
   /// called when a block is visited before all of its predecessors.
   void InvalidatePHILiveOutRegInfo(const PHINode *PN) {
Index: lib/CodeGen/SelectionDAG/FunctionLoweringInfo.cpp
===================================================================
--- lib/CodeGen/SelectionDAG/FunctionLoweringInfo.cpp
+++ lib/CodeGen/SelectionDAG/FunctionLoweringInfo.cpp
@@ -409,6 +409,29 @@
   return LOI;
 }
 
+/// Try to recompute LiveOutRegInfo for an invalidated PHI when it's referred as
+/// an input value in a later block if its predecessors are all visited at that
+/// point.
+const FunctionLoweringInfo::LiveOutInfo *
+FunctionLoweringInfo::tryToRecomputePHILiveOutRegInfo(Value *V,
+                                                      unsigned BitWidth) {
+  PHINode *Phi = dyn_cast<PHINode>(V);
+  if (!Phi || !InvalidatedPHIs.count(Phi))
+    return nullptr;
+
+  const BasicBlock *LLVMBB = Phi->getParent();
+  for (const_pred_iterator PI = pred_begin(LLVMBB), PE = pred_end(LLVMBB);
+       PI != PE; ++PI) {
+    if (!VisitedBBs.count(*PI) || MBBMap[*PI] == MBB)
+      return nullptr;
+  }
+  // If all predecessors are visited, retry to compute LiveOutRegInfo.
+  unsigned SrcReg = ValueMap[Phi];
+  InvalidatedPHIs.erase(Phi);
+  ComputePHILiveOutRegInfo(Phi);
+  return GetLiveOutRegInfo(SrcReg, BitWidth);
+}
+
 /// ComputePHILiveOutRegInfo - Compute LiveOutInfo for a PHI's destination
 /// register based on the LiveOutInfo of its operands.
 void FunctionLoweringInfo::ComputePHILiveOutRegInfo(const PHINode *PN) {
@@ -457,8 +480,10 @@
     }
     const LiveOutInfo *SrcLOI = GetLiveOutRegInfo(SrcReg, BitWidth);
     if (!SrcLOI) {
-      DestLOI.IsValid = false;
-      return;
+      if (!(SrcLOI = tryToRecomputePHILiveOutRegInfo(V, BitWidth))) {
+        DestLOI.IsValid = false;
+        return;
+      }
     }
     DestLOI = *SrcLOI;
   }
@@ -494,8 +519,10 @@
     }
     const LiveOutInfo *SrcLOI = GetLiveOutRegInfo(SrcReg, BitWidth);
     if (!SrcLOI) {
-      DestLOI.IsValid = false;
-      return;
+      if (!(SrcLOI = tryToRecomputePHILiveOutRegInfo(V, BitWidth))) {
+        DestLOI.IsValid = false;
+        return;
+      }
     }
     DestLOI.NumSignBits = std::min(DestLOI.NumSignBits, SrcLOI->NumSignBits);
     DestLOI.KnownZero &= SrcLOI->KnownZero;
Index: lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
===================================================================
--- lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
+++ lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
@@ -1505,6 +1505,7 @@
 
   // Iterate over all basic blocks in the function.
   for (const BasicBlock *LLVMBB : RPOT) {
+    FuncInfo->MBB = FuncInfo->MBBMap[LLVMBB];
     if (OptLevel != CodeGenOpt::None) {
       bool AllPredsVisited = true;
       for (const_pred_iterator PI = pred_begin(LLVMBB), PE = pred_end(LLVMBB);
@@ -1521,8 +1522,10 @@
           FuncInfo->ComputePHILiveOutRegInfo(PN);
       } else {
         for (BasicBlock::const_iterator I = LLVMBB->begin();
-             const PHINode *PN = dyn_cast<PHINode>(I); ++I)
+             const PHINode *PN = dyn_cast<PHINode>(I); ++I) {
           FuncInfo->InvalidatePHILiveOutRegInfo(PN);
+          FuncInfo->InvalidatedPHIs.insert(PN);
+        }
       }
 
       FuncInfo->VisitedBBs.insert(LLVMBB);
@@ -1533,7 +1536,6 @@
     BasicBlock::const_iterator const End = LLVMBB->end();
     BasicBlock::const_iterator BI = End;
 
-    FuncInfo->MBB = FuncInfo->MBBMap[LLVMBB];
     if (!FuncInfo->MBB)
       continue; // Some blocks like catchpads have no code or MBB.