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 an iterative scan register
11 // allocator. Iterative scan is a linear scan variant with the
12 // following difference:
14 // It performs linear scan and keeps a list of the registers it cannot
15 // allocate. It then spills all those registers and repeats the
16 // process until allocation succeeds.
18 //===----------------------------------------------------------------------===//
20 #define DEBUG_TYPE "regalloc"
21 #include "llvm/Function.h"
22 #include "llvm/CodeGen/MachineFunctionPass.h"
23 #include "llvm/CodeGen/MachineInstr.h"
24 #include "llvm/CodeGen/Passes.h"
25 #include "llvm/CodeGen/SSARegMap.h"
26 #include "llvm/Target/MRegisterInfo.h"
27 #include "llvm/Target/TargetMachine.h"
28 #include "llvm/Support/Debug.h"
29 #include "llvm/ADT/Statistic.h"
30 #include "llvm/ADT/STLExtras.h"
31 #include "LiveIntervalAnalysis.h"
32 #include "PhysRegTracker.h"
33 #include "VirtRegMap.h"
42 Statistic<double> efficiency
43 ("regalloc", "Ratio of intervals processed over total intervals");
45 static unsigned numIterations = 0;
46 static unsigned numIntervals = 0;
48 class RA : public MachineFunctionPass {
51 const TargetMachine* tm_;
52 const MRegisterInfo* mri_;
55 typedef std::vector<LiveInterval*> IntervalPtrs;
56 IntervalPtrs unhandled_, fixed_, active_, inactive_, handled_, spilled_;
58 std::auto_ptr<PhysRegTracker> prt_;
59 std::auto_ptr<VirtRegMap> vrm_;
60 std::auto_ptr<Spiller> spiller_;
62 typedef std::vector<float> SpillWeights;
63 SpillWeights spillWeights_;
66 virtual const char* getPassName() const {
67 return "Iterative Scan Register Allocator";
70 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
71 AU.addRequired<LiveIntervals>();
72 MachineFunctionPass::getAnalysisUsage(AU);
75 /// runOnMachineFunction - register allocate the whole function
76 bool runOnMachineFunction(MachineFunction&);
81 /// linearScan - the linear scan algorithm. Returns a boolean
82 /// indicating if there were any spills
85 /// initIntervalSets - initializes the four interval sets:
86 /// unhandled, fixed, active and inactive
87 void initIntervalSets();
89 /// processActiveIntervals - expire old intervals and move
90 /// non-overlapping ones to the incative list
91 void processActiveIntervals(IntervalPtrs::value_type cur);
93 /// processInactiveIntervals - expire old intervals and move
94 /// overlapping ones to the active list
95 void processInactiveIntervals(IntervalPtrs::value_type cur);
97 /// updateSpillWeights - updates the spill weights of the
98 /// specifed physical register and its weight
99 void updateSpillWeights(unsigned reg, SpillWeights::value_type weight);
101 /// assignRegOrStackSlotAtInterval - assign a register if one
102 /// is available, or spill.
103 void assignRegOrSpillAtInterval(IntervalPtrs::value_type cur);
106 /// register handling helpers
109 /// getFreePhysReg - return a free physical register for this
110 /// virtual register interval if we have one, otherwise return
112 unsigned getFreePhysReg(IntervalPtrs::value_type cur);
114 /// assignVirt2StackSlot - assigns this virtual register to a
115 /// stack slot. returns the stack slot
116 int assignVirt2StackSlot(unsigned virtReg);
118 void printIntervals(const char* const str,
119 RA::IntervalPtrs::const_iterator i,
120 RA::IntervalPtrs::const_iterator e) const {
121 if (str) std::cerr << str << " intervals:\n";
122 for (; i != e; ++i) {
123 std::cerr << "\t" << **i << " -> ";
124 unsigned reg = (*i)->reg;
125 if (MRegisterInfo::isVirtualRegister(reg)) {
126 reg = vrm_->getPhys(reg);
128 std::cerr << mri_->getName(reg) << '\n';
134 void RA::releaseMemory()
144 bool RA::runOnMachineFunction(MachineFunction &fn) {
146 tm_ = &fn.getTarget();
147 mri_ = tm_->getRegisterInfo();
148 li_ = &getAnalysis<LiveIntervals>();
150 PhysRegsUsed = new bool[mri_->getNumRegs()];
151 std::fill(PhysRegsUsed, PhysRegsUsed+mri_->getNumRegs(), false);
152 fn.setUsedPhysRegs(PhysRegsUsed);
154 if (!prt_.get()) prt_.reset(new PhysRegTracker(*mri_));
155 vrm_.reset(new VirtRegMap(*mf_));
156 if (!spiller_.get()) spiller_.reset(createSpiller());
160 numIntervals += li_->getNumIntervals();
162 while (linearScan()) {
163 // we spilled some registers, so we need to add intervals for
164 // the spill code and restart the algorithm
165 std::set<unsigned> spilledRegs;
166 for (IntervalPtrs::iterator
167 i = spilled_.begin(); i != spilled_.end(); ++i) {
168 int slot = vrm_->assignVirt2StackSlot((*i)->reg);
169 std::vector<LiveInterval*> added =
170 li_->addIntervalsForSpills(**i, *vrm_, slot);
171 std::copy(added.begin(), added.end(), std::back_inserter(handled_));
172 spilledRegs.insert((*i)->reg);
175 for (IntervalPtrs::iterator
176 i = handled_.begin(); i != handled_.end(); )
177 if (spilledRegs.count((*i)->reg))
178 i = handled_.erase(i);
181 handled_.swap(unhandled_);
182 vrm_->clearAllVirt();
185 efficiency = double(numIterations) / double(numIntervals);
187 DEBUG(std::cerr << *vrm_);
189 spiller_->runOnMachineFunction(*mf_, *vrm_);
194 bool RA::linearScan()
196 // linear scan algorithm
197 DEBUG(std::cerr << "********** LINEAR SCAN **********\n");
198 DEBUG(std::cerr << "********** Function: "
199 << mf_->getFunction()->getName() << '\n');
202 std::sort(unhandled_.begin(), unhandled_.end(),
203 greater_ptr<LiveInterval>());
204 DEBUG(printIntervals("unhandled", unhandled_.begin(), unhandled_.end()));
205 DEBUG(printIntervals("fixed", fixed_.begin(), fixed_.end()));
206 DEBUG(printIntervals("active", active_.begin(), active_.end()));
207 DEBUG(printIntervals("inactive", inactive_.begin(), inactive_.end()));
209 while (!unhandled_.empty()) {
210 // pick the interval with the earliest start point
211 IntervalPtrs::value_type cur = unhandled_.back();
212 unhandled_.pop_back();
214 DEBUG(std::cerr << "\n*** CURRENT ***: " << *cur << '\n');
216 processActiveIntervals(cur);
217 processInactiveIntervals(cur);
219 // if this register is fixed we are done
220 if (MRegisterInfo::isPhysicalRegister(cur->reg)) {
221 prt_->addRegUse(cur->reg);
222 active_.push_back(cur);
223 handled_.push_back(cur);
225 // otherwise we are allocating a virtual register. try to find
226 // a free physical register or spill an interval in order to
227 // assign it one (we could spill the current though).
229 assignRegOrSpillAtInterval(cur);
232 DEBUG(printIntervals("active", active_.begin(), active_.end()));
233 DEBUG(printIntervals("inactive", inactive_.begin(), inactive_.end()));
236 // expire any remaining active intervals
237 for (IntervalPtrs::reverse_iterator
238 i = active_.rbegin(); i != active_.rend(); ) {
239 unsigned reg = (*i)->reg;
240 DEBUG(std::cerr << "\tinterval " << **i << " expired\n");
241 if (MRegisterInfo::isVirtualRegister(reg))
242 reg = vrm_->getPhys(reg);
243 prt_->delRegUse(reg);
244 i = IntervalPtrs::reverse_iterator(active_.erase(i.base()-1));
247 // expire any remaining inactive intervals
248 for (IntervalPtrs::reverse_iterator
249 i = inactive_.rbegin(); i != inactive_.rend(); ) {
250 DEBUG(std::cerr << "\tinterval " << **i << " expired\n");
251 i = IntervalPtrs::reverse_iterator(inactive_.erase(i.base()-1));
254 // return true if we spilled anything
255 return !spilled_.empty();
258 void RA::initIntervalSets() {
259 assert(unhandled_.empty() && fixed_.empty() &&
260 active_.empty() && inactive_.empty() &&
261 "interval sets should be empty on initialization");
263 for (LiveIntervals::iterator i = li_->begin(), e = li_->end(); i != e; ++i){
264 unhandled_.push_back(&i->second);
265 if (MRegisterInfo::isPhysicalRegister(i->second.reg)) {
266 PhysRegsUsed[i->second.reg] = true;
267 fixed_.push_back(&i->second);
272 void RA::processActiveIntervals(IntervalPtrs::value_type cur)
274 DEBUG(std::cerr << "\tprocessing active intervals:\n");
275 IntervalPtrs::iterator ii = active_.begin(), ie = active_.end();
277 LiveInterval* i = *ii;
278 unsigned reg = i->reg;
280 // remove expired intervals
281 if (i->expiredAt(cur->beginNumber())) {
282 DEBUG(std::cerr << "\t\tinterval " << *i << " expired\n");
283 if (MRegisterInfo::isVirtualRegister(reg))
284 reg = vrm_->getPhys(reg);
285 prt_->delRegUse(reg);
286 // swap with last element and move end iterator back one position
287 std::iter_swap(ii, --ie);
289 // move inactive intervals to inactive list
290 else if (!i->liveAt(cur->beginNumber())) {
291 DEBUG(std::cerr << "\t\tinterval " << *i << " inactive\n");
292 if (MRegisterInfo::isVirtualRegister(reg))
293 reg = vrm_->getPhys(reg);
294 prt_->delRegUse(reg);
296 inactive_.push_back(i);
297 // swap with last element and move end iterator back one postion
298 std::iter_swap(ii, --ie);
304 active_.erase(ie, active_.end());
307 void RA::processInactiveIntervals(IntervalPtrs::value_type cur)
309 DEBUG(std::cerr << "\tprocessing inactive intervals:\n");
310 IntervalPtrs::iterator ii = inactive_.begin(), ie = inactive_.end();
312 LiveInterval* i = *ii;
313 unsigned reg = i->reg;
315 // remove expired intervals
316 if (i->expiredAt(cur->beginNumber())) {
317 DEBUG(std::cerr << "\t\tinterval " << *i << " expired\n");
318 // swap with last element and move end iterator back one position
319 std::iter_swap(ii, --ie);
321 // move re-activated intervals in active list
322 else if (i->liveAt(cur->beginNumber())) {
323 DEBUG(std::cerr << "\t\tinterval " << *i << " active\n");
324 if (MRegisterInfo::isVirtualRegister(reg))
325 reg = vrm_->getPhys(reg);
326 prt_->addRegUse(reg);
328 active_.push_back(i);
329 // swap with last element and move end iterator back one position
330 std::iter_swap(ii, --ie);
336 inactive_.erase(ie, inactive_.end());
339 void RA::updateSpillWeights(unsigned reg, SpillWeights::value_type weight)
341 spillWeights_[reg] += weight;
342 for (const unsigned* as = mri_->getAliasSet(reg); *as; ++as)
343 spillWeights_[*as] += weight;
346 void RA::assignRegOrSpillAtInterval(IntervalPtrs::value_type cur)
348 DEBUG(std::cerr << "\tallocating current interval: ");
350 PhysRegTracker backupPrt = *prt_;
352 spillWeights_.assign(mri_->getNumRegs(), 0.0);
354 // for each interval in active update spill weights
355 for (IntervalPtrs::const_iterator i = active_.begin(), e = active_.end();
357 unsigned reg = (*i)->reg;
358 if (MRegisterInfo::isVirtualRegister(reg))
359 reg = vrm_->getPhys(reg);
360 updateSpillWeights(reg, (*i)->weight);
363 // for every interval in inactive we overlap with, mark the
364 // register as not free and update spill weights
365 for (IntervalPtrs::const_iterator i = inactive_.begin(),
366 e = inactive_.end(); i != e; ++i) {
367 if (cur->overlaps(**i)) {
368 unsigned reg = (*i)->reg;
369 if (MRegisterInfo::isVirtualRegister(reg))
370 reg = vrm_->getPhys(reg);
371 prt_->addRegUse(reg);
372 updateSpillWeights(reg, (*i)->weight);
376 // for every interval in fixed we overlap with,
377 // mark the register as not free and update spill weights
378 for (IntervalPtrs::const_iterator i = fixed_.begin(),
379 e = fixed_.end(); i != e; ++i) {
380 if (cur->overlaps(**i)) {
381 unsigned reg = (*i)->reg;
382 prt_->addRegUse(reg);
383 updateSpillWeights(reg, (*i)->weight);
387 unsigned physReg = getFreePhysReg(cur);
388 // restore the physical register tracker
390 // if we find a free register, we are done: assign this virtual to
391 // the free physical register and add this interval to the active
394 DEBUG(std::cerr << mri_->getName(physReg) << '\n');
395 vrm_->assignVirt2Phys(cur->reg, physReg);
396 prt_->addRegUse(physReg);
397 active_.push_back(cur);
398 handled_.push_back(cur);
401 DEBUG(std::cerr << "no free registers\n");
403 DEBUG(std::cerr << "\tassigning stack slot at interval "<< *cur << ":\n");
405 float minWeight = (float)HUGE_VAL;
407 const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg);
408 for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_),
409 e = rc->allocation_order_end(*mf_); i != e; ++i) {
411 if (minWeight > spillWeights_[reg]) {
412 minWeight = spillWeights_[reg];
416 DEBUG(std::cerr << "\t\tregister with min weight: "
417 << mri_->getName(minReg) << " (" << minWeight << ")\n");
419 // if the current has the minimum weight, we spill it and move on
420 if (cur->weight <= minWeight) {
421 DEBUG(std::cerr << "\t\t\tspilling(c): " << *cur << '\n');
422 spilled_.push_back(cur);
426 // otherwise we spill all intervals aliasing the register with
427 // minimum weight, assigned the newly cleared register to the
428 // current interval and continue
429 assert(MRegisterInfo::isPhysicalRegister(minReg) &&
430 "did not choose a register to spill?");
431 std::vector<bool> toSpill(mri_->getNumRegs(), false);
432 toSpill[minReg] = true;
433 for (const unsigned* as = mri_->getAliasSet(minReg); *as; ++as)
435 unsigned earliestStart = cur->beginNumber();
437 std::set<unsigned> spilled;
439 for (IntervalPtrs::iterator i = active_.begin(); i != active_.end(); ) {
440 unsigned reg = (*i)->reg;
441 if (MRegisterInfo::isVirtualRegister(reg) &&
442 toSpill[vrm_->getPhys(reg)] &&
443 cur->overlaps(**i)) {
444 DEBUG(std::cerr << "\t\t\tspilling(a): " << **i << '\n');
445 spilled_.push_back(*i);
446 prt_->delRegUse(vrm_->getPhys(reg));
447 vrm_->clearVirt(reg);
448 i = active_.erase(i);
453 for (IntervalPtrs::iterator i = inactive_.begin(); i != inactive_.end(); ) {
454 unsigned reg = (*i)->reg;
455 if (MRegisterInfo::isVirtualRegister(reg) &&
456 toSpill[vrm_->getPhys(reg)] &&
457 cur->overlaps(**i)) {
458 DEBUG(std::cerr << "\t\t\tspilling(i): " << **i << '\n');
459 spilled_.push_back(*i);
460 vrm_->clearVirt(reg);
461 i = inactive_.erase(i);
467 vrm_->assignVirt2Phys(cur->reg, minReg);
468 prt_->addRegUse(minReg);
469 active_.push_back(cur);
470 handled_.push_back(cur);
474 unsigned RA::getFreePhysReg(LiveInterval* cur)
476 std::vector<unsigned> inactiveCounts(mri_->getNumRegs(), 0);
477 for (IntervalPtrs::iterator i = inactive_.begin(), e = inactive_.end();
479 unsigned reg = (*i)->reg;
480 if (MRegisterInfo::isVirtualRegister(reg))
481 reg = vrm_->getPhys(reg);
482 ++inactiveCounts[reg];
485 const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg);
487 unsigned freeReg = 0;
488 for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_),
489 e = rc->allocation_order_end(*mf_); i != e; ++i) {
491 if (prt_->isRegAvail(reg) &&
492 (!freeReg || inactiveCounts[freeReg] < inactiveCounts[reg]))
498 FunctionPass* llvm::createIterativeScanRegisterAllocator() {