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/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.isRegister() || !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 && "Using an undefined register!");
 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.isRegister() || !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) && "Using an undefined register!");
 139       continue;
 140     }
 141     assert((isUnused(Reg) || isReserved(Reg)) &&
 142            "Re-defining a live register!");
 143     setUsed(Reg);
 144   }
 145 }
 146
 147 void RegScavenger::backward() {
 148   assert(Tracking && "Not tracking states!");
 149   assert(MBBI != MBB->begin() && "Already at start of basic block!");
 150   // Move ptr backward.
 151   MBBI = prior(MBBI);
 152
 153   MachineInstr *MI = MBBI;
 154   // Process defs first.
 155   const TargetInstrDescriptor *TID = MI->getInstrDescriptor();
 156   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 157     const MachineOperand &MO = MI->getOperand(i);
 158     if (!MO.isRegister() || !MO.isDef())
 159       continue;
 160     // Skip two-address destination operand.
 161     if (TID->findTiedToSrcOperand(i) != -1)
 162       continue;
 163     unsigned Reg = MO.getReg();
 164     assert(isUsed(Reg));
 165     if (!isReserved(Reg))
 166       setUnused(Reg);
 167   }
 168
 169   // Process uses.
 170   BitVector ChangedRegs(NumPhysRegs);
 171   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 172     const MachineOperand &MO = MI->getOperand(i);
 173     if (!MO.isRegister() || !MO.isUse())
 174       continue;
 175     unsigned Reg = MO.getReg();
 176     if (Reg == 0)
 177       continue;
 178     assert(isUnused(Reg) || isReserved(Reg));
 179     ChangedRegs.set(Reg);
 180   }
 181   setUsed(ChangedRegs);
 182 }
 183
 184 void RegScavenger::getRegsUsed(BitVector &used, bool includeReserved) {
 185   if (includeReserved)
 186     used = ~RegsAvailable;
 187   else
 188     used = ~RegsAvailable & ~ReservedRegs;
 189 }
 190
 191 /// CreateRegClassMask - Set the bits that represent the registers in the
 192 /// TargetRegisterClass.
 193 static void CreateRegClassMask(const TargetRegisterClass *RC, BitVector &Mask) {
 194   for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); I != E;
 195        ++I)
 196     Mask.set(*I);
 197 }
 198
 199 unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass,
 200                                      const BitVector &Candidates) const {
 201   // Mask off the registers which are not in the TargetRegisterClass.
 202   BitVector RegsAvailableCopy(NumPhysRegs, false);
 203   CreateRegClassMask(RegClass, RegsAvailableCopy);
 204   RegsAvailableCopy &= RegsAvailable;
 205
 206   // Restrict the search to candidates.
 207   RegsAvailableCopy &= Candidates;
 208
 209   // Returns the first unused (bit is set) register, or 0 is none is found.
 210   int Reg = RegsAvailableCopy.find_first();
 211   return (Reg == -1) ? 0 : Reg;
 212 }
 213
 214 unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass,
 215                                      bool ExCalleeSaved) const {
 216   // Mask off the registers which are not in the TargetRegisterClass.
 217   BitVector RegsAvailableCopy(NumPhysRegs, false);
 218   CreateRegClassMask(RegClass, RegsAvailableCopy);
 219   RegsAvailableCopy &= RegsAvailable;
 220
 221   // If looking for a non-callee-saved register, mask off all the callee-saved
 222   // registers.
 223   if (ExCalleeSaved)
 224     RegsAvailableCopy &= ~CalleeSavedRegs;
 225
 226   // Returns the first unused (bit is set) register, or 0 is none is found.
 227   int Reg = RegsAvailableCopy.find_first();
 228   return (Reg == -1) ? 0 : Reg;
 229 }
 230
 231 /// calcDistanceToUse - Calculate the distance to the first use of the
 232 /// specified register.
 233 static unsigned calcDistanceToUse(MachineBasicBlock *MBB,
 234                                   MachineBasicBlock::iterator I, unsigned Reg) {
 235   unsigned Dist = 0;
 236   I = next(I);
 237   while (I != MBB->end()) {
 238     Dist++;
 239     if (I->findRegisterUseOperandIdx(Reg) != -1)
 240         return Dist;
 241     I = next(I);
 242   }
 243   return Dist + 1;
 244 }
 245
 246 unsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC,
 247                                         MachineBasicBlock::iterator I,
 248                                         int SPAdj) {
 249   assert(ScavengingFrameIndex >= 0 &&
 250          "Cannot scavenge a register without an emergency spill slot!");
 251
 252   // Mask off the registers which are not in the TargetRegisterClass.
 253   BitVector Candidates(NumPhysRegs, false);
 254   CreateRegClassMask(RC, Candidates);
 255   Candidates ^= ReservedRegs;  // Do not include reserved registers.
 256
 257   // Exclude all the registers being used by the instruction.
 258   for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
 259     MachineOperand &MO = I->getOperand(i);
 260     if (MO.isRegister())
 261       Candidates.reset(MO.getReg());
 262   }
 263
 264   // Find the register whose use is furtherest aaway.
 265   unsigned SReg = 0;
 266   unsigned MaxDist = 0;
 267   int Reg = Candidates.find_first();
 268   while (Reg != -1) {
 269     unsigned Dist = calcDistanceToUse(MBB, I, Reg);
 270     if (Dist >= MaxDist) {
 271       MaxDist = Dist;
 272       SReg = Reg;
 273     }
 274     Reg = Candidates.find_next(Reg);
 275   }
 276
 277   if (ScavengedReg != 0) {
 278     // First restore previously scavenged register.
 279     RegInfo->loadRegFromStackSlot(*MBB, I, ScavengedReg,
 280                                   ScavengingFrameIndex, ScavengedRC);
 281     MachineBasicBlock::iterator II = prior(I);
 282     RegInfo->eliminateFrameIndex(II, SPAdj, this);
 283   }
 284
 285   RegInfo->storeRegToStackSlot(*MBB, I, SReg, true, ScavengingFrameIndex, RC);
 286   MachineBasicBlock::iterator II = prior(I);
 287   RegInfo->eliminateFrameIndex(II, SPAdj, this);
 288   ScavengedReg = SReg;
 289   ScavengedRC = RC;
 290
 291   return SReg;
 292 }