lib/CodeGen/RegisterScavenging.cpp

   1 //===-- RegisterScavenging.cpp - Machine register scavenging --------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the Evan Cheng and is distributed under the
   6 // University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the machine register scavenger. It can provide
  11 // information such as unused register at any point in a machine basic block.
  12 // It also provides a mechanism to make registers availbale by evicting them
  13 // to spill slots.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #define DEBUG_TYPE "reg-scavenging"
  18 #include "llvm/CodeGen/RegisterScavenging.h"
  19 #include "llvm/CodeGen/MachineFunction.h"
  20 #include "llvm/CodeGen/MachineBasicBlock.h"
  21 #include "llvm/CodeGen/MachineInstr.h"
  22 #include "llvm/Target/MRegisterInfo.h"
  23 #include "llvm/Target/TargetInstrInfo.h"
  24 #include "llvm/Target/TargetMachine.h"
  25 #include "llvm/ADT/STLExtras.h"
  26 using namespace llvm;
  27
  28 void RegScavenger::enterBasicBlock(MachineBasicBlock *mbb) {
  29   const MachineFunction &MF = *mbb->getParent();
  30   const TargetMachine &TM = MF.getTarget();
  31   TII = TM.getInstrInfo();
  32   RegInfo = TM.getRegisterInfo();
  33
  34   assert((NumPhysRegs == 0 || NumPhysRegs == RegInfo->getNumRegs()) &&
  35          "Target changed?");
  36
  37   if (!MBB) {
  38     NumPhysRegs = RegInfo->getNumRegs();
  39     RegStates.resize(NumPhysRegs);
  40
  41     // Create reserved registers bitvector.
  42     ReservedRegs = RegInfo->getReservedRegs(MF);
  43
  44     // Create callee-saved registers bitvector.
  45     CalleeSavedRegs.resize(NumPhysRegs);
  46     const unsigned *CSRegs = RegInfo->getCalleeSavedRegs();
  47     if (CSRegs != NULL)
  48       for (unsigned i = 0; CSRegs[i]; ++i)
  49         CalleeSavedRegs.set(CSRegs[i]);
  50   }
  51
  52   MBB = mbb;
  53
  54   // All registers started out unused.
  55   RegStates.set();
  56
  57   // Reserved registers are always used.
  58   RegStates ^= ReservedRegs;
  59
  60   // Live-in registers are in use.
  61   if (!MBB->livein_empty())
  62     for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(),
  63            E = MBB->livein_end(); I != E; ++I)
  64       setUsed(*I);
  65
  66   Tracking = false;
  67 }
  68
  69 void RegScavenger::restoreScavengedReg() {
  70   if (!ScavengedReg)
  71     return;
  72
  73   RegInfo->loadRegFromStackSlot(*MBB, MBBI, ScavengedReg,
  74                                 ScavengingFrameIndex, ScavengedRC);
  75   MachineBasicBlock::iterator II = prior(MBBI);
  76   RegInfo->eliminateFrameIndex(II, this);
  77   setUsed(ScavengedReg);
  78   ScavengedReg = 0;
  79   ScavengedRC = NULL;
  80 }
  81
  82 void RegScavenger::forward() {
  83   // Move ptr forward.
  84   if (!Tracking) {
  85     MBBI = MBB->begin();
  86     Tracking = true;
  87   } else {
  88     assert(MBBI != MBB->end() && "Already at the end of the basic block!");
  89     MBBI = next(MBBI);
  90   }
  91
  92   MachineInstr *MI = MBBI;
  93
  94   // Reaching a terminator instruction. Restore a scavenged register (which
  95   // must be life out.
  96   if (TII->isTerminatorInstr(MI->getOpcode()))
  97     restoreScavengedReg();
  98
  99   // Process uses first.
 100   BitVector ChangedRegs(NumPhysRegs);
 101   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 102     const MachineOperand &MO = MI->getOperand(i);
 103     if (!MO.isReg() || !MO.isUse())
 104       continue;
 105     unsigned Reg = MO.getReg();
 106     if (Reg == 0)
 107       continue;
 108     if (!isUsed(Reg)) {
 109       // Register has been scavenged. Restore it!
 110       if (Reg != ScavengedReg)
 111         assert(false);
 112       else
 113         restoreScavengedReg();
 114     }
 115     if (MO.isKill() && !isReserved(Reg))
 116       ChangedRegs.set(Reg);
 117   }
 118   // Change states of all registers after all the uses are processed to guard
 119   // against multiple uses.
 120   setUnused(ChangedRegs);
 121
 122   // Process defs.
 123   const TargetInstrDescriptor *TID = MI->getInstrDescriptor();
 124   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 125     const MachineOperand &MO = MI->getOperand(i);
 126     if (!MO.isReg() || !MO.isDef())
 127       continue;
 128     unsigned Reg = MO.getReg();
 129     // If it's dead upon def, then it is now free.
 130     if (MO.isDead()) {
 131       setUnused(Reg);
 132       continue;
 133     }
 134     // Skip two-address destination operand.
 135     if (TID->findTiedToSrcOperand(i) != -1) {
 136       assert(isUsed(Reg));
 137       continue;
 138     }
 139     assert(isUnused(Reg) || isReserved(Reg));
 140     setUsed(Reg);
 141   }
 142 }
 143
 144 void RegScavenger::backward() {
 145   assert(Tracking && "Not tracking states!");
 146   assert(MBBI != MBB->begin() && "Already at start of basic block!");
 147   // Move ptr backward.
 148   MBBI = prior(MBBI);
 149
 150   MachineInstr *MI = MBBI;
 151   // Process defs first.
 152   const TargetInstrDescriptor *TID = MI->getInstrDescriptor();
 153   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 154     const MachineOperand &MO = MI->getOperand(i);
 155     if (!MO.isReg() || !MO.isDef())
 156       continue;
 157     // Skip two-address destination operand.
 158     if (TID->findTiedToSrcOperand(i) != -1)
 159       continue;
 160     unsigned Reg = MO.getReg();
 161     assert(isUsed(Reg));
 162     if (!isReserved(Reg))
 163       setUnused(Reg);
 164   }
 165
 166   // Process uses.
 167   BitVector ChangedRegs(NumPhysRegs);
 168   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 169     const MachineOperand &MO = MI->getOperand(i);
 170     if (!MO.isReg() || !MO.isUse())
 171       continue;
 172     unsigned Reg = MO.getReg();
 173     if (Reg == 0)
 174       continue;
 175     assert(isUnused(Reg) || isReserved(Reg));
 176     ChangedRegs.set(Reg);
 177   }
 178   setUsed(ChangedRegs);
 179 }
 180
 181 /// CreateRegClassMask - Set the bits that represent the registers in the
 182 /// TargetRegisterClass.
 183 static void CreateRegClassMask(const TargetRegisterClass *RC, BitVector &Mask) {
 184   for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); I != E;
 185        ++I)
 186     Mask.set(*I);
 187 }
 188
 189 unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass,
 190                                      const BitVector &Candidates) const {
 191   // Mask off the registers which are not in the TargetRegisterClass.
 192   BitVector RegStatesCopy(NumPhysRegs, false);
 193   CreateRegClassMask(RegClass, RegStatesCopy);
 194   RegStatesCopy &= RegStates;
 195
 196   // Restrict the search to candidates.
 197   RegStatesCopy &= Candidates;
 198
 199   // Returns the first unused (bit is set) register, or 0 is none is found.
 200   int Reg = RegStatesCopy.find_first();
 201   return (Reg == -1) ? 0 : Reg;
 202 }
 203
 204 unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass,
 205                                      bool ExCalleeSaved) const {
 206   // Mask off the registers which are not in the TargetRegisterClass.
 207   BitVector RegStatesCopy(NumPhysRegs, false);
 208   CreateRegClassMask(RegClass, RegStatesCopy);
 209   RegStatesCopy &= RegStates;
 210
 211   // If looking for a non-callee-saved register, mask off all the callee-saved
 212   // registers.
 213   if (ExCalleeSaved)
 214     RegStatesCopy &= ~CalleeSavedRegs;
 215
 216   // Returns the first unused (bit is set) register, or 0 is none is found.
 217   int Reg = RegStatesCopy.find_first();
 218   return (Reg == -1) ? 0 : Reg;
 219 }
 220
 221 /// calcDistanceToUse - Calculate the distance to the first use of the
 222 /// specified register.
 223 static unsigned calcDistanceToUse(MachineBasicBlock *MBB,
 224                                   MachineBasicBlock::iterator I, unsigned Reg) {
 225   unsigned Dist = 0;
 226   I = next(I);
 227   while (I != MBB->end()) {
 228     Dist++;
 229     if (I->findRegisterUseOperand(Reg))
 230         return Dist;
 231     I = next(I);
 232   }
 233   return Dist + 1;
 234 }
 235
 236 unsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC,
 237                                         MachineBasicBlock::iterator I) {
 238   assert(ScavengingFrameIndex >= 0 &&
 239          "Cannot scavenge a register without an emergency spill slot!");
 240
 241   // Mask off the registers which are not in the TargetRegisterClass.
 242   BitVector Candidates(NumPhysRegs, false);
 243   CreateRegClassMask(RC, Candidates);
 244   Candidates ^= ReservedRegs;  // Do not include reserved registers.
 245
 246   // Exclude all the registers being used by the instruction.
 247   for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
 248     MachineOperand &MO = I->getOperand(i);
 249     if (MO.isReg())
 250       Candidates.reset(MO.getReg());
 251   }
 252
 253   // Find the register whose use is furtherest aaway.
 254   unsigned SReg = 0;
 255   unsigned MaxDist = 0;
 256   int Reg = Candidates.find_first();
 257   while (Reg != -1) {
 258     unsigned Dist = calcDistanceToUse(MBB, I, Reg);
 259     if (Dist >= MaxDist) {
 260       MaxDist = Dist;
 261       SReg = Reg;
 262     }
 263     Reg = Candidates.find_next(Reg);
 264   }
 265
 266   if (ScavengedReg != 0) {
 267     // First restore previously scavenged register.
 268     RegInfo->loadRegFromStackSlot(*MBB, I, ScavengedReg,
 269                                   ScavengingFrameIndex, ScavengedRC);
 270     MachineBasicBlock::iterator II = prior(I);
 271     RegInfo->eliminateFrameIndex(II, this);
 272   }
 273
 274   RegInfo->storeRegToStackSlot(*MBB, I, SReg, ScavengingFrameIndex, RC);
 275   MachineBasicBlock::iterator II = prior(I);
 276   RegInfo->eliminateFrameIndex(II, this);
 277   ScavengedReg = SReg;
 278   ScavengedRC = RC;
 279
 280   return SReg;
 281 }