lib/Target/SparcV9/SparcV9RegClassInfo.cpp

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