Simplify the handling of physreg defs and uses in RegAllocFast.

This adds extra security against using clobbered physregs, and it adds kill
markers to physreg uses.

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

2 files changed, 73 insertions, 110 deletions

diff --git a/lib/CodeGen/RegAllocFast.cpp b/lib/CodeGen/RegAllocFast.cpp
index e1066bf1e7..fde7125996 100644
--- a/lib/CodeGen/RegAllocFast.cpp
+++ b/lib/CodeGen/RegAllocFast.cpp
@@ -135,9 +135,10 @@ namespace {
                       LiveRegMap::iterator i, bool isKill);
     void spillVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI,
                       unsigned VirtReg, bool isKill);
-    void killPhysReg(unsigned PhysReg);
-    void spillPhysReg(MachineBasicBlock &MBB, MachineInstr *I,
-                      unsigned PhysReg, bool isKill);
+
+    void usePhysReg(MachineOperand&);
+    void definePhysReg(MachineBasicBlock &MBB, MachineInstr *MI,
+                       unsigned PhysReg, RegState NewState);
     LiveRegMap::iterator assignVirtToPhysReg(unsigned VirtReg,
                                              unsigned PhysReg);
     LiveRegMap::iterator allocVirtReg(MachineBasicBlock &MBB, MachineInstr *MI,
@@ -146,8 +147,6 @@ namespace {
                            unsigned OpNum, unsigned VirtReg, unsigned Hint);
     unsigned reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI,
                            unsigned OpNum, unsigned VirtReg, unsigned Hint);
-    void reservePhysReg(MachineBasicBlock &MBB, MachineInstr *MI,
-                        unsigned PhysReg);
     void spillAll(MachineBasicBlock &MBB, MachineInstr *MI);
     void setPhysReg(MachineOperand &MO, unsigned PhysReg);
   };
@@ -264,75 +263,106 @@ void RAFast::spillAll(MachineBasicBlock &MBB, MachineInstr *MI) {
     spillVirtReg(MBB, MI, Dirty[i], false);
 }
 
