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