LLVM  10.0.0svn
RegisterScavenging.cpp
Go to the documentation of this file.
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 
18 #include "llvm/ADT/ArrayRef.h"
19 #include "llvm/ADT/BitVector.h"
20 #include "llvm/ADT/SmallVector.h"
21 #include "llvm/ADT/Statistic.h"
34 #include "llvm/MC/MCRegisterInfo.h"
35 #include "llvm/Pass.h"
36 #include "llvm/Support/Debug.h"
39 #include <algorithm>
40 #include <cassert>
41 #include <iterator>
42 #include <limits>
43 #include <string>
44 #include <utility>
45 
46 using namespace llvm;
47 
48 #define DEBUG_TYPE "reg-scavenging"
49 
50 STATISTIC(NumScavengedRegs, "Number of frame index regs scavenged");
51 
53  LiveUnits.addRegMasked(Reg, LaneMask);
54 }
55 
56 void RegScavenger::init(MachineBasicBlock &MBB) {
57  MachineFunction &MF = *MBB.getParent();
58  TII = MF.getSubtarget().getInstrInfo();
60  MRI = &MF.getRegInfo();
61  LiveUnits.init(*TRI);
62 
63  assert((NumRegUnits == 0 || NumRegUnits == TRI->getNumRegUnits()) &&
64  "Target changed?");
65 
66  // Self-initialize.
67  if (!this->MBB) {
68  NumRegUnits = TRI->getNumRegUnits();
69  KillRegUnits.resize(NumRegUnits);
70  DefRegUnits.resize(NumRegUnits);
71  TmpRegUnits.resize(NumRegUnits);
72  }
73  this->MBB = &MBB;
74 
75  for (ScavengedInfo &SI : Scavenged) {
76  SI.Reg = 0;
77  SI.Restore = nullptr;
78  }
79 
80  Tracking = false;
81 }
82 
84  init(MBB);
85  LiveUnits.addLiveIns(MBB);
86 }
87 
89  init(MBB);
90  LiveUnits.addLiveOuts(MBB);
91 
92  // Move internal iterator at the last instruction of the block.
93  if (MBB.begin() != MBB.end()) {
94  MBBI = std::prev(MBB.end());
95  Tracking = true;
96  }
97 }
98 
99 void RegScavenger::addRegUnits(BitVector &BV, Register Reg) {
100  for (MCRegUnitIterator RUI(Reg, TRI); RUI.isValid(); ++RUI)
101  BV.set(*RUI);
102 }
103 
104 void RegScavenger::removeRegUnits(BitVector &BV, Register Reg) {
105  for (MCRegUnitIterator RUI(Reg, TRI); RUI.isValid(); ++RUI)
106  BV.reset(*RUI);
107 }
108 
109 void RegScavenger::determineKillsAndDefs() {
110  assert(Tracking && "Must be tracking to determine kills and defs");
111 
112  MachineInstr &MI = *MBBI;
113  assert(!MI.isDebugInstr() && "Debug values have no kills or defs");
114 
115  // Find out which registers are early clobbered, killed, defined, and marked
116  // def-dead in this instruction.
117  KillRegUnits.reset();
118  DefRegUnits.reset();
119  for (const MachineOperand &MO : MI.operands()) {
120  if (MO.isRegMask()) {
121  TmpRegUnits.clear();
122  for (unsigned RU = 0, RUEnd = TRI->getNumRegUnits(); RU != RUEnd; ++RU) {
123  for (MCRegUnitRootIterator RURI(RU, TRI); RURI.isValid(); ++RURI) {
124  if (MO.clobbersPhysReg(*RURI)) {
125  TmpRegUnits.set(RU);
126  break;
127  }
128  }
129  }
130 
131  // Apply the mask.
132  KillRegUnits |= TmpRegUnits;
133  }
134  if (!MO.isReg())
135  continue;
136  Register Reg = MO.getReg();
137  if (!Register::isPhysicalRegister(Reg) || isReserved(Reg))
138  continue;
139 
140  if (MO.isUse()) {
141  // Ignore undef uses.
142  if (MO.isUndef())
143  continue;
144  if (MO.isKill())
145  addRegUnits(KillRegUnits, Reg);
146  } else {
147  assert(MO.isDef());
148  if (MO.isDead())
149  addRegUnits(KillRegUnits, Reg);
150  else
151  addRegUnits(DefRegUnits, Reg);
152  }
153  }
154 }
155 
157  assert(Tracking && "Cannot unprocess because we're not tracking");
158 
159  MachineInstr &MI = *MBBI;
160  if (!MI.isDebugInstr()) {
161  determineKillsAndDefs();
162 
163  // Commit the changes.
164  setUnused(DefRegUnits);
165  setUsed(KillRegUnits);
166  }
167 
168  if (MBBI == MBB->begin()) {
169  MBBI = MachineBasicBlock::iterator(nullptr);
170  Tracking = false;
171  } else
172  --MBBI;
173 }
174 
176  // Move ptr forward.
177  if (!Tracking) {
178  MBBI = MBB->begin();
179  Tracking = true;
180  } else {
181  assert(MBBI != MBB->end() && "Already past the end of the basic block!");
182  MBBI = std::next(MBBI);
183  }
184  assert(MBBI != MBB->end() && "Already at the end of the basic block!");
185 
186  MachineInstr &MI = *MBBI;
187 
189  IE = Scavenged.end(); I != IE; ++I) {
190  if (I->Restore != &MI)
191  continue;
192 
193  I->Reg = 0;
194  I->Restore = nullptr;
195  }
196 
197  if (MI.isDebugInstr())
198  return;
199 
200  determineKillsAndDefs();
201 
202  // Verify uses and defs.
203 #ifndef NDEBUG
204  for (const MachineOperand &MO : MI.operands()) {
205  if (!MO.isReg())
206  continue;
207  Register Reg = MO.getReg();
208  if (!Register::isPhysicalRegister(Reg) || isReserved(Reg))
209  continue;
210  if (MO.isUse()) {
211  if (MO.isUndef())
212  continue;
213  if (!isRegUsed(Reg)) {
214  // Check if it's partial live: e.g.
215  // D0 = insert_subreg undef D0, S0
216  // ... D0
217  // The problem is the insert_subreg could be eliminated. The use of
218  // D0 is using a partially undef value. This is not *incorrect* since
219  // S1 is can be freely clobbered.
220  // Ideally we would like a way to model this, but leaving the
221  // insert_subreg around causes both correctness and performance issues.
222  bool SubUsed = false;
223  for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs)
224  if (isRegUsed(*SubRegs)) {
225  SubUsed = true;
226  break;
227  }
228  bool SuperUsed = false;
229  for (MCSuperRegIterator SR(Reg, TRI); SR.isValid(); ++SR) {
230  if (isRegUsed(*SR)) {
231  SuperUsed = true;
232  break;
233  }
234  }
235  if (!SubUsed && !SuperUsed) {
236  MBB->getParent()->verify(nullptr, "In Register Scavenger");
237  llvm_unreachable("Using an undefined register!");
238  }
239  (void)SubUsed;
240  (void)SuperUsed;
241  }
242  } else {
243  assert(MO.isDef());
244 #if 0
245  // FIXME: Enable this once we've figured out how to correctly transfer
246  // implicit kills during codegen passes like the coalescer.
247  assert((KillRegs.test(Reg) || isUnused(Reg) ||
248  isLiveInButUnusedBefore(Reg, MI, MBB, TRI, MRI)) &&
249  "Re-defining a live register!");
250 #endif
251  }
252  }
253 #endif // NDEBUG
254 
255  // Commit the changes.
256  setUnused(KillRegUnits);
257  setUsed(DefRegUnits);
258 }
259 
261  assert(Tracking && "Must be tracking to determine kills and defs");
262 
263  const MachineInstr &MI = *MBBI;
264  LiveUnits.stepBackward(MI);
265 
266  // Expire scavenge spill frameindex uses.
267  for (ScavengedInfo &I : Scavenged) {
268  if (I.Restore == &MI) {
269  I.Reg = 0;
270  I.Restore = nullptr;
271  }
272  }
273 
274  if (MBBI == MBB->begin()) {
275  MBBI = MachineBasicBlock::iterator(nullptr);
276  Tracking = false;
277  } else
278  --MBBI;
279 }
280 
281 bool RegScavenger::isRegUsed(Register Reg, bool includeReserved) const {
282  if (isReserved(Reg))
283  return includeReserved;
284  return !LiveUnits.available(Reg);
285 }
286 
288  for (Register Reg : *RC) {
289  if (!isRegUsed(Reg)) {
290  LLVM_DEBUG(dbgs() << "Scavenger found unused reg: " << printReg(Reg, TRI)
291  << "\n");
292  return Reg;
293  }
294  }
295  return 0;
296 }
297 
299  BitVector Mask(TRI->getNumRegs());
300  for (Register Reg : *RC)
301  if (!isRegUsed(Reg))
302  Mask.set(Reg);
303  return Mask;
304 }
305 
306 Register RegScavenger::findSurvivorReg(MachineBasicBlock::iterator StartMI,
307  BitVector &Candidates,
308  unsigned InstrLimit,
310  int Survivor = Candidates.find_first();
311  assert(Survivor > 0 && "No candidates for scavenging");
312 
314  assert(StartMI != ME && "MI already at terminator");
315  MachineBasicBlock::iterator RestorePointMI = StartMI;
317 
318  bool inVirtLiveRange = false;
319  for (++MI; InstrLimit > 0 && MI != ME; ++MI, --InstrLimit) {
320  if (MI->isDebugInstr()) {
321  ++InstrLimit; // Don't count debug instructions
322  continue;
323  }
324  bool isVirtKillInsn = false;
325  bool isVirtDefInsn = false;
326  // Remove any candidates touched by instruction.
327  for (const MachineOperand &MO : MI->operands()) {
328  if (MO.isRegMask())
329  Candidates.clearBitsNotInMask(MO.getRegMask());
330  if (!MO.isReg() || MO.isUndef() || !MO.getReg())
331  continue;
332  if (Register::isVirtualRegister(MO.getReg())) {
333  if (MO.isDef())
334  isVirtDefInsn = true;
335  else if (MO.isKill())
336  isVirtKillInsn = true;
337  continue;
338  }
339  for (MCRegAliasIterator AI(MO.getReg(), TRI, true); AI.isValid(); ++AI)
340  Candidates.reset(*AI);
341  }
342  // If we're not in a virtual reg's live range, this is a valid
343  // restore point.
344  if (!inVirtLiveRange) RestorePointMI = MI;
345 
346  // Update whether we're in the live range of a virtual register
347  if (isVirtKillInsn) inVirtLiveRange = false;
348  if (isVirtDefInsn) inVirtLiveRange = true;
349 
350  // Was our survivor untouched by this instruction?
351  if (Candidates.test(Survivor))
352  continue;
353 
354  // All candidates gone?
355  if (Candidates.none())
356  break;
357 
358  Survivor = Candidates.find_first();
359  }
360  // If we ran off the end, that's where we want to restore.
361  if (MI == ME) RestorePointMI = ME;
362  assert(RestorePointMI != StartMI &&
363  "No available scavenger restore location!");
364 
365  // We ran out of candidates, so stop the search.
366  UseMI = RestorePointMI;
367  return Survivor;
368 }
369 
370 /// Given the bitvector \p Available of free register units at position
371 /// \p From. Search backwards to find a register that is part of \p
372 /// Candidates and not used/clobbered until the point \p To. If there is
373 /// multiple candidates continue searching and pick the one that is not used/
374 /// clobbered for the longest time.
375 /// Returns the register and the earliest position we know it to be free or
376 /// the position MBB.end() if no register is available.
377 static std::pair<MCPhysReg, MachineBasicBlock::iterator>
381  bool RestoreAfter) {
382  bool FoundTo = false;
383  MCPhysReg Survivor = 0;
385  MachineBasicBlock &MBB = *From->getParent();
386  unsigned InstrLimit = 25;
387  unsigned InstrCountDown = InstrLimit;
389  LiveRegUnits Used(TRI);
390 
391  for (MachineBasicBlock::iterator I = From;; --I) {
392  const MachineInstr &MI = *I;
393 
394  Used.accumulate(MI);
395 
396  if (I == To) {
397  // See if one of the registers in RC wasn't used so far.
398  for (MCPhysReg Reg : AllocationOrder) {
399  if (!MRI.isReserved(Reg) && Used.available(Reg) &&
400  LiveOut.available(Reg))
401  return std::make_pair(Reg, MBB.end());
402  }
403  // Otherwise we will continue up to InstrLimit instructions to find
404  // the register which is not defined/used for the longest time.
405  FoundTo = true;
406  Pos = To;
407  // Note: It was fine so far to start our search at From, however now that
408  // we have to spill, and can only place the restore after From then
409  // add the regs used/defed by std::next(From) to the set.
410  if (RestoreAfter)
411  Used.accumulate(*std::next(From));
412  }
413  if (FoundTo) {
414  if (Survivor == 0 || !Used.available(Survivor)) {
415  MCPhysReg AvilableReg = 0;
416  for (MCPhysReg Reg : AllocationOrder) {
417  if (!MRI.isReserved(Reg) && Used.available(Reg)) {
418  AvilableReg = Reg;
419  break;
420  }
421  }
422  if (AvilableReg == 0)
423  break;
424  Survivor = AvilableReg;
425  }
426  if (--InstrCountDown == 0)
427  break;
428 
429  // Keep searching when we find a vreg since the spilled register will
430  // be usefull for this other vreg as well later.
431  bool FoundVReg = false;
432  for (const MachineOperand &MO : MI.operands()) {
433  if (MO.isReg() && Register::isVirtualRegister(MO.getReg())) {
434  FoundVReg = true;
435  break;
436  }
437  }
438  if (FoundVReg) {
439  InstrCountDown = InstrLimit;
440  Pos = I;
441  }
442  if (I == MBB.begin())
443  break;
444  }
445  }
446 
447  return std::make_pair(Survivor, Pos);
448 }
449 
451  unsigned i = 0;
452  while (!MI.getOperand(i).isFI()) {
453  ++i;
454  assert(i < MI.getNumOperands() && "Instr doesn't have FrameIndex operand!");
455  }
456  return i;
457 }
458 
459 RegScavenger::ScavengedInfo &
460 RegScavenger::spill(Register Reg, const TargetRegisterClass &RC, int SPAdj,
463  // Find an available scavenging slot with size and alignment matching
464  // the requirements of the class RC.
465  const MachineFunction &MF = *Before->getMF();
466  const MachineFrameInfo &MFI = MF.getFrameInfo();
467  unsigned NeedSize = TRI->getSpillSize(RC);
468  unsigned NeedAlign = TRI->getSpillAlignment(RC);
469 
470  unsigned SI = Scavenged.size(), Diff = std::numeric_limits<unsigned>::max();
471  int FIB = MFI.getObjectIndexBegin(), FIE = MFI.getObjectIndexEnd();
472  for (unsigned I = 0; I < Scavenged.size(); ++I) {
473  if (Scavenged[I].Reg != 0)
474  continue;
475  // Verify that this slot is valid for this register.
476  int FI = Scavenged[I].FrameIndex;
477  if (FI < FIB || FI >= FIE)
478  continue;
479  unsigned S = MFI.getObjectSize(FI);
480  unsigned A = MFI.getObjectAlignment(FI);
481  if (NeedSize > S || NeedAlign > A)
482  continue;
483  // Avoid wasting slots with large size and/or large alignment. Pick one
484  // that is the best fit for this register class (in street metric).
485  // Picking a larger slot than necessary could happen if a slot for a
486  // larger register is reserved before a slot for a smaller one. When
487  // trying to spill a smaller register, the large slot would be found
488  // first, thus making it impossible to spill the larger register later.
489  unsigned D = (S-NeedSize) + (A-NeedAlign);
490  if (D < Diff) {
491  SI = I;
492  Diff = D;
493  }
494  }
495 
496  if (SI == Scavenged.size()) {
497  // We need to scavenge a register but have no spill slot, the target
498  // must know how to do it (if not, we'll assert below).
499  Scavenged.push_back(ScavengedInfo(FIE));
500  }
501 
502  // Avoid infinite regress
503  Scavenged[SI].Reg = Reg;
504 
505  // If the target knows how to save/restore the register, let it do so;
506  // otherwise, use the emergency stack spill slot.
507  if (!TRI->saveScavengerRegister(*MBB, Before, UseMI, &RC, Reg)) {
508  // Spill the scavenged register before \p Before.
509  int FI = Scavenged[SI].FrameIndex;
510  if (FI < FIB || FI >= FIE) {
511  std::string Msg = std::string("Error while trying to spill ") +
512  TRI->getName(Reg) + " from class " + TRI->getRegClassName(&RC) +
513  ": Cannot scavenge register without an emergency spill slot!";
514  report_fatal_error(Msg.c_str());
515  }
516  TII->storeRegToStackSlot(*MBB, Before, Reg, true, Scavenged[SI].FrameIndex,
517  &RC, TRI);
518  MachineBasicBlock::iterator II = std::prev(Before);
519 
520  unsigned FIOperandNum = getFrameIndexOperandNum(*II);
521  TRI->eliminateFrameIndex(II, SPAdj, FIOperandNum, this);
522 
523  // Restore the scavenged register before its use (or first terminator).
524  TII->loadRegFromStackSlot(*MBB, UseMI, Reg, Scavenged[SI].FrameIndex,
525  &RC, TRI);
526  II = std::prev(UseMI);
527 
528  FIOperandNum = getFrameIndexOperandNum(*II);
529  TRI->eliminateFrameIndex(II, SPAdj, FIOperandNum, this);
530  }
531  return Scavenged[SI];
532 }
533 
536  int SPAdj, bool AllowSpill) {
537  MachineInstr &MI = *I;
538  const MachineFunction &MF = *MI.getMF();
539  // Consider all allocatable registers in the register class initially
540  BitVector Candidates = TRI->getAllocatableSet(MF, RC);
541 
542  // Exclude all the registers being used by the instruction.
543  for (const MachineOperand &MO : MI.operands()) {
544  if (MO.isReg() && MO.getReg() != 0 && !(MO.isUse() && MO.isUndef()) &&
545  !Register::isVirtualRegister(MO.getReg()))
546  for (MCRegAliasIterator AI(MO.getReg(), TRI, true); AI.isValid(); ++AI)
547  Candidates.reset(*AI);
548  }
549 
550  // Try to find a register that's unused if there is one, as then we won't
551  // have to spill.
552  BitVector Available = getRegsAvailable(RC);
553  Available &= Candidates;
554  if (Available.any())
555  Candidates = Available;
556 
557  // Find the register whose use is furthest away.
559  Register SReg = findSurvivorReg(I, Candidates, 25, UseMI);
560 
561  // If we found an unused register there is no reason to spill it.
562  if (!isRegUsed(SReg)) {
563  LLVM_DEBUG(dbgs() << "Scavenged register: " << printReg(SReg, TRI) << "\n");
564  return SReg;
565  }
566 
567  if (!AllowSpill)
568  return 0;
569 
570  ScavengedInfo &Scavenged = spill(SReg, *RC, SPAdj, I, UseMI);
571  Scavenged.Restore = &*std::prev(UseMI);
572 
573  LLVM_DEBUG(dbgs() << "Scavenged register (with spill): "
574  << printReg(SReg, TRI) << "\n");
575 
576  return SReg;
577 }
578 
581  bool RestoreAfter, int SPAdj,
582  bool AllowSpill) {
583  const MachineBasicBlock &MBB = *To->getParent();
584  const MachineFunction &MF = *MBB.getParent();
585 
586  // Find the register whose use is furthest away.
589  std::pair<MCPhysReg, MachineBasicBlock::iterator> P =
590  findSurvivorBackwards(*MRI, MBBI, To, LiveUnits, AllocationOrder,
591  RestoreAfter);
592  MCPhysReg Reg = P.first;
593  MachineBasicBlock::iterator SpillBefore = P.second;
594  assert(Reg != 0 && "No register left to scavenge!");
595  // Found an available register?
596  if (SpillBefore == MBB.end()) {
597  LLVM_DEBUG(dbgs() << "Scavenged free register: " << printReg(Reg, TRI)
598  << '\n');
599  return Reg;
600  }
601 
602  if (!AllowSpill)
603  return 0;
604 
605  MachineBasicBlock::iterator ReloadAfter =
606  RestoreAfter ? std::next(MBBI) : MBBI;
607  MachineBasicBlock::iterator ReloadBefore = std::next(ReloadAfter);
608  if (ReloadBefore != MBB.end())
609  LLVM_DEBUG(dbgs() << "Reload before: " << *ReloadBefore << '\n');
610  ScavengedInfo &Scavenged = spill(Reg, RC, SPAdj, SpillBefore, ReloadBefore);
611  Scavenged.Restore = &*std::prev(SpillBefore);
612  LiveUnits.removeReg(Reg);
613  LLVM_DEBUG(dbgs() << "Scavenged register with spill: " << printReg(Reg, TRI)
614  << " until " << *SpillBefore);
615  return Reg;
616 }
617 
618 /// Allocate a register for the virtual register \p VReg. The last use of
619 /// \p VReg is around the current position of the register scavenger \p RS.
620 /// \p ReserveAfter controls whether the scavenged register needs to be reserved
621 /// after the current instruction, otherwise it will only be reserved before the
622 /// current instruction.
624  Register VReg, bool ReserveAfter) {
626 #ifndef NDEBUG
627  // Verify that all definitions and uses are in the same basic block.
628  const MachineBasicBlock *CommonMBB = nullptr;
629  // Real definition for the reg, re-definitions are not considered.
630  const MachineInstr *RealDef = nullptr;
631  for (MachineOperand &MO : MRI.reg_nodbg_operands(VReg)) {
632  MachineBasicBlock *MBB = MO.getParent()->getParent();
633  if (CommonMBB == nullptr)
634  CommonMBB = MBB;
635  assert(MBB == CommonMBB && "All defs+uses must be in the same basic block");
636  if (MO.isDef()) {
637  const MachineInstr &MI = *MO.getParent();
638  if (!MI.readsRegister(VReg, &TRI)) {
639  assert((!RealDef || RealDef == &MI) &&
640  "Can have at most one definition which is not a redefinition");
641  RealDef = &MI;
642  }
643  }
644  }
645  assert(RealDef != nullptr && "Must have at least 1 Def");
646 #endif
647 
648  // We should only have one definition of the register. However to accommodate
649  // the requirements of two address code we also allow definitions in
650  // subsequent instructions provided they also read the register. That way
651  // we get a single contiguous lifetime.
652  //
653  // Definitions in MRI.def_begin() are unordered, search for the first.
655  std::find_if(MRI.def_begin(VReg), MRI.def_end(),
656  [VReg, &TRI](const MachineOperand &MO) {
657  return !MO.getParent()->readsRegister(VReg, &TRI);
658  });
659  assert(FirstDef != MRI.def_end() &&
660  "Must have one definition that does not redefine vreg");
661  MachineInstr &DefMI = *FirstDef->getParent();
662 
663  // The register scavenger will report a free register inserting an emergency
664  // spill/reload if necessary.
665  int SPAdj = 0;
666  const TargetRegisterClass &RC = *MRI.getRegClass(VReg);
667  Register SReg = RS.scavengeRegisterBackwards(RC, DefMI.getIterator(),
668  ReserveAfter, SPAdj);
669  MRI.replaceRegWith(VReg, SReg);
670  ++NumScavengedRegs;
671  return SReg;
672 }
673 
674 /// Allocate (scavenge) vregs inside a single basic block.
675 /// Returns true if the target spill callback created new vregs and a 2nd pass
676 /// is necessary.
678  RegScavenger &RS,
679  MachineBasicBlock &MBB) {
681  RS.enterBasicBlockEnd(MBB);
682 
683  unsigned InitialNumVirtRegs = MRI.getNumVirtRegs();
684  bool NextInstructionReadsVReg = false;
685  for (MachineBasicBlock::iterator I = MBB.end(); I != MBB.begin(); ) {
686  --I;
687  // Move RegScavenger to the position between *I and *std::next(I).
688  RS.backward(I);
689 
690  // Look for unassigned vregs in the uses of *std::next(I).
691  if (NextInstructionReadsVReg) {
692  MachineBasicBlock::iterator N = std::next(I);
693  const MachineInstr &NMI = *N;
694  for (const MachineOperand &MO : NMI.operands()) {
695  if (!MO.isReg())
696  continue;
697  Register Reg = MO.getReg();
698  // We only care about virtual registers and ignore virtual registers
699  // created by the target callbacks in the process (those will be handled
700  // in a scavenging round).
701  if (!Register::isVirtualRegister(Reg) ||
702  Register::virtReg2Index(Reg) >= InitialNumVirtRegs)
703  continue;
704  if (!MO.readsReg())
705  continue;
706 
707  Register SReg = scavengeVReg(MRI, RS, Reg, true);
708  N->addRegisterKilled(SReg, &TRI, false);
709  RS.setRegUsed(SReg);
710  }
711  }
712 
713  // Look for unassigned vregs in the defs of *I.
714  NextInstructionReadsVReg = false;
715  const MachineInstr &MI = *I;
716  for (const MachineOperand &MO : MI.operands()) {
717  if (!MO.isReg())
718  continue;
719  Register Reg = MO.getReg();
720  // Only vregs, no newly created vregs (see above).
721  if (!Register::isVirtualRegister(Reg) ||
722  Register::virtReg2Index(Reg) >= InitialNumVirtRegs)
723  continue;
724  // We have to look at all operands anyway so we can precalculate here
725  // whether there is a reading operand. This allows use to skip the use
726  // step in the next iteration if there was none.
727  assert(!MO.isInternalRead() && "Cannot assign inside bundles");
728  assert((!MO.isUndef() || MO.isDef()) && "Cannot handle undef uses");
729  if (MO.readsReg()) {
730  NextInstructionReadsVReg = true;
731  }
732  if (MO.isDef()) {
733  Register SReg = scavengeVReg(MRI, RS, Reg, false);
734  I->addRegisterDead(SReg, &TRI, false);
735  }
736  }
737  }
738 #ifndef NDEBUG
739  for (const MachineOperand &MO : MBB.front().operands()) {
740  if (!MO.isReg() || !Register::isVirtualRegister(MO.getReg()))
741  continue;
742  assert(!MO.isInternalRead() && "Cannot assign inside bundles");
743  assert((!MO.isUndef() || MO.isDef()) && "Cannot handle undef uses");
744  assert(!MO.readsReg() && "Vreg use in first instruction not allowed");
745  }
746 #endif
747 
748  return MRI.getNumVirtRegs() != InitialNumVirtRegs;
749 }
750 
752  // FIXME: Iterating over the instruction stream is unnecessary. We can simply
753  // iterate over the vreg use list, which at this point only contains machine
754  // operands for which eliminateFrameIndex need a new scratch reg.
756  // Shortcut.
757  if (MRI.getNumVirtRegs() == 0) {
759  return;
760  }
761 
762  // Run through the instructions and find any virtual registers.
763  for (MachineBasicBlock &MBB : MF) {
764  if (MBB.empty())
765  continue;
766 
767  bool Again = scavengeFrameVirtualRegsInBlock(MRI, RS, MBB);
768  if (Again) {
769  LLVM_DEBUG(dbgs() << "Warning: Required two scavenging passes for block "
770  << MBB.getName() << '\n');
771  Again = scavengeFrameVirtualRegsInBlock(MRI, RS, MBB);
772  // The target required a 2nd run (because it created new vregs while
773  // spilling). Refuse to do another pass to keep compiletime in check.
774  if (Again)
775  report_fatal_error("Incomplete scavenging after 2nd pass");
776  }
777  }
778 
779  MRI.clearVirtRegs();
780  MF.getProperties().set(MachineFunctionProperties::Property::NoVRegs);
781 }
782 
783 namespace {
784 
785 /// This class runs register scavenging independ of the PrologEpilogInserter.
786 /// This is used in for testing.
787 class ScavengerTest : public MachineFunctionPass {
788 public:
789  static char ID;
790 
791  ScavengerTest() : MachineFunctionPass(ID) {}
792 
793  bool runOnMachineFunction(MachineFunction &MF) override {
794  const TargetSubtargetInfo &STI = MF.getSubtarget();
795  const TargetFrameLowering &TFL = *STI.getFrameLowering();
796 
797  RegScavenger RS;
798  // Let's hope that calling those outside of PrologEpilogueInserter works
799  // well enough to initialize the scavenger with some emergency spillslots
800  // for the target.
801  BitVector SavedRegs;
802  TFL.determineCalleeSaves(MF, SavedRegs, &RS);
804 
805  // Let's scavenge the current function
806  scavengeFrameVirtualRegs(MF, RS);
807  return true;
808  }
809 };
810 
811 } // end anonymous namespace
812 
813 char ScavengerTest::ID;
814 
815 INITIALIZE_PASS(ScavengerTest, "scavenger-test",
816  "Scavenge virtual registers inside basic blocks", false, false)
void resize(unsigned N, bool t=false)
resize - Grow or shrink the bitvector.
Definition: BitVector.h:371
BitVector & set()
Definition: BitVector.h:397
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
bool isReserved(Register PhysReg) const
isReserved - Returns true when PhysReg is a reserved register.
static unsigned virtReg2Index(unsigned Reg)
Convert a virtual register number to a 0-based index.
Definition: Register.h:76
const MachineFunction * getMF() const
Return the function that contains the basic block that this instruction belongs to.
LLVM_ATTRIBUTE_NORETURN void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:139
This class represents lattice values for constants.
Definition: AllocatorList.h:23
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
void storeRegToStackSlot(MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI, unsigned SrcReg, bool isKill, int FrameIndex, const TargetRegisterClass *RC, const TargetRegisterInfo *TRI) const override
Store the specified register of the given register class to the specified stack frame index...
ArrayRef< MCPhysReg > getRawAllocationOrder(const MachineFunction &MF) const
Returns the preferred order for allocating registers from this register class in MF.
const MachineFunctionProperties & getProperties() const
Get the function properties.
void push_back(const T &Elt)
Definition: SmallVector.h:211
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:63
iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
iterator_range< reg_nodbg_iterator > reg_nodbg_operands(unsigned Reg) const
unsigned Reg
bool test(unsigned Idx) const
Definition: BitVector.h:501
static void addRegUnits(const SIRegisterInfo &TRI, BitVector &BV, unsigned Reg)
STATISTIC(NumFunctions, "Total number of functions")
unsigned const TargetRegisterInfo * TRI
Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
iterator_range< mop_iterator > operands()
Definition: MachineInstr.h:476
void clearVirtRegs()
clearVirtRegs - Remove all virtual registers (after physreg assignment).
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
virtual void determineCalleeSaves(MachineFunction &MF, BitVector &SavedRegs, RegScavenger *RS=nullptr) const
This method determines which of the registers reported by TargetRegisterInfo::getCalleeSavedRegs() sh...
virtual void processFunctionBeforeFrameFinalized(MachineFunction &MF, RegScavenger *RS=nullptr) const
processFunctionBeforeFrameFinalized - This method is called immediately before the specified function...
void loadRegFromStackSlot(MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI, unsigned DestReg, int FrameIndex, const TargetRegisterClass *RC, const TargetRegisterInfo *TRI) const override
Load the specified register of the given register class from the specified stack frame index...
void clear()
clear - Removes all bits from the bitvector. Does not change capacity.
Definition: BitVector.h:366
MCSuperRegIterator enumerates all super-registers of Reg.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
const HexagonInstrInfo * TII
void addLiveOuts(const MachineBasicBlock &MBB)
Adds registers living out of block MBB.
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:413
int find_first() const
find_first - Returns the index of the first set bit, -1 if none of the bits are set.
Definition: BitVector.h:331
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:41
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted...
void backward()
Update internal register state and move MBB iterator backwards.
def_iterator def_begin(unsigned RegNo) const
void scavengeFrameVirtualRegs(MachineFunction &MF, RegScavenger &RS)
Replaces all frame index virtual registers with physical registers.
void setRegUsed(Register Reg, LaneBitmask LaneMask=LaneBitmask::getAll())
Tell the scavenger a register is used.
void forward()
Move the internal MBB iterator and update register states.
void addLiveIns(const MachineBasicBlock &MBB)
Adds registers living into block MBB.
bool available(MCPhysReg Reg) const
Returns true if no part of physical register Reg is live.
Definition: LiveRegUnits.h:117
MCRegUnitRootIterator enumerates the root registers of a register unit.
BitVector getRegsAvailable(const TargetRegisterClass *RC)
Return all available registers in the register class in Mask.
int getObjectIndexBegin() const
Return the minimum frame object index.
int getObjectIndexEnd() const
Return one past the maximum frame object index.
virtual const TargetInstrInfo * getInstrInfo() const
int64_t getObjectSize(int ObjectIdx) const
Return the size of the specified object.
uint16_t MCPhysReg
An unsigned integer type large enough to represent all physical registers, but not necessarily virtua...
Definition: MCRegister.h:19
void addRegMasked(MCPhysReg Reg, LaneBitmask Mask)
Adds register units covered by physical register Reg that are part of the lanemask Mask...
Definition: LiveRegUnits.h:94
void removeReg(MCPhysReg Reg)
Removes all register units covered by physical register Reg.
Definition: LiveRegUnits.h:103
unsigned getObjectAlignment(int ObjectIdx) const
Return the alignment of the specified stack object.
static Register scavengeVReg(MachineRegisterInfo &MRI, RegScavenger &RS, Register VReg, bool ReserveAfter)
Allocate a register for the virtual register VReg.
#define P(N)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
MachineInstrBundleIterator< MachineInstr > iterator
void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords=~0u)
clearBitsNotInMask - Clear a bit in this vector for every &#39;0&#39; bit in Mask.
Definition: BitVector.h:793
This file declares the machine register scavenger class.
const TargetRegisterInfo * getTargetRegisterInfo() const
void init(const TargetRegisterInfo &TRI)
Initialize and clear the set.
Definition: LiveRegUnits.h:74
unsigned const MachineRegisterInfo * MRI
StringRef getName() const
Return the name of the corresponding LLVM basic block, or an empty string.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
MachineFrameInfo & getFrameInfo()
getFrameInfo - Return the frame info object for the current function.
MachineInstrBuilder & UseMI
bool isRegUsed(Register Reg, bool includeReserved=true) const
Return if a specific register is currently used.
bool any() const
any - Returns true if any bit is set.
Definition: BitVector.h:180
void unprocess()
Invert the behavior of forward() on the current instruction (undo the changes to the available regist...
MCRegAliasIterator enumerates all registers aliasing Reg.
BitVector & reset()
Definition: BitVector.h:438
void stepBackward(const MachineInstr &MI)
Updates liveness when stepping backwards over the instruction MI.
A set of register units.
auto find_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range))
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1193
unsigned getNumVirtRegs() const
getNumVirtRegs - Return the number of virtual registers created.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
MCSubRegIterator enumerates all sub-registers of Reg.
size_t size() const
Definition: SmallVector.h:52
bool isDebugInstr() const
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:33
static bool scavengeFrameVirtualRegsInBlock(MachineRegisterInfo &MRI, RegScavenger &RS, MachineBasicBlock &MBB)
Allocate (scavenge) vregs inside a single basic block.
bool readsRegister(Register Reg, const TargetRegisterInfo *TRI=nullptr) const
Return true if the MachineInstr reads the specified register.
BlockVerifier::State From
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:390
MachineOperand class - Representation of each machine instruction operand.
MachineInstrBuilder MachineInstrBuilder & DefMI
Information about stack frame layout on the target.
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
void enterBasicBlockEnd(MachineBasicBlock &MBB)
Start tracking liveness from the end of basic block MBB.
void accumulate(const MachineInstr &MI)
Adds all register units used, defined or clobbered in MI.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
void replaceRegWith(unsigned FromReg, unsigned ToReg)
replaceRegWith - Replace all instances of FromReg with ToReg in the machine function.
Register scavengeRegisterBackwards(const TargetRegisterClass &RC, MachineBasicBlock::iterator To, bool RestoreAfter, int SPAdj, bool AllowSpill=true)
Make a register of the specific register class available from the current position backwards to the p...
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
MachineFunctionProperties & set(Property P)
bool none() const
none - Returns true if none of the bits are set.
Definition: BitVector.h:201
TargetSubtargetInfo - Generic base class for all target subtargets.
static unsigned getFrameIndexOperandNum(MachineInstr &MI)
Representation of each machine instruction.
Definition: MachineInstr.h:63
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
void enterBasicBlock(MachineBasicBlock &MBB)
Start tracking liveness from the begin of basic block MBB.
Register scavengeRegister(const TargetRegisterClass *RC, MachineBasicBlock::iterator I, int SPAdj, bool AllowSpill=true)
Make a register of the specific register class available and do the appropriate bookkeeping.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
bool verify(Pass *p=nullptr, const char *Banner=nullptr, bool AbortOnError=true) const
Run the current MachineFunction through the machine code verifier, useful for debugger use...
Register FindUnusedReg(const TargetRegisterClass *RC) const
Find an unused register of the specified register class.
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
virtual const TargetFrameLowering * getFrameLowering() const
bool isFI() const
isFI - Tests if this is a MO_FrameIndex operand.
A set of register units used to track register liveness.
Definition: LiveRegUnits.h:30
static cl::opt< unsigned > InstrLimit("dfa-instr-limit", cl::Hidden, cl::init(0), cl::desc("If present, stops packetizing after N instructions"))
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static def_iterator def_end()
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:69
std::underlying_type< E >::type Mask()
Get a bitmask with 1s in all places up to the high-order bit of E&#39;s largest value.
Definition: BitmaskEnum.h:80
IRTranslator LLVM IR MI
bool isValid() const
Check if the iterator is at the end of the list.
static std::pair< MCPhysReg, MachineBasicBlock::iterator > findSurvivorBackwards(const MachineRegisterInfo &MRI, MachineBasicBlock::iterator From, MachineBasicBlock::iterator To, const LiveRegUnits &LiveOut, ArrayRef< MCPhysReg > AllocationOrder, bool RestoreAfter)
Given the bitvector Available of free register units at position From.
#define LLVM_DEBUG(X)
Definition: Debug.h:122
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:415
reg_begin/reg_end - Provide iteration support to walk over all definitions and uses of a register wit...
Wrapper class representing virtual and physical registers.
Definition: Register.h:19