LLVM  16.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 (const 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  } else if (AvailablePhysReg)
144  Matrix->assign(*VirtReg, AvailablePhysReg);
145 
146  for (Register Reg : SplitVRegs) {
148 
149  LiveInterval *SplitVirtReg = &LIS->getInterval(Reg);
150  assert(!VRM->hasPhys(SplitVirtReg->reg()) && "Register already assigned");
151  if (MRI->reg_nodbg_empty(SplitVirtReg->reg())) {
152  assert(SplitVirtReg->empty() && "Non-empty but used interval");
153  LLVM_DEBUG(dbgs() << "not queueing unused " << *SplitVirtReg << '\n');
154  aboutToRemoveInterval(*SplitVirtReg);
155  LIS->removeInterval(SplitVirtReg->reg());
156  continue;
157  }
158  LLVM_DEBUG(dbgs() << "queuing new interval: " << *SplitVirtReg << "\n");
159  assert(Register::isVirtualRegister(SplitVirtReg->reg()) &&
160  "expect split value in virtual register");
161  enqueue(SplitVirtReg);
162  ++NumNewQueued;
163  }
164  }
165 }
166 
169  for (auto *DeadInst : DeadRemats) {
170  LIS->RemoveMachineInstrFromMaps(*DeadInst);
171  DeadInst->eraseFromParent();
172  }
173  DeadRemats.clear();
174 }
175 
177  const Register Reg = LI->reg();
178 
179  assert(Reg.isVirtual() && "Can only enqueue virtual registers");
180 
181  if (VRM->hasPhys(Reg))
182  return;
183 
184  const TargetRegisterClass &RC = *MRI->getRegClass(Reg);
185  if (ShouldAllocateClass(*TRI, RC)) {
186  LLVM_DEBUG(dbgs() << "Enqueuing " << printReg(Reg, TRI) << '\n');
187  enqueueImpl(LI);
188  } else {
189  LLVM_DEBUG(dbgs() << "Not enqueueing " << printReg(Reg, TRI)
190  << " in skipped register class\n");
191  }
192 }
i
i
Definition: README.txt:29
LiveRegMatrix.h
llvm::RegAllocBase::spiller
virtual Spiller & spiller()=0
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:108
MachineInstr.h
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
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:271
llvm::RegisterClassInfo::getOrder
ArrayRef< MCPhysReg > getOrder(const TargetRegisterClass *RC) const
getOrder - Returns the preferred allocation order for RC.
Definition: RegisterClassInfo.h:101
llvm::LiveRange::empty
bool empty() const
Definition: LiveInterval.h:382
llvm::LiveRegMatrix::invalidateVirtRegs
void invalidateVirtRegs()
Invalidate cached interference queries after modifying virtual register live ranges.
Definition: LiveRegMatrix.h:81
llvm::cl::location
LocationClass< Ty > location(Ty &L)
Definition: CommandLine.h:467
Pass.h
llvm::RegAllocBase::enqueue
void enqueue(const LiveInterval *LI)
enqueue - Add VirtReg to the priority queue of unassigned registers.
Definition: RegAllocBase.cpp:176
llvm::RegAllocBase::enqueueImpl
virtual void enqueueImpl(const LiveInterval *LI)=0
enqueue - Add VirtReg to the priority queue of unassigned registers.
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
Statistic.h
ErrorHandling.h
llvm::VirtRegMap
Definition: VirtRegMap.h:33
llvm::X86Disassembler::Reg
Reg
All possible values of the reg field in the ModR/M byte.
Definition: X86DisassemblerDecoder.h:462
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:277
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:140
llvm::LiveIntervals::removeInterval
void removeInterval(Register Reg)
Interval removal.
Definition: LiveIntervals.h:143
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:87
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::MachineRegisterInfo::getNumVirtRegs
unsigned getNumVirtRegs() const
getNumVirtRegs - Return the number of virtual registers created.
Definition: MachineRegisterInfo.h:770
llvm::MachineRegisterInfo::reg_instr_begin
reg_instr_iterator reg_instr_begin(Register RegNo) const
Definition: MachineRegisterInfo.h:302
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::ArrayRef::empty
bool empty() const
empty - Check if the array is empty.
Definition: ArrayRef.h:159
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")
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:145
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:509
llvm::LiveInterval
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:686
llvm::RegAllocBase::RegClassInfo
RegisterClassInfo RegClassInfo
Definition: RegAllocBase.h:70
llvm::MachineRegisterInfo::reg_instr_end
static reg_instr_iterator reg_instr_end()
Definition: MachineRegisterInfo.h:305
llvm::MachineRegisterInfo::getRegClass
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
Definition: MachineRegisterInfo.h:647
llvm::VirtRegMap::hasPhys
bool hasPhys(Register virtReg) const
returns true if the specified virtual register is mapped to a physical register
Definition: VirtRegMap.h:99
llvm::VirtRegMap::getRegInfo
MachineRegisterInfo & getRegInfo() const
Definition: VirtRegMap.h:92
llvm::RegAllocBase::TimerGroupName
static const char TimerGroupName[]
Definition: RegAllocBase.h:115
Timer.h
llvm::cl::opt
Definition: CommandLine.h:1412
llvm::RegisterClassInfo::runOnMachineFunction
void runOnMachineFunction(const MachineFunction &MF)
runOnFunction - Prepare to answer questions about MF.
Definition: RegisterClassInfo.cpp:42
llvm::RegAllocBase::TRI
const TargetRegisterInfo * TRI
Definition: RegAllocBase.h:65
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:66
LiveIntervals.h
VirtRegMap.h
llvm::TargetRegisterInfo::getRegClassName
const char * getRegClassName(const TargetRegisterClass *Class) const
Returns the name of the register class.
Definition: TargetRegisterInfo.h:777
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:67
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:53
llvm::RegAllocBase::LIS
LiveIntervals * LIS
Definition: RegAllocBase.h:68
I
#define I(x, y, z)
Definition: MD5.cpp:58
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::selectOrSplit
virtual MCRegister selectOrSplit(const LiveInterval &VirtReg, SmallVectorImpl< Register > &splitLVRs)=0
llvm::LiveIntervals::getInterval
LiveInterval & getInterval(Register Reg)
Definition: LiveIntervals.h:112
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::RegAllocBase::dequeue
virtual const LiveInterval * dequeue()=0
dequeue - Return the next unassigned register, or NULL.
llvm::RegAllocBase::postOptimization
virtual void postOptimization()
Definition: RegAllocBase.cpp:167
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:167
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:165
llvm::LiveIntervals
Definition: LiveIntervals.h:53
llvm::VirtRegMap::getTargetRegInfo
const TargetRegisterInfo & getTargetRegInfo() const
Definition: VirtRegMap.h:93
LiveInterval.h
SmallVector.h
llvm::LiveIntervals::RemoveMachineInstrFromMaps
void RemoveMachineInstrFromMaps(MachineInstr &MI)
Definition: LiveIntervals.h:270
llvm::LiveInterval::reg
Register reg() const
Definition: LiveInterval.h:717
llvm::RegAllocBase::aboutToRemoveInterval
virtual void aboutToRemoveInterval(const LiveInterval &LI)
Method called when the allocator is about to remove a LiveInterval.
Definition: RegAllocBase.h:119
llvm::RegAllocBase::VerifyEnabled
static bool VerifyEnabled
VerifyEnabled - True when -verify-regalloc is given.
Definition: RegAllocBase.h:123
llvm::LiveRegMatrix::assign
void assign(const LiveInterval &VirtReg, MCRegister PhysReg)
Assign VirtReg to PhysReg.
Definition: LiveRegMatrix.cpp:104
llvm::LiveIntervals::hasInterval
bool hasInterval(Register Reg) const
Definition: LiveIntervals.h:123
llvm::cl::desc
Definition: CommandLine.h:413
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:385
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:111
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