LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

SparcV9RegClassInfo.cpp

Go to the documentation of this file.
00001 //===-- SparcV9RegClassInfo.cpp - Register class def'ns for SparcV9 -------===//
00002 // 
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 // 
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file defines the methods used by the SparcV9 register allocator
00011 // to pick registers of various classes.  Most of this code should be
00012 // considered part of the register allocator.
00013 //
00014 //===----------------------------------------------------------------------===//
00015 
00016 #include "llvm/Type.h"
00017 #include "SparcV9RegClassInfo.h"
00018 #include "SparcV9Internals.h"
00019 #include "SparcV9RegInfo.h"
00020 #include "RegAlloc/RegAllocCommon.h"
00021 #include "RegAlloc/IGNode.h"
00022 #include <iostream>
00023 
00024 namespace llvm {
00025 
00026 //-----------------------------------------------------------------------------
00027 // Int Register Class - method for coloring a node in the interference graph.
00028 //
00029 // Algorithm:
00030 //     Record the colors/suggested colors of all neighbors.
00031 //
00032 //     If there is a suggested color, try to allocate it
00033 //     If there is no call interf, try to allocate volatile, then non volatile
00034 //     If there is call interf, try to allocate non-volatile. If that fails
00035 //     try to allocate a volatile and insert save across calls
00036 //     If both above fail, spill.
00037 //  
00038 //-----------------------------------------------------------------------------
00039 void SparcV9IntRegClass::colorIGNode(IGNode * Node,
00040                                const std::vector<bool> &IsColorUsedArr) const
00041 {
00042   LiveRange *LR = Node->getParentLR();
00043 
00044   if (DEBUG_RA)
00045     std::cerr << "\nColoring LR [CallInt=" << LR->isCallInterference() <<"]:"
00046               << *LR << "\n"; 
00047 
00048   if (LR->hasSuggestedColor()) {
00049     unsigned SugCol = LR->getSuggestedColor();
00050     if (!IsColorUsedArr[SugCol]) {
00051       if (LR->isSuggestedColorUsable()) {
00052   // if the suggested color is volatile, we should use it only if
00053   // there are no call interferences. Otherwise, it will get spilled.
00054   if (DEBUG_RA)
00055     std::cerr << "\n  -Coloring with sug color: " << SugCol;
00056 
00057   LR->setColor(LR->getSuggestedColor());
00058   return;
00059       } else if(DEBUG_RA) {
00060         std::cerr << "\n Couldn't alloc Sug col - LR volatile & calls interf";
00061       }
00062     } else if (DEBUG_RA) {                // can't allocate the suggested col
00063       std::cerr << "\n  Could NOT allocate the suggested color (already used) "
00064                 << *LR << "\n";
00065     }
00066   }
00067 
00068   unsigned SearchStart;                 // start pos of color in pref-order
00069   bool ColorFound= false;               // have we found a color yet?
00070 
00071   //if this Node is between calls
00072   if (! LR->isCallInterference()) { 
00073     // start with volatiles (we can  allocate volatiles safely)
00074     SearchStart = SparcV9IntRegClass::StartOfAllRegs;  
00075   } else {           
00076     // start with non volatiles (no non-volatiles)
00077     SearchStart =  SparcV9IntRegClass::StartOfNonVolatileRegs;  
00078   }
00079 
00080   unsigned c=0;                         // color
00081  
00082   // find first unused color
00083   for (c=SearchStart; c < SparcV9IntRegClass::NumOfAvailRegs; c++) { 
00084     if (!IsColorUsedArr[c]) {
00085       ColorFound = true;
00086       break;
00087     }
00088   }
00089 
00090   if (ColorFound) {
00091     LR->setColor(c);                  // first color found in preferred order
00092     if (DEBUG_RA) std::cerr << "\n  Colored after first search with col " << c;
00093   }
00094 
00095   // if color is not found because of call interference
00096   // try even finding a volatile color and insert save across calls
00097   //
00098   else if (LR->isCallInterference()) {
00099     // start from 0 - try to find even a volatile this time
00100     SearchStart = SparcV9IntRegClass::StartOfAllRegs;  
00101 
00102     // find first unused volatile color
00103     for(c=SearchStart; c < SparcV9IntRegClass::StartOfNonVolatileRegs; c++) { 
00104       if (! IsColorUsedArr[c]) {
00105         ColorFound = true;
00106         break;
00107       }
00108     }
00109 
00110     if (ColorFound) { 
00111       LR->setColor(c);  
00112       //  get the live range corresponding to live var
00113       // since LR span across calls, must save across calls 
00114       //
00115       if (DEBUG_RA)
00116         std::cerr << "\n  Colored after SECOND search with col " << c;
00117     }
00118   }
00119 
00120 
00121   // If we couldn't find a color regardless of call interference - i.e., we
00122   // don't have either a volatile or non-volatile color left
00123   //
00124   if (!ColorFound)  
00125     LR->markForSpill();               // no color found - must spill
00126 }
00127 
00128 //-----------------------------------------------------------------------------
00129 // Int CC Register Class - method for coloring a node in the interference graph.
00130 //
00131 // Algorithm:
00132 //
00133 //     If (node has any interferences)
00134 //         /* all interference operations can use only one register! */
00135 //         mark the LR for spilling
00136 //     else {
00137 //         if (the LR is a 64-bit comparison) use %xcc
00138 //         else /*32-bit or smaller*/ use %icc
00139 //     }
00140 // 
00141 // Note: The third name (%ccr) is essentially an assembly mnemonic and
00142 // depends solely on the opcode, so the name can be chosen in EmitAssembly.
00143 //-----------------------------------------------------------------------------
00144 void SparcV9IntCCRegClass::colorIGNode(IGNode *Node,
00145                                  const std::vector<bool> &IsColorUsedArr) const
00146 {
00147   if (Node->getNumOfNeighbors() > 0)
00148     Node->getParentLR()->markForSpill();
00149 
00150   // Mark the appropriate register in any case (even if it needs to be spilled)
00151   // because there is only one possible register, but more importantly, the
00152   // spill algorithm cannot find it.  In particular, we have to choose
00153   // whether to use %xcc or %icc based on type of value compared
00154   // 
00155   const LiveRange* ccLR = Node->getParentLR();
00156   const Type* setCCType = (* ccLR->begin())->getType(); // any Value in LR
00157   assert(setCCType->isIntegral() || isa<PointerType>(setCCType));
00158   int ccReg = ((isa<PointerType>(setCCType) || setCCType == Type::LongTy)
00159                ? xcc : icc);
00160 
00161 #ifndef NDEBUG
00162   // Let's just make sure values of two different types have not been
00163   // coalesced into this LR.
00164   for (LiveRange::const_iterator I=ccLR->begin(), E=ccLR->end(); I!=E; ++I) {
00165     const Type* ccType = (*I)->getType();
00166     assert((ccReg == xcc && (isa<PointerType>(ccType)
00167                              || ccType == Type::LongTy)) ||
00168            (ccReg == icc && ccType->isIntegral() && ccType != Type::LongTy)
00169            && "Comparisons needing different intCC regs coalesced in LR!");
00170   }
00171 #endif
00172 
00173   Node->setColor(ccReg);                // only one int cc reg is available
00174 }
00175 
00176 
00177 void SparcV9FloatCCRegClass::colorIGNode(IGNode *Node,
00178                                 const std::vector<bool> &IsColorUsedArr) const {
00179   for(unsigned c = 0; c != 4; ++c)
00180     if (!IsColorUsedArr[c]) { // find unused color
00181       Node->setColor(c);   
00182       return;
00183     }
00184   
00185   Node->getParentLR()->markForSpill();
00186 }
00187 
00188 
00189 
00190 //-----------------------------------------------------------------------------
00191 // Float Register Class - method for coloring a node in the interference graph.
00192 //
00193 // Algorithm:
00194 //
00195 //     If the LR is a double try to allocate f32 - f63
00196 //     If the above fails or LR is single precision
00197 //        If the LR does not interfere with a call
00198 //     start allocating from f0
00199 //  Else start allocating from f6
00200 //     If a color is still not found because LR interferes with a call
00201 //        Search in f0 - f6. If found mark for spill across calls.
00202 //     If a color is still not fond, mark for spilling
00203 //
00204 //----------------------------------------------------------------------------
00205 void SparcV9FloatRegClass::colorIGNode(IGNode * Node,
00206                                  const std::vector<bool> &IsColorUsedArr) const
00207 {
00208   LiveRange *LR = Node->getParentLR();
00209 
00210 #ifndef NDEBUG
00211   // Check that the correct colors have been are marked for fp-doubles.
00212   // 
00213   // FIXME: This is old code that is no longer needed.  Temporarily converting
00214   // it into a big assertion just to check that the replacement logic
00215   // (invoking SparcV9FloatRegClass::markColorsUsed() directly from
00216   // RegClass::colorIGNode) works correctly.
00217   // 
00218   // In fact, this entire function should be identical to
00219   // SparcV9IntRegClass::colorIGNode(), and perhaps can be
00220   // made into a general case in CodeGen/RegAlloc/RegClass.cpp.  
00221   // 
00222   unsigned NumNeighbors =  Node->getNumOfNeighbors();   // total # of neighbors
00223   for(unsigned n=0; n < NumNeighbors; n++) {            // for each neigh 
00224     IGNode *NeighIGNode = Node->getAdjIGNode(n);
00225     LiveRange *NeighLR = NeighIGNode->getParentLR();
00226     
00227     if (NeighLR->hasColor()) {
00228       assert(IsColorUsedArr[ NeighLR->getColor() ]);
00229       if (NeighLR->getType() == Type::DoubleTy)
00230         assert(IsColorUsedArr[ NeighLR->getColor()+1 ]);
00231       
00232     } else if (NeighLR->hasSuggestedColor() &&
00233                NeighLR-> isSuggestedColorUsable() ) {
00234 
00235       // if the neighbour can use the suggested color 
00236       assert(IsColorUsedArr[ NeighLR->getSuggestedColor() ]);
00237       if (NeighLR->getType() == Type::DoubleTy)
00238         assert(IsColorUsedArr[ NeighLR->getSuggestedColor()+1 ]);
00239     }
00240   }
00241 #endif
00242 
00243   // **NOTE: We don't check for call interferences in allocating suggested
00244   // color in this class since ALL registers are volatile. If this fact
00245   // changes, we should change the following part 
00246   //- see SparcV9IntRegClass::colorIGNode()
00247   // 
00248   if( LR->hasSuggestedColor() ) {
00249     if( ! IsColorUsedArr[ LR->getSuggestedColor() ] ) {
00250       LR->setColor(  LR->getSuggestedColor() );
00251       return;
00252     } else if (DEBUG_RA)  {                 // can't allocate the suggested col
00253       std::cerr << " Could NOT allocate the suggested color for LR " << *LR
00254                 << "\n";
00255     }
00256   }
00257 
00258 
00259   int ColorFound = -1;               // have we found a color yet?
00260   bool isCallInterf = LR->isCallInterference();
00261 
00262   // if value is a double - search the double only region (f32 - f63)
00263   // i.e. we try to allocate f32 - f63 first for doubles since singles
00264   // cannot go there. By doing that, we provide more space for singles
00265   // in f0 - f31
00266   //
00267   if (LR->getType() == Type::DoubleTy)       
00268     ColorFound = findFloatColor( LR, 32, 64, IsColorUsedArr );
00269 
00270   if (ColorFound >= 0) {               // if we could find a color
00271     LR->setColor(ColorFound);                
00272     return;
00273   } else { 
00274 
00275     // if we didn't find a color because the LR was single precision or
00276     // all f32-f63 range is filled, we try to allocate a register from
00277     // the f0 - f31 region 
00278 
00279     unsigned SearchStart;                 // start pos of color in pref-order
00280 
00281     //if this Node is between calls (i.e., no call interferences )
00282     if (! isCallInterf) {
00283       // start with volatiles (we can  allocate volatiles safely)
00284       SearchStart = SparcV9FloatRegClass::StartOfAllRegs;  
00285     } else {
00286       // start with non volatiles (no non-volatiles)
00287       SearchStart =  SparcV9FloatRegClass::StartOfNonVolatileRegs;  
00288     }
00289     
00290     ColorFound = findFloatColor(LR, SearchStart, 32, IsColorUsedArr);
00291   }
00292 
00293   if (ColorFound >= 0) {               // if we could find a color
00294     LR->setColor(ColorFound);                  
00295     return;
00296   } else if (isCallInterf) { 
00297     // We are here because there is a call interference and no non-volatile
00298     // color could be found.
00299     // Now try to allocate even a volatile color
00300     ColorFound = findFloatColor(LR, SparcV9FloatRegClass::StartOfAllRegs, 
00301         SparcV9FloatRegClass::StartOfNonVolatileRegs,
00302         IsColorUsedArr);
00303   }
00304 
00305   if (ColorFound >= 0) {
00306     LR->setColor(ColorFound);         // first color found in preferred order
00307   } else {
00308     // we are here because no color could be found
00309     LR->markForSpill();               // no color found - must spill
00310   }
00311 }
00312 
00313 //-----------------------------------------------------------------------------
00314 // This method marks the registers used for a given register number.
00315 // This marks a single register for Float regs, but the R,R+1 pair
00316 // for double-precision registers.
00317 //-----------------------------------------------------------------------------
00318 
00319 void SparcV9FloatRegClass::markColorsUsed(unsigned RegInClass,
00320                                         int UserRegType,
00321                                         int RegTypeWanted,
00322                                     std::vector<bool> &IsColorUsedArr) const
00323 {
00324   if (UserRegType == SparcV9RegInfo::FPDoubleRegType ||
00325       RegTypeWanted == SparcV9RegInfo::FPDoubleRegType) {
00326     // This register is used as or is needed as a double-precision reg.
00327     // We need to mark the [even,odd] pair corresponding to this reg.
00328     // Get the even numbered register corresponding to this reg.
00329     unsigned EvenRegInClass = RegInClass & ~1u;
00330     assert(EvenRegInClass+1 < NumOfAllRegs &&
00331            EvenRegInClass+1 < IsColorUsedArr.size());
00332     IsColorUsedArr[EvenRegInClass]   = true;
00333     IsColorUsedArr[EvenRegInClass+1] = true;
00334   }
00335   else {
00336     assert(RegInClass < NumOfAllRegs && RegInClass < IsColorUsedArr.size());
00337     assert(UserRegType == RegTypeWanted
00338            && "Something other than FP single/double types share a reg class?");
00339     IsColorUsedArr[RegInClass] = true;
00340   }
00341 }
00342 
00343 // This method finds unused registers of the specified register type,
00344 // using the given "used" flag array IsColorUsedArr.  It checks a single
00345 // entry in the array directly for float regs, and checks the pair [R,R+1]
00346 // for double-precision registers
00347 // It returns -1 if no unused color is found.
00348 // 
00349 int SparcV9FloatRegClass::findUnusedColor(int RegTypeWanted,
00350                                 const std::vector<bool> &IsColorUsedArr) const
00351 {
00352   if (RegTypeWanted == SparcV9RegInfo::FPDoubleRegType) {
00353     unsigned NC = 2 * this->getNumOfAvailRegs();
00354     assert(IsColorUsedArr.size() == NC && "Invalid colors-used array");
00355     for (unsigned c = 0; c < NC; c+=2)
00356       if (!IsColorUsedArr[c]) {
00357         assert(!IsColorUsedArr[c+1] && "Incorrect used regs for FP double!");
00358   return c;
00359       }
00360     return -1;
00361   }
00362   else
00363     return TargetRegClassInfo::findUnusedColor(RegTypeWanted, IsColorUsedArr);
00364 }
00365 
00366 //-----------------------------------------------------------------------------
00367 // Helper method for coloring a node of Float Reg class.
00368 // Finds the first available color in the range [Start,End] depending on the
00369 // type of the Node (i.e., float/double)
00370 //-----------------------------------------------------------------------------
00371 
00372 int SparcV9FloatRegClass::findFloatColor(const LiveRange *LR, 
00373                                        unsigned Start,
00374                                        unsigned End, 
00375                                const std::vector<bool> &IsColorUsedArr) const
00376 {
00377   if (LR->getType() == Type::DoubleTy) { 
00378     // find first unused color for a double 
00379     assert(Start % 2 == 0 && "Odd register number could be used for double!");
00380     for (unsigned c=Start; c < End ; c+= 2)
00381       if (!IsColorUsedArr[c]) {
00382         assert(!IsColorUsedArr[c+1] &&
00383                "Incorrect marking of used regs for SparcV9 FP double!");
00384   return c;
00385       }
00386   } else {
00387     // find first unused color for a single
00388     for (unsigned c = Start; c < End; c++)
00389       if (!IsColorUsedArr[c])
00390         return c;
00391   }
00392 
00393   return -1;
00394 
00395 }
00396 
00397 } // End llvm namespace