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