OLD | NEW |
1 //===- subzero/src/IceRegAlloc.cpp - Linear-scan implementation -----------===// | 1 //===- subzero/src/IceRegAlloc.cpp - Linear-scan implementation -----------===// |
2 // | 2 // |
3 // The Subzero Code Generator | 3 // The Subzero Code Generator |
4 // | 4 // |
5 // This file is distributed under the University of Illinois Open Source | 5 // This file is distributed under the University of Illinois Open Source |
6 // License. See LICENSE.TXT for details. | 6 // License. See LICENSE.TXT for details. |
7 // | 7 // |
8 //===----------------------------------------------------------------------===// | 8 //===----------------------------------------------------------------------===// |
9 // | 9 // |
10 // This file implements the LinearScan class, which performs the | 10 // This file implements the LinearScan class, which performs the |
(...skipping 11 matching lines...) Expand all Loading... |
22 namespace Ice { | 22 namespace Ice { |
23 | 23 |
24 // Implements the linear-scan algorithm. Based on "Linear Scan | 24 // Implements the linear-scan algorithm. Based on "Linear Scan |
25 // Register Allocation in the Context of SSA Form and Register | 25 // Register Allocation in the Context of SSA Form and Register |
26 // Constraints" by Hanspeter Mössenböck and Michael Pfeiffer, | 26 // Constraints" by Hanspeter Mössenböck and Michael Pfeiffer, |
27 // ftp://ftp.ssw.uni-linz.ac.at/pub/Papers/Moe02.PDF . This | 27 // ftp://ftp.ssw.uni-linz.ac.at/pub/Papers/Moe02.PDF . This |
28 // implementation is modified to take affinity into account and allow | 28 // implementation is modified to take affinity into account and allow |
29 // two interfering variables to share the same register in certain | 29 // two interfering variables to share the same register in certain |
30 // cases. | 30 // cases. |
31 // | 31 // |
32 // Requires running Cfg::liveness(Liveness_RangesFull) in | 32 // Requires running Cfg::liveness(Liveness_Intervals) in |
33 // preparation. Results are assigned to Variable::RegNum for each | 33 // preparation. Results are assigned to Variable::RegNum for each |
34 // Variable. | 34 // Variable. |
35 void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull) { | 35 void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull) { |
36 assert(RegMaskFull.any()); // Sanity check | 36 assert(RegMaskFull.any()); // Sanity check |
37 Unhandled.clear(); | 37 Unhandled.clear(); |
38 Handled.clear(); | 38 Handled.clear(); |
39 Inactive.clear(); | 39 Inactive.clear(); |
40 Active.clear(); | 40 Active.clear(); |
41 Ostream &Str = Func->getContext()->getStrDump(); | 41 Ostream &Str = Func->getContext()->getStrDump(); |
42 Func->setCurrentNode(NULL); | 42 Func->resetCurrentNode(); |
43 | 43 |
44 // Gather the live ranges of all variables and add them to the | 44 // Gather the live ranges of all variables and add them to the |
45 // Unhandled set. TODO: Unhandled is a set<> which is based on a | 45 // Unhandled set. TODO: Unhandled is a set<> which is based on a |
46 // balanced binary tree, so inserting live ranges for N variables is | 46 // balanced binary tree, so inserting live ranges for N variables is |
47 // O(N log N) complexity. N may be proportional to the number of | 47 // O(N log N) complexity. N may be proportional to the number of |
48 // instructions, thanks to temporary generation during lowering. As | 48 // instructions, thanks to temporary generation during lowering. As |
49 // a result, it may be useful to design a better data structure for | 49 // a result, it may be useful to design a better data structure for |
50 // storing Func->getVariables(). | 50 // storing Func->getVariables(). |
51 const VarList &Vars = Func->getVariables(); | 51 const VarList &Vars = Func->getVariables(); |
52 for (VarList::const_iterator I = Vars.begin(), E = Vars.end(); I != E; ++I) { | 52 for (VarList::const_iterator I = Vars.begin(), E = Vars.end(); I != E; ++I) { |
(...skipping 387 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
440 snprintf(buf, BufLen, "%2d", Var->getRegNumTmp()); | 440 snprintf(buf, BufLen, "%2d", Var->getRegNumTmp()); |
441 Str << "R=" << buf << " V="; | 441 Str << "R=" << buf << " V="; |
442 Var->dump(Func); | 442 Var->dump(Func); |
443 Str << " Range=" << range(); | 443 Str << " Range=" << range(); |
444 } | 444 } |
445 | 445 |
446 void LinearScan::dump(Cfg *Func) const { | 446 void LinearScan::dump(Cfg *Func) const { |
447 Ostream &Str = Func->getContext()->getStrDump(); | 447 Ostream &Str = Func->getContext()->getStrDump(); |
448 if (!Func->getContext()->isVerbose(IceV_LinearScan)) | 448 if (!Func->getContext()->isVerbose(IceV_LinearScan)) |
449 return; | 449 return; |
450 Func->setCurrentNode(NULL); | 450 Func->resetCurrentNode(); |
451 Str << "**** Current regalloc state:\n"; | 451 Str << "**** Current regalloc state:\n"; |
452 Str << "++++++ Handled:\n"; | 452 Str << "++++++ Handled:\n"; |
453 for (UnorderedRanges::const_iterator I = Handled.begin(), E = Handled.end(); | 453 for (UnorderedRanges::const_iterator I = Handled.begin(), E = Handled.end(); |
454 I != E; ++I) { | 454 I != E; ++I) { |
455 I->dump(Func); | 455 I->dump(Func); |
456 Str << "\n"; | 456 Str << "\n"; |
457 } | 457 } |
458 Str << "++++++ Unhandled:\n"; | 458 Str << "++++++ Unhandled:\n"; |
459 for (OrderedRanges::const_iterator I = Unhandled.begin(), E = Unhandled.end(); | 459 for (OrderedRanges::const_iterator I = Unhandled.begin(), E = Unhandled.end(); |
460 I != E; ++I) { | 460 I != E; ++I) { |
461 I->dump(Func); | 461 I->dump(Func); |
462 Str << "\n"; | 462 Str << "\n"; |
463 } | 463 } |
464 Str << "++++++ Active:\n"; | 464 Str << "++++++ Active:\n"; |
465 for (UnorderedRanges::const_iterator I = Active.begin(), E = Active.end(); | 465 for (UnorderedRanges::const_iterator I = Active.begin(), E = Active.end(); |
466 I != E; ++I) { | 466 I != E; ++I) { |
467 I->dump(Func); | 467 I->dump(Func); |
468 Str << "\n"; | 468 Str << "\n"; |
469 } | 469 } |
470 Str << "++++++ Inactive:\n"; | 470 Str << "++++++ Inactive:\n"; |
471 for (UnorderedRanges::const_iterator I = Inactive.begin(), E = Inactive.end(); | 471 for (UnorderedRanges::const_iterator I = Inactive.begin(), E = Inactive.end(); |
472 I != E; ++I) { | 472 I != E; ++I) { |
473 I->dump(Func); | 473 I->dump(Func); |
474 Str << "\n"; | 474 Str << "\n"; |
475 } | 475 } |
476 } | 476 } |
477 | 477 |
478 } // end of namespace Ice | 478 } // end of namespace Ice |
OLD | NEW |