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 <cassert>
  41 #include <iterator>
  42 #include <limits>
  43 #include <utility>
  44
  45 using namespace llvm;
  46
  47 #define DEBUG_TYPE "reg-scavenging"
  48
  49 STATISTIC(NumScavengedRegs, "Number of frame index regs scavenged");
  50
  51 void RegScavenger::setRegUsed(Register Reg, LaneBitmask LaneMask) {
  52   LiveUnits.addRegMasked(Reg, LaneMask);
  53 }
  54
  55 void RegScavenger::init(MachineBasicBlock &MBB) {
  56   MachineFunction &MF = *MBB.getParent();
  57   TII = MF.getSubtarget().getInstrInfo();
  58   TRI = MF.getSubtarget().getRegisterInfo();
  59   MRI = &MF.getRegInfo();
  60   LiveUnits.init(*TRI);
  61
  62   this->MBB = &MBB;
  63
  64   for (ScavengedInfo &SI : Scavenged) {
  65     SI.Reg = 0;
  66     SI.Restore = nullptr;
  67   }
  68
  69   Tracking = false;
  70 }
  71
  72 void RegScavenger::enterBasicBlock(MachineBasicBlock &MBB) {
  73   init(MBB);
  74   LiveUnits.addLiveIns(MBB);
  75 }
  76
  77 void RegScavenger::enterBasicBlockEnd(MachineBasicBlock &MBB) {
  78   init(MBB);
  79   LiveUnits.addLiveOuts(MBB);
  80
  81   // Move internal iterator at the last instruction of the block.
  82   if (!MBB.empty()) {
  83     MBBI = std::prev(MBB.end());
  84     Tracking = true;
  85   }
  86 }
  87
  88 void RegScavenger::backward() {
  89   assert(Tracking && "Must be tracking to determine kills and defs");
  90
  91   const MachineInstr &MI = *MBBI;
  92   LiveUnits.stepBackward(MI);
  93
  94   // Expire scavenge spill frameindex uses.
  95   for (ScavengedInfo &I : Scavenged) {
  96     if (I.Restore == &MI) {
  97       I.Reg = 0;
  98       I.Restore = nullptr;
  99     }
 100   }
 101
 102   if (MBBI == MBB->begin()) {
 103     MBBI = MachineBasicBlock::iterator(nullptr);
 104     Tracking = false;
 105   } else
 106     --MBBI;
 107 }
 108
 109 bool RegScavenger::isRegUsed(Register Reg, bool includeReserved) const {
 110   if (isReserved(Reg))
 111     return includeReserved;
 112   return !LiveUnits.available(Reg);
 113 }
 114
 115 Register RegScavenger::FindUnusedReg(const TargetRegisterClass *RC) const {
 116   for (Register Reg : *RC) {
 117     if (!isRegUsed(Reg)) {
 118       LLVM_DEBUG(dbgs() << "Scavenger found unused reg: " << printReg(Reg, TRI)
 119                         << "\n");
 120       return Reg;
 121     }
 122   }
 123   return 0;
 124 }
 125
 126 BitVector RegScavenger::getRegsAvailable(const TargetRegisterClass *RC) {
 127   BitVector Mask(TRI->getNumRegs());
 128   for (Register Reg : *RC)
 129     if (!isRegUsed(Reg))
 130       Mask.set(Reg);
 131   return Mask;
 132 }
 133
 134 /// Given the bitvector \p Available of free register units at position
 135 /// \p From. Search backwards to find a register that is part of \p
 136 /// Candidates and not used/clobbered until the point \p To. If there is
 137 /// multiple candidates continue searching and pick the one that is not used/
 138 /// clobbered for the longest time.
 139 /// Returns the register and the earliest position we know it to be free or
 140 /// the position MBB.end() if no register is available.
 141 static std::pair<MCPhysReg, MachineBasicBlock::iterator>
 142 findSurvivorBackwards(const MachineRegisterInfo &MRI,
 143     MachineBasicBlock::iterator From, MachineBasicBlock::iterator To,
 144     const LiveRegUnits &LiveOut, ArrayRef<MCPhysReg> AllocationOrder,
 145     bool RestoreAfter) {
 146   bool FoundTo = false;
 147   MCPhysReg Survivor = 0;
 148   MachineBasicBlock::iterator Pos;
 149   MachineBasicBlock &MBB = *From->getParent();
 150   unsigned InstrLimit = 25;
 151   unsigned InstrCountDown = InstrLimit;
 152   const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
 153   LiveRegUnits Used(TRI);
 154
 155   assert(From->getParent() == To->getParent() &&
 156          "Target instruction is in other than current basic block, use "
 157          "enterBasicBlockEnd first");
 158
 159   for (MachineBasicBlock::iterator I = From;; --I) {
 160     const MachineInstr &MI = *I;
 161
 162     Used.accumulate(MI);
 163
 164     if (I == To) {
 165       // See if one of the registers in RC wasn't used so far.
 166       for (MCPhysReg Reg : AllocationOrder) {
 167         if (!MRI.isReserved(Reg) && Used.available(Reg) &&
 168             LiveOut.available(Reg))
 169           return std::make_pair(Reg, MBB.end());
 170       }
 171       // Otherwise we will continue up to InstrLimit instructions to find
 172       // the register which is not defined/used for the longest time.
 173       FoundTo = true;
 174       Pos = To;
 175       // Note: It was fine so far to start our search at From, however now that
 176       // we have to spill, and can only place the restore after From then
 177       // add the regs used/defed by std::next(From) to the set.
 178       if (RestoreAfter)
 179         Used.accumulate(*std::next(From));
 180     }
 181     if (FoundTo) {
 182       // Don't search to FrameSetup instructions if we were searching from
 183       // Non-FrameSetup instructions. Otherwise, the spill position may point
 184       // before FrameSetup instructions.
 185       if (!From->getFlag(MachineInstr::FrameSetup) &&
 186           MI.getFlag(MachineInstr::FrameSetup))
 187         break;
 188
 189       if (Survivor == 0 || !Used.available(Survivor)) {
 190         MCPhysReg AvilableReg = 0;
 191         for (MCPhysReg Reg : AllocationOrder) {
 192           if (!MRI.isReserved(Reg) && Used.available(Reg)) {
 193             AvilableReg = Reg;
 194             break;
 195           }
 196         }
 197         if (AvilableReg == 0)
 198           break;
 199         Survivor = AvilableReg;
 200       }
 201       if (--InstrCountDown == 0)
 202         break;
 203
 204       // Keep searching when we find a vreg since the spilled register will
 205       // be usefull for this other vreg as well later.
 206       bool FoundVReg = false;
 207       for (const MachineOperand &MO : MI.operands()) {
 208         if (MO.isReg() && MO.getReg().isVirtual()) {
 209           FoundVReg = true;
 210           break;
 211         }
 212       }
 213       if (FoundVReg) {
 214         InstrCountDown = InstrLimit;
 215         Pos = I;
 216       }
 217       if (I == MBB.begin())
 218         break;
 219     }
 220     assert(I != MBB.begin() && "Did not find target instruction while "
 221                                "iterating backwards");
 222   }
 223
 224   return std::make_pair(Survivor, Pos);
 225 }
 226
 227 static unsigned getFrameIndexOperandNum(MachineInstr &MI) {
 228   unsigned i = 0;
 229   while (!MI.getOperand(i).isFI()) {
 230     ++i;
 231     assert(i < MI.getNumOperands() && "Instr doesn't have FrameIndex operand!");
 232   }
 233   return i;
 234 }
 235
 236 RegScavenger::ScavengedInfo &
 237 RegScavenger::spill(Register Reg, const TargetRegisterClass &RC, int SPAdj,
 238                     MachineBasicBlock::iterator Before,
 239                     MachineBasicBlock::iterator &UseMI) {
 240   // Find an available scavenging slot with size and alignment matching
 241   // the requirements of the class RC.
 242   const MachineFunction &MF = *Before->getMF();
 243   const MachineFrameInfo &MFI = MF.getFrameInfo();
 244   unsigned NeedSize = TRI->getSpillSize(RC);
 245   Align NeedAlign = TRI->getSpillAlign(RC);
 246
 247   unsigned SI = Scavenged.size(), Diff = std::numeric_limits<unsigned>::max();
 248   int FIB = MFI.getObjectIndexBegin(), FIE = MFI.getObjectIndexEnd();
 249   for (unsigned I = 0; I < Scavenged.size(); ++I) {
 250     if (Scavenged[I].Reg != 0)
 251       continue;
 252     // Verify that this slot is valid for this register.
 253     int FI = Scavenged[I].FrameIndex;
 254     if (FI < FIB || FI >= FIE)
 255       continue;
 256     unsigned S = MFI.getObjectSize(FI);
 257     Align A = MFI.getObjectAlign(FI);
 258     if (NeedSize > S || NeedAlign > A)
 259       continue;
 260     // Avoid wasting slots with large size and/or large alignment. Pick one
 261     // that is the best fit for this register class (in street metric).
 262     // Picking a larger slot than necessary could happen if a slot for a
 263     // larger register is reserved before a slot for a smaller one. When
 264     // trying to spill a smaller register, the large slot would be found
 265     // first, thus making it impossible to spill the larger register later.
 266     unsigned D = (S - NeedSize) + (A.value() - NeedAlign.value());
 267     if (D < Diff) {
 268       SI = I;
 269       Diff = D;
 270     }
 271   }
 272
 273   if (SI == Scavenged.size()) {
 274     // We need to scavenge a register but have no spill slot, the target
 275     // must know how to do it (if not, we'll assert below).
 276     Scavenged.push_back(ScavengedInfo(FIE));
 277   }
 278
 279   // Avoid infinite regress
 280   Scavenged[SI].Reg = Reg;
 281
 282   // If the target knows how to save/restore the register, let it do so;
 283   // otherwise, use the emergency stack spill slot.
 284   if (!TRI->saveScavengerRegister(*MBB, Before, UseMI, &RC, Reg)) {
 285     // Spill the scavenged register before \p Before.
 286     int FI = Scavenged[SI].FrameIndex;
 287     if (FI < FIB || FI >= FIE) {
 288       report_fatal_error(Twine("Error while trying to spill ") +
 289                          TRI->getName(Reg) + " from class " +
 290                          TRI->getRegClassName(&RC) +
 291                          ": Cannot scavenge register without an emergency "
 292                          "spill slot!");
 293     }
 294     TII->storeRegToStackSlot(*MBB, Before, Reg, true, FI, &RC, TRI, Register());
 295     MachineBasicBlock::iterator II = std::prev(Before);
 296
 297     unsigned FIOperandNum = getFrameIndexOperandNum(*II);
 298     TRI->eliminateFrameIndex(II, SPAdj, FIOperandNum, this);
 299
 300     // Restore the scavenged register before its use (or first terminator).
 301     TII->loadRegFromStackSlot(*MBB, UseMI, Reg, FI, &RC, TRI, Register());
 302     II = std::prev(UseMI);
 303
 304     FIOperandNum = getFrameIndexOperandNum(*II);
 305     TRI->eliminateFrameIndex(II, SPAdj, FIOperandNum, this);
 306   }
 307   return Scavenged[SI];
 308 }
 309
 310 Register RegScavenger::scavengeRegisterBackwards(const TargetRegisterClass &RC,
 311                                                  MachineBasicBlock::iterator To,
 312                                                  bool RestoreAfter, int SPAdj,
 313                                                  bool AllowSpill) {
 314   const MachineBasicBlock &MBB = *To->getParent();
 315   const MachineFunction &MF = *MBB.getParent();
 316
 317   // Find the register whose use is furthest away.
 318   MachineBasicBlock::iterator UseMI;
 319   ArrayRef<MCPhysReg> AllocationOrder = RC.getRawAllocationOrder(MF);
 320   std::pair<MCPhysReg, MachineBasicBlock::iterator> P =
 321       findSurvivorBackwards(*MRI, MBBI, To, LiveUnits, AllocationOrder,
 322                             RestoreAfter);
 323   MCPhysReg Reg = P.first;
 324   MachineBasicBlock::iterator SpillBefore = P.second;
 325   // Found an available register?
 326   if (Reg != 0 && SpillBefore == MBB.end()) {
 327     LLVM_DEBUG(dbgs() << "Scavenged free register: " << printReg(Reg, TRI)
 328                << '\n');
 329     return Reg;
 330   }
 331
 332   if (!AllowSpill)
 333     return 0;
 334
 335   assert(Reg != 0 && "No register left to scavenge!");
 336
 337   MachineBasicBlock::iterator ReloadAfter =
 338     RestoreAfter ? std::next(MBBI) : MBBI;
 339   MachineBasicBlock::iterator ReloadBefore = std::next(ReloadAfter);
 340   if (ReloadBefore != MBB.end())
 341     LLVM_DEBUG(dbgs() << "Reload before: " << *ReloadBefore << '\n');
 342   ScavengedInfo &Scavenged = spill(Reg, RC, SPAdj, SpillBefore, ReloadBefore);
 343   Scavenged.Restore = &*std::prev(SpillBefore);
 344   LiveUnits.removeReg(Reg);
 345   LLVM_DEBUG(dbgs() << "Scavenged register with spill: " << printReg(Reg, TRI)
 346              << " until " << *SpillBefore);
 347   return Reg;
 348 }
 349
 350 /// Allocate a register for the virtual register \p VReg. The last use of
 351 /// \p VReg is around the current position of the register scavenger \p RS.
 352 /// \p ReserveAfter controls whether the scavenged register needs to be reserved
 353 /// after the current instruction, otherwise it will only be reserved before the
 354 /// current instruction.
 355 static Register scavengeVReg(MachineRegisterInfo &MRI, RegScavenger &RS,
 356                              Register VReg, bool ReserveAfter) {
 357   const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
 358 #ifndef NDEBUG
 359   // Verify that all definitions and uses are in the same basic block.
 360   const MachineBasicBlock *CommonMBB = nullptr;
 361   // Real definition for the reg, re-definitions are not considered.
 362   const MachineInstr *RealDef = nullptr;
 363   for (MachineOperand &MO : MRI.reg_nodbg_operands(VReg)) {
 364     MachineBasicBlock *MBB = MO.getParent()->getParent();
 365     if (CommonMBB == nullptr)
 366       CommonMBB = MBB;
 367     assert(MBB == CommonMBB && "All defs+uses must be in the same basic block");
 368     if (MO.isDef()) {
 369       const MachineInstr &MI = *MO.getParent();
 370       if (!MI.readsRegister(VReg, &TRI)) {
 371         assert((!RealDef || RealDef == &MI) &&
 372                "Can have at most one definition which is not a redefinition");
 373         RealDef = &MI;
 374       }
 375     }
 376   }
 377   assert(RealDef != nullptr && "Must have at least 1 Def");
 378 #endif
 379
 380   // We should only have one definition of the register. However to accommodate
 381   // the requirements of two address code we also allow definitions in
 382   // subsequent instructions provided they also read the register. That way
 383   // we get a single contiguous lifetime.
 384   //
 385   // Definitions in MRI.def_begin() are unordered, search for the first.
 386   MachineRegisterInfo::def_iterator FirstDef = llvm::find_if(
 387       MRI.def_operands(VReg), [VReg, &TRI](const MachineOperand &MO) {
 388         return !MO.getParent()->readsRegister(VReg, &TRI);
 389       });
 390   assert(FirstDef != MRI.def_end() &&
 391          "Must have one definition that does not redefine vreg");
 392   MachineInstr &DefMI = *FirstDef->getParent();
 393
 394   // The register scavenger will report a free register inserting an emergency
 395   // spill/reload if necessary.
 396   int SPAdj = 0;
 397   const TargetRegisterClass &RC = *MRI.getRegClass(VReg);
 398   Register SReg = RS.scavengeRegisterBackwards(RC, DefMI.getIterator(),
 399                                                ReserveAfter, SPAdj);
 400   MRI.replaceRegWith(VReg, SReg);
 401   ++NumScavengedRegs;
 402   return SReg;
 403 }
 404
 405 /// Allocate (scavenge) vregs inside a single basic block.
 406 /// Returns true if the target spill callback created new vregs and a 2nd pass
 407 /// is necessary.
 408 static bool scavengeFrameVirtualRegsInBlock(MachineRegisterInfo &MRI,
 409                                             RegScavenger &RS,
 410                                             MachineBasicBlock &MBB) {
 411   const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
 412   RS.enterBasicBlockEnd(MBB);
 413
 414   unsigned InitialNumVirtRegs = MRI.getNumVirtRegs();
 415   bool NextInstructionReadsVReg = false;
 416   for (MachineBasicBlock::iterator I = MBB.end(); I != MBB.begin(); ) {
 417     --I;
 418     // Move RegScavenger to the position between *I and *std::next(I).
 419     RS.backward(I);
 420
 421     // Look for unassigned vregs in the uses of *std::next(I).
 422     if (NextInstructionReadsVReg) {
 423       MachineBasicBlock::iterator N = std::next(I);
 424       const MachineInstr &NMI = *N;
 425       for (const MachineOperand &MO : NMI.operands()) {
 426         if (!MO.isReg())
 427           continue;
 428         Register Reg = MO.getReg();
 429         // We only care about virtual registers and ignore virtual registers
 430         // created by the target callbacks in the process (those will be handled
 431         // in a scavenging round).
 432         if (!Reg.isVirtual() ||
 433             Register::virtReg2Index(Reg) >= InitialNumVirtRegs)
 434           continue;
 435         if (!MO.readsReg())
 436           continue;
 437
 438         Register SReg = scavengeVReg(MRI, RS, Reg, true);
 439         N->addRegisterKilled(SReg, &TRI, false);
 440         RS.setRegUsed(SReg);
 441       }
 442     }
 443
 444     // Look for unassigned vregs in the defs of *I.
 445     NextInstructionReadsVReg = false;
 446     const MachineInstr &MI = *I;
 447     for (const MachineOperand &MO : MI.operands()) {
 448       if (!MO.isReg())
 449         continue;
 450       Register Reg = MO.getReg();
 451       // Only vregs, no newly created vregs (see above).
 452       if (!Reg.isVirtual() ||
 453           Register::virtReg2Index(Reg) >= InitialNumVirtRegs)
 454         continue;
 455       // We have to look at all operands anyway so we can precalculate here
 456       // whether there is a reading operand. This allows use to skip the use
 457       // step in the next iteration if there was none.
 458       assert(!MO.isInternalRead() && "Cannot assign inside bundles");
 459       assert((!MO.isUndef() || MO.isDef()) && "Cannot handle undef uses");
 460       if (MO.readsReg()) {
 461         NextInstructionReadsVReg = true;
 462       }
 463       if (MO.isDef()) {
 464         Register SReg = scavengeVReg(MRI, RS, Reg, false);
 465         I->addRegisterDead(SReg, &TRI, false);
 466       }
 467     }
 468   }
 469 #ifndef NDEBUG
 470   for (const MachineOperand &MO : MBB.front().operands()) {
 471     if (!MO.isReg() || !MO.getReg().isVirtual())
 472       continue;
 473     assert(!MO.isInternalRead() && "Cannot assign inside bundles");
 474     assert((!MO.isUndef() || MO.isDef()) && "Cannot handle undef uses");
 475     assert(!MO.readsReg() && "Vreg use in first instruction not allowed");
 476   }
 477 #endif
 478
 479   return MRI.getNumVirtRegs() != InitialNumVirtRegs;
 480 }
 481
 482 void llvm::scavengeFrameVirtualRegs(MachineFunction &MF, RegScavenger &RS) {
 483   // FIXME: Iterating over the instruction stream is unnecessary. We can simply
 484   // iterate over the vreg use list, which at this point only contains machine
 485   // operands for which eliminateFrameIndex need a new scratch reg.
 486   MachineRegisterInfo &MRI = MF.getRegInfo();
 487   // Shortcut.
 488   if (MRI.getNumVirtRegs() == 0) {
 489     MF.getProperties().set(MachineFunctionProperties::Property::NoVRegs);
 490     return;
 491   }
 492
 493   // Run through the instructions and find any virtual registers.
 494   for (MachineBasicBlock &MBB : MF) {
 495     if (MBB.empty())
 496       continue;
 497
 498     bool Again = scavengeFrameVirtualRegsInBlock(MRI, RS, MBB);
 499     if (Again) {
 500       LLVM_DEBUG(dbgs() << "Warning: Required two scavenging passes for block "
 501                         << MBB.getName() << '\n');
 502       Again = scavengeFrameVirtualRegsInBlock(MRI, RS, MBB);
 503       // The target required a 2nd run (because it created new vregs while
 504       // spilling). Refuse to do another pass to keep compiletime in check.
 505       if (Again)
 506         report_fatal_error("Incomplete scavenging after 2nd pass");
 507     }
 508   }
 509
 510   MRI.clearVirtRegs();
 511   MF.getProperties().set(MachineFunctionProperties::Property::NoVRegs);
 512 }
 513
 514 namespace {
 515
 516 /// This class runs register scavenging independ of the PrologEpilogInserter.
 517 /// This is used in for testing.
 518 class ScavengerTest : public MachineFunctionPass {
 519 public:
 520   static char ID;
 521
 522   ScavengerTest() : MachineFunctionPass(ID) {}
 523
 524   bool runOnMachineFunction(MachineFunction &MF) override {
 525     const TargetSubtargetInfo &STI = MF.getSubtarget();
 526     const TargetFrameLowering &TFL = *STI.getFrameLowering();
 527
 528     RegScavenger RS;
 529     // Let's hope that calling those outside of PrologEpilogueInserter works
 530     // well enough to initialize the scavenger with some emergency spillslots
 531     // for the target.
 532     BitVector SavedRegs;
 533     TFL.determineCalleeSaves(MF, SavedRegs, &RS);
 534     TFL.processFunctionBeforeFrameFinalized(MF, &RS);
 535
 536     // Let's scavenge the current function
 537     scavengeFrameVirtualRegs(MF, RS);
 538     return true;
 539   }
 540 };
 541
 542 } // end anonymous namespace
 543
 544 char ScavengerTest::ID;
 545
 546 INITIALIZE_PASS(ScavengerTest, "scavenger-test",
 547                 "Scavenge virtual registers inside basic blocks", false, false)