LLVM  14.0.0git
RegAllocFast.cpp
Go to the documentation of this file.
1 //===- RegAllocFast.cpp - A fast register allocator for debug code --------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 /// \file This register allocator allocates registers to a basic block at a
10 /// time, attempting to keep values in registers and reusing registers as
11 /// appropriate.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #include "llvm/ADT/ArrayRef.h"
16 #include "llvm/ADT/DenseMap.h"
17 #include "llvm/ADT/IndexedMap.h"
18 #include "llvm/ADT/MapVector.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/InitializePasses.h"
41 #include "llvm/MC/MCInstrDesc.h"
42 #include "llvm/MC/MCRegisterInfo.h"
43 #include "llvm/Pass.h"
44 #include "llvm/Support/Casting.h"
45 #include "llvm/Support/Compiler.h"
46 #include "llvm/Support/Debug.h"
49 #include <cassert>
50 #include <tuple>
51 #include <vector>
52 
53 using namespace llvm;
54 
55 #define DEBUG_TYPE "regalloc"
56 
57 STATISTIC(NumStores, "Number of stores added");
58 STATISTIC(NumLoads , "Number of loads added");
59 STATISTIC(NumCoalesced, "Number of copies coalesced");
60 
61 // FIXME: Remove this switch when all testcases are fixed!
62 static cl::opt<bool> IgnoreMissingDefs("rafast-ignore-missing-defs",
63  cl::Hidden);
64 
65 static RegisterRegAlloc
66  fastRegAlloc("fast", "fast register allocator", createFastRegisterAllocator);
67 
68 namespace {
69 
70  class RegAllocFast : public MachineFunctionPass {
71  public:
72  static char ID;
73 
74  RegAllocFast(const RegClassFilterFunc F = allocateAllRegClasses,
75  bool ClearVirtRegs_ = true) :
77  ShouldAllocateClass(F),
78  StackSlotForVirtReg(-1),
79  ClearVirtRegs(ClearVirtRegs_) {
80  }
81 
82  private:
83  MachineFrameInfo *MFI;
85  const TargetRegisterInfo *TRI;
86  const TargetInstrInfo *TII;
87  RegisterClassInfo RegClassInfo;
88  const RegClassFilterFunc ShouldAllocateClass;
89 
90  /// Basic block currently being allocated.
92 
93  /// Maps virtual regs to the frame index where these values are spilled.
94  IndexedMap<int, VirtReg2IndexFunctor> StackSlotForVirtReg;
95 
96  bool ClearVirtRegs;
97 
98  /// Everything we know about a live virtual register.
99  struct LiveReg {
100  MachineInstr *LastUse = nullptr; ///< Last instr to use reg.
101  Register VirtReg; ///< Virtual register number.
102  MCPhysReg PhysReg = 0; ///< Currently held here.
103  bool LiveOut = false; ///< Register is possibly live out.
104  bool Reloaded = false; ///< Register was reloaded.
105  bool Error = false; ///< Could not allocate.
106 
107  explicit LiveReg(Register VirtReg) : VirtReg(VirtReg) {}
108 
109  unsigned getSparseSetIndex() const {
110  return Register::virtReg2Index(VirtReg);
111  }
112  };
113 
114  using LiveRegMap = SparseSet<LiveReg>;
115  /// This map contains entries for each virtual register that is currently
116  /// available in a physical register.
117  LiveRegMap LiveVirtRegs;
118 
119  /// Stores assigned virtual registers present in the bundle MI.
120  DenseMap<Register, MCPhysReg> BundleVirtRegsMap;
121 
123  /// List of DBG_VALUE that we encountered without the vreg being assigned
124  /// because they were placed after the last use of the vreg.
126 
127  /// Has a bit set for every virtual register for which it was determined
128  /// that it is alive across blocks.
129  BitVector MayLiveAcrossBlocks;
130 
131  /// State of a register unit.
132  enum RegUnitState {
133  /// A free register is not currently in use and can be allocated
134  /// immediately without checking aliases.
135  regFree,
136 
137  /// A pre-assigned register has been assigned before register allocation
138  /// (e.g., setting up a call parameter).
139  regPreAssigned,
140 
141  /// Used temporarily in reloadAtBegin() to mark register units that are
142  /// live-in to the basic block.
143  regLiveIn,
144 
145  /// A register state may also be a virtual register number, indication
146  /// that the physical register is currently allocated to a virtual
147  /// register. In that case, LiveVirtRegs contains the inverse mapping.
148  };
149 
150  /// Maps each physical register to a RegUnitState enum or virtual register.
151  std::vector<unsigned> RegUnitStates;
152 
154 
155  using RegUnitSet = SparseSet<uint16_t, identity<uint16_t>>;
156  /// Set of register units that are used in the current instruction, and so
157  /// cannot be allocated.
158  RegUnitSet UsedInInstr;
159  RegUnitSet PhysRegUses;
160  SmallVector<uint16_t, 8> DefOperandIndexes;
161  // Register masks attached to the current instruction.
163 
164  void setPhysRegState(MCPhysReg PhysReg, unsigned NewState);
165  bool isPhysRegFree(MCPhysReg PhysReg) const;
166 
167  /// Mark a physreg as used in this instruction.
168  void markRegUsedInInstr(MCPhysReg PhysReg) {
169  for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units)
170  UsedInInstr.insert(*Units);
171  }
172 
173  // Check if physreg is clobbered by instruction's regmask(s).
174  bool isClobberedByRegMasks(MCPhysReg PhysReg) const {
175  return llvm::any_of(RegMasks, [PhysReg](const uint32_t *Mask) {
176  return MachineOperand::clobbersPhysReg(Mask, PhysReg);
177  });
178  }
179 
180  /// Check if a physreg or any of its aliases are used in this instruction.
181  bool isRegUsedInInstr(MCPhysReg PhysReg, bool LookAtPhysRegUses) const {
182  if (LookAtPhysRegUses && isClobberedByRegMasks(PhysReg))
183  return true;
184  for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
185  if (UsedInInstr.count(*Units))
186  return true;
187  if (LookAtPhysRegUses && PhysRegUses.count(*Units))
188  return true;
189  }
190  return false;
191  }
192 
193  /// Mark physical register as being used in a register use operand.
194  /// This is only used by the special livethrough handling code.
195  void markPhysRegUsedInInstr(MCPhysReg PhysReg) {
196  for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units)
197  PhysRegUses.insert(*Units);
198  }
199 
200  /// Remove mark of physical register being used in the instruction.
201  void unmarkRegUsedInInstr(MCPhysReg PhysReg) {
202  for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units)
203  UsedInInstr.erase(*Units);
204  }
205 
206  enum : unsigned {
207  spillClean = 50,
208  spillDirty = 100,
209  spillPrefBonus = 20,
210  spillImpossible = ~0u
211  };
212 
213  public:
214  StringRef getPassName() const override { return "Fast Register Allocator"; }
215 
216  void getAnalysisUsage(AnalysisUsage &AU) const override {
217  AU.setPreservesCFG();
219  }
220 
221  MachineFunctionProperties getRequiredProperties() const override {
224  }
225 
226  MachineFunctionProperties getSetProperties() const override {
227  if (ClearVirtRegs) {
230  }
231 
232  return MachineFunctionProperties();
233  }
234 
235  MachineFunctionProperties getClearedProperties() const override {
238  }
239 
240  private:
241  bool runOnMachineFunction(MachineFunction &MF) override;
242 
243  void allocateBasicBlock(MachineBasicBlock &MBB);
244 
245  void addRegClassDefCounts(std::vector<unsigned> &RegClassDefCounts,
246  Register Reg) const;
247 
248  void allocateInstruction(MachineInstr &MI);
249  void handleDebugValue(MachineInstr &MI);
250  void handleBundle(MachineInstr &MI);
251 
252  bool usePhysReg(MachineInstr &MI, MCPhysReg PhysReg);
253  bool definePhysReg(MachineInstr &MI, MCPhysReg PhysReg);
254  bool displacePhysReg(MachineInstr &MI, MCPhysReg PhysReg);
255  void freePhysReg(MCPhysReg PhysReg);
256 
257  unsigned calcSpillCost(MCPhysReg PhysReg) const;
258 
259  LiveRegMap::iterator findLiveVirtReg(Register VirtReg) {
260  return LiveVirtRegs.find(Register::virtReg2Index(VirtReg));
261  }
262 
263  LiveRegMap::const_iterator findLiveVirtReg(Register VirtReg) const {
264  return LiveVirtRegs.find(Register::virtReg2Index(VirtReg));
265  }
266 
267  void assignVirtToPhysReg(MachineInstr &MI, LiveReg &, MCPhysReg PhysReg);
268  void allocVirtReg(MachineInstr &MI, LiveReg &LR, Register Hint,
269  bool LookAtPhysRegUses = false);
270  void allocVirtRegUndef(MachineOperand &MO);
271  void assignDanglingDebugValues(MachineInstr &Def, Register VirtReg,
272  MCPhysReg Reg);
273  void defineLiveThroughVirtReg(MachineInstr &MI, unsigned OpNum,
274  Register VirtReg);
275  void defineVirtReg(MachineInstr &MI, unsigned OpNum, Register VirtReg,
276  bool LookAtPhysRegUses = false);
277  void useVirtReg(MachineInstr &MI, unsigned OpNum, Register VirtReg);
278 
280  getMBBBeginInsertionPoint(MachineBasicBlock &MBB,
281  SmallSet<Register, 2> &PrologLiveIns) const;
282 
283  void reloadAtBegin(MachineBasicBlock &MBB);
284  void setPhysReg(MachineInstr &MI, MachineOperand &MO, MCPhysReg PhysReg);
285 
286  Register traceCopies(Register VirtReg) const;
287  Register traceCopyChain(Register Reg) const;
288 
289  int getStackSpaceFor(Register VirtReg);
290  void spill(MachineBasicBlock::iterator Before, Register VirtReg,
291  MCPhysReg AssignedReg, bool Kill, bool LiveOut);
292  void reload(MachineBasicBlock::iterator Before, Register VirtReg,
293  MCPhysReg PhysReg);
294 
295  bool mayLiveOut(Register VirtReg);
296  bool mayLiveIn(Register VirtReg);
297 
298  void dumpState() const;
299  };
300 
301 } // end anonymous namespace
302 
303 char RegAllocFast::ID = 0;
304 
305 INITIALIZE_PASS(RegAllocFast, "regallocfast", "Fast Register Allocator", false,
306  false)
307 
308 void RegAllocFast::setPhysRegState(MCPhysReg PhysReg, unsigned NewState) {
309  for (MCRegUnitIterator UI(PhysReg, TRI); UI.isValid(); ++UI)
310  RegUnitStates[*UI] = NewState;
311 }
312 
313 bool RegAllocFast::isPhysRegFree(MCPhysReg PhysReg) const {
314  for (MCRegUnitIterator UI(PhysReg, TRI); UI.isValid(); ++UI) {
315  if (RegUnitStates[*UI] != regFree)
316  return false;
317  }
318  return true;
319 }
320 
321 /// This allocates space for the specified virtual register to be held on the
322 /// stack.
323 int RegAllocFast::getStackSpaceFor(Register VirtReg) {
324  // Find the location Reg would belong...
325  int SS = StackSlotForVirtReg[VirtReg];
326  // Already has space allocated?
327  if (SS != -1)
328  return SS;
329 
330  // Allocate a new stack object for this spill location...
331  const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);
332  unsigned Size = TRI->getSpillSize(RC);
333  Align Alignment = TRI->getSpillAlign(RC);
334  int FrameIdx = MFI->CreateSpillStackObject(Size, Alignment);
335 
336  // Assign the slot.
337  StackSlotForVirtReg[VirtReg] = FrameIdx;
338  return FrameIdx;
339 }
340 
344  auto MBBEnd = MBB.end();
345  if (B == MBBEnd)
346  return true;
347 
349  for (; &*I != A && &*I != B; ++I)
350  ;
351 
352  return &*I == A;
353 }
354 
355 /// Returns false if \p VirtReg is known to not live out of the current block.
356 bool RegAllocFast::mayLiveOut(Register VirtReg) {
357  if (MayLiveAcrossBlocks.test(Register::virtReg2Index(VirtReg))) {
358  // Cannot be live-out if there are no successors.
359  return !MBB->succ_empty();
360  }
361 
362  const MachineInstr *SelfLoopDef = nullptr;
363 
364  // If this block loops back to itself, it is necessary to check whether the
365  // use comes after the def.
366  if (MBB->isSuccessor(MBB)) {
367  SelfLoopDef = MRI->getUniqueVRegDef(VirtReg);
368  if (!SelfLoopDef) {
369  MayLiveAcrossBlocks.set(Register::virtReg2Index(VirtReg));
370  return true;
371  }
372  }
373 
374  // See if the first \p Limit uses of the register are all in the current
375  // block.
376  static const unsigned Limit = 8;
377  unsigned C = 0;
378  for (const MachineInstr &UseInst : MRI->use_nodbg_instructions(VirtReg)) {
379  if (UseInst.getParent() != MBB || ++C >= Limit) {
380  MayLiveAcrossBlocks.set(Register::virtReg2Index(VirtReg));
381  // Cannot be live-out if there are no successors.
382  return !MBB->succ_empty();
383  }
384 
385  if (SelfLoopDef) {
386  // Try to handle some simple cases to avoid spilling and reloading every
387  // value inside a self looping block.
388  if (SelfLoopDef == &UseInst ||
389  !dominates(*MBB, SelfLoopDef->getIterator(), UseInst.getIterator())) {
390  MayLiveAcrossBlocks.set(Register::virtReg2Index(VirtReg));
391  return true;
392  }
393  }
394  }
395 
396  return false;
397 }
398 
399 /// Returns false if \p VirtReg is known to not be live into the current block.
400 bool RegAllocFast::mayLiveIn(Register VirtReg) {
401  if (MayLiveAcrossBlocks.test(Register::virtReg2Index(VirtReg)))
402  return !MBB->pred_empty();
403 
404  // See if the first \p Limit def of the register are all in the current block.
405  static const unsigned Limit = 8;
406  unsigned C = 0;
407  for (const MachineInstr &DefInst : MRI->def_instructions(VirtReg)) {
408  if (DefInst.getParent() != MBB || ++C >= Limit) {
409  MayLiveAcrossBlocks.set(Register::virtReg2Index(VirtReg));
410  return !MBB->pred_empty();
411  }
412  }
413 
414  return false;
415 }
416 
417 /// Insert spill instruction for \p AssignedReg before \p Before. Update
418 /// DBG_VALUEs with \p VirtReg operands with the stack slot.
420  MCPhysReg AssignedReg, bool Kill, bool LiveOut) {
421  LLVM_DEBUG(dbgs() << "Spilling " << printReg(VirtReg, TRI)
422  << " in " << printReg(AssignedReg, TRI));
423  int FI = getStackSpaceFor(VirtReg);
424  LLVM_DEBUG(dbgs() << " to stack slot #" << FI << '\n');
425 
426  const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);
427  TII->storeRegToStackSlot(*MBB, Before, AssignedReg, Kill, FI, &RC, TRI);
428  ++NumStores;
429 
431 
432  // When we spill a virtual register, we will have spill instructions behind
433  // every definition of it, meaning we can switch all the DBG_VALUEs over
434  // to just reference the stack slot.
435  SmallVectorImpl<MachineOperand *> &LRIDbgOperands = LiveDbgValueMap[VirtReg];
437  SpilledOperandsMap;
438  for (MachineOperand *MO : LRIDbgOperands)
439  SpilledOperandsMap[MO->getParent()].push_back(MO);
440  for (auto MISpilledOperands : SpilledOperandsMap) {
441  MachineInstr &DBG = *MISpilledOperands.first;
443  *MBB, Before, *MISpilledOperands.first, FI, MISpilledOperands.second);
444  assert(NewDV->getParent() == MBB && "dangling parent pointer");
445  (void)NewDV;
446  LLVM_DEBUG(dbgs() << "Inserting debug info due to spill:\n" << *NewDV);
447 
448  if (LiveOut) {
449  // We need to insert a DBG_VALUE at the end of the block if the spill slot
450  // is live out, but there is another use of the value after the
451  // spill. This will allow LiveDebugValues to see the correct live out
452  // value to propagate to the successors.
453  MachineInstr *ClonedDV = MBB->getParent()->CloneMachineInstr(NewDV);
454  MBB->insert(FirstTerm, ClonedDV);
455  LLVM_DEBUG(dbgs() << "Cloning debug info due to live out spill\n");
456  }
457 
458  // Rewrite unassigned dbg_values to use the stack slot.
459  // TODO We can potentially do this for list debug values as well if we know
460  // how the dbg_values are getting unassigned.
461  if (DBG.isNonListDebugValue()) {
462  MachineOperand &MO = DBG.getDebugOperand(0);
463  if (MO.isReg() && MO.getReg() == 0) {
464  updateDbgValueForSpill(DBG, FI, 0);
465  }
466  }
467  }
468  // Now this register is spilled there is should not be any DBG_VALUE
469  // pointing to this register because they are all pointing to spilled value
470  // now.
471  LRIDbgOperands.clear();
472 }
473 
474 /// Insert reload instruction for \p PhysReg before \p Before.
475 void RegAllocFast::reload(MachineBasicBlock::iterator Before, Register VirtReg,
476  MCPhysReg PhysReg) {
477  LLVM_DEBUG(dbgs() << "Reloading " << printReg(VirtReg, TRI) << " into "
478  << printReg(PhysReg, TRI) << '\n');
479  int FI = getStackSpaceFor(VirtReg);
480  const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);
481  TII->loadRegFromStackSlot(*MBB, Before, PhysReg, FI, &RC, TRI);
482  ++NumLoads;
483 }
484 
485 /// Get basic block begin insertion point.
486 /// This is not just MBB.begin() because surprisingly we have EH_LABEL
487 /// instructions marking the begin of a basic block. This means we must insert
488 /// new instructions after such labels...
490 RegAllocFast::getMBBBeginInsertionPoint(
491  MachineBasicBlock &MBB, SmallSet<Register, 2> &PrologLiveIns) const {
493  while (I != MBB.end()) {
494  if (I->isLabel()) {
495  ++I;
496  continue;
497  }
498 
499  // Most reloads should be inserted after prolog instructions.
500  if (!TII->isBasicBlockPrologue(*I))
501  break;
502 
503  // However if a prolog instruction reads a register that needs to be
504  // reloaded, the reload should be inserted before the prolog.
505  for (MachineOperand &MO : I->operands()) {
506  if (MO.isReg())
507  PrologLiveIns.insert(MO.getReg());
508  }
509 
510  ++I;
511  }
512 
513  return I;
514 }
515 
516 /// Reload all currently assigned virtual registers.
517 void RegAllocFast::reloadAtBegin(MachineBasicBlock &MBB) {
518  if (LiveVirtRegs.empty())
519  return;
520 
522  MCPhysReg Reg = P.PhysReg;
523  // Set state to live-in. This possibly overrides mappings to virtual
524  // registers but we don't care anymore at this point.
525  setPhysRegState(Reg, regLiveIn);
526  }
527 
528 
529  SmallSet<Register, 2> PrologLiveIns;
530 
531  // The LiveRegMap is keyed by an unsigned (the virtreg number), so the order
532  // of spilling here is deterministic, if arbitrary.
533  MachineBasicBlock::iterator InsertBefore
534  = getMBBBeginInsertionPoint(MBB, PrologLiveIns);
535  for (const LiveReg &LR : LiveVirtRegs) {
536  MCPhysReg PhysReg = LR.PhysReg;
537  if (PhysReg == 0)
538  continue;
539 
540  MCRegister FirstUnit = *MCRegUnitIterator(PhysReg, TRI);
541  if (RegUnitStates[FirstUnit] == regLiveIn)
542  continue;
543 
544  assert((&MBB != &MBB.getParent()->front() || IgnoreMissingDefs) &&
545  "no reload in start block. Missing vreg def?");
546 
547  if (PrologLiveIns.count(PhysReg)) {
548  // FIXME: Theoretically this should use an insert point skipping labels
549  // but I'm not sure how labels should interact with prolog instruction
550  // that need reloads.
551  reload(MBB.begin(), LR.VirtReg, PhysReg);
552  } else
553  reload(InsertBefore, LR.VirtReg, PhysReg);
554  }
555  LiveVirtRegs.clear();
556 }
557 
558 /// Handle the direct use of a physical register. Check that the register is
559 /// not used by a virtreg. Kill the physreg, marking it free. This may add
560 /// implicit kills to MO->getParent() and invalidate MO.
561 bool RegAllocFast::usePhysReg(MachineInstr &MI, MCPhysReg Reg) {
562  assert(Register::isPhysicalRegister(Reg) && "expected physreg");
563  bool displacedAny = displacePhysReg(MI, Reg);
564  setPhysRegState(Reg, regPreAssigned);
565  markRegUsedInInstr(Reg);
566  return displacedAny;
567 }
568 
569 bool RegAllocFast::definePhysReg(MachineInstr &MI, MCPhysReg Reg) {
570  bool displacedAny = displacePhysReg(MI, Reg);
571  setPhysRegState(Reg, regPreAssigned);
572  return displacedAny;
573 }
574 
575 /// Mark PhysReg as reserved or free after spilling any virtregs. This is very
576 /// similar to defineVirtReg except the physreg is reserved instead of
577 /// allocated.
578 bool RegAllocFast::displacePhysReg(MachineInstr &MI, MCPhysReg PhysReg) {
579  bool displacedAny = false;
580 
581  for (MCRegUnitIterator UI(PhysReg, TRI); UI.isValid(); ++UI) {
582  unsigned Unit = *UI;
583  switch (unsigned VirtReg = RegUnitStates[Unit]) {
584  default: {
585  LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg);
586  assert(LRI != LiveVirtRegs.end() && "datastructures in sync");
587  MachineBasicBlock::iterator ReloadBefore =
588  std::next((MachineBasicBlock::iterator)MI.getIterator());
589  reload(ReloadBefore, VirtReg, LRI->PhysReg);
590 
591  setPhysRegState(LRI->PhysReg, regFree);
592  LRI->PhysReg = 0;
593  LRI->Reloaded = true;
594  displacedAny = true;
595  break;
596  }
597  case regPreAssigned:
598  RegUnitStates[Unit] = regFree;
599  displacedAny = true;
600  break;
601  case regFree:
602  break;
603  }
604  }
605  return displacedAny;
606 }
607 
608 void RegAllocFast::freePhysReg(MCPhysReg PhysReg) {
609  LLVM_DEBUG(dbgs() << "Freeing " << printReg(PhysReg, TRI) << ':');
610 
611  MCRegister FirstUnit = *MCRegUnitIterator(PhysReg, TRI);
612  switch (unsigned VirtReg = RegUnitStates[FirstUnit]) {
613  case regFree:
614  LLVM_DEBUG(dbgs() << '\n');
615  return;
616  case regPreAssigned:
617  LLVM_DEBUG(dbgs() << '\n');
618  setPhysRegState(PhysReg, regFree);
619  return;
620  default: {
621  LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg);
622  assert(LRI != LiveVirtRegs.end());
623  LLVM_DEBUG(dbgs() << ' ' << printReg(LRI->VirtReg, TRI) << '\n');
624  setPhysRegState(LRI->PhysReg, regFree);
625  LRI->PhysReg = 0;
626  }
627  return;
628  }
629 }
630 
631 /// Return the cost of spilling clearing out PhysReg and aliases so it is free
632 /// for allocation. Returns 0 when PhysReg is free or disabled with all aliases
633 /// disabled - it can be allocated directly.
634 /// \returns spillImpossible when PhysReg or an alias can't be spilled.
635 unsigned RegAllocFast::calcSpillCost(MCPhysReg PhysReg) const {
636  for (MCRegUnitIterator UI(PhysReg, TRI); UI.isValid(); ++UI) {
637  switch (unsigned VirtReg = RegUnitStates[*UI]) {
638  case regFree:
639  break;
640  case regPreAssigned:
641  LLVM_DEBUG(dbgs() << "Cannot spill pre-assigned "
642  << printReg(PhysReg, TRI) << '\n');
643  return spillImpossible;
644  default: {
645  bool SureSpill = StackSlotForVirtReg[VirtReg] != -1 ||
646  findLiveVirtReg(VirtReg)->LiveOut;
647  return SureSpill ? spillClean : spillDirty;
648  }
649  }
650  }
651  return 0;
652 }
653 
654 void RegAllocFast::assignDanglingDebugValues(MachineInstr &Definition,
655  Register VirtReg, MCPhysReg Reg) {
656  auto UDBGValIter = DanglingDbgValues.find(VirtReg);
657  if (UDBGValIter == DanglingDbgValues.end())
658  return;
659 
660  SmallVectorImpl<MachineInstr*> &Dangling = UDBGValIter->second;
661  for (MachineInstr *DbgValue : Dangling) {
662  assert(DbgValue->isDebugValue());
663  if (!DbgValue->hasDebugOperandForReg(VirtReg))
664  continue;
665 
666  // Test whether the physreg survives from the definition to the DBG_VALUE.
667  MCPhysReg SetToReg = Reg;
668  unsigned Limit = 20;
669  for (MachineBasicBlock::iterator I = std::next(Definition.getIterator()),
670  E = DbgValue->getIterator(); I != E; ++I) {
671  if (I->modifiesRegister(Reg, TRI) || --Limit == 0) {
672  LLVM_DEBUG(dbgs() << "Register did not survive for " << *DbgValue
673  << '\n');
674  SetToReg = 0;
675  break;
676  }
677  }
678  for (MachineOperand &MO : DbgValue->getDebugOperandsForReg(VirtReg)) {
679  MO.setReg(SetToReg);
680  if (SetToReg != 0)
681  MO.setIsRenamable();
682  }
683  }
684  Dangling.clear();
685 }
686 
687 /// This method updates local state so that we know that PhysReg is the
688 /// proper container for VirtReg now. The physical register must not be used
689 /// for anything else when this is called.
690 void RegAllocFast::assignVirtToPhysReg(MachineInstr &AtMI, LiveReg &LR,
691  MCPhysReg PhysReg) {
692  Register VirtReg = LR.VirtReg;
693  LLVM_DEBUG(dbgs() << "Assigning " << printReg(VirtReg, TRI) << " to "
694  << printReg(PhysReg, TRI) << '\n');
695  assert(LR.PhysReg == 0 && "Already assigned a physreg");
696  assert(PhysReg != 0 && "Trying to assign no register");
697  LR.PhysReg = PhysReg;
698  setPhysRegState(PhysReg, VirtReg);
699 
700  assignDanglingDebugValues(AtMI, VirtReg, PhysReg);
701 }
702 
703 static bool isCoalescable(const MachineInstr &MI) {
704  return MI.isFullCopy();
705 }
706 
707 Register RegAllocFast::traceCopyChain(Register Reg) const {
708  static const unsigned ChainLengthLimit = 3;
709  unsigned C = 0;
710  do {
711  if (Reg.isPhysical())
712  return Reg;
713  assert(Reg.isVirtual());
714 
715  MachineInstr *VRegDef = MRI->getUniqueVRegDef(Reg);
716  if (!VRegDef || !isCoalescable(*VRegDef))
717  return 0;
718  Reg = VRegDef->getOperand(1).getReg();
719  } while (++C <= ChainLengthLimit);
720  return 0;
721 }
722 
723 /// Check if any of \p VirtReg's definitions is a copy. If it is follow the
724 /// chain of copies to check whether we reach a physical register we can
725 /// coalesce with.
726 Register RegAllocFast::traceCopies(Register VirtReg) const {
727  static const unsigned DefLimit = 3;
728  unsigned C = 0;
729  for (const MachineInstr &MI : MRI->def_instructions(VirtReg)) {
730  if (isCoalescable(MI)) {
731  Register Reg = MI.getOperand(1).getReg();
732  Reg = traceCopyChain(Reg);
733  if (Reg.isValid())
734  return Reg;
735  }
736 
737  if (++C >= DefLimit)
738  break;
739  }
740  return Register();
741 }
742 
743 /// Allocates a physical register for VirtReg.
744 void RegAllocFast::allocVirtReg(MachineInstr &MI, LiveReg &LR,
745  Register Hint0, bool LookAtPhysRegUses) {
746  const Register VirtReg = LR.VirtReg;
747  assert(LR.PhysReg == 0);
748 
749  const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);
750  LLVM_DEBUG(dbgs() << "Search register for " << printReg(VirtReg)
751  << " in class " << TRI->getRegClassName(&RC)
752  << " with hint " << printReg(Hint0, TRI) << '\n');
753 
754  // Take hint when possible.
755  if (Hint0.isPhysical() && MRI->isAllocatable(Hint0) && RC.contains(Hint0) &&
756  !isRegUsedInInstr(Hint0, LookAtPhysRegUses)) {
757  // Take hint if the register is currently free.
758  if (isPhysRegFree(Hint0)) {
759  LLVM_DEBUG(dbgs() << "\tPreferred Register 1: " << printReg(Hint0, TRI)
760  << '\n');
761  assignVirtToPhysReg(MI, LR, Hint0);
762  return;
763  } else {
764  LLVM_DEBUG(dbgs() << "\tPreferred Register 0: " << printReg(Hint0, TRI)
765  << " occupied\n");
766  }
767  } else {
768  Hint0 = Register();
769  }
770 
771 
772  // Try other hint.
773  Register Hint1 = traceCopies(VirtReg);
774  if (Hint1.isPhysical() && MRI->isAllocatable(Hint1) && RC.contains(Hint1) &&
775  !isRegUsedInInstr(Hint1, LookAtPhysRegUses)) {
776  // Take hint if the register is currently free.
777  if (isPhysRegFree(Hint1)) {
778  LLVM_DEBUG(dbgs() << "\tPreferred Register 0: " << printReg(Hint1, TRI)
779  << '\n');
780  assignVirtToPhysReg(MI, LR, Hint1);
781  return;
782  } else {
783  LLVM_DEBUG(dbgs() << "\tPreferred Register 1: " << printReg(Hint1, TRI)
784  << " occupied\n");
785  }
786  } else {
787  Hint1 = Register();
788  }
789 
790  MCPhysReg BestReg = 0;
791  unsigned BestCost = spillImpossible;
792  ArrayRef<MCPhysReg> AllocationOrder = RegClassInfo.getOrder(&RC);
793  for (MCPhysReg PhysReg : AllocationOrder) {
794  LLVM_DEBUG(dbgs() << "\tRegister: " << printReg(PhysReg, TRI) << ' ');
795  if (isRegUsedInInstr(PhysReg, LookAtPhysRegUses)) {
796  LLVM_DEBUG(dbgs() << "already used in instr.\n");
797  continue;
798  }
799 
800  unsigned Cost = calcSpillCost(PhysReg);
801  LLVM_DEBUG(dbgs() << "Cost: " << Cost << " BestCost: " << BestCost << '\n');
802  // Immediate take a register with cost 0.
803  if (Cost == 0) {
804  assignVirtToPhysReg(MI, LR, PhysReg);
805  return;
806  }
807 
808  if (PhysReg == Hint0 || PhysReg == Hint1)
809  Cost -= spillPrefBonus;
810 
811  if (Cost < BestCost) {
812  BestReg = PhysReg;
813  BestCost = Cost;
814  }
815  }
816 
817  if (!BestReg) {
818  // Nothing we can do: Report an error and keep going with an invalid
819  // allocation.
820  if (MI.isInlineAsm())
821  MI.emitError("inline assembly requires more registers than available");
822  else
823  MI.emitError("ran out of registers during register allocation");
824 
825  LR.Error = true;
826  LR.PhysReg = 0;
827  return;
828  }
829 
830  displacePhysReg(MI, BestReg);
831  assignVirtToPhysReg(MI, LR, BestReg);
832 }
833 
834 void RegAllocFast::allocVirtRegUndef(MachineOperand &MO) {
835  assert(MO.isUndef() && "expected undef use");
836  Register VirtReg = MO.getReg();
837  assert(Register::isVirtualRegister(VirtReg) && "Expected virtreg");
838 
839  LiveRegMap::const_iterator LRI = findLiveVirtReg(VirtReg);
840  MCPhysReg PhysReg;
841  if (LRI != LiveVirtRegs.end() && LRI->PhysReg) {
842  PhysReg = LRI->PhysReg;
843  } else {
844  const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);
845  ArrayRef<MCPhysReg> AllocationOrder = RegClassInfo.getOrder(&RC);
846  assert(!AllocationOrder.empty() && "Allocation order must not be empty");
847  PhysReg = AllocationOrder[0];
848  }
849 
850  unsigned SubRegIdx = MO.getSubReg();
851  if (SubRegIdx != 0) {
852  PhysReg = TRI->getSubReg(PhysReg, SubRegIdx);
853  MO.setSubReg(0);
854  }
855  MO.setReg(PhysReg);
856  MO.setIsRenamable(true);
857 }
858 
859 /// Variation of defineVirtReg() with special handling for livethrough regs
860 /// (tied or earlyclobber) that may interfere with preassigned uses.
861 void RegAllocFast::defineLiveThroughVirtReg(MachineInstr &MI, unsigned OpNum,
862  Register VirtReg) {
863  LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg);
864  if (LRI != LiveVirtRegs.end()) {
865  MCPhysReg PrevReg = LRI->PhysReg;
866  if (PrevReg != 0 && isRegUsedInInstr(PrevReg, true)) {
867  LLVM_DEBUG(dbgs() << "Need new assignment for " << printReg(PrevReg, TRI)
868  << " (tied/earlyclobber resolution)\n");
869  freePhysReg(PrevReg);
870  LRI->PhysReg = 0;
871  allocVirtReg(MI, *LRI, 0, true);
872  MachineBasicBlock::iterator InsertBefore =
873  std::next((MachineBasicBlock::iterator)MI.getIterator());
874  LLVM_DEBUG(dbgs() << "Copy " << printReg(LRI->PhysReg, TRI) << " to "
875  << printReg(PrevReg, TRI) << '\n');
876  BuildMI(*MBB, InsertBefore, MI.getDebugLoc(),
877  TII->get(TargetOpcode::COPY), PrevReg)
878  .addReg(LRI->PhysReg, llvm::RegState::Kill);
879  }
880  MachineOperand &MO = MI.getOperand(OpNum);
881  if (MO.getSubReg() && !MO.isUndef()) {
882  LRI->LastUse = &MI;
883  }
884  }
885  return defineVirtReg(MI, OpNum, VirtReg, true);
886 }
887 
888 /// Allocates a register for VirtReg definition. Typically the register is
889 /// already assigned from a use of the virtreg, however we still need to
890 /// perform an allocation if:
891 /// - It is a dead definition without any uses.
892 /// - The value is live out and all uses are in different basic blocks.
893 void RegAllocFast::defineVirtReg(MachineInstr &MI, unsigned OpNum,
894  Register VirtReg, bool LookAtPhysRegUses) {
895  assert(VirtReg.isVirtual() && "Not a virtual register");
896  MachineOperand &MO = MI.getOperand(OpNum);
897  LiveRegMap::iterator LRI;
898  bool New;
899  std::tie(LRI, New) = LiveVirtRegs.insert(LiveReg(VirtReg));
900  if (New) {
901  if (!MO.isDead()) {
902  if (mayLiveOut(VirtReg)) {
903  LRI->LiveOut = true;
904  } else {
905  // It is a dead def without the dead flag; add the flag now.
906  MO.setIsDead(true);
907  }
908  }
909  }
910  if (LRI->PhysReg == 0)
911  allocVirtReg(MI, *LRI, 0, LookAtPhysRegUses);
912  else {
913  assert(!isRegUsedInInstr(LRI->PhysReg, LookAtPhysRegUses) &&
914  "TODO: preassign mismatch");
915  LLVM_DEBUG(dbgs() << "In def of " << printReg(VirtReg, TRI)
916  << " use existing assignment to "
917  << printReg(LRI->PhysReg, TRI) << '\n');
918  }
919 
920  MCPhysReg PhysReg = LRI->PhysReg;
921  assert(PhysReg != 0 && "Register not assigned");
922  if (LRI->Reloaded || LRI->LiveOut) {
923  if (!MI.isImplicitDef()) {
924  MachineBasicBlock::iterator SpillBefore =
925  std::next((MachineBasicBlock::iterator)MI.getIterator());
926  LLVM_DEBUG(dbgs() << "Spill Reason: LO: " << LRI->LiveOut << " RL: "
927  << LRI->Reloaded << '\n');
928  bool Kill = LRI->LastUse == nullptr;
929  spill(SpillBefore, VirtReg, PhysReg, Kill, LRI->LiveOut);
930  LRI->LastUse = nullptr;
931  }
932  LRI->LiveOut = false;
933  LRI->Reloaded = false;
934  }
935  if (MI.getOpcode() == TargetOpcode::BUNDLE) {
936  BundleVirtRegsMap[VirtReg] = PhysReg;
937  }
938  markRegUsedInInstr(PhysReg);
939  setPhysReg(MI, MO, PhysReg);
940 }
941 
942 /// Allocates a register for a VirtReg use.
943 void RegAllocFast::useVirtReg(MachineInstr &MI, unsigned OpNum,
944  Register VirtReg) {
945  assert(VirtReg.isVirtual() && "Not a virtual register");
946  MachineOperand &MO = MI.getOperand(OpNum);
947  LiveRegMap::iterator LRI;
948  bool New;
949  std::tie(LRI, New) = LiveVirtRegs.insert(LiveReg(VirtReg));
950  if (New) {
951  MachineOperand &MO = MI.getOperand(OpNum);
952  if (!MO.isKill()) {
953  if (mayLiveOut(VirtReg)) {
954  LRI->LiveOut = true;
955  } else {
956  // It is a last (killing) use without the kill flag; add the flag now.
957  MO.setIsKill(true);
958  }
959  }
960  } else {
961  assert((!MO.isKill() || LRI->LastUse == &MI) && "Invalid kill flag");
962  }
963 
964  // If necessary allocate a register.
965  if (LRI->PhysReg == 0) {
966  assert(!MO.isTied() && "tied op should be allocated");
967  Register Hint;
968  if (MI.isCopy() && MI.getOperand(1).getSubReg() == 0) {
969  Hint = MI.getOperand(0).getReg();
970  assert(Hint.isPhysical() &&
971  "Copy destination should already be assigned");
972  }
973  allocVirtReg(MI, *LRI, Hint, false);
974  if (LRI->Error) {
975  const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);
976  ArrayRef<MCPhysReg> AllocationOrder = RegClassInfo.getOrder(&RC);
977  setPhysReg(MI, MO, *AllocationOrder.begin());
978  return;
979  }
980  }
981 
982  LRI->LastUse = &MI;
983 
984  if (MI.getOpcode() == TargetOpcode::BUNDLE) {
985  BundleVirtRegsMap[VirtReg] = LRI->PhysReg;
986  }
987  markRegUsedInInstr(LRI->PhysReg);
988  setPhysReg(MI, MO, LRI->PhysReg);
989 }
990 
991 /// Changes operand OpNum in MI the refer the PhysReg, considering subregs. This
992 /// may invalidate any operand pointers. Return true if the operand kills its
993 /// register.
994 void RegAllocFast::setPhysReg(MachineInstr &MI, MachineOperand &MO,
995  MCPhysReg PhysReg) {
996  if (!MO.getSubReg()) {
997  MO.setReg(PhysReg);
998  MO.setIsRenamable(true);
999  return;
1000  }
1001 
1002  // Handle subregister index.
1003  MO.setReg(PhysReg ? TRI->getSubReg(PhysReg, MO.getSubReg()) : MCRegister());
1004  MO.setIsRenamable(true);
1005  // Note: We leave the subreg number around a little longer in case of defs.
1006  // This is so that the register freeing logic in allocateInstruction can still
1007  // recognize this as subregister defs. The code there will clear the number.
1008  if (!MO.isDef())
1009  MO.setSubReg(0);
1010 
1011  // A kill flag implies killing the full register. Add corresponding super
1012  // register kill.
1013  if (MO.isKill()) {
1014  MI.addRegisterKilled(PhysReg, TRI, true);
1015  return;
1016  }
1017 
1018  // A <def,read-undef> of a sub-register requires an implicit def of the full
1019  // register.
1020  if (MO.isDef() && MO.isUndef()) {
1021  if (MO.isDead())
1022  MI.addRegisterDead(PhysReg, TRI, true);
1023  else
1024  MI.addRegisterDefined(PhysReg, TRI);
1025  }
1026 }
1027 
1028 #ifndef NDEBUG
1029 
1030 void RegAllocFast::dumpState() const {
1031  for (unsigned Unit = 1, UnitE = TRI->getNumRegUnits(); Unit != UnitE;
1032  ++Unit) {
1033  switch (unsigned VirtReg = RegUnitStates[Unit]) {
1034  case regFree:
1035  break;
1036  case regPreAssigned:
1037  dbgs() << " " << printRegUnit(Unit, TRI) << "[P]";
1038  break;
1039  case regLiveIn:
1040  llvm_unreachable("Should not have regLiveIn in map");
1041  default: {
1042  dbgs() << ' ' << printRegUnit(Unit, TRI) << '=' << printReg(VirtReg);
1043  LiveRegMap::const_iterator I = findLiveVirtReg(VirtReg);
1044  assert(I != LiveVirtRegs.end() && "have LiveVirtRegs entry");
1045  if (I->LiveOut || I->Reloaded) {
1046  dbgs() << '[';
1047  if (I->LiveOut) dbgs() << 'O';
1048  if (I->Reloaded) dbgs() << 'R';
1049  dbgs() << ']';
1050  }
1051  assert(TRI->hasRegUnit(I->PhysReg, Unit) && "inverse mapping present");
1052  break;
1053  }
1054  }
1055  }
1056  dbgs() << '\n';
1057  // Check that LiveVirtRegs is the inverse.
1058  for (const LiveReg &LR : LiveVirtRegs) {
1059  Register VirtReg = LR.VirtReg;
1060  assert(VirtReg.isVirtual() && "Bad map key");
1061  MCPhysReg PhysReg = LR.PhysReg;
1062  if (PhysReg != 0) {
1064  "mapped to physreg");
1065  for (MCRegUnitIterator UI(PhysReg, TRI); UI.isValid(); ++UI) {
1066  assert(RegUnitStates[*UI] == VirtReg && "inverse map valid");
1067  }
1068  }
1069  }
1070 }
1071 #endif
1072 
1073 /// Count number of defs consumed from each register class by \p Reg
1074 void RegAllocFast::addRegClassDefCounts(std::vector<unsigned> &RegClassDefCounts,
1075  Register Reg) const {
1076  assert(RegClassDefCounts.size() == TRI->getNumRegClasses());
1077 
1078  if (Reg.isVirtual()) {
1079  const TargetRegisterClass *OpRC = MRI->getRegClass(Reg);
1080  for (unsigned RCIdx = 0, RCIdxEnd = TRI->getNumRegClasses();
1081  RCIdx != RCIdxEnd; ++RCIdx) {
1082  const TargetRegisterClass *IdxRC = TRI->getRegClass(RCIdx);
1083  // FIXME: Consider aliasing sub/super registers.
1084  if (OpRC->hasSubClassEq(IdxRC))
1085  ++RegClassDefCounts[RCIdx];
1086  }
1087 
1088  return;
1089  }
1090 
1091  for (unsigned RCIdx = 0, RCIdxEnd = TRI->getNumRegClasses();
1092  RCIdx != RCIdxEnd; ++RCIdx) {
1093  const TargetRegisterClass *IdxRC = TRI->getRegClass(RCIdx);
1094  for (MCRegAliasIterator Alias(Reg, TRI, true); Alias.isValid(); ++Alias) {
1095  if (IdxRC->contains(*Alias)) {
1096  ++RegClassDefCounts[RCIdx];
1097  break;
1098  }
1099  }
1100  }
1101 }
1102 
1103 void RegAllocFast::allocateInstruction(MachineInstr &MI) {
1104  // The basic algorithm here is:
1105  // 1. Mark registers of def operands as free
1106  // 2. Allocate registers to use operands and place reload instructions for
1107  // registers displaced by the allocation.
1108  //
1109  // However we need to handle some corner cases:
1110  // - pre-assigned defs and uses need to be handled before the other def/use
1111  // operands are processed to avoid the allocation heuristics clashing with
1112  // the pre-assignment.
1113  // - The "free def operands" step has to come last instead of first for tied
1114  // operands and early-clobbers.
1115 
1116  UsedInInstr.clear();
1117  RegMasks.clear();
1118  BundleVirtRegsMap.clear();
1119 
1120  // Scan for special cases; Apply pre-assigned register defs to state.
1121  bool HasPhysRegUse = false;
1122  bool HasRegMask = false;
1123  bool HasVRegDef = false;
1124  bool HasDef = false;
1125  bool HasEarlyClobber = false;
1126  bool NeedToAssignLiveThroughs = false;
1127  for (MachineOperand &MO : MI.operands()) {
1128  if (MO.isReg()) {
1129  Register Reg = MO.getReg();
1130  if (Reg.isVirtual()) {
1131  if (MO.isDef()) {
1132  HasDef = true;
1133  HasVRegDef = true;
1134  if (MO.isEarlyClobber()) {
1135  HasEarlyClobber = true;
1136  NeedToAssignLiveThroughs = true;
1137  }
1138  if (MO.isTied() || (MO.getSubReg() != 0 && !MO.isUndef()))
1139  NeedToAssignLiveThroughs = true;
1140  }
1141  } else if (Reg.isPhysical()) {
1142  if (!MRI->isReserved(Reg)) {
1143  if (MO.isDef()) {
1144  HasDef = true;
1145  bool displacedAny = definePhysReg(MI, Reg);
1146  if (MO.isEarlyClobber())
1147  HasEarlyClobber = true;
1148  if (!displacedAny)
1149  MO.setIsDead(true);
1150  }
1151  if (MO.readsReg())
1152  HasPhysRegUse = true;
1153  }
1154  }
1155  } else if (MO.isRegMask()) {
1156  HasRegMask = true;
1157  RegMasks.push_back(MO.getRegMask());
1158  }
1159  }
1160 
1161  // Allocate virtreg defs.
1162  if (HasDef) {
1163  if (HasVRegDef) {
1164  // Special handling for early clobbers, tied operands or subregister defs:
1165  // Compared to "normal" defs these:
1166  // - Must not use a register that is pre-assigned for a use operand.
1167  // - In order to solve tricky inline assembly constraints we change the
1168  // heuristic to figure out a good operand order before doing
1169  // assignments.
1170  if (NeedToAssignLiveThroughs) {
1171  DefOperandIndexes.clear();
1172  PhysRegUses.clear();
1173 
1174  // Track number of defs which may consume a register from the class.
1175  std::vector<unsigned> RegClassDefCounts(TRI->getNumRegClasses(), 0);
1176  assert(RegClassDefCounts[0] == 0);
1177 
1178  LLVM_DEBUG(dbgs() << "Need to assign livethroughs\n");
1179  for (unsigned I = 0, E = MI.getNumOperands(); I < E; ++I) {
1180  const MachineOperand &MO = MI.getOperand(I);
1181  if (!MO.isReg())
1182  continue;
1183  Register Reg = MO.getReg();
1184  if (MO.readsReg()) {
1185  if (Reg.isPhysical()) {
1186  LLVM_DEBUG(dbgs() << "mark extra used: " << printReg(Reg, TRI)
1187  << '\n');
1188  markPhysRegUsedInInstr(Reg);
1189  }
1190  }
1191 
1192  if (MO.isDef()) {
1193  if (Reg.isVirtual())
1194  DefOperandIndexes.push_back(I);
1195 
1196  addRegClassDefCounts(RegClassDefCounts, Reg);
1197  }
1198  }
1199 
1200  llvm::sort(DefOperandIndexes, [&](uint16_t I0, uint16_t I1) {
1201  const MachineOperand &MO0 = MI.getOperand(I0);
1202  const MachineOperand &MO1 = MI.getOperand(I1);
1203  Register Reg0 = MO0.getReg();
1204  Register Reg1 = MO1.getReg();
1205  const TargetRegisterClass &RC0 = *MRI->getRegClass(Reg0);
1206  const TargetRegisterClass &RC1 = *MRI->getRegClass(Reg1);
1207 
1208  // Identify regclass that are easy to use up completely just in this
1209  // instruction.
1210  unsigned ClassSize0 = RegClassInfo.getOrder(&RC0).size();
1211  unsigned ClassSize1 = RegClassInfo.getOrder(&RC1).size();
1212 
1213  bool SmallClass0 = ClassSize0 < RegClassDefCounts[RC0.getID()];
1214  bool SmallClass1 = ClassSize1 < RegClassDefCounts[RC1.getID()];
1215  if (SmallClass0 > SmallClass1)
1216  return true;
1217  if (SmallClass0 < SmallClass1)
1218  return false;
1219 
1220  // Allocate early clobbers and livethrough operands first.
1221  bool Livethrough0 = MO0.isEarlyClobber() || MO0.isTied() ||
1222  (MO0.getSubReg() == 0 && !MO0.isUndef());
1223  bool Livethrough1 = MO1.isEarlyClobber() || MO1.isTied() ||
1224  (MO1.getSubReg() == 0 && !MO1.isUndef());
1225  if (Livethrough0 > Livethrough1)
1226  return true;
1227  if (Livethrough0 < Livethrough1)
1228  return false;
1229 
1230  // Tie-break rule: operand index.
1231  return I0 < I1;
1232  });
1233 
1234  for (uint16_t OpIdx : DefOperandIndexes) {
1235  MachineOperand &MO = MI.getOperand(OpIdx);
1236  LLVM_DEBUG(dbgs() << "Allocating " << MO << '\n');
1237  unsigned Reg = MO.getReg();
1238  if (MO.isEarlyClobber() || MO.isTied() ||
1239  (MO.getSubReg() && !MO.isUndef())) {
1240  defineLiveThroughVirtReg(MI, OpIdx, Reg);
1241  } else {
1242  defineVirtReg(MI, OpIdx, Reg);
1243  }
1244  }
1245  } else {
1246  // Assign virtual register defs.
1247  for (unsigned I = 0, E = MI.getNumOperands(); I < E; ++I) {
1248  MachineOperand &MO = MI.getOperand(I);
1249  if (!MO.isReg() || !MO.isDef())
1250  continue;
1251  Register Reg = MO.getReg();
1252  if (Reg.isVirtual())
1253  defineVirtReg(MI, I, Reg);
1254  }
1255  }
1256  }
1257 
1258  // Free registers occupied by defs.
1259  // Iterate operands in reverse order, so we see the implicit super register
1260  // defs first (we added them earlier in case of <def,read-undef>).
1261  for (MachineOperand &MO : llvm::reverse(MI.operands())) {
1262  if (!MO.isReg() || !MO.isDef())
1263  continue;
1264 
1265  // subreg defs don't free the full register. We left the subreg number
1266  // around as a marker in setPhysReg() to recognize this case here.
1267  if (MO.getSubReg() != 0) {
1268  MO.setSubReg(0);
1269  continue;
1270  }
1271 
1272  assert((!MO.isTied() || !isClobberedByRegMasks(MO.getReg())) &&
1273  "tied def assigned to clobbered register");
1274 
1275  // Do not free tied operands and early clobbers.
1276  if (MO.isTied() || MO.isEarlyClobber())
1277  continue;
1278  Register Reg = MO.getReg();
1279  if (!Reg)
1280  continue;
1281  assert(Reg.isPhysical());
1282  if (MRI->isReserved(Reg))
1283  continue;
1284  freePhysReg(Reg);
1285  unmarkRegUsedInInstr(Reg);
1286  }
1287  }
1288 
1289  // Displace clobbered registers.
1290  if (HasRegMask) {
1291  assert(!RegMasks.empty() && "expected RegMask");
1292  // MRI bookkeeping.
1293  for (const auto *RM : RegMasks)
1295 
1296  // Displace clobbered registers.
1297  for (const LiveReg &LR : LiveVirtRegs) {
1298  MCPhysReg PhysReg = LR.PhysReg;
1299  if (PhysReg != 0 && isClobberedByRegMasks(PhysReg))
1300  displacePhysReg(MI, PhysReg);
1301  }
1302  }
1303 
1304  // Apply pre-assigned register uses to state.
1305  if (HasPhysRegUse) {
1306  for (MachineOperand &MO : MI.operands()) {
1307  if (!MO.isReg() || !MO.readsReg())
1308  continue;
1309  Register Reg = MO.getReg();
1310  if (!Reg.isPhysical())
1311  continue;
1312  if (MRI->isReserved(Reg))
1313  continue;
1314  bool displacedAny = usePhysReg(MI, Reg);
1315  if (!displacedAny && !MRI->isReserved(Reg))
1316  MO.setIsKill(true);
1317  }
1318  }
1319 
1320  // Allocate virtreg uses and insert reloads as necessary.
1321  bool HasUndefUse = false;
1322  for (unsigned I = 0; I < MI.getNumOperands(); ++I) {
1323  MachineOperand &MO = MI.getOperand(I);
1324  if (!MO.isReg() || !MO.isUse())
1325  continue;
1326  Register Reg = MO.getReg();
1327  if (!Reg.isVirtual())
1328  continue;
1329 
1330  if (MO.isUndef()) {
1331  HasUndefUse = true;
1332  continue;
1333  }
1334 
1335 
1336  // Populate MayLiveAcrossBlocks in case the use block is allocated before
1337  // the def block (removing the vreg uses).
1338  mayLiveIn(Reg);
1339 
1340 
1341  assert(!MO.isInternalRead() && "Bundles not supported");
1342  assert(MO.readsReg() && "reading use");
1343  useVirtReg(MI, I, Reg);
1344  }
1345 
1346  // Allocate undef operands. This is a separate step because in a situation
1347  // like ` = OP undef %X, %X` both operands need the same register assign
1348  // so we should perform the normal assignment first.
1349  if (HasUndefUse) {
1350  for (MachineOperand &MO : MI.uses()) {
1351  if (!MO.isReg() || !MO.isUse())
1352  continue;
1353  Register Reg = MO.getReg();
1354  if (!Reg.isVirtual())
1355  continue;
1356 
1357  assert(MO.isUndef() && "Should only have undef virtreg uses left");
1358  allocVirtRegUndef(MO);
1359  }
1360  }
1361 
1362  // Free early clobbers.
1363  if (HasEarlyClobber) {
1364  for (MachineOperand &MO : llvm::reverse(MI.operands())) {
1365  if (!MO.isReg() || !MO.isDef() || !MO.isEarlyClobber())
1366  continue;
1367  // subreg defs don't free the full register. We left the subreg number
1368  // around as a marker in setPhysReg() to recognize this case here.
1369  if (MO.getSubReg() != 0) {
1370  MO.setSubReg(0);
1371  continue;
1372  }
1373 
1374  Register Reg = MO.getReg();
1375  if (!Reg)
1376  continue;
1377  assert(Reg.isPhysical() && "should have register assigned");
1378 
1379  // We sometimes get odd situations like:
1380  // early-clobber %x0 = INSTRUCTION %x0
1381  // which is semantically questionable as the early-clobber should
1382  // apply before the use. But in practice we consider the use to
1383  // happen before the early clobber now. Don't free the early clobber
1384  // register in this case.
1385  if (MI.readsRegister(Reg, TRI))
1386  continue;
1387 
1388  freePhysReg(Reg);
1389  }
1390  }
1391 
1392  LLVM_DEBUG(dbgs() << "<< " << MI);
1393  if (MI.isCopy() && MI.getOperand(0).getReg() == MI.getOperand(1).getReg() &&
1394  MI.getNumOperands() == 2) {
1395  LLVM_DEBUG(dbgs() << "Mark identity copy for removal\n");
1396  Coalesced.push_back(&MI);
1397  }
1398 }
1399 
1400 void RegAllocFast::handleDebugValue(MachineInstr &MI) {
1401  // Ignore DBG_VALUEs that aren't based on virtual registers. These are
1402  // mostly constants and frame indices.
1403  for (Register Reg : MI.getUsedDebugRegs()) {
1405  continue;
1406 
1407  // Already spilled to a stackslot?
1408  int SS = StackSlotForVirtReg[Reg];
1409  if (SS != -1) {
1410  // Modify DBG_VALUE now that the value is in a spill slot.
1412  LLVM_DEBUG(dbgs() << "Rewrite DBG_VALUE for spilled memory: " << MI);
1413  continue;
1414  }
1415 
1416  // See if this virtual register has already been allocated to a physical
1417  // register or spilled to a stack slot.
1418  LiveRegMap::iterator LRI = findLiveVirtReg(Reg);
1420  for (MachineOperand &Op : MI.getDebugOperandsForReg(Reg))
1421  DbgOps.push_back(&Op);
1422 
1423  if (LRI != LiveVirtRegs.end() && LRI->PhysReg) {
1424  // Update every use of Reg within MI.
1425  for (auto &RegMO : DbgOps)
1426  setPhysReg(MI, *RegMO, LRI->PhysReg);
1427  } else {
1428  DanglingDbgValues[Reg].push_back(&MI);
1429  }
1430 
1431  // If Reg hasn't been spilled, put this DBG_VALUE in LiveDbgValueMap so
1432  // that future spills of Reg will have DBG_VALUEs.
1433  LiveDbgValueMap[Reg].append(DbgOps.begin(), DbgOps.end());
1434  }
1435 }
1436 
1437 void RegAllocFast::handleBundle(MachineInstr &MI) {
1438  MachineBasicBlock::instr_iterator BundledMI = MI.getIterator();
1439  ++BundledMI;
1440  while (BundledMI->isBundledWithPred()) {
1441  for (MachineOperand &MO : BundledMI->operands()) {
1442  if (!MO.isReg())
1443  continue;
1444 
1445  Register Reg = MO.getReg();
1446  if (!Reg.isVirtual())
1447  continue;
1448 
1450  DI = BundleVirtRegsMap.find(Reg);
1451  assert(DI != BundleVirtRegsMap.end() && "Unassigned virtual register");
1452 
1453  setPhysReg(MI, MO, DI->second);
1454  }
1455 
1456  ++BundledMI;
1457  }
1458 }
1459 
1460 void RegAllocFast::allocateBasicBlock(MachineBasicBlock &MBB) {
1461  this->MBB = &MBB;
1462  LLVM_DEBUG(dbgs() << "\nAllocating " << MBB);
1463 
1464  RegUnitStates.assign(TRI->getNumRegUnits(), regFree);
1465  assert(LiveVirtRegs.empty() && "Mapping not cleared from last block?");
1466 
1467  for (auto &LiveReg : MBB.liveouts())
1468  setPhysRegState(LiveReg.PhysReg, regPreAssigned);
1469 
1470  Coalesced.clear();
1471 
1472  // Traverse block in reverse order allocating instructions one by one.
1473  for (MachineInstr &MI : reverse(MBB)) {
1474  LLVM_DEBUG(
1475  dbgs() << "\n>> " << MI << "Regs:";
1476  dumpState()
1477  );
1478 
1479  // Special handling for debug values. Note that they are not allowed to
1480  // affect codegen of the other instructions in any way.
1481  if (MI.isDebugValue()) {
1482  handleDebugValue(MI);
1483  continue;
1484  }
1485 
1486  allocateInstruction(MI);
1487 
1488  // Once BUNDLE header is assigned registers, same assignments need to be
1489  // done for bundled MIs.
1490  if (MI.getOpcode() == TargetOpcode::BUNDLE) {
1491  handleBundle(MI);
1492  }
1493  }
1494 
1495  LLVM_DEBUG(
1496  dbgs() << "Begin Regs:";
1497  dumpState()
1498  );
1499 
1500  // Spill all physical registers holding virtual registers now.
1501  LLVM_DEBUG(dbgs() << "Loading live registers at begin of block.\n");
1502  reloadAtBegin(MBB);
1503 
1504  // Erase all the coalesced copies. We are delaying it until now because
1505  // LiveVirtRegs might refer to the instrs.
1506  for (MachineInstr *MI : Coalesced)
1507  MBB.erase(MI);
1508  NumCoalesced += Coalesced.size();
1509 
1510  for (auto &UDBGPair : DanglingDbgValues) {
1511  for (MachineInstr *DbgValue : UDBGPair.second) {
1512  assert(DbgValue->isDebugValue() && "expected DBG_VALUE");
1513  // Nothing to do if the vreg was spilled in the meantime.
1514  if (!DbgValue->hasDebugOperandForReg(UDBGPair.first))
1515  continue;
1516  LLVM_DEBUG(dbgs() << "Register did not survive for " << *DbgValue
1517  << '\n');
1518  DbgValue->setDebugValueUndef();
1519  }
1520  }
1521  DanglingDbgValues.clear();
1522 
1523  LLVM_DEBUG(MBB.dump());
1524 }
1525 
1526 bool RegAllocFast::runOnMachineFunction(MachineFunction &MF) {
1527  LLVM_DEBUG(dbgs() << "********** FAST REGISTER ALLOCATION **********\n"
1528  << "********** Function: " << MF.getName() << '\n');
1529  MRI = &MF.getRegInfo();
1530  const TargetSubtargetInfo &STI = MF.getSubtarget();
1531  TRI = STI.getRegisterInfo();
1532  TII = STI.getInstrInfo();
1533  MFI = &MF.getFrameInfo();
1534  MRI->freezeReservedRegs(MF);
1535  RegClassInfo.runOnMachineFunction(MF);
1536  unsigned NumRegUnits = TRI->getNumRegUnits();
1537  UsedInInstr.clear();
1538  UsedInInstr.setUniverse(NumRegUnits);
1539  PhysRegUses.clear();
1540  PhysRegUses.setUniverse(NumRegUnits);
1541 
1542  // initialize the virtual->physical register map to have a 'null'
1543  // mapping for all virtual registers
1544  unsigned NumVirtRegs = MRI->getNumVirtRegs();
1545  StackSlotForVirtReg.resize(NumVirtRegs);
1546  LiveVirtRegs.setUniverse(NumVirtRegs);
1547  MayLiveAcrossBlocks.clear();
1548  MayLiveAcrossBlocks.resize(NumVirtRegs);
1549 
1550  // Loop over all of the basic blocks, eliminating virtual register references
1551  for (MachineBasicBlock &MBB : MF)
1552  allocateBasicBlock(MBB);
1553 
1554  if (ClearVirtRegs) {
1555  // All machine operands and other references to virtual registers have been
1556  // replaced. Remove the virtual registers.
1557  MRI->clearVirtRegs();
1558  }
1559 
1560  StackSlotForVirtReg.clear();
1561  LiveDbgValueMap.clear();
1562  return true;
1563 }
1564 
1566  return new RegAllocFast();
1567 }
1568 
1570  std::function<bool(const TargetRegisterInfo &TRI,
1571  const TargetRegisterClass &RC)> Ftor, bool ClearVirtRegs) {
1572  return new RegAllocFast(Ftor, ClearVirtRegs);
1573 }
llvm::Check::Size
@ Size
Definition: FileCheck.h:73
llvm::createFastRegisterAllocator
FunctionPass * createFastRegisterAllocator()
FastRegisterAllocation Pass - This pass register allocates as fast as possible.
Definition: RegAllocFast.cpp:1565
IndexedMap.h
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:105
MachineInstr.h
llvm::TargetRegisterClass::getID
unsigned getID() const
Return the register class ID number.
Definition: TargetRegisterInfo.h:71
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
llvm::tgtok::Def
@ Def
Definition: TGLexer.h:50
llvm::RegisterClassInfo::getOrder
ArrayRef< MCPhysReg > getOrder(const TargetRegisterClass *RC) const
getOrder - Returns the preferred allocation order for RC.
Definition: RegisterClassInfo.h:99
Reg
unsigned Reg
Definition: MachineSink.cpp:1558
RegAllocCommon.h
Metadata.h
MCInstrDesc.h
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:52
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
Pass.h
llvm::BitVector::set
BitVector & set()
Definition: BitVector.h:343
llvm::TargetSubtargetInfo::getInstrInfo
virtual const TargetInstrInfo * getInstrInfo() const
Definition: TargetSubtargetInfo.h:92
llvm::BitVector::clear
void clear()
clear - Removes all bits from the bitvector.
Definition: BitVector.h:327
llvm::MachineOperand::setIsKill
void setIsKill(bool Val=true)
Definition: MachineOperand.h:500
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
Statistic.h
ErrorHandling.h
llvm::MachineOperand::isTied
bool isTied() const
Definition: MachineOperand.h:441
MapVector.h
llvm::MachineRegisterInfo::getUniqueVRegDef
MachineInstr * getUniqueVRegDef(Register Reg) const
getUniqueVRegDef - Return the unique machine instr that defines the specified virtual register or nul...
Definition: MachineRegisterInfo.cpp:409
llvm::MachineFunctionPass
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Definition: MachineFunctionPass.h:30
RegisterClassInfo.h
MachineBasicBlock.h
llvm::TargetSubtargetInfo::getRegisterInfo
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
Definition: TargetSubtargetInfo.h:124
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
llvm::MachineRegisterInfo::use_nodbg_instructions
iterator_range< use_instr_nodbg_iterator > use_nodbg_instructions(Register Reg) const
Definition: MachineRegisterInfo.h:543
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:233
DenseMap.h
llvm::IndexedMap::clear
void clear()
Definition: IndexedMap.h:63
llvm::MachineBasicBlock::liveins
iterator_range< livein_iterator > liveins() const
Definition: MachineBasicBlock.h:412
llvm::BitVector::resize
void resize(unsigned N, bool t=false)
resize - Grow or shrink the bitvector.
Definition: BitVector.h:333
llvm::reverse
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:359
TargetInstrInfo.h
llvm::SmallSet
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:134
llvm::MachineFunctionProperties::Property::IsSSA
@ IsSSA
llvm::MachineFunctionProperties
Properties which a MachineFunction may have at a given point in time.
Definition: MachineFunction.h:111
llvm::MachineRegisterInfo::getNumVirtRegs
unsigned getNumVirtRegs() const
getNumVirtRegs - Return the number of virtual registers created.
Definition: MachineRegisterInfo.h:757
llvm::RegState::Kill
@ Kill
The last use of a register.
Definition: MachineInstrBuilder.h:48
llvm::AllocationOrder::begin
Iterator begin() const
Definition: AllocationOrder.h:95
llvm::MCRegisterInfo::getNumRegUnits
unsigned getNumRegUnits() const
Return the number of (native) register units in the target.
Definition: MCRegisterInfo.h:505
llvm::BitmaskEnumDetail::Mask
std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
Definition: BitmaskEnum.h:80
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1559
llvm::RegisterRegAlloc
Definition: RegAllocRegistry.h:61
llvm::MachineFunctionPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Definition: MachineFunctionPass.cpp:102
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
F
#define F(x, y, z)
Definition: MD5.cpp:56
MachineRegisterInfo.h
llvm::MachineBasicBlock::dump
void dump() const
Definition: MachineBasicBlock.cpp:294
llvm::MachineBasicBlock::erase
instr_iterator erase(instr_iterator I)
Remove an instruction from the instruction list and delete it.
Definition: MachineBasicBlock.cpp:1298
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::MachineOperand::isKill
bool isKill() const
Definition: MachineOperand.h:390
llvm::Register::isPhysical
bool isPhysical() const
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:97
llvm::MachineBasicBlock::liveouts
iterator_range< liveout_iterator > liveouts() const
Definition: MachineBasicBlock.h:506
llvm::TargetRegisterClass::contains
bool contains(Register Reg) const
Return true if the specified register is included in this register class.
Definition: TargetRegisterInfo.h:93
llvm::MachineFunction::front
const MachineBasicBlock & front() const
Definition: MachineFunction.h:835
llvm::MachineFunction::getRegInfo
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Definition: MachineFunction.h:651
llvm::TargetInstrInfo
TargetInstrInfo - Interface to description of machine instruction set.
Definition: TargetInstrInfo.h:97
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::MachineOperand::isUse
bool isUse() const
Definition: MachineOperand.h:370
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::MachineInstr::getOperand
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:499
llvm::buildDbgValueForSpill
MachineInstr * buildDbgValueForSpill(MachineBasicBlock &BB, MachineBasicBlock::iterator I, const MachineInstr &Orig, int FrameIndex, Register SpillReg)
Clone a DBG_VALUE whose value has been spilled to FrameIndex.
Definition: MachineInstr.cpp:2209
llvm::MachineRegisterInfo::isReserved
bool isReserved(MCRegister PhysReg) const
isReserved - Returns true when PhysReg is a reserved register.
Definition: MachineRegisterInfo.h:928
llvm::MachineOperand::getRegMask
const uint32_t * getRegMask() const
getRegMask - Returns a bit mask of registers preserved by this RegMask operand.
Definition: MachineOperand.h:630
llvm::MachineBasicBlock::isSuccessor
bool isSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB is a successor of this block.
Definition: MachineBasicBlock.cpp:912
llvm::MachineOperand::setSubReg
void setSubReg(unsigned subReg)
Definition: MachineOperand.h:471
llvm::IndexedMap
Definition: IndexedMap.h:29
llvm::Register::isPhysicalRegister
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:65
llvm::TargetRegisterClass
Definition: TargetRegisterInfo.h:46
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::TargetRegisterInfo::hasRegUnit
bool hasRegUnit(MCRegister Reg, Register RegUnit) const
Returns true if Reg contains RegUnit.
Definition: TargetRegisterInfo.h:435
TargetOpcodes.h
TII
const HexagonInstrInfo * TII
Definition: HexagonCopyToCombine.cpp:129
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:49
llvm::MachineFunctionProperties::set
MachineFunctionProperties & set(Property P)
Definition: MachineFunction.h:180
llvm::MachineBasicBlock::RegisterMaskPair
Pair of physical register and lane mask.
Definition: MachineBasicBlock.h:101
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
dominates
static bool dominates(MachineBasicBlock &MBB, MachineBasicBlock::const_iterator A, MachineBasicBlock::const_iterator B)
Definition: RegAllocFast.cpp:341
llvm::MachineRegisterInfo::freezeReservedRegs
void freezeReservedRegs(const MachineFunction &)
freezeReservedRegs - Called by the register allocator to freeze the set of reserved registers before ...
Definition: MachineRegisterInfo.cpp:505
DebugLoc.h
llvm::BitVector
Definition: BitVector.h:74
llvm::Align
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:39
llvm::MachineInstr::isNonListDebugValue
bool isNonListDebugValue() const
Definition: MachineInstr.h:1204
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:95
llvm::printRegUnit
Printable printRegUnit(unsigned Unit, const TargetRegisterInfo *TRI)
Create Printable object to print register units on a raw_ostream.
Definition: TargetRegisterInfo.cpp:141
llvm::MachineFrameInfo::CreateSpillStackObject
int CreateSpillStackObject(uint64_t Size, Align Alignment)
Create a new statically sized stack object that represents a spill slot, returning a nonnegative iden...
Definition: MachineFrameInfo.cpp:66
llvm::MachineRegisterInfo::getRegClass
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
Definition: MachineRegisterInfo.h:634
llvm::MachineFunctionProperties::Property::NoVRegs
@ NoVRegs
llvm::Register::isVirtual
bool isVirtual() const
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:91
llvm::TargetRegisterInfo::getSpillAlign
Align getSpillAlign(const TargetRegisterClass &RC) const
Return the minimum required alignment in bytes for a spill slot for a register of this class.
Definition: TargetRegisterInfo.h:288
llvm::SmallMapVector
A MapVector that performs no allocations if smaller than a certain size.
Definition: MapVector.h:233
llvm::MachineFunction::getSubtarget
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Definition: MachineFunction.h:641
llvm::cl::opt< bool >
llvm::AllocationOrder
Definition: AllocationOrder.h:30
llvm::RegisterClassInfo::runOnMachineFunction
void runOnMachineFunction(const MachineFunction &MF)
runOnFunction - Prepare to answer questions about MF.
Definition: RegisterClassInfo.cpp:43
llvm::MachineOperand::clobbersPhysReg
static bool clobbersPhysReg(const uint32_t *RegMask, MCRegister PhysReg)
clobbersPhysReg - Returns true if this RegMask clobbers PhysReg.
Definition: MachineOperand.h:617
llvm::TargetRegisterInfo::getSpillSize
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 ...
Definition: TargetRegisterInfo.h:282
LiveDebugValues::DbgValue
Class recording the (high level) value of a variable.
Definition: InstrRefBasedImpl.h:225
llvm::MachineOperand::isUndef
bool isUndef() const
Definition: MachineOperand.h:395
llvm::SmallSet::count
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
Definition: SmallSet.h:164
llvm::MachineOperand::setIsDead
void setIsDead(bool Val=true)
Definition: MachineOperand.h:506
llvm::MachineInstr::getDebugOperand
MachineOperand & getDebugOperand(unsigned Index)
Definition: MachineInstr.h:508
llvm::TargetRegisterInfo::getRegClass
const TargetRegisterClass * getRegClass(unsigned i) const
Returns the register class associated with the enumeration value.
Definition: TargetRegisterInfo.h:739
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::clear
void clear()
Definition: DenseMap.h:111
llvm::MachineOperand::isReg
bool isReg() const
isReg - Tests if this is a MO_Register operand.
Definition: MachineOperand.h:321
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:64
llvm::updateDbgValueForSpill
void updateDbgValueForSpill(MachineInstr &Orig, int FrameIndex, Register Reg)
Update a DBG_VALUE whose value has been spilled to FrameIndex.
Definition: MachineInstr.cpp:2252
llvm::TargetRegisterInfo::getRegClassName
const char * getRegClassName(const TargetRegisterClass *Class) const
Returns the name of the register class.
Definition: TargetRegisterInfo.h:745
llvm::MachineFunction::CloneMachineInstr
MachineInstr * CloneMachineInstr(const MachineInstr *Orig)
Create a new MachineInstr which is a copy of Orig, identical in all ways except the instruction has n...
Definition: MachineFunction.cpp:362
llvm::HexagonInstrInfo::storeRegToStackSlot
void storeRegToStackSlot(MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI, Register SrcReg, bool isKill, int FrameIndex, const TargetRegisterClass *RC, const TargetRegisterInfo *TRI) const override
Store the specified register of the given register class to the specified stack frame index.
Definition: HexagonInstrInfo.cpp:911
llvm::RegClassFilterFunc
std::function< bool(const TargetRegisterInfo &TRI, const TargetRegisterClass &RC)> RegClassFilterFunc
Definition: RegAllocCommon.h:17
llvm::DenseMap
Definition: DenseMap.h:714
llvm::MachineRegisterInfo::def_instructions
iterator_range< def_instr_iterator > def_instructions(Register Reg) const
Definition: MachineRegisterInfo.h:405
llvm::MachineOperand::isDead
bool isDead() const
Definition: MachineOperand.h:385
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::MCPhysReg
uint16_t MCPhysReg
An unsigned integer type large enough to represent all physical registers, but not necessarily virtua...
Definition: MCRegister.h:21
INITIALIZE_PASS
INITIALIZE_PASS(RegAllocFast, "regallocfast", "Fast Register Allocator", false, false) void RegAllocFast
Definition: RegAllocFast.cpp:305
MCRegisterInfo.h
ArrayRef.h
MachineFunctionPass.h
llvm::X86AS::SS
@ SS
Definition: X86.h:189
llvm::Register::isVirtualRegister
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:71
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
llvm::MachineRegisterInfo::isAllocatable
bool isAllocatable(MCRegister PhysReg) const
isAllocatable - Returns true when PhysReg belongs to an allocatable register class and it hasn't been...
Definition: MachineRegisterInfo.h:946
llvm::MachineFunction::getName
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
Definition: MachineFunction.cpp:545
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::RegisterClassInfo
Definition: RegisterClassInfo.h:30
llvm::MachineFunction::getFrameInfo
MachineFrameInfo & getFrameInfo()
getFrameInfo - Return the frame info object for the current function.
Definition: MachineFunction.h:657
llvm::MachineOperand::isEarlyClobber
bool isEarlyClobber() const
Definition: MachineOperand.h:436
llvm::MachineBasicBlock::getParent
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
Definition: MachineBasicBlock.h:225
llvm::MachineOperand::isRegMask
bool isRegMask() const
isRegMask - Tests if this is a MO_RegisterMask operand.
Definition: MachineOperand.h:345
function
print Print MemDeps of function
Definition: MemDepPrinter.cpp:83
llvm::MachineInstrBuilder::addReg
const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
Definition: MachineInstrBuilder.h:97
llvm::MachineOperand::getReg
Register getReg() const
getReg - Returns the register number.
Definition: MachineOperand.h:360
llvm::MachineBasicBlock::pred_empty
bool pred_empty() const
Definition: MachineBasicBlock.h:331
llvm::MachineFunction
Definition: MachineFunction.h:241
llvm::size
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
Definition: STLExtras.h:1581
llvm::MachineBasicBlock::succ_empty
bool succ_empty() const
Definition: MachineBasicBlock.h:347
llvm::AArch64::RM
@ RM
Definition: AArch64ISelLowering.h:478
llvm::MachineBasicBlock::getFirstTerminator
iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
Definition: MachineBasicBlock.cpp:241
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::any_of
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1607
llvm::AnalysisUsage::setPreservesCFG
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:253
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:57
llvm::HexagonInstrInfo::loadRegFromStackSlot
void loadRegFromStackSlot(MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI, Register DestReg, int FrameIndex, const TargetRegisterClass *RC, const TargetRegisterInfo *TRI) const override
Load the specified register of the given register class from the specified stack frame index.
Definition: HexagonInstrInfo.cpp:956
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:134
if
if(llvm_vc STREQUAL "") set(fake_version_inc "$
Definition: CMakeLists.txt:14
llvm::ms_demangle::IntrinsicFunctionKind::New
@ New
uint32_t
llvm::MachineOperand::setIsRenamable
void setIsRenamable(bool Val=true)
Definition: MachineOperand.cpp:136
Compiler.h
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:81
TargetSubtargetInfo.h
llvm::MachineOperand::isDef
bool isDef() const
Definition: MachineOperand.h:375
llvm::SmallSet::insert
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Definition: SmallSet.h:180
llvm::MachineInstr::getParent
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:286
SparseSet.h
IgnoreMissingDefs
static cl::opt< bool > IgnoreMissingDefs("rafast-ignore-missing-defs", cl::Hidden)
llvm::TargetSubtargetInfo
TargetSubtargetInfo - Generic base class for all target subtargets.
Definition: TargetSubtargetInfo.h:59
MRI
unsigned const MachineRegisterInfo * MRI
Definition: AArch64AdvSIMDScalarPass.cpp:105
llvm::Register
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
llvm::MachineOperand::getSubReg
unsigned getSubReg() const
Definition: MachineOperand.h:365
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::BitVector::test
bool test(unsigned Idx) const
Definition: BitVector.h:447
llvm::MachineFunctionProperties::Property::NoPHIs
@ NoPHIs
llvm::allocateAllRegClasses
static bool allocateAllRegClasses(const TargetRegisterInfo &, const TargetRegisterClass &)
Default register class filter function for register allocation.
Definition: RegAllocCommon.h:24
llvm::MachineOperand::readsReg
bool readsReg() const
readsReg - Returns true if this operand reads the previous value of its register.
Definition: MachineOperand.h:458
uint16_t
fastRegAlloc
static RegisterRegAlloc fastRegAlloc("fast", "fast register allocator", createFastRegisterAllocator)
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::end
iterator end()
Definition: DenseMap.h:83
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:325
llvm::MachineBasicBlock::insert
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
Definition: MachineBasicBlock.cpp:1311
llvm::ilist_iterator
Iterator for intrusive lists based on ilist_node.
Definition: ilist_iterator.h:57
MachineFrameInfo.h
llvm::Error
Lightweight error class with error context and mandatory checking.
Definition: Error.h:157
Casting.h
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1541
llvm::MachineRegisterInfo::addPhysRegsUsedFromRegMask
void addPhysRegsUsedFromRegMask(const uint32_t *RegMask)
addPhysRegsUsedFromRegMask - Mark any registers not in RegMask as used.
Definition: MachineRegisterInfo.h:879
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:585
llvm::MachineRegisterInfo::clearVirtRegs
void clearVirtRegs()
clearVirtRegs - Remove all virtual registers (after physreg assignment).
Definition: MachineRegisterInfo.cpp:202
llvm::TargetRegisterInfo::getNumRegClasses
unsigned getNumRegClasses() const
Definition: TargetRegisterInfo.h:733
llvm::MCRegUnitIterator
Definition: MCRegisterInfo.h:677
llvm::MCRegAliasIterator::isValid
bool isValid() const
Definition: MCRegisterInfo.h:805
llvm::MachineFrameInfo
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted.
Definition: MachineFrameInfo.h:107
SmallVector.h
llvm::MachineBasicBlock::begin
iterator begin()
Definition: MachineBasicBlock.h:268
MachineInstrBuilder.h
llvm::BuildMI
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
Definition: MachineInstrBuilder.h:328
llvm::MCRegisterInfo::DiffListIterator::isValid
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
Definition: MCRegisterInfo.h:224
llvm::MachineOperand::setReg
void setReg(Register Reg)
Change the register this operand corresponds to.
Definition: MachineOperand.cpp:55
llvm::MachineOperand::isInternalRead
bool isInternalRead() const
Definition: MachineOperand.h:431
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:43
MachineOperand.h
llvm::SparseSet
SparseSet - Fast set implementation for objects that can be identified by small unsigned keys.
Definition: SparseSet.h:123
llvm::TargetRegisterInfo::getSubReg
MCRegister getSubReg(MCRegister Reg, unsigned Idx) const
Returns the physical register number of sub-register "Index" for physical register RegNo.
Definition: TargetRegisterInfo.h:1094
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
llvm::TargetRegisterClass::hasSubClassEq
bool hasSubClassEq(const TargetRegisterClass *RC) const
Returns true if RC is a sub-class of or equal to this class.
Definition: TargetRegisterInfo.h:126
llvm::Register::virtReg2Index
static unsigned virtReg2Index(Register Reg)
Convert a virtual register number to a 0-based index.
Definition: Register.h:77
isCoalescable
static bool isCoalescable(const MachineInstr &MI)
Definition: RegAllocFast.cpp:703
spill
the custom lowered code happens to be but we shouldn t have to custom lower anything This is probably related to< 2 x i64 > ops being so bad LLVM currently generates stack realignment when it is not necessary needed The problem is that we need to know about stack alignment too before RA runs At that point we don t whether there will be vector spill
Definition: README-SSE.txt:489
raw_ostream.h
MachineFunction.h
llvm::printReg
Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
Definition: TargetRegisterInfo.cpp:110
llvm::MachineInstrBundleIterator
MachineBasicBlock iterator that automatically skips over MIs that are inside bundles (i....
Definition: MachineInstrBundleIterator.h:108
InitializePasses.h
llvm::IndexedMap::resize
void resize(typename StorageT::size_type s)
Definition: IndexedMap.h:59
TargetRegisterInfo.h
Debug.h
llvm::MachineBasicBlock::end
iterator end()
Definition: MachineBasicBlock.h:270
RegAllocRegistry.h
llvm::MCRegAliasIterator
MCRegAliasIterator enumerates all registers aliasing Reg.
Definition: MCRegisterInfo.h:780
llvm::MCRegister
Wrapper class representing physical registers. Should be passed by value.
Definition: MCRegister.h:24
SmallSet.h
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38