Live interval splitting:

When a live interval is being spilled, rather than creating short, non-spillable
intervals for every def / use, split the interval at BB boundaries. That is, for
every BB where the live interval is defined or used, create a new interval that
covers all the defs and uses in the BB.

This is designed to eliminate one common problem: multiple reloads of the same
value in a single basic block. Note, it does *not* decrease the number of spills
since no copies are inserted so the split intervals are *connected* through
spill and reloads (or rematerialization). The newly created intervals can be
spilled again, in that case, since it does not span multiple basic blocks, it's
spilled in the usual manner. However, it can reuse the same stack slot as the
previously split interval.

This is currently controlled by -split-intervals-at-bb.


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

1 files changed, 39 insertions, 10 deletions

diff --git a/lib/CodeGen/LiveVariables.cpp b/lib/CodeGen/LiveVariables.cpp
index 2af8bf316e..a42011d6f4 100644
--- a/lib/CodeGen/LiveVariables.cpp
+++ b/lib/CodeGen/LiveVariables.cpp
@@ -193,6 +193,7 @@ void LiveVariables::HandleVirtRegUse(VarInfo &VRInfo, MachineBasicBlock *MBB,
 }
 
 bool LiveVariables::addRegisterKilled(unsigned IncomingReg, MachineInstr *MI,
+                                      const MRegisterInfo *RegInfo,
                                       bool AddIfNotFound) {
   bool Found = false;
   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
@@ -224,6 +225,7 @@ bool LiveVariables::addRegisterKilled(unsigned IncomingReg, MachineInstr *MI,
 }
 
 bool LiveVariables::addRegisterDead(unsigned IncomingReg, MachineInstr *MI,
+                                    const MRegisterInfo *RegInfo,
                                     bool AddIfNotFound) {
   bool Found = false;
   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
@@ -331,7 +333,7 @@ bool LiveVariables::HandlePhysRegKill(unsigned Reg, MachineInstr *RefMI,
 void LiveVariables::addRegisterKills(unsigned Reg, MachineInstr *MI,
                                      SmallSet<unsigned, 4> &SubKills) {
   if (SubKills.count(Reg) == 0)
-    addRegisterKilled(Reg, MI, true);
+    addRegisterKilled(Reg, MI, RegInfo, true);
   else {
     for (const unsigned *SubRegs = RegInfo->getImmediateSubRegisters(Reg);
          unsigned SubReg = *SubRegs; ++SubRegs)
@@ -342,7 +344,7 @@ void LiveVariables::addRegisterKills(unsigned Reg, MachineInstr *MI,
 bool LiveVariables::HandlePhysRegKill(unsigned Reg, MachineInstr *RefMI) {
   SmallSet<unsigned, 4> SubKills;
   if (HandlePhysRegKill(Reg, RefMI, SubKills)) {
-    addRegisterKilled(Reg, RefMI, true);
+    addRegisterKilled(Reg, RefMI, RegInfo, true);
     return true;
   } else {
     // Some sub-registers are killed by another MI.
@@ -359,15 +361,15 @@ void LiveVariables::HandlePhysRegDef(unsigned Reg, MachineInstr *MI) {
     if (PhysRegUsed[Reg]) {
       if (!HandlePhysRegKill(Reg, LastRef)) {
         if (PhysRegPartUse[Reg])
-          addRegisterKilled(Reg, PhysRegPartUse[Reg], true);
+          addRegisterKilled(Reg, PhysRegPartUse[Reg], RegInfo, true);
       }
     } else if (PhysRegPartUse[Reg])
       // Add implicit use / kill to last partial use.
-      addRegisterKilled(Reg, PhysRegPartUse[Reg], true);
+      addRegisterKilled(Reg, PhysRegPartUse[Reg], RegInfo, true);
     else if (LastRef != MI)
       // Defined, but not used. However, watch out for cases where a super-reg
       // is also defined on the same MI.
-      addRegisterDead(Reg, LastRef);
+      addRegisterDead(Reg, LastRef, RegInfo);
   }
 
   for (const unsigned *SubRegs = RegInfo->getSubRegisters(Reg);
@@ -376,14 +378,14 @@ void LiveVariables::HandlePhysRegDef(unsigned Reg, MachineInstr *MI) {
       if (PhysRegUsed[SubReg]) {
         if (!HandlePhysRegKill(SubReg, LastRef)) {
           if (PhysRegPartUse[SubReg])
-            addRegisterKilled(SubReg, PhysRegPartUse[SubReg], true);
+            addRegisterKilled(SubReg, PhysRegPartUse[SubReg], RegInfo, true);
         }
       } else if (PhysRegPartUse[SubReg])
         // Add implicit use / kill to last use of a sub-register.
-        addRegisterKilled(SubReg, PhysRegPartUse[SubReg], true);
+        addRegisterKilled(SubReg, PhysRegPartUse[SubReg], RegInfo, true);
       else if (LastRef != MI)
         // This must be a def of the subreg on the same MI.
-        addRegisterDead(SubReg, LastRef);
+        addRegisterDead(SubReg, LastRef, RegInfo);
     }
   }
 
@@ -561,10 +563,10 @@ bool LiveVariables::runOnMachineFunction(MachineFunction &mf) {
     for (unsigned j = 0, e2 = VirtRegInfo[i].Kills.size(); j != e2; ++j) {
       if (VirtRegInfo[i].Kills[j] == VirtRegInfo[i].DefInst)
         addRegisterDead(i + MRegisterInfo::FirstVirtualRegister,
-                        VirtRegInfo[i].Kills[j]);
+                        VirtRegInfo[i].Kills[j], RegInfo);
       else
         addRegisterKilled(i + MRegisterInfo::FirstVirtualRegister,
-                          VirtRegInfo[i].Kills[j]);
+                          VirtRegInfo[i].Kills[j], RegInfo);
     }
 
   // Check to make sure there are no unreachable blocks in the MC CFG for the
@@ -618,6 +620,33 @@ void LiveVariables::instructionChanged(MachineInstr *OldMI,
   }
 }
 
+/// transferKillDeadInfo - Similar to instructionChanged except it does not
+/// update live variables internal data structures.
+void LiveVariables::transferKillDeadInfo(MachineInstr *OldMI,
+                                         MachineInstr *NewMI,
+                                         const MRegisterInfo *RegInfo) {
+  // If the instruction defines any virtual registers, update the VarInfo,
+  // kill and dead information for the instruction.
+  for (unsigned i = 0, e = OldMI->getNumOperands(); i != e; ++i) {
+    MachineOperand &MO = OldMI->getOperand(i);
+    if (MO.isRegister() && MO.getReg() &&
+        MRegisterInfo::isVirtualRegister(MO.getReg())) {
+      unsigned Reg = MO.getReg();
+      if (MO.isDef()) {
+        if (MO.isDead()) {
+          MO.unsetIsDead();
+          addRegisterDead(Reg, NewMI, RegInfo);
+        }
+      }
+      if (MO.isKill()) {
+        MO.unsetIsKill();
+        addRegisterKilled(Reg, NewMI, RegInfo);
+      }
+    }
+  }
+}
+
+
 /// removeVirtualRegistersKilled - Remove all killed info for the specified
 /// instruction.
 void LiveVariables::removeVirtualRegistersKilled(MachineInstr *MI) {