LLVM  6.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();
60  TRI = MF.getSubtarget().getRegisterInfo();
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.isDebugValue() && "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.isDebugValue()) {
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.isDebugValue())
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 D0<undef>, 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  DEBUG(dbgs() << "Scavenger found unused reg: " << TRI->getName(Reg) <<
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->isDebugValue()) {
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;
389  const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
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  DEBUG(dbgs() << "Scavenged register: " << TRI->getName(SReg) << "\n");
565  return SReg;
566  }
567 
568  ScavengedInfo &Scavenged = spill(SReg, *RC, SPAdj, I, UseMI);
569  Scavenged.Restore = &*std::prev(UseMI);
570 
571  DEBUG(dbgs() << "Scavenged register (with spill): " << TRI->getName(SReg) <<
572  "\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  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  DEBUG(dbgs() << "Scavenged register with spill: " << PrintReg(Reg, TRI)
602  << " until " << *SpillBefore);
603  } else {
604  DEBUG(dbgs() << "Scavenged free register: " << PrintReg(Reg, TRI) << '\n');
605  }
606  return Reg;
607 }
608 
609 /// Allocate a register for the virtual register \p VReg. The last use of
610 /// \p VReg is around the current position of the register scavenger \p RS.
611 /// \p ReserveAfter controls whether the scavenged register needs to be reserved
612 /// after the current instruction, otherwise it will only be reserved before the
613 /// current instruction.
615  unsigned VReg, bool ReserveAfter) {
616  const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
617 #ifndef NDEBUG
618  // Verify that all definitions and uses are in the same basic block.
619  const MachineBasicBlock *CommonMBB = nullptr;
620  // Real definition for the reg, re-definitions are not considered.
621  const MachineInstr *RealDef = nullptr;
622  for (MachineOperand &MO : MRI.reg_nodbg_operands(VReg)) {
623  MachineBasicBlock *MBB = MO.getParent()->getParent();
624  if (CommonMBB == nullptr)
625  CommonMBB = MBB;
626  assert(MBB == CommonMBB && "All defs+uses must be in the same basic block");
627  if (MO.isDef()) {
628  const MachineInstr &MI = *MO.getParent();
629  if (!MI.readsRegister(VReg, &TRI)) {
630  assert((!RealDef || RealDef == &MI) &&
631  "Can have at most one definition which is not a redefinition");
632  RealDef = &MI;
633  }
634  }
635  }
636  assert(RealDef != nullptr && "Must have at least 1 Def");
637 #endif
638 
639  // We should only have one definition of the register. However to accommodate
640  // the requirements of two address code we also allow definitions in
641  // subsequent instructions provided they also read the register. That way
642  // we get a single contiguous lifetime.
643  //
644  // Definitions in MRI.def_begin() are unordered, search for the first.
646  std::find_if(MRI.def_begin(VReg), MRI.def_end(),
647  [VReg, &TRI](const MachineOperand &MO) {
648  return !MO.getParent()->readsRegister(VReg, &TRI);
649  });
650  assert(FirstDef != MRI.def_end() &&
651  "Must have one definition that does not redefine vreg");
652  MachineInstr &DefMI = *FirstDef->getParent();
653 
654  // The register scavenger will report a free register inserting an emergency
655  // spill/reload if necessary.
656  int SPAdj = 0;
657  const TargetRegisterClass &RC = *MRI.getRegClass(VReg);
658  unsigned SReg = RS.scavengeRegisterBackwards(RC, DefMI.getIterator(),
659  ReserveAfter, SPAdj);
660  MRI.replaceRegWith(VReg, SReg);
661  ++NumScavengedRegs;
662  return SReg;
663 }
664 
665 /// Allocate (scavenge) vregs inside a single basic block.
666 /// Returns true if the target spill callback created new vregs and a 2nd pass
667 /// is necessary.
669  RegScavenger &RS,
670  MachineBasicBlock &MBB) {
671  const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
672  RS.enterBasicBlockEnd(MBB);
673 
674  unsigned InitialNumVirtRegs = MRI.getNumVirtRegs();
675  bool NextInstructionReadsVReg = false;
676  for (MachineBasicBlock::iterator I = MBB.end(); I != MBB.begin(); ) {
677  --I;
678  // Move RegScavenger to the position between *I and *std::next(I).
679  RS.backward(I);
680 
681  // Look for unassigned vregs in the uses of *std::next(I).
682  if (NextInstructionReadsVReg) {
683  MachineBasicBlock::iterator N = std::next(I);
684  const MachineInstr &NMI = *N;
685  for (const MachineOperand &MO : NMI.operands()) {
686  if (!MO.isReg())
687  continue;
688  unsigned Reg = MO.getReg();
689  // We only care about virtual registers and ignore virtual registers
690  // created by the target callbacks in the process (those will be handled
691  // in a scavenging round).
693  TargetRegisterInfo::virtReg2Index(Reg) >= InitialNumVirtRegs)
694  continue;
695  if (!MO.readsReg())
696  continue;
697 
698  unsigned SReg = scavengeVReg(MRI, RS, Reg, true);
699  N->addRegisterKilled(SReg, &TRI, false);
700  RS.setRegUsed(SReg);
701  }
702  }
703 
704  // Look for unassigned vregs in the defs of *I.
705  NextInstructionReadsVReg = false;
706  const MachineInstr &MI = *I;
707  for (const MachineOperand &MO : MI.operands()) {
708  if (!MO.isReg())
709  continue;
710  unsigned Reg = MO.getReg();
711  // Only vregs, no newly created vregs (see above).
713  TargetRegisterInfo::virtReg2Index(Reg) >= InitialNumVirtRegs)
714  continue;
715  // We have to look at all operands anyway so we can precalculate here
716  // whether there is a reading operand. This allows use to skip the use
717  // step in the next iteration if there was none.
718  assert(!MO.isInternalRead() && "Cannot assign inside bundles");
719  assert((!MO.isUndef() || MO.isDef()) && "Cannot handle undef uses");
720  if (MO.readsReg()) {
721  NextInstructionReadsVReg = true;
722  }
723  if (MO.isDef()) {
724  unsigned SReg = scavengeVReg(MRI, RS, Reg, false);
725  I->addRegisterDead(SReg, &TRI, false);
726  }
727  }
728  }
729 #ifndef NDEBUG
730  for (const MachineOperand &MO : MBB.front().operands()) {
731  if (!MO.isReg() || !TargetRegisterInfo::isVirtualRegister(MO.getReg()))
732  continue;
733  assert(!MO.isInternalRead() && "Cannot assign inside bundles");
734  assert((!MO.isUndef() || MO.isDef()) && "Cannot handle undef uses");
735  assert(!MO.readsReg() && "Vreg use in first instruction not allowed");
736  }
737 #endif
738 
739  return MRI.getNumVirtRegs() != InitialNumVirtRegs;
740 }
741 
743  // FIXME: Iterating over the instruction stream is unnecessary. We can simply
744  // iterate over the vreg use list, which at this point only contains machine
745  // operands for which eliminateFrameIndex need a new scratch reg.
747  // Shortcut.
748  if (MRI.getNumVirtRegs() == 0) {
750  return;
751  }
752 
753  // Run through the instructions and find any virtual registers.
754  for (MachineBasicBlock &MBB : MF) {
755  if (MBB.empty())
756  continue;
757 
758  bool Again = scavengeFrameVirtualRegsInBlock(MRI, RS, MBB);
759  if (Again) {
760  DEBUG(dbgs() << "Warning: Required two scavenging passes for block "
761  << MBB.getName() << '\n');
762  Again = scavengeFrameVirtualRegsInBlock(MRI, RS, MBB);
763  // The target required a 2nd run (because it created new vregs while
764  // spilling). Refuse to do another pass to keep compiletime in check.
765  if (Again)
766  report_fatal_error("Incomplete scavenging after 2nd pass");
767  }
768  }
769 
770  MRI.clearVirtRegs();
771  MF.getProperties().set(MachineFunctionProperties::Property::NoVRegs);
772 }
773 
774 namespace {
775 
776 /// This class runs register scavenging independ of the PrologEpilogInserter.
777 /// This is used in for testing.
778 class ScavengerTest : public MachineFunctionPass {
779 public:
780  static char ID;
781 
782  ScavengerTest() : MachineFunctionPass(ID) {}
783 
784  bool runOnMachineFunction(MachineFunction &MF) override {
785  const TargetSubtargetInfo &STI = MF.getSubtarget();
786  const TargetFrameLowering &TFL = *STI.getFrameLowering();
787 
788  RegScavenger RS;
789  // Let's hope that calling those outside of PrologEpilogueInserter works
790  // well enough to initialize the scavenger with some emergency spillslots
791  // for the target.
792  BitVector SavedRegs;
793  TFL.determineCalleeSaves(MF, SavedRegs, &RS);
795 
796  // Let's scavenge the current function
797  scavengeFrameVirtualRegs(MF, RS);
798  return true;
799  }
800 };
801 
802 } // end anonymous namespace
803 
804 char ScavengerTest::ID;
805 
806 INITIALIZE_PASS(ScavengerTest, "scavenger-test",
807  "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
BitVector getAllocatableSet(const MachineFunction &MF, const TargetRegisterClass *RC=nullptr) const
Returns a bitset indexed by register number indicating if a register is allocatable or not...
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
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 FindUnusedReg(const TargetRegisterClass *RegClass) const
Find an unused register of the specified register class.
iterator_range< mop_iterator > operands()
Definition: MachineInstr.h:332
unsigned getNumRegUnits() const
Return the number of (native) register units in the target.
unsigned getSpillSize(const TargetRegisterClass &RC) const
Return the size in bytes of the stack slot allocated to hold a spilled copy of a register from class ...
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...
const char * getRegClassName(const TargetRegisterClass *Class) const
Returns the name of the register class.
unsigned getSpillAlignment(const TargetRegisterClass &RC) const
Return the minimum required alignment in bytes for a spill slot for a register of this class...
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:293
void removeReg(unsigned Reg)
Removes all register units covered by physical register Reg.
Definition: LiveRegUnits.h:73
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
Reg
All possible values of the reg field in the ModR/M byte.
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 void eliminateFrameIndex(MachineBasicBlock::iterator MI, int SPAdj, unsigned FIOperandNum, RegScavenger *RS=nullptr) const =0
This method must be overriden to eliminate abstract frame indices from instructions which may use the...
virtual const TargetInstrInfo * getInstrInfo() const
Printable PrintReg(unsigned Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubRegIdx=0)
Prints virtual and physical registers with or without a TRI instance.
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...
const char * getName(unsigned RegNo) const
Return the human-readable symbolic target-specific name for the specified physical register...
unsigned getObjectAlignment(int ObjectIdx) const
Return the alignment of the specified stack object.
#define P(N)
unsigned getNumRegs() const
Return the number of registers this target has (useful for sizing arrays holding per register informa...
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:406
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:44
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: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:841
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.
#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.
bool isDebugValue() const
Definition: MachineInstr.h:816
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:132
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:927
void addRegMasked(unsigned Reg, LaneBitmask Mask)
Adds register units covered by physical register Reg that are part of the lanemask Mask...
Definition: LiveRegUnits.h:64
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:59
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:87
#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()
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
#define DEBUG(X)
Definition: Debug.h:118
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.
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:295
reg_begin/reg_end - Provide iteration support to walk over all definitions and uses of a register wit...
virtual bool saveScavengerRegister(MachineBasicBlock &MBB, MachineBasicBlock::iterator I, MachineBasicBlock::iterator &UseMI, const TargetRegisterClass *RC, unsigned Reg) const
Spill the register so it can be used by the register scavenger.
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.