| 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 |