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
diff --git a/lib/CodeGen/SplitKit.h b/lib/CodeGen/SplitKit.h
index 9ba7cbe..9a7fa53 100644
--- a/lib/CodeGen/SplitKit.h
+++ b/lib/CodeGen/SplitKit.h
@@ -22,7 +22,6 @@
class LiveIntervals;
class LiveRangeEdit;
class MachineInstr;
-class MachineDominatorTree;
class MachineLoop;
class MachineLoopInfo;
class MachineRegisterInfo;
@@ -31,6 +30,11 @@
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 @@
// 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,