LLVM  7.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  setUsed(KillRegUnits);
166  setUnused(DefRegUnits);
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  LLVM_DEBUG(dbgs() << "Reload before: " << *ReloadBefore << '\n');
598  ScavengedInfo &Scavenged = spill(Reg, RC, SPAdj, SpillBefore, ReloadBefore);
599  Scavenged.Restore = &*std::prev(SpillBefore);
600  LiveUnits.removeReg(Reg);
601  LLVM_DEBUG(dbgs() << "Scavenged register with spill: " << printReg(Reg, TRI)
602  << " until " << *SpillBefore);
603  } else {
604  LLVM_DEBUG(dbgs() << "Scavenged free register: " << printReg(Reg, TRI)
605  << '\n');
606  }
607  return Reg;
608 }
609 
610 /// Allocate a register for the virtual register \p VReg. The last use of
611 /// \p VReg is around the current position of the register scavenger \p RS.
612 /// \p ReserveAfter controls whether the scavenged register needs to be reserved
613 /// after the current instruction, otherwise it will only be reserved before the
614 /// current instruction.
616  unsigned VReg, bool ReserveAfter) {
618 #ifndef NDEBUG
619  // Verify that all definitions and uses are in the same basic block.
620  const MachineBasicBlock *CommonMBB = nullptr;
621  // Real definition for the reg, re-definitions are not considered.
622  const MachineInstr *RealDef = nullptr;
623  for (MachineOperand &MO : MRI.reg_nodbg_operands(VReg)) {
624  MachineBasicBlock *MBB = MO.getParent()->getParent();
625  if (CommonMBB == nullptr)
626  CommonMBB = MBB;
627  assert(MBB == CommonMBB && "All defs+uses must be in the same basic block");
628  if (MO.isDef()) {
629  const MachineInstr &MI = *MO.getParent();
630  if (!MI.readsRegister(VReg, &TRI)) {
631  assert((!RealDef || RealDef == &MI) &&
632  "Can have at most one definition which is not a redefinition");
633  RealDef = &MI;
634  }
635  }
636  }
637  assert(RealDef != nullptr && "Must have at least 1 Def");
638 #endif
639 
640  // We should only have one definition of the register. However to accommodate
641  // the requirements of two address code we also allow definitions in
642  // subsequent instructions provided they also read the register. That way
643  // we get a single contiguous lifetime.
644  //
645  // Definitions in MRI.def_begin() are unordered, search for the first.
647  std::find_if(MRI.def_begin(VReg), MRI.def_end(),
648  [VReg, &TRI](const MachineOperand &MO) {
649  return !MO.getParent()->readsRegister(VReg, &TRI);
650  });
651  assert(FirstDef != MRI.def_end() &&
652  "Must have one definition that does not redefine vreg");
653  MachineInstr &DefMI = *FirstDef->getParent();
654 
655  // The register scavenger will report a free register inserting an emergency
656  // spill/reload if necessary.
657  int SPAdj = 0;
658  const TargetRegisterClass &RC = *MRI.getRegClass(VReg);
659  unsigned SReg = RS.scavengeRegisterBackwards(RC, DefMI.getIterator(),
660  ReserveAfter, SPAdj);
661  MRI.replaceRegWith(VReg, SReg);
662  ++NumScavengedRegs;
663  return SReg;
664 }
665 
666 /// Allocate (scavenge) vregs inside a single basic block.
667 /// Returns true if the target spill callback created new vregs and a 2nd pass
668 /// is necessary.
670  RegScavenger &RS,
671  MachineBasicBlock &MBB) {
673  RS.enterBasicBlockEnd(MBB);
674 
675  unsigned InitialNumVirtRegs = MRI.getNumVirtRegs();
676  bool NextInstructionReadsVReg = false;
677  for (MachineBasicBlock::iterator I = MBB.end(); I != MBB.begin(); ) {
678  --I;
679  // Move RegScavenger to the position between *I and *std::next(I).
680  RS.backward(I);
681 
682  // Look for unassigned vregs in the uses of *std::next(I).
683  if (NextInstructionReadsVReg) {
684  MachineBasicBlock::iterator N = std::next(I);
685  const MachineInstr &NMI = *N;
686  for (const MachineOperand &MO : NMI.operands()) {
687  if (!MO.isReg())
688  continue;
689  unsigned Reg = MO.getReg();
690  // We only care about virtual registers and ignore virtual registers
691  // created by the target callbacks in the process (those will be handled
692  // in a scavenging round).
694  TargetRegisterInfo::virtReg2Index(Reg) >= InitialNumVirtRegs)
695  continue;
696  if (!MO.readsReg())
697  continue;
698 
699  unsigned SReg = scavengeVReg(MRI, RS, Reg, true);
700  N->addRegisterKilled(SReg, &TRI, false);
701  RS.setRegUsed(SReg);
702  }
703  }
704 
705  // Look for unassigned vregs in the defs of *I.
706  NextInstructionReadsVReg = false;
707  const MachineInstr &MI = *I;
708  for (const MachineOperand &MO : MI.operands()) {
709  if (!MO.isReg())
710  continue;
711  unsigned Reg = MO.getReg();
712  // Only vregs, no newly created vregs (see above).
714  TargetRegisterInfo::virtReg2Index(Reg) >= InitialNumVirtRegs)
715  continue;
716  // We have to look at all operands anyway so we can precalculate here
717  // whether there is a reading operand. This allows use to skip the use
718  // step in the next iteration if there was none.
719  assert(!MO.isInternalRead() && "Cannot assign inside bundles");
720  assert((!MO.isUndef() || MO.isDef()) && "Cannot handle undef uses");
721  if (MO.readsReg()) {
722  NextInstructionReadsVReg = true;
723  }
724  if (MO.isDef()) {
725  unsigned SReg = scavengeVReg(MRI, RS, Reg, false);
726  I->addRegisterDead(SReg, &TRI, false);
727  }
728  }
729  }
730 #ifndef NDEBUG
731  for (const MachineOperand &MO : MBB.front().operands()) {
732  if (!MO.isReg() || !TargetRegisterInfo::isVirtualRegister(MO.getReg()))
733  continue;
734  assert(!MO.isInternalRead() && "Cannot assign inside bundles");
735  assert((!MO.isUndef() || MO.isDef()) && "Cannot handle undef uses");
736  assert(!MO.readsReg() && "Vreg use in first instruction not allowed");
737  }
738 #endif
739 
740  return MRI.getNumVirtRegs() != InitialNumVirtRegs;
741 }
742 
744  // FIXME: Iterating over the instruction stream is unnecessary. We can simply
745  // iterate over the vreg use list, which at this point only contains machine
746  // operands for which eliminateFrameIndex need a new scratch reg.
748  // Shortcut.
749  if (MRI.getNumVirtRegs() == 0) {
751  return;
752  }
753 
754  // Run through the instructions and find any virtual registers.
755  for (MachineBasicBlock &MBB : MF) {
756  if (MBB.empty())
757  continue;
758 
759  bool Again = scavengeFrameVirtualRegsInBlock(MRI, RS, MBB);
760  if (Again) {
761  LLVM_DEBUG(dbgs() << "Warning: Required two scavenging passes for block "
762  << MBB.getName() << '\n');
763  Again = scavengeFrameVirtualRegsInBlock(MRI, RS, MBB);
764  // The target required a 2nd run (because it created new vregs while
765  // spilling). Refuse to do another pass to keep compiletime in check.
766  if (Again)
767  report_fatal_error("Incomplete scavenging after 2nd pass");
768  }
769  }
770 
771  MRI.clearVirtRegs();
772  MF.getProperties().set(MachineFunctionProperties::Property::NoVRegs);
773 }
774 
775 namespace {
776 
777 /// This class runs register scavenging independ of the PrologEpilogInserter.
778 /// This is used in for testing.
779 class ScavengerTest : public MachineFunctionPass {
780 public:
781  static char ID;
782 
783  ScavengerTest() : MachineFunctionPass(ID) {}
784 
785  bool runOnMachineFunction(MachineFunction &MF) override {
786  const TargetSubtargetInfo &STI = MF.getSubtarget();
787  const TargetFrameLowering &TFL = *STI.getFrameLowering();
788 
789  RegScavenger RS;
790  // Let's hope that calling those outside of PrologEpilogueInserter works
791  // well enough to initialize the scavenger with some emergency spillslots
792  // for the target.
793  BitVector SavedRegs;
794  TFL.determineCalleeSaves(MF, SavedRegs, &RS);
796 
797  // Let's scavenge the current function
798  scavengeFrameVirtualRegs(MF, RS);
799  return true;
800  }
801 };
802 
803 } // end anonymous namespace
804 
805 char ScavengerTest::ID;
806 
807 INITIALIZE_PASS(ScavengerTest, "scavenger-test",
808  "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:212
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:115
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:136
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
unsigned FindUnusedReg(const TargetRegisterClass *RegClass) const
Find an unused register of the specified register class.
iterator_range< mop_iterator > operands()
Definition: MachineInstr.h:353
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
Access to explicit operands of the instruction.
Definition: MachineInstr.h:314
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.
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:777
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.
Printable printReg(unsigned Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubRegIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
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:116
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:936
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.
bool isDebugInstr() const
Definition: MachineInstr.h:845
#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.
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.
Definition: MachineInstr.h:959
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:60
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:120
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.
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:119
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:316
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.
unsigned scavengeRegister(const TargetRegisterClass *RegClass, MachineBasicBlock::iterator I, int SPAdj)
Make a register of the specific register class available and do the appropriate bookkeeping.