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