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     RegsAvailable.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   ScavengedReg = 0;
  54   ScavengedRC = NULL;
  55
  56   // All registers started out unused.
  57   RegsAvailable.set();
  58
  59   // Reserved registers are always used.
  60   RegsAvailable ^= ReservedRegs;
  61
  62   // Live-in registers are in use.
  63   if (!MBB->livein_empty())
  64     for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(),
  65            E = MBB->livein_end(); I != E; ++I)
  66       setUsed(*I);
  67
  68   Tracking = false;
  69 }
  70
  71 void RegScavenger::restoreScavengedReg() {
  72   if (!ScavengedReg)
  73     return;
  74
  75   RegInfo->loadRegFromStackSlot(*MBB, MBBI, ScavengedReg,
  76                                 ScavengingFrameIndex, ScavengedRC);
  77   MachineBasicBlock::iterator II = prior(MBBI);
  78   RegInfo->eliminateFrameIndex(II, 0, this);
  79   setUsed(ScavengedReg);
  80   ScavengedReg = 0;
  81   ScavengedRC = NULL;
  82 }
  83
  84 void RegScavenger::forward() {
  85   // Move ptr forward.
  86   if (!Tracking) {
  87     MBBI = MBB->begin();
  88     Tracking = true;
  89   } else {
  90     assert(MBBI != MBB->end() && "Already at the end of the basic block!");
  91     MBBI = next(MBBI);
  92   }
  93
  94   MachineInstr *MI = MBBI;
  95
  96   // Reaching a terminator instruction. Restore a scavenged register (which
  97   // must be life out.
  98   if (TII->isTerminatorInstr(MI->getOpcode()))
  99     restoreScavengedReg();
 100
 101   // Process uses first.
 102   BitVector ChangedRegs(NumPhysRegs);
 103   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 104     const MachineOperand &MO = MI->getOperand(i);
 105     if (!MO.isReg() || !MO.isUse())
 106       continue;
 107     unsigned Reg = MO.getReg();
 108     if (Reg == 0)
 109       continue;
 110     if (!isUsed(Reg)) {
 111       // Register has been scavenged. Restore it!
 112       if (Reg != ScavengedReg)
 113         assert(false);
 114       else
 115         restoreScavengedReg();
 116     }
 117     if (MO.isKill() && !isReserved(Reg))
 118       ChangedRegs.set(Reg);
 119   }
 120   // Change states of all registers after all the uses are processed to guard
 121   // against multiple uses.
 122   setUnused(ChangedRegs);
 123
 124   // Process defs.
 125   const TargetInstrDescriptor *TID = MI->getInstrDescriptor();
 126   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 127     const MachineOperand &MO = MI->getOperand(i);
 128     if (!MO.isReg() || !MO.isDef())
 129       continue;
 130     unsigned Reg = MO.getReg();
 131     // If it's dead upon def, then it is now free.
 132     if (MO.isDead()) {
 133       setUnused(Reg);
 134       continue;
 135     }
 136     // Skip two-address destination operand.
 137     if (TID->findTiedToSrcOperand(i) != -1) {
 138       assert(isUsed(Reg));
 139       continue;
 140     }
 141     assert(isUnused(Reg) || isReserved(Reg));
 142     setUsed(Reg);
 143   }
 144 }
 145
 146 void RegScavenger::backward() {
 147   assert(Tracking && "Not tracking states!");
 148   assert(MBBI != MBB->begin() && "Already at start of basic block!");
 149   // Move ptr backward.
 150   MBBI = prior(MBBI);
 151
 152   MachineInstr *MI = MBBI;
 153   // Process defs first.
 154   const TargetInstrDescriptor *TID = MI->getInstrDescriptor();
 155   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 156     const MachineOperand &MO = MI->getOperand(i);
 157     if (!MO.isReg() || !MO.isDef())
 158       continue;
 159     // Skip two-address destination operand.
 160     if (TID->findTiedToSrcOperand(i) != -1)
 161       continue;
 162     unsigned Reg = MO.getReg();
 163     assert(isUsed(Reg));
 164     if (!isReserved(Reg))
 165       setUnused(Reg);
 166   }
 167
 168   // Process uses.
 169   BitVector ChangedRegs(NumPhysRegs);
 170   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 171     const MachineOperand &MO = MI->getOperand(i);
 172     if (!MO.isReg() || !MO.isUse())
 173       continue;
 174     unsigned Reg = MO.getReg();
 175     if (Reg == 0)
 176       continue;
 177     assert(isUnused(Reg) || isReserved(Reg));
 178     ChangedRegs.set(Reg);
 179   }
 180   setUsed(ChangedRegs);
 181 }
 182
 183 void RegScavenger::getRegsUsed(BitVector &used, bool includeReserved) {
 184   if (includeReserved)
 185     used = ~RegsAvailable;
 186   else
 187     used = ~RegsAvailable & ~ReservedRegs;
 188 }
 189
 190 /// CreateRegClassMask - Set the bits that represent the registers in the
 191 /// TargetRegisterClass.
 192 static void CreateRegClassMask(const TargetRegisterClass *RC, BitVector &Mask) {
 193   for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); I != E;
 194        ++I)
 195     Mask.set(*I);
 196 }
 197
 198 unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass,
 199                                      const BitVector &Candidates) const {
 200   // Mask off the registers which are not in the TargetRegisterClass.
 201   BitVector RegsAvailableCopy(NumPhysRegs, false);
 202   CreateRegClassMask(RegClass, RegsAvailableCopy);
 203   RegsAvailableCopy &= RegsAvailable;
 204
 205   // Restrict the search to candidates.
 206   RegsAvailableCopy &= Candidates;
 207
 208   // Returns the first unused (bit is set) register, or 0 is none is found.
 209   int Reg = RegsAvailableCopy.find_first();
 210   return (Reg == -1) ? 0 : Reg;
 211 }
 212
 213 unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass,
 214                                      bool ExCalleeSaved) const {
 215   // Mask off the registers which are not in the TargetRegisterClass.
 216   BitVector RegsAvailableCopy(NumPhysRegs, false);
 217   CreateRegClassMask(RegClass, RegsAvailableCopy);
 218   RegsAvailableCopy &= RegsAvailable;
 219
 220   // If looking for a non-callee-saved register, mask off all the callee-saved
 221   // registers.
 222   if (ExCalleeSaved)
 223     RegsAvailableCopy &= ~CalleeSavedRegs;
 224
 225   // Returns the first unused (bit is set) register, or 0 is none is found.
 226   int Reg = RegsAvailableCopy.find_first();
 227   return (Reg == -1) ? 0 : Reg;
 228 }
 229
 230 /// calcDistanceToUse - Calculate the distance to the first use of the
 231 /// specified register.
 232 static unsigned calcDistanceToUse(MachineBasicBlock *MBB,
 233                                   MachineBasicBlock::iterator I, unsigned Reg) {
 234   unsigned Dist = 0;
 235   I = next(I);
 236   while (I != MBB->end()) {
 237     Dist++;
 238     if (I->findRegisterUseOperandIdx(Reg) != -1)
 239         return Dist;
 240     I = next(I);
 241   }
 242   return Dist + 1;
 243 }
 244
 245 unsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC,
 246                                         MachineBasicBlock::iterator I,
 247                                         int SPAdj) {
 248   assert(ScavengingFrameIndex >= 0 &&
 249          "Cannot scavenge a register without an emergency spill slot!");
 250
 251   // Mask off the registers which are not in the TargetRegisterClass.
 252   BitVector Candidates(NumPhysRegs, false);
 253   CreateRegClassMask(RC, Candidates);
 254   Candidates ^= ReservedRegs;  // Do not include reserved registers.
 255
 256   // Exclude all the registers being used by the instruction.
 257   for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
 258     MachineOperand &MO = I->getOperand(i);
 259     if (MO.isReg())
 260       Candidates.reset(MO.getReg());
 261   }
 262
 263   // Find the register whose use is furtherest aaway.
 264   unsigned SReg = 0;
 265   unsigned MaxDist = 0;
 266   int Reg = Candidates.find_first();
 267   while (Reg != -1) {
 268     unsigned Dist = calcDistanceToUse(MBB, I, Reg);
 269     if (Dist >= MaxDist) {
 270       MaxDist = Dist;
 271       SReg = Reg;
 272     }
 273     Reg = Candidates.find_next(Reg);
 274   }
 275
 276   if (ScavengedReg != 0) {
 277     // First restore previously scavenged register.
 278     RegInfo->loadRegFromStackSlot(*MBB, I, ScavengedReg,
 279                                   ScavengingFrameIndex, ScavengedRC);
 280     MachineBasicBlock::iterator II = prior(I);
 281     RegInfo->eliminateFrameIndex(II, SPAdj, this);
 282   }
 283
 284   RegInfo->storeRegToStackSlot(*MBB, I, SReg, ScavengingFrameIndex, RC);
 285   MachineBasicBlock::iterator II = prior(I);
 286   RegInfo->eliminateFrameIndex(II, SPAdj, this);
 287   ScavengedReg = SReg;
 288   ScavengedRC = RC;
 289
 290   return SReg;
 291 }