X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FRegisterScavenging.cpp;h=ca02aa1b81436721f72eec90325ecdf7451f432e;hb=340d596509129de8c3fa9dbe4184a2b148b78757;hp=15592128480e2a2655f4f217489b196ea5334b91;hpb=92dfe2001e96f6e2b6d327e8816f38033f88b295;p=oota-llvm.git

diff --git a/lib/CodeGen/RegisterScavenging.cpp b/lib/CodeGen/RegisterScavenging.cpp
index 15592128480..ca02aa1b814 100644
--- a/lib/CodeGen/RegisterScavenging.cpp
+++ b/lib/CodeGen/RegisterScavenging.cpp
@@ -2,83 +2,122 @@
 //
 //                     The LLVM Compiler Infrastructure
 //
-// This file was developed by the Evan Cheng and is distributed under the
-// University of Illinois Open Source License. See LICENSE.TXT for details.
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the machine register scavenger. It can provide
-// information such as unused register at any point in a machine basic block.
-// It also provides a mechanism to make registers availbale by evicting them
-// to spill slots.
+// information, such as unused registers, at any point in a machine basic block.
+// It also provides a mechanism to make registers available by evicting them to
+// spill slots.
 //
 //===----------------------------------------------------------------------===//
 
 #define DEBUG_TYPE "reg-scavenging"
 #include "llvm/CodeGen/RegisterScavenging.h"
+#include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineInstr.h"
-#include "llvm/Target/MRegisterInfo.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/ErrorHandling.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/Target/TargetRegisterInfo.h"
 #include "llvm/Target/TargetInstrInfo.h"
 #include "llvm/Target/TargetMachine.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/STLExtras.h"
 using namespace llvm;
 
+/// setUsed - Set the register and its sub-registers as being used.
+void RegScavenger::setUsed(unsigned Reg) {
+  RegsAvailable.reset(Reg);
+
+  for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
+       unsigned SubReg = *SubRegs; ++SubRegs)
+    RegsAvailable.reset(SubReg);
+}
+
+bool RegScavenger::isAliasUsed(unsigned Reg) const {
+  if (isUsed(Reg))
+    return true;
+  for (const unsigned *R = TRI->getAliasSet(Reg); *R; ++R)
+    if (isUsed(*R))
+      return true;
+  return false;
+}
+
+void RegScavenger::initRegState() {
+  ScavengedReg = 0;
+  ScavengedRC = NULL;
+  ScavengeRestore = NULL;
+
+  // All registers started out unused.
+  RegsAvailable.set();
+
+  // Reserved registers are always used.
+  RegsAvailable ^= ReservedRegs;
+
+  if (!MBB)
+    return;
+
+  // Live-in registers are in use.
+  for (MachineBasicBlock::livein_iterator I = MBB->livein_begin(),
+         E = MBB->livein_end(); I != E; ++I)
+    setUsed(*I);
+
+  // Pristine CSRs are also unavailable.
+  BitVector PR = MBB->getParent()->getFrameInfo()->getPristineRegs(MBB);
+  for (int I = PR.find_first(); I>0; I = PR.find_next(I))
+    setUsed(I);
+}
+
 void RegScavenger::enterBasicBlock(MachineBasicBlock *mbb) {
-  const MachineFunction &MF = *mbb->getParent();
+  MachineFunction &MF = *mbb->getParent();
   const TargetMachine &TM = MF.getTarget();
   TII = TM.getInstrInfo();
-  RegInfo = TM.getRegisterInfo();
+  TRI = TM.getRegisterInfo();
+  MRI = &MF.getRegInfo();
 
-  assert((NumPhysRegs == 0 || NumPhysRegs == RegInfo->getNumRegs()) &&
+  assert((NumPhysRegs == 0 || NumPhysRegs == TRI->getNumRegs()) &&
          "Target changed?");
 
+  // Self-initialize.
   if (!MBB) {
-    NumPhysRegs = RegInfo->getNumRegs();
+    NumPhysRegs = TRI->getNumRegs();
     RegsAvailable.resize(NumPhysRegs);
 
     // Create reserved registers bitvector.
-    ReservedRegs = RegInfo->getReservedRegs(MF);
+    ReservedRegs = TRI->getReservedRegs(MF);
 
     // Create callee-saved registers bitvector.
     CalleeSavedRegs.resize(NumPhysRegs);
-    const unsigned *CSRegs = RegInfo->getCalleeSavedRegs();
+    const unsigned *CSRegs = TRI->getCalleeSavedRegs();
     if (CSRegs != NULL)
       for (unsigned i = 0; CSRegs[i]; ++i)
         CalleeSavedRegs.set(CSRegs[i]);
   }
 
   MBB = mbb;
-  ScavengedReg = 0;
-  ScavengedRC = NULL;
-
-  // All registers started out unused.
-  RegsAvailable.set();
-
-  // Reserved registers are always used.
-  RegsAvailable ^= ReservedRegs;
-
-  // Live-in registers are in use.
-  if (!MBB->livein_empty())
-    for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(),
-           E = MBB->livein_end(); I != E; ++I)
-      setUsed(*I);
+  initRegState();
 
   Tracking = false;
 }
 
