1 #include "llvm/CodeGen/RegClass.h"
2 #include "llvm/CodeGen/RegAllocCommon.h"
5 //----------------------------------------------------------------------------
6 // This constructor inits IG. The actual matrix is created by a call to
7 // createInterferenceGraph() above.
8 //----------------------------------------------------------------------------
9 RegClass::RegClass(const Function *M,
10 const MachineRegClassInfo *Mrc,
11 const ReservedColorListType *RCL)
12 : Meth(M), MRC(Mrc), RegClassID( Mrc->getRegClassID() ),
13 IG(this), IGNodeStack(), ReservedColorList(RCL) {
15 cerr << "Created Reg Class: " << RegClassID << "\n";
17 IsColorUsedArr.resize(Mrc->getNumOfAllRegs());
22 //----------------------------------------------------------------------------
23 // Main entry point for coloring a register class.
24 //----------------------------------------------------------------------------
25 void RegClass::colorAllRegs()
27 if(DEBUG_RA) cerr << "Coloring IG of reg class " << RegClassID << " ...\n";
30 pushAllIGNodes(); // push all IG Nodes
32 unsigned int StackSize = IGNodeStack.size();
35 // for all LRs on stack
36 for( unsigned int IGN=0; IGN < StackSize; IGN++) {
38 CurIGNode = IGNodeStack.top(); // pop the IGNode on top of stack
40 colorIGNode (CurIGNode); // color it
47 //----------------------------------------------------------------------------
48 // The method for pushing all IGNodes on to the stack.
49 //----------------------------------------------------------------------------
50 void RegClass::pushAllIGNodes()
55 IG.setCurDegreeOfIGNodes(); // calculate degree of IGNodes
57 // push non-constrained IGNodes
58 bool PushedAll = pushUnconstrainedIGNodes();
61 cerr << " Puhsed all-unconstrained IGNodes. ";
62 if( PushedAll ) cerr << " No constrained nodes left.";
66 if( PushedAll ) // if NO constrained nodes left
70 // now, we have constrained nodes. So, push one of them (the one with min
71 // spill cost) and try to push the others as unConstrained nodes.
75 //get node with min spill cost
77 IGNode *IGNodeSpill = getIGNodeWithMinSpillCost();
79 // push that node on to stack
81 IGNodeStack.push(IGNodeSpill);
83 // set its OnStack flag and decrement degree of neighs
85 IGNodeSpill->pushOnStack();
87 // now push NON-constrined ones, if any
89 NeedMoreSpills = !pushUnconstrainedIGNodes();
92 cerr << "\nConstrained IG Node found !@!" << IGNodeSpill->getIndex();
94 } while(NeedMoreSpills); // repeat until we have pushed all
101 //--------------------------------------------------------------------------
102 // This method goes thru all IG nodes in the IGNodeList of an IG of a
103 // register class and push any unconstrained IG node left (that is not
105 //--------------------------------------------------------------------------
107 bool RegClass::pushUnconstrainedIGNodes()
109 // # of LRs for this reg class
110 unsigned int IGNodeListSize = IG.getIGNodeList().size();
111 bool pushedall = true;
113 // a pass over IGNodeList
114 for( unsigned i =0; i < IGNodeListSize; i++) {
116 // get IGNode i from IGNodeList
117 IGNode *IGNode = IG.getIGNodeList()[i];
119 if( !IGNode ) // can be null due to merging
122 // if already pushed on stack, continue. This can happen since this
123 // method can be called repeatedly until all constrained nodes are
125 if( IGNode->isOnStack() )
127 // if the degree of IGNode is lower
128 if( (unsigned) IGNode->getCurDegree() < MRC->getNumOfAvailRegs() ) {
129 IGNodeStack.push( IGNode ); // push IGNode on to the stack
130 IGNode->pushOnStack(); // set OnStack and dec deg of neighs
133 cerr << " pushed un-constrained IGNode " << IGNode->getIndex() ;
134 cerr << " on to stack\n";
137 else pushedall = false; // we didn't push all live ranges
141 // returns true if we pushed all live ranges - else false
147 //----------------------------------------------------------------------------
148 // Get the IGNode withe the minimum spill cost
149 //----------------------------------------------------------------------------
150 IGNode * RegClass::getIGNodeWithMinSpillCost()
153 unsigned int IGNodeListSize = IG.getIGNodeList().size();
155 IGNode *MinCostIGNode = NULL;
156 bool isFirstNode = true;
158 // pass over IGNodeList to find the IGNode with minimum spill cost
159 // among all IGNodes that are not yet pushed on to the stack
161 for( unsigned int i =0; i < IGNodeListSize; i++) {
162 IGNode *IGNode = IG.getIGNodeList()[i];
164 if( ! IGNode ) // can be null due to merging
167 if( ! IGNode->isOnStack() ) {
169 double SpillCost = (double) IGNode->getParentLR()->getSpillCost() /
170 (double) (IGNode->getCurDegree() + 1);
172 if( isFirstNode ) { // for the first IG node
173 MinSpillCost = SpillCost;
174 MinCostIGNode = IGNode;
178 else if( MinSpillCost > SpillCost) {
179 MinSpillCost = SpillCost;
180 MinCostIGNode = IGNode;
186 assert( MinCostIGNode && "No IGNode to spill");
187 return MinCostIGNode;
192 //----------------------------------------------------------------------------
193 // Color the IGNode using the machine specific code.
194 //----------------------------------------------------------------------------
195 void RegClass::colorIGNode(IGNode *const Node)
198 if( ! Node->hasColor() ) { // not colored as an arg etc.
201 // init all elements of to IsColorUsedAr false;
203 for (unsigned i=0; i < MRC->getNumOfAllRegs(); i++)
204 IsColorUsedArr[i] = false;
206 // init all reserved_regs to true - we can't use them
208 for( unsigned i=0; i < ReservedColorList->size() ; i++) {
209 IsColorUsedArr[(*ReservedColorList)[i]] = true;
212 // initialize all colors used by neighbors of this node to true
213 LiveRange *LR = Node->getParentLR();
214 unsigned NumNeighbors = Node->getNumOfNeighbors();
215 for (unsigned n=0; n < NumNeighbors; n++) {
216 IGNode *NeighIGNode = Node->getAdjIGNode(n);
217 LiveRange *NeighLR = NeighIGNode->getParentLR();
219 if (NeighLR->hasColor()) { // if has a color
220 IsColorUsedArr[NeighLR->getColor()] = true; // mark color as used
221 } else if (NeighLR->hasSuggestedColor() &&
222 NeighLR->isSuggestedColorUsable()) {
223 // this color is suggested for the neighbour, so don't use it
224 IsColorUsedArr[NeighLR->getSuggestedColor()] = true;
228 // call the target specific code for coloring
230 MRC->colorIGNode(Node, IsColorUsedArr);
234 cerr << " Node " << Node->getIndex();
235 cerr << " already colored with color " << Node->getColor() << "\n";
240 if( !Node->hasColor() ) {
242 cerr << " Node " << Node->getIndex();
243 cerr << " - could not find a color (needs spilling)\n";