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