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