LLVM  10.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"
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) {
76  unsigned Reg = Register::index2VirtReg(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  MI = &*(I++);
123  if (MI->isInlineAsm())
124  break;
125  }
126  if (MI && MI->isInlineAsm()) {
127  MI->emitError("inline assembly requires more registers than available");
128  } else if (MI) {
130  MI->getParent()->getParent()->getMMI().getModule()->getContext();
131  Context.emitError("ran out of registers during register allocation");
132  } else {
133  report_fatal_error("ran out of registers during register allocation");
134  }
135  // Keep going after reporting the error.
136  VRM->assignVirt2Phys(VirtReg->reg,
137  RegClassInfo.getOrder(MRI->getRegClass(VirtReg->reg)).front());
138  continue;
139  }
140 
141  if (AvailablePhysReg)
142  Matrix->assign(*VirtReg, AvailablePhysReg);
143 
144  for (unsigned Reg : SplitVRegs) {
146 
147  LiveInterval *SplitVirtReg = &LIS->getInterval(Reg);
148  assert(!VRM->hasPhys(SplitVirtReg->reg) && "Register already assigned");
149  if (MRI->reg_nodbg_empty(SplitVirtReg->reg)) {
150  assert(SplitVirtReg->empty() && "Non-empty but used interval");
151  LLVM_DEBUG(dbgs() << "not queueing unused " << *SplitVirtReg << '\n');
152  aboutToRemoveInterval(*SplitVirtReg);
153  LIS->removeInterval(SplitVirtReg->reg);
154  continue;
155  }
156  LLVM_DEBUG(dbgs() << "queuing new interval: " << *SplitVirtReg << "\n");
157  assert(Register::isVirtualRegister(SplitVirtReg->reg) &&
158  "expect split value in virtual register");
159  enqueue(SplitVirtReg);
160  ++NumNewQueued;
161  }
162  }
163 }
164 
167  for (auto DeadInst : DeadRemats) {
168  LIS->RemoveMachineInstrFromMaps(*DeadInst);
169  DeadInst->eraseFromParent();
170  }
171  DeadRemats.clear();
172 }
ArrayRef< MCPhysReg > getOrder(const TargetRegisterClass *RC) const
getOrder - Returns the preferred allocation order for RC.
static const char TimerGroupDescription[]
Definition: RegAllocBase.h:109
LLVMContext & Context
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
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:679
LiveRegMatrix * Matrix
Definition: RegAllocBase.h:68
unsigned Reg
virtual unsigned selectOrSplit(LiveInterval &VirtReg, SmallVectorImpl< unsigned > &splitLVRs)=0
bool isInlineAsm() const
STATISTIC(NumFunctions, "Total number of functions")
MachineModuleInfo & getMMI() const
static unsigned index2VirtReg(unsigned Index)
Convert a 0-based index to a virtual register number.
Definition: Register.h:83
bool hasPhys(Register virtReg) const
returns true if the specified virtual register is mapped to a physical register
Definition: VirtRegMap.h:96
const TargetRegisterInfo & getTargetRegInfo() const
Definition: VirtRegMap.h:90
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
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:84
LLVMContext & getContext() const
Get the global data context.
Definition: Module.h:245
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 emitError(unsigned LocCookie, const Twine &ErrorStr)
emitError - Emit an error message to the currently installed error handler with optional location inf...
bool hasInterval(Register Reg) const
void assign(LiveInterval &VirtReg, unsigned PhysReg)
Assign VirtReg to PhysReg.
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
VirtRegMap * VRM
Definition: RegAllocBase.h:66
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:64
void removeInterval(unsigned Reg)
Interval removal.
MachineRegisterInfo & getRegInfo() const
Definition: VirtRegMap.h:89
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
void assignVirt2Phys(Register virtReg, MCPhysReg physReg)
creates a mapping for the specified virtual register to the specified physical register ...
Definition: VirtRegMap.cpp:83
bool reg_nodbg_empty(Register RegNo) const
reg_nodbg_empty - Return true if the only instructions using or defining Reg are Debug instructions...
constexpr double e
Definition: MathExtras.h:57
LiveInterval & getInterval(Register Reg)
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.
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
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:255
Representation of each machine instruction.
Definition: MachineInstr.h:63
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
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
virtual void postOptimization()
Definition: Spiller.h:32
virtual void postOptimization()
const Module * getModule() const
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:69
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:361
#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:448
virtual Spiller & spiller()=0
virtual LiveInterval * dequeue()=0
dequeue - Return the next unassigned register, or NULL.