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
   8 //-----------------------------------------------------------------------------
   9
  10 void SparcIntRegClass::colorIGNode(IGNode * Node, bool IsColorUsedArr[]) const
  11 {
  12
  13   /* Algorithm:
  14      Record the colors/suggested colors of all neighbors.
  15
  16      If there is a suggested color, try to allocate it
  17      If there is no call interf, try to allocate volatile, then non volatile
  18      If there is call interf, try to allocate non-volatile. If that fails
  19      try to allocate a volatile and insert save across calls
  20      If both above fail, spill.
  21
  22   */
  23
  24   LiveRange * LR = Node->getParentLR();
  25   unsigned NumNeighbors =  Node->getNumOfNeighbors();   // total # of neighbors
  26
  27   for(unsigned n=0; n < NumNeighbors; n++) {            // for each neigh
  28     IGNode *NeighIGNode = Node->getAdjIGNode(n);
  29     LiveRange *NeighLR = NeighIGNode->getParentLR();
  30
  31     if( NeighLR->hasColor() )                        // if has a color
  32       IsColorUsedArr[ NeighLR->getColor() ] = true; // record that color
  33
  34     else if( NeighLR->hasSuggestedColor() )        // or has a suggest col
  35       IsColorUsedArr[ NeighLR->getSuggestedColor() ] = true;
  36
  37   }
  38
  39
  40   if( LR->hasSuggestedColor() ) {
  41     if( ! IsColorUsedArr[ LR->getSuggestedColor() ] ) {
  42       LR->setColor(  LR->getSuggestedColor() );
  43       return;
  44     }
  45     else {                              // can't allocate the suggested col
  46       cout << " Coud NOT allocate the suggested color for LR ";
  47       LR->printSet(); cout << endl;
  48     }
  49   }
  50
  51   unsigned SearchStart;                 // start pos of color in pref-order
  52   bool ColorFound= false;               // have we found a color yet?
  53
  54   //if this Node is between calls
  55   if( LR->getNumOfCallInterferences() == 0) {
  56
  57     // start with volatiles (we can  allocate volatiles safely)
  58     SearchStart = SparcIntRegOrder::StartOfAllRegs;
  59   }
  60   else {
  61     // start with non volatiles (no non-volatiles)
  62     SearchStart =  SparcIntRegOrder::StartOfNonVolatileRegs;
  63   }
  64
  65   unsigned c=0;                         // color
  66
  67   // find first unused color
  68   for( c=SearchStart; c < SparcIntRegOrder::NumOfAvailRegs; c++) {
  69     if( ! IsColorUsedArr[ c ] ) { ColorFound = true; break; }
  70   }
  71
  72   if( ColorFound)
  73     LR->setColor(c);                  // first color found in preffered order
  74
  75
  76   // if color is not found because of call interference
  77   // try even finding a volatile color and insert save across calls
  78   else if( LR->getNumOfCallInterferences() )
  79   {
  80     // start from 0 - try to find even a volatile this time
  81     SearchStart = SparcIntRegOrder::StartOfAllRegs;
  82
  83     // find first unused volatile color
  84     for(c=SearchStart; c < SparcIntRegOrder::StartOfNonVolatileRegs; c++) {
  85       if( ! IsColorUsedArr[ c ] ) { ColorFound = true; break; }
  86     }
  87
  88     if( ColorFound) {
  89       LR->setColor(c);
  90       // since LR span across calls, must save across calls
  91       LR->markForSaveAcrossCalls();
  92     }
  93
  94   }
  95
  96
  97   // If we couldn't find a color regardless of call interference - i.e., we
  98   // don't have either a volatile or non-volatile color left
  99   if( !ColorFound )
 100     LR->markForSpill();               // no color found - must spill
 101
 102
 103   if( DEBUG_RA)
 104       UltraSparcRegInfo::printReg(  LR  );
 105
 106 }
 107
 108
 109
 110
 111
 112
 113 //-----------------------------------------------------------------------------
 114 // Float Register Class
 115 //-----------------------------------------------------------------------------
 116
 117 // find the first available color in the range [Start,End] depending on the
 118 // type of the Node (i.e., float/double)
 119
 120 int SparcFloatRegClass::findFloatColor(const LiveRange *const LR,
 121                                        unsigned Start,
 122                                        unsigned End,
 123                                        bool IsColorUsedArr[] ) const
 124 {
 125
 126   bool ColorFound = false;
 127   unsigned c;
 128
 129   if( LR->getTypeID() == Type::DoubleTyID ) {
 130
 131     // find first unused color for a double
 132     for( c=Start; c < End ;c+= 2){
 133       if( ! IsColorUsedArr[ c ] &&  ! IsColorUsedArr[ c+1 ])
 134         { ColorFound=true;  break; }
 135     }
 136
 137   } else {
 138
 139     // find first unused color for a single
 140     for( c=Start; c < End; c++) {
 141       if( ! IsColorUsedArr[ c ] ) { ColorFound=true;  break; }
 142     }
 143   }
 144
 145   if( ColorFound ) return c;
 146   else return -1;
 147 }
 148
 149
 150
 151
 152
 153 void SparcFloatRegClass::colorIGNode(IGNode * Node,bool IsColorUsedArr[]) const
 154 {
 155
 156   /* Algorithm:
 157
 158      If the LR is a double try to allocate f32 - f63
 159      If the above fails or LR is single precision
 160         If the LR does not interfere with a call
 161            start allocating from f0
 162         Else start allocating from f6
 163      If a color is still not found because LR interferes with a call
 164         Search in f0 - f6. If found mark for spill across calls.
 165      If a color is still not fond, mark for spilling
 166   */
 167
 168
 169   LiveRange * LR = Node->getParentLR();
 170   unsigned NumNeighbors =  Node->getNumOfNeighbors();   // total # of neighbors
 171
 172   for(unsigned n=0; n < NumNeighbors; n++) {            // for each neigh
 173     IGNode *NeighIGNode = Node->getAdjIGNode(n);
 174     LiveRange *NeighLR = NeighIGNode->getParentLR();
 175
 176       if( NeighLR->hasColor() )   {                     // if neigh has a color
 177         IsColorUsedArr[ NeighLR->getColor() ] = true; // record that color
 178         if( NeighLR->getTypeID() == Type::DoubleTyID )
 179           IsColorUsedArr[ (NeighLR->getColor()) + 1 ] = true;
 180       }
 181       else if( NeighLR->hasSuggestedColor() )   {   // if neigh has sugg color
 182         IsColorUsedArr[ NeighLR->getSuggestedColor() ] = true;
 183         if( NeighLR->getTypeID() == Type::DoubleTyID )
 184           IsColorUsedArr[ (NeighLR->getSuggestedColor()) + 1 ] = true;
 185       }
 186
 187   }
 188
 189
 190   if( LR->hasSuggestedColor() ) {
 191     if( ! IsColorUsedArr[ LR->getSuggestedColor() ] ) {
 192       LR->setColor(  LR->getSuggestedColor() );
 193       return;
 194     }
 195     else {                              // can't allocate the suggested col
 196       cout << " Coud NOT allocate the suggested color for LR ";
 197       LR->printSet(); cout << endl;
 198     }
 199   }
 200
 201
 202   int ColorFound = -1;               // have we found a color yet?
 203   unsigned NumOfCallInterf = LR->getNumOfCallInterferences();
 204
 205   // if value is a double - search the double only reigon (f32 - f63)
 206   if( LR->getTypeID() == Type::DoubleTyID )
 207     ColorFound = findFloatColor( LR, 32, 64, IsColorUsedArr );
 208
 209
 210   if( ColorFound >= 0 ) {
 211     LR->setColor(ColorFound);
 212     if( DEBUG_RA) UltraSparcRegInfo::printReg( LR );
 213     return;
 214   }
 215
 216   else { // the above fails or LR is single precision
 217
 218     unsigned SearchStart;                 // start pos of color in pref-order
 219
 220     //if this Node is between calls (i.e., no call interferences )
 221     if( ! NumOfCallInterf ) {
 222       // start with volatiles (we can  allocate volatiles safely)
 223       SearchStart = SparcFloatRegOrder::StartOfAllRegs;
 224     }
 225     else {
 226       // start with non volatiles (no non-volatiles)
 227       SearchStart =  SparcFloatRegOrder::StartOfNonVolatileRegs;
 228     }
 229
 230     ColorFound = findFloatColor( LR, SearchStart, 32, IsColorUsedArr );
 231
 232   }
 233
 234   if( ColorFound >= 0 ) {
 235     LR->setColor(ColorFound);
 236     if( DEBUG_RA) UltraSparcRegInfo::printReg( LR );
 237     return;
 238   }
 239
 240
 241   else if( NumOfCallInterf ) {
 242
 243     // We are here because there is a call interference and no non-volatile
 244     // color could be found.
 245     // Now try to allocate even a volatile color
 246
 247     ColorFound = findFloatColor( LR, SparcFloatRegOrder::StartOfAllRegs,
 248                                 SparcFloatRegOrder::StartOfNonVolatileRegs,
 249                                 IsColorUsedArr);
 250   }
 251
 252
 253
 254   if( ColorFound >= 0 ) {
 255     LR->setColor(ColorFound);         // first color found in preffered order
 256     LR->markForSaveAcrossCalls();
 257     if( DEBUG_RA) UltraSparcRegInfo::printReg( LR );
 258     return;
 259   }
 260
 261
 262   // we are here because no color could be found
 263
 264   LR->markForSpill();               // no color found - must spill
 265   if( DEBUG_RA) UltraSparcRegInfo::printReg( LR );
 266
 267
 268 }
 269
 270
 271
 272
 273
 274
 275
 276
 277
 278
 279
 280
 281
 282
 283
 284