-void RegScavenger::restoreScavengedReg() {
-  if (!ScavengedReg)
-    return;
+void RegScavenger::addRegWithSubRegs(BitVector &BV, unsigned Reg) {
+  BV.set(Reg);
+  for (const unsigned *R = TRI->getSubRegisters(Reg); *R; R++)
+    BV.set(*R);
+}
 
-  RegInfo->loadRegFromStackSlot(*MBB, MBBI, ScavengedReg,
-                                ScavengingFrameIndex, ScavengedRC);
-  MachineBasicBlock::iterator II = prior(MBBI);
-  RegInfo->eliminateFrameIndex(II, 0, this);
-  setUsed(ScavengedReg);
-  ScavengedReg = 0;
-  ScavengedRC = NULL;
+void RegScavenger::addRegWithAliases(BitVector &BV, unsigned Reg) {
+  BV.set(Reg);
+  for (const unsigned *R = TRI->getAliasSet(Reg); *R; R++)
+    BV.set(*R);
 }
 
 void RegScavenger::forward() {
@@ -87,98 +126,106 @@ void RegScavenger::forward() {
     MBBI = MBB->begin();
     Tracking = true;
   } else {
-    assert(MBBI != MBB->end() && "Already at the end of the basic block!");
-    MBBI = next(MBBI);
+    assert(MBBI != MBB->end() && "Already past the end of the basic block!");
+    MBBI = llvm::next(MBBI);
   }
+  assert(MBBI != MBB->end() && "Already at the end of the basic block!");
 
   MachineInstr *MI = MBBI;
 
-  // Reaching a terminator instruction. Restore a scavenged register (which
-  // must be life out.
-  if (TII->isTerminatorInstr(MI->getOpcode()))
-    restoreScavengedReg();
+  if (MI == ScavengeRestore) {
+    ScavengedReg = 0;
+    ScavengedRC = NULL;
+    ScavengeRestore = NULL;
+  }
 
-  // Process uses first.
-  BitVector ChangedRegs(NumPhysRegs);
+  if (MI->isDebugValue())
+    return;
+
+  // Find out which registers are early clobbered, killed, defined, and marked
+  // def-dead in this instruction.
+  // FIXME: The scavenger is not predication aware. If the instruction is
+  // predicated, conservatively assume "kill" markers do not actually kill the
+  // register. Similarly ignores "dead" markers.
+  bool isPred = TII->isPredicated(MI);
+  BitVector EarlyClobberRegs(NumPhysRegs);
+  BitVector KillRegs(NumPhysRegs);
+  BitVector DefRegs(NumPhysRegs);
+  BitVector DeadRegs(NumPhysRegs);
   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
     const MachineOperand &MO = MI->getOperand(i);
-    if (!MO.isRegister() || !MO.isUse())
+    if (!MO.isReg())
       continue;
     unsigned Reg = MO.getReg();
-    if (Reg == 0)
+    if (!Reg || isReserved(Reg))
       continue;
-    if (!isUsed(Reg)) {
-      // Register has been scavenged. Restore it!
-      if (Reg != ScavengedReg)
-        assert(false && "Using an undefined register!");
+
+    if (MO.isUse()) {
+      // Ignore undef uses.
+      if (MO.isUndef())
+        continue;
+      // Two-address operands implicitly kill.
+      if (!isPred && (MO.isKill() || MI->isRegTiedToDefOperand(i)))
+        addRegWithSubRegs(KillRegs, Reg);
+    } else {
+      assert(MO.isDef());
+      if (!isPred && MO.isDead())
+        addRegWithSubRegs(DeadRegs, Reg);
       else
-        restoreScavengedReg();
+        addRegWithSubRegs(DefRegs, Reg);
+      if (MO.isEarlyClobber())
+        addRegWithAliases(EarlyClobberRegs, Reg);
     }
-    if (MO.isKill() && !isReserved(Reg))
-      ChangedRegs.set(Reg);
   }
-  // Change states of all registers after all the uses are processed to guard
-  // against multiple uses.
-  setUnused(ChangedRegs);
 
-  // Process defs.
-  const TargetInstrDescriptor *TID = MI->getInstrDescriptor();
+  // Verify uses and defs.
   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
     const MachineOperand &MO = MI->getOperand(i);
-    if (!MO.isRegister() || !MO.isDef())
+    if (!MO.isReg())
       continue;
     unsigned Reg = MO.getReg();
-    // If it's dead upon def, then it is now free.
-    if (MO.isDead()) {
-      setUnused(Reg);
-      continue;
-    }
-    // Skip two-address destination operand.
-    if (TID->findTiedToSrcOperand(i) != -1) {
-      assert(isUsed(Reg) && "Using an undefined register!");
+    if (!Reg || isReserved(Reg))
       continue;
+    if (MO.isUse()) {
+      if (MO.isUndef())
+        continue;
+      if (!isUsed(Reg)) {
+        // Check if it's partial live: e.g.
+        // D0 = insert_subreg D0<undef>, S0
+        // ... D0
+        // The problem is the insert_subreg could be eliminated. The use of
+        // D0 is using a partially undef value. This is not *incorrect* since
+        // S1 is can be freely clobbered.
+        // Ideally we would like a way to model this, but leaving the
+        // insert_subreg around causes both correctness and performance issues.
+        bool SubUsed = false;
+        for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
+             unsigned SubReg = *SubRegs; ++SubRegs)
+          if (isUsed(SubReg)) {
+            SubUsed = true;
+            break;
+          }
+        assert(SubUsed && "Using an undefined register!");
+        (void)SubUsed;
+      }
+      assert((!EarlyClobberRegs.test(Reg) || MI->isRegTiedToDefOperand(i)) &&
+             "Using an early clobbered register!");
+    } else {
+      assert(MO.isDef());
+#if 0
+      // FIXME: Enable this once we've figured out how to correctly transfer
+      // implicit kills during codegen passes like the coalescer.
+      assert((KillRegs.test(Reg) || isUnused(Reg) ||
+              isLiveInButUnusedBefore(Reg, MI, MBB, TRI, MRI)) &&
+             "Re-defining a live register!");
+#endif
     }
-    assert((isUnused(Reg) || isReserved(Reg)) &&
-           "Re-defining a live register!");
-    setUsed(Reg);
-  }
-}
-
-void RegScavenger::backward() {
-  assert(Tracking && "Not tracking states!");
-  assert(MBBI != MBB->begin() && "Already at start of basic block!");
-  // Move ptr backward.
-  MBBI = prior(MBBI);
-
-  MachineInstr *MI = MBBI;
-  // Process defs first.
-  const TargetInstrDescriptor *TID = MI->getInstrDescriptor();
-  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
-    const MachineOperand &MO = MI->getOperand(i);
-    if (!MO.isRegister() || !MO.isDef())
-      continue;
-    // Skip two-address destination operand.
-    if (TID->findTiedToSrcOperand(i) != -1)
-      continue;
-    unsigned Reg = MO.getReg();
-    assert(isUsed(Reg));
-    if (!isReserved(Reg))
-      setUnused(Reg);
   }
 
