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