lib/Target/SparcV9/SparcV9RegClassInfo.cpp

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