1 //===-- RegClass.cpp -----------------------------------------------------===//
3 // class RegClass for coloring-based register allocation for LLVM.
5 //===----------------------------------------------------------------------===//
8 #include "RegAllocCommon.h"
10 #include "llvm/Target/TargetRegInfo.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 TargetRegInfo *_MRI_,
18 const TargetRegClassInfo *_MRC_)
19 : Meth(M), MRI(_MRI_), MRC(_MRC_),
20 RegClassID( _MRC_->getRegClassID() ),
21 IG(this), IGNodeStack() {
22 if( DEBUG_RA >= RA_DEBUG_Interference)
23 std::cerr << "Created Reg Class: " << RegClassID << "\n";
25 IsColorUsedArr.resize(MRC->getNumOfAllRegs());
30 //----------------------------------------------------------------------------
31 // Main entry point for coloring a register class.
32 //----------------------------------------------------------------------------
33 void RegClass::colorAllRegs()
35 if(DEBUG_RA >= RA_DEBUG_Coloring)
36 std::cerr << "Coloring IG of reg class " << RegClassID << " ...\n";
39 pushAllIGNodes(); // push all IG Nodes
41 unsigned int StackSize = IGNodeStack.size();
44 // for all LRs on stack
45 for( unsigned int IGN=0; IGN < StackSize; IGN++) {
47 CurIGNode = IGNodeStack.top(); // pop the IGNode on top of stack
49 colorIGNode (CurIGNode); // color it
56 //----------------------------------------------------------------------------
57 // The method for pushing all IGNodes on to the stack.
58 //----------------------------------------------------------------------------
59 void RegClass::pushAllIGNodes()
64 IG.setCurDegreeOfIGNodes(); // calculate degree of IGNodes
66 // push non-constrained IGNodes
67 bool PushedAll = pushUnconstrainedIGNodes();
69 if( DEBUG_RA >= RA_DEBUG_Coloring) {
70 std::cerr << " Puhsed all-unconstrained IGNodes. ";
71 if( PushedAll ) std::cerr << " No constrained nodes left.";
75 if( PushedAll ) // if NO constrained nodes left
79 // now, we have constrained nodes. So, push one of them (the one with min
80 // spill cost) and try to push the others as unConstrained nodes.
84 //get node with min spill cost
86 IGNode *IGNodeSpill = getIGNodeWithMinSpillCost();
88 // push that node on to stack
90 IGNodeStack.push(IGNodeSpill);
92 // set its OnStack flag and decrement degree of neighs
94 IGNodeSpill->pushOnStack();
96 // now push NON-constrained ones, if any
98 NeedMoreSpills = !pushUnconstrainedIGNodes();
100 if (DEBUG_RA >= RA_DEBUG_Coloring)
101 std::cerr << "\nConstrained IG Node found !@!" << IGNodeSpill->getIndex();
103 } while(NeedMoreSpills); // repeat until we have pushed all
110 //--------------------------------------------------------------------------
111 // This method goes thru all IG nodes in the IGNodeList of an IG of a
112 // register class and push any unconstrained IG node left (that is not
114 //--------------------------------------------------------------------------
116 bool RegClass::pushUnconstrainedIGNodes()
118 // # of LRs for this reg class
119 unsigned int IGNodeListSize = IG.getIGNodeList().size();
120 bool pushedall = true;
122 // a pass over IGNodeList
123 for( unsigned i =0; i < IGNodeListSize; i++) {
125 // get IGNode i from IGNodeList
126 IGNode *IGNode = IG.getIGNodeList()[i];
128 if( !IGNode ) // can be null due to merging
131 // if already pushed on stack, continue. This can happen since this
132 // method can be called repeatedly until all constrained nodes are
134 if( IGNode->isOnStack() )
136 // if the degree of IGNode is lower
137 if( (unsigned) IGNode->getCurDegree() < MRC->getNumOfAvailRegs()) {
138 IGNodeStack.push( IGNode ); // push IGNode on to the stack
139 IGNode->pushOnStack(); // set OnStack and dec deg of neighs
141 if (DEBUG_RA >= RA_DEBUG_Coloring) {
142 std::cerr << " pushed un-constrained IGNode " << IGNode->getIndex()
146 else pushedall = false; // we didn't push all live ranges
150 // returns true if we pushed all live ranges - else false
156 //----------------------------------------------------------------------------
157 // Get the IGNode with the minimum spill cost
158 //----------------------------------------------------------------------------
159 IGNode * RegClass::getIGNodeWithMinSpillCost()
162 unsigned int IGNodeListSize = IG.getIGNodeList().size();
163 double MinSpillCost = 0;
164 IGNode *MinCostIGNode = NULL;
165 bool isFirstNode = true;
167 // pass over IGNodeList to find the IGNode with minimum spill cost
168 // among all IGNodes that are not yet pushed on to the stack
170 for( unsigned int i =0; i < IGNodeListSize; i++) {
171 IGNode *IGNode = IG.getIGNodeList()[i];
173 if( ! IGNode ) // can be null due to merging
176 if( ! IGNode->isOnStack() ) {
178 double SpillCost = (double) IGNode->getParentLR()->getSpillCost() /
179 (double) (IGNode->getCurDegree() + 1);
181 if( isFirstNode ) { // for the first IG node
182 MinSpillCost = SpillCost;
183 MinCostIGNode = IGNode;
187 else if( MinSpillCost > SpillCost) {
188 MinSpillCost = SpillCost;
189 MinCostIGNode = IGNode;
195 assert( MinCostIGNode && "No IGNode to spill");
196 return MinCostIGNode;
201 //----------------------------------------------------------------------------
202 // Color the IGNode using the machine specific code.
203 //----------------------------------------------------------------------------
204 void RegClass::colorIGNode(IGNode *const Node)
207 if( ! Node->hasColor() ) { // not colored as an arg etc.
209 // init all elements of to IsColorUsedAr false;
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 // Don't use a color if it is in use by the neighbor,
220 // or is suggested for use by the neighbor,
221 // markColorsUsed() should be given the color and the reg type for
222 // LR, not for NeighLR, because it should mark registers used based on
223 // the type we are looking for, not on the regType for the neighbour.
224 if (NeighLR->hasColor())
225 this->markColorsUsed(NeighLR->getColor(),
226 MRI->getRegTypeForLR(NeighLR),
227 MRI->getRegTypeForLR(LR)); // use LR, not NeighLR
228 else if (NeighLR->hasSuggestedColor() &&
229 NeighLR->isSuggestedColorUsable())
230 this->markColorsUsed(NeighLR->getSuggestedColor(),
231 MRI->getRegTypeForLR(NeighLR),
232 MRI->getRegTypeForLR(LR)); // use LR, not NeighLR
235 // call the target specific code for coloring
237 MRC->colorIGNode(Node, IsColorUsedArr);
240 if( DEBUG_RA >= RA_DEBUG_Coloring) {
241 std::cerr << " Node " << Node->getIndex();
242 std::cerr << " already colored with color " << Node->getColor() << "\n";
247 if( !Node->hasColor() ) {
248 if( DEBUG_RA >= RA_DEBUG_Coloring) {
249 std::cerr << " Node " << Node->getIndex();
250 std::cerr << " - could not find a color (needs spilling)\n";
256 void RegClass::printIGNodeList() const {
257 std::cerr << "IG Nodes for Register Class " << RegClassID << ":" << "\n";
258 IG.printIGNodeList();
261 void RegClass::printIG() {
262 std::cerr << "IG for Register Class " << RegClassID << ":" << "\n";