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   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 }