1 //===-- RegClass.cpp -----------------------------------------------------===//
3 // class RegClass for coloring-based register allocation for LLVM.
5 //===----------------------------------------------------------------------===//
7 #include "llvm/CodeGen/RegClass.h"
8 #include "llvm/CodeGen/RegAllocCommon.h"
9 #include "llvm/CodeGen/IGNode.h"
12 //----------------------------------------------------------------------------
13 // This constructor inits IG. The actual matrix is created by a call to
14 // createInterferenceGraph() above.
15 //----------------------------------------------------------------------------
16 RegClass::RegClass(const Function *M,
17 const MachineRegClassInfo *Mrc,
18 const ReservedColorListType *RCL)
19 : Meth(M), MRC(Mrc), RegClassID( Mrc->getRegClassID() ),
20 IG(this), IGNodeStack(), ReservedColorList(RCL) {
21 if( DEBUG_RA >= RA_DEBUG_Interference)
22 cerr << "Created Reg Class: " << RegClassID << "\n";
24 IsColorUsedArr.resize(Mrc->getNumOfAllRegs());
29 //----------------------------------------------------------------------------
30 // Main entry point for coloring a register class.
31 //----------------------------------------------------------------------------
32 void RegClass::colorAllRegs()
34 if(DEBUG_RA >= RA_DEBUG_Coloring)
35 cerr << "Coloring IG of reg class " << RegClassID << " ...\n";
38 pushAllIGNodes(); // push all IG Nodes
40 unsigned int StackSize = IGNodeStack.size();
43 // for all LRs on stack
44 for( unsigned int IGN=0; IGN < StackSize; IGN++) {
46 CurIGNode = IGNodeStack.top(); // pop the IGNode on top of stack
48 colorIGNode (CurIGNode); // color it
55 //----------------------------------------------------------------------------
56 // The method for pushing all IGNodes on to the stack.
57 //----------------------------------------------------------------------------
58 void RegClass::pushAllIGNodes()
63 IG.setCurDegreeOfIGNodes(); // calculate degree of IGNodes
65 // push non-constrained IGNodes
66 bool PushedAll = pushUnconstrainedIGNodes();
68 if( DEBUG_RA >= RA_DEBUG_Coloring) {
69 cerr << " Puhsed all-unconstrained IGNodes. ";
70 if( PushedAll ) cerr << " No constrained nodes left.";
74 if( PushedAll ) // if NO constrained nodes left
78 // now, we have constrained nodes. So, push one of them (the one with min
79 // spill cost) and try to push the others as unConstrained nodes.
83 //get node with min spill cost
85 IGNode *IGNodeSpill = getIGNodeWithMinSpillCost();
87 // push that node on to stack
89 IGNodeStack.push(IGNodeSpill);
91 // set its OnStack flag and decrement degree of neighs
93 IGNodeSpill->pushOnStack();
95 // now push NON-constrined ones, if any
97 NeedMoreSpills = !pushUnconstrainedIGNodes();
99 if (DEBUG_RA >= RA_DEBUG_Coloring)
100 cerr << "\nConstrained IG Node found !@!" << IGNodeSpill->getIndex();
102 } while(NeedMoreSpills); // repeat until we have pushed all
109 //--------------------------------------------------------------------------
110 // This method goes thru all IG nodes in the IGNodeList of an IG of a
111 // register class and push any unconstrained IG node left (that is not
113 //--------------------------------------------------------------------------
115 bool RegClass::pushUnconstrainedIGNodes()
117 // # of LRs for this reg class
118 unsigned int IGNodeListSize = IG.getIGNodeList().size();
119 bool pushedall = true;
121 // a pass over IGNodeList
122 for( unsigned i =0; i < IGNodeListSize; i++) {
124 // get IGNode i from IGNodeList
125 IGNode *IGNode = IG.getIGNodeList()[i];
127 if( !IGNode ) // can be null due to merging
130 // if already pushed on stack, continue. This can happen since this
131 // method can be called repeatedly until all constrained nodes are
133 if( IGNode->isOnStack() )
135 // if the degree of IGNode is lower
136 if( (unsigned) IGNode->getCurDegree() < MRC->getNumOfAvailRegs() ) {
137 IGNodeStack.push( IGNode ); // push IGNode on to the stack
138 IGNode->pushOnStack(); // set OnStack and dec deg of neighs
140 if (DEBUG_RA >= RA_DEBUG_Coloring) {
141 cerr << " pushed un-constrained IGNode " << IGNode->getIndex() ;
142 cerr << " on to stack\n";
145 else pushedall = false; // we didn't push all live ranges
149 // returns true if we pushed all live ranges - else false
155 //----------------------------------------------------------------------------
156 // Get the IGNode withe the minimum spill cost
157 //----------------------------------------------------------------------------
158 IGNode * RegClass::getIGNodeWithMinSpillCost()
161 unsigned int IGNodeListSize = IG.getIGNodeList().size();
162 double MinSpillCost = 0;
163 IGNode *MinCostIGNode = NULL;
164 bool isFirstNode = true;
166 // pass over IGNodeList to find the IGNode with minimum spill cost
167 // among all IGNodes that are not yet pushed on to the stack
169 for( unsigned int i =0; i < IGNodeListSize; i++) {
170 IGNode *IGNode = IG.getIGNodeList()[i];
172 if( ! IGNode ) // can be null due to merging
175 if( ! IGNode->isOnStack() ) {
177 double SpillCost = (double) IGNode->getParentLR()->getSpillCost() /
178 (double) (IGNode->getCurDegree() + 1);
180 if( isFirstNode ) { // for the first IG node
181 MinSpillCost = SpillCost;
182 MinCostIGNode = IGNode;
186 else if( MinSpillCost > SpillCost) {
187 MinSpillCost = SpillCost;
188 MinCostIGNode = IGNode;
194 assert( MinCostIGNode && "No IGNode to spill");
195 return MinCostIGNode;
200 //----------------------------------------------------------------------------
201 // Color the IGNode using the machine specific code.
202 //----------------------------------------------------------------------------
203 void RegClass::colorIGNode(IGNode *const Node)
206 if( ! Node->hasColor() ) { // not colored as an arg etc.
209 // init all elements of to IsColorUsedAr false;
211 for (unsigned i=0; i < MRC->getNumOfAllRegs(); i++)
212 IsColorUsedArr[i] = false;
214 // init all reserved_regs to true - we can't use them
216 for( unsigned i=0; i < ReservedColorList->size() ; i++) {
217 IsColorUsedArr[(*ReservedColorList)[i]] = true;
220 // initialize all colors used by neighbors of this node to true
221 LiveRange *LR = Node->getParentLR();
222 unsigned NumNeighbors = Node->getNumOfNeighbors();
223 for (unsigned n=0; n < NumNeighbors; n++) {
224 IGNode *NeighIGNode = Node->getAdjIGNode(n);
225 LiveRange *NeighLR = NeighIGNode->getParentLR();
227 if (NeighLR->hasColor()) { // if has a color
228 IsColorUsedArr[NeighLR->getColor()] = true; // mark color as used
229 } else if (NeighLR->hasSuggestedColor() &&
230 NeighLR->isSuggestedColorUsable()) {
231 // this color is suggested for the neighbour, so don't use it
232 IsColorUsedArr[NeighLR->getSuggestedColor()] = true;
236 // call the target specific code for coloring
238 MRC->colorIGNode(Node, IsColorUsedArr);
241 if( DEBUG_RA >= RA_DEBUG_Coloring) {
242 cerr << " Node " << Node->getIndex();
243 cerr << " already colored with color " << Node->getColor() << "\n";
248 if( !Node->hasColor() ) {
249 if( DEBUG_RA >= RA_DEBUG_Coloring) {
250 cerr << " Node " << Node->getIndex();
251 cerr << " - could not find a color (needs spilling)\n";
257 void RegClass::printIGNodeList() const {
258 std::cerr << "IG Nodes for Register Class " << RegClassID << ":" << "\n";
259 IG.printIGNodeList();
262 void RegClass::printIG() {
263 std::cerr << "IG for Register Class " << RegClassID << ":" << "\n";