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