Move extendRange() into SplitEditor and delete the LiveRangeMap class.

Extract the updateSSA() method from the too long extendRange().

LiveOutCache can be shared among all the new intervals since there is at most
one of the new ranges live out from each basic block.

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

1 files changed, 135 insertions, 176 deletions

diff --git a/lib/CodeGen/SplitKit.cpp b/lib/CodeGen/SplitKit.cpp
index a2214bb3be..4c2a7bda0f 100644
--- a/lib/CodeGen/SplitKit.cpp
+++ b/lib/CodeGen/SplitKit.cpp
@@ -198,29 +198,101 @@ void SplitAnalysis::analyze(const LiveInterval *li) {
 
 
 //===----------------------------------------------------------------------===//
-//                               LiveIntervalMap
+//                               Split Editor
 //===----------------------------------------------------------------------===//
 
-// Work around the fact that the std::pair constructors are broken for pointer
-// pairs in some implementations. makeVV(x, 0) works.
-static inline std::pair<const VNInfo*, VNInfo*>
-makeVV(const VNInfo *a, VNInfo *b) {
-  return std::make_pair(a, b);
+/// Create a new SplitEditor for editing the LiveInterval analyzed by SA.
+SplitEditor::SplitEditor(SplitAnalysis &sa,
+                         LiveIntervals &lis,
+                         VirtRegMap &vrm,
+                         MachineDominatorTree &mdt,
+                         LiveRangeEdit &edit)
+  : SA(sa), LIS(lis), VRM(vrm),
+    MRI(vrm.getMachineFunction().getRegInfo()),
+    MDT(mdt),
+    TII(*vrm.getMachineFunction().getTarget().getInstrInfo()),
+    TRI(*vrm.getMachineFunction().getTarget().getRegisterInfo()),
+    Edit(edit),
+    OpenIdx(0),
+    RegAssign(Allocator)
+{
+  // We don't need an AliasAnalysis since we will only be performing
+  // cheap-as-a-copy remats anyway.
+  Edit.anyRematerializable(LIS, TII, 0);
+}
+
+void SplitEditor::dump() const {
+  if (RegAssign.empty()) {
+    dbgs() << " empty\n";
+    return;
+  }
+
+  for (RegAssignMap::const_iterator I = RegAssign.begin(); I.valid(); ++I)
+    dbgs() << " [" << I.start() << ';' << I.stop() << "):" << I.value();
+  dbgs() << '\n';
 }
 
-void LiveIntervalMap::reset(LiveInterval *li) {
-  LI = li;
-  LiveOutCache.clear();
+VNInfo *SplitEditor::defValue(unsigned RegIdx,
+                              const VNInfo *ParentVNI,
+                              SlotIndex Idx) {
+  assert(ParentVNI && "Mapping  NULL value");
+  assert(Idx.isValid() && "Invalid SlotIndex");
+  assert(Edit.getParent().getVNInfoAt(Idx) == ParentVNI && "Bad Parent VNI");
+  LiveInterval *LI = Edit.get(RegIdx);
+
+  // Create a new value.
+  VNInfo *VNI = LI->getNextValue(Idx, 0, LIS.getVNInfoAllocator());
+
+  // Preserve the PHIDef bit.
+  if (ParentVNI->isPHIDef() && Idx == ParentVNI->def)
+    VNI->setIsPHIDef(true);
+
+  // Use insert for lookup, so we can add missing values with a second lookup.
+  std::pair<ValueMap::iterator, bool> InsP =
+    Values.insert(std::make_pair(std::make_pair(RegIdx, ParentVNI->id), VNI));
+
+  // This was the first time (RegIdx, ParentVNI) was mapped.
+  // Keep it as a simple def without any liveness.
+  if (InsP.second)
+    return VNI;
+
+  // If the previous value was a simple mapping, add liveness for it now.
+  if (VNInfo *OldVNI = InsP.first->second) {
+    SlotIndex Def = OldVNI->def;
+    LI->addRange(LiveRange(Def, Def.getNextSlot(), OldVNI));
+    // No longer a simple mapping.
+    InsP.first->second = 0;
+  }
+
+  // This is a complex mapping, add liveness for VNI
+  SlotIndex Def = VNI->def;
+  LI->addRange(LiveRange(Def, Def.getNextSlot(), VNI));
+
+  return VNI;
 }
 
+void SplitEditor::markComplexMapped(unsigned RegIdx, const VNInfo *ParentVNI) {
+  assert(ParentVNI && "Mapping  NULL value");
+  VNInfo *&VNI = Values[std::make_pair(RegIdx, ParentVNI->id)];
+
+  // ParentVNI was either unmapped or already complex mapped. Either way.
+  if (!VNI)
+    return;
+
+  // This was previously a single mapping. Make sure the old def is represented
+  // by a trivial live range.
+  SlotIndex Def = VNI->def;
+  Edit.get(RegIdx)->addRange(LiveRange(Def, Def.getNextSlot(), VNI));
+  VNI = 0;
+}
 
 // extendRange - Extend the live range to reach Idx.
 // Potentially create phi-def values.
-void LiveIntervalMap::extendRange(SlotIndex Idx) {
-  assert(LI && "call reset first");
+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))
@@ -247,12 +319,8 @@ void LiveIntervalMap::extendRange(SlotIndex Idx) {
        std::pair<LiveOutMap::iterator,bool> LOIP =
          LiveOutCache.insert(std::make_pair(Pred, LiveOutPair()));
        // Yes, we have been here before.
-       if (!LOIP.second) {
-         DEBUG(if (VNInfo *VNI = LOIP.first->second.first)
-                 dbgs() << "    known valno #" << VNI->id
-                        << " at BB#" << Pred->getNumber() << '\n');
+       if (!LOIP.second)
          continue;
-       }
 
        // Does Pred provide a live-out value?
        SlotIndex Start, Last;
@@ -260,9 +328,6 @@ void LiveIntervalMap::extendRange(SlotIndex Idx) {
        Last = Last.getPrevSlot();
        if (VNInfo *VNI = LI->extendInBlock(Start, Last)) {
          MachineBasicBlock *DefMBB = LIS.getMBBFromIndex(VNI->def);
-         DEBUG(dbgs() << "    found valno #" << VNI->id
-                      << " from BB#" << DefMBB->getNumber()
-                      << " at BB#" << Pred->getNumber() << '\n');
          LiveOutPair &LOP = LOIP.first->second;
          LOP.first = VNI;
          LOP.second = MDT[DefMBB];
@@ -275,16 +340,56 @@ void LiveIntervalMap::extendRange(SlotIndex Idx) {
   }
 
   // We may need to add phi-def values to preserve the SSA form.
+  VNInfo *IdxVNI = updateSSA(RegIdx, LiveIn, Idx, IdxMBB);
+
+#ifndef NDEBUG
+  // Check the LiveOutCache invariants.
+  for (LiveOutMap::iterator I = LiveOutCache.begin(), E = LiveOutCache.end();
+         I != E; ++I) {
+    assert(I->first && "Null MBB entry in cache");
+    assert(I->second.first && "Null VNInfo in cache");
+    assert(I->second.second && "Null DomTreeNode in cache");
+    if (I->second.second->getBlock() == I->first)
+      continue;
+    for (MachineBasicBlock::pred_iterator PI = I->first->pred_begin(),
+           PE = I->first->pred_end(); PI != PE; ++PI)
+      assert(LiveOutCache.lookup(*PI) == I->second && "Bad invariant");
+  }
+#endif
+
+  // Since we went through the trouble of a full BFS visiting all reaching defs,
+  // the values in LiveIn are now accurate. No more phi-defs are needed
+  // for these blocks, so we can color the live ranges.
+  for (unsigned i = 0, e = LiveIn.size(); i != e; ++i) {
+    MachineBasicBlock *MBB = LiveIn[i]->getBlock();
+    SlotIndex Start = LIS.getMBBStartIdx(MBB);
+    VNInfo *VNI = LiveOutCache.lookup(MBB).first;
+
+    // Anything in LiveIn other than IdxMBB is live-through.
+    // In IdxMBB, we should stop at Idx unless the same value is live-out.
+    if (MBB == IdxMBB && IdxVNI != VNI)
+      LI->addRange(LiveRange(Start, Idx.getNextSlot(), IdxVNI));
+    else
+      LI->addRange(LiveRange(Start, LIS.getMBBEndIdx(MBB), VNI));
+  }
+}
+
+VNInfo *SplitEditor::updateSSA(unsigned RegIdx,
+                               SmallVectorImpl<MachineDomTreeNode*> &LiveIn,
+                               SlotIndex Idx,
+                               const MachineBasicBlock *IdxMBB) {
   // 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.
+  LiveInterval *LI = Edit.get(RegIdx);
   VNInfo *IdxVNI = 0;
   unsigned Changes;
   do {
     Changes = 0;
     DEBUG(dbgs() << "  Iterating over " << LiveIn.size() << " blocks.\n");
-    // Propagate live-out values down the dominator tree, inserting phi-defs when
-    // necessary. Since LiveIn was created by a BFS, going backwards makes it more
-    // likely for us to visit immediate dominators before their children.
+    // Propagate live-out values down the dominator tree, inserting phi-defs
+    // when necessary. Since LiveIn was created by a BFS, going backwards makes
+    // it more likely for us to visit immediate dominators before their
+    // children.
     for (unsigned i = LiveIn.size(); i; --i) {
       MachineDomTreeNode *Node = LiveIn[i-1];
       MachineBasicBlock *MBB = Node->getBlock();
@@ -369,146 +474,7 @@ void LiveIntervalMap::extendRange(SlotIndex Idx) {
   } while (Changes);
 
   assert(IdxVNI && "Didn't find value for Idx");
-
-#ifndef NDEBUG
-  // Check the LiveOutCache invariants.
-  for (LiveOutMap::iterator I = LiveOutCache.begin(), E = LiveOutCache.end();
-         I != E; ++I) {
-    assert(I->first && "Null MBB entry in cache");
-    assert(I->second.first && "Null VNInfo in cache");
-    assert(I->second.second && "Null DomTreeNode in cache");
-    if (I->second.second->getBlock() == I->first)
-      continue;
-    for (MachineBasicBlock::pred_iterator PI = I->first->pred_begin(),
-           PE = I->first->pred_end(); PI != PE; ++PI)
-      assert(LiveOutCache.lookup(*PI) == I->second && "Bad invariant");
-  }
-#endif
-
-  // Since we went through the trouble of a full BFS visiting all reaching defs,
-  // the values in LiveIn are now accurate. No more phi-defs are needed
-  // for these blocks, so we can color the live ranges.
-  for (unsigned i = 0, e = LiveIn.size(); i != e; ++i) {
-    MachineBasicBlock *MBB = LiveIn[i]->getBlock();
-    SlotIndex Start = LIS.getMBBStartIdx(MBB);
-    VNInfo *VNI = LiveOutCache.lookup(MBB).first;
-
-    // Anything in LiveIn other than IdxMBB is live-through.
-    // In IdxMBB, we should stop at Idx unless the same value is live-out.
-    if (MBB == IdxMBB && IdxVNI != VNI)
-      LI->addRange(LiveRange(Start, Idx.getNextSlot(), IdxVNI));
-    else
-      LI->addRange(LiveRange(Start, LIS.getMBBEndIdx(MBB), VNI));
-  }
-}
-
-#ifndef NDEBUG
-void LiveIntervalMap::dumpCache() {
-  for (LiveOutMap::iterator I = LiveOutCache.begin(), E = LiveOutCache.end();
-         I != E; ++I) {
-    assert(I->first && "Null MBB entry in cache");
-    assert(I->second.first && "Null VNInfo in cache");
-    assert(I->second.second && "Null DomTreeNode in cache");
-    dbgs() << "    cache: BB#" << I->first->getNumber()
-           << " has valno #" << I->second.first->id << " from BB#"
-           << I->second.second->getBlock()->getNumber() << ", preds";
-    for (MachineBasicBlock::pred_iterator PI = I->first->pred_begin(),
-           PE = I->first->pred_end(); PI != PE; ++PI)
-      dbgs() << " BB#" << (*PI)->getNumber();
-    dbgs() << '\n';
-  }
-  dbgs() << "    cache: " << LiveOutCache.size() << " entries.\n";
-}
-#endif
-
-
-//===----------------------------------------------------------------------===//
-//                               Split Editor
-//===----------------------------------------------------------------------===//
-
-/// Create a new SplitEditor for editing the LiveInterval analyzed by SA.
-SplitEditor::SplitEditor(SplitAnalysis &sa,
-                         LiveIntervals &lis,
-                         VirtRegMap &vrm,
-                         MachineDominatorTree &mdt,
-                         LiveRangeEdit &edit)
-  : SA(sa), LIS(lis), VRM(vrm),
-    MRI(vrm.getMachineFunction().getRegInfo()),
-    MDT(mdt),
-    TII(*vrm.getMachineFunction().getTarget().getInstrInfo()),
-    TRI(*vrm.getMachineFunction().getTarget().getRegisterInfo()),
-    Edit(edit),
-    OpenIdx(0),
-    RegAssign(Allocator)
-{
-  // We don't need an AliasAnalysis since we will only be performing
-  // cheap-as-a-copy remats anyway.
-  Edit.anyRematerializable(LIS, TII, 0);
-}
-
-void SplitEditor::dump() const {
-  if (RegAssign.empty()) {
-    dbgs() << " empty\n";
-    return;
-  }
-
-  for (RegAssignMap::const_iterator I = RegAssign.begin(); I.valid(); ++I)
-    dbgs() << " [" << I.start() << ';' << I.stop() << "):" << I.value();
-  dbgs() << '\n';
-}
-
-VNInfo *SplitEditor::defValue(unsigned RegIdx,
-                              const VNInfo *ParentVNI,
-                              SlotIndex Idx) {
-  assert(ParentVNI && "Mapping  NULL value");
-  assert(Idx.isValid() && "Invalid SlotIndex");
-  assert(Edit.getParent().getVNInfoAt(Idx) == ParentVNI && "Bad Parent VNI");
-  LiveInterval *LI = Edit.get(RegIdx);
-
-  // Create a new value.
-  VNInfo *VNI = LI->getNextValue(Idx, 0, LIS.getVNInfoAllocator());
-
-  // Preserve the PHIDef bit.
-  if (ParentVNI->isPHIDef() && Idx == ParentVNI->def)
-    VNI->setIsPHIDef(true);
-
-  // Use insert for lookup, so we can add missing values with a second lookup.
-  std::pair<ValueMap::iterator, bool> InsP =
-    Values.insert(std::make_pair(std::make_pair(RegIdx, ParentVNI->id), VNI));
-
-  // This was the first time (RegIdx, ParentVNI) was mapped.
-  // Keep it as a simple def without any liveness.
-  if (InsP.second)
-    return VNI;
-
-  // If the previous value was a simple mapping, add liveness for it now.
-  if (VNInfo *OldVNI = InsP.first->second) {
-    SlotIndex Def = OldVNI->def;
-    LI->addRange(LiveRange(Def, Def.getNextSlot(), OldVNI));
-    // No longer a simple mapping.
-    InsP.first->second = 0;
-  }
-
-  // This is a complex mapping, add liveness for VNI
-  SlotIndex Def = VNI->def;
-  LI->addRange(LiveRange(Def, Def.getNextSlot(), VNI));
-
-  return VNI;
-}
-
-void SplitEditor::markComplexMapped(unsigned RegIdx, const VNInfo *ParentVNI) {
-  assert(ParentVNI && "Mapping  NULL value");
-  VNInfo *&VNI = Values[std::make_pair(RegIdx, ParentVNI->id)];
-
-  // ParentVNI was either unmapped or already complex mapped. Either way.
-  if (!VNI)
-    return;
-
-  // This was previously a single mapping. Make sure the old def is represented
-  // by a trivial live range.
-  SlotIndex Def = VNI->def;
-  Edit.get(RegIdx)->addRange(LiveRange(Def, Def.getNextSlot(), VNI));
-  VNI = 0;
+  return IdxVNI;
 }
 
 VNInfo *SplitEditor::defFromParent(unsigned RegIdx,
@@ -545,17 +511,12 @@ void SplitEditor::openIntv() {
   assert(!OpenIdx && "Previous LI not closed before openIntv");
 
   // Create the complement as index 0.
-  if (Edit.empty()) {
+  if (Edit.empty())
     Edit.create(MRI, LIS, VRM);
-    LIMappers.push_back(LiveIntervalMap(LIS, MDT, Edit.getParent()));
-    LIMappers.back().reset(Edit.get(0));
-  }
 
   // Create the open interval.
   OpenIdx = Edit.size();
   Edit.create(MRI, LIS, VRM);
-  LIMappers.push_back(LiveIntervalMap(LIS, MDT, Edit.getParent()));
-  LIMappers[OpenIdx].reset(Edit.get(OpenIdx));
 }
 
 SlotIndex SplitEditor::enterIntvBefore(SlotIndex Idx) {
@@ -716,7 +677,7 @@ void SplitEditor::rewriteAssigned() {
                  << Idx << ':' << RegIdx << '\t' << *MI);
 
     // Extend liveness to Idx.
-    LIMappers[RegIdx].extendRange(Idx);
+    extendRange(RegIdx, Idx);
   }
 }
 
@@ -783,7 +744,6 @@ void SplitEditor::finish() {
     if (PHIVNI->isUnused() || !PHIVNI->isPHIDef())
       continue;
     unsigned RegIdx = RegAssign.lookup(PHIVNI->def);
-    LiveIntervalMap &LIM = LIMappers[RegIdx];
     MachineBasicBlock *MBB = LIS.getMBBFromIndex(PHIVNI->def);
     DEBUG(dbgs() << "  map phi in BB#" << MBB->getNumber() << '@' << PHIVNI->def
                  << " -> " << RegIdx << '\n');
@@ -793,16 +753,15 @@ void SplitEditor::finish() {
       DEBUG(dbgs() << "    pred BB#" << (*PI)->getNumber() << '@' << End);
       // The predecessor may not have a live-out value. That is OK, like an
       // undef PHI operand.
-      if (VNInfo *VNI = Edit.getParent().getVNInfoAt(End)) {
-        DEBUG(dbgs() << " has parent valno #" << VNI->id << " live out\n");
+      if (Edit.getParent().liveAt(End)) {
+        DEBUG(dbgs() << " has parent live out\n");
         assert(RegAssign.lookup(End) == RegIdx &&
                "Different register assignment in phi predecessor");
-        LIM.extendRange(End);
-      }
-      else
+        extendRange(RegIdx, End);
+      } else
         DEBUG(dbgs() << " is not live-out\n");
     }
-    DEBUG(dbgs() << "    " << *LIM.getLI() << '\n');
+    DEBUG(dbgs() << "    " << *Edit.get(RegIdx) << '\n');
   }
 
   // Rewrite instructions.