lib/Target/SparcV9/SparcV9RegClassInfo.cpp

   1 #include "SparcInternals.h"
   2 #include "llvm/CodeGen/IGNode.h"
   3 #include "llvm/Target/Sparc.h"
   4 #include <iostream>
   5 using std::cerr;
   6
   7 //-----------------------------------------------------------------------------
   8 // Int Register Class - method for coloring a node in the interference graph.
   9 //
  10 // Algorithm:
  11 //     Record the colors/suggested colors of all neighbors.
  12 //
  13 //     If there is a suggested color, try to allocate it
  14 //     If there is no call interf, try to allocate volatile, then non volatile
  15 //     If there is call interf, try to allocate non-volatile. If that fails
  16 //     try to allocate a volatile and insert save across calls
  17 //     If both above fail, spill.
  18 //
  19 //-----------------------------------------------------------------------------
  20 void SparcIntRegClass::colorIGNode(IGNode * Node, bool IsColorUsedArr[]) const
  21 {
  22   LiveRange * LR = Node->getParentLR();
  23   unsigned NumNeighbors =  Node->getNumOfNeighbors();   // total # of neighbors
  24
  25   for(unsigned n=0; n < NumNeighbors; n++) {            // for each neigh
  26     IGNode *NeighIGNode = Node->getAdjIGNode(n);
  27     LiveRange *NeighLR = NeighIGNode->getParentLR();
  28
  29     if( NeighLR->hasColor() )                        // if has a color
  30       IsColorUsedArr[ NeighLR->getColor() ] = true; // record that color
  31
  32     else if( NeighLR->hasSuggestedColor() ) {
  33
  34         // if the neighbout can use the suggested color
  35         if( NeighLR-> isSuggestedColorUsable() )
  36           IsColorUsedArr[ NeighLR->getSuggestedColor() ] = true;
  37     }
  38   }
  39
  40   if( DEBUG_RA ) {
  41     cerr << "\nColoring LR [CallInt=" << LR->isCallInterference() <<"]:";
  42     LR->printSet();
  43   }
  44
  45   if( LR->hasSuggestedColor() ) {
  46
  47     unsigned SugCol = LR->getSuggestedColor();
  48
  49     if( ! IsColorUsedArr[ SugCol ] ) {
  50
  51       if( LR->isSuggestedColorUsable()  ) {
  52
  53         // if the suggested color is volatile, we should use it only if
  54         // there are no call interferences. Otherwise, it will get spilled.
  55
  56         if (DEBUG_RA)
  57           cerr << "\n  -Coloring with sug color: " << SugCol;
  58
  59         LR->setColor(  LR->getSuggestedColor() );
  60         return;
  61       }
  62        else if(DEBUG_RA)
  63          cerr << "\n Couldn't alloc Sug col - LR voloatile & calls interf";
  64
  65     }
  66     else if ( DEBUG_RA ) {                // can't allocate the suggested col
  67       cerr << "  \n  Could NOT allocate the suggested color (already used) ";
  68       LR->printSet(); cerr << "\n";
  69     }
  70   }
  71
  72   unsigned SearchStart;                 // start pos of color in pref-order
  73   bool ColorFound= false;               // have we found a color yet?
  74
  75   //if this Node is between calls
  76   if( ! LR->isCallInterference() ) {
  77
  78     // start with volatiles (we can  allocate volatiles safely)
  79     SearchStart = SparcIntRegOrder::StartOfAllRegs;
  80   }
  81   else {
  82     // start with non volatiles (no non-volatiles)
  83     SearchStart =  SparcIntRegOrder::StartOfNonVolatileRegs;
  84   }
  85
  86   unsigned c=0;                         // color
  87
  88   // find first unused color
  89   for( c=SearchStart; c < SparcIntRegOrder::NumOfAvailRegs; c++) {
  90     if( ! IsColorUsedArr[ c ] ) { ColorFound = true; break; }
  91   }
  92
  93   if( ColorFound) {
  94     LR->setColor(c);                  // first color found in preffered order
  95     if (DEBUG_RA) cerr << "\n  Colored after first search with col " << c ;
  96   }
  97
  98   // if color is not found because of call interference
  99   // try even finding a volatile color and insert save across calls
 100   //
 101   else if( LR->isCallInterference() )
 102   {
 103     // start from 0 - try to find even a volatile this time
 104     SearchStart = SparcIntRegOrder::StartOfAllRegs;
 105
 106     // find first unused volatile color
 107     for(c=SearchStart; c < SparcIntRegOrder::StartOfNonVolatileRegs; c++) {
 108       if( ! IsColorUsedArr[ c ] ) { ColorFound = true; break; }
 109     }
 110
 111     if( ColorFound) {
 112        LR->setColor(c);
 113        //  get the live range corresponding to live var
 114        // since LR span across calls, must save across calls
 115        //
 116        LR->markForSaveAcrossCalls();
 117        if(DEBUG_RA) cerr << "\n  Colored after SECOND search with col " << c ;
 118     }
 119   }
 120
 121
 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
 124   //
 125   if( !ColorFound )
 126     LR->markForSpill();               // no color found - must spill
 127
 128
 129   if( DEBUG_RA)
 130       UltraSparcRegInfo::printReg(  LR  );
 131
 132 }
 133
 134
 135
 136
 137
 138
 139 //-----------------------------------------------------------------------------
 140 // Float Register Class - method for coloring a node in the interference graph.
 141 //
 142 // Algorithm:
 143 //
 144 //     If the LR is a double try to allocate f32 - f63
 145 //     If the above fails or LR is single precision
 146 //        If the LR does not interfere with a call
 147 //         start allocating from f0
 148 //      Else start allocating from f6
 149 //     If a color is still not found because LR interferes with a call
 150 //        Search in f0 - f6. If found mark for spill across calls.
 151 //     If a color is still not fond, mark for spilling
 152 //
 153 //----------------------------------------------------------------------------
 154 void SparcFloatRegClass::colorIGNode(IGNode * Node,bool IsColorUsedArr[]) const
 155 {
 156
 157   LiveRange * LR = Node->getParentLR();
 158   unsigned NumNeighbors =  Node->getNumOfNeighbors();   // total # of neighbors
 159
 160   for(unsigned n=0; n < NumNeighbors; n++) {            // for each neigh
 161     IGNode *NeighIGNode = Node->getAdjIGNode(n);
 162     LiveRange *NeighLR = NeighIGNode->getParentLR();
 163
 164       if( NeighLR->hasColor() )   {                     // if neigh has a color
 165         IsColorUsedArr[ NeighLR->getColor() ] = true; // record that color
 166         if( NeighLR->getTypeID() == Type::DoubleTyID )
 167           IsColorUsedArr[ (NeighLR->getColor()) + 1 ] = true;
 168       }
 169       else if( NeighLR->hasSuggestedColor() )   {   // if neigh has sugg color
 170
 171         if( NeighLR-> isSuggestedColorUsable() ) {
 172
 173           // if the neighbout can use the suggested color
 174
 175           IsColorUsedArr[ NeighLR->getSuggestedColor() ] = true;
 176           if( NeighLR->getTypeID() == Type::DoubleTyID )
 177             IsColorUsedArr[ (NeighLR->getSuggestedColor()) + 1 ] = true;
 178         }
 179
 180       }
 181
 182   }
 183
 184
 185   // **NOTE: We don't check for call interferences in allocating suggested
 186   // color in this class since ALL registers are volatile. If this fact
 187   // changes, we should change the following part
 188   //- see SparcIntRegClass::colorIGNode()
 189
 190   if( LR->hasSuggestedColor() ) {
 191     if( ! IsColorUsedArr[ LR->getSuggestedColor() ] ) {
 192       LR->setColor(  LR->getSuggestedColor() );
 193       return;
 194     }
 195     else if (DEBUG_RA)  {                 // can't allocate the suggested col
 196       cerr << " Could NOT allocate the suggested color for LR ";
 197       LR->printSet(); cerr << "\n";
 198     }
 199   }
 200
 201
 202   int ColorFound = -1;               // have we found a color yet?
 203   bool isCallInterf = LR->isCallInterference();
 204
 205   // if value is a double - search the double only reigon (f32 - f63)
 206   // i.e. we try to allocate f32 - f63 first for doubles since singles
 207   // cannot go there. By doing that, we provide more space for singles
 208   // in f0 - f31
 209   //
 210   if( LR->getTypeID() == Type::DoubleTyID )
 211     ColorFound = findFloatColor( LR, 32, 64, IsColorUsedArr );
 212
 213
 214   if( ColorFound >= 0 ) {               // if we could find a color
 215     LR->setColor(ColorFound);
 216     if( DEBUG_RA) UltraSparcRegInfo::printReg( LR );
 217     return;
 218   }
 219   else {
 220
 221     // if we didn't find a color becuase the LR was single precision or
 222     // all f32-f63 range is filled, we try to allocate a register from
 223     // the f0 - f31 region
 224
 225     unsigned SearchStart;                 // start pos of color in pref-order
 226
 227     //if this Node is between calls (i.e., no call interferences )
 228     if( ! isCallInterf ) {
 229       // start with volatiles (we can  allocate volatiles safely)
 230       SearchStart = SparcFloatRegOrder::StartOfAllRegs;
 231     }
 232     else {
 233       // start with non volatiles (no non-volatiles)
 234       SearchStart =  SparcFloatRegOrder::StartOfNonVolatileRegs;
 235     }
 236
 237     ColorFound = findFloatColor( LR, SearchStart, 32, IsColorUsedArr );
 238   }
 239
 240
 241
 242   if( ColorFound >= 0 ) {               // if we could find a color
 243     LR->setColor(ColorFound);
 244     if( DEBUG_RA) UltraSparcRegInfo::printReg( LR );
 245     return;
 246   }
 247   else if( isCallInterf ) {
 248
 249     // We are here because there is a call interference and no non-volatile
 250     // color could be found.
 251     // Now try to allocate even a volatile color
 252
 253     ColorFound = findFloatColor( LR, SparcFloatRegOrder::StartOfAllRegs,
 254                                 SparcFloatRegOrder::StartOfNonVolatileRegs,
 255                                 IsColorUsedArr);
 256   }
 257
 258
 259
 260   if( ColorFound >= 0 ) {
 261     LR->setColor(ColorFound);         // first color found in preffered order
 262     LR->markForSaveAcrossCalls();
 263     if( DEBUG_RA) UltraSparcRegInfo::printReg( LR );
 264     return;
 265   }
 266
 267
 268   // we are here because no color could be found
 269
 270   LR->markForSpill();               // no color found - must spill
 271   if( DEBUG_RA) UltraSparcRegInfo::printReg( LR );
 272
 273 }
 274
 275
 276
 277 //-----------------------------------------------------------------------------
 278 // Helper method for coloring a node of Float Reg class.
 279 // Finds the first available color in the range [Start,End] depending on the
 280 // type of the Node (i.e., float/double)
 281 //-----------------------------------------------------------------------------
 282 int SparcFloatRegClass::findFloatColor(const LiveRange *const LR,
 283                                        unsigned Start,
 284                                        unsigned End,
 285                                        bool IsColorUsedArr[] ) const {
 286
 287   bool ColorFound = false;
 288   unsigned c;
 289
 290   if( LR->getTypeID() == Type::DoubleTyID ) {
 291
 292     // find first unused color for a double
 293     for( c=Start; c < End ;c+= 2){
 294       if( ! IsColorUsedArr[ c ] &&  ! IsColorUsedArr[ c+1 ])
 295         { ColorFound=true;  break; }
 296     }
 297
 298   } else {
 299
 300     // find first unused color for a single
 301     for( c=Start; c < End; c++) {
 302       if( ! IsColorUsedArr[ c ] ) { ColorFound=true;  break; }
 303     }
 304   }
 305
 306   if( ColorFound ) return c;
 307   else return -1;
 308 }
 309
 310
 311
 312
 313
 314
 315
 316
 317
 318
 319
 320
 321
 322