LLVM  6.0.0svn
RegAllocFast.cpp
Go to the documentation of this file.
1 //===- RegAllocFast.cpp - A fast register allocator for debug code --------===//
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 This register allocator allocates registers to a basic block at a
11 /// time, attempting to keep values in registers and reusing registers as
12 /// appropriate.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #include "llvm/ADT/ArrayRef.h"
17 #include "llvm/ADT/DenseMap.h"
18 #include "llvm/ADT/IndexedMap.h"
19 #include "llvm/ADT/SmallSet.h"
20 #include "llvm/ADT/SmallVector.h"
21 #include "llvm/ADT/SparseSet.h"
22 #include "llvm/ADT/Statistic.h"
38 #include "llvm/IR/DebugLoc.h"
39 #include "llvm/IR/Metadata.h"
40 #include "llvm/MC/MCInstrDesc.h"
41 #include "llvm/MC/MCRegisterInfo.h"
42 #include "llvm/Pass.h"
43 #include "llvm/Support/Casting.h"
44 #include "llvm/Support/Compiler.h"
45 #include "llvm/Support/Debug.h"
48 #include <cassert>
49 #include <tuple>
50 #include <vector>
51 
52 using namespace llvm;
53 
54 #define DEBUG_TYPE "regalloc"
55 
56 STATISTIC(NumStores, "Number of stores added");
57 STATISTIC(NumLoads , "Number of loads added");
58 STATISTIC(NumCopies, "Number of copies coalesced");
59 
60 static RegisterRegAlloc
61  fastRegAlloc("fast", "fast register allocator", createFastRegisterAllocator);
62 
63 namespace {
64 
65  class RegAllocFast : public MachineFunctionPass {
66  public:
67  static char ID;
68 
69  RegAllocFast() : MachineFunctionPass(ID), StackSlotForVirtReg(-1) {}
70 
71  private:
72  MachineFrameInfo *MFI;
74  const TargetRegisterInfo *TRI;
75  const TargetInstrInfo *TII;
76  RegisterClassInfo RegClassInfo;
77 
78  /// Basic block currently being allocated.
79  MachineBasicBlock *MBB;
80 
81  /// Maps virtual regs to the frame index where these values are spilled.
82  IndexedMap<int, VirtReg2IndexFunctor> StackSlotForVirtReg;
83 
84  /// Everything we know about a live virtual register.
85  struct LiveReg {
86  MachineInstr *LastUse = nullptr; ///< Last instr to use reg.
87  unsigned VirtReg; ///< Virtual register number.
88  MCPhysReg PhysReg = 0; ///< Currently held here.
89  unsigned short LastOpNum = 0; ///< OpNum on LastUse.
90  bool Dirty = false; ///< Register needs spill.
91 
92  explicit LiveReg(unsigned v) : VirtReg(v) {}
93 
94  unsigned getSparseSetIndex() const {
95  return TargetRegisterInfo::virtReg2Index(VirtReg);
96  }
97  };
98 
99  using LiveRegMap = SparseSet<LiveReg>;
100 
101  /// This map contains entries for each virtual register that is currently
102  /// available in a physical register.
103  LiveRegMap LiveVirtRegs;
104 
106 
107  /// Track the state of a physical register.
108  enum RegState {
109  /// A disabled register is not available for allocation, but an alias may
110  /// be in use. A register can only be moved out of the disabled state if
111  /// all aliases are disabled.
112  regDisabled,
113 
114  /// A free register is not currently in use and can be allocated
115  /// immediately without checking aliases.
116  regFree,
117 
118  /// A reserved register has been assigned explicitly (e.g., setting up a
119  /// call parameter), and it remains reserved until it is used.
120  regReserved
121 
122  /// A register state may also be a virtual register number, indication
123  /// that the physical register is currently allocated to a virtual
124  /// register. In that case, LiveVirtRegs contains the inverse mapping.
125  };
126 
127  /// One of the RegState enums, or a virtreg.
128  std::vector<unsigned> PhysRegState;
129 
130  SmallVector<unsigned, 16> VirtDead;
132 
133  /// Set of register units.
134  using UsedInInstrSet = SparseSet<unsigned>;
135 
136  /// Set of register units that are used in the current instruction, and so
137  /// cannot be allocated.
138  UsedInInstrSet UsedInInstr;
139 
140  /// Mark a physreg as used in this instruction.
141  void markRegUsedInInstr(MCPhysReg PhysReg) {
142  for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units)
143  UsedInInstr.insert(*Units);
144  }
145 
146  /// Check if a physreg or any of its aliases are used in this instruction.
147  bool isRegUsedInInstr(MCPhysReg PhysReg) const {
148  for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units)
149  if (UsedInInstr.count(*Units))
150  return true;
151  return false;
152  }
153 
154  /// This flag is set when LiveRegMap will be cleared completely after
155  /// spilling all live registers. LiveRegMap entries should not be erased.
156  bool isBulkSpilling = false;
157 
158  enum : unsigned {
159  spillClean = 1,
160  spillDirty = 100,
161  spillImpossible = ~0u
162  };
163 
164  public:
165  StringRef getPassName() const override { return "Fast Register Allocator"; }
166 
167  void getAnalysisUsage(AnalysisUsage &AU) const override {
168  AU.setPreservesCFG();
170  }
171 
172  MachineFunctionProperties getRequiredProperties() const override {
175  }
176 
177  MachineFunctionProperties getSetProperties() const override {
180  }
181 
182  private:
183  bool runOnMachineFunction(MachineFunction &Fn) override;
184  void allocateBasicBlock(MachineBasicBlock &MBB);
185  void handleThroughOperands(MachineInstr &MI,
186  SmallVectorImpl<unsigned> &VirtDead);
187  int getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass &RC);
188  bool isLastUseOfLocalReg(const MachineOperand &MO) const;
189 
190  void addKillFlag(const LiveReg &LRI);
191  void killVirtReg(LiveRegMap::iterator LRI);
192  void killVirtReg(unsigned VirtReg);
193  void spillVirtReg(MachineBasicBlock::iterator MI, LiveRegMap::iterator);
194  void spillVirtReg(MachineBasicBlock::iterator MI, unsigned VirtReg);
195 
196  void usePhysReg(MachineOperand &MO);
197  void definePhysReg(MachineInstr &MI, MCPhysReg PhysReg, RegState NewState);
198  unsigned calcSpillCost(MCPhysReg PhysReg) const;
199  void assignVirtToPhysReg(LiveReg&, MCPhysReg PhysReg);
200 
201  LiveRegMap::iterator findLiveVirtReg(unsigned VirtReg) {
202  return LiveVirtRegs.find(TargetRegisterInfo::virtReg2Index(VirtReg));
203  }
204 
205  LiveRegMap::const_iterator findLiveVirtReg(unsigned VirtReg) const {
206  return LiveVirtRegs.find(TargetRegisterInfo::virtReg2Index(VirtReg));
207  }
208 
209  LiveRegMap::iterator assignVirtToPhysReg(unsigned VReg, MCPhysReg PhysReg);
210  LiveRegMap::iterator allocVirtReg(MachineInstr &MI, LiveRegMap::iterator,
211  unsigned Hint);
212  LiveRegMap::iterator defineVirtReg(MachineInstr &MI, unsigned OpNum,
213  unsigned VirtReg, unsigned Hint);
214  LiveRegMap::iterator reloadVirtReg(MachineInstr &MI, unsigned OpNum,
215  unsigned VirtReg, unsigned Hint);
216  void spillAll(MachineBasicBlock::iterator MI);
217  bool setPhysReg(MachineInstr &MI, unsigned OpNum, MCPhysReg PhysReg);
218 
219  void dumpState();
220  };
221 
222 } // end anonymous namespace
223 
224 char RegAllocFast::ID = 0;
225 
226 INITIALIZE_PASS(RegAllocFast, "regallocfast", "Fast Register Allocator", false,
227  false)
228 
229 /// This allocates space for the specified virtual register to be held on the
230 /// stack.
231 int RegAllocFast::getStackSpaceFor(unsigned VirtReg,
233  // Find the location Reg would belong...
234  int SS = StackSlotForVirtReg[VirtReg];
235  // Already has space allocated?
236  if (SS != -1)
237  return SS;
238 
239  // Allocate a new stack object for this spill location...
240  unsigned Size = TRI->getSpillSize(RC);
241  unsigned Align = TRI->getSpillAlignment(RC);
242  int FrameIdx = MFI->CreateSpillStackObject(Size, Align);
243 
244  // Assign the slot.
245  StackSlotForVirtReg[VirtReg] = FrameIdx;
246  return FrameIdx;
247 }
248 
249 /// Return true if MO is the only remaining reference to its virtual register,
250 /// and it is guaranteed to be a block-local register.
251 bool RegAllocFast::isLastUseOfLocalReg(const MachineOperand &MO) const {
252  // If the register has ever been spilled or reloaded, we conservatively assume
253  // it is a global register used in multiple blocks.
254  if (StackSlotForVirtReg[MO.getReg()] != -1)
255  return false;
256 
257  // Check that the use/def chain has exactly one operand - MO.
259  if (&*I != &MO)
260  return false;
261  return ++I == MRI->reg_nodbg_end();
262 }
263 
264 /// Set kill flags on last use of a virtual register.
265 void RegAllocFast::addKillFlag(const LiveReg &LR) {
266  if (!LR.LastUse) return;
267  MachineOperand &MO = LR.LastUse->getOperand(LR.LastOpNum);
268  if (MO.isUse() && !LR.LastUse->isRegTiedToDefOperand(LR.LastOpNum)) {
269  if (MO.getReg() == LR.PhysReg)
270  MO.setIsKill();
271  // else, don't do anything we are problably redefining a
272  // subreg of this register and given we don't track which
273  // lanes are actually dead, we cannot insert a kill flag here.
274  // Otherwise we may end up in a situation like this:
275  // ... = (MO) physreg:sub1, physreg <implicit-use, kill>
276  // ... <== Here we would allow later pass to reuse physreg:sub1
277  // which is potentially wrong.
278  // LR:sub0 = ...
279  // ... = LR.sub1 <== This is going to use physreg:sub1
280  }
281 }
282 
283 /// Mark virtreg as no longer available.
284 void RegAllocFast::killVirtReg(LiveRegMap::iterator LRI) {
285  addKillFlag(*LRI);
286  assert(PhysRegState[LRI->PhysReg] == LRI->VirtReg &&
287  "Broken RegState mapping");
288  PhysRegState[LRI->PhysReg] = regFree;
289  // Erase from LiveVirtRegs unless we're spilling in bulk.
290  if (!isBulkSpilling)
291  LiveVirtRegs.erase(LRI);
292 }
293 
294 /// Mark virtreg as no longer available.
295 void RegAllocFast::killVirtReg(unsigned VirtReg) {
297  "killVirtReg needs a virtual register");
298  LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg);
299  if (LRI != LiveVirtRegs.end())
300  killVirtReg(LRI);
301 }
302 
303 /// This method spills the value specified by VirtReg into the corresponding
304 /// stack slot if needed.
305 void RegAllocFast::spillVirtReg(MachineBasicBlock::iterator MI,
306  unsigned VirtReg) {
308  "Spilling a physical register is illegal!");
309  LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg);
310  assert(LRI != LiveVirtRegs.end() && "Spilling unmapped virtual register");
311  spillVirtReg(MI, LRI);
312 }
313 
314 /// Do the actual work of spilling.
315 void RegAllocFast::spillVirtReg(MachineBasicBlock::iterator MI,
316  LiveRegMap::iterator LRI) {
317  LiveReg &LR = *LRI;
318  assert(PhysRegState[LR.PhysReg] == LRI->VirtReg && "Broken RegState mapping");
319 
320  if (LR.Dirty) {
321  // If this physreg is used by the instruction, we want to kill it on the
322  // instruction, not on the spill.
323  bool SpillKill = MachineBasicBlock::iterator(LR.LastUse) != MI;
324  LR.Dirty = false;
325  DEBUG(dbgs() << "Spilling " << PrintReg(LRI->VirtReg, TRI)
326  << " in " << PrintReg(LR.PhysReg, TRI));
327  const TargetRegisterClass &RC = *MRI->getRegClass(LRI->VirtReg);
328  int FI = getStackSpaceFor(LRI->VirtReg, RC);
329  DEBUG(dbgs() << " to stack slot #" << FI << "\n");
330  TII->storeRegToStackSlot(*MBB, MI, LR.PhysReg, SpillKill, FI, &RC, TRI);
331  ++NumStores; // Update statistics
332 
333  // If this register is used by DBG_VALUE then insert new DBG_VALUE to
334  // identify spilled location as the place to find corresponding variable's
335  // value.
336  SmallVectorImpl<MachineInstr *> &LRIDbgValues =
337  LiveDbgValueMap[LRI->VirtReg];
338  for (MachineInstr *DBG : LRIDbgValues) {
339  MachineInstr *NewDV = buildDbgValueForSpill(*MBB, MI, *DBG, FI);
340  assert(NewDV->getParent() == MBB && "dangling parent pointer");
341  (void)NewDV;
342  DEBUG(dbgs() << "Inserting debug info due to spill:" << "\n" << *NewDV);
343  }
344  // Now this register is spilled there is should not be any DBG_VALUE
345  // pointing to this register because they are all pointing to spilled value
346  // now.
347  LRIDbgValues.clear();
348  if (SpillKill)
349  LR.LastUse = nullptr; // Don't kill register again
350  }
351  killVirtReg(LRI);
352 }
353 
354 /// Spill all dirty virtregs without killing them.
355 void RegAllocFast::spillAll(MachineBasicBlock::iterator MI) {
356  if (LiveVirtRegs.empty()) return;
357  isBulkSpilling = true;
358  // The LiveRegMap is keyed by an unsigned (the virtreg number), so the order
359  // of spilling here is deterministic, if arbitrary.
360  for (LiveRegMap::iterator I = LiveVirtRegs.begin(), E = LiveVirtRegs.end();
361  I != E; ++I)
362  spillVirtReg(MI, I);
363  LiveVirtRegs.clear();
364  isBulkSpilling = false;
365 }
366 
367 /// Handle the direct use of a physical register. Check that the register is
368 /// not used by a virtreg. Kill the physreg, marking it free. This may add
369 /// implicit kills to MO->getParent() and invalidate MO.
370 void RegAllocFast::usePhysReg(MachineOperand &MO) {
371  // Ignore undef uses.
372  if (MO.isUndef())
373  return;
374 
375  unsigned PhysReg = MO.getReg();
377  "Bad usePhysReg operand");
378 
379  markRegUsedInInstr(PhysReg);
380  switch (PhysRegState[PhysReg]) {
381  case regDisabled:
382  break;
383  case regReserved:
384  PhysRegState[PhysReg] = regFree;
386  case regFree:
387  MO.setIsKill();
388  return;
389  default:
390  // The physreg was allocated to a virtual register. That means the value we
391  // wanted has been clobbered.
392  llvm_unreachable("Instruction uses an allocated register");
393  }
394 
395  // Maybe a superregister is reserved?
396  for (MCRegAliasIterator AI(PhysReg, TRI, false); AI.isValid(); ++AI) {
397  MCPhysReg Alias = *AI;
398  switch (PhysRegState[Alias]) {
399  case regDisabled:
400  break;
401  case regReserved:
402  // Either PhysReg is a subregister of Alias and we mark the
403  // whole register as free, or PhysReg is the superregister of
404  // Alias and we mark all the aliases as disabled before freeing
405  // PhysReg.
406  // In the latter case, since PhysReg was disabled, this means that
407  // its value is defined only by physical sub-registers. This check
408  // is performed by the assert of the default case in this loop.
409  // Note: The value of the superregister may only be partial
410  // defined, that is why regDisabled is a valid state for aliases.
411  assert((TRI->isSuperRegister(PhysReg, Alias) ||
412  TRI->isSuperRegister(Alias, PhysReg)) &&
413  "Instruction is not using a subregister of a reserved register");
415  case regFree:
416  if (TRI->isSuperRegister(PhysReg, Alias)) {
417  // Leave the superregister in the working set.
418  PhysRegState[Alias] = regFree;
419  MO.getParent()->addRegisterKilled(Alias, TRI, true);
420  return;
421  }
422  // Some other alias was in the working set - clear it.
423  PhysRegState[Alias] = regDisabled;
424  break;
425  default:
426  llvm_unreachable("Instruction uses an alias of an allocated register");
427  }
428  }
429 
430  // All aliases are disabled, bring register into working set.
431  PhysRegState[PhysReg] = regFree;
432  MO.setIsKill();
433 }
434 
435 /// Mark PhysReg as reserved or free after spilling any virtregs. This is very
436 /// similar to defineVirtReg except the physreg is reserved instead of
437 /// allocated.
438 void RegAllocFast::definePhysReg(MachineInstr &MI, MCPhysReg PhysReg,
439  RegState NewState) {
440  markRegUsedInInstr(PhysReg);
441  switch (unsigned VirtReg = PhysRegState[PhysReg]) {
442  case regDisabled:
443  break;
444  default:
445  spillVirtReg(MI, VirtReg);
447  case regFree:
448  case regReserved:
449  PhysRegState[PhysReg] = NewState;
450  return;
451  }
452 
453  // This is a disabled register, disable all aliases.
454  PhysRegState[PhysReg] = NewState;
455  for (MCRegAliasIterator AI(PhysReg, TRI, false); AI.isValid(); ++AI) {
456  MCPhysReg Alias = *AI;
457  switch (unsigned VirtReg = PhysRegState[Alias]) {
458  case regDisabled:
459  break;
460  default:
461  spillVirtReg(MI, VirtReg);
463  case regFree:
464  case regReserved:
465  PhysRegState[Alias] = regDisabled;
466  if (TRI->isSuperRegister(PhysReg, Alias))
467  return;
468  break;
469  }
470  }
471 }
472 
473 /// \brief Return the cost of spilling clearing out PhysReg and aliases so it is
474 /// free for allocation. Returns 0 when PhysReg is free or disabled with all
475 /// aliases disabled - it can be allocated directly.
476 /// \returns spillImpossible when PhysReg or an alias can't be spilled.
477 unsigned RegAllocFast::calcSpillCost(MCPhysReg PhysReg) const {
478  if (isRegUsedInInstr(PhysReg)) {
479  DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " is already used in instr.\n");
480  return spillImpossible;
481  }
482  switch (unsigned VirtReg = PhysRegState[PhysReg]) {
483  case regDisabled:
484  break;
485  case regFree:
486  return 0;
487  case regReserved:
488  DEBUG(dbgs() << PrintReg(VirtReg, TRI) << " corresponding "
489  << PrintReg(PhysReg, TRI) << " is reserved already.\n");
490  return spillImpossible;
491  default: {
492  LiveRegMap::const_iterator I = findLiveVirtReg(VirtReg);
493  assert(I != LiveVirtRegs.end() && "Missing VirtReg entry");
494  return I->Dirty ? spillDirty : spillClean;
495  }
496  }
497 
498  // This is a disabled register, add up cost of aliases.
499  DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " is disabled.\n");
500  unsigned Cost = 0;
501  for (MCRegAliasIterator AI(PhysReg, TRI, false); AI.isValid(); ++AI) {
502  MCPhysReg Alias = *AI;
503  switch (unsigned VirtReg = PhysRegState[Alias]) {
504  case regDisabled:
505  break;
506  case regFree:
507  ++Cost;
508  break;
509  case regReserved:
510  return spillImpossible;
511  default: {
512  LiveRegMap::const_iterator I = findLiveVirtReg(VirtReg);
513  assert(I != LiveVirtRegs.end() && "Missing VirtReg entry");
514  Cost += I->Dirty ? spillDirty : spillClean;
515  break;
516  }
517  }
518  }
519  return Cost;
520 }
521 
522 /// \brief This method updates local state so that we know that PhysReg is the
523 /// proper container for VirtReg now. The physical register must not be used
524 /// for anything else when this is called.
525 void RegAllocFast::assignVirtToPhysReg(LiveReg &LR, MCPhysReg PhysReg) {
526  DEBUG(dbgs() << "Assigning " << PrintReg(LR.VirtReg, TRI) << " to "
527  << PrintReg(PhysReg, TRI) << "\n");
528  PhysRegState[PhysReg] = LR.VirtReg;
529  assert(!LR.PhysReg && "Already assigned a physreg");
530  LR.PhysReg = PhysReg;
531 }
532 
534 RegAllocFast::assignVirtToPhysReg(unsigned VirtReg, MCPhysReg PhysReg) {
535  LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg);
536  assert(LRI != LiveVirtRegs.end() && "VirtReg disappeared");
537  assignVirtToPhysReg(*LRI, PhysReg);
538  return LRI;
539 }
540 
541 /// Allocates a physical register for VirtReg.
542 RegAllocFast::LiveRegMap::iterator RegAllocFast::allocVirtReg(MachineInstr &MI,
543  LiveRegMap::iterator LRI, unsigned Hint) {
544  const unsigned VirtReg = LRI->VirtReg;
545 
547  "Can only allocate virtual registers");
548 
549  // Take hint when possible.
550  const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);
552  MRI->isAllocatable(Hint) && RC.contains(Hint)) {
553  // Ignore the hint if we would have to spill a dirty register.
554  unsigned Cost = calcSpillCost(Hint);
555  if (Cost < spillDirty) {
556  if (Cost)
557  definePhysReg(MI, Hint, regFree);
558  // definePhysReg may kill virtual registers and modify LiveVirtRegs.
559  // That invalidates LRI, so run a new lookup for VirtReg.
560  return assignVirtToPhysReg(VirtReg, Hint);
561  }
562  }
563 
564  // First try to find a completely free register.
565  ArrayRef<MCPhysReg> AO = RegClassInfo.getOrder(&RC);
566  for (MCPhysReg PhysReg : AO) {
567  if (PhysRegState[PhysReg] == regFree && !isRegUsedInInstr(PhysReg)) {
568  assignVirtToPhysReg(*LRI, PhysReg);
569  return LRI;
570  }
571  }
572 
573  DEBUG(dbgs() << "Allocating " << PrintReg(VirtReg) << " from "
574  << TRI->getRegClassName(&RC) << "\n");
575 
576  unsigned BestReg = 0;
577  unsigned BestCost = spillImpossible;
578  for (MCPhysReg PhysReg : AO) {
579  unsigned Cost = calcSpillCost(PhysReg);
580  DEBUG(dbgs() << "\tRegister: " << PrintReg(PhysReg, TRI) << "\n");
581  DEBUG(dbgs() << "\tCost: " << Cost << "\n");
582  DEBUG(dbgs() << "\tBestCost: " << BestCost << "\n");
583  // Cost is 0 when all aliases are already disabled.
584  if (Cost == 0) {
585  assignVirtToPhysReg(*LRI, PhysReg);
586  return LRI;
587  }
588  if (Cost < BestCost)
589  BestReg = PhysReg, BestCost = Cost;
590  }
591 
592  if (BestReg) {
593  definePhysReg(MI, BestReg, regFree);
594  // definePhysReg may kill virtual registers and modify LiveVirtRegs.
595  // That invalidates LRI, so run a new lookup for VirtReg.
596  return assignVirtToPhysReg(VirtReg, BestReg);
597  }
598 
599  // Nothing we can do. Report an error and keep going with a bad allocation.
600  if (MI.isInlineAsm())
601  MI.emitError("inline assembly requires more registers than available");
602  else
603  MI.emitError("ran out of registers during register allocation");
604  definePhysReg(MI, *AO.begin(), regFree);
605  return assignVirtToPhysReg(VirtReg, *AO.begin());
606 }
607 
608 /// Allocates a register for VirtReg and mark it as dirty.
609 RegAllocFast::LiveRegMap::iterator RegAllocFast::defineVirtReg(MachineInstr &MI,
610  unsigned OpNum,
611  unsigned VirtReg,
612  unsigned Hint) {
614  "Not a virtual register");
615  LiveRegMap::iterator LRI;
616  bool New;
617  std::tie(LRI, New) = LiveVirtRegs.insert(LiveReg(VirtReg));
618  if (New) {
619  // If there is no hint, peek at the only use of this register.
620  if ((!Hint || !TargetRegisterInfo::isPhysicalRegister(Hint)) &&
621  MRI->hasOneNonDBGUse(VirtReg)) {
622  const MachineInstr &UseMI = *MRI->use_instr_nodbg_begin(VirtReg);
623  // It's a copy, use the destination register as a hint.
624  if (UseMI.isCopyLike())
625  Hint = UseMI.getOperand(0).getReg();
626  }
627  LRI = allocVirtReg(MI, LRI, Hint);
628  } else if (LRI->LastUse) {
629  // Redefining a live register - kill at the last use, unless it is this
630  // instruction defining VirtReg multiple times.
631  if (LRI->LastUse != &MI || LRI->LastUse->getOperand(LRI->LastOpNum).isUse())
632  addKillFlag(*LRI);
633  }
634  assert(LRI->PhysReg && "Register not assigned");
635  LRI->LastUse = &MI;
636  LRI->LastOpNum = OpNum;
637  LRI->Dirty = true;
638  markRegUsedInInstr(LRI->PhysReg);
639  return LRI;
640 }
641 
642 /// Make sure VirtReg is available in a physreg and return it.
643 RegAllocFast::LiveRegMap::iterator RegAllocFast::reloadVirtReg(MachineInstr &MI,
644  unsigned OpNum,
645  unsigned VirtReg,
646  unsigned Hint) {
648  "Not a virtual register");
649  LiveRegMap::iterator LRI;
650  bool New;
651  std::tie(LRI, New) = LiveVirtRegs.insert(LiveReg(VirtReg));
652  MachineOperand &MO = MI.getOperand(OpNum);
653  if (New) {
654  LRI = allocVirtReg(MI, LRI, Hint);
655  const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);
656  int FrameIndex = getStackSpaceFor(VirtReg, RC);
657  DEBUG(dbgs() << "Reloading " << PrintReg(VirtReg, TRI) << " into "
658  << PrintReg(LRI->PhysReg, TRI) << "\n");
659  TII->loadRegFromStackSlot(*MBB, MI, LRI->PhysReg, FrameIndex, &RC, TRI);
660  ++NumLoads;
661  } else if (LRI->Dirty) {
662  if (isLastUseOfLocalReg(MO)) {
663  DEBUG(dbgs() << "Killing last use: " << MO << "\n");
664  if (MO.isUse())
665  MO.setIsKill();
666  else
667  MO.setIsDead();
668  } else if (MO.isKill()) {
669  DEBUG(dbgs() << "Clearing dubious kill: " << MO << "\n");
670  MO.setIsKill(false);
671  } else if (MO.isDead()) {
672  DEBUG(dbgs() << "Clearing dubious dead: " << MO << "\n");
673  MO.setIsDead(false);
674  }
675  } else if (MO.isKill()) {
676  // We must remove kill flags from uses of reloaded registers because the
677  // register would be killed immediately, and there might be a second use:
678  // %foo = OR %x<kill>, %x
679  // This would cause a second reload of %x into a different register.
680  DEBUG(dbgs() << "Clearing clean kill: " << MO << "\n");
681  MO.setIsKill(false);
682  } else if (MO.isDead()) {
683  DEBUG(dbgs() << "Clearing clean dead: " << MO << "\n");
684  MO.setIsDead(false);
685  }
686  assert(LRI->PhysReg && "Register not assigned");
687  LRI->LastUse = &MI;
688  LRI->LastOpNum = OpNum;
689  markRegUsedInInstr(LRI->PhysReg);
690  return LRI;
691 }
692 
693 /// Changes operand OpNum in MI the refer the PhysReg, considering subregs. This
694 /// may invalidate any operand pointers. Return true if the operand kills its
695 /// register.
696 bool RegAllocFast::setPhysReg(MachineInstr &MI, unsigned OpNum,
697  MCPhysReg PhysReg) {
698  MachineOperand &MO = MI.getOperand(OpNum);
699  bool Dead = MO.isDead();
700  if (!MO.getSubReg()) {
701  MO.setReg(PhysReg);
702  return MO.isKill() || Dead;
703  }
704 
705  // Handle subregister index.
706  MO.setReg(PhysReg ? TRI->getSubReg(PhysReg, MO.getSubReg()) : 0);
707  MO.setSubReg(0);
708 
709  // A kill flag implies killing the full register. Add corresponding super
710  // register kill.
711  if (MO.isKill()) {
712  MI.addRegisterKilled(PhysReg, TRI, true);
713  return true;
714  }
715 
716  // A <def,read-undef> of a sub-register requires an implicit def of the full
717  // register.
718  if (MO.isDef() && MO.isUndef())
719  MI.addRegisterDefined(PhysReg, TRI);
720 
721  return Dead;
722 }
723 
724 // Handles special instruction operand like early clobbers and tied ops when
725 // there are additional physreg defines.
726 void RegAllocFast::handleThroughOperands(MachineInstr &MI,
727  SmallVectorImpl<unsigned> &VirtDead) {
728  DEBUG(dbgs() << "Scanning for through registers:");
729  SmallSet<unsigned, 8> ThroughRegs;
730  for (const MachineOperand &MO : MI.operands()) {
731  if (!MO.isReg()) continue;
732  unsigned Reg = MO.getReg();
734  continue;
735  if (MO.isEarlyClobber() || (MO.isUse() && MO.isTied()) ||
736  (MO.getSubReg() && MI.readsVirtualRegister(Reg))) {
737  if (ThroughRegs.insert(Reg).second)
738  DEBUG(dbgs() << ' ' << PrintReg(Reg));
739  }
740  }
741 
742  // If any physreg defines collide with preallocated through registers,
743  // we must spill and reallocate.
744  DEBUG(dbgs() << "\nChecking for physdef collisions.\n");
745  for (const MachineOperand &MO : MI.operands()) {
746  if (!MO.isReg() || !MO.isDef()) continue;
747  unsigned Reg = MO.getReg();
748  if (!Reg || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue;
749  markRegUsedInInstr(Reg);
750  for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) {
751  if (ThroughRegs.count(PhysRegState[*AI]))
752  definePhysReg(MI, *AI, regFree);
753  }
754  }
755 
756  SmallVector<unsigned, 8> PartialDefs;
757  DEBUG(dbgs() << "Allocating tied uses.\n");
758  for (unsigned I = 0, E = MI.getNumOperands(); I != E; ++I) {
759  const MachineOperand &MO = MI.getOperand(I);
760  if (!MO.isReg()) continue;
761  unsigned Reg = MO.getReg();
762  if (!TargetRegisterInfo::isVirtualRegister(Reg)) continue;
763  if (MO.isUse()) {
764  if (!MO.isTied()) continue;
765  DEBUG(dbgs() << "Operand " << I << "("<< MO << ") is tied to operand "
766  << MI.findTiedOperandIdx(I) << ".\n");
767  LiveRegMap::iterator LRI = reloadVirtReg(MI, I, Reg, 0);
768  MCPhysReg PhysReg = LRI->PhysReg;
769  setPhysReg(MI, I, PhysReg);
770  // Note: we don't update the def operand yet. That would cause the normal
771  // def-scan to attempt spilling.
772  } else if (MO.getSubReg() && MI.readsVirtualRegister(Reg)) {
773  DEBUG(dbgs() << "Partial redefine: " << MO << "\n");
774  // Reload the register, but don't assign to the operand just yet.
775  // That would confuse the later phys-def processing pass.
776  LiveRegMap::iterator LRI = reloadVirtReg(MI, I, Reg, 0);
777  PartialDefs.push_back(LRI->PhysReg);
778  }
779  }
780 
781  DEBUG(dbgs() << "Allocating early clobbers.\n");
782  for (unsigned I = 0, E = MI.getNumOperands(); I != E; ++I) {
783  const MachineOperand &MO = MI.getOperand(I);
784  if (!MO.isReg()) continue;
785  unsigned Reg = MO.getReg();
786  if (!TargetRegisterInfo::isVirtualRegister(Reg)) continue;
787  if (!MO.isEarlyClobber())
788  continue;
789  // Note: defineVirtReg may invalidate MO.
790  LiveRegMap::iterator LRI = defineVirtReg(MI, I, Reg, 0);
791  MCPhysReg PhysReg = LRI->PhysReg;
792  if (setPhysReg(MI, I, PhysReg))
793  VirtDead.push_back(Reg);
794  }
795 
796  // Restore UsedInInstr to a state usable for allocating normal virtual uses.
797  UsedInInstr.clear();
798  for (const MachineOperand &MO : MI.operands()) {
799  if (!MO.isReg() || (MO.isDef() && !MO.isEarlyClobber())) continue;
800  unsigned Reg = MO.getReg();
801  if (!Reg || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue;
802  DEBUG(dbgs() << "\tSetting " << PrintReg(Reg, TRI)
803  << " as used in instr\n");
804  markRegUsedInInstr(Reg);
805  }
806 
807  // Also mark PartialDefs as used to avoid reallocation.
808  for (unsigned PartialDef : PartialDefs)
809  markRegUsedInInstr(PartialDef);
810 }
811 
812 #ifndef NDEBUG
813 void RegAllocFast::dumpState() {
814  for (unsigned Reg = 1, E = TRI->getNumRegs(); Reg != E; ++Reg) {
815  if (PhysRegState[Reg] == regDisabled) continue;
816  dbgs() << " " << TRI->getName(Reg);
817  switch(PhysRegState[Reg]) {
818  case regFree:
819  break;
820  case regReserved:
821  dbgs() << "*";
822  break;
823  default: {
824  dbgs() << '=' << PrintReg(PhysRegState[Reg]);
825  LiveRegMap::iterator I = findLiveVirtReg(PhysRegState[Reg]);
826  assert(I != LiveVirtRegs.end() && "Missing VirtReg entry");
827  if (I->Dirty)
828  dbgs() << "*";
829  assert(I->PhysReg == Reg && "Bad inverse map");
830  break;
831  }
832  }
833  }
834  dbgs() << '\n';
835  // Check that LiveVirtRegs is the inverse.
836  for (LiveRegMap::iterator i = LiveVirtRegs.begin(),
837  e = LiveVirtRegs.end(); i != e; ++i) {
839  "Bad map key");
841  "Bad map value");
842  assert(PhysRegState[i->PhysReg] == i->VirtReg && "Bad inverse map");
843  }
844 }
845 #endif
846 
847 void RegAllocFast::allocateBasicBlock(MachineBasicBlock &MBB) {
848  this->MBB = &MBB;
849  DEBUG(dbgs() << "\nAllocating " << MBB);
850 
851  PhysRegState.assign(TRI->getNumRegs(), regDisabled);
852  assert(LiveVirtRegs.empty() && "Mapping not cleared from last block?");
853 
855 
856  // Add live-in registers as live.
857  for (const MachineBasicBlock::RegisterMaskPair LI : MBB.liveins())
858  if (MRI->isAllocatable(LI.PhysReg))
859  definePhysReg(*MII, LI.PhysReg, regReserved);
860 
861  VirtDead.clear();
862  Coalesced.clear();
863 
864  // Otherwise, sequentially allocate each instruction in the MBB.
865  for (MachineInstr &MI : MBB) {
866  const MCInstrDesc &MCID = MI.getDesc();
867  DEBUG(
868  dbgs() << "\n>> " << MI << "Regs:";
869  dumpState()
870  );
871 
872  // Debug values are not allowed to change codegen in any way.
873  if (MI.isDebugValue()) {
874  MachineInstr *DebugMI = &MI;
875  MachineOperand &MO = DebugMI->getOperand(0);
876 
877  // Ignore DBG_VALUEs that aren't based on virtual registers. These are
878  // mostly constants and frame indices.
879  if (!MO.isReg())
880  continue;
881  unsigned Reg = MO.getReg();
883  continue;
884 
885  // See if this virtual register has already been allocated to a physical
886  // register or spilled to a stack slot.
887  LiveRegMap::iterator LRI = findLiveVirtReg(Reg);
888  if (LRI != LiveVirtRegs.end())
889  setPhysReg(*DebugMI, 0, LRI->PhysReg);
890  else {
891  int SS = StackSlotForVirtReg[Reg];
892  if (SS != -1) {
893  // Modify DBG_VALUE now that the value is in a spill slot.
894  updateDbgValueForSpill(*DebugMI, SS);
895  DEBUG(dbgs() << "Modifying debug info due to spill:"
896  << "\t" << *DebugMI);
897  continue;
898  }
899 
900  // We can't allocate a physreg for a DebugValue, sorry!
901  DEBUG(dbgs() << "Unable to allocate vreg used by DBG_VALUE");
902  MO.setReg(0);
903  }
904 
905  // If Reg hasn't been spilled, put this DBG_VALUE in LiveDbgValueMap so
906  // that future spills of Reg will have DBG_VALUEs.
907  LiveDbgValueMap[Reg].push_back(DebugMI);
908  continue;
909  }
910 
911  // If this is a copy, we may be able to coalesce.
912  unsigned CopySrcReg = 0;
913  unsigned CopyDstReg = 0;
914  unsigned CopySrcSub = 0;
915  unsigned CopyDstSub = 0;
916  if (MI.isCopy()) {
917  CopyDstReg = MI.getOperand(0).getReg();
918  CopySrcReg = MI.getOperand(1).getReg();
919  CopyDstSub = MI.getOperand(0).getSubReg();
920  CopySrcSub = MI.getOperand(1).getSubReg();
921  }
922 
923  // Track registers used by instruction.
924  UsedInInstr.clear();
925 
926  // First scan.
927  // Mark physreg uses and early clobbers as used.
928  // Find the end of the virtreg operands
929  unsigned VirtOpEnd = 0;
930  bool hasTiedOps = false;
931  bool hasEarlyClobbers = false;
932  bool hasPartialRedefs = false;
933  bool hasPhysDefs = false;
934  for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
935  MachineOperand &MO = MI.getOperand(i);
936  // Make sure MRI knows about registers clobbered by regmasks.
937  if (MO.isRegMask()) {
939  continue;
940  }
941  if (!MO.isReg()) continue;
942  unsigned Reg = MO.getReg();
943  if (!Reg) continue;
945  VirtOpEnd = i+1;
946  if (MO.isUse()) {
947  hasTiedOps = hasTiedOps ||
948  MCID.getOperandConstraint(i, MCOI::TIED_TO) != -1;
949  } else {
950  if (MO.isEarlyClobber())
951  hasEarlyClobbers = true;
952  if (MO.getSubReg() && MI.readsVirtualRegister(Reg))
953  hasPartialRedefs = true;
954  }
955  continue;
956  }
957  if (!MRI->isAllocatable(Reg)) continue;
958  if (MO.isUse()) {
959  usePhysReg(MO);
960  } else if (MO.isEarlyClobber()) {
961  definePhysReg(MI, Reg,
962  (MO.isImplicit() || MO.isDead()) ? regFree : regReserved);
963  hasEarlyClobbers = true;
964  } else
965  hasPhysDefs = true;
966  }
967 
968  // The instruction may have virtual register operands that must be allocated
969  // the same register at use-time and def-time: early clobbers and tied
970  // operands. If there are also physical defs, these registers must avoid
971  // both physical defs and uses, making them more constrained than normal
972  // operands.
973  // Similarly, if there are multiple defs and tied operands, we must make
974  // sure the same register is allocated to uses and defs.
975  // We didn't detect inline asm tied operands above, so just make this extra
976  // pass for all inline asm.
977  if (MI.isInlineAsm() || hasEarlyClobbers || hasPartialRedefs ||
978  (hasTiedOps && (hasPhysDefs || MCID.getNumDefs() > 1))) {
979  handleThroughOperands(MI, VirtDead);
980  // Don't attempt coalescing when we have funny stuff going on.
981  CopyDstReg = 0;
982  // Pretend we have early clobbers so the use operands get marked below.
983  // This is not necessary for the common case of a single tied use.
984  hasEarlyClobbers = true;
985  }
986 
987  // Second scan.
988  // Allocate virtreg uses.
989  for (unsigned I = 0; I != VirtOpEnd; ++I) {
990  const MachineOperand &MO = MI.getOperand(I);
991  if (!MO.isReg()) continue;
992  unsigned Reg = MO.getReg();
993  if (!TargetRegisterInfo::isVirtualRegister(Reg)) continue;
994  if (MO.isUse()) {
995  LiveRegMap::iterator LRI = reloadVirtReg(MI, I, Reg, CopyDstReg);
996  MCPhysReg PhysReg = LRI->PhysReg;
997  CopySrcReg = (CopySrcReg == Reg || CopySrcReg == PhysReg) ? PhysReg : 0;
998  if (setPhysReg(MI, I, PhysReg))
999  killVirtReg(LRI);
1000  }
1001  }
1002 
1003  // Track registers defined by instruction - early clobbers and tied uses at
1004  // this point.
1005  UsedInInstr.clear();
1006  if (hasEarlyClobbers) {
1007  for (const MachineOperand &MO : MI.operands()) {
1008  if (!MO.isReg()) continue;
1009  unsigned Reg = MO.getReg();
1010  if (!Reg || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue;
1011  // Look for physreg defs and tied uses.
1012  if (!MO.isDef() && !MO.isTied()) continue;
1013  markRegUsedInInstr(Reg);
1014  }
1015  }
1016 
1017  unsigned DefOpEnd = MI.getNumOperands();
1018  if (MI.isCall()) {
1019  // Spill all virtregs before a call. This serves one purpose: If an
1020  // exception is thrown, the landing pad is going to expect to find
1021  // registers in their spill slots.
1022  // Note: although this is appealing to just consider all definitions
1023  // as call-clobbered, this is not correct because some of those
1024  // definitions may be used later on and we do not want to reuse
1025  // those for virtual registers in between.
1026  DEBUG(dbgs() << " Spilling remaining registers before call.\n");
1027  spillAll(MI);
1028  }
1029 
1030  // Third scan.
1031  // Allocate defs and collect dead defs.
1032  for (unsigned I = 0; I != DefOpEnd; ++I) {
1033  const MachineOperand &MO = MI.getOperand(I);
1034  if (!MO.isReg() || !MO.isDef() || !MO.getReg() || MO.isEarlyClobber())
1035  continue;
1036  unsigned Reg = MO.getReg();
1037 
1039  if (!MRI->isAllocatable(Reg)) continue;
1040  definePhysReg(MI, Reg, MO.isDead() ? regFree : regReserved);
1041  continue;
1042  }
1043  LiveRegMap::iterator LRI = defineVirtReg(MI, I, Reg, CopySrcReg);
1044  MCPhysReg PhysReg = LRI->PhysReg;
1045  if (setPhysReg(MI, I, PhysReg)) {
1046  VirtDead.push_back(Reg);
1047  CopyDstReg = 0; // cancel coalescing;
1048  } else
1049  CopyDstReg = (CopyDstReg == Reg || CopyDstReg == PhysReg) ? PhysReg : 0;
1050  }
1051 
1052  // Kill dead defs after the scan to ensure that multiple defs of the same
1053  // register are allocated identically. We didn't need to do this for uses
1054  // because we are crerating our own kill flags, and they are always at the
1055  // last use.
1056  for (unsigned VirtReg : VirtDead)
1057  killVirtReg(VirtReg);
1058  VirtDead.clear();
1059 
1060  if (CopyDstReg && CopyDstReg == CopySrcReg && CopyDstSub == CopySrcSub) {
1061  DEBUG(dbgs() << "-- coalescing: " << MI);
1062  Coalesced.push_back(&MI);
1063  } else {
1064  DEBUG(dbgs() << "<< " << MI);
1065  }
1066  }
1067 
1068  // Spill all physical registers holding virtual registers now.
1069  DEBUG(dbgs() << "Spilling live registers at end of block.\n");
1070  spillAll(MBB.getFirstTerminator());
1071 
1072  // Erase all the coalesced copies. We are delaying it until now because
1073  // LiveVirtRegs might refer to the instrs.
1074  for (MachineInstr *MI : Coalesced)
1075  MBB.erase(MI);
1076  NumCopies += Coalesced.size();
1077 
1078  DEBUG(MBB.dump());
1079 }
1080 
1081 /// Allocates registers for a function.
1082 bool RegAllocFast::runOnMachineFunction(MachineFunction &MF) {
1083  DEBUG(dbgs() << "********** FAST REGISTER ALLOCATION **********\n"
1084  << "********** Function: " << MF.getName() << '\n');
1085  MRI = &MF.getRegInfo();
1086  const TargetSubtargetInfo &STI = MF.getSubtarget();
1087  TRI = STI.getRegisterInfo();
1088  TII = STI.getInstrInfo();
1089  MFI = &MF.getFrameInfo();
1090  MRI->freezeReservedRegs(MF);
1091  RegClassInfo.runOnMachineFunction(MF);
1092  UsedInInstr.clear();
1093  UsedInInstr.setUniverse(TRI->getNumRegUnits());
1094 
1095  // initialize the virtual->physical register map to have a 'null'
1096  // mapping for all virtual registers
1097  unsigned NumVirtRegs = MRI->getNumVirtRegs();
1098  StackSlotForVirtReg.resize(NumVirtRegs);
1099  LiveVirtRegs.setUniverse(NumVirtRegs);
1100 
1101  // Loop over all of the basic blocks, eliminating virtual register references
1102  for (MachineBasicBlock &MBB : MF)
1103  allocateBasicBlock(MBB);
1104 
1105  // All machine operands and other references to virtual registers have been
1106  // replaced. Remove the virtual registers.
1107  MRI->clearVirtRegs();
1108 
1109  StackSlotForVirtReg.clear();
1110  LiveDbgValueMap.clear();
1111  return true;
1112 }
1113 
1115  return new RegAllocFast();
1116 }
bool isRegMask() const
isRegMask - Tests if this is a MO_RegisterMask operand.
ArrayRef< MCPhysReg > getOrder(const TargetRegisterClass *RC) const
getOrder - Returns the preferred allocation order for RC.
void push_back(const T &Elt)
Definition: SmallVector.h:212
constexpr char Align[]
Key for Kernel::Arg::Metadata::mAlign.
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
bool contains(unsigned Reg) const
Return true if the specified register is included in this register class.
bool isCall(QueryType Type=AnyInBundle) const
Definition: MachineInstr.h:458
const TargetRegisterClass * getRegClass(unsigned Reg) const
Return the register class of the specified virtual register.
void emitError(StringRef Msg) const
Emit an error referring to the source location of this instruction.
bool isAllocatable(unsigned PhysReg) const
isAllocatable - Returns true when PhysReg belongs to an allocatable register class and it hasn&#39;t been...
static unsigned virtReg2Index(unsigned Reg)
Convert a virtual register number to a 0-based index.
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
std::pair< iterator, bool > insert(const ValueT &Val)
insert - Attempts to insert a new element.
Definition: SparseSet.h:249
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:163
unsigned getReg() const
getReg - Returns the register number.
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
This file contains the declarations for metadata subclasses.
unsigned getSubReg() const
bool isInlineAsm() const
Definition: MachineInstr.h:832
STATISTIC(NumFunctions, "Total number of functions")
void setIsDead(bool Val=true)
reg_nodbg_iterator reg_nodbg_begin(unsigned RegNo) const
iterator_range< mop_iterator > operands()
Definition: MachineInstr.h:332
bool isCopyLike() const
Return true if the instruction behaves like a copy.
Definition: MachineInstr.h:871
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 ...
bool isEarlyClobber() const
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...
MachineInstr * buildDbgValueForSpill(MachineBasicBlock &BB, MachineBasicBlock::iterator I, const MachineInstr &Orig, int FrameIndex)
Clone a DBG_VALUE whose value has been spilled to FrameIndex.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
const HexagonInstrInfo * TII
unsigned getNumOperands() const
Access to explicit operands of the instruction.
Definition: MachineInstr.h:293
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...
const MCInstrDesc & getDesc() const
Returns the target instruction descriptor of this MachineInstr.
Definition: MachineInstr.h:287
RegisterRegAlloc class - Track the registration of register allocators.
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.
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
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...
TargetInstrInfo - Interface to description of machine instruction set.
bool isSuperRegister(unsigned RegA, unsigned RegB) const
Returns true if RegB is a super-register of RegA.
unsigned getNumRegs() const
Return the number of registers this target has (useful for sizing arrays holding per register informa...
MachineInstrBundleIterator< MachineInstr > iterator
unsigned const MachineRegisterInfo * MRI
typename DenseT::iterator iterator
Definition: SparseSet.h:171
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
bool readsVirtualRegister(unsigned Reg) const
Return true if the MachineInstr reads the specified virtual register.
Definition: MachineInstr.h:935
MachineFrameInfo & getFrameInfo()
getFrameInfo - Return the frame info object for the current function.
MachineInstrBuilder & UseMI
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
unsigned getSubReg(unsigned Reg, unsigned Idx) const
Returns the physical register number of sub-register "Index" for physical register RegNo...
MCRegAliasIterator enumerates all registers aliasing Reg.
Represent the analysis usage information of a pass.
void resize(typename StorageT::size_type s)
Definition: IndexedMap.h:60
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn&#39;t already there.
Definition: SmallSet.h:81
void runOnMachineFunction(const MachineFunction &MF)
runOnFunction - Prepare to answer questions about MF.
bool isCopy() const
Definition: MachineInstr.h:857
Information about a live register.
int CreateSpillStackObject(uint64_t Size, unsigned Alignment)
Create a new statically sized stack object that represents a spill slot, returning a nonnegative iden...
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
void setIsKill(bool Val=true)
int getOperandConstraint(unsigned OpNum, MCOI::OperandConstraint Constraint) const
Returns the value of the specific constraint if it is set.
Definition: MCInstrDesc.h:187
unsigned findTiedOperandIdx(unsigned OpIdx) const
Given the index of a tied register operand, find the operand it is tied to.
bool isDebugValue() const
Definition: MachineInstr.h:816
MachineOperand class - Representation of each machine instruction operand.
static RegisterRegAlloc fastRegAlloc("fast", "fast register allocator", createFastRegisterAllocator)
void updateDbgValueForSpill(MachineInstr &Orig, int FrameIndex)
Update a DBG_VALUE whose value has been spilled to FrameIndex.
unsigned getNumDefs() const
Return the number of MachineOperands that are register definitions.
Definition: MCInstrDesc.h:225
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:285
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
void addRegisterDefined(unsigned Reg, const TargetRegisterInfo *RegInfo=nullptr)
We have determined MI defines a register.
const uint32_t * getRegMask() const
getRegMask - Returns a bit mask of registers preserved by this RegMask operand.
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
virtual void storeRegToStackSlot(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI, unsigned SrcReg, bool isKill, int FrameIndex, const TargetRegisterClass *RC, const TargetRegisterInfo *TRI) const
Store the specified register of the given register class to the specified stack frame index...
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:139
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
MachineFunctionProperties & set(Property P)
TargetSubtargetInfo - Generic base class for all target subtargets.
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.
SparseSet - Fast set implmentation for objects that can be identified by small unsigned keys...
Definition: SparseSet.h:123
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
void setReg(unsigned Reg)
Change the register this operand corresponds to.
#define I(x, y, z)
Definition: MD5.cpp:58
Pair of physical register and lane mask.
void setSubReg(unsigned subReg)
void addPhysRegsUsedFromRegMask(const uint32_t *RegMask)
addPhysRegsUsedFromRegMask - Mark any registers not in RegMask as used.
INITIALIZE_PASS(RegAllocFast, "regallocfast", "Fast Register Allocator", false, false) int RegAllocFast
This allocates space for the specified virtual register to be held on the stack.
bool hasOneNonDBGUse(unsigned RegNo) const
hasOneNonDBGUse - Return true if there is exactly one non-Debug instruction using the specified regis...
iterator_range< livein_iterator > liveins() const
bool isReg() const
isReg - Tests if this is a MO_Register operand.
static reg_nodbg_iterator reg_nodbg_end()
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
FunctionPass * createFastRegisterAllocator()
FastRegisterAllocation Pass - This pass register allocates as fast as possible.
aarch64 promote const
use_instr_nodbg_iterator use_instr_nodbg_begin(unsigned RegNo) const
constexpr char Size[]
Key for Kernel::Arg::Metadata::mSize.
#define LLVM_FALLTHROUGH
LLVM_FALLTHROUGH - Mark fallthrough cases in switch statements.
Definition: Compiler.h:235
#define DEBUG(X)
Definition: Debug.h:118
bool addRegisterKilled(unsigned IncomingReg, const TargetRegisterInfo *RegInfo, bool AddIfNotFound=false)
We have determined MI kills a register.
IRTranslator LLVM IR MI
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
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 void loadRegFromStackSlot(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI, unsigned DestReg, int FrameIndex, const TargetRegisterClass *RC, const TargetRegisterInfo *TRI) const
Load the specified register of the given register class from the specified stack frame index...
Properties which a MachineFunction may have at a given point in time.
bool isImplicit() const
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
Definition: SmallSet.h:65