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 "RegAllocBase.h"
20 #include "VirtRegMap.h"
21 #include "VirtRegRewriter.h"
22 #include "llvm/Analysis/AliasAnalysis.h"
23 #include "llvm/Function.h"
24 #include "llvm/PassAnalysisSupport.h"
25 #include "llvm/CodeGen/CalcSpillWeights.h"
26 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
27 #include "llvm/CodeGen/LiveStackAnalysis.h"
28 #include "llvm/CodeGen/MachineFunctionPass.h"
29 #include "llvm/CodeGen/MachineLoopInfo.h"
30 #include "llvm/CodeGen/MachineRegisterInfo.h"
31 #include "llvm/CodeGen/Passes.h"
32 #include "llvm/CodeGen/RegAllocRegistry.h"
33 #include "llvm/CodeGen/RegisterCoalescer.h"
34 #include "llvm/Target/TargetOptions.h"
35 #include "llvm/Support/Debug.h"
36 #include "llvm/Support/ErrorHandling.h"
37 #include "llvm/Support/raw_ostream.h"
38 #include "llvm/Support/Timer.h"
42 static RegisterRegAlloc greedyRegAlloc("greedy", "greedy register allocator",
43 createGreedyRegisterAllocator);
46 class RAGreedy : public MachineFunctionPass, public RegAllocBase {
49 BitVector ReservedRegs;
55 std::auto_ptr<Spiller> SpillerInstance;
60 /// Return the pass name.
61 virtual const char* getPassName() const {
62 return "Greedy Register Allocator";
65 /// RAGreedy analysis usage.
66 virtual void getAnalysisUsage(AnalysisUsage &AU) const;
68 virtual void releaseMemory();
70 virtual Spiller &spiller() { return *SpillerInstance; }
72 virtual float getPriority(LiveInterval *LI);
74 virtual unsigned selectOrSplit(LiveInterval &VirtReg,
75 SmallVectorImpl<LiveInterval*> &SplitVRegs);
77 /// Perform register allocation.
78 virtual bool runOnMachineFunction(MachineFunction &mf);
83 bool checkUncachedInterference(LiveInterval&, unsigned);
84 LiveInterval *getSingleInterference(LiveInterval&, unsigned);
85 bool reassignVReg(LiveInterval &InterferingVReg, unsigned OldPhysReg);
86 bool reassignInterferences(LiveInterval &VirtReg, unsigned PhysReg);
88 unsigned tryReassign(LiveInterval&, AllocationOrder&);
89 unsigned trySplit(LiveInterval&, AllocationOrder&,
90 SmallVectorImpl<LiveInterval*>&);
92 } // end anonymous namespace
94 char RAGreedy::ID = 0;
96 FunctionPass* llvm::createGreedyRegisterAllocator() {
97 return new RAGreedy();
100 RAGreedy::RAGreedy(): MachineFunctionPass(ID) {
101 initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
102 initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
103 initializeStrongPHIEliminationPass(*PassRegistry::getPassRegistry());
104 initializeRegisterCoalescerAnalysisGroup(*PassRegistry::getPassRegistry());
105 initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry());
106 initializeLiveStacksPass(*PassRegistry::getPassRegistry());
107 initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry());
108 initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry());
109 initializeVirtRegMapPass(*PassRegistry::getPassRegistry());
112 void RAGreedy::getAnalysisUsage(AnalysisUsage &AU) const {
113 AU.setPreservesCFG();
114 AU.addRequired<AliasAnalysis>();
115 AU.addPreserved<AliasAnalysis>();
116 AU.addRequired<LiveIntervals>();
117 AU.addPreserved<SlotIndexes>();
119 AU.addRequiredID(StrongPHIEliminationID);
120 AU.addRequiredTransitive<RegisterCoalescer>();
121 AU.addRequired<CalculateSpillWeights>();
122 AU.addRequired<LiveStacks>();
123 AU.addPreserved<LiveStacks>();
124 AU.addRequiredID(MachineDominatorsID);
125 AU.addPreservedID(MachineDominatorsID);
126 AU.addRequired<MachineLoopInfo>();
127 AU.addPreserved<MachineLoopInfo>();
128 AU.addRequired<VirtRegMap>();
129 AU.addPreserved<VirtRegMap>();
130 MachineFunctionPass::getAnalysisUsage(AU);
133 void RAGreedy::releaseMemory() {
134 SpillerInstance.reset(0);
135 RegAllocBase::releaseMemory();
138 float RAGreedy::getPriority(LiveInterval *LI) {
139 float Priority = LI->weight;
141 // Prioritize hinted registers so they are allocated first.
142 std::pair<unsigned, unsigned> Hint;
143 if (Hint.first || Hint.second) {
144 // The hint can be target specific, a virtual register, or a physreg.
147 // Prefer physreg hints above anything else.
148 if (Hint.first == 0 && TargetRegisterInfo::isPhysicalRegister(Hint.second))
154 // Check interference without using the cache.
155 bool RAGreedy::checkUncachedInterference(LiveInterval &VirtReg,
157 LiveIntervalUnion::Query subQ(&VirtReg, &PhysReg2LiveUnion[PhysReg]);
158 if (subQ.checkInterference())
160 for (const unsigned *AliasI = TRI->getAliasSet(PhysReg); *AliasI; ++AliasI) {
161 subQ.init(&VirtReg, &PhysReg2LiveUnion[*AliasI]);
162 if (subQ.checkInterference())
168 /// getSingleInterference - Return the single interfering virtual register
169 /// assigned to PhysReg. Return 0 if more than one virtual register is
171 LiveInterval *RAGreedy::getSingleInterference(LiveInterval &VirtReg,
173 LiveInterval *Interference = 0;
175 // Check direct interferences.
176 LiveIntervalUnion::Query &Q = query(VirtReg, PhysReg);
177 if (Q.checkInterference()) {
178 if (!Q.seenAllInterferences())
180 Q.collectInterferingVRegs(1);
181 Interference = Q.interferingVRegs().front();
185 for (const unsigned *AliasI = TRI->getAliasSet(PhysReg); *AliasI; ++AliasI) {
186 LiveIntervalUnion::Query &Q = query(VirtReg, *AliasI);
187 if (Q.checkInterference()) {
188 if (Interference || !Q.seenAllInterferences())
190 Q.collectInterferingVRegs(1);
191 Interference = Q.interferingVRegs().front();
197 // Attempt to reassign this virtual register to a different physical register.
199 // FIXME: we are not yet caching these "second-level" interferences discovered
200 // in the sub-queries. These interferences can change with each call to
201 // selectOrSplit. However, we could implement a "may-interfere" cache that
202 // could be conservatively dirtied when we reassign or split.
204 // FIXME: This may result in a lot of alias queries. We could summarize alias
205 // live intervals in their parent register's live union, but it's messy.
206 bool RAGreedy::reassignVReg(LiveInterval &InterferingVReg,
207 unsigned WantedPhysReg) {
208 assert(TargetRegisterInfo::isVirtualRegister(InterferingVReg.reg) &&
209 "Can only reassign virtual registers");
210 assert(TRI->regsOverlap(WantedPhysReg, VRM->getPhys(InterferingVReg.reg)) &&
211 "inconsistent phys reg assigment");
213 AllocationOrder Order(InterferingVReg.reg, *VRM, ReservedRegs);
214 while (unsigned PhysReg = Order.next()) {
215 // Don't reassign to a WantedPhysReg alias.
216 if (TRI->regsOverlap(PhysReg, WantedPhysReg))
219 if (checkUncachedInterference(InterferingVReg, PhysReg))
222 // Reassign the interfering virtual reg to this physical reg.
223 unsigned OldAssign = VRM->getPhys(InterferingVReg.reg);
224 DEBUG(dbgs() << "reassigning: " << InterferingVReg << " from " <<
225 TRI->getName(OldAssign) << " to " << TRI->getName(PhysReg) << '\n');
226 PhysReg2LiveUnion[OldAssign].extract(InterferingVReg);
227 VRM->clearVirt(InterferingVReg.reg);
228 VRM->assignVirt2Phys(InterferingVReg.reg, PhysReg);
229 PhysReg2LiveUnion[PhysReg].unify(InterferingVReg);
236 /// reassignInterferences - Reassign all interferences to different physical
237 /// registers such that Virtreg can be assigned to PhysReg.
238 /// Currently this only works with a single interference.
239 /// @param VirtReg Currently unassigned virtual register.
240 /// @param PhysReg Physical register to be cleared.
241 /// @return True on success, false if nothing was changed.
242 bool RAGreedy::reassignInterferences(LiveInterval &VirtReg, unsigned PhysReg) {
243 LiveInterval *InterferingVReg = getSingleInterference(VirtReg, PhysReg);
244 if (!InterferingVReg)
246 if (TargetRegisterInfo::isPhysicalRegister(InterferingVReg->reg))
248 return reassignVReg(*InterferingVReg, PhysReg);
251 /// tryReassign - Try to reassign interferences to different physregs.
252 /// @param VirtReg Currently unassigned virtual register.
253 /// @param Order Physregs to try.
254 /// @return Physreg to assign VirtReg, or 0.
255 unsigned RAGreedy::tryReassign(LiveInterval &VirtReg, AllocationOrder &Order) {
256 NamedRegionTimer T("Reassign", TimerGroupName, TimePassesIsEnabled);
258 while (unsigned PhysReg = Order.next())
259 if (reassignInterferences(VirtReg, PhysReg))
264 /// trySplit - Try to split VirtReg or one of its interferences, making it
266 /// @return Physreg when VirtReg may be assigned and/or new SplitVRegs.
267 unsigned RAGreedy::trySplit(LiveInterval &VirtReg, AllocationOrder &Order,
268 SmallVectorImpl<LiveInterval*>&SplitVRegs) {
269 NamedRegionTimer T("Splitter", TimerGroupName, TimePassesIsEnabled);
273 unsigned RAGreedy::selectOrSplit(LiveInterval &VirtReg,
274 SmallVectorImpl<LiveInterval*> &SplitVRegs) {
275 // Populate a list of physical register spill candidates.
276 SmallVector<unsigned, 8> PhysRegSpillCands;
278 // Check for an available register in this class.
279 AllocationOrder Order(VirtReg.reg, *VRM, ReservedRegs);
280 while (unsigned PhysReg = Order.next()) {
281 // Check interference and as a side effect, intialize queries for this
282 // VirtReg and its aliases.
283 unsigned InterfReg = checkPhysRegInterference(VirtReg, PhysReg);
284 if (InterfReg == 0) {
285 // Found an available register.
288 assert(!VirtReg.empty() && "Empty VirtReg has interference");
289 LiveInterval *InterferingVirtReg =
290 Queries[InterfReg].firstInterference().liveUnionPos().value();
292 // The current VirtReg must either be spillable, or one of its interferences
293 // must have less spill weight.
294 if (InterferingVirtReg->weight < VirtReg.weight )
295 PhysRegSpillCands.push_back(PhysReg);
298 // Try to reassign interferences.
299 if (unsigned PhysReg = tryReassign(VirtReg, Order))
302 // Try splitting VirtReg or interferences.
303 unsigned PhysReg = trySplit(VirtReg, Order, SplitVRegs);
304 if (PhysReg || !SplitVRegs.empty())
307 // Try to spill another interfering reg with less spill weight.
308 NamedRegionTimer T("Spiller", TimerGroupName, TimePassesIsEnabled);
310 // FIXME: do this in two steps: (1) check for unspillable interferences while
311 // accumulating spill weight; (2) spill the interferences with lowest
312 // aggregate spill weight.
313 for (SmallVectorImpl<unsigned>::iterator PhysRegI = PhysRegSpillCands.begin(),
314 PhysRegE = PhysRegSpillCands.end(); PhysRegI != PhysRegE; ++PhysRegI) {
316 if (!spillInterferences(VirtReg, *PhysRegI, SplitVRegs)) continue;
318 assert(checkPhysRegInterference(VirtReg, *PhysRegI) == 0 &&
319 "Interference after spill.");
320 // Tell the caller to allocate to this newly freed physical register.
324 // No other spill candidates were found, so spill the current VirtReg.
325 DEBUG(dbgs() << "spilling: " << VirtReg << '\n');
326 SmallVector<LiveInterval*, 1> pendingSpills;
328 spiller().spill(&VirtReg, SplitVRegs, pendingSpills);
330 // The live virtual register requesting allocation was spilled, so tell
331 // the caller not to allocate anything during this round.
335 bool RAGreedy::runOnMachineFunction(MachineFunction &mf) {
336 DEBUG(dbgs() << "********** GREEDY REGISTER ALLOCATION **********\n"
337 << "********** Function: "
338 << ((Value*)mf.getFunction())->getName() << '\n');
341 RegAllocBase::init(getAnalysis<VirtRegMap>(), getAnalysis<LiveIntervals>());
343 ReservedRegs = TRI->getReservedRegs(*MF);
344 SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM));
350 NamedRegionTimer T("Rewriter", TimerGroupName, TimePassesIsEnabled);
351 std::auto_ptr<VirtRegRewriter> rewriter(createVirtRegRewriter());
352 rewriter->runOnMachineFunction(*MF, *VRM, LIS);
355 // The pass output is in VirtRegMap. Release all the transient data.