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