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