1 #include "llvm/CodeGen/RegClass.h"
5 RegClass::RegClass(const Method *const M,
6 const MachineRegClassInfo *const Mrc,
7 const ReservedColorListType *const RCL)
8 : Meth(M), MRC(Mrc), RegClassID( Mrc->getRegClassID() ),
9 IG(this), IGNodeStack(), ReservedColorList(RCL)
12 cout << "Created Reg Class: " << RegClassID << endl;
14 // This constructor inits IG. The actual matrix is created by a call to
15 // createInterferenceGraph() above.
17 IsColorUsedArr = new bool[ Mrc->getNumOfAllRegs() ];
22 void RegClass::colorAllRegs()
24 if(DEBUG_RA) cout << "Coloring IG of reg class " << RegClassID << " ...\n";
26 //preColorIGNodes(); // pre-color IGNodes
27 pushAllIGNodes(); // push all IG Nodes
29 unsigned int StackSize = IGNodeStack.size();
32 // for all LRs on stack
33 for( unsigned int IGN=0; IGN < StackSize; IGN++) {
35 CurIGNode = IGNodeStack.top(); // pop the IGNode on top of stack
37 colorIGNode (CurIGNode); // color it
41 // InsertSpillCode; ********* TODO ********
47 void RegClass::pushAllIGNodes()
52 IG.setCurDegreeOfIGNodes(); // calculate degree of IGNodes
54 // push non-constrained IGNodes
55 bool PushedAll = pushUnconstrainedIGNodes();
58 cout << " Puhsed all-unconstrained IGNodes. ";
59 if( PushedAll ) cout << " No constrained nodes left.";
63 if( PushedAll ) // if NO constrained nodes left
67 // now, we have constrained nodes. So, push one of them (the one with min
68 // spill cost) and try to push the others as unConstrained nodes.
73 //get node with min spill cost
74 IGNode *IGNodeSpill = getIGNodeWithMinSpillCost();
76 // push that node on to stack
77 IGNodeStack.push( IGNodeSpill );
79 // set its OnStack flag and decrement degree of neighs
80 IGNodeSpill->pushOnStack();
82 // now push NON-constrined ones, if any
83 NeedMoreSpills = ! pushUnconstrainedIGNodes();
85 cerr << "\nConstrained IG Node found !@!" << IGNodeSpill->getIndex();
87 } while( NeedMoreSpills ); // repeat until we have pushed all
94 //--------------------------------------------------------------------------
95 // This method goes thru all IG nodes in the IGNodeList of an IG of a
96 // register class and push any unconstrained IG node left (that is not
98 //--------------------------------------------------------------------------
100 bool RegClass::pushUnconstrainedIGNodes()
102 // # of LRs for this reg class
103 unsigned int IGNodeListSize = IG.getIGNodeList().size();
104 bool pushedall = true;
106 // a pass over IGNodeList
107 for( unsigned i =0; i < IGNodeListSize; i++) {
109 // get IGNode i from IGNodeList
110 IGNode *IGNode = IG.getIGNodeList()[i];
112 if( !IGNode ) // can be null due to merging
115 // if already pushed on stack, continue. This can happen since this
116 // method can be called repeatedly until all constrained nodes are
118 if( IGNode->isOnStack() )
120 // if the degree of IGNode is lower
121 if( (unsigned) IGNode->getCurDegree() < MRC->getNumOfAvailRegs() ) {
122 IGNodeStack.push( IGNode ); // push IGNode on to the stack
123 IGNode->pushOnStack(); // set OnStack and dec deg of neighs
126 cout << " pushed un-constrained IGNode " << IGNode->getIndex() ;
127 cout << " on to stack" << endl;
130 else pushedall = false; // we didn't push all live ranges
134 // returns true if we pushed all live ranges - else false
141 IGNode * RegClass::getIGNodeWithMinSpillCost()
144 unsigned int IGNodeListSize = IG.getIGNodeList().size();
146 // pass over IGNodeList
147 for( unsigned int i =0; i < IGNodeListSize; i++) {
148 IGNode = IG.getIGNodeList()[i];
150 if( ! IGNode ) // can be null due to merging
153 // return the first IGNode ########## Change this #######
154 if( ! IGNode->isOnStack() ) return IGNode;
164 void RegClass::colorIGNode(IGNode *const Node)
167 if( ! Node->hasColor() ) { // not colored as an arg etc.
170 // init all elements to false;
171 for( unsigned i=0; i < MRC->getNumOfAllRegs(); i++) {
172 IsColorUsedArr[ i ] = false;
175 // init all reserved_regs to true - we can't use them
176 for( unsigned i=0; i < ReservedColorList->size() ; i++) {
177 IsColorUsedArr[ (*ReservedColorList)[i] ] = true;
180 MRC->colorIGNode(Node, IsColorUsedArr);
184 cout << " Node " << Node->getIndex();
185 cout << " already colored with color " << Node->getColor() << endl;
190 if( !Node->hasColor() ) {
192 cout << " Node " << Node->getIndex();
193 cout << " - could not find a color (needs spilling)" << endl;