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