1 //===-- RegAllocBasic.cpp - Basic Register Allocator ----------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines the RABasic function pass, which provides a minimal
11 // implementation of the basic register allocator.
13 //===----------------------------------------------------------------------===//
15 #include "llvm/CodeGen/Passes.h"
16 #include "AllocationOrder.h"
17 #include "LiveDebugVariables.h"
18 #include "RegAllocBase.h"
20 #include "llvm/Analysis/AliasAnalysis.h"
21 #include "llvm/CodeGen/CalcSpillWeights.h"
22 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
23 #include "llvm/CodeGen/LiveRangeEdit.h"
24 #include "llvm/CodeGen/LiveRegMatrix.h"
25 #include "llvm/CodeGen/LiveStackAnalysis.h"
26 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
27 #include "llvm/CodeGen/MachineFunctionPass.h"
28 #include "llvm/CodeGen/MachineInstr.h"
29 #include "llvm/CodeGen/MachineLoopInfo.h"
30 #include "llvm/CodeGen/MachineRegisterInfo.h"
31 #include "llvm/CodeGen/RegAllocRegistry.h"
32 #include "llvm/CodeGen/VirtRegMap.h"
33 #include "llvm/PassAnalysisSupport.h"
34 #include "llvm/Support/Debug.h"
35 #include "llvm/Support/raw_ostream.h"
36 #include "llvm/Target/TargetRegisterInfo.h"
42 #define DEBUG_TYPE "regalloc"
44 static RegisterRegAlloc
basicRegAlloc("basic", "basic register allocator",
45 createBasicRegisterAllocator
);
48 struct CompSpillWeight
{
49 bool operator()(LiveInterval
*A
, LiveInterval
*B
) const {
50 return A
->weight
< B
->weight
;
56 /// RABasic provides a minimal implementation of the basic register allocation
57 /// algorithm. It prioritizes live virtual registers by spill weight and spills
58 /// whenever a register is unavailable. This is not practical in production but
59 /// provides a useful baseline both for measuring other allocators and comparing
60 /// the speed of the basic algorithm against other styles of allocators.
61 class RABasic
: public MachineFunctionPass
, public RegAllocBase
67 std::unique_ptr
<Spiller
> SpillerInstance
;
68 std::priority_queue
<LiveInterval
*, std::vector
<LiveInterval
*>,
69 CompSpillWeight
> Queue
;
71 // Scratch space. Allocated here to avoid repeated malloc calls in
78 /// Return the pass name.
79 const char* getPassName() const override
{
80 return "Basic Register Allocator";
83 /// RABasic analysis usage.
84 void getAnalysisUsage(AnalysisUsage
&AU
) const override
;
86 void releaseMemory() override
;
88 Spiller
&spiller() override
{ return *SpillerInstance
; }
90 void enqueue(LiveInterval
*LI
) override
{
94 LiveInterval
*dequeue() override
{
97 LiveInterval
*LI
= Queue
.top();
102 unsigned selectOrSplit(LiveInterval
&VirtReg
,
103 SmallVectorImpl
<unsigned> &SplitVRegs
) override
;
105 /// Perform register allocation.
106 bool runOnMachineFunction(MachineFunction
&mf
) override
;
108 // Helper for spilling all live virtual registers currently unified under preg
109 // that interfere with the most recently queried lvr. Return true if spilling
110 // was successful, and append any new spilled/split intervals to splitLVRs.
111 bool spillInterferences(LiveInterval
&VirtReg
, unsigned PhysReg
,
112 SmallVectorImpl
<unsigned> &SplitVRegs
);
117 char RABasic::ID
= 0;
119 } // end anonymous namespace
121 RABasic::RABasic(): MachineFunctionPass(ID
) {
122 initializeLiveDebugVariablesPass(*PassRegistry::getPassRegistry());
123 initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
124 initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
125 initializeRegisterCoalescerPass(*PassRegistry::getPassRegistry());
126 initializeMachineSchedulerPass(*PassRegistry::getPassRegistry());
127 initializeLiveStacksPass(*PassRegistry::getPassRegistry());
128 initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry());
129 initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry());
130 initializeVirtRegMapPass(*PassRegistry::getPassRegistry());
131 initializeLiveRegMatrixPass(*PassRegistry::getPassRegistry());
134 void RABasic::getAnalysisUsage(AnalysisUsage
&AU
) const {
135 AU
.setPreservesCFG();
136 AU
.addRequired
<AliasAnalysis
>();
137 AU
.addPreserved
<AliasAnalysis
>();
138 AU
.addRequired
<LiveIntervals
>();
139 AU
.addPreserved
<LiveIntervals
>();
140 AU
.addPreserved
<SlotIndexes
>();
141 AU
.addRequired
<LiveDebugVariables
>();
142 AU
.addPreserved
<LiveDebugVariables
>();
143 AU
.addRequired
<LiveStacks
>();
144 AU
.addPreserved
<LiveStacks
>();
145 AU
.addRequired
<MachineBlockFrequencyInfo
>();
146 AU
.addPreserved
<MachineBlockFrequencyInfo
>();
147 AU
.addRequiredID(MachineDominatorsID
);
148 AU
.addPreservedID(MachineDominatorsID
);
149 AU
.addRequired
<MachineLoopInfo
>();
150 AU
.addPreserved
<MachineLoopInfo
>();
151 AU
.addRequired
<VirtRegMap
>();
152 AU
.addPreserved
<VirtRegMap
>();
153 AU
.addRequired
<LiveRegMatrix
>();
154 AU
.addPreserved
<LiveRegMatrix
>();
155 MachineFunctionPass::getAnalysisUsage(AU
);
158 void RABasic::releaseMemory() {
159 SpillerInstance
.reset();
163 // Spill or split all live virtual registers currently unified under PhysReg
164 // that interfere with VirtReg. The newly spilled or split live intervals are
165 // returned by appending them to SplitVRegs.
166 bool RABasic::spillInterferences(LiveInterval
&VirtReg
, unsigned PhysReg
,
167 SmallVectorImpl
<unsigned> &SplitVRegs
) {
168 // Record each interference and determine if all are spillable before mutating
169 // either the union or live intervals.
170 SmallVector
<LiveInterval
*, 8> Intfs
;
172 // Collect interferences assigned to any alias of the physical register.
173 for (MCRegUnitIterator
Units(PhysReg
, TRI
); Units
.isValid(); ++Units
) {
174 LiveIntervalUnion::Query
&Q
= Matrix
->query(VirtReg
, *Units
);
175 Q
.collectInterferingVRegs();
176 if (Q
.seenUnspillableVReg())
178 for (unsigned i
= Q
.interferingVRegs().size(); i
; --i
) {
179 LiveInterval
*Intf
= Q
.interferingVRegs()[i
- 1];
180 if (!Intf
->isSpillable() || Intf
->weight
> VirtReg
.weight
)
182 Intfs
.push_back(Intf
);
185 DEBUG(dbgs() << "spilling " << TRI
->getName(PhysReg
) <<
186 " interferences with " << VirtReg
<< "\n");
187 assert(!Intfs
.empty() && "expected interference");
189 // Spill each interfering vreg allocated to PhysReg or an alias.
190 for (unsigned i
= 0, e
= Intfs
.size(); i
!= e
; ++i
) {
191 LiveInterval
&Spill
= *Intfs
[i
];
194 if (!VRM
->hasPhys(Spill
.reg
))
197 // Deallocate the interfering vreg by removing it from the union.
198 // A LiveInterval instance may not be in a union during modification!
199 Matrix
->unassign(Spill
);
201 // Spill the extracted interval.
202 LiveRangeEdit
LRE(&Spill
, SplitVRegs
, *MF
, *LIS
, VRM
);
203 spiller().spill(LRE
);
208 // Driver for the register assignment and splitting heuristics.
209 // Manages iteration over the LiveIntervalUnions.
211 // This is a minimal implementation of register assignment and splitting that
212 // spills whenever we run out of registers.
214 // selectOrSplit can only be called once per live virtual register. We then do a
215 // single interference test for each register the correct class until we find an
216 // available register. So, the number of interference tests in the worst case is
217 // |vregs| * |machineregs|. And since the number of interference tests is
218 // minimal, there is no value in caching them outside the scope of
220 unsigned RABasic::selectOrSplit(LiveInterval
&VirtReg
,
221 SmallVectorImpl
<unsigned> &SplitVRegs
) {
222 // Populate a list of physical register spill candidates.
223 SmallVector
<unsigned, 8> PhysRegSpillCands
;
225 // Check for an available register in this class.
226 AllocationOrder
Order(VirtReg
.reg
, *VRM
, RegClassInfo
);
227 while (unsigned PhysReg
= Order
.next()) {
228 // Check for interference in PhysReg
229 switch (Matrix
->checkInterference(VirtReg
, PhysReg
)) {
230 case LiveRegMatrix::IK_Free
:
231 // PhysReg is available, allocate it.
234 case LiveRegMatrix::IK_VirtReg
:
235 // Only virtual registers in the way, we may be able to spill them.
236 PhysRegSpillCands
.push_back(PhysReg
);
240 // RegMask or RegUnit interference.
245 // Try to spill another interfering reg with less spill weight.
246 for (SmallVectorImpl
<unsigned>::iterator PhysRegI
= PhysRegSpillCands
.begin(),
247 PhysRegE
= PhysRegSpillCands
.end(); PhysRegI
!= PhysRegE
; ++PhysRegI
) {
248 if (!spillInterferences(VirtReg
, *PhysRegI
, SplitVRegs
))
251 assert(!Matrix
->checkInterference(VirtReg
, *PhysRegI
) &&
252 "Interference after spill.");
253 // Tell the caller to allocate to this newly freed physical register.
257 // No other spill candidates were found, so spill the current VirtReg.
258 DEBUG(dbgs() << "spilling: " << VirtReg
<< '\n');
259 if (!VirtReg
.isSpillable())
261 LiveRangeEdit
LRE(&VirtReg
, SplitVRegs
, *MF
, *LIS
, VRM
);
262 spiller().spill(LRE
);
264 // The live virtual register requesting allocation was spilled, so tell
265 // the caller not to allocate anything during this round.
269 bool RABasic::runOnMachineFunction(MachineFunction
&mf
) {
270 DEBUG(dbgs() << "********** BASIC REGISTER ALLOCATION **********\n"
271 << "********** Function: "
272 << mf
.getName() << '\n');
275 RegAllocBase::init(getAnalysis
<VirtRegMap
>(),
276 getAnalysis
<LiveIntervals
>(),
277 getAnalysis
<LiveRegMatrix
>());
279 calculateSpillWeightsAndHints(*LIS
, *MF
,
280 getAnalysis
<MachineLoopInfo
>(),
281 getAnalysis
<MachineBlockFrequencyInfo
>());
283 SpillerInstance
.reset(createInlineSpiller(*this, *MF
, *VRM
));
287 // Diagnostic output before rewriting
288 DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *VRM
<< "\n");
294 FunctionPass
* llvm::createBasicRegisterAllocator()
296 return new RABasic();