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