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