LLVM API Documentation
00001 //===-- LiveRangeInfo.cpp -------------------------------------------------===// 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 // Live range construction for coloring-based register allocation for LLVM. 00011 // 00012 //===----------------------------------------------------------------------===// 00013 00014 #include "IGNode.h" 00015 #include "LiveRangeInfo.h" 00016 #include "RegAllocCommon.h" 00017 #include "RegClass.h" 00018 #include "llvm/Function.h" 00019 #include "llvm/CodeGen/MachineInstr.h" 00020 #include "llvm/CodeGen/MachineFunction.h" 00021 #include "llvm/Target/TargetMachine.h" 00022 #include "llvm/Target/TargetInstrInfo.h" 00023 #include "../SparcV9RegInfo.h" 00024 #include "llvm/ADT/SetOperations.h" 00025 #include <iostream> 00026 00027 namespace llvm { 00028 00029 unsigned LiveRange::getRegClassID() const { return getRegClass()->getID(); } 00030 00031 LiveRangeInfo::LiveRangeInfo(const Function *F, const TargetMachine &tm, 00032 std::vector<RegClass *> &RCL) 00033 : Meth(F), TM(tm), RegClassList(RCL), MRI(*tm.getRegInfo()) { } 00034 00035 00036 LiveRangeInfo::~LiveRangeInfo() { 00037 for (LiveRangeMapType::iterator MI = LiveRangeMap.begin(); 00038 MI != LiveRangeMap.end(); ++MI) { 00039 00040 if (MI->first && MI->second) { 00041 LiveRange *LR = MI->second; 00042 00043 // we need to be careful in deleting LiveRanges in LiveRangeMap 00044 // since two/more Values in the live range map can point to the same 00045 // live range. We have to make the other entries NULL when we delete 00046 // a live range. 00047 00048 for (LiveRange::iterator LI = LR->begin(); LI != LR->end(); ++LI) 00049 LiveRangeMap[*LI] = 0; 00050 00051 delete LR; 00052 } 00053 } 00054 } 00055 00056 00057 //--------------------------------------------------------------------------- 00058 // union two live ranges into one. The 2nd LR is deleted. Used for coalescing. 00059 // Note: the caller must make sure that L1 and L2 are distinct and both 00060 // LRs don't have suggested colors 00061 //--------------------------------------------------------------------------- 00062 00063 void LiveRangeInfo::unionAndUpdateLRs(LiveRange *L1, LiveRange *L2) { 00064 assert(L1 != L2 && (!L1->hasSuggestedColor() || !L2->hasSuggestedColor())); 00065 assert(! (L1->hasColor() && L2->hasColor()) || 00066 L1->getColor() == L2->getColor()); 00067 00068 L2->insert (L1->begin(), L1->end()); // add elements of L2 to L1 00069 00070 for(LiveRange::iterator L2It = L2->begin(); L2It != L2->end(); ++L2It) { 00071 L1->insert(*L2It); // add the var in L2 to L1 00072 LiveRangeMap[*L2It] = L1; // now the elements in L2 should map 00073 //to L1 00074 } 00075 00076 // set call interference for L1 from L2 00077 if (L2->isCallInterference()) 00078 L1->setCallInterference(); 00079 00080 // add the spill costs 00081 L1->addSpillCost(L2->getSpillCost()); 00082 00083 // If L2 has a color, give L1 that color. Note that L1 may have had the same 00084 // color or none, but would not have a different color as asserted above. 00085 if (L2->hasColor()) 00086 L1->setColor(L2->getColor()); 00087 00088 // Similarly, if LROfUse(L2) has a suggested color, the new range 00089 // must have the same color. 00090 if (L2->hasSuggestedColor()) 00091 L1->setSuggestedColor(L2->getSuggestedColor()); 00092 00093 delete L2; // delete L2 as it is no longer needed 00094 } 00095 00096 00097 //--------------------------------------------------------------------------- 00098 // Method for creating a single live range for a definition. 00099 // The definition must be represented by a virtual register (a Value). 00100 // Note: this function does *not* check that no live range exists for def. 00101 //--------------------------------------------------------------------------- 00102 00103 LiveRange* 00104 LiveRangeInfo::createNewLiveRange(const Value* Def, bool isCC /* = false*/) 00105 { 00106 LiveRange* DefRange = new LiveRange(); // Create a new live range, 00107 DefRange->insert(Def); // add Def to it, 00108 LiveRangeMap[Def] = DefRange; // and update the map. 00109 00110 // set the register class of the new live range 00111 DefRange->setRegClass(RegClassList[MRI.getRegClassIDOfType(Def->getType(), 00112 isCC)]); 00113 00114 if (DEBUG_RA >= RA_DEBUG_LiveRanges) { 00115 std::cerr << " Creating a LR for def "; 00116 if (isCC) std::cerr << " (CC Register!)"; 00117 std::cerr << " : " << RAV(Def) << "\n"; 00118 } 00119 return DefRange; 00120 } 00121 00122 00123 LiveRange* 00124 LiveRangeInfo::createOrAddToLiveRange(const Value* Def, bool isCC /* = false*/) 00125 { 00126 LiveRange *DefRange = LiveRangeMap[Def]; 00127 00128 // check if the LR is already there (because of multiple defs) 00129 if (!DefRange) { 00130 DefRange = createNewLiveRange(Def, isCC); 00131 } else { // live range already exists 00132 DefRange->insert(Def); // add the operand to the range 00133 LiveRangeMap[Def] = DefRange; // make operand point to merged set 00134 if (DEBUG_RA >= RA_DEBUG_LiveRanges) 00135 std::cerr << " Added to existing LR for def: " << RAV(Def) << "\n"; 00136 } 00137 return DefRange; 00138 } 00139 00140 00141 //--------------------------------------------------------------------------- 00142 // Method for constructing all live ranges in a function. It creates live 00143 // ranges for all values defined in the instruction stream. Also, it 00144 // creates live ranges for all incoming arguments of the function. 00145 //--------------------------------------------------------------------------- 00146 void LiveRangeInfo::constructLiveRanges() { 00147 00148 if (DEBUG_RA >= RA_DEBUG_LiveRanges) 00149 std::cerr << "Constructing Live Ranges ...\n"; 00150 00151 // first find the live ranges for all incoming args of the function since 00152 // those LRs start from the start of the function 00153 for (Function::const_aiterator AI = Meth->abegin(); AI != Meth->aend(); ++AI) 00154 createNewLiveRange(AI, /*isCC*/ false); 00155 00156 // Now suggest hardware registers for these function args 00157 MRI.suggestRegs4MethodArgs(Meth, *this); 00158 00159 // Now create LRs for machine instructions. A new LR will be created 00160 // only for defs in the machine instr since, we assume that all Values are 00161 // defined before they are used. However, there can be multiple defs for 00162 // the same Value in machine instructions. 00163 // 00164 // Also, find CALL and RETURN instructions, which need extra work. 00165 // 00166 MachineFunction &MF = MachineFunction::get(Meth); 00167 for (MachineFunction::iterator BBI = MF.begin(); BBI != MF.end(); ++BBI) { 00168 MachineBasicBlock &MBB = *BBI; 00169 00170 // iterate over all the machine instructions in BB 00171 for(MachineBasicBlock::iterator MInstIterator = MBB.begin(); 00172 MInstIterator != MBB.end(); ++MInstIterator) { 00173 MachineInstr *MInst = MInstIterator; 00174 00175 // If the machine instruction is a call/return instruction, add it to 00176 // CallRetInstrList for processing its args, ret value, and ret addr. 00177 // 00178 if(TM.getInstrInfo()->isReturn(MInst->getOpcode()) || 00179 TM.getInstrInfo()->isCall(MInst->getOpcode())) 00180 CallRetInstrList.push_back(MInst); 00181 00182 // iterate over explicit MI operands and create a new LR 00183 // for each operand that is defined by the instruction 00184 for (MachineInstr::val_op_iterator OpI = MInst->begin(), 00185 OpE = MInst->end(); OpI != OpE; ++OpI) 00186 if (OpI.isDef()) { 00187 const Value *Def = *OpI; 00188 bool isCC = (OpI.getMachineOperand().getType() 00189 == MachineOperand::MO_CCRegister); 00190 LiveRange* LR = createOrAddToLiveRange(Def, isCC); 00191 00192 // If the operand has a pre-assigned register, 00193 // set it directly in the LiveRange 00194 if (OpI.getMachineOperand().hasAllocatedReg()) { 00195 unsigned getClassId; 00196 LR->setColor(MRI.getClassRegNum(OpI.getMachineOperand().getReg(), 00197 getClassId)); 00198 } 00199 } 00200 00201 // iterate over implicit MI operands and create a new LR 00202 // for each operand that is defined by the instruction 00203 for (unsigned i = 0; i < MInst->getNumImplicitRefs(); ++i) 00204 if (MInst->getImplicitOp(i).isDef()) { 00205 const Value *Def = MInst->getImplicitRef(i); 00206 LiveRange* LR = createOrAddToLiveRange(Def, /*isCC*/ false); 00207 00208 // If the implicit operand has a pre-assigned register, 00209 // set it directly in the LiveRange 00210 if (MInst->getImplicitOp(i).hasAllocatedReg()) { 00211 unsigned getClassId; 00212 LR->setColor(MRI.getClassRegNum( 00213 MInst->getImplicitOp(i).getReg(), 00214 getClassId)); 00215 } 00216 } 00217 00218 } // for all machine instructions in the BB 00219 } // for all BBs in function 00220 00221 // Now we have to suggest clors for call and return arg live ranges. 00222 // Also, if there are implicit defs (e.g., retun value of a call inst) 00223 // they must be added to the live range list 00224 // 00225 suggestRegs4CallRets(); 00226 00227 if( DEBUG_RA >= RA_DEBUG_LiveRanges) 00228 std::cerr << "Initial Live Ranges constructed!\n"; 00229 } 00230 00231 00232 //--------------------------------------------------------------------------- 00233 // If some live ranges must be colored with specific hardware registers 00234 // (e.g., for outgoing call args), suggesting of colors for such live 00235 // ranges is done using target specific function. Those functions are called 00236 // from this function. The target specific methods must: 00237 // 1) suggest colors for call and return args. 00238 // 2) create new LRs for implicit defs in machine instructions 00239 //--------------------------------------------------------------------------- 00240 void LiveRangeInfo::suggestRegs4CallRets() { 00241 std::vector<MachineInstr*>::iterator It = CallRetInstrList.begin(); 00242 for( ; It != CallRetInstrList.end(); ++It) { 00243 MachineInstr *MInst = *It; 00244 MachineOpCode OpCode = MInst->getOpcode(); 00245 00246 if (TM.getInstrInfo()->isReturn(OpCode)) 00247 MRI.suggestReg4RetValue(MInst, *this); 00248 else if (TM.getInstrInfo()->isCall(OpCode)) 00249 MRI.suggestRegs4CallArgs(MInst, *this); 00250 else 00251 assert( 0 && "Non call/ret instr in CallRetInstrList" ); 00252 } 00253 } 00254 00255 00256 //-------------------------------------------------------------------------- 00257 // The following method coalesces live ranges when possible. This method 00258 // must be called after the interference graph has been constructed. 00259 00260 00261 /* Algorithm: 00262 for each BB in function 00263 for each machine instruction (inst) 00264 for each definition (def) in inst 00265 for each operand (op) of inst that is a use 00266 if the def and op are of the same register type 00267 if the def and op do not interfere //i.e., not simultaneously live 00268 if (degree(LR of def) + degree(LR of op)) <= # avail regs 00269 if both LRs do not have suggested colors 00270 merge2IGNodes(def, op) // i.e., merge 2 LRs 00271 00272 */ 00273 //--------------------------------------------------------------------------- 00274 00275 00276 // Checks if live range LR interferes with any node assigned or suggested to 00277 // be assigned the specified color 00278 // 00279 inline bool InterferesWithColor(const LiveRange& LR, unsigned color) { 00280 IGNode* lrNode = LR.getUserIGNode(); 00281 for (unsigned n=0, NN = lrNode->getNumOfNeighbors(); n < NN; n++) { 00282 LiveRange *neighLR = lrNode->getAdjIGNode(n)->getParentLR(); 00283 if (neighLR->hasColor() && neighLR->getColor() == color) 00284 return true; 00285 if (neighLR->hasSuggestedColor() && neighLR->getSuggestedColor() == color) 00286 return true; 00287 } 00288 return false; 00289 } 00290 00291 // Cannot coalesce if any of the following is true: 00292 // (1) Both LRs have suggested colors (should be "different suggested colors"?) 00293 // (2) Both LR1 and LR2 have colors and the colors are different 00294 // (but if the colors are the same, it is definitely safe to coalesce) 00295 // (3) LR1 has color and LR2 interferes with any LR that has the same color 00296 // (4) LR2 has color and LR1 interferes with any LR that has the same color 00297 // 00298 inline bool InterfsPreventCoalescing(const LiveRange& LROfDef, 00299 const LiveRange& LROfUse) { 00300 // (4) if they have different suggested colors, cannot coalesce 00301 if (LROfDef.hasSuggestedColor() && LROfUse.hasSuggestedColor()) 00302 return true; 00303 00304 // if neither has a color, nothing more to do. 00305 if (! LROfDef.hasColor() && ! LROfUse.hasColor()) 00306 return false; 00307 00308 // (2, 3) if L1 has color... 00309 if (LROfDef.hasColor()) { 00310 if (LROfUse.hasColor()) 00311 return (LROfUse.getColor() != LROfDef.getColor()); 00312 return InterferesWithColor(LROfUse, LROfDef.getColor()); 00313 } 00314 00315 // (4) else only LROfUse has a color: check if that could interfere 00316 return InterferesWithColor(LROfDef, LROfUse.getColor()); 00317 } 00318 00319 00320 void LiveRangeInfo::coalesceLRs() 00321 { 00322 if(DEBUG_RA >= RA_DEBUG_LiveRanges) 00323 std::cerr << "\nCoalescing LRs ...\n"; 00324 00325 MachineFunction &MF = MachineFunction::get(Meth); 00326 for (MachineFunction::iterator BBI = MF.begin(); BBI != MF.end(); ++BBI) { 00327 MachineBasicBlock &MBB = *BBI; 00328 00329 // iterate over all the machine instructions in BB 00330 for(MachineBasicBlock::iterator MII = MBB.begin(); MII != MBB.end(); ++MII){ 00331 const MachineInstr *MI = MII; 00332 00333 if( DEBUG_RA >= RA_DEBUG_LiveRanges) { 00334 std::cerr << " *Iterating over machine instr "; 00335 MI->dump(); 00336 std::cerr << "\n"; 00337 } 00338 00339 // iterate over MI operands to find defs 00340 for(MachineInstr::const_val_op_iterator DefI = MI->begin(), 00341 DefE = MI->end(); DefI != DefE; ++DefI) { 00342 if (DefI.isDef()) { // this operand is modified 00343 LiveRange *LROfDef = getLiveRangeForValue( *DefI ); 00344 RegClass *RCOfDef = LROfDef->getRegClass(); 00345 00346 MachineInstr::const_val_op_iterator UseI = MI->begin(), 00347 UseE = MI->end(); 00348 for( ; UseI != UseE; ++UseI) { // for all uses 00349 LiveRange *LROfUse = getLiveRangeForValue( *UseI ); 00350 if (!LROfUse) { // if LR of use is not found 00351 //don't warn about labels 00352 if (!isa<BasicBlock>(*UseI) && DEBUG_RA >= RA_DEBUG_LiveRanges) 00353 std::cerr << " !! Warning: No LR for use " << RAV(*UseI)<< "\n"; 00354 continue; // ignore and continue 00355 } 00356 00357 if (LROfUse == LROfDef) // nothing to merge if they are same 00358 continue; 00359 00360 if (MRI.getRegTypeForLR(LROfDef) == 00361 MRI.getRegTypeForLR(LROfUse)) { 00362 // If the two RegTypes are the same 00363 if (!RCOfDef->getInterference(LROfDef, LROfUse) ) { 00364 00365 unsigned CombinedDegree = 00366 LROfDef->getUserIGNode()->getNumOfNeighbors() + 00367 LROfUse->getUserIGNode()->getNumOfNeighbors(); 00368 00369 if (CombinedDegree > RCOfDef->getNumOfAvailRegs()) { 00370 // get more precise estimate of combined degree 00371 CombinedDegree = LROfDef->getUserIGNode()-> 00372 getCombinedDegree(LROfUse->getUserIGNode()); 00373 } 00374 00375 if (CombinedDegree <= RCOfDef->getNumOfAvailRegs()) { 00376 // if both LRs do not have different pre-assigned colors 00377 // and both LRs do not have suggested colors 00378 if (! InterfsPreventCoalescing(*LROfDef, *LROfUse)) { 00379 RCOfDef->mergeIGNodesOfLRs(LROfDef, LROfUse); 00380 unionAndUpdateLRs(LROfDef, LROfUse); 00381 } 00382 00383 } // if combined degree is less than # of regs 00384 } // if def and use do not interfere 00385 }// if reg classes are the same 00386 } // for all uses 00387 } // if def 00388 } // for all defs 00389 } // for all machine instructions 00390 } // for all BBs 00391 00392 if (DEBUG_RA >= RA_DEBUG_LiveRanges) 00393 std::cerr << "\nCoalescing Done!\n"; 00394 } 00395 00396 /*--------------------------- Debug code for printing ---------------*/ 00397 00398 00399 void LiveRangeInfo::printLiveRanges() { 00400 LiveRangeMapType::iterator HMI = LiveRangeMap.begin(); // hash map iterator 00401 std::cerr << "\nPrinting Live Ranges from Hash Map:\n"; 00402 for( ; HMI != LiveRangeMap.end(); ++HMI) { 00403 if (HMI->first && HMI->second) { 00404 std::cerr << " Value* " << RAV(HMI->first) << "\t: "; 00405 if (IGNode* igNode = HMI->second->getUserIGNode()) 00406 std::cerr << "LR# " << igNode->getIndex(); 00407 else 00408 std::cerr << "LR# " << "<no-IGNode>"; 00409 std::cerr << "\t:Values = " << *HMI->second << "\n"; 00410 } 00411 } 00412 } 00413 00414 } // End llvm namespace