Home | History | Annotate | Download | only in CodeGen 
      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/MachineBasicBlock.h"
     20 #include "llvm/CodeGen/MachineFrameInfo.h"
     21 #include "llvm/CodeGen/MachineFunction.h"
     22 #include "llvm/CodeGen/MachineInstr.h"
     23 #include "llvm/CodeGen/MachineRegisterInfo.h"
     24 #include "llvm/Support/Debug.h"
     25 #include "llvm/Support/ErrorHandling.h"
     26 #include "llvm/Support/raw_ostream.h"
     27 #include "llvm/Target/TargetInstrInfo.h"
     28 #include "llvm/Target/TargetMachine.h"
     29 #include "llvm/Target/TargetRegisterInfo.h"
     30 using namespace llvm;
     31 
     32 /// setUsed - Set the register and its sub-registers as being used.
     33 void RegScavenger::setUsed(unsigned Reg) {
     34   RegsAvailable.reset(Reg);
     35 
     36   for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs)
     37     RegsAvailable.reset(*SubRegs);
     38 }
     39 
     40 bool RegScavenger::isAliasUsed(unsigned Reg) const {
     41   for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
     42     if (isUsed(*AI, *AI == Reg))
     43       return true;
     44   return false;
     45 }
     46 
     47 void RegScavenger::initRegState() {
     48   ScavengedReg = 0;
     49   ScavengedRC = NULL;
     50   ScavengeRestore = NULL;
     51 
     52   // All registers started out unused.
     53   RegsAvailable.set();
     54 
     55   if (!MBB)
     56     return;
     57 
     58   // Live-in registers are in use.
     59   for (MachineBasicBlock::livein_iterator I = MBB->livein_begin(),
     60          E = MBB->livein_end(); I != E; ++I)
     61     setUsed(*I);
     62 
     63   // Pristine CSRs are also unavailable.
     64   BitVector PR = MBB->getParent()->getFrameInfo()->getPristineRegs(MBB);
     65   for (int I = PR.find_first(); I>0; I = PR.find_next(I))
     66     setUsed(I);
     67 }
     68 
     69 void RegScavenger::enterBasicBlock(MachineBasicBlock *mbb) {
     70   MachineFunction &MF = *mbb->getParent();
     71   const TargetMachine &TM = MF.getTarget();
     72   TII = TM.getInstrInfo();
     73   TRI = TM.getRegisterInfo();
     74   MRI = &MF.getRegInfo();
     75 
     76   assert((NumPhysRegs == 0 || NumPhysRegs == TRI->getNumRegs()) &&
     77          "Target changed?");
     78 
     79   // It is not possible to use the register scavenger after late optimization
     80   // passes that don't preserve accurate liveness information.
     81   assert(MRI->tracksLiveness() &&
     82          "Cannot use register scavenger with inaccurate liveness");
     83 
     84   // Self-initialize.
     85   if (!MBB) {
     86     NumPhysRegs = TRI->getNumRegs();
     87     RegsAvailable.resize(NumPhysRegs);
     88     KillRegs.resize(NumPhysRegs);
     89     DefRegs.resize(NumPhysRegs);
     90 
     91     // Create callee-saved registers bitvector.
     92     CalleeSavedRegs.resize(NumPhysRegs);
     93     const uint16_t *CSRegs = TRI->getCalleeSavedRegs(&MF);
     94     if (CSRegs != NULL)
     95       for (unsigned i = 0; CSRegs[i]; ++i)
     96         CalleeSavedRegs.set(CSRegs[i]);
     97   }
     98 
     99   MBB = mbb;
    100   initRegState();
    101 
    102   Tracking = false;
    103 }
    104 
    105 void RegScavenger::addRegWithSubRegs(BitVector &BV, unsigned Reg) {
    106   BV.set(Reg);
    107   for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs)
    108     BV.set(*SubRegs);
    109 }
    110 
    111 void RegScavenger::forward() {
    112   // Move ptr forward.
    113   if (!Tracking) {
    114     MBBI = MBB->begin();
    115     Tracking = true;
    116   } else {
    117     assert(MBBI != MBB->end() && "Already past the end of the basic block!");
    118     MBBI = llvm::next(MBBI);
    119   }
    120   assert(MBBI != MBB->end() && "Already at the end of the basic block!");
    121 
    122   MachineInstr *MI = MBBI;
    123 
    124   if (MI == ScavengeRestore) {
    125     ScavengedReg = 0;
    126     ScavengedRC = NULL;
    127     ScavengeRestore = NULL;
    128   }
    129 
    130   if (MI->isDebugValue())
    131     return;
    132 
    133   // Find out which registers are early clobbered, killed, defined, and marked
    134   // def-dead in this instruction.
    135   // FIXME: The scavenger is not predication aware. If the instruction is
    136   // predicated, conservatively assume "kill" markers do not actually kill the
    137   // register. Similarly ignores "dead" markers.
    138   bool isPred = TII->isPredicated(MI);
    139   KillRegs.reset();
    140   DefRegs.reset();
    141   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
    142     const MachineOperand &MO = MI->getOperand(i);
    143     if (MO.isRegMask())
    144       (isPred ? DefRegs : KillRegs).setBitsNotInMask(MO.getRegMask());
    145     if (!MO.isReg())
    146       continue;
    147     unsigned Reg = MO.getReg();
    148     if (!Reg || isReserved(Reg))
    149       continue;
    150 
    151     if (MO.isUse()) {
    152       // Ignore undef uses.
    153       if (MO.isUndef())
    154         continue;
    155       if (!isPred && MO.isKill())
    156         addRegWithSubRegs(KillRegs, Reg);
    157     } else {
    158       assert(MO.isDef());
    159       if (!isPred && MO.isDead())
    160         addRegWithSubRegs(KillRegs, Reg);
    161       else
    162         addRegWithSubRegs(DefRegs, Reg);
    163     }
    164   }
    165 
    166   // Verify uses and defs.
    167 #ifndef NDEBUG
    168   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
    169     const MachineOperand &MO = MI->getOperand(i);
    170     if (!MO.isReg())
    171       continue;
    172     unsigned Reg = MO.getReg();
    173     if (!Reg || isReserved(Reg))
    174       continue;
    175     if (MO.isUse()) {
    176       if (MO.isUndef())
    177         continue;
    178       if (!isUsed(Reg)) {
    179         // Check if it's partial live: e.g.
    180         // D0 = insert_subreg D0<undef>, S0
    181         // ... D0
    182         // The problem is the insert_subreg could be eliminated. The use of
    183         // D0 is using a partially undef value. This is not *incorrect* since
    184         // S1 is can be freely clobbered.
    185         // Ideally we would like a way to model this, but leaving the
    186         // insert_subreg around causes both correctness and performance issues.
    187         bool SubUsed = false;
    188         for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs)
    189           if (isUsed(*SubRegs)) {
    190             SubUsed = true;
    191             break;
    192           }
    193         if (!SubUsed) {
    194           MBB->getParent()->verify(NULL, "In Register Scavenger");
    195           llvm_unreachable("Using an undefined register!");
    196         }
    197         (void)SubUsed;
    198       }
    199     } else {
    200       assert(MO.isDef());
    201 #if 0
    202       // FIXME: Enable this once we've figured out how to correctly transfer
    203       // implicit kills during codegen passes like the coalescer.
    204       assert((KillRegs.test(Reg) || isUnused(Reg) ||
    205               isLiveInButUnusedBefore(Reg, MI, MBB, TRI, MRI)) &&
    206              "Re-defining a live register!");
    207 #endif
    208     }
    209   }
    210 #endif // NDEBUG
    211 
    212   // Commit the changes.
    213   setUnused(KillRegs);
    214   setUsed(DefRegs);
    215 }
    216 
    217 void RegScavenger::getRegsUsed(BitVector &used, bool includeReserved) {
    218   used = RegsAvailable;
    219   used.flip();
    220   if (includeReserved)
    221     used |= MRI->getReservedRegs();
    222   else
    223     used.reset(MRI->getReservedRegs());
    224 }
    225 
    226 unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RC) const {
    227   for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end();
    228        I != E; ++I)
    229     if (!isAliasUsed(*I)) {
    230       DEBUG(dbgs() << "Scavenger found unused reg: " << TRI->getName(*I) <<
    231             "\n");
    232       return *I;
    233     }
    234   return 0;
    235 }
    236 
    237 /// getRegsAvailable - Return all available registers in the register class
    238 /// in Mask.
    239 BitVector RegScavenger::getRegsAvailable(const TargetRegisterClass *RC) {
    240   BitVector Mask(TRI->getNumRegs());
    241   for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end();
    242        I != E; ++I)
    243     if (!isAliasUsed(*I))
    244       Mask.set(*I);
    245   return Mask;
    246 }
    247 
    248 /// findSurvivorReg - Return the candidate register that is unused for the
    249 /// longest after StargMII. UseMI is set to the instruction where the search
    250 /// stopped.
    251 ///
    252 /// No more than InstrLimit instructions are inspected.
    253 ///
    254 unsigned RegScavenger::findSurvivorReg(MachineBasicBlock::iterator StartMI,
    255                                        BitVector &Candidates,
    256                                        unsigned InstrLimit,
    257                                        MachineBasicBlock::iterator &UseMI) {
    258   int Survivor = Candidates.find_first();
    259   assert(Survivor > 0 && "No candidates for scavenging");
    260 
    261   MachineBasicBlock::iterator ME = MBB->getFirstTerminator();
    262   assert(StartMI != ME && "MI already at terminator");
    263   MachineBasicBlock::iterator RestorePointMI = StartMI;
    264   MachineBasicBlock::iterator MI = StartMI;
    265 
    266   bool inVirtLiveRange = false;
    267   for (++MI; InstrLimit > 0 && MI != ME; ++MI, --InstrLimit) {
    268     if (MI->isDebugValue()) {
    269       ++InstrLimit; // Don't count debug instructions
    270       continue;
    271     }
    272     bool isVirtKillInsn = false;
    273     bool isVirtDefInsn = false;
    274     // Remove any candidates touched by instruction.
    275     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
    276       const MachineOperand &MO = MI->getOperand(i);
    277       if (MO.isRegMask())
    278         Candidates.clearBitsNotInMask(MO.getRegMask());
    279       if (!MO.isReg() || MO.isUndef() || !MO.getReg())
    280         continue;
    281       if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) {
    282         if (MO.isDef())
    283           isVirtDefInsn = true;
    284         else if (MO.isKill())
    285           isVirtKillInsn = true;
    286         continue;
    287       }
    288       for (MCRegAliasIterator AI(MO.getReg(), TRI, true); AI.isValid(); ++AI)
    289         Candidates.reset(*AI);
    290     }
    291     // If we're not in a virtual reg's live range, this is a valid
    292     // restore point.
    293     if (!inVirtLiveRange) RestorePointMI = MI;
    294 
    295     // Update whether we're in the live range of a virtual register
    296     if (isVirtKillInsn) inVirtLiveRange = false;
    297     if (isVirtDefInsn) inVirtLiveRange = true;
    298 
    299     // Was our survivor untouched by this instruction?
    300     if (Candidates.test(Survivor))
    301       continue;
    302 
    303     // All candidates gone?
    304     if (Candidates.none())
    305       break;
    306 
    307     Survivor = Candidates.find_first();
    308   }
    309   // If we ran off the end, that's where we want to restore.
    310   if (MI == ME) RestorePointMI = ME;
    311   assert (RestorePointMI != StartMI &&
    312           "No available scavenger restore location!");
    313 
    314   // We ran out of candidates, so stop the search.
    315   UseMI = RestorePointMI;
    316   return Survivor;
    317 }
    318 
    319 static unsigned getFrameIndexOperandNum(MachineInstr *MI) {
    320   unsigned i = 0;
    321   while (!MI->getOperand(i).isFI()) {
    322     ++i;
    323     assert(i < MI->getNumOperands() &&
    324            "Instr doesn't have FrameIndex operand!");
    325   }
    326   return i;
    327 }
    328 
    329 unsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC,
    330                                         MachineBasicBlock::iterator I,
    331                                         int SPAdj) {
    332   // Consider all allocatable registers in the register class initially
    333   BitVector Candidates =
    334     TRI->getAllocatableSet(*I->getParent()->getParent(), RC);
    335 
    336   // Exclude all the registers being used by the instruction.
    337   for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
    338     MachineOperand &MO = I->getOperand(i);
    339     if (MO.isReg() && MO.getReg() != 0 &&
    340         !TargetRegisterInfo::isVirtualRegister(MO.getReg()))
    341       Candidates.reset(MO.getReg());
    342   }
    343 
    344   // Try to find a register that's unused if there is one, as then we won't
    345   // have to spill. Search explicitly rather than masking out based on
    346   // RegsAvailable, as RegsAvailable does not take aliases into account.
    347   // That's what getRegsAvailable() is for.
    348   BitVector Available = getRegsAvailable(RC);
    349   Available &= Candidates;
    350   if (Available.any())
    351     Candidates = Available;
    352 
    353   // Find the register whose use is furthest away.
    354   MachineBasicBlock::iterator UseMI;
    355   unsigned SReg = findSurvivorReg(I, Candidates, 25, UseMI);
    356 
    357   // If we found an unused register there is no reason to spill it.
    358   if (!isAliasUsed(SReg)) {
    359     DEBUG(dbgs() << "Scavenged register: " << TRI->getName(SReg) << "\n");
    360     return SReg;
    361   }
    362 
    363   assert(ScavengedReg == 0 &&
    364          "Scavenger slot is live, unable to scavenge another register!");
    365 
    366   // Avoid infinite regress
    367   ScavengedReg = SReg;
    368 
    369   // If the target knows how to save/restore the register, let it do so;
    370   // otherwise, use the emergency stack spill slot.
    371   if (!TRI->saveScavengerRegister(*MBB, I, UseMI, RC, SReg)) {
    372     // Spill the scavenged register before I.
    373     assert(ScavengingFrameIndex >= 0 &&
    374            "Cannot scavenge register without an emergency spill slot!");
    375     TII->storeRegToStackSlot(*MBB, I, SReg, true, ScavengingFrameIndex, RC,TRI);
    376     MachineBasicBlock::iterator II = prior(I);
    377 
    378     unsigned FIOperandNum = getFrameIndexOperandNum(II);
    379     TRI->eliminateFrameIndex(II, SPAdj, FIOperandNum, this);
    380 
    381     // Restore the scavenged register before its use (or first terminator).
    382     TII->loadRegFromStackSlot(*MBB, UseMI, SReg, ScavengingFrameIndex, RC, TRI);
    383     II = prior(UseMI);
    384 
    385     FIOperandNum = getFrameIndexOperandNum(II);
    386     TRI->eliminateFrameIndex(II, SPAdj, FIOperandNum, this);
    387   }
    388 
    389   ScavengeRestore = prior(UseMI);
    390 
    391   // Doing this here leads to infinite regress.
    392   // ScavengedReg = SReg;
    393   ScavengedRC = RC;
    394 
    395   DEBUG(dbgs() << "Scavenged register (with spill): " << TRI->getName(SReg) <<
    396         "\n");
    397 
    398   return SReg;
    399 }
    400