lib/Target/SparcV9/SparcV9RegClassInfo.cpp

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