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