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