Register scavenger is now capable of scavenging. It spills a register whose use of furthest away to make it available.

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

2 files changed, 129 insertions, 4 deletions

diff --git a/include/llvm/CodeGen/RegisterScavenging.h b/include/llvm/CodeGen/RegisterScavenging.h
index 733c9e549d..c99c3eaab4 100644
--- a/include/llvm/CodeGen/RegisterScavenging.h
+++ b/include/llvm/CodeGen/RegisterScavenging.h
@@ -22,6 +22,8 @@
 
 namespace llvm {
 
+class MRegisterInfo;
+class TargetInstrInfo;
 class TargetRegisterClass;
 
 class RegScavenger {
@@ -33,6 +35,18 @@ class RegScavenger {
   /// registers.
   bool Tracking;
 
+  /// ScavengingFrameIndex - Special spill slot used for scavenging a register
+  /// post register allocation.
+  int ScavengingFrameIndex;
+
+  /// ScavengedReg - If none zero, the specific register is currently being
+  /// scavenged. That is, it is spilled to the special scavenging stack slot.
+  unsigned ScavengedReg;
+
+  /// ScavengedRC - Register class of the scavenged register.
+  ///
+  const TargetRegisterClass *ScavengedRC;
+
   /// RegStates - The current state of all the physical registers immediately
   /// before MBBI. One bit per physical register. If bit is set that means it's
   /// available, unset means the register is currently being used.
@@ -40,10 +54,12 @@ class RegScavenger {
 
 public:
   RegScavenger()
-    : MBB(NULL), NumPhysRegs(0), Tracking(false) {};
+    : MBB(NULL), NumPhysRegs(0), Tracking(false),
+      ScavengingFrameIndex(-1), ScavengedReg(0), ScavengedRC(NULL) {};
 
   RegScavenger(MachineBasicBlock *mbb)
-    : MBB(mbb), NumPhysRegs(0), Tracking(false) {};
+    : MBB(mbb), NumPhysRegs(0), Tracking(false),
+      ScavengingFrameIndex(-1), ScavengedReg(0), ScavengedRC(NULL) {};
 
   /// enterBasicBlock - Start tracking liveness from the begin of the specific
   /// basic block.
@@ -88,7 +104,24 @@ public:
   unsigned FindUnusedReg(const TargetRegisterClass *RegClass,
                          bool ExCalleeSaved = false) const;
 
+  /// setScavengingFrameIndex / getScavengingFrameIndex - accessor and setter of
+  /// ScavengingFrameIndex.
+  void setScavengingFrameIndex(int FI) { ScavengingFrameIndex = FI; }
+  int getScavengingFrameIndex() const { return ScavengingFrameIndex; }
+
+  /// scavengeRegister - Make a register of the specific register class
+  /// available and do the appropriate bookkeeping. Returns the scavenged
+  /// register.
+  unsigned scavengeRegister(const TargetRegisterClass *RegClass,
+                            MachineBasicBlock::iterator I);
+  unsigned scavengeRegister(const TargetRegisterClass *RegClass) {
+    return scavengeRegister(RegClass, MBBI);
+  }
+
 private:
+  const MRegisterInfo *RegInfo;
+  const TargetInstrInfo *TII;
+
   /// CalleeSavedrRegs - A bitvector of callee saved registers for the target.
   ///
   BitVector CalleeSavedRegs;
@@ -96,6 +129,10 @@ private:
   /// ReservedRegs - A bitvector of reserved registers.
   ///
   BitVector ReservedRegs;
+
+  /// restoreScavengedReg - Restore scavenged by loading it back from the
+  /// emergency spill slot. Mark it used.
+  void restoreScavengedReg();
 };
  
 } // End llvm namespace
diff --git a/lib/CodeGen/RegisterScavenging.cpp b/lib/CodeGen/RegisterScavenging.cpp
index c5389d922e..6197430b39 100644
--- a/lib/CodeGen/RegisterScavenging.cpp
+++ b/lib/CodeGen/RegisterScavenging.cpp
@@ -28,7 +28,8 @@ using namespace llvm;
 void RegScavenger::enterBasicBlock(MachineBasicBlock *mbb) {
   const MachineFunction &MF = *mbb->getParent();
   const TargetMachine &TM = MF.getTarget();
-  const MRegisterInfo *RegInfo = TM.getRegisterInfo();
+  TII = TM.getInstrInfo();
+  RegInfo = TM.getRegisterInfo();
 
   assert((NumPhysRegs == 0 || NumPhysRegs == RegInfo->getNumRegs()) &&
          "Target changed?");
@@ -65,6 +66,19 @@ void RegScavenger::enterBasicBlock(MachineBasicBlock *mbb) {
   Tracking = false;
 }
 
+void RegScavenger::restoreScavengedReg() {
+  if (!ScavengedReg)
+    return;
+
+  RegInfo->loadRegFromStackSlot(*MBB, MBBI, ScavengedReg,
+                                ScavengingFrameIndex, ScavengedRC);
+  MachineBasicBlock::iterator II = prior(MBBI);
+  RegInfo->eliminateFrameIndex(II, this);
+  setUsed(ScavengedReg);
+  ScavengedReg = 0;
+  ScavengedRC = NULL;
+}
+
 void RegScavenger::forward() {
   // Move ptr forward.
   if (!Tracking) {
@@ -76,6 +90,12 @@ void RegScavenger::forward() {
   }
 
   MachineInstr *MI = MBBI;
+
+  // Reaching a terminator instruction. Restore a scavenged register (which
+  // must be life out.
+  if (TII->isTerminatorInstr(MI->getOpcode()))
+    restoreScavengedReg();
+
   // Process uses first.
   BitVector ChangedRegs(NumPhysRegs);
   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
@@ -85,7 +105,13 @@ void RegScavenger::forward() {
     unsigned Reg = MO.getReg();
     if (Reg == 0)
       continue;
-    assert(isUsed(Reg));
+    if (!isUsed(Reg)) {
+      // Register has been scavenged. Restore it!
+      if (Reg != ScavengedReg)
+        assert(false);
+      else
+        restoreScavengedReg();
+    }
     if (MO.isKill() && !isReserved(Reg))
       ChangedRegs.set(Reg);
   }
@@ -191,3 +217,65 @@ unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass,
   int Reg = RegStatesCopy.find_first();
   return (Reg == -1) ? 0 : Reg;
 }
+
+/// 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->findRegisterUseOperand(Reg))
+        return Dist;
+    I = next(I);    
+  }
+  return Dist + 1;
+}
+
+unsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC,
+                                        MachineBasicBlock::iterator I) {
+  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.
+
+  // 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.isReg())
+      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);
+  }
+
+  if (ScavengedReg != 0) {
+    // First restore previously scavenged register.
+    RegInfo->loadRegFromStackSlot(*MBB, I, ScavengedReg,
+                                  ScavengingFrameIndex, ScavengedRC);
+    MachineBasicBlock::iterator II = prior(I);
+    RegInfo->eliminateFrameIndex(II, this);
+  }
+
+  RegInfo->storeRegToStackSlot(*MBB, I, SReg, ScavengingFrameIndex, RC);
+  MachineBasicBlock::iterator II = prior(I);
+  RegInfo->eliminateFrameIndex(II, this);
+  ScavengedReg = SReg;
+  ScavengedRC = RC;
+
+  return SReg;
+}