LLVM  7.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"
37 #include "llvm/IR/DebugLoc.h"
38 #include "llvm/IR/Metadata.h"
39 #include "llvm/MC/MCInstrDesc.h"
40 #include "llvm/MC/MCRegisterInfo.h"
41 #include "llvm/Pass.h"
42 #include "llvm/Support/Casting.h"
43 #include "llvm/Support/Compiler.h"
44 #include "llvm/Support/Debug.h"
47 #include <cassert>
48 #include <tuple>
49 #include <vector>
50 
51 using namespace llvm;
52 
53 #define DEBUG_TYPE "regalloc"
54 
55 STATISTIC(NumStores, "Number of stores added");
56 STATISTIC(NumLoads , "Number of loads added");
57 STATISTIC(NumCopies, "Number of copies coalesced");
58 
59 static RegisterRegAlloc
60  fastRegAlloc("fast", "fast register allocator", createFastRegisterAllocator);
61 
62 namespace {
63 
64  class RegAllocFast : public MachineFunctionPass {
65  public:
66  static char ID;
67 
68  RegAllocFast() : MachineFunctionPass(ID), StackSlotForVirtReg(-1) {}
69 
70  private:
71  MachineFrameInfo *MFI;
73  const TargetRegisterInfo *TRI;
74  const TargetInstrInfo *TII;
75  RegisterClassInfo RegClassInfo;
76 
77  /// Basic block currently being allocated.
78  MachineBasicBlock *MBB;
79 
80  /// Maps virtual regs to the frame index where these values are spilled.
81  IndexedMap<int, VirtReg2IndexFunctor> StackSlotForVirtReg;
82 
83  /// Everything we know about a live virtual register.
84  struct LiveReg {
85  MachineInstr *LastUse = nullptr; ///< Last instr to use reg.
86  unsigned VirtReg; ///< Virtual register number.
87  MCPhysReg PhysReg = 0; ///< Currently held here.
88  unsigned short LastOpNum = 0; ///< OpNum on LastUse.
89  bool Dirty = false; ///< Register needs spill.
90 
91  explicit LiveReg(unsigned v) : VirtReg(v) {}
92 
93  unsigned getSparseSetIndex() const {
94  return TargetRegisterInfo::virtReg2Index(VirtReg);
95  }
96  };
97 
98  using LiveRegMap = SparseSet<LiveReg>;
99 
100  /// This map contains entries for each virtual register that is currently
101  /// available in a physical register.
102  LiveRegMap LiveVirtRegs;
103 
105 
106  /// Track the state of a physical register.
107  enum RegState {
108  /// A disabled register is not available for allocation, but an alias may
109  /// be in use. A register can only be moved out of the disabled state if
110  /// all aliases are disabled.
111  regDisabled,
112 
113  /// A free register is not currently in use and can be allocated
114  /// immediately without checking aliases.
115  regFree,
116 
117  /// A reserved register has been assigned explicitly (e.g., setting up a
118  /// call parameter), and it remains reserved until it is used.
119  regReserved
120 
121  /// A register state may also be a virtual register number, indication
122  /// that the physical register is currently allocated to a virtual
123  /// register. In that case, LiveVirtRegs contains the inverse mapping.
124  };
125 
126  /// One of the RegState enums, or a virtreg.
127  std::vector<unsigned> PhysRegState;
128 
129  SmallVector<unsigned, 16> VirtDead;
131 
132  /// Set of register units.
133  using UsedInInstrSet = SparseSet<unsigned>;
134 
135  /// Set of register units that are used in the current instruction, and so
136  /// cannot be allocated.
137  UsedInInstrSet UsedInInstr;
138 
139  /// Mark a physreg as used in this instruction.
140  void markRegUsedInInstr(MCPhysReg PhysReg) {
141  for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units)
142  UsedInInstr.insert(*Units);
143  }
144 
145  /// Check if a physreg or any of its aliases are used in this instruction.
146  bool isRegUsedInInstr(MCPhysReg PhysReg) const {
147  for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units)
148  if (UsedInInstr.count(*Units))
149  return true;
150  return false;
151  }
152 
153  /// This flag is set when LiveRegMap will be cleared completely after
154  /// spilling all live registers. LiveRegMap entries should not be erased.
155  bool isBulkSpilling = false;
156 
157  enum : unsigned {
158  spillClean = 1,
159  spillDirty = 100,
160  spillImpossible = ~0u
161  };
162 
163  public:
164  StringRef getPassName() const override { return "Fast Register Allocator"; }
165 
166  void getAnalysisUsage(AnalysisUsage &AU) const override {
167  AU.setPreservesCFG();
169  }
170 
171  MachineFunctionProperties getRequiredProperties() const override {
174  }
175 
176  MachineFunctionProperties getSetProperties() const override {
179  }
180 
181  private:
182  bool runOnMachineFunction(MachineFunction &Fn) override;
183  void allocateBasicBlock(MachineBasicBlock &MBB);
184  void handleThroughOperands(MachineInstr &MI,
185  SmallVectorImpl<unsigned> &VirtDead);
186  int getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass &RC);
187  bool isLastUseOfLocalReg(const MachineOperand &MO) const;
188 
189  void addKillFlag(const LiveReg &LRI);
190  void killVirtReg(LiveRegMap::iterator LRI);
191  void killVirtReg(unsigned VirtReg);
192  void spillVirtReg(MachineBasicBlock::iterator MI, LiveRegMap::iterator);
193  void spillVirtReg(MachineBasicBlock::iterator MI, unsigned VirtReg);
194 
195  void usePhysReg(MachineOperand &MO);
196  void definePhysReg(MachineBasicBlock::iterator MI, MCPhysReg PhysReg,
197  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, implicit killed physreg
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  LLVM_DEBUG(dbgs() << "Spilling " << printReg(LRI->VirtReg, TRI) << " in "
326  << printReg(LR.PhysReg, TRI));
327  const TargetRegisterClass &RC = *MRI->getRegClass(LRI->VirtReg);
328  int FI = getStackSpaceFor(LRI->VirtReg, RC);
329  LLVM_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  LLVM_DEBUG(dbgs() << "Inserting debug info due to spill:"
343  << "\n"
344  << *NewDV);
345  }
346  // Now this register is spilled there is should not be any DBG_VALUE
347  // pointing to this register because they are all pointing to spilled value
348  // now.
349  LRIDbgValues.clear();
350  if (SpillKill)
351  LR.LastUse = nullptr; // Don't kill register again
352  }
353  killVirtReg(LRI);
354 }
355 
356 /// Spill all dirty virtregs without killing them.
357 void RegAllocFast::spillAll(MachineBasicBlock::iterator MI) {
358  if (LiveVirtRegs.empty()) return;
359  isBulkSpilling = true;
360  // The LiveRegMap is keyed by an unsigned (the virtreg number), so the order
361  // of spilling here is deterministic, if arbitrary.
362  for (LiveRegMap::iterator I = LiveVirtRegs.begin(), E = LiveVirtRegs.end();
363  I != E; ++I)
364  spillVirtReg(MI, I);
365  LiveVirtRegs.clear();
366  isBulkSpilling = false;
367 }
368 
369 /// Handle the direct use of a physical register. Check that the register is
370 /// not used by a virtreg. Kill the physreg, marking it free. This may add
371 /// implicit kills to MO->getParent() and invalidate MO.
372 void RegAllocFast::usePhysReg(MachineOperand &MO) {
373  // Ignore undef uses.
374  if (MO.isUndef())
375  return;
376 
377  unsigned PhysReg = MO.getReg();
379  "Bad usePhysReg operand");
380 
381  markRegUsedInInstr(PhysReg);
382  switch (PhysRegState[PhysReg]) {
383  case regDisabled:
384  break;
385  case regReserved:
386  PhysRegState[PhysReg] = regFree;
388  case regFree:
389  MO.setIsKill();
390  return;
391  default:
392  // The physreg was allocated to a virtual register. That means the value we
393  // wanted has been clobbered.
394  llvm_unreachable("Instruction uses an allocated register");
395  }
396 
397  // Maybe a superregister is reserved?
398  for (MCRegAliasIterator AI(PhysReg, TRI, false); AI.isValid(); ++AI) {
399  MCPhysReg Alias = *AI;
400  switch (PhysRegState[Alias]) {
401  case regDisabled:
402  break;
403  case regReserved:
404  // Either PhysReg is a subregister of Alias and we mark the
405  // whole register as free, or PhysReg is the superregister of
406  // Alias and we mark all the aliases as disabled before freeing
407  // PhysReg.
408  // In the latter case, since PhysReg was disabled, this means that
409  // its value is defined only by physical sub-registers. This check
410  // is performed by the assert of the default case in this loop.
411  // Note: The value of the superregister may only be partial
412  // defined, that is why regDisabled is a valid state for aliases.
413  assert((TRI->isSuperRegister(PhysReg, Alias) ||
414  TRI->isSuperRegister(Alias, PhysReg)) &&
415  "Instruction is not using a subregister of a reserved register");
417  case regFree:
418  if (TRI->isSuperRegister(PhysReg, Alias)) {
419  // Leave the superregister in the working set.
420  PhysRegState[Alias] = regFree;
421  MO.getParent()->addRegisterKilled(Alias, TRI, true);
422  return;
423  }
424  // Some other alias was in the working set - clear it.
425  PhysRegState[Alias] = regDisabled;
426  break;
427  default:
428  llvm_unreachable("Instruction uses an alias of an allocated register");
429  }
430  }
431 
432  // All aliases are disabled, bring register into working set.
433  PhysRegState[PhysReg] = regFree;
434  MO.setIsKill();
435 }
436 
437 /// Mark PhysReg as reserved or free after spilling any virtregs. This is very
438 /// similar to defineVirtReg except the physreg is reserved instead of
439 /// allocated.
440 void RegAllocFast::definePhysReg(MachineBasicBlock::iterator MI,
441  MCPhysReg PhysReg, RegState NewState) {
442  markRegUsedInInstr(PhysReg);
443  switch (unsigned VirtReg = PhysRegState[PhysReg]) {
444  case regDisabled:
445  break;
446  default:
447  spillVirtReg(MI, VirtReg);
449  case regFree:
450  case regReserved:
451  PhysRegState[PhysReg] = NewState;
452  return;
453  }
454 
455  // This is a disabled register, disable all aliases.
456  PhysRegState[PhysReg] = NewState;
457  for (MCRegAliasIterator AI(PhysReg, TRI, false); AI.isValid(); ++AI) {
458  MCPhysReg Alias = *AI;
459  switch (unsigned VirtReg = PhysRegState[Alias]) {
460  case regDisabled:
461  break;
462  default:
463  spillVirtReg(MI, VirtReg);
465  case regFree:
466  case regReserved:
467  PhysRegState[Alias] = regDisabled;
468  if (TRI->isSuperRegister(PhysReg, Alias))
469  return;
470  break;
471  }
472  }
473 }
474 
475 /// Return the cost of spilling clearing out PhysReg and aliases so it is
476 /// free for allocation. Returns 0 when PhysReg is free or disabled with all
477 /// aliases disabled - it can be allocated directly.
478 /// \returns spillImpossible when PhysReg or an alias can't be spilled.
479 unsigned RegAllocFast::calcSpillCost(MCPhysReg PhysReg) const {
480  if (isRegUsedInInstr(PhysReg)) {
481  LLVM_DEBUG(dbgs() << printReg(PhysReg, TRI)
482  << " is already used in instr.\n");
483  return spillImpossible;
484  }
485  switch (unsigned VirtReg = PhysRegState[PhysReg]) {
486  case regDisabled:
487  break;
488  case regFree:
489  return 0;
490  case regReserved:
491  LLVM_DEBUG(dbgs() << printReg(VirtReg, TRI) << " corresponding "
492  << printReg(PhysReg, TRI) << " is reserved already.\n");
493  return spillImpossible;
494  default: {
495  LiveRegMap::const_iterator I = findLiveVirtReg(VirtReg);
496  assert(I != LiveVirtRegs.end() && "Missing VirtReg entry");
497  return I->Dirty ? spillDirty : spillClean;
498  }
499  }
500 
501  // This is a disabled register, add up cost of aliases.
502  LLVM_DEBUG(dbgs() << printReg(PhysReg, TRI) << " is disabled.\n");
503  unsigned Cost = 0;
504  for (MCRegAliasIterator AI(PhysReg, TRI, false); AI.isValid(); ++AI) {
505  MCPhysReg Alias = *AI;
506  switch (unsigned VirtReg = PhysRegState[Alias]) {
507  case regDisabled:
508  break;
509  case regFree:
510  ++Cost;
511  break;
512  case regReserved:
513  return spillImpossible;
514  default: {
515  LiveRegMap::const_iterator I = findLiveVirtReg(VirtReg);
516  assert(I != LiveVirtRegs.end() && "Missing VirtReg entry");
517  Cost += I->Dirty ? spillDirty : spillClean;
518  break;
519  }
520  }
521  }
522  return Cost;
523 }
524 
525 /// This method updates local state so that we know that PhysReg is the
526 /// proper container for VirtReg now. The physical register must not be used
527 /// for anything else when this is called.
528 void RegAllocFast::assignVirtToPhysReg(LiveReg &LR, MCPhysReg PhysReg) {
529  LLVM_DEBUG(dbgs() << "Assigning " << printReg(LR.VirtReg, TRI) << " to "
530  << printReg(PhysReg, TRI) << "\n");
531  PhysRegState[PhysReg] = LR.VirtReg;
532  assert(!LR.PhysReg && "Already assigned a physreg");
533  LR.PhysReg = PhysReg;
534 }
535 
537 RegAllocFast::assignVirtToPhysReg(unsigned VirtReg, MCPhysReg PhysReg) {
538  LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg);
539  assert(LRI != LiveVirtRegs.end() && "VirtReg disappeared");
540  assignVirtToPhysReg(*LRI, PhysReg);
541  return LRI;
542 }
543 
544 /// Allocates a physical register for VirtReg.
545 RegAllocFast::LiveRegMap::iterator RegAllocFast::allocVirtReg(MachineInstr &MI,
546  LiveRegMap::iterator LRI, unsigned Hint) {
547  const unsigned VirtReg = LRI->VirtReg;
548 
550  "Can only allocate virtual registers");
551 
552  // Take hint when possible.
553  const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);
555  MRI->isAllocatable(Hint) && RC.contains(Hint)) {
556  // Ignore the hint if we would have to spill a dirty register.
557  unsigned Cost = calcSpillCost(Hint);
558  if (Cost < spillDirty) {
559  if (Cost)
560  definePhysReg(MI, Hint, regFree);
561  // definePhysReg may kill virtual registers and modify LiveVirtRegs.
562  // That invalidates LRI, so run a new lookup for VirtReg.
563  return assignVirtToPhysReg(VirtReg, Hint);
564  }
565  }
566 
567  // First try to find a completely free register.
568  ArrayRef<MCPhysReg> AO = RegClassInfo.getOrder(&RC);
569  for (MCPhysReg PhysReg : AO) {
570  if (PhysRegState[PhysReg] == regFree && !isRegUsedInInstr(PhysReg)) {
571  assignVirtToPhysReg(*LRI, PhysReg);
572  return LRI;
573  }
574  }
575 
576  LLVM_DEBUG(dbgs() << "Allocating " << printReg(VirtReg) << " from "
577  << TRI->getRegClassName(&RC) << "\n");
578 
579  unsigned BestReg = 0;
580  unsigned BestCost = spillImpossible;
581  for (MCPhysReg PhysReg : AO) {
582  unsigned Cost = calcSpillCost(PhysReg);
583  LLVM_DEBUG(dbgs() << "\tRegister: " << printReg(PhysReg, TRI) << "\n");
584  LLVM_DEBUG(dbgs() << "\tCost: " << Cost << "\n");
585  LLVM_DEBUG(dbgs() << "\tBestCost: " << BestCost << "\n");
586  // Cost is 0 when all aliases are already disabled.
587  if (Cost == 0) {
588  assignVirtToPhysReg(*LRI, PhysReg);
589  return LRI;
590  }
591  if (Cost < BestCost)
592  BestReg = PhysReg, BestCost = Cost;
593  }
594 
595  if (BestReg) {
596  definePhysReg(MI, BestReg, regFree);
597  // definePhysReg may kill virtual registers and modify LiveVirtRegs.
598  // That invalidates LRI, so run a new lookup for VirtReg.
599  return assignVirtToPhysReg(VirtReg, BestReg);
600  }
601 
602  // Nothing we can do. Report an error and keep going with a bad allocation.
603  if (MI.isInlineAsm())
604  MI.emitError("inline assembly requires more registers than available");
605  else
606  MI.emitError("ran out of registers during register allocation");
607  definePhysReg(MI, *AO.begin(), regFree);
608  return assignVirtToPhysReg(VirtReg, *AO.begin());
609 }
610 
611 /// Allocates a register for VirtReg and mark it as dirty.
612 RegAllocFast::LiveRegMap::iterator RegAllocFast::defineVirtReg(MachineInstr &MI,
613  unsigned OpNum,
614  unsigned VirtReg,
615  unsigned Hint) {
617  "Not a virtual register");
618  LiveRegMap::iterator LRI;
619  bool New;
620  std::tie(LRI, New) = LiveVirtRegs.insert(LiveReg(VirtReg));
621  if (New) {
622  // If there is no hint, peek at the only use of this register.
623  if ((!Hint || !TargetRegisterInfo::isPhysicalRegister(Hint)) &&
624  MRI->hasOneNonDBGUse(VirtReg)) {
625  const MachineInstr &UseMI = *MRI->use_instr_nodbg_begin(VirtReg);
626  // It's a copy, use the destination register as a hint.
627  if (UseMI.isCopyLike())
628  Hint = UseMI.getOperand(0).getReg();
629  }
630  LRI = allocVirtReg(MI, LRI, Hint);
631  } else if (LRI->LastUse) {
632  // Redefining a live register - kill at the last use, unless it is this
633  // instruction defining VirtReg multiple times.
634  if (LRI->LastUse != &MI || LRI->LastUse->getOperand(LRI->LastOpNum).isUse())
635  addKillFlag(*LRI);
636  }
637  assert(LRI->PhysReg && "Register not assigned");
638  LRI->LastUse = &MI;
639  LRI->LastOpNum = OpNum;
640  LRI->Dirty = true;
641  markRegUsedInInstr(LRI->PhysReg);
642  return LRI;
643 }
644 
645 /// Make sure VirtReg is available in a physreg and return it.
646 RegAllocFast::LiveRegMap::iterator RegAllocFast::reloadVirtReg(MachineInstr &MI,
647  unsigned OpNum,
648  unsigned VirtReg,
649  unsigned Hint) {
651  "Not a virtual register");
652  LiveRegMap::iterator LRI;
653  bool New;
654  std::tie(LRI, New) = LiveVirtRegs.insert(LiveReg(VirtReg));
655  MachineOperand &MO = MI.getOperand(OpNum);
656  if (New) {
657  LRI = allocVirtReg(MI, LRI, Hint);
658  const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);
659  int FrameIndex = getStackSpaceFor(VirtReg, RC);
660  LLVM_DEBUG(dbgs() << "Reloading " << printReg(VirtReg, TRI) << " into "
661  << printReg(LRI->PhysReg, TRI) << "\n");
662  TII->loadRegFromStackSlot(*MBB, MI, LRI->PhysReg, FrameIndex, &RC, TRI);
663  ++NumLoads;
664  } else if (LRI->Dirty) {
665  if (isLastUseOfLocalReg(MO)) {
666  LLVM_DEBUG(dbgs() << "Killing last use: " << MO << "\n");
667  if (MO.isUse())
668  MO.setIsKill();
669  else
670  MO.setIsDead();
671  } else if (MO.isKill()) {
672  LLVM_DEBUG(dbgs() << "Clearing dubious kill: " << MO << "\n");
673  MO.setIsKill(false);
674  } else if (MO.isDead()) {
675  LLVM_DEBUG(dbgs() << "Clearing dubious dead: " << MO << "\n");
676  MO.setIsDead(false);
677  }
678  } else if (MO.isKill()) {
679  // We must remove kill flags from uses of reloaded registers because the
680  // register would be killed immediately, and there might be a second use:
681  // %foo = OR killed %x, %x
682  // This would cause a second reload of %x into a different register.
683  LLVM_DEBUG(dbgs() << "Clearing clean kill: " << MO << "\n");
684  MO.setIsKill(false);
685  } else if (MO.isDead()) {
686  LLVM_DEBUG(dbgs() << "Clearing clean dead: " << MO << "\n");
687  MO.setIsDead(false);
688  }
689  assert(LRI->PhysReg && "Register not assigned");
690  LRI->LastUse = &MI;
691  LRI->LastOpNum = OpNum;
692  markRegUsedInInstr(LRI->PhysReg);
693  return LRI;
694 }
695 
696 /// Changes operand OpNum in MI the refer the PhysReg, considering subregs. This
697 /// may invalidate any operand pointers. Return true if the operand kills its
698 /// register.
699 bool RegAllocFast::setPhysReg(MachineInstr &MI, unsigned OpNum,
700  MCPhysReg PhysReg) {
701  MachineOperand &MO = MI.getOperand(OpNum);
702  bool Dead = MO.isDead();
703  if (!MO.getSubReg()) {
704  MO.setReg(PhysReg);
705  MO.setIsRenamable(true);
706  return MO.isKill() || Dead;
707  }
708 
709  // Handle subregister index.
710  MO.setReg(PhysReg ? TRI->getSubReg(PhysReg, MO.getSubReg()) : 0);
711  MO.setIsRenamable(true);
712  MO.setSubReg(0);
713 
714  // A kill flag implies killing the full register. Add corresponding super
715  // register kill.
716  if (MO.isKill()) {
717  MI.addRegisterKilled(PhysReg, TRI, true);
718  return true;
719  }
720 
721  // A <def,read-undef> of a sub-register requires an implicit def of the full
722  // register.
723  if (MO.isDef() && MO.isUndef())
724  MI.addRegisterDefined(PhysReg, TRI);
725 
726  return Dead;
727 }
728 
729 // Handles special instruction operand like early clobbers and tied ops when
730 // there are additional physreg defines.
731 void RegAllocFast::handleThroughOperands(MachineInstr &MI,
732  SmallVectorImpl<unsigned> &VirtDead) {
733  LLVM_DEBUG(dbgs() << "Scanning for through registers:");
734  SmallSet<unsigned, 8> ThroughRegs;
735  for (const MachineOperand &MO : MI.operands()) {
736  if (!MO.isReg()) continue;
737  unsigned Reg = MO.getReg();
739  continue;
740  if (MO.isEarlyClobber() || (MO.isUse() && MO.isTied()) ||
741  (MO.getSubReg() && MI.readsVirtualRegister(Reg))) {
742  if (ThroughRegs.insert(Reg).second)
743  LLVM_DEBUG(dbgs() << ' ' << printReg(Reg));
744  }
745  }
746 
747  // If any physreg defines collide with preallocated through registers,
748  // we must spill and reallocate.
749  LLVM_DEBUG(dbgs() << "\nChecking for physdef collisions.\n");
750  for (const MachineOperand &MO : MI.operands()) {
751  if (!MO.isReg() || !MO.isDef()) continue;
752  unsigned Reg = MO.getReg();
753  if (!Reg || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue;
754  markRegUsedInInstr(Reg);
755  for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) {
756  if (ThroughRegs.count(PhysRegState[*AI]))
757  definePhysReg(MI, *AI, regFree);
758  }
759  }
760 
761  SmallVector<unsigned, 8> PartialDefs;
762  LLVM_DEBUG(dbgs() << "Allocating tied uses.\n");
763  for (unsigned I = 0, E = MI.getNumOperands(); I != E; ++I) {
764  const MachineOperand &MO = MI.getOperand(I);
765  if (!MO.isReg()) continue;
766  unsigned Reg = MO.getReg();
767  if (!TargetRegisterInfo::isVirtualRegister(Reg)) continue;
768  if (MO.isUse()) {
769  if (!MO.isTied()) continue;
770  LLVM_DEBUG(dbgs() << "Operand " << I << "(" << MO
771  << ") is tied to operand " << MI.findTiedOperandIdx(I)
772  << ".\n");
773  LiveRegMap::iterator LRI = reloadVirtReg(MI, I, Reg, 0);
774  MCPhysReg PhysReg = LRI->PhysReg;
775  setPhysReg(MI, I, PhysReg);
776  // Note: we don't update the def operand yet. That would cause the normal
777  // def-scan to attempt spilling.
778  } else if (MO.getSubReg() && MI.readsVirtualRegister(Reg)) {
779  LLVM_DEBUG(dbgs() << "Partial redefine: " << MO << "\n");
780  // Reload the register, but don't assign to the operand just yet.
781  // That would confuse the later phys-def processing pass.
782  LiveRegMap::iterator LRI = reloadVirtReg(MI, I, Reg, 0);
783  PartialDefs.push_back(LRI->PhysReg);
784  }
785  }
786 
787  LLVM_DEBUG(dbgs() << "Allocating early clobbers.\n");
788  for (unsigned I = 0, E = MI.getNumOperands(); I != E; ++I) {
789  const MachineOperand &MO = MI.getOperand(I);
790  if (!MO.isReg()) continue;
791  unsigned Reg = MO.getReg();
792  if (!TargetRegisterInfo::isVirtualRegister(Reg)) continue;
793  if (!MO.isEarlyClobber())
794  continue;
795  // Note: defineVirtReg may invalidate MO.
796  LiveRegMap::iterator LRI = defineVirtReg(MI, I, Reg, 0);
797  MCPhysReg PhysReg = LRI->PhysReg;
798  if (setPhysReg(MI, I, PhysReg))
799  VirtDead.push_back(Reg);
800  }
801 
802  // Restore UsedInInstr to a state usable for allocating normal virtual uses.
803  UsedInInstr.clear();
804  for (const MachineOperand &MO : MI.operands()) {
805  if (!MO.isReg() || (MO.isDef() && !MO.isEarlyClobber())) continue;
806  unsigned Reg = MO.getReg();
807  if (!Reg || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue;
808  LLVM_DEBUG(dbgs() << "\tSetting " << printReg(Reg, TRI)
809  << " as used in instr\n");
810  markRegUsedInInstr(Reg);
811  }
812 
813  // Also mark PartialDefs as used to avoid reallocation.
814  for (unsigned PartialDef : PartialDefs)
815  markRegUsedInInstr(PartialDef);
816 }
817 
818 #ifndef NDEBUG
819 void RegAllocFast::dumpState() {
820  for (unsigned Reg = 1, E = TRI->getNumRegs(); Reg != E; ++Reg) {
821  if (PhysRegState[Reg] == regDisabled) continue;
822  dbgs() << " " << printReg(Reg, TRI);
823  switch(PhysRegState[Reg]) {
824  case regFree:
825  break;
826  case regReserved:
827  dbgs() << "*";
828  break;
829  default: {
830  dbgs() << '=' << printReg(PhysRegState[Reg]);
831  LiveRegMap::iterator I = findLiveVirtReg(PhysRegState[Reg]);
832  assert(I != LiveVirtRegs.end() && "Missing VirtReg entry");
833  if (I->Dirty)
834  dbgs() << "*";
835  assert(I->PhysReg == Reg && "Bad inverse map");
836  break;
837  }
838  }
839  }
840  dbgs() << '\n';
841  // Check that LiveVirtRegs is the inverse.
842  for (LiveRegMap::iterator i = LiveVirtRegs.begin(),
843  e = LiveVirtRegs.end(); i != e; ++i) {
845  "Bad map key");
847  "Bad map value");
848  assert(PhysRegState[i->PhysReg] == i->VirtReg && "Bad inverse map");
849  }
850 }
851 #endif
852 
853 void RegAllocFast::allocateBasicBlock(MachineBasicBlock &MBB) {
854  this->MBB = &MBB;
855  LLVM_DEBUG(dbgs() << "\nAllocating " << MBB);
856 
857  PhysRegState.assign(TRI->getNumRegs(), regDisabled);
858  assert(LiveVirtRegs.empty() && "Mapping not cleared from last block?");
859 
861 
862  // Add live-in registers as live.
863  for (const MachineBasicBlock::RegisterMaskPair LI : MBB.liveins())
864  if (MRI->isAllocatable(LI.PhysReg))
865  definePhysReg(MII, LI.PhysReg, regReserved);
866 
867  VirtDead.clear();
868  Coalesced.clear();
869 
870  // Otherwise, sequentially allocate each instruction in the MBB.
871  for (MachineInstr &MI : MBB) {
872  const MCInstrDesc &MCID = MI.getDesc();
873  LLVM_DEBUG(dbgs() << "\n>> " << MI << "Regs:"; dumpState());
874 
875  // Debug values are not allowed to change codegen in any way.
876  if (MI.isDebugValue()) {
877  MachineInstr *DebugMI = &MI;
878  MachineOperand &MO = DebugMI->getOperand(0);
879 
880  // Ignore DBG_VALUEs that aren't based on virtual registers. These are
881  // mostly constants and frame indices.
882  if (!MO.isReg())
883  continue;
884  unsigned Reg = MO.getReg();
886  continue;
887 
888  // See if this virtual register has already been allocated to a physical
889  // register or spilled to a stack slot.
890  LiveRegMap::iterator LRI = findLiveVirtReg(Reg);
891  if (LRI != LiveVirtRegs.end())
892  setPhysReg(*DebugMI, 0, LRI->PhysReg);
893  else {
894  int SS = StackSlotForVirtReg[Reg];
895  if (SS != -1) {
896  // Modify DBG_VALUE now that the value is in a spill slot.
897  updateDbgValueForSpill(*DebugMI, SS);
898  LLVM_DEBUG(dbgs() << "Modifying debug info due to spill:"
899  << "\t" << *DebugMI);
900  continue;
901  }
902 
903  // We can't allocate a physreg for a DebugValue, sorry!
904  LLVM_DEBUG(dbgs() << "Unable to allocate vreg used by DBG_VALUE");
905  MO.setReg(0);
906  }
907 
908  // If Reg hasn't been spilled, put this DBG_VALUE in LiveDbgValueMap so
909  // that future spills of Reg will have DBG_VALUEs.
910  LiveDbgValueMap[Reg].push_back(DebugMI);
911  continue;
912  }
913 
914  if (MI.isDebugLabel())
915  continue;
916 
917  // If this is a copy, we may be able to coalesce.
918  unsigned CopySrcReg = 0;
919  unsigned CopyDstReg = 0;
920  unsigned CopySrcSub = 0;
921  unsigned CopyDstSub = 0;
922  if (MI.isCopy()) {
923  CopyDstReg = MI.getOperand(0).getReg();
924  CopySrcReg = MI.getOperand(1).getReg();
925  CopyDstSub = MI.getOperand(0).getSubReg();
926  CopySrcSub = MI.getOperand(1).getSubReg();
927  }
928 
929  // Track registers used by instruction.
930  UsedInInstr.clear();
931 
932  // First scan.
933  // Mark physreg uses and early clobbers as used.
934  // Find the end of the virtreg operands
935  unsigned VirtOpEnd = 0;
936  bool hasTiedOps = false;
937  bool hasEarlyClobbers = false;
938  bool hasPartialRedefs = false;
939  bool hasPhysDefs = false;
940  for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
941  MachineOperand &MO = MI.getOperand(i);
942  // Make sure MRI knows about registers clobbered by regmasks.
943  if (MO.isRegMask()) {
945  continue;
946  }
947  if (!MO.isReg()) continue;
948  unsigned Reg = MO.getReg();
949  if (!Reg) continue;
951  VirtOpEnd = i+1;
952  if (MO.isUse()) {
953  hasTiedOps = hasTiedOps ||
954  MCID.getOperandConstraint(i, MCOI::TIED_TO) != -1;
955  } else {
956  if (MO.isEarlyClobber())
957  hasEarlyClobbers = true;
958  if (MO.getSubReg() && MI.readsVirtualRegister(Reg))
959  hasPartialRedefs = true;
960  }
961  continue;
962  }
963  if (!MRI->isAllocatable(Reg)) continue;
964  if (MO.isUse()) {
965  usePhysReg(MO);
966  } else if (MO.isEarlyClobber()) {
967  definePhysReg(MI, Reg,
968  (MO.isImplicit() || MO.isDead()) ? regFree : regReserved);
969  hasEarlyClobbers = true;
970  } else
971  hasPhysDefs = true;
972  }
973 
974  // The instruction may have virtual register operands that must be allocated
975  // the same register at use-time and def-time: early clobbers and tied
976  // operands. If there are also physical defs, these registers must avoid
977  // both physical defs and uses, making them more constrained than normal
978  // operands.
979  // Similarly, if there are multiple defs and tied operands, we must make
980  // sure the same register is allocated to uses and defs.
981  // We didn't detect inline asm tied operands above, so just make this extra
982  // pass for all inline asm.
983  if (MI.isInlineAsm() || hasEarlyClobbers || hasPartialRedefs ||
984  (hasTiedOps && (hasPhysDefs || MCID.getNumDefs() > 1))) {
985  handleThroughOperands(MI, VirtDead);
986  // Don't attempt coalescing when we have funny stuff going on.
987  CopyDstReg = 0;
988  // Pretend we have early clobbers so the use operands get marked below.
989  // This is not necessary for the common case of a single tied use.
990  hasEarlyClobbers = true;
991  }
992 
993  // Second scan.
994  // Allocate virtreg uses.
995  for (unsigned I = 0; I != VirtOpEnd; ++I) {
996  const MachineOperand &MO = MI.getOperand(I);
997  if (!MO.isReg()) continue;
998  unsigned Reg = MO.getReg();
999  if (!TargetRegisterInfo::isVirtualRegister(Reg)) continue;
1000  if (MO.isUse()) {
1001  LiveRegMap::iterator LRI = reloadVirtReg(MI, I, Reg, CopyDstReg);
1002  MCPhysReg PhysReg = LRI->PhysReg;
1003  CopySrcReg = (CopySrcReg == Reg || CopySrcReg == PhysReg) ? PhysReg : 0;
1004  if (setPhysReg(MI, I, PhysReg))
1005  killVirtReg(LRI);
1006  }
1007  }
1008 
1009  // Track registers defined by instruction - early clobbers and tied uses at
1010  // this point.
1011  UsedInInstr.clear();
1012  if (hasEarlyClobbers) {
1013  for (const MachineOperand &MO : MI.operands()) {
1014  if (!MO.isReg()) continue;
1015  unsigned Reg = MO.getReg();
1016  if (!Reg || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue;
1017  // Look for physreg defs and tied uses.
1018  if (!MO.isDef() && !MO.isTied()) continue;
1019  markRegUsedInInstr(Reg);
1020  }
1021  }
1022 
1023  unsigned DefOpEnd = MI.getNumOperands();
1024  if (MI.isCall()) {
1025  // Spill all virtregs before a call. This serves one purpose: If an
1026  // exception is thrown, the landing pad is going to expect to find
1027  // registers in their spill slots.
1028  // Note: although this is appealing to just consider all definitions
1029  // as call-clobbered, this is not correct because some of those
1030  // definitions may be used later on and we do not want to reuse
1031  // those for virtual registers in between.
1032  LLVM_DEBUG(dbgs() << " Spilling remaining registers before call.\n");
1033  spillAll(MI);
1034  }
1035 
1036  // Third scan.
1037  // Allocate defs and collect dead defs.
1038  for (unsigned I = 0; I != DefOpEnd; ++I) {
1039  const MachineOperand &MO = MI.getOperand(I);
1040  if (!MO.isReg() || !MO.isDef() || !MO.getReg() || MO.isEarlyClobber())
1041  continue;
1042  unsigned Reg = MO.getReg();
1043 
1045  if (!MRI->isAllocatable(Reg)) continue;
1046  definePhysReg(MI, Reg, MO.isDead() ? regFree : regReserved);
1047  continue;
1048  }
1049  LiveRegMap::iterator LRI = defineVirtReg(MI, I, Reg, CopySrcReg);
1050  MCPhysReg PhysReg = LRI->PhysReg;
1051  if (setPhysReg(MI, I, PhysReg)) {
1052  VirtDead.push_back(Reg);
1053  CopyDstReg = 0; // cancel coalescing;
1054  } else
1055  CopyDstReg = (CopyDstReg == Reg || CopyDstReg == PhysReg) ? PhysReg : 0;
1056  }
1057 
1058  // Kill dead defs after the scan to ensure that multiple defs of the same
1059  // register are allocated identically. We didn't need to do this for uses
1060  // because we are crerating our own kill flags, and they are always at the
1061  // last use.
1062  for (unsigned VirtReg : VirtDead)
1063  killVirtReg(VirtReg);
1064  VirtDead.clear();
1065 
1066  if (CopyDstReg && CopyDstReg == CopySrcReg && CopyDstSub == CopySrcSub) {
1067  LLVM_DEBUG(dbgs() << "-- coalescing: " << MI);
1068  Coalesced.push_back(&MI);
1069  } else {
1070  LLVM_DEBUG(dbgs() << "<< " << MI);
1071  }
1072  }
1073 
1074  // Spill all physical registers holding virtual registers now.
1075  LLVM_DEBUG(dbgs() << "Spilling live registers at end of block.\n");
1076  spillAll(MBB.getFirstTerminator());
1077 
1078  // Erase all the coalesced copies. We are delaying it until now because
1079  // LiveVirtRegs might refer to the instrs.
1080  for (MachineInstr *MI : Coalesced)
1081  MBB.erase(MI);
1082  NumCopies += Coalesced.size();
1083 
1084  LLVM_DEBUG(MBB.dump());
1085 }
1086 
1087 /// Allocates registers for a function.
1088 bool RegAllocFast::runOnMachineFunction(MachineFunction &MF) {
1089  LLVM_DEBUG(dbgs() << "********** FAST REGISTER ALLOCATION **********\n"
1090  << "********** Function: " << MF.getName() << '\n');
1091  MRI = &MF.getRegInfo();
1092  const TargetSubtargetInfo &STI = MF.getSubtarget();
1093  TRI = STI.getRegisterInfo();
1094  TII = STI.getInstrInfo();
1095  MFI = &MF.getFrameInfo();
1096  MRI->freezeReservedRegs(MF);
1097  RegClassInfo.runOnMachineFunction(MF);
1098  UsedInInstr.clear();
1099  UsedInInstr.setUniverse(TRI->getNumRegUnits());
1100 
1101  // initialize the virtual->physical register map to have a 'null'
1102  // mapping for all virtual registers
1103  unsigned NumVirtRegs = MRI->getNumVirtRegs();
1104  StackSlotForVirtReg.resize(NumVirtRegs);
1105  LiveVirtRegs.setUniverse(NumVirtRegs);
1106 
1107  // Loop over all of the basic blocks, eliminating virtual register references
1108  for (MachineBasicBlock &MBB : MF)
1109  allocateBasicBlock(MBB);
1110 
1111  // All machine operands and other references to virtual registers have been
1112  // replaced. Remove the virtual registers.
1113  MRI->clearVirtRegs();
1114 
1115  StackSlotForVirtReg.clear();
1116  LiveDbgValueMap.clear();
1117  return true;
1118 }
1119 
1121  return new RegAllocFast();
1122 }
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:213
constexpr char Align[]
Key for Kernel::Arg::Metadata::mAlign.
bool isDebugLabel() const
Definition: MachineInstr.h:850
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:485
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:250
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:161
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.
unsigned Reg
This file contains the declarations for metadata subclasses.
unsigned getSubReg() const
bool isInlineAsm() const
Definition: MachineInstr.h:867
STATISTIC(NumFunctions, "Total number of functions")
unsigned const TargetRegisterInfo * TRI
void setIsDead(bool Val=true)
reg_nodbg_iterator reg_nodbg_begin(unsigned RegNo) const
iterator_range< mop_iterator > operands()
Definition: MachineInstr.h:361
bool isCopyLike() const
Return true if the instruction behaves like a copy.
Definition: MachineInstr.h:906
void setIsRenamable(bool Val=true)
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:314
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:308
RegisterRegAlloc class - Track the registration of register allocators.
virtual const TargetInstrInfo * getInstrInfo() const
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...
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
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.
typename DenseT::iterator iterator
Definition: SparseSet.h:172
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:973
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:892
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:185
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:849
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:223
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:286
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
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:156
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:60
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:124
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
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
#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...
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