From 9b057771ba22441b8d312404204433477b4be657 Mon Sep 17 00:00:00 2001
From: Jakob Stoklund Olesen <stoklund@2pi.dk>
Date: Wed, 9 Feb 2011 23:30:25 +0000
Subject: [PATCH] Use the LiveBLocks array for SplitEditor::splitSingleBlocks()
 as well.

This fixes a bug where splitSingleBlocks() could split a live range after a
terminator instruction.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@125237 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/CodeGen/SplitKit.cpp | 87 ++++++++++++++++++++--------------------
 lib/CodeGen/SplitKit.h   |  4 ++
 2 files changed, 47 insertions(+), 44 deletions(-)

diff --git a/lib/CodeGen/SplitKit.cpp b/lib/CodeGen/SplitKit.cpp
index fef50893f98..c5aed4832ee 100644
--- a/lib/CodeGen/SplitKit.cpp
+++ b/lib/CodeGen/SplitKit.cpp
@@ -954,6 +954,25 @@ SlotIndex SplitEditor::leaveIntvAfter(SlotIndex Idx) {
   return VNI->def;
 }
 
+SlotIndex SplitEditor::leaveIntvBefore(SlotIndex Idx) {
+  assert(OpenIdx && "openIntv not called before leaveIntvBefore");
+  DEBUG(dbgs() << "    leaveIntvBefore " << Idx);
+
+  // The interval must be live into the instruction at Idx.
+  Idx = Idx.getBoundaryIndex();
+  VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Idx);
+  if (!ParentVNI) {
+    DEBUG(dbgs() << ": not live\n");
+    return Idx.getNextSlot();
+  }
+  DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
+
+  MachineInstr *MI = LIS.getInstructionFromIndex(Idx);
+  assert(MI && "No instruction at index");
+  VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI);
+  return VNI->def;
+}
+
 SlotIndex SplitEditor::leaveIntvAtTop(MachineBasicBlock &MBB) {
   assert(OpenIdx && "openIntv not called before leaveIntvAtTop");
   SlotIndex Start = LIS.getMBBStartIdx(&MBB);
@@ -1211,28 +1230,20 @@ void SplitEditor::splitAroundLoop(const MachineLoop *Loop) {
 /// may be an advantage to split CurLI for the duration of the block.
 bool SplitAnalysis::getMultiUseBlocks(BlockPtrSet &Blocks) {
   // If CurLI is local to one block, there is no point to splitting it.
-  if (UsingBlocks.size() <= 1)
+  if (LiveBlocks.size() <= 1)
     return false;
   // Add blocks with multiple uses.
-  for (BlockCountMap::iterator I = UsingBlocks.begin(), E = UsingBlocks.end();
-       I != E; ++I)
-    switch (I->second) {
-    case 0:
-    case 1:
+  for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) {
+    const BlockInfo &BI = LiveBlocks[i];
+    if (!BI.Uses)
       continue;
-    case 2: {
-      // When there are only two uses and CurLI is both live in and live out,
-      // we don't really win anything by isolating the block since we would be
-      // inserting two copies.
-      // The remaing register would still have two uses in the block. (Unless it
-      // separates into disconnected components).
-      if (LIS.isLiveInToMBB(*CurLI, I->first) &&
-          LIS.isLiveOutOfMBB(*CurLI, I->first))
-        continue;
-    } // Fall through.
-    default:
-      Blocks.insert(I->first);
-    }
+    unsigned Instrs = UsingBlocks.lookup(BI.MBB);
+    if (Instrs <= 1)
+      continue;
+    if (Instrs == 2 && BI.LiveIn && BI.LiveOut && !BI.LiveThrough)
+      continue;
+    Blocks.insert(BI.MBB);
+  }
   return !Blocks.empty();
 }
 
@@ -1240,34 +1251,22 @@ bool SplitAnalysis::getMultiUseBlocks(BlockPtrSet &Blocks) {
 /// basic block in Blocks.
 void SplitEditor::splitSingleBlocks(const SplitAnalysis::BlockPtrSet &Blocks) {
   DEBUG(dbgs() << "  splitSingleBlocks for " << Blocks.size() << " blocks.\n");
-  // Determine the first and last instruction using CurLI in each block.
-  typedef std::pair<SlotIndex,SlotIndex> IndexPair;
-  typedef DenseMap<const MachineBasicBlock*,IndexPair> IndexPairMap;
-  IndexPairMap MBBRange;
-  for (SplitAnalysis::InstrPtrSet::const_iterator I = sa_.UsingInstrs.begin(),
-       E = sa_.UsingInstrs.end(); I != E; ++I) {
-    const MachineBasicBlock *MBB = (*I)->getParent();
-    if (!Blocks.count(MBB))
-      continue;
-    SlotIndex Idx = LIS.getInstructionIndex(*I);
-    DEBUG(dbgs() << "  BB#" << MBB->getNumber() << '\t' << Idx << '\t' << **I);
-    IndexPair &IP = MBBRange[MBB];
-    if (!IP.first.isValid() || Idx < IP.first)
-      IP.first = Idx;
-    if (!IP.second.isValid() || Idx > IP.second)
-      IP.second = Idx;
-  }
 
-  // Create a new interval for each block.
-  for (SplitAnalysis::BlockPtrSet::const_iterator I = Blocks.begin(),
-       E = Blocks.end(); I != E; ++I) {
-    IndexPair &IP = MBBRange[*I];
-    DEBUG(dbgs() << "  splitting for BB#" << (*I)->getNumber() << ": ["
-                 << IP.first << ';' << IP.second << ")\n");
-    assert(IP.first.isValid() && IP.second.isValid());
+  for (unsigned i = 0, e = sa_.LiveBlocks.size(); i != e; ++i) {
+    const SplitAnalysis::BlockInfo &BI = sa_.LiveBlocks[i];
+    if (!BI.Uses || !Blocks.count(BI.MBB))
+      continue;
 
     openIntv();
-    useIntv(enterIntvBefore(IP.first), leaveIntvAfter(IP.second));
+    SlotIndex SegStart = enterIntvBefore(BI.FirstUse);
+    if (BI.LastUse < BI.LastSplitPoint) {
+      useIntv(SegStart, leaveIntvAfter(BI.LastUse));
+    } else {
+      // THe last use os after tha last valid split point.
+      SlotIndex SegStop = leaveIntvBefore(BI.LastSplitPoint);
+      useIntv(SegStart, SegStop);
+      overlapIntv(SegStop, BI.LastUse);
+    }
     closeIntv();
   }
   finish();
diff --git a/lib/CodeGen/SplitKit.h b/lib/CodeGen/SplitKit.h
index 92945147ae7..2b593d5887e 100644
--- a/lib/CodeGen/SplitKit.h
+++ b/lib/CodeGen/SplitKit.h
@@ -407,6 +407,10 @@ public:
   /// Return the end of the live range.
   SlotIndex leaveIntvAfter(SlotIndex Idx);
 
+  /// leaveIntvBefore - Leave the open interval before the instruction at Idx.
+  /// Return the end of the live range.
+  SlotIndex leaveIntvBefore(SlotIndex Idx);
+
   /// leaveIntvAtTop - Leave the interval at the top of MBB.
   /// Add liveness from the MBB top to the copy.
   /// Return the end of the live range.
-- 
2.34.1