Extract live range calculations from SplitKit.

SplitKit will soon need two copies of these data structures, and the
algorithms will also be useful when LiveIntervalAnalysis becomes
independent of LiveVariables.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139572 91177308-0d34-0410-b5e6-96231b3b80d8

5 files changed, 516 insertions, 306 deletions

diff --git a/lib/CodeGen/CMakeLists.txt b/lib/CodeGen/CMakeLists.txt
index af0f7f530c..06fc3f3277 100644
--- a/lib/CodeGen/CMakeLists.txt
+++ b/lib/CodeGen/CMakeLists.txt
@@ -30,6 +30,7 @@ add_llvm_library(LLVMCodeGen
   LiveIntervalUnion.cpp
   LiveStackAnalysis.cpp
   LiveVariables.cpp
+  LiveRangeCalc.cpp
   LiveRangeEdit.cpp
   LocalStackSlotAllocation.cpp
   LowerSubregs.cpp
diff --git a/lib/CodeGen/LiveRangeCalc.cpp b/lib/CodeGen/LiveRangeCalc.cpp
new file mode 100644
index 0000000000..21eaa15d01
--- /dev/null
+++ b/lib/CodeGen/LiveRangeCalc.cpp
@@ -0,0 +1,271 @@
+//===---- LiveRangeCalc.cpp - Calculate live ranges -----------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Implementation of the LiveRangeCalc class.
+//
+//===----------------------------------------------------------------------===//
+
+#define DEBUG_TYPE "regalloc"
+#include "LiveRangeCalc.h"
+#include "llvm/CodeGen/MachineDominators.h"
+
+using namespace llvm;
+
+void LiveRangeCalc::reset(const MachineFunction *MF) {
+  unsigned N = MF->getNumBlockIDs();
+  Seen.clear();
+  Seen.resize(N);
+  LiveOut.resize(N);
+  LiveIn.clear();
+}
+
+
+// Transfer information from the LiveIn vector to the live ranges.
+void LiveRangeCalc::updateLiveIns(VNInfo *OverrideVNI, SlotIndexes *Indexes) {
+  for (SmallVectorImpl<LiveInBlock>::iterator I = LiveIn.begin(),
+         E = LiveIn.end(); I != E; ++I) {
+    if (!I->DomNode)
+      continue;
+    MachineBasicBlock *MBB = I->DomNode->getBlock();
+
+    VNInfo *VNI = OverrideVNI ? OverrideVNI : I->Value;
+    assert(VNI && "No live-in value found");
+
+    SlotIndex Start, End;
+    tie(Start, End) = Indexes->getMBBRange(MBB);
+
+    if (I->Kill.isValid())
+      I->LI->addRange(LiveRange(Start, I->Kill, VNI));
+    else {
+      I->LI->addRange(LiveRange(Start, End, VNI));
+      // The value is live-through, update LiveOut as well.  Defer the Domtree
+      // lookup until it is needed.
+      assert(Seen.test(MBB->getNumber()));
+      LiveOut[MBB] = LiveOutPair(VNI, 0);
+    }
+  }
+  LiveIn.clear();
+}
+
+
+void LiveRangeCalc::extend(LiveInterval *LI,
+                           SlotIndex Kill,
+                           SlotIndexes *Indexes,
+                           MachineDominatorTree *DomTree,
+                           VNInfo::Allocator *Alloc) {
+  assert(LI && "Missing live range");
+  assert(Kill.isValid() && "Invalid SlotIndex");
+  assert(Indexes && "Missing SlotIndexes");
+  assert(DomTree && "Missing dominator tree");
+  SlotIndex LastUse = Kill.getPrevSlot();
+
+  MachineBasicBlock *KillMBB = Indexes->getMBBFromIndex(LastUse);
+  assert(Kill && "No MBB at Kill");
+
+  // Is there a def in the same MBB we can extend?
+  if (LI->extendInBlock(Indexes->getMBBStartIdx(KillMBB), LastUse))
+    return;
+
+  // Find the single reaching def, or determine if Kill is jointly dominated by
+  // multiple values, and we may need to create even more phi-defs to preserve
+  // VNInfo SSA form.  Perform a search for all predecessor blocks where we
+  // know the dominating VNInfo.
+  VNInfo *VNI = findReachingDefs(LI, KillMBB, Kill, Indexes, DomTree);
+
+  // When there were multiple different values, we may need new PHIs.
+  if (!VNI)
+    updateSSA(Indexes, DomTree, Alloc);
+
+  updateLiveIns(VNI, Indexes);
+}
+
+
+// This function is called by a client after using the low-level API to add
+// live-out and live-in blocks.  The unique value optimization is not
+// available, SplitEditor::transferValues handles that case directly anyway.
+void LiveRangeCalc::calculateValues(SlotIndexes *Indexes,
+                                    MachineDominatorTree *DomTree,
+                                    VNInfo::Allocator *Alloc) {
+  assert(Indexes && "Missing SlotIndexes");
+  assert(DomTree && "Missing dominator tree");
+  updateSSA(Indexes, DomTree, Alloc);
+  updateLiveIns(0, Indexes);
+}
+
+
+VNInfo *LiveRangeCalc::findReachingDefs(LiveInterval *LI,
+                                        MachineBasicBlock *KillMBB,
+                                        SlotIndex Kill,
+                                        SlotIndexes *Indexes,
+                                        MachineDominatorTree *DomTree) {
+  // Blocks where LI should be live-in.
+  SmallVector<MachineBasicBlock*, 16> WorkList(1, KillMBB);
+
+  // Remember if we have seen more than one value.
+  bool UniqueVNI = true;
+  VNInfo *TheVNI = 0;
+
+  // Using Seen as a visited set, perform a BFS for all reaching defs.
+  for (unsigned i = 0; i != WorkList.size(); ++i) {
+    MachineBasicBlock *MBB = WorkList[i];
+    assert(!MBB->pred_empty() && "Value live-in to entry block?");
+    for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
+           PE = MBB->pred_end(); PI != PE; ++PI) {
+       MachineBasicBlock *Pred = *PI;
+
+       // Is this a known live-out block?
+       if (Seen.test(Pred->getNumber())) {
+         if (VNInfo *VNI = LiveOut[Pred].first) {
+           if (TheVNI && TheVNI != VNI)
+             UniqueVNI = false;
+           TheVNI = VNI;
+         }
+         continue;
+       }
+
+       SlotIndex Start, End;
+       tie(Start, End) = Indexes->getMBBRange(Pred);
+
+       // First time we see Pred.  Try to determine the live-out value, but set
+       // it as null if Pred is live-through with an unknown value.
+       VNInfo *VNI = LI->extendInBlock(Start, End.getPrevSlot());
+       setLiveOutValue(Pred, VNI);
+       if (VNI) {
+         if (TheVNI && TheVNI != VNI)
+           UniqueVNI = false;
+         TheVNI = VNI;
+         continue;
+       }
+
+       // No, we need a live-in value for Pred as well
+       if (Pred != KillMBB)
+          WorkList.push_back(Pred);
+       else
+          // Loopback to KillMBB, so value is really live through.
+         Kill = SlotIndex();
+    }
+  }
+
+  // Transfer WorkList to LiveInBlocks in reverse order.
+  // This ordering works best with updateSSA().
+  LiveIn.clear();
+  LiveIn.reserve(WorkList.size());
+  while(!WorkList.empty())
+    addLiveInBlock(LI, DomTree->getNode(WorkList.pop_back_val()));
+
+  // The kill block may not be live-through.
+  assert(LiveIn.back().DomNode->getBlock() == KillMBB);
+  LiveIn.back().Kill = Kill;
+
+  return UniqueVNI ? TheVNI : 0;
+}
+
+
+// This is essentially the same iterative algorithm that SSAUpdater uses,
+// except we already have a dominator tree, so we don't have to recompute it.
+void LiveRangeCalc::updateSSA(SlotIndexes *Indexes,
+                              MachineDominatorTree *DomTree,
+                              VNInfo::Allocator *Alloc) {
+  assert(Indexes && "Missing SlotIndexes");
+  assert(DomTree && "Missing dominator tree");
+
+  // Interate until convergence.
+  unsigned Changes;
+  do {
+    Changes = 0;
+    // Propagate live-out values down the dominator tree, inserting phi-defs
+    // when necessary.
+    for (SmallVectorImpl<LiveInBlock>::iterator I = LiveIn.begin(),
+           E = LiveIn.end(); I != E; ++I) {
+      MachineDomTreeNode *Node = I->DomNode;
+      // Skip block if the live-in value has already been determined.
+      if (!Node)
+        continue;
+      MachineBasicBlock *MBB = Node->getBlock();
+      MachineDomTreeNode *IDom = Node->getIDom();
+      LiveOutPair IDomValue;
+
+      // We need a live-in value to a block with no immediate dominator?
+      // This is probably an unreachable block that has survived somehow.
+      bool needPHI = !IDom || !Seen.test(IDom->getBlock()->getNumber());
+
+      // IDom dominates all of our predecessors, but it may not be their
+      // immediate dominator. Check if any of them have live-out values that are
+      // properly dominated by IDom. If so, we need a phi-def here.
+      if (!needPHI) {
+        IDomValue = LiveOut[IDom->getBlock()];
+
+        // Cache the DomTree node that defined the value.
+        if (IDomValue.first && !IDomValue.second)
+          LiveOut[IDom->getBlock()].second = IDomValue.second =
+            DomTree->getNode(Indexes->getMBBFromIndex(IDomValue.first->def));
+
+        for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
+               PE = MBB->pred_end(); PI != PE; ++PI) {
+          LiveOutPair &Value = LiveOut[*PI];
+          if (!Value.first || Value.first == IDomValue.first)
+            continue;
+
+          // Cache the DomTree node that defined the value.
+          if (!Value.second)
+            Value.second =
+              DomTree->getNode(Indexes->getMBBFromIndex(Value.first->def));
+
+          // This predecessor is carrying something other than IDomValue.
+          // It could be because IDomValue hasn't propagated yet, or it could be
+          // because MBB is in the dominance frontier of that value.
+          if (DomTree->dominates(IDom, Value.second)) {
+            needPHI = true;
+            break;
+          }
+        }
+      }
+
+      // The value may be live-through even if Kill is set, as can happen when
+      // we are called from extendRange. In that case LiveOutSeen is true, and
+      // LiveOut indicates a foreign or missing value.
+      LiveOutPair &LOP = LiveOut[MBB];
+
+      // Create a phi-def if required.
+      if (needPHI) {
+        ++Changes;
+        assert(Alloc && "Need VNInfo allocator to create PHI-defs");
+        SlotIndex Start, End;
+        tie(Start, End) = Indexes->getMBBRange(MBB);
+        VNInfo *VNI = I->LI->getNextValue(Start, 0, *Alloc);
+        VNI->setIsPHIDef(true);
+        I->Value = VNI;
+        // This block is done, we know the final value.
+        I->DomNode = 0;
+
+        // Add liveness since updateLiveIns now skips this node.
+        if (I->Kill.isValid())
+          I->LI->addRange(LiveRange(Start, I->Kill, VNI));
+        else {
+          I->LI->addRange(LiveRange(Start, End, VNI));
+          LOP = LiveOutPair(VNI, Node);
+        }
+      } else if (IDomValue.first) {
+        // No phi-def here. Remember incoming value.
+        I->Value = IDomValue.first;
+
+        // If the IDomValue is killed in the block, don't propagate through.
+        if (I->Kill.isValid())
+          continue;
+
+        // Propagate IDomValue if it isn't killed:
+        // MBB is live-out and doesn't define its own value.
+        if (LOP.first == IDomValue.first)
+          continue;
+        ++Changes;
+        LOP = IDomValue;
+      }
+    }
+  } while (Changes);
+}
diff --git a/lib/CodeGen/LiveRangeCalc.h b/lib/CodeGen/LiveRangeCalc.h
new file mode 100644
index 0000000000..55e67bb144
--- /dev/null
+++ b/lib/CodeGen/LiveRangeCalc.h
@@ -0,0 +1,226 @@
+//===---- LiveRangeCalc.h - Calculate live ranges ---------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// The LiveRangeCalc class can be used to compute live ranges from scratch.  It
+// caches information about values in the CFG to speed up repeated operations
+// on the same live range.  The cache can be shared by non-overlapping live
+// ranges.  SplitKit uses that when computing the live range of split products.
+//
+// A low-level interface is available to clients that know where a variable is
+// live, but don't know which value it has as every point.  LiveRangeCalc will
+// propagate values down the dominator tree, and even insert PHI-defs where
+// needed.  SplitKit uses this faster interface when possible.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CODEGEN_LIVERANGECALC_H
+#define LLVM_CODEGEN_LIVERANGECALC_H
+
+#include "llvm/ADT/BitVector.h"
+#include "llvm/ADT/IndexedMap.h"
+#include "llvm/CodeGen/LiveInterval.h"
+
+namespace llvm {
+
+/// Forward declarations for MachineDominators.h:
+class MachineDominatorTree;
+template <class NodeT> class DomTreeNodeBase;
+typedef DomTreeNodeBase<MachineBasicBlock> MachineDomTreeNode;
+
+class LiveRangeCalc {
+  /// Seen - Bit vector of active entries in LiveOut, also used as a visited
+  /// set by findReachingDefs.  One entry per basic block, indexed by block
+  /// number.  This is kept as a separate bit vector because it can be cleared
+  /// quickly when switching live ranges.
+  BitVector Seen;
+
+  /// LiveOutPair - A value and the block that defined it.  The domtree node is
+  /// redundant, it can be computed as: MDT[Indexes.getMBBFromIndex(VNI->def)].
+  typedef std::pair<VNInfo*, MachineDomTreeNode*> LiveOutPair;
+
+  /// LiveOutMap - Map basic blocks to the value leaving the block.
+  typedef IndexedMap<LiveOutPair, MBB2NumberFunctor> LiveOutMap;
+
+  /// LiveOut - Map each basic block where a live range is live out to the
+  /// live-out value and its defining block.
+  ///
+  /// For every basic block, MBB, one of these conditions shall be true:
+  ///
+  ///  1. !Seen.count(MBB->getNumber())
+  ///     Blocks without a Seen bit are ignored.
+  ///  2. LiveOut[MBB].second.getNode() == MBB
+  ///     The live-out value is defined in MBB.
+  ///  3. forall P in preds(MBB): LiveOut[P] == LiveOut[MBB]
+  ///     The live-out value passses through MBB. All predecessors must carry
+  ///     the same value.
+  ///
+  /// The domtree node may be null, it can be computed.
+  ///
+  /// The map can be shared by multiple live ranges as long as no two are
+  /// live-out of the same block.
+  LiveOutMap LiveOut;
+
+  /// LiveInBlock - Information about a basic block where a live range is known
+  /// to be live-in, but the value has not yet been determined.
+  struct LiveInBlock {
+    // LI - The live range that is live-in to this block.  The algorithms can
+    // handle multiple non-overlapping live ranges simultaneously.
+    LiveInterval *LI;
+
+    // DomNode - Dominator tree node for the block.
+    // Cleared when the final value has been determined and LI has been updated.
+    MachineDomTreeNode *DomNode;
+
+    // Position in block where the live-in range ends, or SlotIndex() if the
+    // range passes through the block.  When the final value has been
+    // determined, the range from the block start to Kill will be added to LI.
+    SlotIndex Kill;
+
+    // Live-in value filled in by updateSSA once it is known.
+    VNInfo *Value;
+
+    LiveInBlock(LiveInterval *li, MachineDomTreeNode *node, SlotIndex kill)
+      : LI(li), DomNode(node), Kill(kill), Value(0) {}
+  };
+
+  /// LiveIn - Work list of blocks where the live-in value has yet to be
+  /// determined.  This list is typically computed by findReachingDefs() and
+  /// used as a work list by updateSSA().  The low-level interface may also be
+  /// used to add entries directly.
+  SmallVector<LiveInBlock, 16> LiveIn;
+
+  /// findReachingDefs - Assuming that LI is live-in to KillMBB and killed at
+  /// Kill, search for values that can reach KillMBB.  All blocks that need LI
+  /// to be live-in are added to LiveIn.  If a unique reaching def is found,
+  /// its value is returned, if Kill is jointly dominated by multiple values,
+  /// NULL is returned.
+  VNInfo *findReachingDefs(LiveInterval *LI,
+                           MachineBasicBlock *KillMBB,
+                           SlotIndex Kill,
+                           SlotIndexes *Indexes,
+                           MachineDominatorTree *DomTree);
+
+  /// updateSSA - Compute the values that will be live in to all requested
+  /// blocks in LiveIn.  Create PHI-def values as required to preserve SSA form.
+  ///
+  /// Every live-in block must be jointly dominated by the added live-out
+  /// blocks.  No values are read from the live ranges.
+  void updateSSA(SlotIndexes *Indexes,
+                 MachineDominatorTree *DomTree,
+                 VNInfo::Allocator *Alloc);
+
+  /// updateLiveIns - Add liveness as specified in the LiveIn vector, using VNI
+  /// as a wildcard value for LiveIn entries without a value.
+  void updateLiveIns(VNInfo *VNI, SlotIndexes*);
+
+public:
+  //===--------------------------------------------------------------------===//
+  // High-level interface.
+  //===--------------------------------------------------------------------===//
+  //
+  // Calculate live ranges from scratch.
+  //
+
+  /// reset - Prepare caches for a new set of non-overlapping live ranges.  The
+  /// caches must be reset before attempting calculations with a live range
+  /// that may overlap a previously computed live range, and before the first
+  /// live range in a function.  If live ranges are not known to be
+  /// non-overlapping, call reset before each.
+  void reset(const MachineFunction *MF);
+
+  /// calculate - Calculate the live range of a virtual register from its defs
+  /// and uses.  LI must be empty with no values.
+  void calculate(LiveInterval *LI,
+                 MachineRegisterInfo *MRI,
+                 SlotIndexes *Indexes,
+                 VNInfo::Allocator *Alloc);
+
+  //===--------------------------------------------------------------------===//
+  // Mid-level interface.
+  //===--------------------------------------------------------------------===//
+  //
+  // Modify existing live ranges.
+  //
+
+  /// extend - Extend the live range of LI to reach Kill.
+  ///
+  /// The existing values in LI must be live so they jointly dominate Kill.  If
+  /// Kill is not dominated by a single existing value, PHI-defs are inserted
+  /// as required to preserve SSA form.  If Kill is known to be dominated by a
+  /// single existing value, Alloc may be null.
+  void extend(LiveInterval *LI,
+              SlotIndex Kill,
+              SlotIndexes *Indexes,
+              MachineDominatorTree *DomTree,
+              VNInfo::Allocator *Alloc);
+
+  /// extendToUses - Extend the live range of LI to reach all uses.
+  ///
+  /// All uses must be jointly dominated by existing liveness.  PHI-defs are
+  /// inserted as needed to preserve SSA form.
+  void extendToUses(LiveInterval *LI,
+                    MachineRegisterInfo *MRI,
+                    SlotIndexes *Indexes,
+                    MachineDominatorTree *DomTree,
+                    VNInfo::Allocator *Alloc);
+
+  //===--------------------------------------------------------------------===//
+  // Low-level interface.
+  //===--------------------------------------------------------------------===//
+  //
+  // These functions can be used to compute live ranges where the live-in and
+  // live-out blocks are already known, but the SSA value in each block is
+  // unknown.
+  //
+  // After calling reset(), add known live-out values and known live-in blocks.
+  // Then call calculateValues() to compute the actual value that is
+  // live-in to each block, and add liveness to the live ranges.
+  //
+
+  /// setLiveOutValue - Indicate that VNI is live out from MBB.  The
+  /// calculateValues() function will not add liveness for MBB, the caller
+  /// should take care of that.
+  ///
+  /// VNI may be null only if MBB is a live-through block also passed to
+  /// addLiveInBlock().
+  void setLiveOutValue(MachineBasicBlock *MBB, VNInfo *VNI) {
+    Seen.set(MBB->getNumber());
+    LiveOut[MBB] = LiveOutPair(VNI, 0);
+  }
+
+  /// addLiveInBlock - Add a block with an unknown live-in value.  This
+  /// function can only be called once per basic block.  Once the live-in value
+  /// has been determined, calculateValues() will add liveness to LI.
+  ///
+  /// @param LI      The live range that is live-in to the block.
+  /// @param DomNode The domtree node for the block.
+  /// @param Kill    Index in block where LI is killed.  If the value is
+  ///                live-through, set Kill = SLotIndex() and also call
+  ///                setLiveOutValue(MBB, 0).
+  void addLiveInBlock(LiveInterval *LI,
+                      MachineDomTreeNode *DomNode,
+                      SlotIndex Kill = SlotIndex()) {
+    LiveIn.push_back(LiveInBlock(LI, DomNode, Kill));
+  }
+
+  /// calculateValues - Calculate the value that will be live-in to each block
+  /// added with addLiveInBlock.  Add PHI-def values as needed to preserve SSA
+  /// form.  Add liveness to all live-in blocks up to the Kill point, or the
+  /// whole block for live-through blocks.
+  ///
+  /// Every predecessor of a live-in block must have been given a value with
+  /// setLiveOutValue, the value may be null for live-trough blocks.
+  void calculateValues(SlotIndexes *Indexes,
+                       MachineDominatorTree *DomTree,
+                       VNInfo::Allocator *Alloc);
+};
+
+} // end namespace llvm
+
+#endif
diff --git a/lib/CodeGen/SplitKit.cpp b/lib/CodeGen/SplitKit.cpp
index 67a722e143..b1416cc17e 100644
--- a/lib/CodeGen/SplitKit.cpp
+++ b/lib/CodeGen/SplitKit.cpp
@@ -319,9 +319,7 @@ void SplitEditor::reset(LiveRangeEdit &LRE, ComplementSpillMode SM) {
   OpenIdx = 0;
   RegAssign.clear();
   Values.clear();
-
-  // We don't need to clear LiveOutCache, only LiveOutSeen entries are read.
-  LiveOutSeen.clear();
+  LRCalc.reset(&VRM.getMachineFunction());
 
   // We don't need an AliasAnalysis since we will only be performing
   // cheap-as-a-copy remats anyway.
@@ -392,212 +390,8 @@ void SplitEditor::markComplexMapped(unsigned RegIdx, const VNInfo *ParentVNI) {
 // extendRange - Extend the live range to reach Idx.
 // Potentially create phi-def values.
 void SplitEditor::extendRange(unsigned RegIdx, SlotIndex Idx) {
-  assert(Idx.isValid() && "Invalid SlotIndex");
-  MachineBasicBlock *IdxMBB = LIS.getMBBFromIndex(Idx);
-  assert(IdxMBB && "No MBB at Idx");
-  LiveInterval *LI = Edit->get(RegIdx);
-
-  // Is there a def in the same MBB we can extend?
-  if (LI->extendInBlock(LIS.getMBBStartIdx(IdxMBB), Idx))
-    return;
-
-  // Now for the fun part. We know that ParentVNI potentially has multiple defs,
-  // and we may need to create even more phi-defs to preserve VNInfo SSA form.
-  // Perform a search for all predecessor blocks where we know the dominating
-  // VNInfo.
-  VNInfo *VNI = findReachingDefs(LI, IdxMBB, Idx.getNextSlot());
-
-  // When there were multiple different values, we may need new PHIs.
-  if (!VNI)
-    return updateSSA();
-
-  // Poor man's SSA update for the single-value case.
-  LiveOutPair LOP(VNI, MDT[LIS.getMBBFromIndex(VNI->def)]);
-  for (SmallVectorImpl<LiveInBlock>::iterator I = LiveInBlocks.begin(),
-         E = LiveInBlocks.end(); I != E; ++I) {
-    MachineBasicBlock *MBB = I->DomNode->getBlock();
-    SlotIndex Start = LIS.getMBBStartIdx(MBB);
-    if (I->Kill.isValid())
-      LI->addRange(LiveRange(Start, I->Kill, VNI));
-    else {
-      LiveOutCache[MBB] = LOP;
-      LI->addRange(LiveRange(Start, LIS.getMBBEndIdx(MBB), VNI));
-    }
-  }
-}
-
-/// findReachingDefs - Search the CFG for known live-out values.
-/// Add required live-in blocks to LiveInBlocks.
-VNInfo *SplitEditor::findReachingDefs(LiveInterval *LI,
-                                      MachineBasicBlock *KillMBB,
-                                      SlotIndex Kill) {
-  // Initialize the live-out cache the first time it is needed.
-  if (LiveOutSeen.empty()) {
-    unsigned N = VRM.getMachineFunction().getNumBlockIDs();
-    LiveOutSeen.resize(N);
-    LiveOutCache.resize(N);
-  }
-
-  // Blocks where LI should be live-in.
-  SmallVector<MachineBasicBlock*, 16> WorkList(1, KillMBB);
-
-  // Remember if we have seen more than one value.
-  bool UniqueVNI = true;
-  VNInfo *TheVNI = 0;
-
-  // Using LiveOutCache as a visited set, perform a BFS for all reaching defs.
-  for (unsigned i = 0; i != WorkList.size(); ++i) {
-    MachineBasicBlock *MBB = WorkList[i];
-    assert(!MBB->pred_empty() && "Value live-in to entry block?");
-    for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
-           PE = MBB->pred_end(); PI != PE; ++PI) {
-       MachineBasicBlock *Pred = *PI;
-       LiveOutPair &LOP = LiveOutCache[Pred];
-
-       // Is this a known live-out block?
-       if (LiveOutSeen.test(Pred->getNumber())) {
-         if (VNInfo *VNI = LOP.first) {
-           if (TheVNI && TheVNI != VNI)
-             UniqueVNI = false;
-           TheVNI = VNI;
-         }
-         continue;
-       }
-
-       // First time. LOP is garbage and must be cleared below.
-       LiveOutSeen.set(Pred->getNumber());
-
-       // Does Pred provide a live-out value?
-       SlotIndex Start, Last;
-       tie(Start, Last) = LIS.getSlotIndexes()->getMBBRange(Pred);
-       Last = Last.getPrevSlot();
-       VNInfo *VNI = LI->extendInBlock(Start, Last);
-       LOP.first = VNI;
-       if (VNI) {
-         LOP.second = MDT[LIS.getMBBFromIndex(VNI->def)];
-         if (TheVNI && TheVNI != VNI)
-           UniqueVNI = false;
-         TheVNI = VNI;
-         continue;
-       }
-       LOP.second = 0;
-
-       // No, we need a live-in value for Pred as well
-       if (Pred != KillMBB)
-          WorkList.push_back(Pred);
-       else
-          // Loopback to KillMBB, so value is really live through.
-         Kill = SlotIndex();
-    }
-  }
-
-  // Transfer WorkList to LiveInBlocks in reverse order.
-  // This ordering works best with updateSSA().
-  LiveInBlocks.clear();
-  LiveInBlocks.reserve(WorkList.size());
-  while(!WorkList.empty())
-    LiveInBlocks.push_back(MDT[WorkList.pop_back_val()]);
-
-  // The kill block may not be live-through.
-  assert(LiveInBlocks.back().DomNode->getBlock() == KillMBB);
-  LiveInBlocks.back().Kill = Kill;
-
-  return UniqueVNI ? TheVNI : 0;
-}
-
-void SplitEditor::updateSSA() {
-  // This is essentially the same iterative algorithm that SSAUpdater uses,
-  // except we already have a dominator tree, so we don't have to recompute it.
-  unsigned Changes;
-  do {
-    Changes = 0;
-    // Propagate live-out values down the dominator tree, inserting phi-defs
-    // when necessary.
-    for (SmallVectorImpl<LiveInBlock>::iterator I = LiveInBlocks.begin(),
-           E = LiveInBlocks.end(); I != E; ++I) {
-      MachineDomTreeNode *Node = I->DomNode;
-      // Skip block if the live-in value has already been determined.
-      if (!Node)
-        continue;
-      MachineBasicBlock *MBB = Node->getBlock();
-      MachineDomTreeNode *IDom = Node->getIDom();
-      LiveOutPair IDomValue;
-
-      // We need a live-in value to a block with no immediate dominator?
-      // This is probably an unreachable block that has survived somehow.
-      bool needPHI = !IDom || !LiveOutSeen.test(IDom->getBlock()->getNumber());
-
-      // IDom dominates all of our predecessors, but it may not be their
-      // immediate dominator. Check if any of them have live-out values that are
-      // properly dominated by IDom. If so, we need a phi-def here.
-      if (!needPHI) {
-        IDomValue = LiveOutCache[IDom->getBlock()];
-        for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
-               PE = MBB->pred_end(); PI != PE; ++PI) {
-          LiveOutPair Value = LiveOutCache[*PI];
-          if (!Value.first || Value.first == IDomValue.first)
-            continue;
-          // This predecessor is carrying something other than IDomValue.
-          // It could be because IDomValue hasn't propagated yet, or it could be
-          // because MBB is in the dominance frontier of that value.
-          if (MDT.dominates(IDom, Value.second)) {
-            needPHI = true;
-            break;
-          }
-        }
-      }
-
-      // The value may be live-through even if Kill is set, as can happen when
-      // we are called from extendRange. In that case LiveOutSeen is true, and
-      // LiveOutCache indicates a foreign or missing value.
-      LiveOutPair &LOP = LiveOutCache[MBB];
-
-      // Create a phi-def if required.
-      if (needPHI) {
-        ++Changes;
-        SlotIndex Start = LIS.getMBBStartIdx(MBB);
-        unsigned RegIdx = RegAssign.lookup(Start);
-        LiveInterval *LI = Edit->get(RegIdx);
-        VNInfo *VNI = LI->getNextValue(Start, 0, LIS.getVNInfoAllocator());
-        VNI->setIsPHIDef(true);
-        I->Value = VNI;
-        // This block is done, we know the final value.
-        I->DomNode = 0;
-        if (I->Kill.isValid())
-          LI->addRange(LiveRange(Start, I->Kill, VNI));
-        else {
-          LI->addRange(LiveRange(Start, LIS.getMBBEndIdx(MBB), VNI));
-          LOP = LiveOutPair(VNI, Node);
-        }
-      } else if (IDomValue.first) {
-        // No phi-def here. Remember incoming value.
-        I->Value = IDomValue.first;
-        if (I->Kill.isValid())
-          continue;
-        // Propagate IDomValue if needed:
-        // MBB is live-out and doesn't define its own value.
-        if (LOP.second != Node && LOP.first != IDomValue.first) {
-          ++Changes;
-          LOP = IDomValue;
-        }
-      }
-    }
-  } while (Changes);
-
-  // The values in LiveInBlocks are now accurate. No more phi-defs are needed
-  // for these blocks, so we can color the live ranges.
-  for (SmallVectorImpl<LiveInBlock>::iterator I = LiveInBlocks.begin(),
-         E = LiveInBlocks.end(); I != E; ++I) {
-    if (!I->DomNode)
-      continue;
-    assert(I->Value && "No live-in value found");
-    MachineBasicBlock *MBB = I->DomNode->getBlock();
-    SlotIndex Start = LIS.getMBBStartIdx(MBB);
-    unsigned RegIdx = RegAssign.lookup(Start);
-    LiveInterval *LI = Edit->get(RegIdx);
-    LI->addRange(LiveRange(Start, I->Kill.isValid() ?
-                                  I->Kill : LIS.getMBBEndIdx(MBB), I->Value));
-  }
+  LRCalc.extend(Edit->get(RegIdx), Idx.getNextSlot(),
+                LIS.getSlotIndexes(), &MDT, &LIS.getVNInfoAllocator());
 }
 
 VNInfo *SplitEditor::defFromParent(unsigned RegIdx,
@@ -794,7 +588,6 @@ void SplitEditor::overlapIntv(SlotIndex Start, SlotIndex End) {
 /// Values that were rematerialized are left alone, they need extendRange().
 bool SplitEditor::transferValues() {
   bool Skipped = false;
-  LiveInBlocks.clear();
   RegAssignMap::const_iterator AssignI = RegAssign.begin();
   for (LiveInterval::const_iterator ParentI = Edit->getParent().begin(),
          ParentE = Edit->getParent().end(); ParentI != ParentE; ++ParentI) {
@@ -840,13 +633,6 @@ bool SplitEditor::transferValues() {
         continue;
       }
 
-      // Initialize the live-out cache the first time it is needed.
-      if (LiveOutSeen.empty()) {
-        unsigned N = VRM.getMachineFunction().getNumBlockIDs();
-        LiveOutSeen.resize(N);
-        LiveOutCache.resize(N);
-      }
-
       // This value has multiple defs in RegIdx, but it wasn't rematerialized,
       // so the live range is accurate. Add live-in blocks in [Start;End) to the
       // LiveInBlocks.
@@ -861,10 +647,9 @@ bool SplitEditor::transferValues() {
         assert(VNI && "Missing def for complex mapped value");
         DEBUG(dbgs() << ':' << VNI->id << "*BB#" << MBB->getNumber());
         // MBB has its own def. Is it also live-out?
-        if (BlockEnd <= End) {
-          LiveOutSeen.set(MBB->getNumber());
-          LiveOutCache[MBB] = LiveOutPair(VNI, MDT[MBB]);
-        }
+        if (BlockEnd <= End)
+          LRCalc.setLiveOutValue(MBB, VNI);
+
         // Skip to the next block for live-in.
         ++MBB;
         BlockStart = BlockEnd;
@@ -881,22 +666,17 @@ bool SplitEditor::transferValues() {
           VNInfo *VNI = LI->extendInBlock(BlockStart,
                                          std::min(BlockEnd, End).getPrevSlot());
           assert(VNI && "Missing def for complex mapped parent PHI");
-          if (End >= BlockEnd) {
-            // Live-out as well.
-            LiveOutSeen.set(MBB->getNumber());
-            LiveOutCache[MBB] = LiveOutPair(VNI, MDT[MBB]);
-          }
+          if (End >= BlockEnd)
+            LRCalc.setLiveOutValue(MBB, VNI); // Live-out as well.
         } else {
-          // This block needs a live-in value.
-          LiveInBlocks.push_back(MDT[MBB]);
-          // The last block covered may not be live-out.
+          // This block needs a live-in value.  The last block covered may not
+          // be live-out.
           if (End < BlockEnd)
-            LiveInBlocks.back().Kill = End;
+            LRCalc.addLiveInBlock(LI, MDT[MBB], End);
           else {
-            // Live-out, but we need updateSSA to tell us the value.
-            LiveOutSeen.set(MBB->getNumber());
-            LiveOutCache[MBB] = LiveOutPair((VNInfo*)0,
-                                            (MachineDomTreeNode*)0);
+            // Live-through, and we don't know the value.
+            LRCalc.addLiveInBlock(LI, MDT[MBB]);
+            LRCalc.setLiveOutValue(MBB, 0);
           }
         }
         BlockStart = BlockEnd;
@@ -907,8 +687,7 @@ bool SplitEditor::transferValues() {
     DEBUG(dbgs() << '\n');
   }
 
-  if (!LiveInBlocks.empty())
-    updateSSA();
+  LRCalc.calculateValues(LIS.getSlotIndexes(), &MDT, &LIS.getVNInfoAllocator());
 
   return Skipped;
 }
diff --git a/lib/CodeGen/SplitKit.h b/lib/CodeGen/SplitKit.h
index 7f74d3acf6..c00b8d366a 100644
--- a/lib/CodeGen/SplitKit.h
+++ b/lib/CodeGen/SplitKit.h
@@ -15,13 +15,11 @@
 #ifndef LLVM_CODEGEN_SPLITKIT_H
 #define LLVM_CODEGEN_SPLITKIT_H
 
+#include "LiveRangeCalc.h"
 #include "llvm/ADT/ArrayRef.h"
-#include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/DenseMap.h"
-#include "llvm/ADT/IndexedMap.h"
 #include "llvm/ADT/IntervalMap.h"
 #include "llvm/ADT/SmallPtrSet.h"
-#include "llvm/CodeGen/SlotIndexes.h"
 
 namespace llvm {
 
@@ -38,12 +36,6 @@ class VirtRegMap;
 class VNInfo;
 class raw_ostream;
 
-/// At some point we should just include MachineDominators.h:
-class MachineDominatorTree;
-template <class NodeT> class DomTreeNodeBase;
-typedef DomTreeNodeBase<MachineBasicBlock> MachineDomTreeNode;
-
-
 /// SplitAnalysis - Analyze a LiveInterval, looking for live range splitting
 /// opportunities.
 class SplitAnalysis {
@@ -281,54 +273,8 @@ private:
   ///    The new value has no live ranges anywhere.
   ValueMap Values;
 
-  typedef std::pair<VNInfo*, MachineDomTreeNode*> LiveOutPair;
-  typedef IndexedMap<LiveOutPair, MBB2NumberFunctor> LiveOutMap;
-
-  // LiveOutCache - Map each basic block where a new register is live out to the
-  // live-out value and its defining block.
-  // One of these conditions shall be true:
-  //
-  //  1. !LiveOutSeen.count(MBB->getNumber())
-  //  2. LiveOutCache[MBB].second.getNode() == MBB
-  //  3. forall P in preds(MBB): LiveOutCache[P] == LiveOutCache[MBB]
-  //
-  // This is only a cache, the values can be computed as:
-  //
-  //  VNI = Edit.get(RegIdx)->getVNInfoAt(LIS.getMBBEndIdx(MBB))
-  //  Node = mbt_[LIS.getMBBFromIndex(VNI->def)]
-  //
-  // The cache can be shared by all the new registers because at most one is
-  // live out of each block.
-  LiveOutMap LiveOutCache;
-
-  // LiveOutSeen - Indexed by MBB->getNumber(), a bit is set for each valid
-  // entry in LiveOutCache.  This is also used as a visited set for
-  // findReachingDefs().
-  BitVector LiveOutSeen;
-
-  /// LiveInBlock - Info for updateSSA() about a block where a register is
-  /// live-in.
-  /// The updateSSA caller provides DomNode and Kill inside MBB, updateSSA()
-  /// adds the computed live-in value.
-  struct LiveInBlock {
-    // Dominator tree node for the block.
-    // Cleared by updateSSA when the final value has been determined.
-    MachineDomTreeNode *DomNode;
-
-    // Live-in value filled in by updateSSA once it is known.
-    VNInfo *Value;
-
-    // Position in block where the live-in range ends, or SlotIndex() if the
-    // range passes through the block.
-    SlotIndex Kill;
-
-    LiveInBlock(MachineDomTreeNode *node) : DomNode(node), Value(0) {}
-  };
-
-  /// LiveInBlocks - List of live-in blocks used by findReachingDefs() and
-  /// updateSSA(). This list is usually empty, it exists here to avoid frequent
-  /// reallocations.
-  SmallVector<LiveInBlock, 16> LiveInBlocks;
+  /// LRCalc - Cache for computing live ranges and SSA update.
+  LiveRangeCalc LRCalc;
 
   /// defValue - define a value in RegIdx from ParentVNI at Idx.
   /// Idx does not have to be ParentVNI->def, but it must be contained within
@@ -353,19 +299,6 @@ private:
   /// Insert PHIDefs as needed to preserve SSA form.
   void extendRange(unsigned RegIdx, SlotIndex Idx);
 
-  /// findReachingDefs - Starting from MBB, add blocks to LiveInBlocks until all
-  /// reaching defs for LI are found.
-  /// @param LI   Live interval whose value is needed.
-  /// @param MBB  Block where LI should be live-in.
-  /// @param Kill Kill point in MBB.
-  /// @return Unique value seen, or NULL.
-  VNInfo *findReachingDefs(LiveInterval *LI, MachineBasicBlock *MBB,
-                           SlotIndex Kill);
-
-  /// updateSSA - Compute and insert PHIDefs such that all blocks in
-  // LiveInBlocks get a known live-in value. Add live ranges to the blocks.
-  void updateSSA();
-
   /// transferValues - Transfer values to the new ranges.
   /// Return true if any ranges were skipped.
   bool transferValues();