From b47fb384fc07e9c3af9cdf87d1cbdbcf76c331fc Mon Sep 17 00:00:00 2001
From: Cameron Zwarich <zwarich@apple.com>
Date: Mon, 11 Feb 2013 09:24:47 +0000
Subject: [PATCH] Add support for updating LiveIntervals to
 MachineBasicBlock::SplitCriticalEdge(). This is currently a bit hairier than
 it needs to be, since depending on where the split block resides the end
 ListEntry of the split block may be the end ListEntry of the original block
 or a new entry. Some changes to the SlotIndexes updating should make it
 possible to eliminate the two cases here.

This also isn't as optimized as it could be. In the future Liveinterval should
probably get a flag that indicates whether the LiveInterval is within a single
basic block. We could ignore all such intervals when splitting an edge.

llvm-svn: 174870
---
 llvm/lib/CodeGen/MachineBasicBlock.cpp | 68 ++++++++++++++++++++++++++++++++++
 llvm/lib/CodeGen/PHIElimination.cpp    |  2 +-
 2 files changed, 69 insertions(+), 1 deletion(-)

diff --git a/llvm/lib/CodeGen/MachineBasicBlock.cpp b/llvm/lib/CodeGen/MachineBasicBlock.cpp
index 7457cd5..7351302 100644
--- a/llvm/lib/CodeGen/MachineBasicBlock.cpp
+++ b/llvm/lib/CodeGen/MachineBasicBlock.cpp
@@ -15,10 +15,12 @@
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/Assembly/Writer.h"
+#include "llvm/CodeGen/LiveIntervalAnalysis.h"
 #include "llvm/CodeGen/LiveVariables.h"
 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/SlotIndexes.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/DataLayout.h"
@@ -769,6 +771,72 @@ MachineBasicBlock::SplitCriticalEdge(MachineBasicBlock *Succ, Pass *P) {
     LV->addNewBlock(NMBB, this, Succ);
   }
 
+  if (LiveIntervals *LIS = P->getAnalysisIfAvailable<LiveIntervals>()) {
+    // After splitting the edge and updating SlotIndexes, live intervals may be
+    // in one of two situations, depending on whether this block was the last in
+    // the function. If the original block was the last in the function, all live
+    // intervals will end prior to the beginning of the new split block. If the
+    // original block was not at the end of the function, all live intervals will
+    // extend to the end of the new split block.
+
+    bool isLastMBB =
+      llvm::next(MachineFunction::iterator(NMBB)) == getParent()->end();
+
+    SlotIndex StartIndex = Indexes->getMBBEndIdx(this);
+    SlotIndex PrevIndex = StartIndex.getPrevSlot();
+    SlotIndex EndIndex = Indexes->getMBBEndIdx(NMBB);
+
+    // Find the registers used from NMBB in PHIs in Succ.
+    SmallSet<unsigned, 8> PHISrcRegs;
+    for (MachineBasicBlock::instr_iterator
+         I = Succ->instr_begin(), E = Succ->instr_end();
+         I != E && I->isPHI(); ++I) {
+      for (unsigned ni = 1, ne = I->getNumOperands(); ni != ne; ni += 2) {
+        if (I->getOperand(ni+1).getMBB() == NMBB) {
+          MachineOperand &MO = I->getOperand(ni);
+          unsigned Reg = MO.getReg();
+          PHISrcRegs.insert(Reg);
+          if (MO.isUndef() || !isLastMBB)
+            break;
+
+          LiveInterval &LI = LIS->getInterval(Reg);
+          VNInfo *VNI = LI.getVNInfoAt(PrevIndex);
+          assert(VNI && "PHI sources should be live out of their predecessors.");
+          LI.addRange(LiveRange(StartIndex, EndIndex, VNI));
+        }
+      }
+    }
+
+    MachineRegisterInfo *MRI = &getParent()->getRegInfo();
+    for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
+      unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
+      if (PHISrcRegs.count(Reg) || !LIS->hasInterval(Reg))
+        continue;
+
+      LiveInterval &LI = LIS->getInterval(Reg);
+      if (!LI.liveAt(PrevIndex))
+        continue;
+
+      bool isLiveOut = false;
+      for (MachineBasicBlock::succ_iterator SI = succ_begin(),
+           SE = succ_end(); SI != SE; ++SI) {
+        MachineBasicBlock *SuccMBB = *SI == NMBB ? Succ : *SI;
+        if (LI.liveAt(LIS->getMBBStartIdx(SuccMBB))) {
+          isLiveOut = true;
+          break;
+        }
+      }
+
+      if (isLiveOut && isLastMBB) {
+        VNInfo *VNI = LI.getVNInfoAt(PrevIndex);
+        assert(VNI && "LiveInterval should have VNInfo where it is live.");
+        LI.addRange(LiveRange(StartIndex, EndIndex, VNI));
+      } else if (!isLiveOut && !isLastMBB) {
+        LI.removeRange(StartIndex, EndIndex);
+      }
+    }
+  }
+
   if (MachineDominatorTree *MDT =
       P->getAnalysisIfAvailable<MachineDominatorTree>()) {
     // Update dominator information.
diff --git a/llvm/lib/CodeGen/PHIElimination.cpp b/llvm/lib/CodeGen/PHIElimination.cpp
index bf2b95f..aa84a60 100644
--- a/llvm/lib/CodeGen/PHIElimination.cpp
+++ b/llvm/lib/CodeGen/PHIElimination.cpp
@@ -129,7 +129,7 @@ bool PHIElimination::runOnMachineFunction(MachineFunction &MF) {
 
   // Split critical edges to help the coalescer. This does not yet support
   // updating LiveIntervals, so we disable it.
-  if (!DisableEdgeSplitting && LV && !LIS) {
+  if (!DisableEdgeSplitting && (LV || LIS)) {
     MachineLoopInfo *MLI = getAnalysisIfAvailable<MachineLoopInfo>();
     for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I)
       Changed |= SplitPHIEdges(MF, *I, MLI);
-- 
2.7.4