1 //===-- RegAllocGreedy.cpp - greedy 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 RAGreedy function pass for register allocation in
13 //===----------------------------------------------------------------------===//
15 #define DEBUG_TYPE "regalloc"
16 #include "AllocationOrder.h"
17 #include "LiveIntervalUnion.h"
18 #include "LiveRangeEdit.h"
19 #include "RegAllocBase.h"
22 #include "VirtRegMap.h"
23 #include "VirtRegRewriter.h"
24 #include "llvm/Analysis/AliasAnalysis.h"
25 #include "llvm/Function.h"
26 #include "llvm/PassAnalysisSupport.h"
27 #include "llvm/CodeGen/CalcSpillWeights.h"
28 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
29 #include "llvm/CodeGen/LiveStackAnalysis.h"
30 #include "llvm/CodeGen/MachineDominators.h"
31 #include "llvm/CodeGen/MachineFunctionPass.h"
32 #include "llvm/CodeGen/MachineLoopInfo.h"
33 #include "llvm/CodeGen/MachineLoopRanges.h"
34 #include "llvm/CodeGen/MachineRegisterInfo.h"
35 #include "llvm/CodeGen/Passes.h"
36 #include "llvm/CodeGen/RegAllocRegistry.h"
37 #include "llvm/CodeGen/RegisterCoalescer.h"
38 #include "llvm/Target/TargetOptions.h"
39 #include "llvm/Support/Debug.h"
40 #include "llvm/Support/ErrorHandling.h"
41 #include "llvm/Support/raw_ostream.h"
42 #include "llvm/Support/Timer.h"
46 static RegisterRegAlloc
greedyRegAlloc("greedy", "greedy register allocator",
47 createGreedyRegisterAllocator
);
50 class RAGreedy
: public MachineFunctionPass
, public RegAllocBase
{
53 BitVector ReservedRegs
;
57 MachineDominatorTree
*DomTree
;
58 MachineLoopInfo
*Loops
;
59 MachineLoopRanges
*LoopRanges
;
62 std::auto_ptr
<Spiller
> SpillerInstance
;
63 std::auto_ptr
<SplitAnalysis
> SA
;
68 /// Return the pass name.
69 virtual const char* getPassName() const {
70 return "Greedy Register Allocator";
73 /// RAGreedy analysis usage.
74 virtual void getAnalysisUsage(AnalysisUsage
&AU
) const;
76 virtual void releaseMemory();
78 virtual Spiller
&spiller() { return *SpillerInstance
; }
80 virtual float getPriority(LiveInterval
*LI
);
82 virtual unsigned selectOrSplit(LiveInterval
&VirtReg
,
83 SmallVectorImpl
<LiveInterval
*> &SplitVRegs
);
85 /// Perform register allocation.
86 virtual bool runOnMachineFunction(MachineFunction
&mf
);
91 bool checkUncachedInterference(LiveInterval
&, unsigned);
92 LiveInterval
*getSingleInterference(LiveInterval
&, unsigned);
93 bool reassignVReg(LiveInterval
&InterferingVReg
, unsigned OldPhysReg
);
94 bool reassignInterferences(LiveInterval
&VirtReg
, unsigned PhysReg
);
95 unsigned findInterferenceFreeReg(MachineLoopRange
*,
96 LiveInterval
&, AllocationOrder
&);
98 unsigned tryReassign(LiveInterval
&, AllocationOrder
&);
99 unsigned trySplit(LiveInterval
&, AllocationOrder
&,
100 SmallVectorImpl
<LiveInterval
*>&);
102 } // end anonymous namespace
104 char RAGreedy::ID
= 0;
106 FunctionPass
* llvm::createGreedyRegisterAllocator() {
107 return new RAGreedy();
110 RAGreedy::RAGreedy(): MachineFunctionPass(ID
) {
111 initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
112 initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
113 initializeStrongPHIEliminationPass(*PassRegistry::getPassRegistry());
114 initializeRegisterCoalescerAnalysisGroup(*PassRegistry::getPassRegistry());
115 initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry());
116 initializeLiveStacksPass(*PassRegistry::getPassRegistry());
117 initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry());
118 initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry());
119 initializeMachineLoopRangesPass(*PassRegistry::getPassRegistry());
120 initializeVirtRegMapPass(*PassRegistry::getPassRegistry());
123 void RAGreedy::getAnalysisUsage(AnalysisUsage
&AU
) const {
124 AU
.setPreservesCFG();
125 AU
.addRequired
<AliasAnalysis
>();
126 AU
.addPreserved
<AliasAnalysis
>();
127 AU
.addRequired
<LiveIntervals
>();
128 AU
.addPreserved
<SlotIndexes
>();
130 AU
.addRequiredID(StrongPHIEliminationID
);
131 AU
.addRequiredTransitive
<RegisterCoalescer
>();
132 AU
.addRequired
<CalculateSpillWeights
>();
133 AU
.addRequired
<LiveStacks
>();
134 AU
.addPreserved
<LiveStacks
>();
135 AU
.addRequired
<MachineDominatorTree
>();
136 AU
.addPreserved
<MachineDominatorTree
>();
137 AU
.addRequired
<MachineLoopInfo
>();
138 AU
.addPreserved
<MachineLoopInfo
>();
139 AU
.addRequired
<MachineLoopRanges
>();
140 AU
.addPreserved
<MachineLoopRanges
>();
141 AU
.addRequired
<VirtRegMap
>();
142 AU
.addPreserved
<VirtRegMap
>();
143 MachineFunctionPass::getAnalysisUsage(AU
);
146 void RAGreedy::releaseMemory() {
147 SpillerInstance
.reset(0);
148 RegAllocBase::releaseMemory();
151 float RAGreedy::getPriority(LiveInterval
*LI
) {
152 float Priority
= LI
->weight
;
154 // Prioritize hinted registers so they are allocated first.
155 std::pair
<unsigned, unsigned> Hint
;
156 if (Hint
.first
|| Hint
.second
) {
157 // The hint can be target specific, a virtual register, or a physreg.
160 // Prefer physreg hints above anything else.
161 if (Hint
.first
== 0 && TargetRegisterInfo::isPhysicalRegister(Hint
.second
))
167 // Check interference without using the cache.
168 bool RAGreedy::checkUncachedInterference(LiveInterval
&VirtReg
,
170 for (const unsigned *AliasI
= TRI
->getOverlaps(PhysReg
); *AliasI
; ++AliasI
) {
171 LiveIntervalUnion::Query
subQ(&VirtReg
, &PhysReg2LiveUnion
[*AliasI
]);
172 if (subQ
.checkInterference())
178 /// getSingleInterference - Return the single interfering virtual register
179 /// assigned to PhysReg. Return 0 if more than one virtual register is
181 LiveInterval
*RAGreedy::getSingleInterference(LiveInterval
&VirtReg
,
183 // Check physreg and aliases.
184 LiveInterval
*Interference
= 0;
185 for (const unsigned *AliasI
= TRI
->getOverlaps(PhysReg
); *AliasI
; ++AliasI
) {
186 LiveIntervalUnion::Query
&Q
= query(VirtReg
, *AliasI
);
187 if (Q
.checkInterference()) {
190 Q
.collectInterferingVRegs(1);
191 if (!Q
.seenAllInterferences())
193 Interference
= Q
.interferingVRegs().front();
199 // Attempt to reassign this virtual register to a different physical register.
201 // FIXME: we are not yet caching these "second-level" interferences discovered
202 // in the sub-queries. These interferences can change with each call to
203 // selectOrSplit. However, we could implement a "may-interfere" cache that
204 // could be conservatively dirtied when we reassign or split.
206 // FIXME: This may result in a lot of alias queries. We could summarize alias
207 // live intervals in their parent register's live union, but it's messy.
208 bool RAGreedy::reassignVReg(LiveInterval
&InterferingVReg
,
209 unsigned WantedPhysReg
) {
210 assert(TargetRegisterInfo::isVirtualRegister(InterferingVReg
.reg
) &&
211 "Can only reassign virtual registers");
212 assert(TRI
->regsOverlap(WantedPhysReg
, VRM
->getPhys(InterferingVReg
.reg
)) &&
213 "inconsistent phys reg assigment");
215 AllocationOrder
Order(InterferingVReg
.reg
, *VRM
, ReservedRegs
);
216 while (unsigned PhysReg
= Order
.next()) {
217 // Don't reassign to a WantedPhysReg alias.
218 if (TRI
->regsOverlap(PhysReg
, WantedPhysReg
))
221 if (checkUncachedInterference(InterferingVReg
, PhysReg
))
224 // Reassign the interfering virtual reg to this physical reg.
225 unsigned OldAssign
= VRM
->getPhys(InterferingVReg
.reg
);
226 DEBUG(dbgs() << "reassigning: " << InterferingVReg
<< " from " <<
227 TRI
->getName(OldAssign
) << " to " << TRI
->getName(PhysReg
) << '\n');
228 PhysReg2LiveUnion
[OldAssign
].extract(InterferingVReg
);
229 VRM
->clearVirt(InterferingVReg
.reg
);
230 VRM
->assignVirt2Phys(InterferingVReg
.reg
, PhysReg
);
231 PhysReg2LiveUnion
[PhysReg
].unify(InterferingVReg
);
238 /// reassignInterferences - Reassign all interferences to different physical
239 /// registers such that Virtreg can be assigned to PhysReg.
240 /// Currently this only works with a single interference.
241 /// @param VirtReg Currently unassigned virtual register.
242 /// @param PhysReg Physical register to be cleared.
243 /// @return True on success, false if nothing was changed.
244 bool RAGreedy::reassignInterferences(LiveInterval
&VirtReg
, unsigned PhysReg
) {
245 LiveInterval
*InterferingVReg
= getSingleInterference(VirtReg
, PhysReg
);
246 if (!InterferingVReg
)
248 if (TargetRegisterInfo::isPhysicalRegister(InterferingVReg
->reg
))
250 return reassignVReg(*InterferingVReg
, PhysReg
);
253 /// tryReassign - Try to reassign interferences to different physregs.
254 /// @param VirtReg Currently unassigned virtual register.
255 /// @param Order Physregs to try.
256 /// @return Physreg to assign VirtReg, or 0.
257 unsigned RAGreedy::tryReassign(LiveInterval
&VirtReg
, AllocationOrder
&Order
) {
258 NamedRegionTimer
T("Reassign", TimerGroupName
, TimePassesIsEnabled
);
260 while (unsigned PhysReg
= Order
.next())
261 if (reassignInterferences(VirtReg
, PhysReg
))
266 /// findInterferenceFreeReg - Find a physical register in Order where Loop has
267 /// no interferences with VirtReg.
268 unsigned RAGreedy::findInterferenceFreeReg(MachineLoopRange
*Loop
,
269 LiveInterval
&VirtReg
,
270 AllocationOrder
&Order
) {
272 while (unsigned PhysReg
= Order
.next()) {
273 bool interference
= false;
274 for (const unsigned *AI
= TRI
->getOverlaps(PhysReg
); *AI
; ++AI
) {
275 if (query(VirtReg
, *AI
).checkLoopInterference(Loop
)) {
287 /// trySplit - Try to split VirtReg or one of its interferences, making it
289 /// @return Physreg when VirtReg may be assigned and/or new SplitVRegs.
290 unsigned RAGreedy::trySplit(LiveInterval
&VirtReg
, AllocationOrder
&Order
,
291 SmallVectorImpl
<LiveInterval
*>&SplitVRegs
) {
292 NamedRegionTimer
T("Splitter", TimerGroupName
, TimePassesIsEnabled
);
293 SA
->analyze(&VirtReg
);
295 // Get the set of loops that have VirtReg uses and are splittable.
296 SplitAnalysis::LoopPtrSet SplitLoopSet
;
297 SA
->getSplitLoops(SplitLoopSet
);
299 // Order loops by descending area.
300 SmallVector
<MachineLoopRange
*, 8> SplitLoops
;
301 for (SplitAnalysis::LoopPtrSet::const_iterator I
= SplitLoopSet
.begin(),
302 E
= SplitLoopSet
.end(); I
!= E
; ++I
)
303 SplitLoops
.push_back(LoopRanges
->getLoopRange(*I
));
304 array_pod_sort(SplitLoops
.begin(), SplitLoops
.end(),
305 MachineLoopRange::byAreaDesc
);
307 // Find the first loop that is interference-free for some register in the
309 MachineLoopRange
*Loop
= 0;
310 for (unsigned i
= 0, e
= SplitLoops
.size(); i
!= e
; ++i
) {
311 if (unsigned PhysReg
= findInterferenceFreeReg(SplitLoops
[i
],
314 Loop
= SplitLoops
[i
];
315 DEBUG(dbgs() << " " << TRI
->getName(PhysReg
)
316 << " has no interferences in " << *Loop
<< '\n');
322 DEBUG(dbgs() << " All candidate loops have interference.\n");
326 // Execute the split around Loop.
327 SmallVector
<LiveInterval
*, 4> SpillRegs
;
328 LiveRangeEdit
LREdit(VirtReg
, SplitVRegs
, SpillRegs
);
329 SplitEditor(*SA
, *LIS
, *VRM
, *DomTree
, LREdit
)
330 .splitAroundLoop(Loop
->getLoop());
333 MF
->verify(this, "After splitting live range around loop");
335 // We have new split regs, don't assign anything.
339 unsigned RAGreedy::selectOrSplit(LiveInterval
&VirtReg
,
340 SmallVectorImpl
<LiveInterval
*> &SplitVRegs
) {
341 // Populate a list of physical register spill candidates.
342 SmallVector
<unsigned, 8> PhysRegSpillCands
;
344 // Check for an available register in this class.
345 AllocationOrder
Order(VirtReg
.reg
, *VRM
, ReservedRegs
);
346 while (unsigned PhysReg
= Order
.next()) {
347 // Check interference and as a side effect, intialize queries for this
348 // VirtReg and its aliases.
349 unsigned InterfReg
= checkPhysRegInterference(VirtReg
, PhysReg
);
350 if (InterfReg
== 0) {
351 // Found an available register.
354 assert(!VirtReg
.empty() && "Empty VirtReg has interference");
355 LiveInterval
*InterferingVirtReg
=
356 Queries
[InterfReg
].firstInterference().liveUnionPos().value();
358 // The current VirtReg must either be spillable, or one of its interferences
359 // must have less spill weight.
360 if (InterferingVirtReg
->weight
< VirtReg
.weight
)
361 PhysRegSpillCands
.push_back(PhysReg
);
364 // Try to reassign interferences.
365 if (unsigned PhysReg
= tryReassign(VirtReg
, Order
))
368 // Try splitting VirtReg or interferences.
369 unsigned PhysReg
= trySplit(VirtReg
, Order
, SplitVRegs
);
370 if (PhysReg
|| !SplitVRegs
.empty())
373 // Try to spill another interfering reg with less spill weight.
374 NamedRegionTimer
T("Spiller", TimerGroupName
, TimePassesIsEnabled
);
376 // FIXME: do this in two steps: (1) check for unspillable interferences while
377 // accumulating spill weight; (2) spill the interferences with lowest
378 // aggregate spill weight.
379 for (SmallVectorImpl
<unsigned>::iterator PhysRegI
= PhysRegSpillCands
.begin(),
380 PhysRegE
= PhysRegSpillCands
.end(); PhysRegI
!= PhysRegE
; ++PhysRegI
) {
382 if (!spillInterferences(VirtReg
, *PhysRegI
, SplitVRegs
)) continue;
384 assert(checkPhysRegInterference(VirtReg
, *PhysRegI
) == 0 &&
385 "Interference after spill.");
386 // Tell the caller to allocate to this newly freed physical register.
390 // No other spill candidates were found, so spill the current VirtReg.
391 DEBUG(dbgs() << "spilling: " << VirtReg
<< '\n');
392 SmallVector
<LiveInterval
*, 1> pendingSpills
;
394 spiller().spill(&VirtReg
, SplitVRegs
, pendingSpills
);
396 // The live virtual register requesting allocation was spilled, so tell
397 // the caller not to allocate anything during this round.
401 bool RAGreedy::runOnMachineFunction(MachineFunction
&mf
) {
402 DEBUG(dbgs() << "********** GREEDY REGISTER ALLOCATION **********\n"
403 << "********** Function: "
404 << ((Value
*)mf
.getFunction())->getName() << '\n');
408 MF
->verify(this, "Before greedy register allocator");
410 RegAllocBase::init(getAnalysis
<VirtRegMap
>(), getAnalysis
<LiveIntervals
>());
411 DomTree
= &getAnalysis
<MachineDominatorTree
>();
412 ReservedRegs
= TRI
->getReservedRegs(*MF
);
413 SpillerInstance
.reset(createInlineSpiller(*this, *MF
, *VRM
));
414 Loops
= &getAnalysis
<MachineLoopInfo
>();
415 LoopRanges
= &getAnalysis
<MachineLoopRanges
>();
416 SA
.reset(new SplitAnalysis(*MF
, *LIS
, *Loops
));
423 NamedRegionTimer
T("Rewriter", TimerGroupName
, TimePassesIsEnabled
);
424 std::auto_ptr
<VirtRegRewriter
> rewriter(createVirtRegRewriter());
425 rewriter
->runOnMachineFunction(*MF
, *VRM
, LIS
);
428 // The pass output is in VirtRegMap. Release all the transient data.