LLVM  9.0.0svn
RegAllocBase.cpp
Go to the documentation of this file.
1 //===- RegAllocBase.cpp - Register Allocator Base Class -------------------===//
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 // This file defines the RegAllocBase class which provides common functionality
10 // for LiveIntervalUnion-based register allocators.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "RegAllocBase.h"
15 #include "Spiller.h"
16 #include "llvm/ADT/SmallVector.h"
17 #include "llvm/ADT/Statistic.h"
25 #include "llvm/Pass.h"
27 #include "llvm/Support/Debug.h"
29 #include "llvm/Support/Timer.h"
31 #include <cassert>
32 
33 using namespace llvm;
34 
35 #define DEBUG_TYPE "regalloc"
36 
37 STATISTIC(NumNewQueued , "Number of new live ranges queued");
38 
39 // Temporary verification option until we can put verification inside
40 // MachineVerifier.
43  cl::Hidden, cl::desc("Verify during register allocation"));
44 
45 const char RegAllocBase::TimerGroupName[] = "regalloc";
46 const char RegAllocBase::TimerGroupDescription[] = "Register Allocation";
47 bool RegAllocBase::VerifyEnabled = false;
48 
49 //===----------------------------------------------------------------------===//
50 // RegAllocBase Implementation
51 //===----------------------------------------------------------------------===//
52 
53 // Pin the vtable to this file.
54 void RegAllocBase::anchor() {}
55 
57  LiveIntervals &lis,
58  LiveRegMatrix &mat) {
59  TRI = &vrm.getTargetRegInfo();
60  MRI = &vrm.getRegInfo();
61  VRM = &vrm;
62  LIS = &lis;
63  Matrix = &mat;
66 }
67 
68 // Visit all the live registers. If they are already assigned to a physical
69 // register, unify them with the corresponding LiveIntervalUnion, otherwise push
70 // them on the priority queue for later assignment.
71 void RegAllocBase::seedLiveRegs() {
72  NamedRegionTimer T("seed", "Seed Live Regs", TimerGroupName,
74  for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
76  if (MRI->reg_nodbg_empty(Reg))
77  continue;
78  enqueue(&LIS->getInterval(Reg));
79  }
80 }
81 
82 // Top-level driver to manage the queue of unassigned VirtRegs and call the
83 // selectOrSplit implementation.
85  seedLiveRegs();
86 
87  // Continue assigning vregs one at a time to available physical registers.
88  while (LiveInterval *VirtReg = dequeue()) {
89  assert(!VRM->hasPhys(VirtReg->reg) && "Register already assigned");
90 
91  // Unused registers can appear when the spiller coalesces snippets.
92  if (MRI->reg_nodbg_empty(VirtReg->reg)) {
93  LLVM_DEBUG(dbgs() << "Dropping unused " << *VirtReg << '\n');
94  aboutToRemoveInterval(*VirtReg);
95  LIS->removeInterval(VirtReg->reg);
96  continue;
97  }
98 
99  // Invalidate all interference queries, live ranges could have changed.
101 
102  // selectOrSplit requests the allocator to return an available physical
103  // register if possible and populate a list of new live intervals that
104  // result from splitting.
105  LLVM_DEBUG(dbgs() << "\nselectOrSplit "
106  << TRI->getRegClassName(MRI->getRegClass(VirtReg->reg))
107  << ':' << *VirtReg << " w=" << VirtReg->weight << '\n');
108 
109  using VirtRegVec = SmallVector<unsigned, 4>;
110 
111  VirtRegVec SplitVRegs;
112  unsigned AvailablePhysReg = selectOrSplit(*VirtReg, SplitVRegs);
113 
114  if (AvailablePhysReg == ~0u) {
115  // selectOrSplit failed to find a register!
116  // Probably caused by an inline asm.
117  MachineInstr *MI = nullptr;
119  I = MRI->reg_instr_begin(VirtReg->reg), E = MRI->reg_instr_end();
120  I != E; ) {
121  MachineInstr *TmpMI = &*(I++);
122  if (TmpMI->isInlineAsm()) {
123  MI = TmpMI;
124  break;
125  }
126  }
127  if (MI)
128  MI->emitError("inline assembly requires more registers than available");
129  else
130  report_fatal_error("ran out of registers during register allocation");
131  // Keep going after reporting the error.
132  VRM->assignVirt2Phys(VirtReg->reg,
133  RegClassInfo.getOrder(MRI->getRegClass(VirtReg->reg)).front());
134  continue;
135  }
136 
137  if (AvailablePhysReg)
138  Matrix->assign(*VirtReg, AvailablePhysReg);
139 
140  for (unsigned Reg : SplitVRegs) {
142 
143  LiveInterval *SplitVirtReg = &LIS->getInterval(Reg);
144  assert(!VRM->hasPhys(SplitVirtReg->reg) && "Register already assigned");
145  if (MRI->reg_nodbg_empty(SplitVirtReg->reg)) {
146  assert(SplitVirtReg->empty() && "Non-empty but used interval");
147  LLVM_DEBUG(dbgs() << "not queueing unused " << *SplitVirtReg << '\n');
148  aboutToRemoveInterval(*SplitVirtReg);
149  LIS->removeInterval(SplitVirtReg->reg);
150  continue;
151  }
152  LLVM_DEBUG(dbgs() << "queuing new interval: " << *SplitVirtReg << "\n");
153  assert(TargetRegisterInfo::isVirtualRegister(SplitVirtReg->reg) &&
154  "expect split value in virtual register");
155  enqueue(SplitVirtReg);
156  ++NumNewQueued;
157  }
158  }
159 }
160 
163  for (auto DeadInst : DeadRemats) {
164  LIS->RemoveMachineInstrFromMaps(*DeadInst);
165  DeadInst->eraseFromParent();
166  }
167  DeadRemats.clear();
168 }
bool reg_nodbg_empty(unsigned RegNo) const
reg_nodbg_empty - Return true if the only instructions using or defining Reg are Debug instructions...
ArrayRef< MCPhysReg > getOrder(const TargetRegisterClass *RC) const
getOrder - Returns the preferred allocation order for RC.
static const char TimerGroupDescription[]
Definition: RegAllocBase.h:109
const TargetRegisterClass * getRegClass(unsigned Reg) const
Return the register class of the specified virtual register.
void emitError(StringRef Msg) const
Emit an error referring to the source location of this instruction.
void RemoveMachineInstrFromMaps(MachineInstr &MI)
LLVM_ATTRIBUTE_NORETURN void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:139
This class represents lattice values for constants.
Definition: AllocatorList.h:23
static unsigned index2VirtReg(unsigned Index)
Convert a 0-based index to a virtual register number.
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:637
LiveRegMatrix * Matrix
Definition: RegAllocBase.h:68
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
unsigned Reg
virtual unsigned selectOrSplit(LiveInterval &VirtReg, SmallVectorImpl< unsigned > &splitLVRs)=0
bool isInlineAsm() const
STATISTIC(NumFunctions, "Total number of functions")
const TargetRegisterInfo & getTargetRegInfo() const
Definition: VirtRegMap.h:88
SmallPtrSet< MachineInstr *, 32 > DeadRemats
Inst which is a def of an original reg and whose defs are already all dead after remat is saved in De...
Definition: RegAllocBase.h:75
const char * getRegClassName(const TargetRegisterClass *Class) const
Returns the name of the register class.
MachineFunction & getMachineFunction() const
Definition: VirtRegMap.h:82
This class is basically a combination of TimeRegion and Timer.
Definition: Timer.h:160
void freezeReservedRegs(const MachineFunction &)
freezeReservedRegs - Called by the register allocator to freeze the set of reserved registers before ...
static reg_instr_iterator reg_instr_end()
defusechain_iterator - This class provides iterator support for machine operands in the function that...
void assign(LiveInterval &VirtReg, unsigned PhysReg)
Assign VirtReg to PhysReg.
#define T
static cl::opt< bool, true > VerifyRegAlloc("verify-regalloc", cl::location(RegAllocBase::VerifyEnabled), cl::Hidden, cl::desc("Verify during register allocation"))
void invalidateVirtRegs()
Invalidate cached interference queries after modifying virtual register live ranges.
Definition: LiveRegMatrix.h:81
bool hasInterval(unsigned Reg) const
VirtRegMap * VRM
Definition: RegAllocBase.h:66
void removeInterval(unsigned Reg)
Interval removal.
MachineRegisterInfo & getRegInfo() const
Definition: VirtRegMap.h:87
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
void runOnMachineFunction(const MachineFunction &MF)
runOnFunction - Prepare to answer questions about MF.
void init(VirtRegMap &vrm, LiveIntervals &lis, LiveRegMatrix &mat)
unsigned getNumVirtRegs() const
getNumVirtRegs - Return the number of virtual registers created.
static const char TimerGroupName[]
Definition: RegAllocBase.h:108
LiveIntervals * LIS
Definition: RegAllocBase.h:67
virtual void enqueue(LiveInterval *LI)=0
enqueue - Add VirtReg to the priority queue of unassigned registers.
void assignVirt2Phys(unsigned virtReg, MCPhysReg physReg)
creates a mapping for the specified virtual register to the specified physical register ...
Definition: VirtRegMap.cpp:83
LiveInterval & getInterval(unsigned Reg)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
virtual void aboutToRemoveInterval(LiveInterval &LI)
Method called when the allocator is about to remove a LiveInterval.
Definition: RegAllocBase.h:112
Representation of each machine instruction.
Definition: MachineInstr.h:63
static bool VerifyEnabled
VerifyEnabled - True when -verify-regalloc is given.
Definition: RegAllocBase.h:116
const TargetRegisterInfo * TRI
Definition: RegAllocBase.h:64
#define I(x, y, z)
Definition: MD5.cpp:58
bool hasPhys(unsigned virtReg) const
returns true if the specified virtual register is mapped to a physical register
Definition: VirtRegMap.h:94
virtual void postOptimization()
Definition: Spiller.h:32
virtual void postOptimization()
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
RegisterClassInfo RegClassInfo
Definition: RegAllocBase.h:69
IRTranslator LLVM IR MI
bool TimePassesIsEnabled
If the user specifies the -time-passes argument on an LLVM tool command line then the value of this b...
Definition: Pass.h:356
#define LLVM_DEBUG(X)
Definition: Debug.h:122
MachineRegisterInfo * MRI
Definition: RegAllocBase.h:65
reg_instr_iterator reg_instr_begin(unsigned RegNo) const
LocationClass< Ty > location(Ty &L)
Definition: CommandLine.h:439
virtual Spiller & spiller()=0
virtual LiveInterval * dequeue()=0
dequeue - Return the next unassigned register, or NULL.