From 5c716bdccce2fa504e1aa0b67226165d181d2459 Mon Sep 17 00:00:00 2001
From: Jakob Stoklund Olesen <stoklund@2pi.dk>
Date: Tue, 8 Feb 2011 18:50:21 +0000
Subject: [PATCH] Add SplitEditor::overlapIntv() to create small ranges where
 both registers are live.

If a live range is used by a terminator instruction, and that live range needs
to leave the block on the stack or in a different register, it can be necessary
to have both sides of the split live at the terminator instruction.

Example:

  %vreg2 = COPY %vreg1
  JMP %vreg1

Becomes after spilling %vreg2:

  SPILL %vreg1
  JMP %vreg1

The spill doesn't kill the register as is normally the case.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@125102 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/CodeGen/RegAllocGreedy.cpp | 27 +++++++++++++++++++++++++--
 lib/CodeGen/SplitKit.cpp       | 16 ++++++++++++++++
 lib/CodeGen/SplitKit.h         | 12 ++++++++++++
 3 files changed, 53 insertions(+), 2 deletions(-)

diff --git a/lib/CodeGen/RegAllocGreedy.cpp b/lib/CodeGen/RegAllocGreedy.cpp
index ff0c790f887..be01bdce44c 100644
--- a/lib/CodeGen/RegAllocGreedy.cpp
+++ b/lib/CodeGen/RegAllocGreedy.cpp
@@ -746,6 +746,7 @@ void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg,
       assert(Use <= BI.LastUse && "Couldn't find last use");
       SlotIndex SegStart = SE.enterIntvBefore(Use);
       assert(SegStart >= IP.second && "Couldn't avoid interference");
+      assert(SegStart < BI.LastSplitPoint && "Impossible split point");
       SE.useIntv(SegStart, Stop);
       continue;
     }
@@ -798,8 +799,30 @@ void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg,
       if (!RegOut) {
         // Block is live-through, but exit bundle is on the stack.
         // Spill immediately after the last use.
-        DEBUG(dbgs() << ", uses, stack-out.\n");
-        SE.useIntv(Start, SE.leaveIntvAfter(BI.LastUse));
+        if (BI.LastUse < BI.LastSplitPoint) {
+          DEBUG(dbgs() << ", uses, stack-out.\n");
+          SE.useIntv(Start, SE.leaveIntvAfter(BI.LastUse));
+          continue;
+        }
+        // The last use is after the last split point, it is probably an
+        // indirect jump.
+        DEBUG(dbgs() << ", uses at " << BI.LastUse << " after split point "
+                     << BI.LastSplitPoint << ", stack-out.\n");
+        SlotIndex SegEnd;
+        if (BI.LastSplitPoint == Start)
+          SegEnd = SE.leaveIntvAtTop(*BI.MBB);
+        else {
+          MachineBasicBlock::iterator I =
+            LIS->getInstructionFromIndex(BI.LastSplitPoint);
+          do assert(I != BI.MBB->begin() && "Expected instruction");
+          while ((--I)->isDebugValue());
+          SegEnd = SE.leaveIntvAfter(LIS->getInstructionIndex(I));
+        }
+        SE.useIntv(Start, SegEnd);
+        // Run a double interval from the split to the last use.
+        // This makes it possible to spill the complement without affecting the
+        // indirect branch.
+        SE.overlapIntv(SegEnd, BI.LastUse);
         continue;
       }
       // Register is live-through.
diff --git a/lib/CodeGen/SplitKit.cpp b/lib/CodeGen/SplitKit.cpp
index 0c2a2cf4329..e26d909211c 100644
--- a/lib/CodeGen/SplitKit.cpp
+++ b/lib/CodeGen/SplitKit.cpp
@@ -882,6 +882,22 @@ SlotIndex SplitEditor::leaveIntvAtTop(MachineBasicBlock &MBB) {
   return VNI->def;
 }
 
+void SplitEditor::overlapIntv(SlotIndex Start, SlotIndex End) {
+  assert(OpenIdx && "openIntv not called before overlapIntv");
+  assert(Edit.getParent().getVNInfoAt(Start) ==
+         Edit.getParent().getVNInfoAt(End.getPrevSlot()) &&
+         "Parent changes value in extended range");
+  assert(Edit.get(0)->getVNInfoAt(Start) && "Start must come from leaveIntv*");
+  assert(LIS.getMBBFromIndex(Start) == LIS.getMBBFromIndex(End) &&
+         "Range cannot span basic blocks");
+
+  // Treat this as useIntv() for now. The complement interval will be extended
+  // as needed by mapValue().
+  DEBUG(dbgs() << "    overlapIntv [" << Start << ';' << End << "):");
+  RegAssign.insert(Start, End, OpenIdx);
+  DEBUG(dump());
+}
+
 /// closeIntv - Indicate that we are done editing the currently open
 /// LiveInterval, and ranges can be trimmed.
 void SplitEditor::closeIntv() {
diff --git a/lib/CodeGen/SplitKit.h b/lib/CodeGen/SplitKit.h
index 205341c19c8..4614796e700 100644
--- a/lib/CodeGen/SplitKit.h
+++ b/lib/CodeGen/SplitKit.h
@@ -377,6 +377,18 @@ public:
   /// Return the end of the live range.
   SlotIndex leaveIntvAtTop(MachineBasicBlock &MBB);
 
+  /// overlapIntv - Indicate that all instructions in range should use the open
+  /// interval, but also let the complement interval be live.
+  ///
+  /// This doubles the register pressure, but is sometimes required to deal with
+  /// register uses after the last valid split point.
+  ///
+  /// The Start index should be a return value from a leaveIntv* call, and End
+  /// should be in the same basic block. The parent interval must have the same
+  /// value across the range.
+  ///
+  void overlapIntv(SlotIndex Start, SlotIndex End);
+
   /// closeIntv - Indicate that we are done editing the currently open
   /// LiveInterval, and ranges can be trimmed.
   void closeIntv();
-- 
2.34.1