LLVM  10.0.0svn
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/MC/MCInstrDesc.h"
39 #include "llvm/MC/MCRegisterInfo.h"
40 #include "llvm/Pass.h"
41 #include "llvm/Support/Casting.h"
42 #include "llvm/Support/Compiler.h"
43 #include "llvm/Support/Debug.h"
46 #include <cassert>
47 #include <tuple>
48 #include <vector>
49 
50 using namespace llvm;
51 
52 #define DEBUG_TYPE "regalloc"
53 
54 STATISTIC(NumStores, "Number of stores added");
55 STATISTIC(NumLoads , "Number of loads added");
56 STATISTIC(NumCoalesced, "Number of copies coalesced");
57 
58 static RegisterRegAlloc
59  fastRegAlloc("fast", "fast register allocator", createFastRegisterAllocator);
60 
61 namespace {
62 
63  class RegAllocFast : public MachineFunctionPass {
64  public:
65  static char ID;
66 
67  RegAllocFast() : MachineFunctionPass(ID), StackSlotForVirtReg(-1) {}
68 
69  private:
70  MachineFrameInfo *MFI;
72  const TargetRegisterInfo *TRI;
73  const TargetInstrInfo *TII;
74  RegisterClassInfo RegClassInfo;
75 
76  /// Basic block currently being allocated.
77  MachineBasicBlock *MBB;
78 
79  /// Maps virtual regs to the frame index where these values are spilled.
80  IndexedMap<int, VirtReg2IndexFunctor> StackSlotForVirtReg;
81 
82  /// Everything we know about a live virtual register.
83  struct LiveReg {
84  MachineInstr *LastUse = nullptr; ///< Last instr to use reg.
85  unsigned VirtReg; ///< Virtual register number.
86  MCPhysReg PhysReg = 0; ///< Currently held here.
87  unsigned short LastOpNum = 0; ///< OpNum on LastUse.
88  bool Dirty = false; ///< Register needs spill.
89 
90  explicit LiveReg(unsigned VirtReg) : VirtReg(VirtReg) {}
91 
92  unsigned getSparseSetIndex() const {
93  return Register::virtReg2Index(VirtReg);
94  }
95  };
96 
97  using LiveRegMap = SparseSet<LiveReg>;
98  /// This map contains entries for each virtual register that is currently
99  /// available in a physical register.
100  LiveRegMap LiveVirtRegs;
101 
103 
104  /// Has a bit set for every virtual register for which it was determined
105  /// that it is alive across blocks.
106  BitVector MayLiveAcrossBlocks;
107 
108  /// State of a physical register.
109  enum RegState {
110  /// A disabled register is not available for allocation, but an alias may
111  /// be in use. A register can only be moved out of the disabled state if
112  /// all aliases are disabled.
113  regDisabled,
114 
115  /// A free register is not currently in use and can be allocated
116  /// immediately without checking aliases.
117  regFree,
118 
119  /// A reserved register has been assigned explicitly (e.g., setting up a
120  /// call parameter), and it remains reserved until it is used.
121  regReserved
122 
123  /// A register state may also be a virtual register number, indication
124  /// that the physical register is currently allocated to a virtual
125  /// register. In that case, LiveVirtRegs contains the inverse mapping.
126  };
127 
128  /// Maps each physical register to a RegState enum or a virtual register.
129  std::vector<unsigned> PhysRegState;
130 
131  SmallVector<unsigned, 16> VirtDead;
133 
134  using RegUnitSet = SparseSet<uint16_t, identity<uint16_t>>;
135  /// Set of register units that are used in the current instruction, and so
136  /// cannot be allocated.
137  RegUnitSet UsedInInstr;
138 
139  void setPhysRegState(MCPhysReg PhysReg, unsigned NewState);
140 
141  /// Mark a physreg as used in this instruction.
142  void markRegUsedInInstr(MCPhysReg PhysReg) {
143  for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units)
144  UsedInInstr.insert(*Units);
145  }
146 
147  /// Check if a physreg or any of its aliases are used in this instruction.
148  bool isRegUsedInInstr(MCPhysReg PhysReg) const {
149  for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units)
150  if (UsedInInstr.count(*Units))
151  return true;
152  return false;
153  }
154 
155  enum : unsigned {
156  spillClean = 50,
157  spillDirty = 100,
158  spillPrefBonus = 20,
159  spillImpossible = ~0u
160  };
161 
162  public:
163  StringRef getPassName() const override { return "Fast Register Allocator"; }
164 
165  void getAnalysisUsage(AnalysisUsage &AU) const override {
166  AU.setPreservesCFG();
168  }
169 
170  MachineFunctionProperties getRequiredProperties() const override {
173  }
174 
175  MachineFunctionProperties getSetProperties() const override {
178  }
179 
180  private:
181  bool runOnMachineFunction(MachineFunction &MF) override;
182 
183  void allocateBasicBlock(MachineBasicBlock &MBB);
184  void allocateInstruction(MachineInstr &MI);
185  void handleDebugValue(MachineInstr &MI);
186  void handleThroughOperands(MachineInstr &MI,
187  SmallVectorImpl<unsigned> &VirtDead);
188  bool isLastUseOfLocalReg(const MachineOperand &MO) const;
189 
190  void addKillFlag(const LiveReg &LRI);
191  void killVirtReg(LiveReg &LR);
192  void killVirtReg(unsigned VirtReg);
193  void spillVirtReg(MachineBasicBlock::iterator MI, LiveReg &LR);
194  void spillVirtReg(MachineBasicBlock::iterator MI, unsigned VirtReg);
195 
196  void usePhysReg(MachineOperand &MO);
197  void definePhysReg(MachineBasicBlock::iterator MI, MCPhysReg PhysReg,
198  RegState NewState);
199  unsigned calcSpillCost(MCPhysReg PhysReg) const;
200  void assignVirtToPhysReg(LiveReg &, MCPhysReg PhysReg);
201 
202  LiveRegMap::iterator findLiveVirtReg(unsigned VirtReg) {
203  return LiveVirtRegs.find(Register::virtReg2Index(VirtReg));
204  }
205 
206  LiveRegMap::const_iterator findLiveVirtReg(unsigned VirtReg) const {
207  return LiveVirtRegs.find(Register::virtReg2Index(VirtReg));
208  }
209 
210  void allocVirtReg(MachineInstr &MI, LiveReg &LR, unsigned Hint);
211  void allocVirtRegUndef(MachineOperand &MO);
212  MCPhysReg defineVirtReg(MachineInstr &MI, unsigned OpNum, unsigned VirtReg,
213  unsigned Hint);
214  LiveReg &reloadVirtReg(MachineInstr &MI, unsigned OpNum, unsigned VirtReg,
215  unsigned Hint);
216  void spillAll(MachineBasicBlock::iterator MI, bool OnlyLiveOut);
217  bool setPhysReg(MachineInstr &MI, MachineOperand &MO, MCPhysReg PhysReg);
218 
219  unsigned traceCopies(unsigned VirtReg) const;
220  unsigned traceCopyChain(unsigned Reg) const;
221 
222  int getStackSpaceFor(unsigned VirtReg);
223  void spill(MachineBasicBlock::iterator Before, unsigned VirtReg,
224  MCPhysReg AssignedReg, bool Kill);
225  void reload(MachineBasicBlock::iterator Before, unsigned VirtReg,
226  MCPhysReg PhysReg);
227 
228  bool mayLiveOut(unsigned VirtReg);
229  bool mayLiveIn(unsigned VirtReg);
230 
231  void dumpState();
232  };
233 
234 } // end anonymous namespace
235 
236 char RegAllocFast::ID = 0;
237 
238 INITIALIZE_PASS(RegAllocFast, "regallocfast", "Fast Register Allocator", false,
239  false)
240 
241 void RegAllocFast::setPhysRegState(MCPhysReg PhysReg, unsigned NewState) {
242  PhysRegState[PhysReg] = NewState;
243 }
244 
245 /// This allocates space for the specified virtual register to be held on the
246 /// stack.
247 int RegAllocFast::getStackSpaceFor(unsigned VirtReg) {
248  // Find the location Reg would belong...
249  int SS = StackSlotForVirtReg[VirtReg];
250  // Already has space allocated?
251  if (SS != -1)
252  return SS;
253 
254  // Allocate a new stack object for this spill location...
255  const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);
256  unsigned Size = TRI->getSpillSize(RC);
257  unsigned Align = TRI->getSpillAlignment(RC);
258  int FrameIdx = MFI->CreateSpillStackObject(Size, Align);
259 
260  // Assign the slot.
261  StackSlotForVirtReg[VirtReg] = FrameIdx;
262  return FrameIdx;
263 }
264 
265 /// Returns false if \p VirtReg is known to not live out of the current block.
266 bool RegAllocFast::mayLiveOut(unsigned VirtReg) {
267  if (MayLiveAcrossBlocks.test(Register::virtReg2Index(VirtReg))) {
268  // Cannot be live-out if there are no successors.
269  return !MBB->succ_empty();
270  }
271 
272  // If this block loops back to itself, it would be necessary to check whether
273  // the use comes after the def.
274  if (MBB->isSuccessor(MBB)) {
275  MayLiveAcrossBlocks.set(Register::virtReg2Index(VirtReg));
276  return true;
277  }
278 
279  // See if the first \p Limit uses of the register are all in the current
280  // block.
281  static const unsigned Limit = 8;
282  unsigned C = 0;
283  for (const MachineInstr &UseInst : MRI->reg_nodbg_instructions(VirtReg)) {
284  if (UseInst.getParent() != MBB || ++C >= Limit) {
285  MayLiveAcrossBlocks.set(Register::virtReg2Index(VirtReg));
286  // Cannot be live-out if there are no successors.
287  return !MBB->succ_empty();
288  }
289  }
290 
291  return false;
292 }
293 
294 /// Returns false if \p VirtReg is known to not be live into the current block.
295 bool RegAllocFast::mayLiveIn(unsigned VirtReg) {
296  if (MayLiveAcrossBlocks.test(Register::virtReg2Index(VirtReg)))
297  return !MBB->pred_empty();
298 
299  // See if the first \p Limit def of the register are all in the current block.
300  static const unsigned Limit = 8;
301  unsigned C = 0;
302  for (const MachineInstr &DefInst : MRI->def_instructions(VirtReg)) {
303  if (DefInst.getParent() != MBB || ++C >= Limit) {
304  MayLiveAcrossBlocks.set(Register::virtReg2Index(VirtReg));
305  return !MBB->pred_empty();
306  }
307  }
308 
309  return false;
310 }
311 
312 /// Insert spill instruction for \p AssignedReg before \p Before. Update
313 /// DBG_VALUEs with \p VirtReg operands with the stack slot.
314 void RegAllocFast::spill(MachineBasicBlock::iterator Before, unsigned VirtReg,
315  MCPhysReg AssignedReg, bool Kill) {
316  LLVM_DEBUG(dbgs() << "Spilling " << printReg(VirtReg, TRI)
317  << " in " << printReg(AssignedReg, TRI));
318  int FI = getStackSpaceFor(VirtReg);
319  LLVM_DEBUG(dbgs() << " to stack slot #" << FI << '\n');
320 
321  const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);
322  TII->storeRegToStackSlot(*MBB, Before, AssignedReg, Kill, FI, &RC, TRI);
323  ++NumStores;
324 
325  // If this register is used by DBG_VALUE then insert new DBG_VALUE to
326  // identify spilled location as the place to find corresponding variable's
327  // value.
328  SmallVectorImpl<MachineInstr *> &LRIDbgValues = LiveDbgValueMap[VirtReg];
329  for (MachineInstr *DBG : LRIDbgValues) {
330  MachineInstr *NewDV = buildDbgValueForSpill(*MBB, Before, *DBG, FI);
331  assert(NewDV->getParent() == MBB && "dangling parent pointer");
332  (void)NewDV;
333  LLVM_DEBUG(dbgs() << "Inserting debug info due to spill:\n" << *NewDV);
334  }
335  // Now this register is spilled there is should not be any DBG_VALUE
336  // pointing to this register because they are all pointing to spilled value
337  // now.
338  LRIDbgValues.clear();
339 }
340 
341 /// Insert reload instruction for \p PhysReg before \p Before.
342 void RegAllocFast::reload(MachineBasicBlock::iterator Before, unsigned VirtReg,
343  MCPhysReg PhysReg) {
344  LLVM_DEBUG(dbgs() << "Reloading " << printReg(VirtReg, TRI) << " into "
345  << printReg(PhysReg, TRI) << '\n');
346  int FI = getStackSpaceFor(VirtReg);
347  const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);
348  TII->loadRegFromStackSlot(*MBB, Before, PhysReg, FI, &RC, TRI);
349  ++NumLoads;
350 }
351 
352 /// Return true if MO is the only remaining reference to its virtual register,
353 /// and it is guaranteed to be a block-local register.
354 bool RegAllocFast::isLastUseOfLocalReg(const MachineOperand &MO) const {
355  // If the register has ever been spilled or reloaded, we conservatively assume
356  // it is a global register used in multiple blocks.
357  if (StackSlotForVirtReg[MO.getReg()] != -1)
358  return false;
359 
360  // Check that the use/def chain has exactly one operand - MO.
362  if (&*I != &MO)
363  return false;
364  return ++I == MRI->reg_nodbg_end();
365 }
366 
367 /// Set kill flags on last use of a virtual register.
368 void RegAllocFast::addKillFlag(const LiveReg &LR) {
369  if (!LR.LastUse) return;
370  MachineOperand &MO = LR.LastUse->getOperand(LR.LastOpNum);
371  if (MO.isUse() && !LR.LastUse->isRegTiedToDefOperand(LR.LastOpNum)) {
372  if (MO.getReg() == LR.PhysReg)
373  MO.setIsKill();
374  // else, don't do anything we are problably redefining a
375  // subreg of this register and given we don't track which
376  // lanes are actually dead, we cannot insert a kill flag here.
377  // Otherwise we may end up in a situation like this:
378  // ... = (MO) physreg:sub1, implicit killed physreg
379  // ... <== Here we would allow later pass to reuse physreg:sub1
380  // which is potentially wrong.
381  // LR:sub0 = ...
382  // ... = LR.sub1 <== This is going to use physreg:sub1
383  }
384 }
385 
386 /// Mark virtreg as no longer available.
387 void RegAllocFast::killVirtReg(LiveReg &LR) {
388  addKillFlag(LR);
389  assert(PhysRegState[LR.PhysReg] == LR.VirtReg &&
390  "Broken RegState mapping");
391  setPhysRegState(LR.PhysReg, regFree);
392  LR.PhysReg = 0;
393 }
394 
395 /// Mark virtreg as no longer available.
396 void RegAllocFast::killVirtReg(unsigned VirtReg) {
398  "killVirtReg needs a virtual register");
399  LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg);
400  if (LRI != LiveVirtRegs.end() && LRI->PhysReg)
401  killVirtReg(*LRI);
402 }
403 
404 /// This method spills the value specified by VirtReg into the corresponding
405 /// stack slot if needed.
406 void RegAllocFast::spillVirtReg(MachineBasicBlock::iterator MI,
407  unsigned VirtReg) {
409  "Spilling a physical register is illegal!");
410  LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg);
411  assert(LRI != LiveVirtRegs.end() && LRI->PhysReg &&
412  "Spilling unmapped virtual register");
413  spillVirtReg(MI, *LRI);
414 }
415 
416 /// Do the actual work of spilling.
417 void RegAllocFast::spillVirtReg(MachineBasicBlock::iterator MI, LiveReg &LR) {
418  assert(PhysRegState[LR.PhysReg] == LR.VirtReg && "Broken RegState mapping");
419 
420  if (LR.Dirty) {
421  // If this physreg is used by the instruction, we want to kill it on the
422  // instruction, not on the spill.
423  bool SpillKill = MachineBasicBlock::iterator(LR.LastUse) != MI;
424  LR.Dirty = false;
425 
426  spill(MI, LR.VirtReg, LR.PhysReg, SpillKill);
427 
428  if (SpillKill)
429  LR.LastUse = nullptr; // Don't kill register again
430  }
431  killVirtReg(LR);
432 }
433 
434 /// Spill all dirty virtregs without killing them.
435 void RegAllocFast::spillAll(MachineBasicBlock::iterator MI, bool OnlyLiveOut) {
436  if (LiveVirtRegs.empty())
437  return;
438  // The LiveRegMap is keyed by an unsigned (the virtreg number), so the order
439  // of spilling here is deterministic, if arbitrary.
440  for (LiveReg &LR : LiveVirtRegs) {
441  if (!LR.PhysReg)
442  continue;
443  if (OnlyLiveOut && !mayLiveOut(LR.VirtReg))
444  continue;
445  spillVirtReg(MI, LR);
446  }
447  LiveVirtRegs.clear();
448 }
449 
450 /// Handle the direct use of a physical register. Check that the register is
451 /// not used by a virtreg. Kill the physreg, marking it free. This may add
452 /// implicit kills to MO->getParent() and invalidate MO.
453 void RegAllocFast::usePhysReg(MachineOperand &MO) {
454  // Ignore undef uses.
455  if (MO.isUndef())
456  return;
457 
458  Register PhysReg = MO.getReg();
459  assert(Register::isPhysicalRegister(PhysReg) && "Bad usePhysReg operand");
460 
461  markRegUsedInInstr(PhysReg);
462  switch (PhysRegState[PhysReg]) {
463  case regDisabled:
464  break;
465  case regReserved:
466  PhysRegState[PhysReg] = regFree;
468  case regFree:
469  MO.setIsKill();
470  return;
471  default:
472  // The physreg was allocated to a virtual register. That means the value we
473  // wanted has been clobbered.
474  llvm_unreachable("Instruction uses an allocated register");
475  }
476 
477  // Maybe a superregister is reserved?
478  for (MCRegAliasIterator AI(PhysReg, TRI, false); AI.isValid(); ++AI) {
479  MCPhysReg Alias = *AI;
480  switch (PhysRegState[Alias]) {
481  case regDisabled:
482  break;
483  case regReserved:
484  // Either PhysReg is a subregister of Alias and we mark the
485  // whole register as free, or PhysReg is the superregister of
486  // Alias and we mark all the aliases as disabled before freeing
487  // PhysReg.
488  // In the latter case, since PhysReg was disabled, this means that
489  // its value is defined only by physical sub-registers. This check
490  // is performed by the assert of the default case in this loop.
491  // Note: The value of the superregister may only be partial
492  // defined, that is why regDisabled is a valid state for aliases.
493  assert((TRI->isSuperRegister(PhysReg, Alias) ||
494  TRI->isSuperRegister(Alias, PhysReg)) &&
495  "Instruction is not using a subregister of a reserved register");
497  case regFree:
498  if (TRI->isSuperRegister(PhysReg, Alias)) {
499  // Leave the superregister in the working set.
500  setPhysRegState(Alias, regFree);
501  MO.getParent()->addRegisterKilled(Alias, TRI, true);
502  return;
503  }
504  // Some other alias was in the working set - clear it.
505  setPhysRegState(Alias, regDisabled);
506  break;
507  default:
508  llvm_unreachable("Instruction uses an alias of an allocated register");
509  }
510  }
511 
512  // All aliases are disabled, bring register into working set.
513  setPhysRegState(PhysReg, regFree);
514  MO.setIsKill();
515 }
516 
517 /// Mark PhysReg as reserved or free after spilling any virtregs. This is very
518 /// similar to defineVirtReg except the physreg is reserved instead of
519 /// allocated.
520 void RegAllocFast::definePhysReg(MachineBasicBlock::iterator MI,
521  MCPhysReg PhysReg, RegState NewState) {
522  markRegUsedInInstr(PhysReg);
523  switch (unsigned VirtReg = PhysRegState[PhysReg]) {
524  case regDisabled:
525  break;
526  default:
527  spillVirtReg(MI, VirtReg);
529  case regFree:
530  case regReserved:
531  setPhysRegState(PhysReg, NewState);
532  return;
533  }
534 
535  // This is a disabled register, disable all aliases.
536  setPhysRegState(PhysReg, NewState);
537  for (MCRegAliasIterator AI(PhysReg, TRI, false); AI.isValid(); ++AI) {
538  MCPhysReg Alias = *AI;
539  switch (unsigned VirtReg = PhysRegState[Alias]) {
540  case regDisabled:
541  break;
542  default:
543  spillVirtReg(MI, VirtReg);
545  case regFree:
546  case regReserved:
547  setPhysRegState(Alias, regDisabled);
548  if (TRI->isSuperRegister(PhysReg, Alias))
549  return;
550  break;
551  }
552  }
553 }
554 
555 /// Return the cost of spilling clearing out PhysReg and aliases so it is free
556 /// for allocation. Returns 0 when PhysReg is free or disabled with all aliases
557 /// disabled - it can be allocated directly.
558 /// \returns spillImpossible when PhysReg or an alias can't be spilled.
559 unsigned RegAllocFast::calcSpillCost(MCPhysReg PhysReg) const {
560  if (isRegUsedInInstr(PhysReg)) {
561  LLVM_DEBUG(dbgs() << printReg(PhysReg, TRI)
562  << " is already used in instr.\n");
563  return spillImpossible;
564  }
565  switch (unsigned VirtReg = PhysRegState[PhysReg]) {
566  case regDisabled:
567  break;
568  case regFree:
569  return 0;
570  case regReserved:
571  LLVM_DEBUG(dbgs() << printReg(VirtReg, TRI) << " corresponding "
572  << printReg(PhysReg, TRI) << " is reserved already.\n");
573  return spillImpossible;
574  default: {
575  LiveRegMap::const_iterator LRI = findLiveVirtReg(VirtReg);
576  assert(LRI != LiveVirtRegs.end() && LRI->PhysReg &&
577  "Missing VirtReg entry");
578  return LRI->Dirty ? spillDirty : spillClean;
579  }
580  }
581 
582  // This is a disabled register, add up cost of aliases.
583  LLVM_DEBUG(dbgs() << printReg(PhysReg, TRI) << " is disabled.\n");
584  unsigned Cost = 0;
585  for (MCRegAliasIterator AI(PhysReg, TRI, false); AI.isValid(); ++AI) {
586  MCPhysReg Alias = *AI;
587  switch (unsigned VirtReg = PhysRegState[Alias]) {
588  case regDisabled:
589  break;
590  case regFree:
591  ++Cost;
592  break;
593  case regReserved:
594  return spillImpossible;
595  default: {
596  LiveRegMap::const_iterator LRI = findLiveVirtReg(VirtReg);
597  assert(LRI != LiveVirtRegs.end() && LRI->PhysReg &&
598  "Missing VirtReg entry");
599  Cost += LRI->Dirty ? spillDirty : spillClean;
600  break;
601  }
602  }
603  }
604  return Cost;
605 }
606 
607 /// This method updates local state so that we know that PhysReg is the
608 /// proper container for VirtReg now. The physical register must not be used
609 /// for anything else when this is called.
610 void RegAllocFast::assignVirtToPhysReg(LiveReg &LR, MCPhysReg PhysReg) {
611  unsigned VirtReg = LR.VirtReg;
612  LLVM_DEBUG(dbgs() << "Assigning " << printReg(VirtReg, TRI) << " to "
613  << printReg(PhysReg, TRI) << '\n');
614  assert(LR.PhysReg == 0 && "Already assigned a physreg");
615  assert(PhysReg != 0 && "Trying to assign no register");
616  LR.PhysReg = PhysReg;
617  setPhysRegState(PhysReg, VirtReg);
618 }
619 
620 static bool isCoalescable(const MachineInstr &MI) {
621  return MI.isFullCopy();
622 }
623 
624 unsigned RegAllocFast::traceCopyChain(unsigned Reg) const {
625  static const unsigned ChainLengthLimit = 3;
626  unsigned C = 0;
627  do {
629  return Reg;
631 
632  MachineInstr *VRegDef = MRI->getUniqueVRegDef(Reg);
633  if (!VRegDef || !isCoalescable(*VRegDef))
634  return 0;
635  Reg = VRegDef->getOperand(1).getReg();
636  } while (++C <= ChainLengthLimit);
637  return 0;
638 }
639 
640 /// Check if any of \p VirtReg's definitions is a copy. If it is follow the
641 /// chain of copies to check whether we reach a physical register we can
642 /// coalesce with.
643 unsigned RegAllocFast::traceCopies(unsigned VirtReg) const {
644  static const unsigned DefLimit = 3;
645  unsigned C = 0;
646  for (const MachineInstr &MI : MRI->def_instructions(VirtReg)) {
647  if (isCoalescable(MI)) {
648  Register Reg = MI.getOperand(1).getReg();
649  Reg = traceCopyChain(Reg);
650  if (Reg != 0)
651  return Reg;
652  }
653 
654  if (++C >= DefLimit)
655  break;
656  }
657  return 0;
658 }
659 
660 /// Allocates a physical register for VirtReg.
661 void RegAllocFast::allocVirtReg(MachineInstr &MI, LiveReg &LR, unsigned Hint0) {
662  const unsigned VirtReg = LR.VirtReg;
663 
665  "Can only allocate virtual registers");
666 
667  const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);
668  LLVM_DEBUG(dbgs() << "Search register for " << printReg(VirtReg)
669  << " in class " << TRI->getRegClassName(&RC)
670  << " with hint " << printReg(Hint0, TRI) << '\n');
671 
672  // Take hint when possible.
673  if (Register::isPhysicalRegister(Hint0) && MRI->isAllocatable(Hint0) &&
674  RC.contains(Hint0)) {
675  // Ignore the hint if we would have to spill a dirty register.
676  unsigned Cost = calcSpillCost(Hint0);
677  if (Cost < spillDirty) {
678  LLVM_DEBUG(dbgs() << "\tPreferred Register 1: " << printReg(Hint0, TRI)
679  << '\n');
680  if (Cost)
681  definePhysReg(MI, Hint0, regFree);
682  assignVirtToPhysReg(LR, Hint0);
683  return;
684  } else {
685  LLVM_DEBUG(dbgs() << "\tPreferred Register 1: " << printReg(Hint0, TRI)
686  << "occupied\n");
687  }
688  } else {
689  Hint0 = 0;
690  }
691 
692  // Try other hint.
693  unsigned Hint1 = traceCopies(VirtReg);
694  if (Register::isPhysicalRegister(Hint1) && MRI->isAllocatable(Hint1) &&
695  RC.contains(Hint1) && !isRegUsedInInstr(Hint1)) {
696  // Ignore the hint if we would have to spill a dirty register.
697  unsigned Cost = calcSpillCost(Hint1);
698  if (Cost < spillDirty) {
699  LLVM_DEBUG(dbgs() << "\tPreferred Register 0: " << printReg(Hint1, TRI)
700  << '\n');
701  if (Cost)
702  definePhysReg(MI, Hint1, regFree);
703  assignVirtToPhysReg(LR, Hint1);
704  return;
705  } else {
706  LLVM_DEBUG(dbgs() << "\tPreferred Register 0: " << printReg(Hint1, TRI)
707  << "occupied\n");
708  }
709  } else {
710  Hint1 = 0;
711  }
712 
713  MCPhysReg BestReg = 0;
714  unsigned BestCost = spillImpossible;
715  ArrayRef<MCPhysReg> AllocationOrder = RegClassInfo.getOrder(&RC);
716  for (MCPhysReg PhysReg : AllocationOrder) {
717  LLVM_DEBUG(dbgs() << "\tRegister: " << printReg(PhysReg, TRI) << ' ');
718  unsigned Cost = calcSpillCost(PhysReg);
719  LLVM_DEBUG(dbgs() << "Cost: " << Cost << " BestCost: " << BestCost << '\n');
720  // Immediate take a register with cost 0.
721  if (Cost == 0) {
722  assignVirtToPhysReg(LR, PhysReg);
723  return;
724  }
725 
726  if (PhysReg == Hint1 || PhysReg == Hint0)
727  Cost -= spillPrefBonus;
728 
729  if (Cost < BestCost) {
730  BestReg = PhysReg;
731  BestCost = Cost;
732  }
733  }
734 
735  if (!BestReg) {
736  // Nothing we can do: Report an error and keep going with an invalid
737  // allocation.
738  if (MI.isInlineAsm())
739  MI.emitError("inline assembly requires more registers than available");
740  else
741  MI.emitError("ran out of registers during register allocation");
742  definePhysReg(MI, *AllocationOrder.begin(), regFree);
743  assignVirtToPhysReg(LR, *AllocationOrder.begin());
744  return;
745  }
746 
747  definePhysReg(MI, BestReg, regFree);
748  assignVirtToPhysReg(LR, BestReg);
749 }
750 
751 void RegAllocFast::allocVirtRegUndef(MachineOperand &MO) {
752  assert(MO.isUndef() && "expected undef use");
753  Register VirtReg = MO.getReg();
754  assert(Register::isVirtualRegister(VirtReg) && "Expected virtreg");
755 
756  LiveRegMap::const_iterator LRI = findLiveVirtReg(VirtReg);
757  MCPhysReg PhysReg;
758  if (LRI != LiveVirtRegs.end() && LRI->PhysReg) {
759  PhysReg = LRI->PhysReg;
760  } else {
761  const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);
762  ArrayRef<MCPhysReg> AllocationOrder = RegClassInfo.getOrder(&RC);
763  assert(!AllocationOrder.empty() && "Allocation order must not be empty");
764  PhysReg = AllocationOrder[0];
765  }
766 
767  unsigned SubRegIdx = MO.getSubReg();
768  if (SubRegIdx != 0) {
769  PhysReg = TRI->getSubReg(PhysReg, SubRegIdx);
770  MO.setSubReg(0);
771  }
772  MO.setReg(PhysReg);
773  MO.setIsRenamable(true);
774 }
775 
776 /// Allocates a register for VirtReg and mark it as dirty.
777 MCPhysReg RegAllocFast::defineVirtReg(MachineInstr &MI, unsigned OpNum,
778  unsigned VirtReg, unsigned Hint) {
779  assert(Register::isVirtualRegister(VirtReg) && "Not a virtual register");
780  LiveRegMap::iterator LRI;
781  bool New;
782  std::tie(LRI, New) = LiveVirtRegs.insert(LiveReg(VirtReg));
783  if (!LRI->PhysReg) {
784  // If there is no hint, peek at the only use of this register.
785  if ((!Hint || !Register::isPhysicalRegister(Hint)) &&
786  MRI->hasOneNonDBGUse(VirtReg)) {
787  const MachineInstr &UseMI = *MRI->use_instr_nodbg_begin(VirtReg);
788  // It's a copy, use the destination register as a hint.
789  if (UseMI.isCopyLike())
790  Hint = UseMI.getOperand(0).getReg();
791  }
792  allocVirtReg(MI, *LRI, Hint);
793  } else if (LRI->LastUse) {
794  // Redefining a live register - kill at the last use, unless it is this
795  // instruction defining VirtReg multiple times.
796  if (LRI->LastUse != &MI || LRI->LastUse->getOperand(LRI->LastOpNum).isUse())
797  addKillFlag(*LRI);
798  }
799  assert(LRI->PhysReg && "Register not assigned");
800  LRI->LastUse = &MI;
801  LRI->LastOpNum = OpNum;
802  LRI->Dirty = true;
803  markRegUsedInInstr(LRI->PhysReg);
804  return LRI->PhysReg;
805 }
806 
807 /// Make sure VirtReg is available in a physreg and return it.
808 RegAllocFast::LiveReg &RegAllocFast::reloadVirtReg(MachineInstr &MI,
809  unsigned OpNum,
810  unsigned VirtReg,
811  unsigned Hint) {
812  assert(Register::isVirtualRegister(VirtReg) && "Not a virtual register");
813  LiveRegMap::iterator LRI;
814  bool New;
815  std::tie(LRI, New) = LiveVirtRegs.insert(LiveReg(VirtReg));
816  MachineOperand &MO = MI.getOperand(OpNum);
817  if (!LRI->PhysReg) {
818  allocVirtReg(MI, *LRI, Hint);
819  reload(MI, VirtReg, LRI->PhysReg);
820  } else if (LRI->Dirty) {
821  if (isLastUseOfLocalReg(MO)) {
822  LLVM_DEBUG(dbgs() << "Killing last use: " << MO << '\n');
823  if (MO.isUse())
824  MO.setIsKill();
825  else
826  MO.setIsDead();
827  } else if (MO.isKill()) {
828  LLVM_DEBUG(dbgs() << "Clearing dubious kill: " << MO << '\n');
829  MO.setIsKill(false);
830  } else if (MO.isDead()) {
831  LLVM_DEBUG(dbgs() << "Clearing dubious dead: " << MO << '\n');
832  MO.setIsDead(false);
833  }
834  } else if (MO.isKill()) {
835  // We must remove kill flags from uses of reloaded registers because the
836  // register would be killed immediately, and there might be a second use:
837  // %foo = OR killed %x, %x
838  // This would cause a second reload of %x into a different register.
839  LLVM_DEBUG(dbgs() << "Clearing clean kill: " << MO << '\n');
840  MO.setIsKill(false);
841  } else if (MO.isDead()) {
842  LLVM_DEBUG(dbgs() << "Clearing clean dead: " << MO << '\n');
843  MO.setIsDead(false);
844  }
845  assert(LRI->PhysReg && "Register not assigned");
846  LRI->LastUse = &MI;
847  LRI->LastOpNum = OpNum;
848  markRegUsedInInstr(LRI->PhysReg);
849  return *LRI;
850 }
851 
852 /// Changes operand OpNum in MI the refer the PhysReg, considering subregs. This
853 /// may invalidate any operand pointers. Return true if the operand kills its
854 /// register.
855 bool RegAllocFast::setPhysReg(MachineInstr &MI, MachineOperand &MO,
856  MCPhysReg PhysReg) {
857  bool Dead = MO.isDead();
858  if (!MO.getSubReg()) {
859  MO.setReg(PhysReg);
860  MO.setIsRenamable(true);
861  return MO.isKill() || Dead;
862  }
863 
864  // Handle subregister index.
865  MO.setReg(PhysReg ? TRI->getSubReg(PhysReg, MO.getSubReg()) : Register());
866  MO.setIsRenamable(true);
867  MO.setSubReg(0);
868 
869  // A kill flag implies killing the full register. Add corresponding super
870  // register kill.
871  if (MO.isKill()) {
872  MI.addRegisterKilled(PhysReg, TRI, true);
873  return true;
874  }
875 
876  // A <def,read-undef> of a sub-register requires an implicit def of the full
877  // register.
878  if (MO.isDef() && MO.isUndef())
879  MI.addRegisterDefined(PhysReg, TRI);
880 
881  return Dead;
882 }
883 
884 // Handles special instruction operand like early clobbers and tied ops when
885 // there are additional physreg defines.
886 void RegAllocFast::handleThroughOperands(MachineInstr &MI,
887  SmallVectorImpl<unsigned> &VirtDead) {
888  LLVM_DEBUG(dbgs() << "Scanning for through registers:");
889  SmallSet<unsigned, 8> ThroughRegs;
890  for (const MachineOperand &MO : MI.operands()) {
891  if (!MO.isReg()) continue;
892  Register Reg = MO.getReg();
893  if (!Register::isVirtualRegister(Reg))
894  continue;
895  if (MO.isEarlyClobber() || (MO.isUse() && MO.isTied()) ||
896  (MO.getSubReg() && MI.readsVirtualRegister(Reg))) {
897  if (ThroughRegs.insert(Reg).second)
898  LLVM_DEBUG(dbgs() << ' ' << printReg(Reg));
899  }
900  }
901 
902  // If any physreg defines collide with preallocated through registers,
903  // we must spill and reallocate.
904  LLVM_DEBUG(dbgs() << "\nChecking for physdef collisions.\n");
905  for (const MachineOperand &MO : MI.operands()) {
906  if (!MO.isReg() || !MO.isDef()) continue;
907  Register Reg = MO.getReg();
908  if (!Reg || !Register::isPhysicalRegister(Reg))
909  continue;
910  markRegUsedInInstr(Reg);
911  for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) {
912  if (ThroughRegs.count(PhysRegState[*AI]))
913  definePhysReg(MI, *AI, regFree);
914  }
915  }
916 
917  SmallVector<unsigned, 8> PartialDefs;
918  LLVM_DEBUG(dbgs() << "Allocating tied uses.\n");
919  for (unsigned I = 0, E = MI.getNumOperands(); I != E; ++I) {
920  MachineOperand &MO = MI.getOperand(I);
921  if (!MO.isReg()) continue;
922  Register Reg = MO.getReg();
923  if (!Register::isVirtualRegister(Reg))
924  continue;
925  if (MO.isUse()) {
926  if (!MO.isTied()) continue;
927  LLVM_DEBUG(dbgs() << "Operand " << I << "(" << MO
928  << ") is tied to operand " << MI.findTiedOperandIdx(I)
929  << ".\n");
930  LiveReg &LR = reloadVirtReg(MI, I, Reg, 0);
931  MCPhysReg PhysReg = LR.PhysReg;
932  setPhysReg(MI, MO, PhysReg);
933  // Note: we don't update the def operand yet. That would cause the normal
934  // def-scan to attempt spilling.
935  } else if (MO.getSubReg() && MI.readsVirtualRegister(Reg)) {
936  LLVM_DEBUG(dbgs() << "Partial redefine: " << MO << '\n');
937  // Reload the register, but don't assign to the operand just yet.
938  // That would confuse the later phys-def processing pass.
939  LiveReg &LR = reloadVirtReg(MI, I, Reg, 0);
940  PartialDefs.push_back(LR.PhysReg);
941  }
942  }
943 
944  LLVM_DEBUG(dbgs() << "Allocating early clobbers.\n");
945  for (unsigned I = 0, E = MI.getNumOperands(); I != E; ++I) {
946  const MachineOperand &MO = MI.getOperand(I);
947  if (!MO.isReg()) continue;
948  Register Reg = MO.getReg();
949  if (!Register::isVirtualRegister(Reg))
950  continue;
951  if (!MO.isEarlyClobber())
952  continue;
953  // Note: defineVirtReg may invalidate MO.
954  MCPhysReg PhysReg = defineVirtReg(MI, I, Reg, 0);
955  if (setPhysReg(MI, MI.getOperand(I), PhysReg))
956  VirtDead.push_back(Reg);
957  }
958 
959  // Restore UsedInInstr to a state usable for allocating normal virtual uses.
960  UsedInInstr.clear();
961  for (const MachineOperand &MO : MI.operands()) {
962  if (!MO.isReg() || (MO.isDef() && !MO.isEarlyClobber())) continue;
963  Register Reg = MO.getReg();
964  if (!Reg || !Register::isPhysicalRegister(Reg))
965  continue;
966  LLVM_DEBUG(dbgs() << "\tSetting " << printReg(Reg, TRI)
967  << " as used in instr\n");
968  markRegUsedInInstr(Reg);
969  }
970 
971  // Also mark PartialDefs as used to avoid reallocation.
972  for (unsigned PartialDef : PartialDefs)
973  markRegUsedInInstr(PartialDef);
974 }
975 
976 #ifndef NDEBUG
977 void RegAllocFast::dumpState() {
978  for (unsigned Reg = 1, E = TRI->getNumRegs(); Reg != E; ++Reg) {
979  if (PhysRegState[Reg] == regDisabled) continue;
980  dbgs() << " " << printReg(Reg, TRI);
981  switch(PhysRegState[Reg]) {
982  case regFree:
983  break;
984  case regReserved:
985  dbgs() << "*";
986  break;
987  default: {
988  dbgs() << '=' << printReg(PhysRegState[Reg]);
989  LiveRegMap::iterator LRI = findLiveVirtReg(PhysRegState[Reg]);
990  assert(LRI != LiveVirtRegs.end() && LRI->PhysReg &&
991  "Missing VirtReg entry");
992  if (LRI->Dirty)
993  dbgs() << "*";
994  assert(LRI->PhysReg == Reg && "Bad inverse map");
995  break;
996  }
997  }
998  }
999  dbgs() << '\n';
1000  // Check that LiveVirtRegs is the inverse.
1001  for (LiveRegMap::iterator i = LiveVirtRegs.begin(),
1002  e = LiveVirtRegs.end(); i != e; ++i) {
1003  if (!i->PhysReg)
1004  continue;
1005  assert(Register::isVirtualRegister(i->VirtReg) && "Bad map key");
1006  assert(Register::isPhysicalRegister(i->PhysReg) && "Bad map value");
1007  assert(PhysRegState[i->PhysReg] == i->VirtReg && "Bad inverse map");
1008  }
1009 }
1010 #endif
1011 
1012 void RegAllocFast::allocateInstruction(MachineInstr &MI) {
1013  const MCInstrDesc &MCID = MI.getDesc();
1014 
1015  // If this is a copy, we may be able to coalesce.
1016  unsigned CopySrcReg = 0;
1017  unsigned CopyDstReg = 0;
1018  unsigned CopySrcSub = 0;
1019  unsigned CopyDstSub = 0;
1020  if (MI.isCopy()) {
1021  CopyDstReg = MI.getOperand(0).getReg();
1022  CopySrcReg = MI.getOperand(1).getReg();
1023  CopyDstSub = MI.getOperand(0).getSubReg();
1024  CopySrcSub = MI.getOperand(1).getSubReg();
1025  }
1026 
1027  // Track registers used by instruction.
1028  UsedInInstr.clear();
1029 
1030  // First scan.
1031  // Mark physreg uses and early clobbers as used.
1032  // Find the end of the virtreg operands
1033  unsigned VirtOpEnd = 0;
1034  bool hasTiedOps = false;
1035  bool hasEarlyClobbers = false;
1036  bool hasPartialRedefs = false;
1037  bool hasPhysDefs = false;
1038  for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
1039  MachineOperand &MO = MI.getOperand(i);
1040  // Make sure MRI knows about registers clobbered by regmasks.
1041  if (MO.isRegMask()) {
1043  continue;
1044  }
1045  if (!MO.isReg()) continue;
1046  Register Reg = MO.getReg();
1047  if (!Reg) continue;
1048  if (Register::isVirtualRegister(Reg)) {
1049  VirtOpEnd = i+1;
1050  if (MO.isUse()) {
1051  hasTiedOps = hasTiedOps ||
1052  MCID.getOperandConstraint(i, MCOI::TIED_TO) != -1;
1053  } else {
1054  if (MO.isEarlyClobber())
1055  hasEarlyClobbers = true;
1056  if (MO.getSubReg() && MI.readsVirtualRegister(Reg))
1057  hasPartialRedefs = true;
1058  }
1059  continue;
1060  }
1061  if (!MRI->isAllocatable(Reg)) continue;
1062  if (MO.isUse()) {
1063  usePhysReg(MO);
1064  } else if (MO.isEarlyClobber()) {
1065  definePhysReg(MI, Reg,
1066  (MO.isImplicit() || MO.isDead()) ? regFree : regReserved);
1067  hasEarlyClobbers = true;
1068  } else
1069  hasPhysDefs = true;
1070  }
1071 
1072  // The instruction may have virtual register operands that must be allocated
1073  // the same register at use-time and def-time: early clobbers and tied
1074  // operands. If there are also physical defs, these registers must avoid
1075  // both physical defs and uses, making them more constrained than normal
1076  // operands.
1077  // Similarly, if there are multiple defs and tied operands, we must make
1078  // sure the same register is allocated to uses and defs.
1079  // We didn't detect inline asm tied operands above, so just make this extra
1080  // pass for all inline asm.
1081  if (MI.isInlineAsm() || hasEarlyClobbers || hasPartialRedefs ||
1082  (hasTiedOps && (hasPhysDefs || MCID.getNumDefs() > 1))) {
1083  handleThroughOperands(MI, VirtDead);
1084  // Don't attempt coalescing when we have funny stuff going on.
1085  CopyDstReg = 0;
1086  // Pretend we have early clobbers so the use operands get marked below.
1087  // This is not necessary for the common case of a single tied use.
1088  hasEarlyClobbers = true;
1089  }
1090 
1091  // Second scan.
1092  // Allocate virtreg uses.
1093  bool HasUndefUse = false;
1094  for (unsigned I = 0; I != VirtOpEnd; ++I) {
1095  MachineOperand &MO = MI.getOperand(I);
1096  if (!MO.isReg()) continue;
1097  Register Reg = MO.getReg();
1098  if (!Register::isVirtualRegister(Reg))
1099  continue;
1100  if (MO.isUse()) {
1101  if (MO.isUndef()) {
1102  HasUndefUse = true;
1103  // There is no need to allocate a register for an undef use.
1104  continue;
1105  }
1106 
1107  // Populate MayLiveAcrossBlocks in case the use block is allocated before
1108  // the def block (removing the vreg uses).
1109  mayLiveIn(Reg);
1110 
1111  LiveReg &LR = reloadVirtReg(MI, I, Reg, CopyDstReg);
1112  MCPhysReg PhysReg = LR.PhysReg;
1113  CopySrcReg = (CopySrcReg == Reg || CopySrcReg == PhysReg) ? PhysReg : 0;
1114  if (setPhysReg(MI, MO, PhysReg))
1115  killVirtReg(LR);
1116  }
1117  }
1118 
1119  // Allocate undef operands. This is a separate step because in a situation
1120  // like ` = OP undef %X, %X` both operands need the same register assign
1121  // so we should perform the normal assignment first.
1122  if (HasUndefUse) {
1123  for (MachineOperand &MO : MI.uses()) {
1124  if (!MO.isReg() || !MO.isUse())
1125  continue;
1126  Register Reg = MO.getReg();
1127  if (!Register::isVirtualRegister(Reg))
1128  continue;
1129 
1130  assert(MO.isUndef() && "Should only have undef virtreg uses left");
1131  allocVirtRegUndef(MO);
1132  }
1133  }
1134 
1135  // Track registers defined by instruction - early clobbers and tied uses at
1136  // this point.
1137  UsedInInstr.clear();
1138  if (hasEarlyClobbers) {
1139  for (const MachineOperand &MO : MI.operands()) {
1140  if (!MO.isReg()) continue;
1141  Register Reg = MO.getReg();
1142  if (!Reg || !Register::isPhysicalRegister(Reg))
1143  continue;
1144  // Look for physreg defs and tied uses.
1145  if (!MO.isDef() && !MO.isTied()) continue;
1146  markRegUsedInInstr(Reg);
1147  }
1148  }
1149 
1150  unsigned DefOpEnd = MI.getNumOperands();
1151  if (MI.isCall()) {
1152  // Spill all virtregs before a call. This serves one purpose: If an
1153  // exception is thrown, the landing pad is going to expect to find
1154  // registers in their spill slots.
1155  // Note: although this is appealing to just consider all definitions
1156  // as call-clobbered, this is not correct because some of those
1157  // definitions may be used later on and we do not want to reuse
1158  // those for virtual registers in between.
1159  LLVM_DEBUG(dbgs() << " Spilling remaining registers before call.\n");
1160  spillAll(MI, /*OnlyLiveOut*/ false);
1161  }
1162 
1163  // Third scan.
1164  // Mark all physreg defs as used before allocating virtreg defs.
1165  for (unsigned I = 0; I != DefOpEnd; ++I) {
1166  const MachineOperand &MO = MI.getOperand(I);
1167  if (!MO.isReg() || !MO.isDef() || !MO.getReg() || MO.isEarlyClobber())
1168  continue;
1169  Register Reg = MO.getReg();
1170 
1171  if (!Reg || !Register::isPhysicalRegister(Reg) || !MRI->isAllocatable(Reg))
1172  continue;
1173  definePhysReg(MI, Reg, MO.isDead() ? regFree : regReserved);
1174  }
1175 
1176  // Fourth scan.
1177  // Allocate defs and collect dead defs.
1178  for (unsigned I = 0; I != DefOpEnd; ++I) {
1179  const MachineOperand &MO = MI.getOperand(I);
1180  if (!MO.isReg() || !MO.isDef() || !MO.getReg() || MO.isEarlyClobber())
1181  continue;
1182  Register Reg = MO.getReg();
1183 
1184  // We have already dealt with phys regs in the previous scan.
1186  continue;
1187  MCPhysReg PhysReg = defineVirtReg(MI, I, Reg, CopySrcReg);
1188  if (setPhysReg(MI, MI.getOperand(I), PhysReg)) {
1189  VirtDead.push_back(Reg);
1190  CopyDstReg = 0; // cancel coalescing;
1191  } else
1192  CopyDstReg = (CopyDstReg == Reg || CopyDstReg == PhysReg) ? PhysReg : 0;
1193  }
1194 
1195  // Kill dead defs after the scan to ensure that multiple defs of the same
1196  // register are allocated identically. We didn't need to do this for uses
1197  // because we are crerating our own kill flags, and they are always at the
1198  // last use.
1199  for (unsigned VirtReg : VirtDead)
1200  killVirtReg(VirtReg);
1201  VirtDead.clear();
1202 
1203  LLVM_DEBUG(dbgs() << "<< " << MI);
1204  if (CopyDstReg && CopyDstReg == CopySrcReg && CopyDstSub == CopySrcSub) {
1205  LLVM_DEBUG(dbgs() << "Mark identity copy for removal\n");
1206  Coalesced.push_back(&MI);
1207  }
1208 }
1209 
1210 void RegAllocFast::handleDebugValue(MachineInstr &MI) {
1211  MachineOperand &MO = MI.getOperand(0);
1212 
1213  // Ignore DBG_VALUEs that aren't based on virtual registers. These are
1214  // mostly constants and frame indices.
1215  if (!MO.isReg())
1216  return;
1217  Register Reg = MO.getReg();
1218  if (!Register::isVirtualRegister(Reg))
1219  return;
1220 
1221  // See if this virtual register has already been allocated to a physical
1222  // register or spilled to a stack slot.
1223  LiveRegMap::iterator LRI = findLiveVirtReg(Reg);
1224  if (LRI != LiveVirtRegs.end() && LRI->PhysReg) {
1225  setPhysReg(MI, MO, LRI->PhysReg);
1226  } else {
1227  int SS = StackSlotForVirtReg[Reg];
1228  if (SS != -1) {
1229  // Modify DBG_VALUE now that the value is in a spill slot.
1230  updateDbgValueForSpill(MI, SS);
1231  LLVM_DEBUG(dbgs() << "Modifying debug info due to spill:" << "\t" << MI);
1232  return;
1233  }
1234 
1235  // We can't allocate a physreg for a DebugValue, sorry!
1236  LLVM_DEBUG(dbgs() << "Unable to allocate vreg used by DBG_VALUE");
1237  MO.setReg(0);
1238  }
1239 
1240  // If Reg hasn't been spilled, put this DBG_VALUE in LiveDbgValueMap so
1241  // that future spills of Reg will have DBG_VALUEs.
1242  LiveDbgValueMap[Reg].push_back(&MI);
1243 }
1244 
1245 void RegAllocFast::allocateBasicBlock(MachineBasicBlock &MBB) {
1246  this->MBB = &MBB;
1247  LLVM_DEBUG(dbgs() << "\nAllocating " << MBB);
1248 
1249  PhysRegState.assign(TRI->getNumRegs(), regDisabled);
1250  assert(LiveVirtRegs.empty() && "Mapping not cleared from last block?");
1251 
1252  MachineBasicBlock::iterator MII = MBB.begin();
1253 
1254  // Add live-in registers as live.
1255  for (const MachineBasicBlock::RegisterMaskPair LI : MBB.liveins())
1256  if (MRI->isAllocatable(LI.PhysReg))
1257  definePhysReg(MII, LI.PhysReg, regReserved);
1258 
1259  VirtDead.clear();
1260  Coalesced.clear();
1261 
1262  // Otherwise, sequentially allocate each instruction in the MBB.
1263  for (MachineInstr &MI : MBB) {
1264  LLVM_DEBUG(
1265  dbgs() << "\n>> " << MI << "Regs:";
1266  dumpState()
1267  );
1268 
1269  // Special handling for debug values. Note that they are not allowed to
1270  // affect codegen of the other instructions in any way.
1271  if (MI.isDebugValue()) {
1272  handleDebugValue(MI);
1273  continue;
1274  }
1275 
1276  allocateInstruction(MI);
1277  }
1278 
1279  // Spill all physical registers holding virtual registers now.
1280  LLVM_DEBUG(dbgs() << "Spilling live registers at end of block.\n");
1281  spillAll(MBB.getFirstTerminator(), /*OnlyLiveOut*/ true);
1282 
1283  // Erase all the coalesced copies. We are delaying it until now because
1284  // LiveVirtRegs might refer to the instrs.
1285  for (MachineInstr *MI : Coalesced)
1286  MBB.erase(MI);
1287  NumCoalesced += Coalesced.size();
1288 
1289  LLVM_DEBUG(MBB.dump());
1290 }
1291 
1292 bool RegAllocFast::runOnMachineFunction(MachineFunction &MF) {
1293  LLVM_DEBUG(dbgs() << "********** FAST REGISTER ALLOCATION **********\n"
1294  << "********** Function: " << MF.getName() << '\n');
1295  MRI = &MF.getRegInfo();
1296  const TargetSubtargetInfo &STI = MF.getSubtarget();
1297  TRI = STI.getRegisterInfo();
1298  TII = STI.getInstrInfo();
1299  MFI = &MF.getFrameInfo();
1300  MRI->freezeReservedRegs(MF);
1301  RegClassInfo.runOnMachineFunction(MF);
1302  UsedInInstr.clear();
1303  UsedInInstr.setUniverse(TRI->getNumRegUnits());
1304 
1305  // initialize the virtual->physical register map to have a 'null'
1306  // mapping for all virtual registers
1307  unsigned NumVirtRegs = MRI->getNumVirtRegs();
1308  StackSlotForVirtReg.resize(NumVirtRegs);
1309  LiveVirtRegs.setUniverse(NumVirtRegs);
1310  MayLiveAcrossBlocks.clear();
1311  MayLiveAcrossBlocks.resize(NumVirtRegs);
1312 
1313  // Loop over all of the basic blocks, eliminating virtual register references
1314  for (MachineBasicBlock &MBB : MF)
1315  allocateBasicBlock(MBB);
1316 
1317  // All machine operands and other references to virtual registers have been
1318  // replaced. Remove the virtual registers.
1319  MRI->clearVirtRegs();
1320 
1321  StackSlotForVirtReg.clear();
1322  LiveDbgValueMap.clear();
1323  return true;
1324 }
1325 
1327  return new RegAllocFast();
1328 }
void resize(unsigned N, bool t=false)
resize - Grow or shrink the bitvector.
Definition: BitVector.h:371
bool isRegMask() const
isRegMask - Tests if this is a MO_RegisterMask operand.
uint64_t CallInst * C
static bool isCoalescable(const MachineInstr &MI)
ArrayRef< MCPhysReg > getOrder(const TargetRegisterClass *RC) const
getOrder - Returns the preferred allocation order for RC.
iterator_range< reg_instr_nodbg_iterator > reg_nodbg_instructions(unsigned Reg) const
BitVector & set()
Definition: BitVector.h:397
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
bool contains(unsigned Reg) const
Return true if the specified register is included in this register class.
bool isCall(QueryType Type=AnyInBundle) const
Definition: MachineInstr.h:635
static unsigned virtReg2Index(unsigned Reg)
Convert a virtual register number to a 0-based index.
Definition: Register.h:76
void emitError(StringRef Msg) const
Emit an error referring to the source location of this instruction.
bool isAllocatable(unsigned PhysReg) const
isAllocatable - Returns true when PhysReg belongs to an allocatable register class and it hasn&#39;t been...
This class represents lattice values for constants.
Definition: AllocatorList.h:23
iterator_range< mop_iterator > uses()
Returns a range that includes all operands that are register uses.
Definition: MachineInstr.h:494
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
void push_back(const T &Elt)
Definition: SmallVector.h:211
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:63
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:178
unsigned Reg
This file contains the declarations for metadata subclasses.
unsigned getSubReg() const
bool isInlineAsm() const
bool test(unsigned Idx) const
Definition: BitVector.h:501
bool readsVirtualRegister(Register Reg) const
Return true if the MachineInstr reads the specified virtual register.
STATISTIC(NumFunctions, "Total number of functions")
unsigned const TargetRegisterInfo * TRI
void setIsDead(bool Val=true)
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.
iterator_range< mop_iterator > operands()
Definition: MachineInstr.h:461
bool isCopyLike() const
Return true if the instruction behaves like a copy.
void setIsRenamable(bool Val=true)
unsigned getNumRegUnits() const
Return the number of (native) register units in the target.
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 ...
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
bool isEarlyClobber() const
const char * getRegClassName(const TargetRegisterClass *Class) const
Returns the name of the register class.
unsigned getSpillAlignment(const TargetRegisterClass &RC) const
Return the minimum required alignment in bytes for a spill slot for a register of this class...
void clear()
clear - Removes all bits from the bitvector. Does not change capacity.
Definition: BitVector.h:366
MachineInstr * buildDbgValueForSpill(MachineBasicBlock &BB, MachineBasicBlock::iterator I, const MachineInstr &Orig, int FrameIndex)
Clone a DBG_VALUE whose value has been spilled to FrameIndex.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
const HexagonInstrInfo * TII
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:414
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted...
const MCInstrDesc & getDesc() const
Returns the target instruction descriptor of this MachineInstr.
Definition: MachineInstr.h:408
bool isFullCopy() const
bool addRegisterKilled(Register IncomingReg, const TargetRegisterInfo *RegInfo, bool AddIfNotFound=false)
We have determined MI kills a register.
Register getSubReg(MCRegister Reg, unsigned Idx) const
Returns the physical register number of sub-register "Index" for physical register RegNo...
void setReg(Register Reg)
Change the register this operand corresponds to.
virtual const TargetInstrInfo * getInstrInfo() const
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
uint16_t MCPhysReg
An unsigned integer type large enough to represent all physical registers, but not necessarily virtua...
Definition: MCRegister.h:19
TargetInstrInfo - Interface to description of machine instruction set.
unsigned getNumRegs() const
Return the number of registers this target has (useful for sizing arrays holding per register informa...
MachineInstrBundleIterator< MachineInstr > iterator
unsigned const MachineRegisterInfo * MRI
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
MachineFrameInfo & getFrameInfo()
getFrameInfo - Return the frame info object for the current function.
MachineInstrBuilder & UseMI
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
MCRegAliasIterator enumerates all registers aliasing Reg.
Represent the analysis usage information of a pass.
void resize(typename StorageT::size_type s)
Definition: IndexedMap.h:59
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
bool isSuperRegister(MCRegister RegA, MCRegister RegB) const
Returns true if RegB is a super-register of RegA.
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn&#39;t already there.
Definition: SmallSet.h:180
void runOnMachineFunction(const MachineFunction &MF)
runOnFunction - Prepare to answer questions about MF.
bool isCopy() const
int CreateSpillStackObject(uint64_t Size, unsigned Alignment)
Create a new statically sized stack object that represents a spill slot, returning a nonnegative iden...
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:40
void setIsKill(bool Val=true)
int getOperandConstraint(unsigned OpNum, MCOI::OperandConstraint Constraint) const
Returns the value of the specific constraint if it is set.
Definition: MCInstrDesc.h:202
unsigned findTiedOperandIdx(unsigned OpIdx) const
Given the index of a tied register operand, find the operand it is tied to.
bool isDebugValue() const
MachineOperand class - Representation of each machine instruction operand.
static RegisterRegAlloc fastRegAlloc("fast", "fast register allocator", createFastRegisterAllocator)
Promote Memory to Register
Definition: Mem2Reg.cpp:109
void updateDbgValueForSpill(MachineInstr &Orig, int FrameIndex)
Update a DBG_VALUE whose value has been spilled to FrameIndex.
unsigned getNumDefs() const
Return the number of MachineOperands that are register definitions.
Definition: MCInstrDesc.h:240
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:301
MachineInstr * getUniqueVRegDef(unsigned Reg) const
getUniqueVRegDef - Return the unique machine instr that defines the specified virtual register or nul...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
const uint32_t * getRegMask() const
getRegMask - Returns a bit mask of registers preserved by this RegMask operand.
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
virtual void storeRegToStackSlot(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI, unsigned SrcReg, bool isKill, int FrameIndex, const TargetRegisterClass *RC, const TargetRegisterInfo *TRI) const
Store the specified register of the given register class to the specified stack frame index...
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:256
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
MachineFunctionProperties & set(Property P)
TargetSubtargetInfo - Generic base class for all target subtargets.
Representation of each machine instruction.
Definition: MachineInstr.h:64
reg_nodbg_iterator reg_nodbg_begin(Register RegNo) const
SparseSet - Fast set implmentation for objects that can be identified by small unsigned keys...
Definition: SparseSet.h:123
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
#define I(x, y, z)
Definition: MD5.cpp:58
INITIALIZE_PASS(RegAllocFast, "regallocfast", "Fast Register Allocator", false, false) void RegAllocFast
Pair of physical register and lane mask.
void setSubReg(unsigned subReg)
void addPhysRegsUsedFromRegMask(const uint32_t *RegMask)
addPhysRegsUsedFromRegMask - Mark any registers not in RegMask as used.
uint32_t Size
Definition: Profile.cpp:46
bool isSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB is a successor of this block.
bool hasOneNonDBGUse(unsigned RegNo) const
hasOneNonDBGUse - Return true if there is exactly one non-Debug use of the specified register...
iterator_range< livein_iterator > liveins() const
bool isReg() const
isReg - Tests if this is a MO_Register operand.
static reg_nodbg_iterator reg_nodbg_end()
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
FunctionPass * createFastRegisterAllocator()
FastRegisterAllocation Pass - This pass register allocates as fast as possible.
use_instr_nodbg_iterator use_instr_nodbg_begin(unsigned RegNo) const
void addRegisterDefined(Register Reg, const TargetRegisterInfo *RegInfo=nullptr)
We have determined MI defines a register.
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:69
iterator_range< def_instr_iterator > def_instructions(unsigned Reg) const
#define LLVM_FALLTHROUGH
LLVM_FALLTHROUGH - Mark fallthrough cases in switch statements.
Definition: Compiler.h:258
IRTranslator LLVM IR MI
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
Register getReg() const
getReg - Returns the register number.
#define LLVM_DEBUG(X)
Definition: Debug.h:122
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:416
reg_begin/reg_end - Provide iteration support to walk over all definitions and uses of a register wit...
virtual void loadRegFromStackSlot(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI, unsigned DestReg, int FrameIndex, const TargetRegisterClass *RC, const TargetRegisterInfo *TRI) const
Load the specified register of the given register class from the specified stack frame index...
Properties which a MachineFunction may have at a given point in time.
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
bool empty() const
empty - Check if the array is empty.
Definition: ArrayRef.h:143
bool isImplicit() const
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
Definition: SmallSet.h:164