lib/CodeGen/RegisterScavenging.cpp

   1 //===-- RegisterScavenging.cpp - Machine register scavenging --------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // 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/TargetRegisterInfo.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 /// setUsed - Set the register and its sub-registers as being used.
  29 void RegScavenger::setUsed(unsigned Reg) {
  30   RegsAvailable.reset(Reg);
  31
  32   for (const unsigned *SubRegs = RegInfo->getSubRegisters(Reg);
  33        unsigned SubReg = *SubRegs; ++SubRegs)
  34     RegsAvailable.reset(SubReg);
  35 }
  36
  37 /// setUnused - Set the register and its sub-registers as being unused.
  38 void RegScavenger::setUnused(unsigned Reg) {
  39   RegsAvailable.set(Reg);
  40
  41   for (const unsigned *SubRegs = RegInfo->getSubRegisters(Reg);
  42        unsigned SubReg = *SubRegs; ++SubRegs)
  43     RegsAvailable.set(SubReg);
  44 }
  45
  46 void RegScavenger::enterBasicBlock(MachineBasicBlock *mbb) {
  47   const MachineFunction &MF = *mbb->getParent();
  48   const TargetMachine &TM = MF.getTarget();
  49   TII = TM.getInstrInfo();
  50   RegInfo = TM.getRegisterInfo();
  51
  52   assert((NumPhysRegs == 0 || NumPhysRegs == RegInfo->getNumRegs()) &&
  53          "Target changed?");
  54
  55   if (!MBB) {
  56     NumPhysRegs = RegInfo->getNumRegs();
  57     RegsAvailable.resize(NumPhysRegs);
  58
  59     // Create reserved registers bitvector.
  60     ReservedRegs = RegInfo->getReservedRegs(MF);
  61
  62     // Create callee-saved registers bitvector.
  63     CalleeSavedRegs.resize(NumPhysRegs);
  64     const unsigned *CSRegs = RegInfo->getCalleeSavedRegs();
  65     if (CSRegs != NULL)
  66       for (unsigned i = 0; CSRegs[i]; ++i)
  67         CalleeSavedRegs.set(CSRegs[i]);
  68   }
  69
  70   MBB = mbb;
  71   ScavengedReg = 0;
  72   ScavengedRC = NULL;
  73
  74   // All registers started out unused.
  75   RegsAvailable.set();
  76
  77   // Reserved registers are always used.
  78   RegsAvailable ^= ReservedRegs;
  79
  80   // Live-in registers are in use.
  81   if (!MBB->livein_empty())
  82     for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(),
  83            E = MBB->livein_end(); I != E; ++I)
  84       setUsed(*I);
  85
  86   Tracking = false;
  87 }
  88
  89 void RegScavenger::restoreScavengedReg() {
  90   if (!ScavengedReg)
  91     return;
  92
  93   TII->loadRegFromStackSlot(*MBB, MBBI, ScavengedReg,
  94                                 ScavengingFrameIndex, ScavengedRC);
  95   MachineBasicBlock::iterator II = prior(MBBI);
  96   RegInfo->eliminateFrameIndex(II, 0, this);
  97   setUsed(ScavengedReg);
  98   ScavengedReg = 0;
  99   ScavengedRC = NULL;
 100 }
 101
 102 void RegScavenger::forward() {
 103   // Move ptr forward.
 104   if (!Tracking) {
 105     MBBI = MBB->begin();
 106     Tracking = true;
 107   } else {
 108     assert(MBBI != MBB->end() && "Already at the end of the basic block!");
 109     MBBI = next(MBBI);
 110   }
 111
 112   MachineInstr *MI = MBBI;
 113   const TargetInstrDesc &TID = MI->getDesc();
 114
 115   // Reaching a terminator instruction. Restore a scavenged register (which
 116   // must be life out.
 117   if (TID.isTerminator())
 118     restoreScavengedReg();
 119
 120   // Process uses first.
 121   BitVector ChangedRegs(NumPhysRegs);
 122   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 123     const MachineOperand &MO = MI->getOperand(i);
 124     if (!MO.isRegister() || !MO.isUse())
 125       continue;
 126
 127     unsigned Reg = MO.getReg();
 128     if (Reg == 0) continue;
 129
 130     if (!isUsed(Reg)) {
 131       // Register has been scavenged. Restore it!
 132       if (Reg != ScavengedReg)
 133         assert(false && "Using an undefined register!");
 134       else
 135         restoreScavengedReg();
 136     }
 137
 138     if (MO.isKill() && !isReserved(Reg)) {
 139       ChangedRegs.set(Reg);
 140
 141       for (const unsigned *SubRegs = RegInfo->getSubRegisters(Reg);
 142            unsigned SubReg = *SubRegs; ++SubRegs)
 143         ChangedRegs.set(SubReg);
 144     }
 145   }
 146
 147   // Change states of all registers after all the uses are processed to guard
 148   // against multiple uses.
 149   setUnused(ChangedRegs);
 150
 151   // Process defs.
 152   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 153     const MachineOperand &MO = MI->getOperand(i);
 154
 155     if (!MO.isRegister() || !MO.isDef())
 156       continue;
 157
 158     unsigned Reg = MO.getReg();
 159
 160     // If it's dead upon def, then it is now free.
 161     if (MO.isDead()) {
 162       setUnused(Reg);
 163       continue;
 164     }
 165
 166     // Skip two-address destination operand.
 167     if (TID.findTiedToSrcOperand(i) != -1) {
 168       assert(isUsed(Reg) && "Using an undefined register!");
 169       continue;
 170     }
 171
 172     assert((isUnused(Reg) || isReserved(Reg)) &&
 173            "Re-defining a live register!");
 174     setUsed(Reg);
 175   }
 176 }
 177
 178 void RegScavenger::backward() {
 179   assert(Tracking && "Not tracking states!");
 180   assert(MBBI != MBB->begin() && "Already at start of basic block!");
 181   // Move ptr backward.
 182   MBBI = prior(MBBI);
 183
 184   MachineInstr *MI = MBBI;
 185   // Process defs first.
 186   const TargetInstrDesc &TID = MI->getDesc();
 187   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 188     const MachineOperand &MO = MI->getOperand(i);
 189     if (!MO.isRegister() || !MO.isDef())
 190       continue;
 191     // Skip two-address destination operand.
 192     if (TID.findTiedToSrcOperand(i) != -1)
 193       continue;
 194     unsigned Reg = MO.getReg();
 195     assert(isUsed(Reg));
 196     if (!isReserved(Reg))
 197       setUnused(Reg);
 198   }
 199
 200   // Process uses.
 201   BitVector ChangedRegs(NumPhysRegs);
 202   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 203     const MachineOperand &MO = MI->getOperand(i);
 204     if (!MO.isRegister() || !MO.isUse())
 205       continue;
 206     unsigned Reg = MO.getReg();
 207     if (Reg == 0)
 208       continue;
 209     assert(isUnused(Reg) || isReserved(Reg));
 210     ChangedRegs.set(Reg);
 211
 212     // Set the sub-registers as "used".
 213     for (const unsigned *SubRegs = RegInfo->getSubRegisters(Reg);
 214          unsigned SubReg = *SubRegs; ++SubRegs)
 215       ChangedRegs.set(SubReg);
 216   }
 217   setUsed(ChangedRegs);
 218 }
 219
 220 void RegScavenger::getRegsUsed(BitVector &used, bool includeReserved) {
 221   if (includeReserved)
 222     used = ~RegsAvailable;
 223   else
 224     used = ~RegsAvailable & ~ReservedRegs;
 225 }
 226
 227 /// CreateRegClassMask - Set the bits that represent the registers in the
 228 /// TargetRegisterClass.
 229 static void CreateRegClassMask(const TargetRegisterClass *RC, BitVector &Mask) {
 230   for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); I != E;
 231        ++I)
 232     Mask.set(*I);
 233 }
 234
 235 unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass,
 236                                      const BitVector &Candidates) const {
 237   // Mask off the registers which are not in the TargetRegisterClass.
 238   BitVector RegsAvailableCopy(NumPhysRegs, false);
 239   CreateRegClassMask(RegClass, RegsAvailableCopy);
 240   RegsAvailableCopy &= RegsAvailable;
 241
 242   // Restrict the search to candidates.
 243   RegsAvailableCopy &= Candidates;
 244
 245   // Returns the first unused (bit is set) register, or 0 is none is found.
 246   int Reg = RegsAvailableCopy.find_first();
 247   return (Reg == -1) ? 0 : Reg;
 248 }
 249
 250 unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass,
 251                                      bool ExCalleeSaved) const {
 252   // Mask off the registers which are not in the TargetRegisterClass.
 253   BitVector RegsAvailableCopy(NumPhysRegs, false);
 254   CreateRegClassMask(RegClass, RegsAvailableCopy);
 255   RegsAvailableCopy &= RegsAvailable;
 256
 257   // If looking for a non-callee-saved register, mask off all the callee-saved
 258   // registers.
 259   if (ExCalleeSaved)
 260     RegsAvailableCopy &= ~CalleeSavedRegs;
 261
 262   // Returns the first unused (bit is set) register, or 0 is none is found.
 263   int Reg = RegsAvailableCopy.find_first();
 264   return (Reg == -1) ? 0 : Reg;
 265 }
 266
 267 /// calcDistanceToUse - Calculate the distance to the first use of the
 268 /// specified register.
 269 static unsigned calcDistanceToUse(MachineBasicBlock *MBB,
 270                                   MachineBasicBlock::iterator I, unsigned Reg) {
 271   unsigned Dist = 0;
 272   I = next(I);
 273   while (I != MBB->end()) {
 274     Dist++;
 275     if (I->findRegisterUseOperandIdx(Reg) != -1)
 276         return Dist;
 277     I = next(I);
 278   }
 279   return Dist + 1;
 280 }
 281
 282 unsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC,
 283                                         MachineBasicBlock::iterator I,
 284                                         int SPAdj) {
 285   assert(ScavengingFrameIndex >= 0 &&
 286          "Cannot scavenge a register without an emergency spill slot!");
 287
 288   // Mask off the registers which are not in the TargetRegisterClass.
 289   BitVector Candidates(NumPhysRegs, false);
 290   CreateRegClassMask(RC, Candidates);
 291   Candidates ^= ReservedRegs;  // Do not include reserved registers.
 292
 293   // Exclude all the registers being used by the instruction.
 294   for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
 295     MachineOperand &MO = I->getOperand(i);
 296     if (MO.isRegister())
 297       Candidates.reset(MO.getReg());
 298   }
 299
 300   // Find the register whose use is furthest away.
 301   unsigned SReg = 0;
 302   unsigned MaxDist = 0;
 303   int Reg = Candidates.find_first();
 304   while (Reg != -1) {
 305     unsigned Dist = calcDistanceToUse(MBB, I, Reg);
 306     if (Dist >= MaxDist) {
 307       MaxDist = Dist;
 308       SReg = Reg;
 309     }
 310     Reg = Candidates.find_next(Reg);
 311   }
 312
 313   if (ScavengedReg != 0) {
 314     // First restore previously scavenged register.
 315     TII->loadRegFromStackSlot(*MBB, I, ScavengedReg,
 316                               ScavengingFrameIndex, ScavengedRC);
 317     MachineBasicBlock::iterator II = prior(I);
 318     RegInfo->eliminateFrameIndex(II, SPAdj, this);
 319   }
 320
 321   TII->storeRegToStackSlot(*MBB, I, SReg, true, ScavengingFrameIndex, RC);
 322   MachineBasicBlock::iterator II = prior(I);
 323   RegInfo->eliminateFrameIndex(II, SPAdj, this);
 324   ScavengedReg = SReg;
 325   ScavengedRC = RC;
 326
 327   return SReg;
 328 }