contrib/llvm/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 /// \file
  11 /// This file implements the machine register scavenger. It can provide
  12 /// information, such as unused registers, at any point in a machine basic
  13 /// block. It also provides a mechanism to make registers available by evicting
  14 /// them to spill slots.
  15 //
  16 //===----------------------------------------------------------------------===//
  17
  18 #include "llvm/ADT/BitVector.h"
  19 #include "llvm/ADT/SmallVector.h"
  20 #include "llvm/CodeGen/RegisterScavenging.h"
  21 #include "llvm/CodeGen/MachineBasicBlock.h"
  22 #include "llvm/CodeGen/MachineFrameInfo.h"
  23 #include "llvm/CodeGen/MachineFunction.h"
  24 #include "llvm/CodeGen/MachineInstr.h"
  25 #include "llvm/CodeGen/MachineOperand.h"
  26 #include "llvm/MC/MCRegisterInfo.h"
  27 #include "llvm/Support/Debug.h"
  28 #include "llvm/Support/ErrorHandling.h"
  29 #include "llvm/Support/raw_ostream.h"
  30 #include "llvm/Target/TargetInstrInfo.h"
  31 #include "llvm/Target/TargetRegisterInfo.h"
  32 #include "llvm/Target/TargetSubtargetInfo.h"
  33 #include <cassert>
  34 #include <iterator>
  35 #include <limits>
  36 #include <string>
  37
  38 using namespace llvm;
  39
  40 #define DEBUG_TYPE "reg-scavenging"
  41
  42 void RegScavenger::setRegUsed(unsigned Reg, LaneBitmask LaneMask) {
  43   LiveUnits.addRegMasked(Reg, LaneMask);
  44 }
  45
  46 void RegScavenger::init(MachineBasicBlock &MBB) {
  47   MachineFunction &MF = *MBB.getParent();
  48   TII = MF.getSubtarget().getInstrInfo();
  49   TRI = MF.getSubtarget().getRegisterInfo();
  50   MRI = &MF.getRegInfo();
  51   LiveUnits.init(*TRI);
  52
  53   assert((NumRegUnits == 0 || NumRegUnits == TRI->getNumRegUnits()) &&
  54          "Target changed?");
  55
  56   // Self-initialize.
  57   if (!this->MBB) {
  58     NumRegUnits = TRI->getNumRegUnits();
  59     KillRegUnits.resize(NumRegUnits);
  60     DefRegUnits.resize(NumRegUnits);
  61     TmpRegUnits.resize(NumRegUnits);
  62   }
  63   this->MBB = &MBB;
  64
  65   for (SmallVectorImpl<ScavengedInfo>::iterator I = Scavenged.begin(),
  66          IE = Scavenged.end(); I != IE; ++I) {
  67     I->Reg = 0;
  68     I->Restore = nullptr;
  69   }
  70
  71   Tracking = false;
  72 }
  73
  74 void RegScavenger::enterBasicBlock(MachineBasicBlock &MBB) {
  75   init(MBB);
  76   LiveUnits.addLiveIns(MBB);
  77 }
  78
  79 void RegScavenger::enterBasicBlockEnd(MachineBasicBlock &MBB) {
  80   init(MBB);
  81   LiveUnits.addLiveOuts(MBB);
  82
  83   // Move internal iterator at the last instruction of the block.
  84   if (MBB.begin() != MBB.end()) {
  85     MBBI = std::prev(MBB.end());
  86     Tracking = true;
  87   }
  88 }
  89
  90 void RegScavenger::addRegUnits(BitVector &BV, unsigned Reg) {
  91   for (MCRegUnitIterator RUI(Reg, TRI); RUI.isValid(); ++RUI)
  92     BV.set(*RUI);
  93 }
  94
  95 void RegScavenger::removeRegUnits(BitVector &BV, unsigned Reg) {
  96   for (MCRegUnitIterator RUI(Reg, TRI); RUI.isValid(); ++RUI)
  97     BV.reset(*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 (const MachineOperand &MO : MI.operands()) {
 111     if (MO.isRegMask()) {
 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 (!TargetRegisterInfo::isPhysicalRegister(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 (const MachineOperand &MO : MI.operands()) {
 196     if (!MO.isReg())
 197       continue;
 198     unsigned Reg = MO.getReg();
 199     if (!TargetRegisterInfo::isPhysicalRegister(Reg) || isReserved(Reg))
 200       continue;
 201     if (MO.isUse()) {
 202       if (MO.isUndef())
 203         continue;
 204       if (!isRegUsed(Reg)) {
 205         // Check if it's partial live: e.g.
 206         // D0 = insert_subreg D0<undef>, S0
 207         // ... D0
 208         // The problem is the insert_subreg could be eliminated. The use of
 209         // D0 is using a partially undef value. This is not *incorrect* since
 210         // S1 is can be freely clobbered.
 211         // Ideally we would like a way to model this, but leaving the
 212         // insert_subreg around causes both correctness and performance issues.
 213         bool SubUsed = false;
 214         for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs)
 215           if (isRegUsed(*SubRegs)) {
 216             SubUsed = true;
 217             break;
 218           }
 219         bool SuperUsed = false;
 220         for (MCSuperRegIterator SR(Reg, TRI); SR.isValid(); ++SR) {
 221           if (isRegUsed(*SR)) {
 222             SuperUsed = true;
 223             break;
 224           }
 225         }
 226         if (!SubUsed && !SuperUsed) {
 227           MBB->getParent()->verify(nullptr, "In Register Scavenger");
 228           llvm_unreachable("Using an undefined register!");
 229         }
 230         (void)SubUsed;
 231         (void)SuperUsed;
 232       }
 233     } else {
 234       assert(MO.isDef());
 235 #if 0
 236       // FIXME: Enable this once we've figured out how to correctly transfer
 237       // implicit kills during codegen passes like the coalescer.
 238       assert((KillRegs.test(Reg) || isUnused(Reg) ||
 239               isLiveInButUnusedBefore(Reg, MI, MBB, TRI, MRI)) &&
 240              "Re-defining a live register!");
 241 #endif
 242     }
 243   }
 244 #endif // NDEBUG
 245
 246   // Commit the changes.
 247   setUnused(KillRegUnits);
 248   setUsed(DefRegUnits);
 249 }
 250
 251 void RegScavenger::backward() {
 252   assert(Tracking && "Must be tracking to determine kills and defs");
 253
 254   const MachineInstr &MI = *MBBI;
 255   LiveUnits.stepBackward(MI);
 256
 257   if (MBBI == MBB->begin()) {
 258     MBBI = MachineBasicBlock::iterator(nullptr);
 259     Tracking = false;
 260   } else
 261     --MBBI;
 262 }
 263
 264 bool RegScavenger::isRegUsed(unsigned Reg, bool includeReserved) const {
 265   if (isReserved(Reg))
 266     return includeReserved;
 267   return !LiveUnits.available(Reg);
 268 }
 269
 270 unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RC) const {
 271   for (unsigned Reg : *RC) {
 272     if (!isRegUsed(Reg)) {
 273       DEBUG(dbgs() << "Scavenger found unused reg: " << TRI->getName(Reg) <<
 274             "\n");
 275       return Reg;
 276     }
 277   }
 278   return 0;
 279 }
 280
 281 BitVector RegScavenger::getRegsAvailable(const TargetRegisterClass *RC) {
 282   BitVector Mask(TRI->getNumRegs());
 283   for (unsigned Reg : *RC)
 284     if (!isRegUsed(Reg))
 285       Mask.set(Reg);
 286   return Mask;
 287 }
 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 (const MachineOperand &MO : MI->operands()) {
 311       if (MO.isRegMask())
 312         Candidates.clearBitsNotInMask(MO.getRegMask());
 313       if (!MO.isReg() || MO.isUndef() || !MO.getReg())
 314         continue;
 315       if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) {
 316         if (MO.isDef())
 317           isVirtDefInsn = true;
 318         else if (MO.isKill())
 319           isVirtKillInsn = true;
 320         continue;
 321       }
 322       for (MCRegAliasIterator AI(MO.getReg(), TRI, true); AI.isValid(); ++AI)
 323         Candidates.reset(*AI);
 324     }
 325     // If we're not in a virtual reg's live range, this is a valid
 326     // restore point.
 327     if (!inVirtLiveRange) RestorePointMI = MI;
 328
 329     // Update whether we're in the live range of a virtual register
 330     if (isVirtKillInsn) inVirtLiveRange = false;
 331     if (isVirtDefInsn) inVirtLiveRange = true;
 332
 333     // Was our survivor untouched by this instruction?
 334     if (Candidates.test(Survivor))
 335       continue;
 336
 337     // All candidates gone?
 338     if (Candidates.none())
 339       break;
 340
 341     Survivor = Candidates.find_first();
 342   }
 343   // If we ran off the end, that's where we want to restore.
 344   if (MI == ME) RestorePointMI = ME;
 345   assert(RestorePointMI != StartMI &&
 346          "No available scavenger restore location!");
 347
 348   // We ran out of candidates, so stop the search.
 349   UseMI = RestorePointMI;
 350   return Survivor;
 351 }
 352
 353 static unsigned getFrameIndexOperandNum(MachineInstr &MI) {
 354   unsigned i = 0;
 355   while (!MI.getOperand(i).isFI()) {
 356     ++i;
 357     assert(i < MI.getNumOperands() && "Instr doesn't have FrameIndex operand!");
 358   }
 359   return i;
 360 }
 361
 362 unsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC,
 363                                         MachineBasicBlock::iterator I,
 364                                         int SPAdj) {
 365   MachineInstr &MI = *I;
 366   const MachineFunction &MF = *MI.getParent()->getParent();
 367   // Consider all allocatable registers in the register class initially
 368   BitVector Candidates = TRI->getAllocatableSet(MF, RC);
 369
 370   // Exclude all the registers being used by the instruction.
 371   for (const MachineOperand &MO : MI.operands()) {
 372     if (MO.isReg() && MO.getReg() != 0 && !(MO.isUse() && MO.isUndef()) &&
 373         !TargetRegisterInfo::isVirtualRegister(MO.getReg()))
 374       for (MCRegAliasIterator AI(MO.getReg(), TRI, true); AI.isValid(); ++AI)
 375         Candidates.reset(*AI);
 376   }
 377
 378   // Try to find a register that's unused if there is one, as then we won't
 379   // have to spill.
 380   BitVector Available = getRegsAvailable(RC);
 381   Available &= Candidates;
 382   if (Available.any())
 383     Candidates = Available;
 384
 385   // Find the register whose use is furthest away.
 386   MachineBasicBlock::iterator UseMI;
 387   unsigned SReg = findSurvivorReg(I, Candidates, 25, UseMI);
 388
 389   // If we found an unused register there is no reason to spill it.
 390   if (!isRegUsed(SReg)) {
 391     DEBUG(dbgs() << "Scavenged register: " << TRI->getName(SReg) << "\n");
 392     return SReg;
 393   }
 394
 395   // Find an available scavenging slot with size and alignment matching
 396   // the requirements of the class RC.
 397   const MachineFrameInfo &MFI = MF.getFrameInfo();
 398   unsigned NeedSize = TRI->getSpillSize(*RC);
 399   unsigned NeedAlign = TRI->getSpillAlignment(*RC);
 400
 401   unsigned SI = Scavenged.size(), Diff = std::numeric_limits<unsigned>::max();
 402   int FIB = MFI.getObjectIndexBegin(), FIE = MFI.getObjectIndexEnd();
 403   for (unsigned I = 0; I < Scavenged.size(); ++I) {
 404     if (Scavenged[I].Reg != 0)
 405       continue;
 406     // Verify that this slot is valid for this register.
 407     int FI = Scavenged[I].FrameIndex;
 408     if (FI < FIB || FI >= FIE)
 409       continue;
 410     unsigned S = MFI.getObjectSize(FI);
 411     unsigned A = MFI.getObjectAlignment(FI);
 412     if (NeedSize > S || NeedAlign > A)
 413       continue;
 414     // Avoid wasting slots with large size and/or large alignment. Pick one
 415     // that is the best fit for this register class (in street metric).
 416     // Picking a larger slot than necessary could happen if a slot for a
 417     // larger register is reserved before a slot for a smaller one. When
 418     // trying to spill a smaller register, the large slot would be found
 419     // first, thus making it impossible to spill the larger register later.
 420     unsigned D = (S-NeedSize) + (A-NeedAlign);
 421     if (D < Diff) {
 422       SI = I;
 423       Diff = D;
 424     }
 425   }
 426
 427   if (SI == Scavenged.size()) {
 428     // We need to scavenge a register but have no spill slot, the target
 429     // must know how to do it (if not, we'll assert below).
 430     Scavenged.push_back(ScavengedInfo(FIE));
 431   }
 432
 433   // Avoid infinite regress
 434   Scavenged[SI].Reg = SReg;
 435
 436   // If the target knows how to save/restore the register, let it do so;
 437   // otherwise, use the emergency stack spill slot.
 438   if (!TRI->saveScavengerRegister(*MBB, I, UseMI, RC, SReg)) {
 439     // Spill the scavenged register before I.
 440     int FI = Scavenged[SI].FrameIndex;
 441     if (FI < FIB || FI >= FIE) {
 442       std::string Msg = std::string("Error while trying to spill ") +
 443           TRI->getName(SReg) + " from class " + TRI->getRegClassName(RC) +
 444           ": Cannot scavenge register without an emergency spill slot!";
 445       report_fatal_error(Msg.c_str());
 446     }
 447     TII->storeRegToStackSlot(*MBB, I, SReg, true, Scavenged[SI].FrameIndex,
 448                              RC, TRI);
 449     MachineBasicBlock::iterator II = std::prev(I);
 450
 451     unsigned FIOperandNum = getFrameIndexOperandNum(*II);
 452     TRI->eliminateFrameIndex(II, SPAdj, FIOperandNum, this);
 453
 454     // Restore the scavenged register before its use (or first terminator).
 455     TII->loadRegFromStackSlot(*MBB, UseMI, SReg, Scavenged[SI].FrameIndex,
 456                               RC, TRI);
 457     II = std::prev(UseMI);
 458
 459     FIOperandNum = getFrameIndexOperandNum(*II);
 460     TRI->eliminateFrameIndex(II, SPAdj, FIOperandNum, this);
 461   }
 462
 463   Scavenged[SI].Restore = &*std::prev(UseMI);
 464
 465   // Doing this here leads to infinite regress.
 466   // Scavenged[SI].Reg = SReg;
 467
 468   DEBUG(dbgs() << "Scavenged register (with spill): " << TRI->getName(SReg) <<
 469         "\n");
 470
 471   return SReg;
 472 }