LLVM API Documentation
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