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