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   ScavengedReg = 0;
  54   ScavengedRC = NULL;
  55
  56   // All registers started out unused.
  57   RegStates.set();
  58
  59   // Reserved registers are always used.
  60   RegStates ^= 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, 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 /// CreateRegClassMask - Set the bits that represent the registers in the
 184 /// TargetRegisterClass.
 185 static void CreateRegClassMask(const TargetRegisterClass *RC, BitVector &Mask) {
 186   for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); I != E;
 187        ++I)
 188     Mask.set(*I);
 189 }
 190
 191 unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass,
 192                                      const BitVector &Candidates) const {
 193   // Mask off the registers which are not in the TargetRegisterClass.
 194   BitVector RegStatesCopy(NumPhysRegs, false);
 195   CreateRegClassMask(RegClass, RegStatesCopy);
 196   RegStatesCopy &= RegStates;
 197
 198   // Restrict the search to candidates.
 199   RegStatesCopy &= Candidates;
 200
 201   // Returns the first unused (bit is set) register, or 0 is none is found.
 202   int Reg = RegStatesCopy.find_first();
 203   return (Reg == -1) ? 0 : Reg;
 204 }
 205
 206 unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass,
 207                                      bool ExCalleeSaved) const {
 208   // Mask off the registers which are not in the TargetRegisterClass.
 209   BitVector RegStatesCopy(NumPhysRegs, false);
 210   CreateRegClassMask(RegClass, RegStatesCopy);
 211   RegStatesCopy &= RegStates;
 212
 213   // If looking for a non-callee-saved register, mask off all the callee-saved
 214   // registers.
 215   if (ExCalleeSaved)
 216     RegStatesCopy &= ~CalleeSavedRegs;
 217
 218   // Returns the first unused (bit is set) register, or 0 is none is found.
 219   int Reg = RegStatesCopy.find_first();
 220   return (Reg == -1) ? 0 : Reg;
 221 }
 222
 223 /// calcDistanceToUse - Calculate the distance to the first use of the
 224 /// specified register.
 225 static unsigned calcDistanceToUse(MachineBasicBlock *MBB,
 226                                   MachineBasicBlock::iterator I, unsigned Reg) {
 227   unsigned Dist = 0;
 228   I = next(I);
 229   while (I != MBB->end()) {
 230     Dist++;
 231     if (I->findRegisterUseOperand(Reg))
 232         return Dist;
 233     I = next(I);
 234   }
 235   return Dist + 1;
 236 }
 237
 238 unsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC,
 239                                         MachineBasicBlock::iterator I) {
 240   assert(ScavengingFrameIndex >= 0 &&
 241          "Cannot scavenge a register without an emergency spill slot!");
 242
 243   // Mask off the registers which are not in the TargetRegisterClass.
 244   BitVector Candidates(NumPhysRegs, false);
 245   CreateRegClassMask(RC, Candidates);
 246   Candidates ^= ReservedRegs;  // Do not include reserved registers.
 247
 248   // Exclude all the registers being used by the instruction.
 249   for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
 250     MachineOperand &MO = I->getOperand(i);
 251     if (MO.isReg())
 252       Candidates.reset(MO.getReg());
 253   }
 254
 255   // Find the register whose use is furtherest aaway.
 256   unsigned SReg = 0;
 257   unsigned MaxDist = 0;
 258   int Reg = Candidates.find_first();
 259   while (Reg != -1) {
 260     unsigned Dist = calcDistanceToUse(MBB, I, Reg);
 261     if (Dist >= MaxDist) {
 262       MaxDist = Dist;
 263       SReg = Reg;
 264     }
 265     Reg = Candidates.find_next(Reg);
 266   }
 267
 268   if (ScavengedReg != 0) {
 269     // First restore previously scavenged register.
 270     RegInfo->loadRegFromStackSlot(*MBB, I, ScavengedReg,
 271                                   ScavengingFrameIndex, ScavengedRC);
 272     MachineBasicBlock::iterator II = prior(I);
 273     RegInfo->eliminateFrameIndex(II, this);
 274   }
 275
 276   RegInfo->storeRegToStackSlot(*MBB, I, SReg, ScavengingFrameIndex, RC);
 277   MachineBasicBlock::iterator II = prior(I);
 278   RegInfo->eliminateFrameIndex(II, this);
 279   ScavengedReg = SReg;
 280   ScavengedRC = RC;
 281
 282   return SReg;
 283 }