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