1 #include "llvm/CodeGen/RegClass.h"
4 //----------------------------------------------------------------------------
5 // This constructor inits IG. The actual matrix is created by a call to
6 // createInterferenceGraph() above.
7 //----------------------------------------------------------------------------
8 RegClass::RegClass(const Method *const M,
9 const MachineRegClassInfo *const Mrc,
10 const ReservedColorListType *const RCL)
11 : Meth(M), MRC(Mrc), RegClassID( Mrc->getRegClassID() ),
12 IG(this), IGNodeStack(), ReservedColorList(RCL) {
14 cout << "Created Reg Class: " << RegClassID << endl;
16 IsColorUsedArr = new bool[ Mrc->getNumOfAllRegs() ];
21 //----------------------------------------------------------------------------
22 // Main entry point for coloring a register class.
23 //----------------------------------------------------------------------------
24 void RegClass::colorAllRegs()
26 if(DEBUG_RA) cout << "Coloring IG of reg class " << RegClassID << " ...\n";
29 pushAllIGNodes(); // push all IG Nodes
31 unsigned int StackSize = IGNodeStack.size();
34 // for all LRs on stack
35 for( unsigned int IGN=0; IGN < StackSize; IGN++) {
37 CurIGNode = IGNodeStack.top(); // pop the IGNode on top of stack
39 colorIGNode (CurIGNode); // color it
46 //----------------------------------------------------------------------------
47 // The method for pushing all IGNodes on to the stack.
48 //----------------------------------------------------------------------------
49 void RegClass::pushAllIGNodes()
54 IG.setCurDegreeOfIGNodes(); // calculate degree of IGNodes
56 // push non-constrained IGNodes
57 bool PushedAll = pushUnconstrainedIGNodes();
60 cout << " Puhsed all-unconstrained IGNodes. ";
61 if( PushedAll ) cout << " No constrained nodes left.";
65 if( PushedAll ) // if NO constrained nodes left
69 // now, we have constrained nodes. So, push one of them (the one with min
70 // 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();
91 cerr << "\nConstrained IG Node found !@!" << IGNodeSpill->getIndex();
93 } while( NeedMoreSpills ); // repeat until we have pushed all
100 //--------------------------------------------------------------------------
101 // This method goes thru all IG nodes in the IGNodeList of an IG of a
102 // register class and push any unconstrained IG node left (that is not
104 //--------------------------------------------------------------------------
106 bool RegClass::pushUnconstrainedIGNodes()
108 // # of LRs for this reg class
109 unsigned int IGNodeListSize = IG.getIGNodeList().size();
110 bool pushedall = true;
112 // a pass over IGNodeList
113 for( unsigned i =0; i < IGNodeListSize; i++) {
115 // get IGNode i from IGNodeList
116 IGNode *IGNode = IG.getIGNodeList()[i];
118 if( !IGNode ) // can be null due to merging
121 // if already pushed on stack, continue. This can happen since this
122 // method can be called repeatedly until all constrained nodes are
124 if( IGNode->isOnStack() )
126 // if the degree of IGNode is lower
127 if( (unsigned) IGNode->getCurDegree() < MRC->getNumOfAvailRegs() ) {
128 IGNodeStack.push( IGNode ); // push IGNode on to the stack
129 IGNode->pushOnStack(); // set OnStack and dec deg of neighs
132 cout << " pushed un-constrained IGNode " << IGNode->getIndex() ;
133 cout << " on to stack" << endl;
136 else pushedall = false; // we didn't push all live ranges
140 // returns true if we pushed all live ranges - else false
146 //----------------------------------------------------------------------------
147 // Get the IGNode withe the minimum spill cost
148 //----------------------------------------------------------------------------
149 IGNode * RegClass::getIGNodeWithMinSpillCost()
152 unsigned int IGNodeListSize = IG.getIGNodeList().size();
153 long MinSpillCost = -1;
154 IGNode *MinCostIGNode = NULL;
157 // pass over IGNodeList to find the IGNode with minimum spill cost
158 // among all IGNodes that are not yet pushed on to the stack
160 for( unsigned int i =0; i < IGNodeListSize; i++) {
161 IGNode *IGNode = IG.getIGNodeList()[i];
163 if( ! IGNode ) // can be null due to merging
166 if( ! IGNode->isOnStack() ) {
168 long SpillCost = (long) IGNode->getParentLR()->getSpillCost();
170 if( MinSpillCost == -1) { // for the first IG node
171 MinSpillCost = SpillCost;
172 MinCostIGNode = IGNode;
175 else if( MinSpillCost > SpillCost) {
176 MinSpillCost = SpillCost;
177 MinCostIGNode = IGNode;
183 assert( MinCostIGNode && "No IGNode to spill");
184 return MinCostIGNode;
189 //----------------------------------------------------------------------------
190 // Color the IGNode using the machine specific code.
191 //----------------------------------------------------------------------------
192 void RegClass::colorIGNode(IGNode *const Node)
195 if( ! Node->hasColor() ) { // not colored as an arg etc.
198 // init all elements of to IsColorUsedAr false;
200 for( unsigned i=0; i < MRC->getNumOfAllRegs(); i++) {
201 IsColorUsedArr[ i ] = false;
204 // init all reserved_regs to true - we can't use them
206 for( unsigned i=0; i < ReservedColorList->size() ; i++) {
207 IsColorUsedArr[ (*ReservedColorList)[i] ] = true;
210 // call the target specific code for coloring
212 MRC->colorIGNode(Node, IsColorUsedArr);
216 cout << " Node " << Node->getIndex();
217 cout << " already colored with color " << Node->getColor() << endl;
222 if( !Node->hasColor() ) {
224 cout << " Node " << Node->getIndex();
225 cout << " - could not find a color (needs spilling)" << endl;