1 #include "SparcRegClassInfo.h"
2 #include "llvm/CodeGen/IGNode.h"
3 #include "llvm/Target/Sparc.h"
8 //-----------------------------------------------------------------------------
9 // Int Register Class - method for coloring a node in the interference graph.
12 // Record the colors/suggested colors of all neighbors.
14 // If there is a suggested color, try to allocate it
15 // If there is no call interf, try to allocate volatile, then non volatile
16 // If there is call interf, try to allocate non-volatile. If that fails
17 // try to allocate a volatile and insert save across calls
18 // If both above fail, spill.
20 //-----------------------------------------------------------------------------
21 void SparcIntRegClass::colorIGNode(IGNode * Node, bool IsColorUsedArr[]) const {
22 LiveRange *LR = Node->getParentLR();
23 unsigned NumNeighbors = Node->getNumOfNeighbors(); // total # of neighbors
25 for (unsigned n=0; n < NumNeighbors; n++) { // for each neigh
26 IGNode *NeighIGNode = Node->getAdjIGNode(n);
27 LiveRange *NeighLR = NeighIGNode->getParentLR();
29 if(NeighLR->hasColor()) // if has a color
30 IsColorUsedArr[NeighLR->getColor()] = true; // record that color
32 else if (NeighLR->hasSuggestedColor()) {
34 // if the neighbout can use the suggested color
35 if(NeighLR->isSuggestedColorUsable())
36 IsColorUsedArr[NeighLR->getSuggestedColor()] = true;
41 cerr << "\nColoring LR [CallInt=" << LR->isCallInterference() <<"]:";
45 if( LR->hasSuggestedColor() ) {
47 unsigned SugCol = LR->getSuggestedColor();
49 if( ! IsColorUsedArr[ SugCol ] ) {
51 if( LR->isSuggestedColorUsable() ) {
53 // if the suggested color is volatile, we should use it only if
54 // there are no call interferences. Otherwise, it will get spilled.
57 cerr << "\n -Coloring with sug color: " << SugCol;
59 LR->setColor( LR->getSuggestedColor() );
63 cerr << "\n Couldn't alloc Sug col - LR voloatile & calls interf";
66 else if ( DEBUG_RA ) { // can't allocate the suggested col
67 cerr << " \n Could NOT allocate the suggested color (already used) ";
68 printSet(*LR); cerr << "\n";
72 unsigned SearchStart; // start pos of color in pref-order
73 bool ColorFound= false; // have we found a color yet?
75 //if this Node is between calls
76 if( ! LR->isCallInterference() ) {
78 // start with volatiles (we can allocate volatiles safely)
79 SearchStart = SparcIntRegOrder::StartOfAllRegs;
82 // start with non volatiles (no non-volatiles)
83 SearchStart = SparcIntRegOrder::StartOfNonVolatileRegs;
86 unsigned c=0; // color
88 // find first unused color
89 for( c=SearchStart; c < SparcIntRegOrder::NumOfAvailRegs; c++) {
90 if( ! IsColorUsedArr[ c ] ) { ColorFound = true; break; }
94 LR->setColor(c); // first color found in preffered order
95 if (DEBUG_RA) cerr << "\n Colored after first search with col " << c ;
98 // if color is not found because of call interference
99 // try even finding a volatile color and insert save across calls
101 else if( LR->isCallInterference() )
103 // start from 0 - try to find even a volatile this time
104 SearchStart = SparcIntRegOrder::StartOfAllRegs;
106 // find first unused volatile color
107 for(c=SearchStart; c < SparcIntRegOrder::StartOfNonVolatileRegs; c++) {
108 if( ! IsColorUsedArr[ c ] ) { ColorFound = true; break; }
113 // get the live range corresponding to live var
114 // since LR span across calls, must save across calls
116 LR->markForSaveAcrossCalls();
117 if(DEBUG_RA) cerr << "\n Colored after SECOND search with col " << c ;
122 // If we couldn't find a color regardless of call interference - i.e., we
123 // don't have either a volatile or non-volatile color left
126 LR->markForSpill(); // no color found - must spill
134 //-----------------------------------------------------------------------------
135 // Float Register Class - method for coloring a node in the interference graph.
139 // If the LR is a double try to allocate f32 - f63
140 // If the above fails or LR is single precision
141 // If the LR does not interfere with a call
142 // start allocating from f0
143 // Else start allocating from f6
144 // If a color is still not found because LR interferes with a call
145 // Search in f0 - f6. If found mark for spill across calls.
146 // If a color is still not fond, mark for spilling
148 //----------------------------------------------------------------------------
149 void SparcFloatRegClass::colorIGNode(IGNode * Node,bool IsColorUsedArr[]) const{
150 LiveRange *LR = Node->getParentLR();
151 unsigned NumNeighbors = Node->getNumOfNeighbors(); // total # of neighbors
153 for(unsigned n=0; n < NumNeighbors; n++) { // for each neigh
154 IGNode *NeighIGNode = Node->getAdjIGNode(n);
155 LiveRange *NeighLR = NeighIGNode->getParentLR();
157 if( NeighLR->hasColor() ) { // if neigh has a color
158 IsColorUsedArr[ NeighLR->getColor() ] = true; // record that color
159 if (NeighLR->getType() == Type::DoubleTy)
160 IsColorUsedArr[ (NeighLR->getColor()) + 1 ] = true;
162 else if( NeighLR->hasSuggestedColor() ) { // if neigh has sugg color
164 if( NeighLR-> isSuggestedColorUsable() ) {
166 // if the neighbout can use the suggested color
168 IsColorUsedArr[ NeighLR->getSuggestedColor() ] = true;
169 if (NeighLR->getType() == Type::DoubleTy)
170 IsColorUsedArr[ (NeighLR->getSuggestedColor()) + 1 ] = true;
178 // **NOTE: We don't check for call interferences in allocating suggested
179 // color in this class since ALL registers are volatile. If this fact
180 // changes, we should change the following part
181 //- see SparcIntRegClass::colorIGNode()
183 if( LR->hasSuggestedColor() ) {
184 if( ! IsColorUsedArr[ LR->getSuggestedColor() ] ) {
185 LR->setColor( LR->getSuggestedColor() );
187 } else if (DEBUG_RA) { // can't allocate the suggested col
188 cerr << " Could NOT allocate the suggested color for LR ";
189 printSet(*LR); cerr << "\n";
194 int ColorFound = -1; // have we found a color yet?
195 bool isCallInterf = LR->isCallInterference();
197 // if value is a double - search the double only reigon (f32 - f63)
198 // i.e. we try to allocate f32 - f63 first for doubles since singles
199 // cannot go there. By doing that, we provide more space for singles
202 if (LR->getType() == Type::DoubleTy)
203 ColorFound = findFloatColor( LR, 32, 64, IsColorUsedArr );
206 if( ColorFound >= 0 ) { // if we could find a color
207 LR->setColor(ColorFound);
211 // if we didn't find a color becuase the LR was single precision or
212 // all f32-f63 range is filled, we try to allocate a register from
213 // the f0 - f31 region
215 unsigned SearchStart; // start pos of color in pref-order
217 //if this Node is between calls (i.e., no call interferences )
218 if( ! isCallInterf ) {
219 // start with volatiles (we can allocate volatiles safely)
220 SearchStart = SparcFloatRegOrder::StartOfAllRegs;
223 // start with non volatiles (no non-volatiles)
224 SearchStart = SparcFloatRegOrder::StartOfNonVolatileRegs;
227 ColorFound = findFloatColor( LR, SearchStart, 32, IsColorUsedArr );
232 if( ColorFound >= 0 ) { // if we could find a color
233 LR->setColor(ColorFound);
236 else if( isCallInterf ) {
238 // We are here because there is a call interference and no non-volatile
239 // color could be found.
240 // Now try to allocate even a volatile color
242 ColorFound = findFloatColor( LR, SparcFloatRegOrder::StartOfAllRegs,
243 SparcFloatRegOrder::StartOfNonVolatileRegs,
249 if( ColorFound >= 0 ) {
250 LR->setColor(ColorFound); // first color found in preffered order
251 LR->markForSaveAcrossCalls();
253 // we are here because no color could be found
254 LR->markForSpill(); // no color found - must spill
259 //-----------------------------------------------------------------------------
260 // Helper method for coloring a node of Float Reg class.
261 // Finds the first available color in the range [Start,End] depending on the
262 // type of the Node (i.e., float/double)
263 //-----------------------------------------------------------------------------
265 int SparcFloatRegClass::findFloatColor(const LiveRange *LR,
266 unsigned Start, unsigned End,
267 bool IsColorUsedArr[]) const {
268 bool ColorFound = false;
271 if (LR->getType() == Type::DoubleTy) {
272 // find first unused color for a double
273 for (c=Start; c < End ; c+= 2)
274 if (!IsColorUsedArr[c] && !IsColorUsedArr[c+1])
277 // find first unused color for a single
278 for (c = Start; c < End; c++)
279 if (!IsColorUsedArr[c])