From ff3ae8691c18c4c40d09fb21ecac880aea9a536b Mon Sep 17 00:00:00 2001
From: Jakob Stoklund Olesen <stoklund@2pi.dk>
Date: Wed, 18 Aug 2010 20:29:53 +0000
Subject: [PATCH] Thinking about it, we don't need MachineDominatorTree after
 all. The DomValue map discovers the iterated dominance frontier for free.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@111400 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/CodeGen/SplitKit.cpp | 40 +++++++++++++++++++++++++---------------
 lib/CodeGen/SplitKit.h   |  5 +----
 2 files changed, 26 insertions(+), 19 deletions(-)

diff --git a/lib/CodeGen/SplitKit.cpp b/lib/CodeGen/SplitKit.cpp
index b081bf37337..9bdef957116 100644
--- a/lib/CodeGen/SplitKit.cpp
+++ b/lib/CodeGen/SplitKit.cpp
@@ -17,7 +17,6 @@
 #include "VirtRegMap.h"
 #include "llvm/CodeGen/CalcSpillWeights.h"
 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
-#include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
@@ -423,31 +422,41 @@ VNInfo *LiveIntervalMap::mapValue(const VNInfo *ParentVNI, SlotIndex Idx) {
     // Yes, VNI dominates MBB. Track the path back to IdxMBB, creating phi-defs
     // as needed along the way.
     for (unsigned PI = IDFI.getPathLength()-1; PI != 0; --PI) {
-      // Start from MBB's immediate successor.
+      // Start from MBB's immediate successor. End at IdxMBB.
       MachineBasicBlock *Succ = IDFI.getPath(PI-1);
       std::pair<MBBValueMap::iterator, bool> InsP =
         DomValue.insert(MBBValueMap::value_type(Succ, VNI));
+
+      // This is the first time we backtrack to Succ.
+      if (InsP.second)
+        continue;
+
+      // We reached Succ again with the same VNI. Nothing is going to change.
+      VNInfo *OVNI = InsP.first->second;
+      if (OVNI == VNI)
+        break;
+
+      // Succ already has a phi-def. No need to continue.
       SlotIndex Start = lis_.getMBBStartIdx(Succ);
-      if (InsP.second) {
-        // This is the first time we backtrack to Succ. Verify dominance.
-        if (Succ->pred_size() == 1 || dt_.dominates(MBB, Succ))
-          continue;
-      } else if (InsP.first->second == VNI ||
-                 InsP.first->second->def == Start) {
-        // We have previously backtracked VNI to Succ, or Succ already has a
-        // phi-def. No need to backtrack further.
+      if (OVNI->def == Start)
         break;
-      }
-      // VNI does not dominate Succ, we need a new phi-def.
+
+      // We have a collision between the old and new VNI at Succ. That means
+      // neither dominates and we need a new phi-def.
       VNI = li_.getNextValue(Start, 0, true, lis_.getVNInfoAllocator());
       VNI->setIsPHIDef(true);
       InsP.first->second = VNI;
-      MBB = Succ;
+
+      // Replace OVNI with VNI in the remaining path.
+      for (; PI > 1 ; --PI) {
+        MBBValueMap::iterator I = DomValue.find(IDFI.getPath(PI-2));
+        if (I == DomValue.end() || I->second != OVNI)
+          break;
+        I->second = VNI;
+      }
     }
 
     // No need to search the children, we found a dominating value.
-    // FIXME: We could prune up to the last phi-def we inserted, need df_iterator
-    // for that.
     IDFI.skipChildren();
   }
 
@@ -468,6 +477,7 @@ VNInfo *LiveIntervalMap::mapValue(const VNInfo *ParentVNI, SlotIndex Idx) {
        // Don't add full liveness to IdxMBB, stop at Idx.
        if (Start != Idx)
          li_.addRange(LiveRange(Start, Idx, VNI));
+       // The caller had better add some liveness to IdxVNI, or it leaks.
        IdxVNI = VNI;
      } else
       li_.addRange(LiveRange(Start, lis_.getMBBEndIdx(MBB), VNI));
diff --git a/lib/CodeGen/SplitKit.h b/lib/CodeGen/SplitKit.h
index 622d7e77496..ddef7461dc3 100644
--- a/lib/CodeGen/SplitKit.h
+++ b/lib/CodeGen/SplitKit.h
@@ -20,7 +20,6 @@ namespace llvm {
 
 class LiveInterval;
 class LiveIntervals;
-class MachineDominatorTree;
 class MachineInstr;
 class MachineLoop;
 class MachineLoopInfo;
@@ -147,7 +146,6 @@ public:
 /// Values in parentli_ may map to any number of openli_ values, including 0.
 class LiveIntervalMap {
   LiveIntervals &lis_;
-  MachineDominatorTree &dt_;
 
   // The parent interval is never changed.
   const LiveInterval &parentli_;
@@ -174,10 +172,9 @@ class LiveIntervalMap {
 
 public:
   LiveIntervalMap(LiveIntervals &lis,
-                  MachineDominatorTree &dt,
                   const LiveInterval &parentli,
                   LiveInterval &li)
-    : lis_(lis), dt_(dt), parentli_(parentli), li_(li) {}
+    : lis_(lis), parentli_(parentli), li_(li) {}
 
   /// defValue - define a value in li_ from the parentli_ value VNI and Idx.
   /// Idx does not have to be ParentVNI->def, but it must be contained within
-- 
2.34.1