lib/Target/SparcV9/SparcV9RegClassInfo.cpp

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