lib/Target/SparcV9/SparcV9RegClassInfo.cpp

   1 #include "SparcRegClassInfo.h"
   2 #include "llvm/CodeGen/IGNode.h"
   3 #include "llvm/Target/Sparc.h"
   4 #include "llvm/Type.h"
   5 #include <iostream>
   6 using std::cerr;
   7
   8 //-----------------------------------------------------------------------------
   9 // Int Register Class - method for coloring a node in the interference graph.
  10 //
  11 // Algorithm:
  12 //     Record the colors/suggested colors of all neighbors.
  13 //
  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.
  19 //
  20 //-----------------------------------------------------------------------------
  21 void SparcIntRegClass::colorIGNode(IGNode * Node, bool IsColorUsedArr[]) const {
  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     printSet(*LR);
  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       printSet(*LR); 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
 130
 131
 132
 133
 134 //-----------------------------------------------------------------------------
 135 // Float Register Class - method for coloring a node in the interference graph.
 136 //
 137 // Algorithm:
 138 //
 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
 147 //
 148 //----------------------------------------------------------------------------
 149 void SparcFloatRegClass::colorIGNode(IGNode * Node,bool IsColorUsedArr[]) const{
 150   LiveRange *LR = Node->getParentLR();
 151   unsigned NumNeighbors =  Node->getNumOfNeighbors();   // total # of neighbors
 152
 153   for(unsigned n=0; n < NumNeighbors; n++) {            // for each neigh
 154     IGNode *NeighIGNode = Node->getAdjIGNode(n);
 155     LiveRange *NeighLR = NeighIGNode->getParentLR();
 156
 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;
 161       }
 162       else if( NeighLR->hasSuggestedColor() )   {   // if neigh has sugg color
 163
 164         if( NeighLR-> isSuggestedColorUsable() ) {
 165
 166           // if the neighbout can use the suggested color
 167
 168           IsColorUsedArr[ NeighLR->getSuggestedColor() ] = true;
 169           if (NeighLR->getType() == Type::DoubleTy)
 170             IsColorUsedArr[ (NeighLR->getSuggestedColor()) + 1 ] = true;
 171         }
 172
 173       }
 174
 175   }
 176
 177
 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()
 182
 183   if( LR->hasSuggestedColor() ) {
 184     if( ! IsColorUsedArr[ LR->getSuggestedColor() ] ) {
 185       LR->setColor(  LR->getSuggestedColor() );
 186       return;
 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";
 190     }
 191   }
 192
 193
 194   int ColorFound = -1;               // have we found a color yet?
 195   bool isCallInterf = LR->isCallInterference();
 196
 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
 200   // in f0 - f31
 201   //
 202   if (LR->getType() == Type::DoubleTy)
 203     ColorFound = findFloatColor( LR, 32, 64, IsColorUsedArr );
 204
 205
 206   if( ColorFound >= 0 ) {               // if we could find a color
 207     LR->setColor(ColorFound);
 208     return;
 209   } else {
 210
 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
 214
 215     unsigned SearchStart;                 // start pos of color in pref-order
 216
 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;
 221     }
 222     else {
 223       // start with non volatiles (no non-volatiles)
 224       SearchStart =  SparcFloatRegOrder::StartOfNonVolatileRegs;
 225     }
 226
 227     ColorFound = findFloatColor( LR, SearchStart, 32, IsColorUsedArr );
 228   }
 229
 230
 231
 232   if( ColorFound >= 0 ) {               // if we could find a color
 233     LR->setColor(ColorFound);
 234     return;
 235   }
 236   else if( isCallInterf ) {
 237
 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
 241
 242     ColorFound = findFloatColor( LR, SparcFloatRegOrder::StartOfAllRegs,
 243                                 SparcFloatRegOrder::StartOfNonVolatileRegs,
 244                                 IsColorUsedArr);
 245   }
 246
 247
 248
 249   if( ColorFound >= 0 ) {
 250     LR->setColor(ColorFound);         // first color found in preffered order
 251     LR->markForSaveAcrossCalls();
 252   } else {
 253     // we are here because no color could be found
 254     LR->markForSpill();               // no color found - must spill
 255   }
 256 }
 257
 258
 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 //-----------------------------------------------------------------------------
 264
 265 int SparcFloatRegClass::findFloatColor(const LiveRange *LR,
 266                                        unsigned Start, unsigned End,
 267                                        bool IsColorUsedArr[]) const {
 268   bool ColorFound = false;
 269   unsigned c;
 270
 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])
 275         return c;
 276   } else {
 277     // find first unused color for a single
 278     for (c = Start; c < End; c++)
 279       if (!IsColorUsedArr[c])
 280         return c;
 281   }
 282
 283   return -1;
 284 }