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