Replace SplitKit SSA update with an iterative algorithm very similar to the one

in SSAUpdaterImpl.h

Verifying live intervals revealed that the old method was completely wrong, and
we need an iterative approach to calculating PHI placemant. Fortunately, we have
MachineDominators available, so we don't have to compute that over and over
like SSAUpdaterImpl.h must.

Live-out values are cached between calls to mapValue() and computed in a greedy
way, so most calls will be working with very small block sets.

Thanks to Bob for explaining how this should work.

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

1 files changed, 23 insertions, 1 deletions

diff --git a/lib/CodeGen/SplitKit.h b/lib/CodeGen/SplitKit.h
index 9ba7cbeb10..9a7fa5388a 100644
--- a/lib/CodeGen/SplitKit.h
+++ b/lib/CodeGen/SplitKit.h
@@ -22,7 +22,6 @@ class LiveInterval;
 class LiveIntervals;
 class LiveRangeEdit;
 class MachineInstr;
-class MachineDominatorTree;
 class MachineLoop;
 class MachineLoopInfo;
 class MachineRegisterInfo;
@@ -31,6 +30,11 @@ 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 {
@@ -171,6 +175,24 @@ class LiveIntervalMap {
   // values not present (unknown/unmapped).
   ValueMap valueMap_;
 
+  typedef std::pair<VNInfo*, MachineDomTreeNode*> LiveOutPair;
+  typedef DenseMap<MachineBasicBlock*,LiveOutPair> LiveOutMap;
+
+  // liveOutCache_ - Map each basic block where li_ is live out to the live-out
+  // value and its defining block. One of these conditions shall be true:
+  //
+  //  1. !liveOutCache_.count(MBB)
+  //  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 = li_->getVNInfoAt(lis_.getMBBEndIdx(MBB))
+  //  Node = mbt_[lis_.getMBBFromIndex(VNI->def)]
+  //
+  // The cache is also used as a visiteed set by mapValue().
+  LiveOutMap liveOutCache_;
+
 public:
   LiveIntervalMap(LiveIntervals &lis,
                   MachineDominatorTree &mdt,