lib/Target/SparcV9/SparcV9RegClassInfo.cpp

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