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 "SparcInternals.h"
   9 #include "llvm/Type.h"
  10 #include "../../CodeGen/RegAlloc/RegAllocCommon.h"   // FIXME!
  11 #include "../../CodeGen/RegAlloc/IGNode.h"           // FIXME!
  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,
  27                                const std::vector<bool> &IsColorUsedArr) const
  28 {
  29   LiveRange *LR = Node->getParentLR();
  30
  31   if (DEBUG_RA) {
  32     std::cerr << "\nColoring LR [CallInt=" << LR->isCallInterference() <<"]:";
  33     printSet(*LR);
  34   }
  35
  36   if (LR->hasSuggestedColor()) {
  37     unsigned SugCol = LR->getSuggestedColor();
  38     if (!IsColorUsedArr[SugCol]) {
  39       if (LR->isSuggestedColorUsable()) {
  40         // if the suggested color is volatile, we should use it only if
  41         // there are no call interferences. Otherwise, it will get spilled.
  42         if (DEBUG_RA)
  43           std::cerr << "\n  -Coloring with sug color: " << SugCol;
  44
  45         LR->setColor(LR->getSuggestedColor());
  46         return;
  47       } else if(DEBUG_RA) {
  48         std::cerr << "\n Couldn't alloc Sug col - LR volatile & calls interf";
  49       }
  50     } else if (DEBUG_RA) {                // can't allocate the suggested col
  51       std::cerr << "\n  Could NOT allocate the suggested color (already used) ";
  52       printSet(*LR); std::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     // start with volatiles (we can  allocate volatiles safely)
  62     SearchStart = SparcIntRegClass::StartOfAllRegs;
  63   } else {
  64     // start with non volatiles (no non-volatiles)
  65     SearchStart =  SparcIntRegClass::StartOfNonVolatileRegs;
  66   }
  67
  68   unsigned c=0;                         // color
  69
  70   // find first unused color
  71   for (c=SearchStart; c < SparcIntRegClass::NumOfAvailRegs; c++) {
  72     if (!IsColorUsedArr[c]) {
  73       ColorFound = true;
  74       break;
  75     }
  76   }
  77
  78   if (ColorFound) {
  79     LR->setColor(c);                  // first color found in preffered order
  80     if (DEBUG_RA) std::cerr << "\n  Colored after first search with col " << c;
  81   }
  82
  83   // if color is not found because of call interference
  84   // try even finding a volatile color and insert save across calls
  85   //
  86   else if (LR->isCallInterference()) {
  87     // start from 0 - try to find even a volatile this time
  88     SearchStart = SparcIntRegClass::StartOfAllRegs;
  89
  90     // find first unused volatile color
  91     for(c=SearchStart; c < SparcIntRegClass::StartOfNonVolatileRegs; c++) {
  92       if (! IsColorUsedArr[c]) {
  93         ColorFound = true;
  94         break;
  95       }
  96     }
  97
  98     if (ColorFound) {
  99       LR->setColor(c);
 100       //  get the live range corresponding to live var
 101       // since LR span across calls, must save across calls
 102       //
 103       LR->markForSaveAcrossCalls();
 104       if (DEBUG_RA)
 105         std::cerr << "\n  Colored after SECOND search with col " << c;
 106     }
 107   }
 108
 109
 110   // If we couldn't find a color regardless of call interference - i.e., we
 111   // don't have either a volatile or non-volatile color left
 112   //
 113   if (!ColorFound)
 114     LR->markForSpill();               // no color found - must spill
 115 }
 116
 117 //-----------------------------------------------------------------------------
 118 // Int CC Register Class - method for coloring a node in the interference graph.
 119 //
 120 // Algorithm:
 121 //
 122 //     If (node has any interferences)
 123 //         /* all interference operations can use only one register! */
 124 //         mark the LR for spilling
 125 //     else {
 126 //         if (the LR is a 64-bit comparison) use %xcc
 127 //         else /*32-bit or smaller*/ use %icc
 128 //     }
 129 //
 130 // Note: The third name (%ccr) is essentially an assembly mnemonic and
 131 // depends solely on the opcode, so the name can be chosen in EmitAssembly.
 132 //-----------------------------------------------------------------------------
 133 void SparcIntCCRegClass::colorIGNode(IGNode *Node,
 134                                  const std::vector<bool> &IsColorUsedArr) const
 135 {
 136   if (Node->getNumOfNeighbors() > 0)
 137     Node->getParentLR()->markForSpill();
 138
 139   // Mark the appropriate register in any case (even if it needs to be spilled)
 140   // because there is only one possible register, but more importantly, the
 141   // spill algorithm cannot find it.  In particular, we have to choose
 142   // whether to use %xcc or %icc based on type of value compared
 143   //
 144   const LiveRange* ccLR = Node->getParentLR();
 145   const Type* setCCType = (* ccLR->begin())->getType(); // any Value in LR
 146   assert(setCCType->isIntegral() || isa<PointerType>(setCCType));
 147   int ccReg = ((isa<PointerType>(setCCType) || setCCType == Type::LongTy)
 148                ? xcc : icc);
 149
 150 #ifndef NDEBUG
 151   // Let's just make sure values of two different types have not been
 152   // coalesced into this LR.
 153   for (ValueSet::const_iterator I=ccLR->begin(), E=ccLR->end(); I!=E; ++I) {
 154     const Type* ccType = (*I)->getType();
 155     assert((ccReg == xcc && (isa<PointerType>(ccType)
 156                              || ccType == Type::LongTy)) ||
 157            (ccReg == icc && ccType->isIntegral() && ccType != Type::LongTy)
 158            && "Comparisons needing different intCC regs coalesced in LR!");
 159   }
 160 #endif
 161
 162   Node->setColor(ccReg);                // only one int cc reg is available
 163 }
 164
 165
 166 void SparcFloatCCRegClass::colorIGNode(IGNode *Node,
 167                                 const std::vector<bool> &IsColorUsedArr) const {
 168   for(unsigned c = 0; c != 4; ++c)
 169     if (!IsColorUsedArr[c]) { // find unused color
 170       Node->setColor(c);
 171       return;
 172     }
 173
 174   Node->getParentLR()->markForSpill();
 175 }
 176
 177
 178
 179 //-----------------------------------------------------------------------------
 180 // Float Register Class - method for coloring a node in the interference graph.
 181 //
 182 // Algorithm:
 183 //
 184 //     If the LR is a double try to allocate f32 - f63
 185 //     If the above fails or LR is single precision
 186 //        If the LR does not interfere with a call
 187 //         start allocating from f0
 188 //      Else start allocating from f6
 189 //     If a color is still not found because LR interferes with a call
 190 //        Search in f0 - f6. If found mark for spill across calls.
 191 //     If a color is still not fond, mark for spilling
 192 //
 193 //----------------------------------------------------------------------------
 194 void SparcFloatRegClass::colorIGNode(IGNode * Node,
 195                                  const std::vector<bool> &IsColorUsedArr) const
 196 {
 197   LiveRange *LR = Node->getParentLR();
 198
 199 #ifndef NDEBUG
 200   // Check that the correct colors have been are marked for fp-doubles.
 201   //
 202   // FIXME: This is old code that is no longer needed.  Temporarily converting
 203   // it into a big assertion just to check that the replacement logic
 204   // (invoking SparcFloatRegClass::markColorsUsed() directly from
 205   // RegClass::colorIGNode) works correctly.
 206   //
 207   // In fact, this entire function should be identical to
 208   // SparcIntRegClass::colorIGNode(), and perhaps can be
 209   // made into a general case in CodeGen/RegAlloc/RegClass.cpp.
 210   //
 211   unsigned NumNeighbors =  Node->getNumOfNeighbors();   // total # of neighbors
 212   for(unsigned n=0; n < NumNeighbors; n++) {            // for each neigh
 213     IGNode *NeighIGNode = Node->getAdjIGNode(n);
 214     LiveRange *NeighLR = NeighIGNode->getParentLR();
 215
 216     if (NeighLR->hasColor()) {
 217       assert(IsColorUsedArr[ NeighLR->getColor() ]);
 218       if (NeighLR->getType() == Type::DoubleTy)
 219         assert(IsColorUsedArr[ NeighLR->getColor()+1 ]);
 220
 221     } else if (NeighLR->hasSuggestedColor() &&
 222                NeighLR-> isSuggestedColorUsable() ) {
 223
 224       // if the neighbour can use the suggested color
 225       assert(IsColorUsedArr[ NeighLR->getSuggestedColor() ]);
 226       if (NeighLR->getType() == Type::DoubleTy)
 227         assert(IsColorUsedArr[ NeighLR->getSuggestedColor()+1 ]);
 228     }
 229   }
 230 #endif
 231
 232   // **NOTE: We don't check for call interferences in allocating suggested
 233   // color in this class since ALL registers are volatile. If this fact
 234   // changes, we should change the following part
 235   //- see SparcIntRegClass::colorIGNode()
 236   //
 237   if( LR->hasSuggestedColor() ) {
 238     if( ! IsColorUsedArr[ LR->getSuggestedColor() ] ) {
 239       LR->setColor(  LR->getSuggestedColor() );
 240       return;
 241     } else if (DEBUG_RA)  {                 // can't allocate the suggested col
 242       std::cerr << " Could NOT allocate the suggested color for LR ";
 243       printSet(*LR); std::cerr << "\n";
 244     }
 245   }
 246
 247
 248   int ColorFound = -1;               // have we found a color yet?
 249   bool isCallInterf = LR->isCallInterference();
 250
 251   // if value is a double - search the double only region (f32 - f63)
 252   // i.e. we try to allocate f32 - f63 first for doubles since singles
 253   // cannot go there. By doing that, we provide more space for singles
 254   // in f0 - f31
 255   //
 256   if (LR->getType() == Type::DoubleTy)
 257     ColorFound = findFloatColor( LR, 32, 64, IsColorUsedArr );
 258
 259   if (ColorFound >= 0) {               // if we could find a color
 260     LR->setColor(ColorFound);
 261     return;
 262   } else {
 263
 264     // if we didn't find a color becuase the LR was single precision or
 265     // all f32-f63 range is filled, we try to allocate a register from
 266     // the f0 - f31 region
 267
 268     unsigned SearchStart;                 // start pos of color in pref-order
 269
 270     //if this Node is between calls (i.e., no call interferences )
 271     if (! isCallInterf) {
 272       // start with volatiles (we can  allocate volatiles safely)
 273       SearchStart = SparcFloatRegClass::StartOfAllRegs;
 274     } else {
 275       // start with non volatiles (no non-volatiles)
 276       SearchStart =  SparcFloatRegClass::StartOfNonVolatileRegs;
 277     }
 278
 279     ColorFound = findFloatColor(LR, SearchStart, 32, IsColorUsedArr);
 280   }
 281
 282   if (ColorFound >= 0) {               // if we could find a color
 283     LR->setColor(ColorFound);
 284     return;
 285   } else if (isCallInterf) {
 286     // We are here because there is a call interference and no non-volatile
 287     // color could be found.
 288     // Now try to allocate even a volatile color
 289     ColorFound = findFloatColor(LR, SparcFloatRegClass::StartOfAllRegs,
 290                                 SparcFloatRegClass::StartOfNonVolatileRegs,
 291                                 IsColorUsedArr);
 292   }
 293
 294   if (ColorFound >= 0) {
 295     LR->setColor(ColorFound);         // first color found in prefered order
 296     LR->markForSaveAcrossCalls();
 297   } else {
 298     // we are here because no color could be found
 299     LR->markForSpill();               // no color found - must spill
 300   }
 301 }
 302
 303 //-----------------------------------------------------------------------------
 304 // This method marks the registers used for a given register number.
 305 // This marks a single register for Float regs, but the R,R+1 pair
 306 // for double-precision registers.
 307 //-----------------------------------------------------------------------------
 308
 309 void SparcFloatRegClass::markColorsUsed(unsigned RegInClass,
 310                                         int UserRegType,
 311                                         int RegTypeWanted,
 312                                     std::vector<bool> &IsColorUsedArr) const
 313 {
 314   if (UserRegType == UltraSparcRegInfo::FPDoubleRegType ||
 315       RegTypeWanted == UltraSparcRegInfo::FPDoubleRegType) {
 316     // This register is used as or is needed as a double-precision reg.
 317     // We need to mark the [even,odd] pair corresponding to this reg.
 318     // Get the even numbered register corresponding to this reg.
 319     unsigned EvenRegInClass = RegInClass & ~1u;
 320     assert(EvenRegInClass+1 < NumOfAllRegs &&
 321            EvenRegInClass+1 < IsColorUsedArr.size());
 322     IsColorUsedArr[EvenRegInClass]   = true;
 323     IsColorUsedArr[EvenRegInClass+1] = true;
 324   }
 325   else {
 326     assert(RegInClass < NumOfAllRegs && RegInClass < IsColorUsedArr.size());
 327     assert(UserRegType == RegTypeWanted
 328            && "Something other than FP single/double types share a reg class?");
 329     IsColorUsedArr[RegInClass] = true;
 330   }
 331 }
 332
 333 // This method finds unused registers of the specified register type,
 334 // using the given "used" flag array IsColorUsedArr.  It checks a single
 335 // entry in the array directly for float regs, and checks the pair [R,R+1]
 336 // for double-precision registers
 337 // It returns -1 if no unused color is found.
 338 //
 339 int SparcFloatRegClass::findUnusedColor(int RegTypeWanted,
 340                                 const std::vector<bool> &IsColorUsedArr) const
 341 {
 342   if (RegTypeWanted == UltraSparcRegInfo::FPDoubleRegType) {
 343     unsigned NC = 2 * this->getNumOfAvailRegs();
 344     assert(IsColorUsedArr.size() == NC && "Invalid colors-used array");
 345     for (unsigned c = 0; c < NC; c+=2)
 346       if (!IsColorUsedArr[c]) {
 347         assert(!IsColorUsedArr[c+1] && "Incorrect used regs for FP double!");
 348         return c;
 349       }
 350     return -1;
 351   }
 352   else
 353     return TargetRegClassInfo::findUnusedColor(RegTypeWanted, IsColorUsedArr);
 354 }
 355
 356 //-----------------------------------------------------------------------------
 357 // Helper method for coloring a node of Float Reg class.
 358 // Finds the first available color in the range [Start,End] depending on the
 359 // type of the Node (i.e., float/double)
 360 //-----------------------------------------------------------------------------
 361
 362 int SparcFloatRegClass::findFloatColor(const LiveRange *LR,
 363                                        unsigned Start,
 364                                        unsigned End,
 365                                const std::vector<bool> &IsColorUsedArr) const
 366 {
 367   if (LR->getType() == Type::DoubleTy) {
 368     // find first unused color for a double
 369     assert(Start % 2 == 0 && "Odd register number could be used for double!");
 370     for (unsigned c=Start; c < End ; c+= 2)
 371       if (!IsColorUsedArr[c]) {
 372         assert(!IsColorUsedArr[c+1] &&
 373                "Incorrect marking of used regs for Sparc FP double!");
 374         return c;
 375       }
 376   } else {
 377     // find first unused color for a single
 378     for (unsigned c = Start; c < End; c++)
 379       if (!IsColorUsedArr[c])
 380         return c;
 381   }
 382
 383   return -1;
 384
 385 }