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