-  // Process uses.
-  BitVector ChangedRegs(NumPhysRegs);
-  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
-    const MachineOperand &MO = MI->getOperand(i);
-    if (!MO.isRegister() || !MO.isUse())
-      continue;
-    unsigned Reg = MO.getReg();
-    if (Reg == 0)
-      continue;
-    assert(isUnused(Reg) || isReserved(Reg));
-    ChangedRegs.set(Reg);
-  }
-  setUsed(ChangedRegs);
+  // Commit the changes.
+  setUnused(KillRegs);
+  setUnused(DeadRegs);
+  setUsed(DefRegs);
 }
 
 void RegScavenger::getRegsUsed(BitVector &used, bool includeReserved) {
@@ -188,105 +235,162 @@ void RegScavenger::getRegsUsed(BitVector &used, bool includeReserved) {
     used = ~RegsAvailable & ~ReservedRegs;
 }
 
-/// CreateRegClassMask - Set the bits that represent the registers in the
-/// TargetRegisterClass.
-static void CreateRegClassMask(const TargetRegisterClass *RC, BitVector &Mask) {
-  for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); I != E;
-       ++I)
-    Mask.set(*I);
+unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RC) const {
+  for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end();
+       I != E; ++I)
+    if (!isAliasUsed(*I)) {
+      DEBUG(dbgs() << "Scavenger found unused reg: " << TRI->getName(*I) <<
+            "\n");
+      return *I;
+    }
+  return 0;
+}
+
+/// getRegsAvailable - Return all available registers in the register class
+/// in Mask.
+BitVector RegScavenger::getRegsAvailable(const TargetRegisterClass *RC) {
+  BitVector Mask(TRI->getNumRegs());
+  for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end();
+       I != E; ++I)
+    if (!isAliasUsed(*I))
+      Mask.set(*I);
+  return Mask;
 }
 
-unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass,
-                                     const BitVector &Candidates) const {
-  // Mask off the registers which are not in the TargetRegisterClass.
-  BitVector RegsAvailableCopy(NumPhysRegs, false);
-  CreateRegClassMask(RegClass, RegsAvailableCopy);
-  RegsAvailableCopy &= RegsAvailable;
+/// findSurvivorReg - Return the candidate register that is unused for the
+/// longest after StargMII. UseMI is set to the instruction where the search
+/// stopped.
+///
+/// No more than InstrLimit instructions are inspected.
+///
+unsigned RegScavenger::findSurvivorReg(MachineBasicBlock::iterator StartMI,
+                                       BitVector &Candidates,
+                                       unsigned InstrLimit,
+                                       MachineBasicBlock::iterator &UseMI) {
+  int Survivor = Candidates.find_first();
+  assert(Survivor > 0 && "No candidates for scavenging");
+
+  MachineBasicBlock::iterator ME = MBB->getFirstTerminator();
+  assert(StartMI != ME && "MI already at terminator");
+  MachineBasicBlock::iterator RestorePointMI = StartMI;
+  MachineBasicBlock::iterator MI = StartMI;
+
+  bool inVirtLiveRange = false;
+  for (++MI; InstrLimit > 0 && MI != ME; ++MI, --InstrLimit) {
+    if (MI->isDebugValue()) {
+      ++InstrLimit; // Don't count debug instructions
+      continue;
+    }
+    bool isVirtKillInsn = false;
+    bool isVirtDefInsn = false;
+    // Remove any candidates touched by instruction.
+    for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
+      const MachineOperand &MO = MI->getOperand(i);
+      if (!MO.isReg() || MO.isUndef() || !MO.getReg())
+        continue;
+      if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) {
+        if (MO.isDef())
+          isVirtDefInsn = true;
+        else if (MO.isKill())
+          isVirtKillInsn = true;
+        continue;
+      }
+      Candidates.reset(MO.getReg());
+      for (const unsigned *R = TRI->getAliasSet(MO.getReg()); *R; R++)
+        Candidates.reset(*R);
+    }
+    // If we're not in a virtual reg's live range, this is a valid
+    // restore point.
+    if (!inVirtLiveRange) RestorePointMI = MI;
 
-  // Restrict the search to candidates.
-  RegsAvailableCopy &= Candidates;
+    // Update whether we're in the live range of a virtual register
+    if (isVirtKillInsn) inVirtLiveRange = false;
+    if (isVirtDefInsn) inVirtLiveRange = true;
 
-  // Returns the first unused (bit is set) register, or 0 is none is found.
-  int Reg = RegsAvailableCopy.find_first();
-  return (Reg == -1) ? 0 : Reg;
-}
+    // Was our survivor untouched by this instruction?
+    if (Candidates.test(Survivor))
+      continue;
 
-unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass,
-                                     bool ExCalleeSaved) const {
-  // Mask off the registers which are not in the TargetRegisterClass.
-  BitVector RegsAvailableCopy(NumPhysRegs, false);
-  CreateRegClassMask(RegClass, RegsAvailableCopy);
-  RegsAvailableCopy &= RegsAvailable;
-
-  // If looking for a non-callee-saved register, mask off all the callee-saved
-  // registers.
-  if (ExCalleeSaved)
-    RegsAvailableCopy &= ~CalleeSavedRegs;
-
-  // Returns the first unused (bit is set) register, or 0 is none is found.
-  int Reg = RegsAvailableCopy.find_first();
-  return (Reg == -1) ? 0 : Reg;
-}
+    // All candidates gone?
+    if (Candidates.none())
+      break;
 
