LLVM  8.0.1
RegAllocBase.cpp
Go to the documentation of this file.
1 //===- RegAllocBase.cpp - Register Allocator Base Class -------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file defines the RegAllocBase class which provides common functionality
11 // for LiveIntervalUnion-based register allocators.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #include "RegAllocBase.h"
16 #include "Spiller.h"
17 #include "llvm/ADT/SmallVector.h"
18 #include "llvm/ADT/Statistic.h"
26 #include "llvm/Pass.h"
28 #include "llvm/Support/Debug.h"
30 #include "llvm/Support/Timer.h"
32 #include <cassert>
33 
34 using namespace llvm;
35 
36 #define DEBUG_TYPE "regalloc"
37 
38 STATISTIC(NumNewQueued , "Number of new live ranges queued");
39 
40 // Temporary verification option until we can put verification inside
41 // MachineVerifier.
44  cl::Hidden, cl::desc("Verify during register allocation"));
45 
46 const char RegAllocBase::TimerGroupName[] = "regalloc";
47 const char RegAllocBase::TimerGroupDescription[] = "Register Allocation";
48 bool RegAllocBase::VerifyEnabled = false;
49 
50 //===----------------------------------------------------------------------===//
51 // RegAllocBase Implementation
52 //===----------------------------------------------------------------------===//
53 
54 // Pin the vtable to this file.
55 void RegAllocBase::anchor() {}
56 
58  LiveIntervals &lis,
59  LiveRegMatrix &mat) {
60  TRI = &vrm.getTargetRegInfo();
61  MRI = &vrm.getRegInfo();
62  VRM = &vrm;
63  LIS = &lis;
64  Matrix = &mat;
67 }
68 
69 // Visit all the live registers. If they are already assigned to a physical
70 // register, unify them with the corresponding LiveIntervalUnion, otherwise push
71 // them on the priority queue for later assignment.
72 void RegAllocBase::seedLiveRegs() {
73  NamedRegionTimer T("seed", "Seed Live Regs", TimerGroupName,
75  for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
77  if (MRI->reg_nodbg_empty(Reg))
78  continue;
79  enqueue(&LIS->getInterval(Reg));
80  }
81 }
82 
83 // Top-level driver to manage the queue of unassigned VirtRegs and call the
84 // selectOrSplit implementation.
86  seedLiveRegs();
87 
88  // Continue assigning vregs one at a time to available physical registers.
89  while (LiveInterval *VirtReg = dequeue()) {
90  assert(!VRM->hasPhys(VirtReg->reg) && "Register already assigned");
91 
92  // Unused registers can appear when the spiller coalesces snippets.
93  if (MRI->reg_nodbg_empty(VirtReg->reg)) {
94  LLVM_DEBUG(dbgs() << "Dropping unused " << *VirtReg << '\n');
95  aboutToRemoveInterval(*VirtReg);
96  LIS->removeInterval(VirtReg->reg);
97  continue;
98  }
99 
100  // Invalidate all interference queries, live ranges could have changed.
102 
103  // selectOrSplit requests the allocator to return an available physical
104  // register if possible and populate a list of new live intervals that
105  // result from splitting.
106  LLVM_DEBUG(dbgs() << "\nselectOrSplit "
107  << TRI->getRegClassName(MRI->getRegClass(VirtReg->reg))
108  << ':' << *VirtReg << " w=" << VirtReg->weight << '\n');
109 
110  using VirtRegVec = SmallVector<unsigned, 4>;
111 
112  VirtRegVec SplitVRegs;
113  unsigned AvailablePhysReg = selectOrSplit(*VirtReg, SplitVRegs);
114 
115  if (AvailablePhysReg == ~0u) {
116  // selectOrSplit failed to find a register!
117  // Probably caused by an inline asm.
118  MachineInstr *MI = nullptr;
120  I = MRI->reg_instr_begin(VirtReg->reg), E = MRI->reg_instr_end();
121  I != E; ) {
122  MachineInstr *TmpMI = &*(I++);
123  if (TmpMI->isInlineAsm()) {
124  MI = TmpMI;
125  break;
126  }
127  }
128  if (MI)
129  MI->emitError("inline assembly requires more registers than available");
130  else
131  report_fatal_error("ran out of registers during register allocation");
132  // Keep going after reporting the error.
133  VRM->assignVirt2Phys(VirtReg->reg,
134  RegClassInfo.getOrder(MRI->getRegClass(VirtReg->reg)).front());
135  continue;
136  }
137 
138  if (AvailablePhysReg)
139  Matrix->assign(*VirtReg, AvailablePhysReg);
140 
141  for (unsigned Reg : SplitVRegs) {
143 
144  LiveInterval *SplitVirtReg = &LIS->getInterval(Reg);
145  assert(!VRM->hasPhys(SplitVirtReg->reg) && "Register already assigned");
146  if (MRI->reg_nodbg_empty(SplitVirtReg->reg)) {
147  assert(SplitVirtReg->empty() && "Non-empty but used interval");
148  LLVM_DEBUG(dbgs() << "not queueing unused " << *SplitVirtReg << '\n');
149  aboutToRemoveInterval(*SplitVirtReg);
150  LIS->removeInterval(SplitVirtReg->reg);
151  continue;
152  }
153  LLVM_DEBUG(dbgs() << "queuing new interval: " << *SplitVirtReg << "\n");
154  assert(TargetRegisterInfo::isVirtualRegister(SplitVirtReg->reg) &&
155  "expect split value in virtual register");
156  enqueue(SplitVirtReg);
157  ++NumNewQueued;
158  }
159  }
160 }
161 
164  for (auto DeadInst : DeadRemats) {
165  LIS->RemoveMachineInstrFromMaps(*DeadInst);
166  DeadInst->eraseFromParent();
167  }
168  DeadRemats.clear();
169 }
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:110
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:140
This class represents lattice values for constants.
Definition: AllocatorList.h:24
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:638
LiveRegMatrix * Matrix
Definition: RegAllocBase.h:69
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:89
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:76
const char * getRegClassName(const TargetRegisterClass *Class) const
Returns the name of the register class.
MachineFunction & getMachineFunction() const
Definition: VirtRegMap.h:83
This class is basically a combination of TimeRegion and Timer.
Definition: Timer.h:161
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:82
bool hasInterval(unsigned Reg) const
VirtRegMap * VRM
Definition: RegAllocBase.h:67
void removeInterval(unsigned Reg)
Interval removal.
MachineRegisterInfo & getRegInfo() const
Definition: VirtRegMap.h:88
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:109
LiveIntervals * LIS
Definition: RegAllocBase.h:68
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:84
LiveInterval & getInterval(unsigned Reg)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
virtual void aboutToRemoveInterval(LiveInterval &LI)
Method called when the allocator is about to remove a LiveInterval.
Definition: RegAllocBase.h:113
Representation of each machine instruction.
Definition: MachineInstr.h:64
static bool VerifyEnabled
VerifyEnabled - True when -verify-regalloc is given.
Definition: RegAllocBase.h:117
const TargetRegisterInfo * TRI
Definition: RegAllocBase.h:65
#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:95
virtual void postOptimization()
Definition: Spiller.h:33
virtual void postOptimization()
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
RegisterClassInfo RegClassInfo
Definition: RegAllocBase.h:70
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:357
#define LLVM_DEBUG(X)
Definition: Debug.h:123
MachineRegisterInfo * MRI
Definition: RegAllocBase.h:66
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.