lib/Target/SparcV9/SparcV9RegClassInfo.cpp

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