-/// calcDistanceToUse - Calculate the distance to the first use of the
-/// specified register.
-static unsigned calcDistanceToUse(MachineBasicBlock *MBB,
-                                  MachineBasicBlock::iterator I, unsigned Reg) {
-  unsigned Dist = 0;
-  I = next(I);
-  while (I != MBB->end()) {
-    Dist++;
-    if (I->findRegisterUseOperandIdx(Reg) != -1)
-        return Dist;
-    I = next(I);    
+    Survivor = Candidates.find_first();
   }
-  return Dist + 1;
+  // If we ran off the end, that's where we want to restore.
+  if (MI == ME) RestorePointMI = ME;
+  assert (RestorePointMI != StartMI &&
+          "No available scavenger restore location!");
+
+  // We ran out of candidates, so stop the search.
+  UseMI = RestorePointMI;
+  return Survivor;
 }
 
 unsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC,
                                         MachineBasicBlock::iterator I,
                                         int SPAdj) {
-  assert(ScavengingFrameIndex >= 0 &&
-         "Cannot scavenge a register without an emergency spill slot!");
-
-  // Mask off the registers which are not in the TargetRegisterClass.
-  BitVector Candidates(NumPhysRegs, false);
-  CreateRegClassMask(RC, Candidates);
-  Candidates ^= ReservedRegs;  // Do not include reserved registers.
+  // Consider all allocatable registers in the register class initially
+  BitVector Candidates =
+    TRI->getAllocatableSet(*I->getParent()->getParent(), RC);
 
   // Exclude all the registers being used by the instruction.
   for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
     MachineOperand &MO = I->getOperand(i);
-    if (MO.isRegister())
+    if (MO.isReg() && MO.getReg() != 0 &&
+        !TargetRegisterInfo::isVirtualRegister(MO.getReg()))
       Candidates.reset(MO.getReg());
   }
 
-  // Find the register whose use is furtherest aaway.
-  unsigned SReg = 0;
-  unsigned MaxDist = 0;
-  int Reg = Candidates.find_first();
-  while (Reg != -1) {
-    unsigned Dist = calcDistanceToUse(MBB, I, Reg);
-    if (Dist >= MaxDist) {
-      MaxDist = Dist;
-      SReg = Reg;
-    }
-    Reg = Candidates.find_next(Reg);
+  // Try to find a register that's unused if there is one, as then we won't
+  // have to spill. Search explicitly rather than masking out based on
+  // RegsAvailable, as RegsAvailable does not take aliases into account.
+  // That's what getRegsAvailable() is for.
+  BitVector Available = getRegsAvailable(RC);
+
+  if ((Candidates & Available).any())
+     Candidates &= Available;
+
+  // Find the register whose use is furthest away.
+  MachineBasicBlock::iterator UseMI;
+  unsigned SReg = findSurvivorReg(I, Candidates, 25, UseMI);
+
+  // If we found an unused register there is no reason to spill it.
+  if (!isAliasUsed(SReg)) {
+    DEBUG(dbgs() << "Scavenged register: " << TRI->getName(SReg) << "\n");
+    return SReg;
   }
 
-  if (ScavengedReg != 0) {
-    // First restore previously scavenged register.
-    RegInfo->loadRegFromStackSlot(*MBB, I, ScavengedReg,
-                                  ScavengingFrameIndex, ScavengedRC);
+  assert(ScavengedReg == 0 &&
+         "Scavenger slot is live, unable to scavenge another register!");
+
+  // Avoid infinite regress
+  ScavengedReg = SReg;
+
+  // If the target knows how to save/restore the register, let it do so;
+  // otherwise, use the emergency stack spill slot.
+  if (!TRI->saveScavengerRegister(*MBB, I, UseMI, RC, SReg)) {
+    // Spill the scavenged register before I.
+    assert(ScavengingFrameIndex >= 0 &&
+           "Cannot scavenge register without an emergency spill slot!");
+    TII->storeRegToStackSlot(*MBB, I, SReg, true, ScavengingFrameIndex, RC,TRI);
     MachineBasicBlock::iterator II = prior(I);
-    RegInfo->eliminateFrameIndex(II, SPAdj, this);
+    TRI->eliminateFrameIndex(II, SPAdj, this);
+
+    // Restore the scavenged register before its use (or first terminator).
+    TII->loadRegFromStackSlot(*MBB, UseMI, SReg, ScavengingFrameIndex, RC, TRI);
+    II = prior(UseMI);
+    TRI->eliminateFrameIndex(II, SPAdj, this);
   }
 
-  RegInfo->storeRegToStackSlot(*MBB, I, SReg, ScavengingFrameIndex, RC);
-  MachineBasicBlock::iterator II = prior(I);
-  RegInfo->eliminateFrameIndex(II, SPAdj, this);
-  ScavengedReg = SReg;
+  ScavengeRestore = prior(UseMI);
+
+  // Doing this here leads to infinite regress.
+  // ScavengedReg = SReg;
   ScavengedRC = RC;
 
+  DEBUG(dbgs() << "Scavenged register (with spill): " << TRI->getName(SReg) <<
+        "\n");
+
   return SReg;
 }