llvm/lib/CodeGen/RegisterScavenging.cpp

   1 //===- RegisterScavenging.cpp - Machine register scavenging ---------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 /// \file
  10 /// This file implements the machine register scavenger. It can provide
  11 /// information, such as unused registers, at any point in a machine basic
  12 /// block. It also provides a mechanism to make registers available by evicting
  13 /// them to spill slots.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #include "llvm/CodeGen/RegisterScavenging.h"
  18 #include "llvm/ADT/ArrayRef.h"
  19 #include "llvm/ADT/BitVector.h"
  20 #include "llvm/ADT/SmallVector.h"
  21 #include "llvm/ADT/Statistic.h"
  22 #include "llvm/CodeGen/LiveRegUnits.h"
  23 #include "llvm/CodeGen/MachineBasicBlock.h"
  24 #include "llvm/CodeGen/MachineFrameInfo.h"
  25 #include "llvm/CodeGen/MachineFunction.h"
  26 #include "llvm/CodeGen/MachineFunctionPass.h"
  27 #include "llvm/CodeGen/MachineInstr.h"
  28 #include "llvm/CodeGen/MachineOperand.h"
  29 #include "llvm/CodeGen/MachineRegisterInfo.h"
  30 #include "llvm/CodeGen/TargetFrameLowering.h"
  31 #include "llvm/CodeGen/TargetInstrInfo.h"
  32 #include "llvm/CodeGen/TargetRegisterInfo.h"
  33 #include "llvm/CodeGen/TargetSubtargetInfo.h"
  34 #include "llvm/InitializePasses.h"
  35 #include "llvm/MC/MCRegisterInfo.h"
  36 #include "llvm/Pass.h"
  37 #include "llvm/Support/Debug.h"
  38 #include "llvm/Support/ErrorHandling.h"
  39 #include "llvm/Support/raw_ostream.h"
  40 #include <algorithm>
  41 #include <cassert>
  42 #include <iterator>
  43 #include <limits>
  44 #include <string>
  45 #include <utility>
  46
  47 using namespace llvm;
  48
  49 #define DEBUG_TYPE "reg-scavenging"
  50
  51 STATISTIC(NumScavengedRegs, "Number of frame index regs scavenged");
  52
  53 void RegScavenger::setRegUsed(Register Reg, LaneBitmask LaneMask) {
  54   LiveUnits.addRegMasked(Reg, LaneMask);
  55 }
  56
  57 void RegScavenger::init(MachineBasicBlock &MBB) {
  58   MachineFunction &MF = *MBB.getParent();
  59   TII = MF.getSubtarget().getInstrInfo();
  60   TRI = MF.getSubtarget().getRegisterInfo();
  61   MRI = &MF.getRegInfo();
  62   LiveUnits.init(*TRI);
  63
  64   assert((NumRegUnits == 0 || NumRegUnits == TRI->getNumRegUnits()) &&
  65          "Target changed?");
  66
  67   // Self-initialize.
  68   if (!this->MBB) {
  69     NumRegUnits = TRI->getNumRegUnits();
  70     KillRegUnits.resize(NumRegUnits);
  71     DefRegUnits.resize(NumRegUnits);
  72     TmpRegUnits.resize(NumRegUnits);
  73   }
  74   this->MBB = &MBB;
  75
  76   for (ScavengedInfo &SI : Scavenged) {
  77     SI.Reg = 0;
  78     SI.Restore = nullptr;
  79   }
  80
  81   Tracking = false;
  82 }
  83
  84 void RegScavenger::enterBasicBlock(MachineBasicBlock &MBB) {
  85   init(MBB);
  86   LiveUnits.addLiveIns(MBB);
  87 }
  88
  89 void RegScavenger::enterBasicBlockEnd(MachineBasicBlock &MBB) {
  90   init(MBB);
  91   LiveUnits.addLiveOuts(MBB);
  92
  93   // Move internal iterator at the last instruction of the block.
  94   if (!MBB.empty()) {
  95     MBBI = std::prev(MBB.end());
  96     Tracking = true;
  97   }
  98 }
  99
 100 void RegScavenger::addRegUnits(BitVector &BV, MCRegister Reg) {
 101   for (MCRegUnitIterator RUI(Reg, TRI); RUI.isValid(); ++RUI)
 102     BV.set(*RUI);
 103 }
 104
 105 void RegScavenger::removeRegUnits(BitVector &BV, MCRegister Reg) {
 106   for (MCRegUnitIterator RUI(Reg, TRI); RUI.isValid(); ++RUI)
 107     BV.reset(*RUI);
 108 }
 109
 110 void RegScavenger::determineKillsAndDefs() {
 111   assert(Tracking && "Must be tracking to determine kills and defs");
 112
 113   MachineInstr &MI = *MBBI;
 114   assert(!MI.isDebugInstr() && "Debug values have no kills or defs");
 115
 116   // Find out which registers are early clobbered, killed, defined, and marked
 117   // def-dead in this instruction.
 118   KillRegUnits.reset();
 119   DefRegUnits.reset();
 120   for (const MachineOperand &MO : MI.operands()) {
 121     if (MO.isRegMask()) {
 122       TmpRegUnits.reset();
 123       for (unsigned RU = 0, RUEnd = TRI->getNumRegUnits(); RU != RUEnd; ++RU) {
 124         for (MCRegUnitRootIterator RURI(RU, TRI); RURI.isValid(); ++RURI) {
 125           if (MO.clobbersPhysReg(*RURI)) {
 126             TmpRegUnits.set(RU);
 127             break;
 128           }
 129         }
 130       }
 131
 132       // Apply the mask.
 133       KillRegUnits |= TmpRegUnits;
 134     }
 135     if (!MO.isReg())
 136       continue;
 137     if (!MO.getReg().isPhysical() || isReserved(MO.getReg()))
 138       continue;
 139     MCRegister Reg = MO.getReg().asMCReg();
 140
 141     if (MO.isUse()) {
 142       // Ignore undef uses.
 143       if (MO.isUndef())
 144         continue;
 145       if (MO.isKill())
 146         addRegUnits(KillRegUnits, Reg);
 147     } else {
 148       assert(MO.isDef());
 149       if (MO.isDead())
 150         addRegUnits(KillRegUnits, Reg);
 151       else
 152         addRegUnits(DefRegUnits, Reg);
 153     }
 154   }
 155 }
 156
 157 void RegScavenger::forward() {
 158   // Move ptr forward.
 159   if (!Tracking) {
 160     MBBI = MBB->begin();
 161     Tracking = true;
 162   } else {
 163     assert(MBBI != MBB->end() && "Already past the end of the basic block!");
 164     MBBI = std::next(MBBI);
 165   }
 166   assert(MBBI != MBB->end() && "Already at the end of the basic block!");
 167
 168   MachineInstr &MI = *MBBI;
 169
 170   for (ScavengedInfo &I : Scavenged) {
 171     if (I.Restore != &MI)
 172       continue;
 173
 174     I.Reg = 0;
 175     I.Restore = nullptr;
 176   }
 177
 178   if (MI.isDebugOrPseudoInstr())
 179     return;
 180
 181   determineKillsAndDefs();
 182
 183   // Verify uses and defs.
 184 #ifndef NDEBUG
 185   for (const MachineOperand &MO : MI.operands()) {
 186     if (!MO.isReg())
 187       continue;
 188     Register Reg = MO.getReg();
 189     if (!Register::isPhysicalRegister(Reg) || isReserved(Reg))
 190       continue;
 191     if (MO.isUse()) {
 192       if (MO.isUndef())
 193         continue;
 194       if (!isRegUsed(Reg)) {
 195         // Check if it's partial live: e.g.
 196         // D0 = insert_subreg undef D0, S0
 197         // ... D0
 198         // The problem is the insert_subreg could be eliminated. The use of
 199         // D0 is using a partially undef value. This is not *incorrect* since
 200         // S1 is can be freely clobbered.
 201         // Ideally we would like a way to model this, but leaving the
 202         // insert_subreg around causes both correctness and performance issues.
 203         bool SubUsed = false;
 204         for (const MCPhysReg &SubReg : TRI->subregs(Reg))
 205           if (isRegUsed(SubReg)) {
 206             SubUsed = true;
 207             break;
 208           }
 209         bool SuperUsed = false;
 210         for (MCSuperRegIterator SR(Reg, TRI); SR.isValid(); ++SR) {
 211           if (isRegUsed(*SR)) {
 212             SuperUsed = true;
 213             break;
 214           }
 215         }
 216         if (!SubUsed && !SuperUsed) {
 217           MBB->getParent()->verify(nullptr, "In Register Scavenger");
 218           llvm_unreachable("Using an undefined register!");
 219         }
 220         (void)SubUsed;
 221         (void)SuperUsed;
 222       }
 223     } else {
 224       assert(MO.isDef());
 225 #if 0
 226       // FIXME: Enable this once we've figured out how to correctly transfer
 227       // implicit kills during codegen passes like the coalescer.
 228       assert((KillRegs.test(Reg) || isUnused(Reg) ||
 229               isLiveInButUnusedBefore(Reg, MI, MBB, TRI, MRI)) &&
 230              "Re-defining a live register!");
 231 #endif
 232     }
 233   }
 234 #endif // NDEBUG
 235
 236   // Commit the changes.
 237   setUnused(KillRegUnits);
 238   setUsed(DefRegUnits);
 239 }
 240
 241 void RegScavenger::backward() {
 242   assert(Tracking && "Must be tracking to determine kills and defs");
 243
 244   const MachineInstr &MI = *MBBI;
 245   LiveUnits.stepBackward(MI);
 246
 247   // Expire scavenge spill frameindex uses.
 248   for (ScavengedInfo &I : Scavenged) {
 249     if (I.Restore == &MI) {
 250       I.Reg = 0;
 251       I.Restore = nullptr;
 252     }
 253   }
 254
 255   if (MBBI == MBB->begin()) {
 256     MBBI = MachineBasicBlock::iterator(nullptr);
 257     Tracking = false;
 258   } else
 259     --MBBI;
 260 }
 261
 262 bool RegScavenger::isRegUsed(Register Reg, bool includeReserved) const {
 263   if (isReserved(Reg))
 264     return includeReserved;
 265   return !LiveUnits.available(Reg);
 266 }
 267
 268 Register RegScavenger::FindUnusedReg(const TargetRegisterClass *RC) const {
 269   for (Register Reg : *RC) {
 270     if (!isRegUsed(Reg)) {
 271       LLVM_DEBUG(dbgs() << "Scavenger found unused reg: " << printReg(Reg, TRI)
 272                         << "\n");
 273       return Reg;
 274     }
 275   }
 276   return 0;
 277 }
 278
 279 BitVector RegScavenger::getRegsAvailable(const TargetRegisterClass *RC) {
 280   BitVector Mask(TRI->getNumRegs());
 281   for (Register Reg : *RC)
 282     if (!isRegUsed(Reg))
 283       Mask.set(Reg);
 284   return Mask;
 285 }
 286
 287 Register RegScavenger::findSurvivorReg(MachineBasicBlock::iterator StartMI,
 288                                        BitVector &Candidates,
 289                                        unsigned InstrLimit,
 290                                        MachineBasicBlock::iterator &UseMI) {
 291   int Survivor = Candidates.find_first();
 292   assert(Survivor > 0 && "No candidates for scavenging");
 293
 294   MachineBasicBlock::iterator ME = MBB->getFirstTerminator();
 295   assert(StartMI != ME && "MI already at terminator");
 296   MachineBasicBlock::iterator RestorePointMI = StartMI;
 297   MachineBasicBlock::iterator MI = StartMI;
 298
 299   bool inVirtLiveRange = false;
 300   for (++MI; InstrLimit > 0 && MI != ME; ++MI, --InstrLimit) {
 301     if (MI->isDebugOrPseudoInstr()) {
 302       ++InstrLimit; // Don't count debug instructions
 303       continue;
 304     }
 305     bool isVirtKillInsn = false;
 306     bool isVirtDefInsn = false;
 307     // Remove any candidates touched by instruction.
 308     for (const MachineOperand &MO : MI->operands()) {
 309       if (MO.isRegMask())
 310         Candidates.clearBitsNotInMask(MO.getRegMask());
 311       if (!MO.isReg() || MO.isUndef() || !MO.getReg())
 312         continue;
 313       if (Register::isVirtualRegister(MO.getReg())) {
 314         if (MO.isDef())
 315           isVirtDefInsn = true;
 316         else if (MO.isKill())
 317           isVirtKillInsn = true;
 318         continue;
 319       }
 320       for (MCRegAliasIterator AI(MO.getReg(), TRI, true); AI.isValid(); ++AI)
 321         Candidates.reset(*AI);
 322     }
 323     // If we're not in a virtual reg's live range, this is a valid
 324     // restore point.
 325     if (!inVirtLiveRange) RestorePointMI = MI;
 326
 327     // Update whether we're in the live range of a virtual register
 328     if (isVirtKillInsn) inVirtLiveRange = false;
 329     if (isVirtDefInsn) inVirtLiveRange = true;
 330
 331     // Was our survivor untouched by this instruction?
 332     if (Candidates.test(Survivor))
 333       continue;
 334
 335     // All candidates gone?
 336     if (Candidates.none())
 337       break;
 338
 339     Survivor = Candidates.find_first();
 340   }
 341   // If we ran off the end, that's where we want to restore.
 342   if (MI == ME) RestorePointMI = ME;
 343   assert(RestorePointMI != StartMI &&
 344          "No available scavenger restore location!");
 345
 346   // We ran out of candidates, so stop the search.
 347   UseMI = RestorePointMI;
 348   return Survivor;
 349 }
 350
 351 /// Given the bitvector \p Available of free register units at position
 352 /// \p From. Search backwards to find a register that is part of \p
 353 /// Candidates and not used/clobbered until the point \p To. If there is
 354 /// multiple candidates continue searching and pick the one that is not used/
 355 /// clobbered for the longest time.
 356 /// Returns the register and the earliest position we know it to be free or
 357 /// the position MBB.end() if no register is available.
 358 static std::pair<MCPhysReg, MachineBasicBlock::iterator>
 359 findSurvivorBackwards(const MachineRegisterInfo &MRI,
 360     MachineBasicBlock::iterator From, MachineBasicBlock::iterator To,
 361     const LiveRegUnits &LiveOut, ArrayRef<MCPhysReg> AllocationOrder,
 362     bool RestoreAfter) {
 363   bool FoundTo = false;
 364   MCPhysReg Survivor = 0;
 365   MachineBasicBlock::iterator Pos;
 366   MachineBasicBlock &MBB = *From->getParent();
 367   unsigned InstrLimit = 25;
 368   unsigned InstrCountDown = InstrLimit;
 369   const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
 370   LiveRegUnits Used(TRI);
 371
 372   assert(From->getParent() == To->getParent() &&
 373          "Target instruction is in other than current basic block, use "
 374          "enterBasicBlockEnd first");
 375
 376   for (MachineBasicBlock::iterator I = From;; --I) {
 377     const MachineInstr &MI = *I;
 378
 379     Used.accumulate(MI);
 380
 381     if (I == To) {
 382       // See if one of the registers in RC wasn't used so far.
 383       for (MCPhysReg Reg : AllocationOrder) {
 384         if (!MRI.isReserved(Reg) && Used.available(Reg) &&
 385             LiveOut.available(Reg))
 386           return std::make_pair(Reg, MBB.end());
 387       }
 388       // Otherwise we will continue up to InstrLimit instructions to find
 389       // the register which is not defined/used for the longest time.
 390       FoundTo = true;
 391       Pos = To;
 392       // Note: It was fine so far to start our search at From, however now that
 393       // we have to spill, and can only place the restore after From then
 394       // add the regs used/defed by std::next(From) to the set.
 395       if (RestoreAfter)
 396         Used.accumulate(*std::next(From));
 397     }
 398     if (FoundTo) {
 399       if (Survivor == 0 || !Used.available(Survivor)) {
 400         MCPhysReg AvilableReg = 0;
 401         for (MCPhysReg Reg : AllocationOrder) {
 402           if (!MRI.isReserved(Reg) && Used.available(Reg)) {
 403             AvilableReg = Reg;
 404             break;
 405           }
 406         }
 407         if (AvilableReg == 0)
 408           break;
 409         Survivor = AvilableReg;
 410       }
 411       if (--InstrCountDown == 0)
 412         break;
 413
 414       // Keep searching when we find a vreg since the spilled register will
 415       // be usefull for this other vreg as well later.
 416       bool FoundVReg = false;
 417       for (const MachineOperand &MO : MI.operands()) {
 418         if (MO.isReg() && Register::isVirtualRegister(MO.getReg())) {
 419           FoundVReg = true;
 420           break;
 421         }
 422       }
 423       if (FoundVReg) {
 424         InstrCountDown = InstrLimit;
 425         Pos = I;
 426       }
 427       if (I == MBB.begin())
 428         break;
 429     }
 430     assert(I != MBB.begin() && "Did not find target instruction while "
 431                                "iterating backwards");
 432   }
 433
 434   return std::make_pair(Survivor, Pos);
 435 }
 436
 437 static unsigned getFrameIndexOperandNum(MachineInstr &MI) {
 438   unsigned i = 0;
 439   while (!MI.getOperand(i).isFI()) {
 440     ++i;
 441     assert(i < MI.getNumOperands() && "Instr doesn't have FrameIndex operand!");
 442   }
 443   return i;
 444 }
 445
 446 RegScavenger::ScavengedInfo &
 447 RegScavenger::spill(Register Reg, const TargetRegisterClass &RC, int SPAdj,
 448                     MachineBasicBlock::iterator Before,
 449                     MachineBasicBlock::iterator &UseMI) {
 450   // Find an available scavenging slot with size and alignment matching
 451   // the requirements of the class RC.
 452   const MachineFunction &MF = *Before->getMF();
 453   const MachineFrameInfo &MFI = MF.getFrameInfo();
 454   unsigned NeedSize = TRI->getSpillSize(RC);
 455   Align NeedAlign = TRI->getSpillAlign(RC);
 456
 457   unsigned SI = Scavenged.size(), Diff = std::numeric_limits<unsigned>::max();
 458   int FIB = MFI.getObjectIndexBegin(), FIE = MFI.getObjectIndexEnd();
 459   for (unsigned I = 0; I < Scavenged.size(); ++I) {
 460     if (Scavenged[I].Reg != 0)
 461       continue;
 462     // Verify that this slot is valid for this register.
 463     int FI = Scavenged[I].FrameIndex;
 464     if (FI < FIB || FI >= FIE)
 465       continue;
 466     unsigned S = MFI.getObjectSize(FI);
 467     Align A = MFI.getObjectAlign(FI);
 468     if (NeedSize > S || NeedAlign > A)
 469       continue;
 470     // Avoid wasting slots with large size and/or large alignment. Pick one
 471     // that is the best fit for this register class (in street metric).
 472     // Picking a larger slot than necessary could happen if a slot for a
 473     // larger register is reserved before a slot for a smaller one. When
 474     // trying to spill a smaller register, the large slot would be found
 475     // first, thus making it impossible to spill the larger register later.
 476     unsigned D = (S - NeedSize) + (A.value() - NeedAlign.value());
 477     if (D < Diff) {
 478       SI = I;
 479       Diff = D;
 480     }
 481   }
 482
 483   if (SI == Scavenged.size()) {
 484     // We need to scavenge a register but have no spill slot, the target
 485     // must know how to do it (if not, we'll assert below).
 486     Scavenged.push_back(ScavengedInfo(FIE));
 487   }
 488
 489   // Avoid infinite regress
 490   Scavenged[SI].Reg = Reg;
 491
 492   // If the target knows how to save/restore the register, let it do so;
 493   // otherwise, use the emergency stack spill slot.
 494   if (!TRI->saveScavengerRegister(*MBB, Before, UseMI, &RC, Reg)) {
 495     // Spill the scavenged register before \p Before.
 496     int FI = Scavenged[SI].FrameIndex;
 497     if (FI < FIB || FI >= FIE) {
 498       report_fatal_error(Twine("Error while trying to spill ") +
 499                          TRI->getName(Reg) + " from class " +
 500                          TRI->getRegClassName(&RC) +
 501                          ": Cannot scavenge register without an emergency "
 502                          "spill slot!");
 503     }
 504     TII->storeRegToStackSlot(*MBB, Before, Reg, true, FI, &RC, TRI);
 505     MachineBasicBlock::iterator II = std::prev(Before);
 506
 507     unsigned FIOperandNum = getFrameIndexOperandNum(*II);
 508     TRI->eliminateFrameIndex(II, SPAdj, FIOperandNum, this);
 509
 510     // Restore the scavenged register before its use (or first terminator).
 511     TII->loadRegFromStackSlot(*MBB, UseMI, Reg, FI, &RC, TRI);
 512     II = std::prev(UseMI);
 513
 514     FIOperandNum = getFrameIndexOperandNum(*II);
 515     TRI->eliminateFrameIndex(II, SPAdj, FIOperandNum, this);
 516   }
 517   return Scavenged[SI];
 518 }
 519
 520 Register RegScavenger::scavengeRegister(const TargetRegisterClass *RC,
 521                                         MachineBasicBlock::iterator I,
 522                                         int SPAdj, bool AllowSpill) {
 523   MachineInstr &MI = *I;
 524   const MachineFunction &MF = *MI.getMF();
 525   // Consider all allocatable registers in the register class initially
 526   BitVector Candidates = TRI->getAllocatableSet(MF, RC);
 527
 528   // Exclude all the registers being used by the instruction.
 529   for (const MachineOperand &MO : MI.operands()) {
 530     if (MO.isReg() && MO.getReg() != 0 && !(MO.isUse() && MO.isUndef()) &&
 531         !Register::isVirtualRegister(MO.getReg()))
 532       for (MCRegAliasIterator AI(MO.getReg(), TRI, true); AI.isValid(); ++AI)
 533         Candidates.reset(*AI);
 534   }
 535
 536   // If we have already scavenged some registers, remove them from the
 537   // candidates. If we end up recursively calling eliminateFrameIndex, we don't
 538   // want to be clobbering previously scavenged registers or their associated
 539   // stack slots.
 540   for (ScavengedInfo &SI : Scavenged) {
 541     if (SI.Reg) {
 542       if (isRegUsed(SI.Reg)) {
 543         LLVM_DEBUG(
 544           dbgs() << "Removing " << printReg(SI.Reg, TRI) <<
 545           " from scavenging candidates since it was already scavenged\n");
 546         for (MCRegAliasIterator AI(SI.Reg, TRI, true); AI.isValid(); ++AI)
 547           Candidates.reset(*AI);
 548       }
 549     }
 550   }
 551
 552   // Try to find a register that's unused if there is one, as then we won't
 553   // have to spill.
 554   BitVector Available = getRegsAvailable(RC);
 555   Available &= Candidates;
 556   if (Available.any())
 557     Candidates = Available;
 558
 559   // Find the register whose use is furthest away.
 560   MachineBasicBlock::iterator UseMI;
 561   Register SReg = findSurvivorReg(I, Candidates, 25, UseMI);
 562
 563   // If we found an unused register there is no reason to spill it.
 564   if (!isRegUsed(SReg)) {
 565     LLVM_DEBUG(dbgs() << "Scavenged register: " << printReg(SReg, TRI) << "\n");
 566     return SReg;
 567   }
 568
 569   if (!AllowSpill)
 570     return 0;
 571
 572 #ifndef NDEBUG
 573   for (ScavengedInfo &SI : Scavenged) {
 574     assert(SI.Reg != SReg && "scavenged a previously scavenged register");
 575   }
 576 #endif
 577
 578   ScavengedInfo &Scavenged = spill(SReg, *RC, SPAdj, I, UseMI);
 579   Scavenged.Restore = &*std::prev(UseMI);
 580
 581   LLVM_DEBUG(dbgs() << "Scavenged register (with spill): "
 582                     << printReg(SReg, TRI) << "\n");
 583
 584   return SReg;
 585 }
 586
 587 Register RegScavenger::scavengeRegisterBackwards(const TargetRegisterClass &RC,
 588                                                  MachineBasicBlock::iterator To,
 589                                                  bool RestoreAfter, int SPAdj,
 590                                                  bool AllowSpill) {
 591   const MachineBasicBlock &MBB = *To->getParent();
 592   const MachineFunction &MF = *MBB.getParent();
 593
 594   // Find the register whose use is furthest away.
 595   MachineBasicBlock::iterator UseMI;
 596   ArrayRef<MCPhysReg> AllocationOrder = RC.getRawAllocationOrder(MF);
 597   std::pair<MCPhysReg, MachineBasicBlock::iterator> P =
 598       findSurvivorBackwards(*MRI, MBBI, To, LiveUnits, AllocationOrder,
 599                             RestoreAfter);
 600   MCPhysReg Reg = P.first;
 601   MachineBasicBlock::iterator SpillBefore = P.second;
 602   // Found an available register?
 603   if (Reg != 0 && SpillBefore == MBB.end()) {
 604     LLVM_DEBUG(dbgs() << "Scavenged free register: " << printReg(Reg, TRI)
 605                << '\n');
 606     return Reg;
 607   }
 608
 609   if (!AllowSpill)
 610     return 0;
 611
 612   assert(Reg != 0 && "No register left to scavenge!");
 613
 614   MachineBasicBlock::iterator ReloadAfter =
 615     RestoreAfter ? std::next(MBBI) : MBBI;
 616   MachineBasicBlock::iterator ReloadBefore = std::next(ReloadAfter);
 617   if (ReloadBefore != MBB.end())
 618     LLVM_DEBUG(dbgs() << "Reload before: " << *ReloadBefore << '\n');
 619   ScavengedInfo &Scavenged = spill(Reg, RC, SPAdj, SpillBefore, ReloadBefore);
 620   Scavenged.Restore = &*std::prev(SpillBefore);
 621   LiveUnits.removeReg(Reg);
 622   LLVM_DEBUG(dbgs() << "Scavenged register with spill: " << printReg(Reg, TRI)
 623              << " until " << *SpillBefore);
 624   return Reg;
 625 }
 626
 627 /// Allocate a register for the virtual register \p VReg. The last use of
 628 /// \p VReg is around the current position of the register scavenger \p RS.
 629 /// \p ReserveAfter controls whether the scavenged register needs to be reserved
 630 /// after the current instruction, otherwise it will only be reserved before the
 631 /// current instruction.
 632 static Register scavengeVReg(MachineRegisterInfo &MRI, RegScavenger &RS,
 633                              Register VReg, bool ReserveAfter) {
 634   const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
 635 #ifndef NDEBUG
 636   // Verify that all definitions and uses are in the same basic block.
 637   const MachineBasicBlock *CommonMBB = nullptr;
 638   // Real definition for the reg, re-definitions are not considered.
 639   const MachineInstr *RealDef = nullptr;
 640   for (MachineOperand &MO : MRI.reg_nodbg_operands(VReg)) {
 641     MachineBasicBlock *MBB = MO.getParent()->getParent();
 642     if (CommonMBB == nullptr)
 643       CommonMBB = MBB;
 644     assert(MBB == CommonMBB && "All defs+uses must be in the same basic block");
 645     if (MO.isDef()) {
 646       const MachineInstr &MI = *MO.getParent();
 647       if (!MI.readsRegister(VReg, &TRI)) {
 648         assert((!RealDef || RealDef == &MI) &&
 649                "Can have at most one definition which is not a redefinition");
 650         RealDef = &MI;
 651       }
 652     }
 653   }
 654   assert(RealDef != nullptr && "Must have at least 1 Def");
 655 #endif
 656
 657   // We should only have one definition of the register. However to accommodate
 658   // the requirements of two address code we also allow definitions in
 659   // subsequent instructions provided they also read the register. That way
 660   // we get a single contiguous lifetime.
 661   //
 662   // Definitions in MRI.def_begin() are unordered, search for the first.
 663   MachineRegisterInfo::def_iterator FirstDef = llvm::find_if(
 664       MRI.def_operands(VReg), [VReg, &TRI](const MachineOperand &MO) {
 665         return !MO.getParent()->readsRegister(VReg, &TRI);
 666       });
 667   assert(FirstDef != MRI.def_end() &&
 668          "Must have one definition that does not redefine vreg");
 669   MachineInstr &DefMI = *FirstDef->getParent();
 670
 671   // The register scavenger will report a free register inserting an emergency
 672   // spill/reload if necessary.
 673   int SPAdj = 0;
 674   const TargetRegisterClass &RC = *MRI.getRegClass(VReg);
 675   Register SReg = RS.scavengeRegisterBackwards(RC, DefMI.getIterator(),
 676                                                ReserveAfter, SPAdj);
 677   MRI.replaceRegWith(VReg, SReg);
 678   ++NumScavengedRegs;
 679   return SReg;
 680 }
 681
 682 /// Allocate (scavenge) vregs inside a single basic block.
 683 /// Returns true if the target spill callback created new vregs and a 2nd pass
 684 /// is necessary.
 685 static bool scavengeFrameVirtualRegsInBlock(MachineRegisterInfo &MRI,
 686                                             RegScavenger &RS,
 687                                             MachineBasicBlock &MBB) {
 688   const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
 689   RS.enterBasicBlockEnd(MBB);
 690
 691   unsigned InitialNumVirtRegs = MRI.getNumVirtRegs();
 692   bool NextInstructionReadsVReg = false;
 693   for (MachineBasicBlock::iterator I = MBB.end(); I != MBB.begin(); ) {
 694     --I;
 695     // Move RegScavenger to the position between *I and *std::next(I).
 696     RS.backward(I);
 697
 698     // Look for unassigned vregs in the uses of *std::next(I).
 699     if (NextInstructionReadsVReg) {
 700       MachineBasicBlock::iterator N = std::next(I);
 701       const MachineInstr &NMI = *N;
 702       for (const MachineOperand &MO : NMI.operands()) {
 703         if (!MO.isReg())
 704           continue;
 705         Register Reg = MO.getReg();
 706         // We only care about virtual registers and ignore virtual registers
 707         // created by the target callbacks in the process (those will be handled
 708         // in a scavenging round).
 709         if (!Register::isVirtualRegister(Reg) ||
 710             Register::virtReg2Index(Reg) >= InitialNumVirtRegs)
 711           continue;
 712         if (!MO.readsReg())
 713           continue;
 714
 715         Register SReg = scavengeVReg(MRI, RS, Reg, true);
 716         N->addRegisterKilled(SReg, &TRI, false);
 717         RS.setRegUsed(SReg);
 718       }
 719     }
 720
 721     // Look for unassigned vregs in the defs of *I.
 722     NextInstructionReadsVReg = false;
 723     const MachineInstr &MI = *I;
 724     for (const MachineOperand &MO : MI.operands()) {
 725       if (!MO.isReg())
 726         continue;
 727       Register Reg = MO.getReg();
 728       // Only vregs, no newly created vregs (see above).
 729       if (!Register::isVirtualRegister(Reg) ||
 730           Register::virtReg2Index(Reg) >= InitialNumVirtRegs)
 731         continue;
 732       // We have to look at all operands anyway so we can precalculate here
 733       // whether there is a reading operand. This allows use to skip the use
 734       // step in the next iteration if there was none.
 735       assert(!MO.isInternalRead() && "Cannot assign inside bundles");
 736       assert((!MO.isUndef() || MO.isDef()) && "Cannot handle undef uses");
 737       if (MO.readsReg()) {
 738         NextInstructionReadsVReg = true;
 739       }
 740       if (MO.isDef()) {
 741         Register SReg = scavengeVReg(MRI, RS, Reg, false);
 742         I->addRegisterDead(SReg, &TRI, false);
 743       }
 744     }
 745   }
 746 #ifndef NDEBUG
 747   for (const MachineOperand &MO : MBB.front().operands()) {
 748     if (!MO.isReg() || !Register::isVirtualRegister(MO.getReg()))
 749       continue;
 750     assert(!MO.isInternalRead() && "Cannot assign inside bundles");
 751     assert((!MO.isUndef() || MO.isDef()) && "Cannot handle undef uses");
 752     assert(!MO.readsReg() && "Vreg use in first instruction not allowed");
 753   }
 754 #endif
 755
 756   return MRI.getNumVirtRegs() != InitialNumVirtRegs;
 757 }
 758
 759 void llvm::scavengeFrameVirtualRegs(MachineFunction &MF, RegScavenger &RS) {
 760   // FIXME: Iterating over the instruction stream is unnecessary. We can simply
 761   // iterate over the vreg use list, which at this point only contains machine
 762   // operands for which eliminateFrameIndex need a new scratch reg.
 763   MachineRegisterInfo &MRI = MF.getRegInfo();
 764   // Shortcut.
 765   if (MRI.getNumVirtRegs() == 0) {
 766     MF.getProperties().set(MachineFunctionProperties::Property::NoVRegs);
 767     return;
 768   }
 769
 770   // Run through the instructions and find any virtual registers.
 771   for (MachineBasicBlock &MBB : MF) {
 772     if (MBB.empty())
 773       continue;
 774
 775     bool Again = scavengeFrameVirtualRegsInBlock(MRI, RS, MBB);
 776     if (Again) {
 777       LLVM_DEBUG(dbgs() << "Warning: Required two scavenging passes for block "
 778                         << MBB.getName() << '\n');
 779       Again = scavengeFrameVirtualRegsInBlock(MRI, RS, MBB);
 780       // The target required a 2nd run (because it created new vregs while
 781       // spilling). Refuse to do another pass to keep compiletime in check.
 782       if (Again)
 783         report_fatal_error("Incomplete scavenging after 2nd pass");
 784     }
 785   }
 786
 787   MRI.clearVirtRegs();
 788   MF.getProperties().set(MachineFunctionProperties::Property::NoVRegs);
 789 }
 790
 791 namespace {
 792
 793 /// This class runs register scavenging independ of the PrologEpilogInserter.
 794 /// This is used in for testing.
 795 class ScavengerTest : public MachineFunctionPass {
 796 public:
 797   static char ID;
 798
 799   ScavengerTest() : MachineFunctionPass(ID) {}
 800
 801   bool runOnMachineFunction(MachineFunction &MF) override {
 802     const TargetSubtargetInfo &STI = MF.getSubtarget();
 803     const TargetFrameLowering &TFL = *STI.getFrameLowering();
 804
 805     RegScavenger RS;
 806     // Let's hope that calling those outside of PrologEpilogueInserter works
 807     // well enough to initialize the scavenger with some emergency spillslots
 808     // for the target.
 809     BitVector SavedRegs;
 810     TFL.determineCalleeSaves(MF, SavedRegs, &RS);
 811     TFL.processFunctionBeforeFrameFinalized(MF, &RS);
 812
 813     // Let's scavenge the current function
 814     scavengeFrameVirtualRegs(MF, RS);
 815     return true;
 816   }
 817 };
 818
 819 } // end anonymous namespace
 820
 821 char ScavengerTest::ID;
 822
 823 INITIALIZE_PASS(ScavengerTest, "scavenger-test",
 824                 "Scavenge virtual registers inside basic blocks", false, false)