LLVM  14.0.0git
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 "llvm/ADT/SmallVector.h"
16 #include "llvm/ADT/Statistic.h"
23 #include "llvm/CodeGen/Spiller.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  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;
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<Register, 4>;
110 
111  VirtRegVec SplitVRegs;
112  MCRegister 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()),
120  E = MRI->reg_instr_end();
121  I != E;) {
122  MI = &*(I++);
123  if (MI->isInlineAsm())
124  break;
125  }
126 
127  const TargetRegisterClass *RC = MRI->getRegClass(VirtReg->reg());
128  ArrayRef<MCPhysReg> AllocOrder = RegClassInfo.getOrder(RC);
129  if (AllocOrder.empty())
130  report_fatal_error("no registers from class available to allocate");
131  else if (MI && MI->isInlineAsm()) {
132  MI->emitError("inline assembly requires more registers than available");
133  } else if (MI) {
135  MI->getParent()->getParent()->getMMI().getModule()->getContext();
136  Context.emitError("ran out of registers during register allocation");
137  } else {
138  report_fatal_error("ran out of registers during register allocation");
139  }
140 
141  // Keep going after reporting the error.
142  VRM->assignVirt2Phys(VirtReg->reg(), AllocOrder.front());
143  continue;
144  }
145 
146  if (AvailablePhysReg)
147  Matrix->assign(*VirtReg, AvailablePhysReg);
148 
149  for (Register Reg : SplitVRegs) {
151 
152  LiveInterval *SplitVirtReg = &LIS->getInterval(Reg);
153  assert(!VRM->hasPhys(SplitVirtReg->reg()) && "Register already assigned");
154  if (MRI->reg_nodbg_empty(SplitVirtReg->reg())) {
155  assert(SplitVirtReg->empty() && "Non-empty but used interval");
156  LLVM_DEBUG(dbgs() << "not queueing unused " << *SplitVirtReg << '\n');
157  aboutToRemoveInterval(*SplitVirtReg);
158  LIS->removeInterval(SplitVirtReg->reg());
159  continue;
160  }
161  LLVM_DEBUG(dbgs() << "queuing new interval: " << *SplitVirtReg << "\n");
162  assert(Register::isVirtualRegister(SplitVirtReg->reg()) &&
163  "expect split value in virtual register");
164  enqueue(SplitVirtReg);
165  ++NumNewQueued;
166  }
167  }
168 }
169 
172  for (auto DeadInst : DeadRemats) {
173  LIS->RemoveMachineInstrFromMaps(*DeadInst);
174  DeadInst->eraseFromParent();
175  }
176  DeadRemats.clear();
177 }
178 
180  const Register Reg = LI->reg();
181 
182  assert(Reg.isVirtual() && "Can only enqueue virtual registers");
183 
184  if (VRM->hasPhys(Reg))
185  return;
186 
187  const TargetRegisterClass &RC = *MRI->getRegClass(Reg);
188  if (ShouldAllocateClass(*TRI, RC)) {
189  LLVM_DEBUG(dbgs() << "Enqueuing " << printReg(Reg, TRI) << '\n');
190  enqueueImpl(LI);
191  } else {
192  LLVM_DEBUG(dbgs() << "Not enqueueing " << printReg(Reg, TRI)
193  << " in skipped register class\n");
194  }
195 }
i
i
Definition: README.txt:29
LiveRegMatrix.h
llvm::RegAllocBase::spiller
virtual Spiller & spiller()=0
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:105
MachineInstr.h
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
llvm::LLVMContext::emitError
void emitError(uint64_t LocCookie, const Twine &ErrorStr)
emitError - Emit an error message to the currently installed error handler with optional location inf...
Definition: LLVMContext.cpp:251
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
llvm::LiveRange::empty
bool empty() const
Definition: LiveInterval.h:374
llvm::RegAllocBase::enqueueImpl
virtual void enqueueImpl(LiveInterval *LI)=0
enqueue - Add VirtReg to the priority queue of unassigned registers.
llvm::LiveRegMatrix::invalidateVirtRegs
void invalidateVirtRegs()
Invalidate cached interference queries after modifying virtual register live ranges.
Definition: LiveRegMatrix.h:81
T
llvm::cl::location
LocationClass< Ty > location(Ty &L)
Definition: CommandLine.h:457
Pass.h
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::VirtRegMap
Definition: VirtRegMap.h:33
llvm::VirtRegMap::assignVirt2Phys
void assignVirt2Phys(Register virtReg, MCPhysReg physReg)
creates a mapping for the specified virtual register to the specified physical register
Definition: VirtRegMap.cpp:85
llvm::MachineRegisterInfo::defusechain_instr_iterator
defusechain_iterator - This class provides iterator support for machine operands in the function that...
Definition: MachineRegisterInfo.h:269
llvm::RegAllocBase::enqueue
void enqueue(LiveInterval *LI)
enqueue - Add VirtReg to the priority queue of unassigned registers.
Definition: RegAllocBase.cpp:179
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
llvm::LiveIntervals::removeInterval
void removeInterval(Register Reg)
Interval removal.
Definition: LiveIntervals.h:145
Spiller.h
llvm::TimePassesIsEnabled
bool TimePassesIsEnabled
If the user specifies the -time-passes argument on an LLVM tool command line then the value of this b...
Definition: PassTimingInfo.cpp:37
llvm::VirtRegMap::getMachineFunction
MachineFunction & getMachineFunction() const
Definition: VirtRegMap.h:88
llvm::MachineRegisterInfo::getNumVirtRegs
unsigned getNumVirtRegs() const
getNumVirtRegs - Return the number of virtual registers created.
Definition: MachineRegisterInfo.h:757
llvm::MachineRegisterInfo::reg_instr_begin
reg_instr_iterator reg_instr_begin(Register RegNo) const
Definition: MachineRegisterInfo.h:294
llvm::Register::index2VirtReg
static Register index2VirtReg(unsigned Index)
Convert a 0-based index to a virtual register number.
Definition: Register.h:84
llvm::RegAllocBase::DeadRemats
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:77
llvm::RegAllocBase::TimerGroupDescription
static const char TimerGroupDescription[]
Definition: RegAllocBase.h:116
llvm::RegAllocBase::selectOrSplit
virtual MCRegister selectOrSplit(LiveInterval &VirtReg, SmallVectorImpl< Register > &splitLVRs)=0
llvm::ArrayRef::empty
bool empty() const
empty - Check if the array is empty.
Definition: ArrayRef.h:160
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
MachineRegisterInfo.h
Context
LLVMContext & Context
Definition: NVVMIntrRange.cpp:66
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
CommandLine.h
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::LiveRegMatrix::assign
void assign(LiveInterval &VirtReg, MCRegister PhysReg)
Assign VirtReg to PhysReg.
Definition: LiveRegMatrix.cpp:104
VerifyRegAlloc
static cl::opt< bool, true > VerifyRegAlloc("verify-regalloc", cl::location(RegAllocBase::VerifyEnabled), cl::Hidden, cl::desc("Verify during register allocation"))
llvm::RegAllocBase::Matrix
LiveRegMatrix * Matrix
Definition: RegAllocBase.h:69
llvm::TargetRegisterClass
Definition: TargetRegisterInfo.h:46
llvm::RegAllocBase::init
void init(VirtRegMap &vrm, LiveIntervals &lis, LiveRegMatrix &mat)
Definition: RegAllocBase.cpp:57
llvm::report_fatal_error
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:140
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
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
llvm::LiveInterval
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:680
llvm::RegAllocBase::RegClassInfo
RegisterClassInfo RegClassInfo
Definition: RegAllocBase.h:70
llvm::MachineRegisterInfo::reg_instr_end
static reg_instr_iterator reg_instr_end()
Definition: MachineRegisterInfo.h:297
llvm::MachineRegisterInfo::getRegClass
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
Definition: MachineRegisterInfo.h:634
llvm::VirtRegMap::hasPhys
bool hasPhys(Register virtReg) const
returns true if the specified virtual register is mapped to a physical register
Definition: VirtRegMap.h:100
llvm::VirtRegMap::getRegInfo
MachineRegisterInfo & getRegInfo() const
Definition: VirtRegMap.h:93
llvm::RegAllocBase::TimerGroupName
static const char TimerGroupName[]
Definition: RegAllocBase.h:115
Timer.h
llvm::cl::opt
Definition: CommandLine.h:1432
llvm::RegisterClassInfo::runOnMachineFunction
void runOnMachineFunction(const MachineFunction &MF)
runOnFunction - Prepare to answer questions about MF.
Definition: RegisterClassInfo.cpp:43
llvm::RegAllocBase::TRI
const TargetRegisterInfo * TRI
Definition: RegAllocBase.h:65
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:64
LiveIntervals.h
VirtRegMap.h
llvm::TargetRegisterInfo::getRegClassName
const char * getRegClassName(const TargetRegisterClass *Class) const
Returns the name of the register class.
Definition: TargetRegisterInfo.h:745
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:68
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::RegAllocBase::LIS
LiveIntervals * LIS
Definition: RegAllocBase.h:68
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::RegAllocBase::VRM
VirtRegMap * VRM
Definition: RegAllocBase.h:67
llvm::RegAllocBase::MRI
MachineRegisterInfo * MRI
Definition: RegAllocBase.h:66
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
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::RegAllocBase::allocatePhysRegs
void allocatePhysRegs()
Definition: RegAllocBase.cpp:84
MachineModuleInfo.h
llvm::RegAllocBase::dequeue
virtual LiveInterval * dequeue()=0
dequeue - Return the next unassigned register, or NULL.
llvm::LiveIntervals::getInterval
LiveInterval & getInterval(Register Reg)
Definition: LiveIntervals.h:114
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::RegAllocBase::postOptimization
virtual void postOptimization()
Definition: RegAllocBase.cpp:170
llvm::RegAllocBase::aboutToRemoveInterval
virtual void aboutToRemoveInterval(LiveInterval &LI)
Method called when the allocator is about to remove a LiveInterval.
Definition: RegAllocBase.h:119
llvm::Spiller::postOptimization
virtual void postOptimization()
Definition: Spiller.h:33
llvm::ArrayRef::front
const T & front() const
front - Get the first element.
Definition: ArrayRef.h:168
llvm::Register
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
RegAllocBase.h
llvm::NamedRegionTimer
This class is basically a combination of TimeRegion and Timer.
Definition: Timer.h:166
llvm::LiveIntervals
Definition: LiveIntervals.h:54
llvm::VirtRegMap::getTargetRegInfo
const TargetRegisterInfo & getTargetRegInfo() const
Definition: VirtRegMap.h:94
LiveInterval.h
SmallVector.h
llvm::LiveIntervals::RemoveMachineInstrFromMaps
void RemoveMachineInstrFromMaps(MachineInstr &MI)
Definition: LiveIntervals.h:276
llvm::LiveInterval::reg
Register reg() const
Definition: LiveInterval.h:711
llvm::RegAllocBase::VerifyEnabled
static bool VerifyEnabled
VerifyEnabled - True when -verify-regalloc is given.
Definition: RegAllocBase.h:123
llvm::LiveIntervals::hasInterval
bool hasInterval(Register Reg) const
Definition: LiveIntervals.h:125
llvm::cl::desc
Definition: CommandLine.h:412
llvm::MachineRegisterInfo::reg_nodbg_empty
bool reg_nodbg_empty(Register RegNo) const
reg_nodbg_empty - Return true if the only instructions using or defining Reg are Debug instructions.
Definition: MachineRegisterInfo.h:377
raw_ostream.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
TargetRegisterInfo.h
Debug.h
llvm::RegAllocBase::ShouldAllocateClass
const RegClassFilterFunc ShouldAllocateClass
Definition: RegAllocBase.h:71
llvm::MCRegister
Wrapper class representing physical registers. Should be passed by value.
Definition: MCRegister.h:24
llvm::LiveRegMatrix
Definition: LiveRegMatrix.h:40