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