-/// killPhysReg - Kill any virtual register aliased by PhysReg.
-void RAFast::killPhysReg(unsigned PhysReg) {
-  // Fast path for the normal case.
-  switch (unsigned VirtReg = PhysRegState[PhysReg]) {
+/// usePhysReg - Handle the direct use of a physical register.
+/// Check that the register is not used by a virtreg.
+/// Kill the physreg, marking it free.
+/// This may add implicit kills to MO->getParent() and invalidate MO.
+void RAFast::usePhysReg(MachineOperand &MO) {
+  unsigned PhysReg = MO.getReg();
+  assert(TargetRegisterInfo::isPhysicalRegister(PhysReg) &&
+         "Bad usePhysReg operand");
+
+  switch (PhysRegState[PhysReg]) {
   case regDisabled:
     break;
-  case regFree:
-    return;
   case regReserved:
     PhysRegState[PhysReg] = regFree;
+    // Fall through
+  case regFree:
+    UsedInInstr.set(PhysReg);
+    MO.setIsKill();
     return;
   default:
-    killVirtReg(VirtReg);
-    return;
+    // The physreg was allocated to a virtual register. That means to value we
+    // wanted has been clobbered.
+    llvm_unreachable("Instruction uses an allocated register");
   }
 
-  // This is a disabled register, we have to check aliases.
+  // Maybe a superregister is reserved?
   for (const unsigned *AS = TRI->getAliasSet(PhysReg);
        unsigned Alias = *AS; ++AS) {
-    switch (unsigned VirtReg = PhysRegState[Alias]) {
+    switch (PhysRegState[Alias]) {
     case regDisabled:
-    case regFree:
       break;
     case regReserved:
+      assert(TRI->isSuperRegister(PhysReg, Alias) &&
+             "Instruction is not using a subregister of a reserved register");
+      // Leave the superregister in the working set.
       PhysRegState[Alias] = regFree;
+      UsedInInstr.set(Alias);
+      MO.getParent()->addRegisterKilled(Alias, TRI, true);
+      return;
+    case regFree:
+      if (TRI->isSuperRegister(PhysReg, Alias)) {
+        // Leave the superregister in the working set.
+        UsedInInstr.set(Alias);
+        MO.getParent()->addRegisterKilled(Alias, TRI, true);
+        return;
+      }
+      // Some other alias was in the working set - clear it.
+      PhysRegState[Alias] = regDisabled;
       break;
     default:
-      killVirtReg(VirtReg);
-      break;
+      llvm_unreachable("Instruction uses an alias of an allocated register");
     }
   }
+
+  // All aliases are disabled, bring register into working set.
+  PhysRegState[PhysReg] = regFree;
+  UsedInInstr.set(PhysReg);
+  MO.setIsKill();
 }
 
-/// spillPhysReg - Spill any dirty virtual registers that aliases PhysReg. If
-/// isKill is set, they are also killed.
-void RAFast::spillPhysReg(MachineBasicBlock &MBB, MachineInstr *MI,
-                           unsigned PhysReg, bool isKill) {
+/// definePhysReg - Mark PhysReg as reserved or free after spilling any
+/// virtregs. This is very similar to defineVirtReg except the physreg is
+/// reserved instead of allocated.
+void RAFast::definePhysReg(MachineBasicBlock &MBB, MachineInstr *MI,
+                           unsigned PhysReg, RegState NewState) {
+  UsedInInstr.set(PhysReg);
   switch (unsigned VirtReg = PhysRegState[PhysReg]) {
   case regDisabled:
     break;
+  default:
+    spillVirtReg(MBB, MI, VirtReg, true);
+    // Fall through.
   case regFree:
-    return;
   case regReserved:
-    if (isKill)
-      PhysRegState[PhysReg] = regFree;
-    return;
-  default:
-    spillVirtReg(MBB, MI, VirtReg, isKill);
+    PhysRegState[PhysReg] = NewState;
     return;
   }
 
-  // This is a disabled register, we have to check aliases.
+  // This is a disabled register, disable all aliases.
+  PhysRegState[PhysReg] = NewState;
   for (const unsigned *AS = TRI->getAliasSet(PhysReg);
        unsigned Alias = *AS; ++AS) {
+    UsedInInstr.set(Alias);
     switch (unsigned VirtReg = PhysRegState[Alias]) {
     case regDisabled:
-    case regFree:
-      break;
-    case regReserved:
-      if (isKill)
-        PhysRegState[Alias] = regFree;
       break;
     default:
-      spillVirtReg(MBB, MI, VirtReg, isKill);
+      spillVirtReg(MBB, MI, VirtReg, true);
+      // Fall through.
+    case regFree:
+    case regReserved:
+      PhysRegState[Alias] = regDisabled;
+      if (TRI->isSuperRegister(PhysReg, Alias))
+        return;
       break;
     }
   }
 }
 
+
 /// assignVirtToPhysReg - This method updates local state so that we know
 /// that PhysReg is the proper container for VirtReg now.  The physical
 /// register must not be used for anything else when this is called.
@@ -538,47 +568,6 @@ unsigned RAFast::reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI,
   return LR.PhysReg;
 }
 
-/// reservePhysReg - Mark PhysReg as reserved. This is very similar to
-/// defineVirtReg except the physreg is reserved instead of allocated.
-void RAFast::reservePhysReg(MachineBasicBlock &MBB, MachineInstr *MI,
-                            unsigned PhysReg) {
-  UsedInInstr.set(PhysReg);
-  switch (unsigned VirtReg = PhysRegState[PhysReg]) {
-  case regDisabled:
-    break;
-  case regFree:
-    PhysRegState[PhysReg] = regReserved;
-    return;
-  case regReserved:
-    return;
-  default:
-    spillVirtReg(MBB, MI, VirtReg, true);
-    PhysRegState[PhysReg] = regReserved;
-    return;
-  }
-
-  // This is a disabled register, disable all aliases.
-  for (const unsigned *AS = TRI->getAliasSet(PhysReg);
-       unsigned Alias = *AS; ++AS) {
-    UsedInInstr.set(Alias);
-    switch (unsigned VirtReg = PhysRegState[Alias]) {
-    case regDisabled:
-    case regFree:
-      break;
-    case regReserved:
-      // is a super register already reserved?
-      if (TRI->isSuperRegister(PhysReg, Alias))
-        return;
-      break;
-    default:
-      spillVirtReg(MBB, MI, VirtReg, true);
-      break;
-    }
-    PhysRegState[Alias] = regDisabled;
-  }
-  PhysRegState[PhysReg] = regReserved;
-}
-
 // setPhysReg - Change MO the refer the PhysReg, considering subregs.
 void RAFast::setPhysReg(MachineOperand &MO, unsigned PhysReg) {
   if (unsigned Idx = MO.getSubReg()) {
@@ -600,9 +589,9 @@ void RAFast::AllocateBasicBlock(MachineBasicBlock &MBB) {
   // Add live-in registers as live.
   for (MachineBasicBlock::livein_iterator I = MBB.livein_begin(),
          E = MBB.livein_end(); I != E; ++I)
-    reservePhysReg(MBB, MII, *I);
+    definePhysReg(MBB, MII, *I, regReserved);
 
-  SmallVector<unsigned, 8> VirtKills, PhysKills, PhysDefs;
+  SmallVector<unsigned, 8> VirtKills, PhysDefs;
   SmallVector<MachineInstr*, 32> Coalesced;
 
   // Otherwise, sequentially allocate each instruction in the MBB.
@@ -670,7 +659,6 @@ void RAFast::AllocateBasicBlock(MachineBasicBlock &MBB) {
 
     // First scan.
     // Mark physreg uses and early clobbers as used.
-    // Collect PhysKills.
     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
       MachineOperand &MO = MI->getOperand(i);
       if (!MO.isReg()) continue;
@@ -678,25 +666,14 @@ void RAFast::AllocateBasicBlock(MachineBasicBlock &MBB) {
       if (!Reg || !TargetRegisterInfo::isPhysicalRegister(Reg) ||
           ReservedRegs.test(Reg)) continue;
       if (MO.isUse()) {
-#ifndef NDEBUG
-        // We are using a physreg directly. It had better not be clobbered by a
-        // virtreg.
-        assert(PhysRegState[Reg] <= regReserved && "Using clobbered physreg");
-        if (PhysRegState[Reg] == regDisabled)
-          for (const unsigned *AS = TRI->getAliasSet(Reg);
-               unsigned Alias = *AS; ++AS)
-            assert(PhysRegState[Alias] <= regReserved &&
-                   "Physreg alias was clobbered");
-#endif
-        PhysKills.push_back(Reg); // Any clean physreg use is a kill.
-        UsedInInstr.set(Reg);
+        usePhysReg(MO);
       } else if (MO.isEarlyClobber()) {
-        spillPhysReg(MBB, MI, Reg, true);
-        UsedInInstr.set(Reg);
+        definePhysReg(MBB, MI, Reg, MO.isDead() ? regFree : regReserved);
         PhysDefs.push_back(Reg);
       }
     }
 
+
     // Second scan.
     // Allocate virtreg uses and early clobbers.
     // Collect VirtKills
@@ -723,11 +700,6 @@ void RAFast::AllocateBasicBlock(MachineBasicBlock &MBB) {
       killVirtReg(VirtKills[i]);
     VirtKills.clear();
 
-    // Process physreg kills
-    for (unsigned i = 0, e = PhysKills.size(); i != e; ++i)
-      killPhysReg(PhysKills[i]);
-    PhysKills.clear();
-
     MRI->addPhysRegsUsed(UsedInInstr);
 
     // Track registers defined by instruction - early clobbers at this point.
@@ -749,12 +721,8 @@ void RAFast::AllocateBasicBlock(MachineBasicBlock &MBB) {
 
       if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
         if (ReservedRegs.test(Reg)) continue;
-        if (MO.isImplicit())
-          spillPhysReg(MBB, MI, Reg, true);
-        else
-          reservePhysReg(MBB, MI, Reg);
-        if (MO.isDead())
-          PhysKills.push_back(Reg);
+        definePhysReg(MBB, MI, Reg, (MO.isImplicit() || MO.isDead()) ?
+                                    regFree : regReserved);
         continue;
       }
       unsigned PhysReg = defineVirtReg(MBB, MI, i, Reg, CopySrc);
@@ -777,11 +745,6 @@ void RAFast::AllocateBasicBlock(MachineBasicBlock &MBB) {
       killVirtReg(VirtKills[i]);
     VirtKills.clear();
 
-    // Process physreg deads.
-    for (unsigned i = 0, e = PhysKills.size(); i != e; ++i)
-      killPhysReg(PhysKills[i]);
-    PhysKills.clear();
-
     MRI->addPhysRegsUsed(UsedInInstr);
 
     if (CopyDst && CopyDst == CopySrc && CopyDstSub == CopySrcSub) {
diff --git a/test/CodeGen/X86/2008-09-18-inline-asm-2.ll b/test/CodeGen/X86/2008-09-18-inline-asm-2.ll
index d3a227d353..440094058c 100644
--- a/test/CodeGen/X86/2008-09-18-inline-asm-2.ll
+++ b/test/CodeGen/X86/2008-09-18-inline-asm-2.ll
@@ -1,6 +1,6 @@
 ; RUN: llc < %s -march=x86 | grep "#%ebp %esi %edi 8(%edx) %eax (%ebx)"
 ; RUN: llc < %s -march=x86 -regalloc=local | grep "#%edi %ebp %edx 8(%ebx) %eax (%esi)"
-; RUN: llc < %s -march=x86 -regalloc=fast  | grep "#%ecx %ebx %edx 8(%edi) %eax (%esi)"
+; RUN: llc < %s -march=x86 -regalloc=fast  | grep "#%edi %ebp %edx 8(%ebx) %eax (%esi)"
 
 ; The 1st, 2nd, 3rd and 5th registers above must all be different.  The registers
 ; referenced in the 4th and 6th operands must not be the same as the 1st or 5th