1 //===-- RegClass.cpp -----------------------------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // class RegClass for coloring-based register allocation for LLVM.
12 //===----------------------------------------------------------------------===//
15 #include "RegAllocCommon.h"
17 #include "llvm/Target/TargetRegInfo.h"
21 //----------------------------------------------------------------------------
22 // This constructor inits IG. The actual matrix is created by a call to
23 // createInterferenceGraph() above.
24 //----------------------------------------------------------------------------
25 RegClass::RegClass(const Function *M,
26 const TargetRegInfo *_MRI_,
27 const TargetRegClassInfo *_MRC_)
28 : Meth(M), MRI(_MRI_), MRC(_MRC_),
29 RegClassID( _MRC_->getRegClassID() ),
30 IG(this), IGNodeStack() {
31 if (DEBUG_RA >= RA_DEBUG_Interference)
32 std::cerr << "Created Reg Class: " << RegClassID << "\n";
34 IsColorUsedArr.resize(MRC->getNumOfAllRegs());
39 //----------------------------------------------------------------------------
40 // Main entry point for coloring a register class.
41 //----------------------------------------------------------------------------
42 void RegClass::colorAllRegs()
44 if (DEBUG_RA >= RA_DEBUG_Coloring)
45 std::cerr << "Coloring IG of reg class " << RegClassID << " ...\n";
47 pushAllIGNodes(); // push all IG Nodes
49 unsigned int StackSize = IGNodeStack.size();
51 // for all LRs on stack
52 for (unsigned int IGN=0; IGN < StackSize; IGN++) {
53 CurIGNode = IGNodeStack.top(); // pop the IGNode on top of stack
55 colorIGNode (CurIGNode); // color it
61 //----------------------------------------------------------------------------
62 // The method for pushing all IGNodes on to the stack.
63 //----------------------------------------------------------------------------
64 void RegClass::pushAllIGNodes()
69 IG.setCurDegreeOfIGNodes(); // calculate degree of IGNodes
71 // push non-constrained IGNodes
72 bool PushedAll = pushUnconstrainedIGNodes();
74 if (DEBUG_RA >= RA_DEBUG_Coloring) {
75 std::cerr << " Puhsed all-unconstrained IGNodes. ";
76 if( PushedAll ) std::cerr << " No constrained nodes left.";
80 if (PushedAll) // if NO constrained nodes left
84 // now, we have constrained nodes. So, push one of them (the one with min
85 // spill cost) and try to push the others as unConstrained nodes.
89 //get node with min spill cost
90 IGNode *IGNodeSpill = getIGNodeWithMinSpillCost();
91 // push that node on to stack
92 IGNodeStack.push(IGNodeSpill);
93 // set its OnStack flag and decrement degree of neighs
94 IGNodeSpill->pushOnStack();
95 // now push NON-constrained ones, if any
96 NeedMoreSpills = !pushUnconstrainedIGNodes();
97 if (DEBUG_RA >= RA_DEBUG_Coloring)
98 std::cerr << "\nConstrained IG Node found !@!" << IGNodeSpill->getIndex();
99 } while(NeedMoreSpills); // repeat until we have pushed all
106 //--------------------------------------------------------------------------
107 // This method goes thru all IG nodes in the IGNodeList of an IG of a
108 // register class and push any unconstrained IG node left (that is not
110 //--------------------------------------------------------------------------
112 bool RegClass::pushUnconstrainedIGNodes()
114 // # of LRs for this reg class
115 unsigned int IGNodeListSize = IG.getIGNodeList().size();
116 bool pushedall = true;
118 // a pass over IGNodeList
119 for (unsigned i =0; i < IGNodeListSize; i++) {
121 // get IGNode i from IGNodeList
122 IGNode *IGNode = IG.getIGNodeList()[i];
124 if (!IGNode ) // can be null due to merging
127 // if already pushed on stack, continue. This can happen since this
128 // method can be called repeatedly until all constrained nodes are
130 if (IGNode->isOnStack() )
132 // if the degree of IGNode is lower
133 if ((unsigned) IGNode->getCurDegree() < MRC->getNumOfAvailRegs()) {
134 IGNodeStack.push( IGNode ); // push IGNode on to the stack
135 IGNode->pushOnStack(); // set OnStack and dec deg of neighs
137 if (DEBUG_RA >= RA_DEBUG_Coloring) {
138 std::cerr << " pushed un-constrained IGNode " << IGNode->getIndex()
142 else pushedall = false; // we didn't push all live ranges
146 // returns true if we pushed all live ranges - else false
152 //----------------------------------------------------------------------------
153 // Get the IGNode with the minimum spill cost
154 //----------------------------------------------------------------------------
155 IGNode * RegClass::getIGNodeWithMinSpillCost() {
156 unsigned int IGNodeListSize = IG.getIGNodeList().size();
157 double MinSpillCost = 0;
158 IGNode *MinCostIGNode = NULL;
159 bool isFirstNode = true;
161 // pass over IGNodeList to find the IGNode with minimum spill cost
162 // among all IGNodes that are not yet pushed on to the stack
163 for (unsigned int i =0; i < IGNodeListSize; i++) {
164 IGNode *IGNode = IG.getIGNodeList()[i];
166 if (!IGNode) // can be null due to merging
169 if (!IGNode->isOnStack()) {
170 double SpillCost = (double) IGNode->getParentLR()->getSpillCost() /
171 (double) (IGNode->getCurDegree() + 1);
173 if (isFirstNode) { // for the first IG node
174 MinSpillCost = SpillCost;
175 MinCostIGNode = IGNode;
177 } else if (MinSpillCost > SpillCost) {
178 MinSpillCost = SpillCost;
179 MinCostIGNode = IGNode;
184 assert (MinCostIGNode && "No IGNode to spill");
185 return MinCostIGNode;
189 //----------------------------------------------------------------------------
190 // Color the IGNode using the machine specific code.
191 //----------------------------------------------------------------------------
192 void RegClass::colorIGNode(IGNode *const Node) {
193 if (! Node->hasColor()) { // not colored as an arg etc.
195 // init all elements of to IsColorUsedAr false;
198 // initialize all colors used by neighbors of this node to true
199 LiveRange *LR = Node->getParentLR();
200 unsigned NumNeighbors = Node->getNumOfNeighbors();
201 for (unsigned n=0; n < NumNeighbors; n++) {
202 IGNode *NeighIGNode = Node->getAdjIGNode(n);
203 LiveRange *NeighLR = NeighIGNode->getParentLR();
205 // Don't use a color if it is in use by the neighbor,
206 // or is suggested for use by the neighbor,
207 // markColorsUsed() should be given the color and the reg type for
208 // LR, not for NeighLR, because it should mark registers used based on
209 // the type we are looking for, not on the regType for the neighbour.
210 if (NeighLR->hasColor())
211 this->markColorsUsed(NeighLR->getColor(),
212 MRI->getRegTypeForLR(NeighLR),
213 MRI->getRegTypeForLR(LR)); // use LR, not NeighLR
214 else if (NeighLR->hasSuggestedColor() &&
215 NeighLR->isSuggestedColorUsable())
216 this->markColorsUsed(NeighLR->getSuggestedColor(),
217 MRI->getRegTypeForLR(NeighLR),
218 MRI->getRegTypeForLR(LR)); // use LR, not NeighLR
221 // call the target specific code for coloring
223 MRC->colorIGNode(Node, IsColorUsedArr);
225 if (DEBUG_RA >= RA_DEBUG_Coloring) {
226 std::cerr << " Node " << Node->getIndex();
227 std::cerr << " already colored with color " << Node->getColor() << "\n";
232 if (!Node->hasColor() ) {
233 if (DEBUG_RA >= RA_DEBUG_Coloring) {
234 std::cerr << " Node " << Node->getIndex();
235 std::cerr << " - could not find a color (needs spilling)\n";
240 void RegClass::printIGNodeList() const {
241 std::cerr << "IG Nodes for Register Class " << RegClassID << ":" << "\n";
242 IG.printIGNodeList();
245 void RegClass::printIG() {
246 std::cerr << "IG for Register Class " << RegClassID << ":" << "\n";
250 } // End llvm namespace