1 //===-- RegAllocIterativeScan.cpp - Iterative Scan register allocator -----===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements a linear scan register allocator.
12 //===----------------------------------------------------------------------===//
14 #define DEBUG_TYPE "regalloc"
15 #include "llvm/Function.h"
16 #include "llvm/CodeGen/LiveVariables.h"
17 #include "llvm/CodeGen/MachineFunctionPass.h"
18 #include "llvm/CodeGen/MachineInstr.h"
19 #include "llvm/CodeGen/Passes.h"
20 #include "llvm/CodeGen/SSARegMap.h"
21 #include "llvm/Target/MRegisterInfo.h"
22 #include "llvm/Target/TargetMachine.h"
23 #include "Support/Debug.h"
24 #include "Support/Statistic.h"
25 #include "Support/STLExtras.h"
26 #include "LiveIntervals.h"
27 #include "PhysRegTracker.h"
28 #include "VirtRegMap.h"
38 Statistic<double> efficiency
39 ("regalloc", "Ratio of intervals processed over total intervals");
41 static unsigned numIterations = 0;
42 static unsigned numIntervals = 0;
44 class RA : public MachineFunctionPass {
47 const TargetMachine* tm_;
48 const MRegisterInfo* mri_;
50 typedef std::list<LiveInterval*> IntervalPtrs;
51 IntervalPtrs unhandled_, fixed_, active_, inactive_, handled_, spilled_;
53 std::auto_ptr<PhysRegTracker> prt_;
54 std::auto_ptr<VirtRegMap> vrm_;
55 std::auto_ptr<Spiller> spiller_;
57 typedef std::vector<float> SpillWeights;
58 SpillWeights spillWeights_;
61 virtual const char* getPassName() const {
62 return "Linear Scan Register Allocator";
65 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
66 AU.addRequired<LiveVariables>();
67 AU.addRequired<LiveIntervals>();
68 MachineFunctionPass::getAnalysisUsage(AU);
71 /// runOnMachineFunction - register allocate the whole function
72 bool runOnMachineFunction(MachineFunction&);
77 /// linearScan - the linear scan algorithm. Returns a boolean
78 /// indicating if there were any spills
81 /// initIntervalSets - initializes the four interval sets:
82 /// unhandled, fixed, active and inactive
83 void initIntervalSets(LiveIntervals::Intervals& li);
85 /// processActiveIntervals - expire old intervals and move
86 /// non-overlapping ones to the incative list
87 void processActiveIntervals(IntervalPtrs::value_type cur);
89 /// processInactiveIntervals - expire old intervals and move
90 /// overlapping ones to the active list
91 void processInactiveIntervals(IntervalPtrs::value_type cur);
93 /// updateSpillWeights - updates the spill weights of the
94 /// specifed physical register and its weight
95 void updateSpillWeights(unsigned reg, SpillWeights::value_type weight);
97 /// assignRegOrStackSlotAtInterval - assign a register if one
98 /// is available, or spill.
99 void assignRegOrSpillAtInterval(IntervalPtrs::value_type cur);
102 /// register handling helpers
105 /// getFreePhysReg - return a free physical register for this
106 /// virtual register interval if we have one, otherwise return
108 unsigned getFreePhysReg(IntervalPtrs::value_type cur);
110 /// assignVirt2StackSlot - assigns this virtual register to a
111 /// stack slot. returns the stack slot
112 int assignVirt2StackSlot(unsigned virtReg);
114 void printIntervals(const char* const str,
115 RA::IntervalPtrs::const_iterator i,
116 RA::IntervalPtrs::const_iterator e) const {
117 if (str) std::cerr << str << " intervals:\n";
118 for (; i != e; ++i) {
119 std::cerr << "\t" << **i << " -> ";
120 unsigned reg = (*i)->reg;
121 if (MRegisterInfo::isVirtualRegister(reg)) {
122 reg = vrm_->getPhys(reg);
124 std::cerr << mri_->getName(reg) << '\n';
130 void RA::releaseMemory()
140 bool RA::runOnMachineFunction(MachineFunction &fn) {
142 tm_ = &fn.getTarget();
143 mri_ = tm_->getRegisterInfo();
144 li_ = &getAnalysis<LiveIntervals>();
145 if (!prt_.get()) prt_.reset(new PhysRegTracker(*mri_));
146 vrm_.reset(new VirtRegMap(*mf_));
147 if (!spiller_.get()) spiller_.reset(createSpiller());
149 initIntervalSets(li_->getIntervals());
151 numIntervals += li_->getIntervals().size();
153 while (linearScan()) {
154 // we spilled some registers, so we need to add intervals for
155 // the spill code and restart the algorithm
156 std::set<unsigned> spilledRegs;
157 for (IntervalPtrs::iterator
158 i = spilled_.begin(); i != spilled_.end(); ) {
159 int slot = vrm_->assignVirt2StackSlot((*i)->reg);
160 std::vector<LiveInterval*> added =
161 li_->addIntervalsForSpills(**i, *vrm_, slot);
162 std::copy(added.begin(), added.end(), std::back_inserter(handled_));
163 spilledRegs.insert((*i)->reg);
164 i = spilled_.erase(i);
166 for (IntervalPtrs::iterator
167 i = handled_.begin(); i != handled_.end(); )
168 if (spilledRegs.count((*i)->reg))
169 i = handled_.erase(i);
172 handled_.swap(unhandled_);
173 vrm_->clearAllVirt();
176 efficiency = double(numIterations) / double(numIntervals);
178 DEBUG(std::cerr << *vrm_);
180 spiller_->runOnMachineFunction(*mf_, *vrm_);
185 bool RA::linearScan()
187 // linear scan algorithm
188 DEBUG(std::cerr << "********** LINEAR SCAN **********\n");
189 DEBUG(std::cerr << "********** Function: "
190 << mf_->getFunction()->getName() << '\n');
193 unhandled_.sort(less_ptr<LiveInterval>());
194 DEBUG(printIntervals("unhandled", unhandled_.begin(), unhandled_.end()));
195 DEBUG(printIntervals("fixed", fixed_.begin(), fixed_.end()));
196 DEBUG(printIntervals("active", active_.begin(), active_.end()));
197 DEBUG(printIntervals("inactive", inactive_.begin(), inactive_.end()));
199 while (!unhandled_.empty()) {
200 // pick the interval with the earliest start point
201 IntervalPtrs::value_type cur = unhandled_.front();
202 unhandled_.pop_front();
204 DEBUG(std::cerr << "\n*** CURRENT ***: " << *cur << '\n');
206 processActiveIntervals(cur);
207 processInactiveIntervals(cur);
209 // if this register is fixed we are done
210 if (MRegisterInfo::isPhysicalRegister(cur->reg)) {
211 prt_->addRegUse(cur->reg);
212 active_.push_back(cur);
213 handled_.push_back(cur);
215 // otherwise we are allocating a virtual register. try to find
216 // a free physical register or spill an interval in order to
217 // assign it one (we could spill the current though).
219 assignRegOrSpillAtInterval(cur);
222 DEBUG(printIntervals("active", active_.begin(), active_.end()));
223 DEBUG(printIntervals("inactive", inactive_.begin(), inactive_.end()));
226 // expire any remaining active intervals
227 for (IntervalPtrs::iterator i = active_.begin(); i != active_.end(); ) {
228 unsigned reg = (*i)->reg;
229 DEBUG(std::cerr << "\tinterval " << **i << " expired\n");
230 if (MRegisterInfo::isVirtualRegister(reg))
231 reg = vrm_->getPhys(reg);
232 prt_->delRegUse(reg);
233 i = active_.erase(i);
236 // expire any remaining inactive intervals
237 for (IntervalPtrs::iterator
238 i = inactive_.begin(); i != inactive_.end(); ) {
239 DEBUG(std::cerr << "\tinterval " << **i << " expired\n");
240 i = inactive_.erase(i);
243 // return true if we spilled anything
244 return !spilled_.empty();
247 void RA::initIntervalSets(LiveIntervals::Intervals& li)
249 assert(unhandled_.empty() && fixed_.empty() &&
250 active_.empty() && inactive_.empty() &&
251 "interval sets should be empty on initialization");
253 for (LiveIntervals::Intervals::iterator i = li.begin(), e = li.end();
255 unhandled_.push_back(&*i);
256 if (MRegisterInfo::isPhysicalRegister(i->reg))
257 fixed_.push_back(&*i);
261 void RA::processActiveIntervals(IntervalPtrs::value_type cur)
263 DEBUG(std::cerr << "\tprocessing active intervals:\n");
264 for (IntervalPtrs::iterator i = active_.begin(); i != active_.end();) {
265 unsigned reg = (*i)->reg;
266 // remove expired intervals
267 if ((*i)->expiredAt(cur->start())) {
268 DEBUG(std::cerr << "\t\tinterval " << **i << " expired\n");
269 if (MRegisterInfo::isVirtualRegister(reg))
270 reg = vrm_->getPhys(reg);
271 prt_->delRegUse(reg);
272 // remove from active
273 i = active_.erase(i);
275 // move inactive intervals to inactive list
276 else if (!(*i)->liveAt(cur->start())) {
277 DEBUG(std::cerr << "\t\tinterval " << **i << " inactive\n");
278 if (MRegisterInfo::isVirtualRegister(reg))
279 reg = vrm_->getPhys(reg);
280 prt_->delRegUse(reg);
282 inactive_.push_back(*i);
283 // remove from active
284 i = active_.erase(i);
292 void RA::processInactiveIntervals(IntervalPtrs::value_type cur)
294 DEBUG(std::cerr << "\tprocessing inactive intervals:\n");
295 for (IntervalPtrs::iterator i = inactive_.begin(); i != inactive_.end();) {
296 unsigned reg = (*i)->reg;
298 // remove expired intervals
299 if ((*i)->expiredAt(cur->start())) {
300 DEBUG(std::cerr << "\t\tinterval " << **i << " expired\n");
301 // remove from inactive
302 i = inactive_.erase(i);
304 // move re-activated intervals in active list
305 else if ((*i)->liveAt(cur->start())) {
306 DEBUG(std::cerr << "\t\tinterval " << **i << " active\n");
307 if (MRegisterInfo::isVirtualRegister(reg))
308 reg = vrm_->getPhys(reg);
309 prt_->addRegUse(reg);
311 active_.push_back(*i);
312 // remove from inactive
313 i = inactive_.erase(i);
321 void RA::updateSpillWeights(unsigned reg, SpillWeights::value_type weight)
323 spillWeights_[reg] += weight;
324 for (const unsigned* as = mri_->getAliasSet(reg); *as; ++as)
325 spillWeights_[*as] += weight;
328 void RA::assignRegOrSpillAtInterval(IntervalPtrs::value_type cur)
330 DEBUG(std::cerr << "\tallocating current interval: ");
332 PhysRegTracker backupPrt = *prt_;
334 spillWeights_.assign(mri_->getNumRegs(), 0.0);
336 // for each interval in active update spill weights
337 for (IntervalPtrs::const_iterator i = active_.begin(), e = active_.end();
339 unsigned reg = (*i)->reg;
340 if (MRegisterInfo::isVirtualRegister(reg))
341 reg = vrm_->getPhys(reg);
342 updateSpillWeights(reg, (*i)->weight);
345 // for every interval in inactive we overlap with, mark the
346 // register as not free and update spill weights
347 for (IntervalPtrs::const_iterator i = inactive_.begin(),
348 e = inactive_.end(); i != e; ++i) {
349 if (cur->overlaps(**i)) {
350 unsigned reg = (*i)->reg;
351 if (MRegisterInfo::isVirtualRegister(reg))
352 reg = vrm_->getPhys(reg);
353 prt_->addRegUse(reg);
354 updateSpillWeights(reg, (*i)->weight);
358 // for every interval in fixed we overlap with,
359 // mark the register as not free and update spill weights
360 for (IntervalPtrs::const_iterator i = fixed_.begin(),
361 e = fixed_.end(); i != e; ++i) {
362 if (cur->overlaps(**i)) {
363 unsigned reg = (*i)->reg;
364 prt_->addRegUse(reg);
365 updateSpillWeights(reg, (*i)->weight);
369 unsigned physReg = getFreePhysReg(cur);
370 // restore the physical register tracker
372 // if we find a free register, we are done: assign this virtual to
373 // the free physical register and add this interval to the active
376 DEBUG(std::cerr << mri_->getName(physReg) << '\n');
377 vrm_->assignVirt2Phys(cur->reg, physReg);
378 prt_->addRegUse(physReg);
379 active_.push_back(cur);
380 handled_.push_back(cur);
383 DEBUG(std::cerr << "no free registers\n");
385 DEBUG(std::cerr << "\tassigning stack slot at interval "<< *cur << ":\n");
387 float minWeight = HUGE_VAL;
389 const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg);
390 for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_);
391 i != rc->allocation_order_end(*mf_); ++i) {
393 if (minWeight > spillWeights_[reg]) {
394 minWeight = spillWeights_[reg];
398 DEBUG(std::cerr << "\t\tregister with min weight: "
399 << mri_->getName(minReg) << " (" << minWeight << ")\n");
401 // if the current has the minimum weight, we spill it and move on
402 if (cur->weight <= minWeight) {
403 DEBUG(std::cerr << "\t\t\tspilling(c): " << *cur << '\n');
404 spilled_.push_back(cur);
408 // otherwise we spill all intervals aliasing the register with
409 // minimum weight, assigned the newly cleared register to the
410 // current interval and continue
411 std::vector<LiveInterval*> added;
412 assert(MRegisterInfo::isPhysicalRegister(minReg) &&
413 "did not choose a register to spill?");
414 std::vector<bool> toSpill(mri_->getNumRegs(), false);
415 toSpill[minReg] = true;
416 for (const unsigned* as = mri_->getAliasSet(minReg); *as; ++as)
418 unsigned earliestStart = cur->start();
420 std::set<unsigned> spilled;
422 for (IntervalPtrs::iterator i = active_.begin(); i != active_.end(); ) {
423 unsigned reg = (*i)->reg;
424 if (MRegisterInfo::isVirtualRegister(reg) &&
425 toSpill[vrm_->getPhys(reg)] &&
426 cur->overlaps(**i)) {
427 DEBUG(std::cerr << "\t\t\tspilling(a): " << **i << '\n');
428 spilled_.push_back(*i);
429 prt_->delRegUse(vrm_->getPhys(reg));
430 vrm_->clearVirt(reg);
431 i = active_.erase(i);
436 for (IntervalPtrs::iterator i = inactive_.begin(); i != inactive_.end(); ) {
437 unsigned reg = (*i)->reg;
438 if (MRegisterInfo::isVirtualRegister(reg) &&
439 toSpill[vrm_->getPhys(reg)] &&
440 cur->overlaps(**i)) {
441 DEBUG(std::cerr << "\t\t\tspilling(i): " << **i << '\n');
442 spilled_.push_back(*i);
443 vrm_->clearVirt(reg);
444 i = inactive_.erase(i);
450 vrm_->assignVirt2Phys(cur->reg, minReg);
451 prt_->addRegUse(minReg);
452 active_.push_back(cur);
453 handled_.push_back(cur);
457 unsigned RA::getFreePhysReg(IntervalPtrs::value_type cur)
459 const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg);
461 for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_);
462 i != rc->allocation_order_end(*mf_); ++i) {
464 if (prt_->isRegAvail(reg))
470 FunctionPass* llvm::createIterativeScanRegisterAllocator() {