LLVM API Documentation
00001 //===-- RegClass.cpp -----------------------------------------------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // class RegClass for coloring-based register allocation for LLVM. 00011 // 00012 //===----------------------------------------------------------------------===// 00013 00014 #include "IGNode.h" 00015 #include "RegAllocCommon.h" 00016 #include "RegClass.h" 00017 #include "../SparcV9RegInfo.h" 00018 #include <iostream> 00019 00020 namespace llvm { 00021 00022 //---------------------------------------------------------------------------- 00023 // This constructor inits IG. The actual matrix is created by a call to 00024 // createInterferenceGraph() above. 00025 //---------------------------------------------------------------------------- 00026 RegClass::RegClass(const Function *M, 00027 const SparcV9RegInfo *_MRI_, 00028 const TargetRegClassInfo *_MRC_) 00029 : Meth(M), MRI(_MRI_), MRC(_MRC_), 00030 RegClassID( _MRC_->getRegClassID() ), 00031 IG(this), IGNodeStack() { 00032 if (DEBUG_RA >= RA_DEBUG_Interference) 00033 std::cerr << "Created Reg Class: " << RegClassID << "\n"; 00034 00035 IsColorUsedArr.resize(MRC->getNumOfAllRegs()); 00036 } 00037 00038 00039 00040 //---------------------------------------------------------------------------- 00041 // Main entry point for coloring a register class. 00042 //---------------------------------------------------------------------------- 00043 void RegClass::colorAllRegs() 00044 { 00045 if (DEBUG_RA >= RA_DEBUG_Coloring) 00046 std::cerr << "Coloring IG of reg class " << RegClassID << " ...\n"; 00047 // pre-color IGNodes 00048 pushAllIGNodes(); // push all IG Nodes 00049 00050 unsigned int StackSize = IGNodeStack.size(); 00051 IGNode *CurIGNode; 00052 // for all LRs on stack 00053 for (unsigned int IGN=0; IGN < StackSize; IGN++) { 00054 CurIGNode = IGNodeStack.top(); // pop the IGNode on top of stack 00055 IGNodeStack.pop(); 00056 colorIGNode (CurIGNode); // color it 00057 } 00058 } 00059 00060 00061 00062 //---------------------------------------------------------------------------- 00063 // The method for pushing all IGNodes on to the stack. 00064 //---------------------------------------------------------------------------- 00065 void RegClass::pushAllIGNodes() 00066 { 00067 bool NeedMoreSpills; 00068 00069 00070 IG.setCurDegreeOfIGNodes(); // calculate degree of IGNodes 00071 00072 // push non-constrained IGNodes 00073 bool PushedAll = pushUnconstrainedIGNodes(); 00074 00075 if (DEBUG_RA >= RA_DEBUG_Coloring) { 00076 std::cerr << " Puhsed all-unconstrained IGNodes. "; 00077 if( PushedAll ) std::cerr << " No constrained nodes left."; 00078 std::cerr << "\n"; 00079 } 00080 00081 if (PushedAll) // if NO constrained nodes left 00082 return; 00083 00084 00085 // now, we have constrained nodes. So, push one of them (the one with min 00086 // spill cost) and try to push the others as unConstrained nodes. 00087 // Repeat this. 00088 00089 do { 00090 //get node with min spill cost 00091 IGNode *IGNodeSpill = getIGNodeWithMinSpillCost(); 00092 // push that node on to stack 00093 IGNodeStack.push(IGNodeSpill); 00094 // set its OnStack flag and decrement degree of neighs 00095 IGNodeSpill->pushOnStack(); 00096 // now push NON-constrained ones, if any 00097 NeedMoreSpills = !pushUnconstrainedIGNodes(); 00098 if (DEBUG_RA >= RA_DEBUG_Coloring) 00099 std::cerr << "\nConstrained IG Node found !@!" << IGNodeSpill->getIndex(); 00100 } while(NeedMoreSpills); // repeat until we have pushed all 00101 00102 } 00103 00104 00105 00106 00107 //-------------------------------------------------------------------------- 00108 // This method goes thru all IG nodes in the IGNodeList of an IG of a 00109 // register class and push any unconstrained IG node left (that is not 00110 // already pushed) 00111 //-------------------------------------------------------------------------- 00112 00113 bool RegClass::pushUnconstrainedIGNodes() 00114 { 00115 // # of LRs for this reg class 00116 unsigned int IGNodeListSize = IG.getIGNodeList().size(); 00117 bool pushedall = true; 00118 00119 // a pass over IGNodeList 00120 for (unsigned i =0; i < IGNodeListSize; i++) { 00121 00122 // get IGNode i from IGNodeList 00123 IGNode *IGNode = IG.getIGNodeList()[i]; 00124 00125 if (!IGNode ) // can be null due to merging 00126 continue; 00127 00128 // if already pushed on stack, continue. This can happen since this 00129 // method can be called repeatedly until all constrained nodes are 00130 // pushed 00131 if (IGNode->isOnStack() ) 00132 continue; 00133 // if the degree of IGNode is lower 00134 if ((unsigned) IGNode->getCurDegree() < MRC->getNumOfAvailRegs()) { 00135 IGNodeStack.push( IGNode ); // push IGNode on to the stack 00136 IGNode->pushOnStack(); // set OnStack and dec deg of neighs 00137 00138 if (DEBUG_RA >= RA_DEBUG_Coloring) { 00139 std::cerr << " pushed un-constrained IGNode " << IGNode->getIndex() 00140 << " on to stack\n"; 00141 } 00142 } 00143 else pushedall = false; // we didn't push all live ranges 00144 00145 } // for 00146 00147 // returns true if we pushed all live ranges - else false 00148 return pushedall; 00149 } 00150 00151 00152 00153 //---------------------------------------------------------------------------- 00154 // Get the IGNode with the minimum spill cost 00155 //---------------------------------------------------------------------------- 00156 IGNode * RegClass::getIGNodeWithMinSpillCost() { 00157 unsigned int IGNodeListSize = IG.getIGNodeList().size(); 00158 double MinSpillCost = 0; 00159 IGNode *MinCostIGNode = NULL; 00160 bool isFirstNode = true; 00161 00162 // pass over IGNodeList to find the IGNode with minimum spill cost 00163 // among all IGNodes that are not yet pushed on to the stack 00164 for (unsigned int i =0; i < IGNodeListSize; i++) { 00165 IGNode *IGNode = IG.getIGNodeList()[i]; 00166 00167 if (!IGNode) // can be null due to merging 00168 continue; 00169 00170 if (!IGNode->isOnStack()) { 00171 double SpillCost = (double) IGNode->getParentLR()->getSpillCost() / 00172 (double) (IGNode->getCurDegree() + 1); 00173 00174 if (isFirstNode) { // for the first IG node 00175 MinSpillCost = SpillCost; 00176 MinCostIGNode = IGNode; 00177 isFirstNode = false; 00178 } else if (MinSpillCost > SpillCost) { 00179 MinSpillCost = SpillCost; 00180 MinCostIGNode = IGNode; 00181 } 00182 } 00183 } 00184 00185 assert (MinCostIGNode && "No IGNode to spill"); 00186 return MinCostIGNode; 00187 } 00188 00189 00190 //---------------------------------------------------------------------------- 00191 // Color the IGNode using the machine specific code. 00192 //---------------------------------------------------------------------------- 00193 void RegClass::colorIGNode(IGNode *const Node) { 00194 if (! Node->hasColor()) { // not colored as an arg etc. 00195 00196 // init all elements of to IsColorUsedAr false; 00197 clearColorsUsed(); 00198 00199 // initialize all colors used by neighbors of this node to true 00200 LiveRange *LR = Node->getParentLR(); 00201 unsigned NumNeighbors = Node->getNumOfNeighbors(); 00202 for (unsigned n=0; n < NumNeighbors; n++) { 00203 IGNode *NeighIGNode = Node->getAdjIGNode(n); 00204 LiveRange *NeighLR = NeighIGNode->getParentLR(); 00205 00206 // Don't use a color if it is in use by the neighbor, 00207 // or is suggested for use by the neighbor, 00208 // markColorsUsed() should be given the color and the reg type for 00209 // LR, not for NeighLR, because it should mark registers used based on 00210 // the type we are looking for, not on the regType for the neighbour. 00211 if (NeighLR->hasColor()) 00212 this->markColorsUsed(NeighLR->getColor(), 00213 MRI->getRegTypeForLR(NeighLR), 00214 MRI->getRegTypeForLR(LR)); // use LR, not NeighLR 00215 else if (NeighLR->hasSuggestedColor() && 00216 NeighLR->isSuggestedColorUsable()) 00217 this->markColorsUsed(NeighLR->getSuggestedColor(), 00218 MRI->getRegTypeForLR(NeighLR), 00219 MRI->getRegTypeForLR(LR)); // use LR, not NeighLR 00220 } 00221 00222 // call the target specific code for coloring 00223 // 00224 MRC->colorIGNode(Node, IsColorUsedArr); 00225 } else { 00226 if (DEBUG_RA >= RA_DEBUG_Coloring) { 00227 std::cerr << " Node " << Node->getIndex(); 00228 std::cerr << " already colored with color " << Node->getColor() << "\n"; 00229 } 00230 } 00231 00232 00233 if (!Node->hasColor() ) { 00234 if (DEBUG_RA >= RA_DEBUG_Coloring) { 00235 std::cerr << " Node " << Node->getIndex(); 00236 std::cerr << " - could not find a color (needs spilling)\n"; 00237 } 00238 } 00239 } 00240 00241 void RegClass::printIGNodeList() const { 00242 std::cerr << "IG Nodes for Register Class " << RegClassID << ":" << "\n"; 00243 IG.printIGNodeList(); 00244 } 00245 00246 void RegClass::printIG() { 00247 std::cerr << "IG for Register Class " << RegClassID << ":" << "\n"; 00248 IG.printIG(); 00249 } 00250 00251 } // End llvm namespace