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