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