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/MachineFrameInfo.h"
  20 #include "llvm/CodeGen/MachineFunction.h"
  21 #include "llvm/CodeGen/MachineBasicBlock.h"
  22 #include "llvm/CodeGen/MachineInstr.h"
  23 #include "llvm/CodeGen/MachineRegisterInfo.h"
  24 #include "llvm/Support/ErrorHandling.h"
  25 #include "llvm/Target/TargetRegisterInfo.h"
  26 #include "llvm/Target/TargetInstrInfo.h"
  27 #include "llvm/Target/TargetMachine.h"
  28 #include "llvm/ADT/SmallPtrSet.h"
  29 #include "llvm/ADT/SmallVector.h"
  30 #include "llvm/ADT/STLExtras.h"
  31 using namespace llvm;
  32
  33 /// RedefinesSuperRegPart - Return true if the specified register is redefining
  34 /// part of a super-register.
  35 static bool RedefinesSuperRegPart(const MachineInstr *MI, unsigned SubReg,
  36                                   const TargetRegisterInfo *TRI) {
  37   bool SeenSuperUse = false;
  38   bool SeenSuperDef = false;
  39   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
  40     const MachineOperand &MO = MI->getOperand(i);
  41     if (!MO.isReg() || MO.isUndef())
  42       continue;
  43     if (TRI->isSuperRegister(SubReg, MO.getReg())) {
  44       if (MO.isUse())
  45         SeenSuperUse = true;
  46       else if (MO.isImplicit())
  47         SeenSuperDef = true;
  48     }
  49   }
  50
  51   return SeenSuperDef && SeenSuperUse;
  52 }
  53
  54 bool RegScavenger::isSuperRegUsed(unsigned Reg) const {
  55   for (const unsigned *SuperRegs = TRI->getSuperRegisters(Reg);
  56        unsigned SuperReg = *SuperRegs; ++SuperRegs)
  57     if (isUsed(SuperReg))
  58       return true;
  59   return false;
  60 }
  61
  62 /// setUsed - Set the register and its sub-registers as being used.
  63 void RegScavenger::setUsed(unsigned Reg) {
  64   RegsAvailable.reset(Reg);
  65
  66   for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
  67        unsigned SubReg = *SubRegs; ++SubRegs)
  68     RegsAvailable.reset(SubReg);
  69 }
  70
  71 /// setUnused - Set the register and its sub-registers as being unused.
  72 void RegScavenger::setUnused(unsigned Reg, const MachineInstr *MI) {
  73   RegsAvailable.set(Reg);
  74
  75   for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
  76        unsigned SubReg = *SubRegs; ++SubRegs)
  77     if (!RedefinesSuperRegPart(MI, Reg, TRI))
  78       RegsAvailable.set(SubReg);
  79 }
  80
  81 void RegScavenger::initRegState() {
  82   ScavengedReg = 0;
  83   ScavengedRC = NULL;
  84   ScavengeRestore = NULL;
  85   CurrDist = 0;
  86   DistanceMap.clear();
  87
  88   // All registers started out unused.
  89   RegsAvailable.set();
  90
  91   // Reserved registers are always used.
  92   RegsAvailable ^= ReservedRegs;
  93
  94   // Live-in registers are in use.
  95   if (!MBB || MBB->livein_empty())
  96     return;
  97   for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(),
  98          E = MBB->livein_end(); I != E; ++I)
  99     setUsed(*I);
 100 }
 101
 102 void RegScavenger::enterBasicBlock(MachineBasicBlock *mbb) {
 103   MachineFunction &MF = *mbb->getParent();
 104   const TargetMachine &TM = MF.getTarget();
 105   TII = TM.getInstrInfo();
 106   TRI = TM.getRegisterInfo();
 107   MRI = &MF.getRegInfo();
 108
 109   assert((NumPhysRegs == 0 || NumPhysRegs == TRI->getNumRegs()) &&
 110          "Target changed?");
 111
 112   // Self-initialize.
 113   if (!MBB) {
 114     NumPhysRegs = TRI->getNumRegs();
 115     RegsAvailable.resize(NumPhysRegs);
 116
 117     // Create reserved registers bitvector.
 118     ReservedRegs = TRI->getReservedRegs(MF);
 119
 120     // Create callee-saved registers bitvector.
 121     CalleeSavedRegs.resize(NumPhysRegs);
 122     const unsigned *CSRegs = TRI->getCalleeSavedRegs();
 123     if (CSRegs != NULL)
 124       for (unsigned i = 0; CSRegs[i]; ++i)
 125         CalleeSavedRegs.set(CSRegs[i]);
 126   }
 127
 128   // RS used within emit{Pro,Epi}logue()
 129   if (mbb != MBB) {
 130     MBB = mbb;
 131     initRegState();
 132   }
 133
 134   Tracking = false;
 135 }
 136
 137 void RegScavenger::restoreScavengedReg() {
 138   TII->loadRegFromStackSlot(*MBB, MBBI, ScavengedReg,
 139                             ScavengingFrameIndex, ScavengedRC);
 140   MachineBasicBlock::iterator II = prior(MBBI);
 141   TRI->eliminateFrameIndex(II, 0, this);
 142   setUsed(ScavengedReg);
 143   ScavengedReg = 0;
 144   ScavengedRC = NULL;
 145 }
 146
 147 #ifndef NDEBUG
 148 /// isLiveInButUnusedBefore - Return true if register is livein the MBB not
 149 /// not used before it reaches the MI that defines register.
 150 static bool isLiveInButUnusedBefore(unsigned Reg, MachineInstr *MI,
 151                                     MachineBasicBlock *MBB,
 152                                     const TargetRegisterInfo *TRI,
 153                                     MachineRegisterInfo* MRI) {
 154   // First check if register is livein.
 155   bool isLiveIn = false;
 156   for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(),
 157          E = MBB->livein_end(); I != E; ++I)
 158     if (Reg == *I || TRI->isSuperRegister(Reg, *I)) {
 159       isLiveIn = true;
 160       break;
 161     }
 162   if (!isLiveIn)
 163     return false;
 164
 165   // Is there any use of it before the specified MI?
 166   SmallPtrSet<MachineInstr*, 4> UsesInMBB;
 167   for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg),
 168          UE = MRI->use_end(); UI != UE; ++UI) {
 169     MachineOperand &UseMO = UI.getOperand();
 170     if (UseMO.isReg() && UseMO.isUndef())
 171       continue;
 172     MachineInstr *UseMI = &*UI;
 173     if (UseMI->getParent() == MBB)
 174       UsesInMBB.insert(UseMI);
 175   }
 176   if (UsesInMBB.empty())
 177     return true;
 178
 179   for (MachineBasicBlock::iterator I = MBB->begin(), E = MI; I != E; ++I)
 180     if (UsesInMBB.count(&*I))
 181       return false;
 182   return true;
 183 }
 184 #endif
 185
 186 void RegScavenger::addRegWithSubRegs(BitVector &BV, unsigned Reg) {
 187   BV.set(Reg);
 188   for (const unsigned *R = TRI->getSubRegisters(Reg); *R; R++)
 189     BV.set(*R);
 190 }
 191
 192 void RegScavenger::addRegWithAliases(BitVector &BV, unsigned Reg) {
 193   BV.set(Reg);
 194   for (const unsigned *R = TRI->getAliasSet(Reg); *R; R++)
 195     BV.set(*R);
 196 }
 197
 198 void RegScavenger::forward() {
 199   // Move ptr forward.
 200   if (!Tracking) {
 201     MBBI = MBB->begin();
 202     Tracking = true;
 203   } else {
 204     assert(MBBI != MBB->end() && "Already at the end of the basic block!");
 205     MBBI = next(MBBI);
 206   }
 207
 208   MachineInstr *MI = MBBI;
 209   DistanceMap.insert(std::make_pair(MI, CurrDist++));
 210
 211   if (MI == ScavengeRestore) {
 212     ScavengedReg = 0;
 213     ScavengedRC = NULL;
 214     ScavengeRestore = NULL;
 215   }
 216
 217   // Find out which registers are early clobbered, killed, defined, and marked
 218   // def-dead in this instruction.
 219   BitVector EarlyClobberRegs(NumPhysRegs);
 220   BitVector KillRegs(NumPhysRegs);
 221   BitVector DefRegs(NumPhysRegs);
 222   BitVector DeadRegs(NumPhysRegs);
 223   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 224     const MachineOperand &MO = MI->getOperand(i);
 225     if (!MO.isReg() || MO.isUndef())
 226       continue;
 227     unsigned Reg = MO.getReg();
 228     if (!Reg || isReserved(Reg))
 229       continue;
 230
 231     if (MO.isUse()) {
 232       // Two-address operands implicitly kill.
 233       if (MO.isKill() || MI->isRegTiedToDefOperand(i))
 234         addRegWithSubRegs(KillRegs, Reg);
 235     } else {
 236       assert(MO.isDef());
 237       if (MO.isDead())
 238         addRegWithSubRegs(DeadRegs, Reg);
 239       else
 240         addRegWithSubRegs(DefRegs, Reg);
 241       if (MO.isEarlyClobber())
 242         addRegWithAliases(EarlyClobberRegs, Reg);
 243     }
 244   }
 245
 246   // Verify uses and defs.
 247   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 248     const MachineOperand &MO = MI->getOperand(i);
 249     if (!MO.isReg() || MO.isUndef())
 250       continue;
 251     unsigned Reg = MO.getReg();
 252     if (!Reg || isReserved(Reg))
 253       continue;
 254     if (MO.isUse()) {
 255       assert(isUsed(Reg) && "Using an undefined register!");
 256       assert(!EarlyClobberRegs.test(Reg) &&
 257              "Using an early clobbered register!");
 258     } else {
 259       assert(MO.isDef());
 260       assert((KillRegs.test(Reg) || isUnused(Reg) || isSuperRegUsed(Reg) ||
 261               isLiveInButUnusedBefore(Reg, MI, MBB, TRI, MRI)) &&
 262              "Re-defining a live register!");
 263     }
 264   }
 265
 266   // Commit the changes.
 267   setUnused(KillRegs);
 268   setUnused(DeadRegs);
 269   setUsed(DefRegs);
 270 }
 271
 272 void RegScavenger::getRegsUsed(BitVector &used, bool includeReserved) {
 273   if (includeReserved)
 274     used = ~RegsAvailable;
 275   else
 276     used = ~RegsAvailable & ~ReservedRegs;
 277 }
 278
 279 /// CreateRegClassMask - Set the bits that represent the registers in the
 280 /// TargetRegisterClass.
 281 static void CreateRegClassMask(const TargetRegisterClass *RC, BitVector &Mask) {
 282   for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); I != E;
 283        ++I)
 284     Mask.set(*I);
 285 }
 286
 287 unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass,
 288                                      const BitVector &Candidates) const {
 289   // Mask off the registers which are not in the TargetRegisterClass.
 290   BitVector RegsAvailableCopy(NumPhysRegs, false);
 291   CreateRegClassMask(RegClass, RegsAvailableCopy);
 292   RegsAvailableCopy &= RegsAvailable;
 293
 294   // Restrict the search to candidates.
 295   RegsAvailableCopy &= Candidates;
 296
 297   // Returns the first unused (bit is set) register, or 0 is none is found.
 298   int Reg = RegsAvailableCopy.find_first();
 299   return (Reg == -1) ? 0 : Reg;
 300 }
 301
 302 unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass,
 303                                      bool ExCalleeSaved) const {
 304   // Mask off the registers which are not in the TargetRegisterClass.
 305   BitVector RegsAvailableCopy(NumPhysRegs, false);
 306   CreateRegClassMask(RegClass, RegsAvailableCopy);
 307   RegsAvailableCopy &= RegsAvailable;
 308
 309   // If looking for a non-callee-saved register, mask off all the callee-saved
 310   // registers.
 311   if (ExCalleeSaved)
 312     RegsAvailableCopy &= ~CalleeSavedRegs;
 313
 314   // Returns the first unused (bit is set) register, or 0 is none is found.
 315   int Reg = RegsAvailableCopy.find_first();
 316   return (Reg == -1) ? 0 : Reg;
 317 }
 318
 319 /// findFirstUse - Calculate the distance to the first use of the
 320 /// specified register.
 321 MachineInstr*
 322 RegScavenger::findFirstUse(MachineBasicBlock *MBB,
 323                            MachineBasicBlock::iterator I, unsigned Reg,
 324                            unsigned &Dist) {
 325   MachineInstr *UseMI = 0;
 326   Dist = ~0U;
 327   for (MachineRegisterInfo::reg_iterator RI = MRI->reg_begin(Reg),
 328          RE = MRI->reg_end(); RI != RE; ++RI) {
 329     MachineInstr *UDMI = &*RI;
 330     if (UDMI->getParent() != MBB)
 331       continue;
 332     DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(UDMI);
 333     if (DI == DistanceMap.end()) {
 334       // If it's not in map, it's below current MI, let's initialize the
 335       // map.
 336       I = next(I);
 337       unsigned Dist = CurrDist + 1;
 338       while (I != MBB->end()) {
 339         DistanceMap.insert(std::make_pair(I, Dist++));
 340         I = next(I);
 341       }
 342     }
 343     DI = DistanceMap.find(UDMI);
 344     if (DI->second > CurrDist && DI->second < Dist) {
 345       Dist = DI->second;
 346       UseMI = UDMI;
 347     }
 348   }
 349   return UseMI;
 350 }
 351
 352 unsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC,
 353                                         MachineBasicBlock::iterator I,
 354                                         int SPAdj) {
 355   assert(ScavengingFrameIndex >= 0 &&
 356          "Cannot scavenge a register without an emergency spill slot!");
 357
 358   // Mask off the registers which are not in the TargetRegisterClass.
 359   BitVector Candidates(NumPhysRegs, false);
 360   CreateRegClassMask(RC, Candidates);
 361   // Do not include reserved registers.
 362   Candidates ^= ReservedRegs & Candidates;
 363
 364   // Exclude all the registers being used by the instruction.
 365   for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
 366     MachineOperand &MO = I->getOperand(i);
 367     if (MO.isReg())
 368       Candidates.reset(MO.getReg());
 369   }
 370
 371   // Find the register whose use is furthest away.
 372   unsigned SReg = 0;
 373   unsigned MaxDist = 0;
 374   MachineInstr *MaxUseMI = 0;
 375   int Reg = Candidates.find_first();
 376   while (Reg != -1) {
 377     unsigned Dist;
 378     MachineInstr *UseMI = findFirstUse(MBB, I, Reg, Dist);
 379     for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) {
 380       unsigned AsDist;
 381       MachineInstr *AsUseMI = findFirstUse(MBB, I, *AS, AsDist);
 382       if (AsDist < Dist) {
 383         Dist = AsDist;
 384         UseMI = AsUseMI;
 385       }
 386     }
 387     if (Dist >= MaxDist) {
 388       MaxDist = Dist;
 389       MaxUseMI = UseMI;
 390       SReg = Reg;
 391     }
 392     Reg = Candidates.find_next(Reg);
 393   }
 394
 395   assert(ScavengedReg == 0 &&
 396          "Scavenger slot is live, unable to scavenge another register!");
 397
 398   // Avoid infinite regress
 399   ScavengedReg = SReg;
 400
 401   // Make sure SReg is marked as used. It could be considered available
 402   // if it is one of the callee saved registers, but hasn't been spilled.
 403   if (!isUsed(SReg)) {
 404     MBB->addLiveIn(SReg);
 405     setUsed(SReg);
 406   }
 407
 408   // Spill the scavenged register before I.
 409   TII->storeRegToStackSlot(*MBB, I, SReg, true, ScavengingFrameIndex, RC);
 410   MachineBasicBlock::iterator II = prior(I);
 411   TRI->eliminateFrameIndex(II, SPAdj, this);
 412
 413   // Restore the scavenged register before its use (or first terminator).
 414   II = MaxUseMI
 415     ? MachineBasicBlock::iterator(MaxUseMI) : MBB->getFirstTerminator();
 416   TII->loadRegFromStackSlot(*MBB, II, SReg, ScavengingFrameIndex, RC);
 417   ScavengeRestore = prior(II);
 418   // Doing this here leads to infinite regress.
 419   // ScavengedReg = SReg;
 420   ScavengedRC = RC;
 421
 422   return SReg;
 423 }