LLVM API Documentation
00001 //===-- PhyRegAlloc.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 // Traditional graph-coloring global register allocator currently used 00011 // by the SPARC back-end. 00012 // 00013 // NOTE: This register allocator has some special support 00014 // for the Reoptimizer, such as not saving some registers on calls to 00015 // the first-level instrumentation function. 00016 // 00017 // NOTE 2: This register allocator can save its state in a global 00018 // variable in the module it's working on. This feature is not 00019 // thread-safe; if you have doubts, leave it turned off. 00020 // 00021 //===----------------------------------------------------------------------===// 00022 00023 #include "AllocInfo.h" 00024 #include "IGNode.h" 00025 #include "PhyRegAlloc.h" 00026 #include "RegAllocCommon.h" 00027 #include "RegClass.h" 00028 #include "../LiveVar/FunctionLiveVarInfo.h" 00029 #include "../MachineCodeForInstruction.h" 00030 #include "../MachineFunctionInfo.h" 00031 #include "../SparcV9InstrInfo.h" 00032 #include "../SparcV9TmpInstr.h" 00033 #include "llvm/Constants.h" 00034 #include "llvm/DerivedTypes.h" 00035 #include "llvm/Instructions.h" 00036 #include "llvm/Module.h" 00037 #include "llvm/Type.h" 00038 #include "llvm/Analysis/LoopInfo.h" 00039 #include "llvm/CodeGen/MachineFunction.h" 00040 #include "llvm/CodeGen/MachineInstr.h" 00041 #include "llvm/CodeGen/MachineInstrBuilder.h" 00042 #include "../MachineInstrAnnot.h" 00043 #include "llvm/CodeGen/Passes.h" 00044 #include "llvm/Support/InstIterator.h" 00045 #include "llvm/Target/TargetInstrInfo.h" 00046 #include "llvm/Support/CommandLine.h" 00047 #include "llvm/ADT/SetOperations.h" 00048 #include "llvm/ADT/STLExtras.h" 00049 #include <cmath> 00050 #include <iostream> 00051 00052 namespace llvm { 00053 00054 RegAllocDebugLevel_t DEBUG_RA; 00055 00056 static cl::opt<RegAllocDebugLevel_t, true> 00057 DRA_opt("dregalloc", cl::Hidden, cl::location(DEBUG_RA), 00058 cl::desc("enable register allocation debugging information"), 00059 cl::values( 00060 clEnumValN(RA_DEBUG_None , "n", "disable debug output"), 00061 clEnumValN(RA_DEBUG_Results, "y", "debug output for allocation results"), 00062 clEnumValN(RA_DEBUG_Coloring, "c", "debug output for graph coloring step"), 00063 clEnumValN(RA_DEBUG_Interference,"ig","debug output for interference graphs"), 00064 clEnumValN(RA_DEBUG_LiveRanges , "lr","debug output for live ranges"), 00065 clEnumValN(RA_DEBUG_Verbose, "v", "extra debug output"), 00066 clEnumValEnd)); 00067 00068 /// The reoptimizer wants to be able to grovel through the register 00069 /// allocator's state after it has done its job. This is a hack. 00070 /// 00071 PhyRegAlloc::SavedStateMapTy ExportedFnAllocState; 00072 bool SaveRegAllocState = false; 00073 bool SaveStateToModule = true; 00074 static cl::opt<bool, true> 00075 SaveRegAllocStateOpt("save-ra-state", cl::Hidden, 00076 cl::location (SaveRegAllocState), 00077 cl::init(false), 00078 cl::desc("write reg. allocator state into module")); 00079 00080 FunctionPass *getRegisterAllocator(TargetMachine &T) { 00081 return new PhyRegAlloc (T); 00082 } 00083 00084 void PhyRegAlloc::getAnalysisUsage(AnalysisUsage &AU) const { 00085 AU.addRequired<LoopInfo> (); 00086 AU.addRequired<FunctionLiveVarInfo> (); 00087 } 00088 00089 00090 /// Initialize interference graphs (one in each reg class) and IGNodeLists 00091 /// (one in each IG). The actual nodes will be pushed later. 00092 /// 00093 void PhyRegAlloc::createIGNodeListsAndIGs() { 00094 if (DEBUG_RA >= RA_DEBUG_LiveRanges) std::cerr << "Creating LR lists ...\n"; 00095 00096 LiveRangeMapType::const_iterator HMI = LRI->getLiveRangeMap()->begin(); 00097 LiveRangeMapType::const_iterator HMIEnd = LRI->getLiveRangeMap()->end(); 00098 00099 for (; HMI != HMIEnd ; ++HMI ) { 00100 if (HMI->first) { 00101 LiveRange *L = HMI->second; // get the LiveRange 00102 if (!L) { 00103 if (DEBUG_RA && !isa<ConstantIntegral> (HMI->first)) 00104 std::cerr << "\n**** ?!?WARNING: NULL LIVE RANGE FOUND FOR: " 00105 << RAV(HMI->first) << "****\n"; 00106 continue; 00107 } 00108 00109 // if the Value * is not null, and LR is not yet written to the IGNodeList 00110 if (!(L->getUserIGNode()) ) { 00111 RegClass *const RC = // RegClass of first value in the LR 00112 RegClassList[ L->getRegClassID() ]; 00113 RC->addLRToIG(L); // add this LR to an IG 00114 } 00115 } 00116 } 00117 00118 // init RegClassList 00119 for ( unsigned rc=0; rc < NumOfRegClasses ; rc++) 00120 RegClassList[rc]->createInterferenceGraph(); 00121 00122 if (DEBUG_RA >= RA_DEBUG_LiveRanges) std::cerr << "LRLists Created!\n"; 00123 } 00124 00125 00126 /// Add all interferences for a given instruction. Interference occurs only 00127 /// if the LR of Def (Inst or Arg) is of the same reg class as that of live 00128 /// var. The live var passed to this function is the LVset AFTER the 00129 /// instruction. 00130 /// 00131 void PhyRegAlloc::addInterference(const Value *Def, const ValueSet *LVSet, 00132 bool isCallInst) { 00133 ValueSet::const_iterator LIt = LVSet->begin(); 00134 00135 // get the live range of instruction 00136 const LiveRange *const LROfDef = LRI->getLiveRangeForValue( Def ); 00137 00138 IGNode *const IGNodeOfDef = LROfDef->getUserIGNode(); 00139 assert( IGNodeOfDef ); 00140 00141 RegClass *const RCOfDef = LROfDef->getRegClass(); 00142 00143 // for each live var in live variable set 00144 for ( ; LIt != LVSet->end(); ++LIt) { 00145 00146 if (DEBUG_RA >= RA_DEBUG_Verbose) 00147 std::cerr << "< Def=" << RAV(Def) << ", Lvar=" << RAV(*LIt) << "> "; 00148 00149 // get the live range corresponding to live var 00150 LiveRange *LROfVar = LRI->getLiveRangeForValue(*LIt); 00151 00152 // LROfVar can be null if it is a const since a const 00153 // doesn't have a dominating def - see Assumptions above 00154 if (LROfVar) 00155 if (LROfDef != LROfVar) // do not set interf for same LR 00156 if (RCOfDef == LROfVar->getRegClass()) // 2 reg classes are the same 00157 RCOfDef->setInterference( LROfDef, LROfVar); 00158 } 00159 } 00160 00161 00162 /// For a call instruction, this method sets the CallInterference flag in 00163 /// the LR of each variable live in the Live Variable Set live after the 00164 /// call instruction (except the return value of the call instruction - since 00165 /// the return value does not interfere with that call itself). 00166 /// 00167 void PhyRegAlloc::setCallInterferences(const MachineInstr *MInst, 00168 const ValueSet *LVSetAft) { 00169 if (DEBUG_RA >= RA_DEBUG_Interference) 00170 std::cerr << "\n For call inst: " << *MInst; 00171 00172 // for each live var in live variable set after machine inst 00173 for (ValueSet::const_iterator LIt = LVSetAft->begin(), LEnd = LVSetAft->end(); 00174 LIt != LEnd; ++LIt) { 00175 00176 // get the live range corresponding to live var 00177 LiveRange *const LR = LRI->getLiveRangeForValue(*LIt); 00178 00179 // LR can be null if it is a const since a const 00180 // doesn't have a dominating def - see Assumptions above 00181 if (LR) { 00182 if (DEBUG_RA >= RA_DEBUG_Interference) 00183 std::cerr << "\n\tLR after Call: " << *LR << "\n"; 00184 LR->setCallInterference(); 00185 if (DEBUG_RA >= RA_DEBUG_Interference) 00186 std::cerr << "\n ++After adding call interference for LR: " << *LR << "\n"; 00187 } 00188 } 00189 00190 // Now find the LR of the return value of the call 00191 // We do this because, we look at the LV set *after* the instruction 00192 // to determine, which LRs must be saved across calls. The return value 00193 // of the call is live in this set - but it does not interfere with call 00194 // (i.e., we can allocate a volatile register to the return value) 00195 CallArgsDescriptor* argDesc = CallArgsDescriptor::get(MInst); 00196 00197 if (const Value *RetVal = argDesc->getReturnValue()) { 00198 LiveRange *RetValLR = LRI->getLiveRangeForValue( RetVal ); 00199 assert( RetValLR && "No LR for RetValue of call"); 00200 RetValLR->clearCallInterference(); 00201 } 00202 00203 // If the CALL is an indirect call, find the LR of the function pointer. 00204 // That has a call interference because it conflicts with outgoing args. 00205 if (const Value *AddrVal = argDesc->getIndirectFuncPtr()) { 00206 LiveRange *AddrValLR = LRI->getLiveRangeForValue( AddrVal ); 00207 // LR can be null if the function pointer is a constant. 00208 if (AddrValLR) 00209 AddrValLR->setCallInterference(); 00210 } 00211 } 00212 00213 00214 /// Create interferences in the IG of each RegClass, and calculate the spill 00215 /// cost of each Live Range (it is done in this method to save another pass 00216 /// over the code). 00217 /// 00218 void PhyRegAlloc::buildInterferenceGraphs() { 00219 if (DEBUG_RA >= RA_DEBUG_Interference) 00220 std::cerr << "Creating interference graphs ...\n"; 00221 00222 unsigned BBLoopDepthCost; 00223 for (MachineFunction::iterator BBI = MF->begin(), BBE = MF->end(); 00224 BBI != BBE; ++BBI) { 00225 const MachineBasicBlock &MBB = *BBI; 00226 const BasicBlock *BB = MBB.getBasicBlock(); 00227 00228 // find the 10^(loop_depth) of this BB 00229 BBLoopDepthCost = (unsigned)pow(10.0, LoopDepthCalc->getLoopDepth(BB)); 00230 00231 // get the iterator for machine instructions 00232 MachineBasicBlock::const_iterator MII = MBB.begin(); 00233 00234 // iterate over all the machine instructions in BB 00235 for ( ; MII != MBB.end(); ++MII) { 00236 const MachineInstr *MInst = MII; 00237 00238 // get the LV set after the instruction 00239 const ValueSet &LVSetAI = LVI->getLiveVarSetAfterMInst(MInst, BB); 00240 bool isCallInst = TM.getInstrInfo()->isCall(MInst->getOpcode()); 00241 00242 if (isCallInst) { 00243 // set the isCallInterference flag of each live range which extends 00244 // across this call instruction. This information is used by graph 00245 // coloring algorithm to avoid allocating volatile colors to live ranges 00246 // that span across calls (since they have to be saved/restored) 00247 setCallInterferences(MInst, &LVSetAI); 00248 } 00249 00250 // iterate over all MI operands to find defs 00251 for (MachineInstr::const_val_op_iterator OpI = MInst->begin(), 00252 OpE = MInst->end(); OpI != OpE; ++OpI) { 00253 if (OpI.isDef()) // create a new LR since def 00254 addInterference(*OpI, &LVSetAI, isCallInst); 00255 00256 // Calculate the spill cost of each live range 00257 LiveRange *LR = LRI->getLiveRangeForValue(*OpI); 00258 if (LR) LR->addSpillCost(BBLoopDepthCost); 00259 } 00260 // Also add interference for any implicit definitions in a machine 00261 // instr (currently, only calls have this). 00262 unsigned NumOfImpRefs = MInst->getNumImplicitRefs(); 00263 for (unsigned z=0; z < NumOfImpRefs; z++) 00264 if (MInst->getImplicitOp(z).isDef()) 00265 addInterference( MInst->getImplicitRef(z), &LVSetAI, isCallInst ); 00266 } // for all machine instructions in BB 00267 } // for all BBs in function 00268 00269 // add interferences for function arguments. Since there are no explicit 00270 // defs in the function for args, we have to add them manually 00271 addInterferencesForArgs(); 00272 00273 if (DEBUG_RA >= RA_DEBUG_Interference) 00274 std::cerr << "Interference graphs calculated!\n"; 00275 } 00276 00277 00278 /// Mark all operands of the given MachineInstr as interfering with one 00279 /// another. 00280 /// 00281 void PhyRegAlloc::addInterf4PseudoInstr(const MachineInstr *MInst) { 00282 bool setInterf = false; 00283 00284 // iterate over MI operands to find defs 00285 for (MachineInstr::const_val_op_iterator It1 = MInst->begin(), 00286 ItE = MInst->end(); It1 != ItE; ++It1) { 00287 const LiveRange *LROfOp1 = LRI->getLiveRangeForValue(*It1); 00288 assert((LROfOp1 || It1.isDef()) && "No LR for Def in PSEUDO insruction"); 00289 00290 MachineInstr::const_val_op_iterator It2 = It1; 00291 for (++It2; It2 != ItE; ++It2) { 00292 const LiveRange *LROfOp2 = LRI->getLiveRangeForValue(*It2); 00293 00294 if (LROfOp2) { 00295 RegClass *RCOfOp1 = LROfOp1->getRegClass(); 00296 RegClass *RCOfOp2 = LROfOp2->getRegClass(); 00297 00298 if (RCOfOp1 == RCOfOp2 ){ 00299 RCOfOp1->setInterference( LROfOp1, LROfOp2 ); 00300 setInterf = true; 00301 } 00302 } // if Op2 has a LR 00303 } // for all other defs in machine instr 00304 } // for all operands in an instruction 00305 00306 if (!setInterf && MInst->getNumOperands() > 2) { 00307 std::cerr << "\nInterf not set for any operand in pseudo instr:\n"; 00308 std::cerr << *MInst; 00309 assert(0 && "Interf not set for pseudo instr with > 2 operands" ); 00310 } 00311 } 00312 00313 00314 /// Add interferences for incoming arguments to a function. 00315 /// 00316 void PhyRegAlloc::addInterferencesForArgs() { 00317 // get the InSet of root BB 00318 const ValueSet &InSet = LVI->getInSetOfBB(&Fn->front()); 00319 00320 for (Function::const_aiterator AI = Fn->abegin(); AI != Fn->aend(); ++AI) { 00321 // add interferences between args and LVars at start 00322 addInterference(AI, &InSet, false); 00323 00324 if (DEBUG_RA >= RA_DEBUG_Interference) 00325 std::cerr << " - %% adding interference for argument " << RAV(AI) << "\n"; 00326 } 00327 } 00328 00329 00330 /// The following are utility functions used solely by updateMachineCode and 00331 /// the functions that it calls. They should probably be folded back into 00332 /// updateMachineCode at some point. 00333 /// 00334 00335 // used by: updateMachineCode (1 time), PrependInstructions (1 time) 00336 inline void InsertBefore(MachineInstr* newMI, MachineBasicBlock& MBB, 00337 MachineBasicBlock::iterator& MII) { 00338 MII = MBB.insert(MII, newMI); 00339 ++MII; 00340 } 00341 00342 // used by: AppendInstructions (1 time) 00343 inline void InsertAfter(MachineInstr* newMI, MachineBasicBlock& MBB, 00344 MachineBasicBlock::iterator& MII) { 00345 ++MII; // insert before the next instruction 00346 MII = MBB.insert(MII, newMI); 00347 } 00348 00349 // used by: updateMachineCode (2 times) 00350 inline void PrependInstructions(std::vector<MachineInstr *> &IBef, 00351 MachineBasicBlock& MBB, 00352 MachineBasicBlock::iterator& MII, 00353 const std::string& msg) { 00354 if (!IBef.empty()) { 00355 MachineInstr* OrigMI = MII; 00356 std::vector<MachineInstr *>::iterator AdIt; 00357 for (AdIt = IBef.begin(); AdIt != IBef.end() ; ++AdIt) { 00358 if (DEBUG_RA) { 00359 if (OrigMI) std::cerr << "For MInst:\n " << *OrigMI; 00360 std::cerr << msg << "PREPENDed instr:\n " << **AdIt << "\n"; 00361 } 00362 InsertBefore(*AdIt, MBB, MII); 00363 } 00364 } 00365 } 00366 00367 // used by: updateMachineCode (1 time) 00368 inline void AppendInstructions(std::vector<MachineInstr *> &IAft, 00369 MachineBasicBlock& MBB, 00370 MachineBasicBlock::iterator& MII, 00371 const std::string& msg) { 00372 if (!IAft.empty()) { 00373 MachineInstr* OrigMI = MII; 00374 std::vector<MachineInstr *>::iterator AdIt; 00375 for ( AdIt = IAft.begin(); AdIt != IAft.end() ; ++AdIt ) { 00376 if (DEBUG_RA) { 00377 if (OrigMI) std::cerr << "For MInst:\n " << *OrigMI; 00378 std::cerr << msg << "APPENDed instr:\n " << **AdIt << "\n"; 00379 } 00380 InsertAfter(*AdIt, MBB, MII); 00381 } 00382 } 00383 } 00384 00385 /// Set the registers for operands in the given MachineInstr, if a register was 00386 /// successfully allocated. Return true if any of its operands has been marked 00387 /// for spill. 00388 /// 00389 bool PhyRegAlloc::markAllocatedRegs(MachineInstr* MInst) 00390 { 00391 bool instrNeedsSpills = false; 00392 00393 // First, set the registers for operands in the machine instruction 00394 // if a register was successfully allocated. Do this first because we 00395 // will need to know which registers are already used by this instr'n. 00396 for (unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum) { 00397 MachineOperand& Op = MInst->getOperand(OpNum); 00398 if (Op.getType() == MachineOperand::MO_VirtualRegister || 00399 Op.getType() == MachineOperand::MO_CCRegister) { 00400 const Value *const Val = Op.getVRegValue(); 00401 if (const LiveRange* LR = LRI->getLiveRangeForValue(Val)) { 00402 // Remember if any operand needs spilling 00403 instrNeedsSpills |= LR->isMarkedForSpill(); 00404 00405 // An operand may have a color whether or not it needs spilling 00406 if (LR->hasColor()) 00407 MInst->SetRegForOperand(OpNum, 00408 MRI.getUnifiedRegNum(LR->getRegClassID(), 00409 LR->getColor())); 00410 } 00411 } 00412 } // for each operand 00413 00414 return instrNeedsSpills; 00415 } 00416 00417 /// Mark allocated registers (using markAllocatedRegs()) on the instruction 00418 /// that MII points to. Then, if it's a call instruction, insert caller-saving 00419 /// code before and after it. Finally, insert spill code before and after it, 00420 /// using insertCode4SpilledLR(). 00421 /// 00422 void PhyRegAlloc::updateInstruction(MachineBasicBlock::iterator& MII, 00423 MachineBasicBlock &MBB) { 00424 MachineInstr* MInst = MII; 00425 unsigned Opcode = MInst->getOpcode(); 00426 00427 // Reset tmp stack positions so they can be reused for each machine instr. 00428 MF->getInfo<SparcV9FunctionInfo>()->popAllTempValues(); 00429 00430 // Mark the operands for which regs have been allocated. 00431 bool instrNeedsSpills = markAllocatedRegs(MII); 00432 00433 #ifndef NDEBUG 00434 // Mark that the operands have been updated. Later, 00435 // setRelRegsUsedByThisInst() is called to find registers used by each 00436 // MachineInst, and it should not be used for an instruction until 00437 // this is done. This flag just serves as a sanity check. 00438 OperandsColoredMap[MInst] = true; 00439 #endif 00440 00441 // Now insert caller-saving code before/after the call. 00442 // Do this before inserting spill code since some registers must be 00443 // used by save/restore and spill code should not use those registers. 00444 if (TM.getInstrInfo()->isCall(Opcode)) { 00445 AddedInstrns &AI = AddedInstrMap[MInst]; 00446 insertCallerSavingCode(AI.InstrnsBefore, AI.InstrnsAfter, MInst, 00447 MBB.getBasicBlock()); 00448 } 00449 00450 // Now insert spill code for remaining operands not allocated to 00451 // registers. This must be done even for call return instructions 00452 // since those are not handled by the special code above. 00453 if (instrNeedsSpills) 00454 for (unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum) { 00455 MachineOperand& Op = MInst->getOperand(OpNum); 00456 if (Op.getType() == MachineOperand::MO_VirtualRegister || 00457 Op.getType() == MachineOperand::MO_CCRegister) { 00458 const Value* Val = Op.getVRegValue(); 00459 if (const LiveRange *LR = LRI->getLiveRangeForValue(Val)) 00460 if (LR->isMarkedForSpill()) 00461 insertCode4SpilledLR(LR, MII, MBB, OpNum); 00462 } 00463 } // for each operand 00464 } 00465 00466 /// Iterate over all the MachineBasicBlocks in the current function and set 00467 /// the allocated registers for each instruction (using updateInstruction()), 00468 /// after register allocation is complete. Then move code out of delay slots. 00469 /// 00470 void PhyRegAlloc::updateMachineCode() 00471 { 00472 // Insert any instructions needed at method entry 00473 MachineBasicBlock::iterator MII = MF->front().begin(); 00474 PrependInstructions(AddedInstrAtEntry.InstrnsBefore, MF->front(), MII, 00475 "At function entry: \n"); 00476 assert(AddedInstrAtEntry.InstrnsAfter.empty() && 00477 "InstrsAfter should be unnecessary since we are just inserting at " 00478 "the function entry point here."); 00479 00480 for (MachineFunction::iterator BBI = MF->begin(), BBE = MF->end(); 00481 BBI != BBE; ++BBI) { 00482 MachineBasicBlock &MBB = *BBI; 00483 00484 // Iterate over all machine instructions in BB and mark operands with 00485 // their assigned registers or insert spill code, as appropriate. 00486 // Also, fix operands of call/return instructions. 00487 for (MachineBasicBlock::iterator MII = MBB.begin(); MII != MBB.end(); ++MII) 00488 if (MII->getOpcode() != V9::PHI) 00489 updateInstruction(MII, MBB); 00490 00491 // Now, move code out of delay slots of branches and returns if needed. 00492 // (Also, move "after" code from calls to the last delay slot instruction.) 00493 // Moving code out of delay slots is needed in 2 situations: 00494 // (1) If this is a branch and it needs instructions inserted after it, 00495 // move any existing instructions out of the delay slot so that the 00496 // instructions can go into the delay slot. This only supports the 00497 // case that #instrsAfter <= #delay slots. 00498 // 00499 // (2) If any instruction in the delay slot needs 00500 // instructions inserted, move it out of the delay slot and before the 00501 // branch because putting code before or after it would be VERY BAD! 00502 // 00503 // If the annul bit of the branch is set, neither of these is legal! 00504 // If so, we need to handle spill differently but annulling is not yet used. 00505 for (MachineBasicBlock::iterator MII = MBB.begin(); MII != MBB.end(); ++MII) 00506 if (unsigned delaySlots = 00507 TM.getInstrInfo()->getNumDelaySlots(MII->getOpcode())) { 00508 MachineBasicBlock::iterator DelaySlotMI = next(MII); 00509 assert(DelaySlotMI != MBB.end() && "no instruction for delay slot"); 00510 00511 // Check the 2 conditions above: 00512 // (1) Does a branch need instructions added after it? 00513 // (2) O/w does delay slot instr. need instrns before or after? 00514 bool isBranch = (TM.getInstrInfo()->isBranch(MII->getOpcode()) || 00515 TM.getInstrInfo()->isReturn(MII->getOpcode())); 00516 bool cond1 = (isBranch && 00517 AddedInstrMap.count(MII) && 00518 AddedInstrMap[MII].InstrnsAfter.size() > 0); 00519 bool cond2 = (AddedInstrMap.count(DelaySlotMI) && 00520 (AddedInstrMap[DelaySlotMI].InstrnsBefore.size() > 0 || 00521 AddedInstrMap[DelaySlotMI].InstrnsAfter.size() > 0)); 00522 00523 if (cond1 || cond2) { 00524 assert(delaySlots==1 && 00525 "InsertBefore does not yet handle >1 delay slots!"); 00526 00527 if (DEBUG_RA) { 00528 std::cerr << "\nRegAlloc: Moved instr. with added code: " 00529 << *DelaySlotMI 00530 << " out of delay slots of instr: " << *MII; 00531 } 00532 00533 // move instruction before branch 00534 MBB.insert(MII, MBB.remove(DelaySlotMI++)); 00535 00536 // On cond1 we are done (we already moved the 00537 // instruction out of the delay slot). On cond2 we need 00538 // to insert a nop in place of the moved instruction 00539 if (cond2) { 00540 MBB.insert(MII, BuildMI(V9::NOP, 1)); 00541 } 00542 } 00543 else { 00544 // For non-branch instr with delay slots (probably a call), move 00545 // InstrAfter to the instr. in the last delay slot. 00546 MachineBasicBlock::iterator tmp = next(MII, delaySlots); 00547 move2DelayedInstr(MII, tmp); 00548 } 00549 } 00550 00551 // Finally iterate over all instructions in BB and insert before/after 00552 for (MachineBasicBlock::iterator MII=MBB.begin(); MII != MBB.end(); ++MII) { 00553 MachineInstr *MInst = MII; 00554 00555 // do not process Phis 00556 if (MInst->getOpcode() == V9::PHI) 00557 continue; 00558 00559 // if there are any added instructions... 00560 if (AddedInstrMap.count(MInst)) { 00561 AddedInstrns &CallAI = AddedInstrMap[MInst]; 00562 00563 #ifndef NDEBUG 00564 bool isBranch = (TM.getInstrInfo()->isBranch(MInst->getOpcode()) || 00565 TM.getInstrInfo()->isReturn(MInst->getOpcode())); 00566 assert((!isBranch || 00567 AddedInstrMap[MInst].InstrnsAfter.size() <= 00568 TM.getInstrInfo()->getNumDelaySlots(MInst->getOpcode())) && 00569 "Cannot put more than #delaySlots instrns after " 00570 "branch or return! Need to handle temps differently."); 00571 #endif 00572 00573 #ifndef NDEBUG 00574 // Temporary sanity checking code to detect whether the same machine 00575 // instruction is ever inserted twice before/after a call. 00576 // I suspect this is happening but am not sure. --Vikram, 7/1/03. 00577 std::set<const MachineInstr*> instrsSeen; 00578 for (int i = 0, N = CallAI.InstrnsBefore.size(); i < N; ++i) { 00579 assert(instrsSeen.count(CallAI.InstrnsBefore[i]) == 0 && 00580 "Duplicate machine instruction in InstrnsBefore!"); 00581 instrsSeen.insert(CallAI.InstrnsBefore[i]); 00582 } 00583 for (int i = 0, N = CallAI.InstrnsAfter.size(); i < N; ++i) { 00584 assert(instrsSeen.count(CallAI.InstrnsAfter[i]) == 0 && 00585 "Duplicate machine instruction in InstrnsBefore/After!"); 00586 instrsSeen.insert(CallAI.InstrnsAfter[i]); 00587 } 00588 #endif 00589 00590 // Now add the instructions before/after this MI. 00591 // We do this here to ensure that spill for an instruction is inserted 00592 // as close as possible to an instruction (see above insertCode4Spill) 00593 if (! CallAI.InstrnsBefore.empty()) 00594 PrependInstructions(CallAI.InstrnsBefore, MBB, MII,""); 00595 00596 if (! CallAI.InstrnsAfter.empty()) 00597 AppendInstructions(CallAI.InstrnsAfter, MBB, MII,""); 00598 00599 } // if there are any added instructions 00600 } // for each machine instruction 00601 } 00602 } 00603 00604 00605 /// Insert spill code for AN operand whose LR was spilled. May be called 00606 /// repeatedly for a single MachineInstr if it has many spilled operands. On 00607 /// each call, it finds a register which is not live at that instruction and 00608 /// also which is not used by other spilled operands of the same 00609 /// instruction. Then it uses this register temporarily to accommodate the 00610 /// spilled value. 00611 /// 00612 void PhyRegAlloc::insertCode4SpilledLR(const LiveRange *LR, 00613 MachineBasicBlock::iterator& MII, 00614 MachineBasicBlock &MBB, 00615 const unsigned OpNum) { 00616 MachineInstr *MInst = MII; 00617 const BasicBlock *BB = MBB.getBasicBlock(); 00618 00619 assert((! TM.getInstrInfo()->isCall(MInst->getOpcode()) || OpNum == 0) && 00620 "Outgoing arg of a call must be handled elsewhere (func arg ok)"); 00621 assert(! TM.getInstrInfo()->isReturn(MInst->getOpcode()) && 00622 "Return value of a ret must be handled elsewhere"); 00623 00624 MachineOperand& Op = MInst->getOperand(OpNum); 00625 bool isDef = Op.isDef(); 00626 bool isUse = Op.isUse(); 00627 unsigned RegType = MRI.getRegTypeForLR(LR); 00628 int SpillOff = LR->getSpillOffFromFP(); 00629 RegClass *RC = LR->getRegClass(); 00630 00631 // Get the live-variable set to find registers free before this instr. 00632 const ValueSet &LVSetBef = LVI->getLiveVarSetBeforeMInst(MInst, BB); 00633 00634 #ifndef NDEBUG 00635 // If this instr. is in the delay slot of a branch or return, we need to 00636 // include all live variables before that branch or return -- we don't want to 00637 // trample those! Verify that the set is included in the LV set before MInst. 00638 if (MII != MBB.begin()) { 00639 MachineBasicBlock::iterator PredMI = prior(MII); 00640 if (unsigned DS = TM.getInstrInfo()->getNumDelaySlots(PredMI->getOpcode())) 00641 assert(set_difference(LVI->getLiveVarSetBeforeMInst(PredMI), LVSetBef) 00642 .empty() && "Live-var set before branch should be included in " 00643 "live-var set of each delay slot instruction!"); 00644 } 00645 #endif 00646 00647 MF->getInfo<SparcV9FunctionInfo>()->pushTempValue(MRI.getSpilledRegSize(RegType)); 00648 00649 std::vector<MachineInstr*> MIBef, MIAft; 00650 std::vector<MachineInstr*> AdIMid; 00651 00652 // Choose a register to hold the spilled value, if one was not preallocated. 00653 // This may insert code before and after MInst to free up the value. If so, 00654 // this code should be first/last in the spill sequence before/after MInst. 00655 int TmpRegU=(LR->hasColor() 00656 ? MRI.getUnifiedRegNum(LR->getRegClassID(),LR->getColor()) 00657 : getUsableUniRegAtMI(RegType, &LVSetBef, MInst, MIBef,MIAft)); 00658 00659 // Set the operand first so that it this register does not get used 00660 // as a scratch register for later calls to getUsableUniRegAtMI below 00661 MInst->SetRegForOperand(OpNum, TmpRegU); 00662 00663 // get the added instructions for this instruction 00664 AddedInstrns &AI = AddedInstrMap[MInst]; 00665 00666 // We may need a scratch register to copy the spilled value to/from memory. 00667 // This may itself have to insert code to free up a scratch register. 00668 // Any such code should go before (after) the spill code for a load (store). 00669 // The scratch reg is not marked as used because it is only used 00670 // for the copy and not used across MInst. 00671 int scratchRegType = -1; 00672 int scratchReg = -1; 00673 if (MRI.regTypeNeedsScratchReg(RegType, scratchRegType)) { 00674 scratchReg = getUsableUniRegAtMI(scratchRegType, &LVSetBef, 00675 MInst, MIBef, MIAft); 00676 assert(scratchReg != MRI.getInvalidRegNum()); 00677 } 00678 00679 if (isUse) { 00680 // for a USE, we have to load the value of LR from stack to a TmpReg 00681 // and use the TmpReg as one operand of instruction 00682 00683 // actual loading instruction(s) 00684 MRI.cpMem2RegMI(AdIMid, MRI.getFramePointer(), SpillOff, TmpRegU, 00685 RegType, scratchReg); 00686 00687 // the actual load should be after the instructions to free up TmpRegU 00688 MIBef.insert(MIBef.end(), AdIMid.begin(), AdIMid.end()); 00689 AdIMid.clear(); 00690 } 00691 00692 if (isDef) { // if this is a Def 00693 // for a DEF, we have to store the value produced by this instruction 00694 // on the stack position allocated for this LR 00695 00696 // actual storing instruction(s) 00697 MRI.cpReg2MemMI(AdIMid, TmpRegU, MRI.getFramePointer(), SpillOff, 00698 RegType, scratchReg); 00699 00700 MIAft.insert(MIAft.begin(), AdIMid.begin(), AdIMid.end()); 00701 } // if !DEF 00702 00703 // Finally, insert the entire spill code sequences before/after MInst 00704 AI.InstrnsBefore.insert(AI.InstrnsBefore.end(), MIBef.begin(), MIBef.end()); 00705 AI.InstrnsAfter.insert(AI.InstrnsAfter.begin(), MIAft.begin(), MIAft.end()); 00706 00707 if (DEBUG_RA) { 00708 std::cerr << "\nFor Inst:\n " << *MInst; 00709 std::cerr << "SPILLED LR# " << LR->getUserIGNode()->getIndex(); 00710 std::cerr << "; added Instructions:"; 00711 for_each(MIBef.begin(), MIBef.end(), std::mem_fun(&MachineInstr::dump)); 00712 for_each(MIAft.begin(), MIAft.end(), std::mem_fun(&MachineInstr::dump)); 00713 } 00714 } 00715 00716 00717 /// Insert caller saving/restoring instructions before/after a call machine 00718 /// instruction (before or after any other instructions that were inserted for 00719 /// the call). 00720 /// 00721 void 00722 PhyRegAlloc::insertCallerSavingCode(std::vector<MachineInstr*> &instrnsBefore, 00723 std::vector<MachineInstr*> &instrnsAfter, 00724 MachineInstr *CallMI, 00725 const BasicBlock *BB) { 00726 assert(TM.getInstrInfo()->isCall(CallMI->getOpcode())); 00727 00728 // hash set to record which registers were saved/restored 00729 hash_set<unsigned> PushedRegSet; 00730 00731 CallArgsDescriptor* argDesc = CallArgsDescriptor::get(CallMI); 00732 00733 // if the call is to a instrumentation function, do not insert save and 00734 // restore instructions the instrumentation function takes care of save 00735 // restore for volatile regs. 00736 // 00737 // FIXME: this should be made general, not specific to the reoptimizer! 00738 const Function *Callee = argDesc->getCallInst()->getCalledFunction(); 00739 bool isLLVMFirstTrigger = Callee && Callee->getName() == "llvm_first_trigger"; 00740 00741 // Now check if the call has a return value (using argDesc) and if so, 00742 // find the LR of the TmpInstruction representing the return value register. 00743 // (using the last or second-last *implicit operand* of the call MI). 00744 // Insert it to to the PushedRegSet since we must not save that register 00745 // and restore it after the call. 00746 // We do this because, we look at the LV set *after* the instruction 00747 // to determine, which LRs must be saved across calls. The return value 00748 // of the call is live in this set - but we must not save/restore it. 00749 if (const Value *origRetVal = argDesc->getReturnValue()) { 00750 unsigned retValRefNum = (CallMI->getNumImplicitRefs() - 00751 (argDesc->getIndirectFuncPtr()? 1 : 2)); 00752 const TmpInstruction* tmpRetVal = 00753 cast<TmpInstruction>(CallMI->getImplicitRef(retValRefNum)); 00754 assert(tmpRetVal->getOperand(0) == origRetVal && 00755 tmpRetVal->getType() == origRetVal->getType() && 00756 "Wrong implicit ref?"); 00757 LiveRange *RetValLR = LRI->getLiveRangeForValue(tmpRetVal); 00758 assert(RetValLR && "No LR for RetValue of call"); 00759 00760 if (! RetValLR->isMarkedForSpill()) 00761 PushedRegSet.insert(MRI.getUnifiedRegNum(RetValLR->getRegClassID(), 00762 RetValLR->getColor())); 00763 } 00764 00765 const ValueSet &LVSetAft = LVI->getLiveVarSetAfterMInst(CallMI, BB); 00766 ValueSet::const_iterator LIt = LVSetAft.begin(); 00767 00768 // for each live var in live variable set after machine inst 00769 for( ; LIt != LVSetAft.end(); ++LIt) { 00770 // get the live range corresponding to live var 00771 LiveRange *const LR = LRI->getLiveRangeForValue(*LIt); 00772 00773 // LR can be null if it is a const since a const 00774 // doesn't have a dominating def - see Assumptions above 00775 if (LR) { 00776 if (! LR->isMarkedForSpill()) { 00777 assert(LR->hasColor() && "LR is neither spilled nor colored?"); 00778 unsigned RCID = LR->getRegClassID(); 00779 unsigned Color = LR->getColor(); 00780 00781 if (MRI.isRegVolatile(RCID, Color) ) { 00782 // if this is a call to the first-level reoptimizer 00783 // instrumentation entry point, and the register is not 00784 // modified by call, don't save and restore it. 00785 if (isLLVMFirstTrigger && !MRI.modifiedByCall(RCID, Color)) 00786 continue; 00787 00788 // if the value is in both LV sets (i.e., live before and after 00789 // the call machine instruction) 00790 unsigned Reg = MRI.getUnifiedRegNum(RCID, Color); 00791 00792 // if we haven't already pushed this register... 00793 if( PushedRegSet.find(Reg) == PushedRegSet.end() ) { 00794 unsigned RegType = MRI.getRegTypeForLR(LR); 00795 00796 // Now get two instructions - to push on stack and pop from stack 00797 // and add them to InstrnsBefore and InstrnsAfter of the 00798 // call instruction 00799 int StackOff = 00800 MF->getInfo<SparcV9FunctionInfo>()->pushTempValue(MRI.getSpilledRegSize(RegType)); 00801 00802 //---- Insert code for pushing the reg on stack ---------- 00803 00804 std::vector<MachineInstr*> AdIBef, AdIAft; 00805 00806 // We may need a scratch register to copy the saved value 00807 // to/from memory. This may itself have to insert code to 00808 // free up a scratch register. Any such code should go before 00809 // the save code. The scratch register, if any, is by default 00810 // temporary and not "used" by the instruction unless the 00811 // copy code itself decides to keep the value in the scratch reg. 00812 int scratchRegType = -1; 00813 int scratchReg = -1; 00814 if (MRI.regTypeNeedsScratchReg(RegType, scratchRegType)) 00815 { // Find a register not live in the LVSet before CallMI 00816 const ValueSet &LVSetBef = 00817 LVI->getLiveVarSetBeforeMInst(CallMI, BB); 00818 scratchReg = getUsableUniRegAtMI(scratchRegType, &LVSetBef, 00819 CallMI, AdIBef, AdIAft); 00820 assert(scratchReg != MRI.getInvalidRegNum()); 00821 } 00822 00823 if (AdIBef.size() > 0) 00824 instrnsBefore.insert(instrnsBefore.end(), 00825 AdIBef.begin(), AdIBef.end()); 00826 00827 MRI.cpReg2MemMI(instrnsBefore, Reg, MRI.getFramePointer(), 00828 StackOff, RegType, scratchReg); 00829 00830 if (AdIAft.size() > 0) 00831 instrnsBefore.insert(instrnsBefore.end(), 00832 AdIAft.begin(), AdIAft.end()); 00833 00834 //---- Insert code for popping the reg from the stack ---------- 00835 AdIBef.clear(); 00836 AdIAft.clear(); 00837 00838 // We may need a scratch register to copy the saved value 00839 // from memory. This may itself have to insert code to 00840 // free up a scratch register. Any such code should go 00841 // after the save code. As above, scratch is not marked "used". 00842 scratchRegType = -1; 00843 scratchReg = -1; 00844 if (MRI.regTypeNeedsScratchReg(RegType, scratchRegType)) 00845 { // Find a register not live in the LVSet after CallMI 00846 scratchReg = getUsableUniRegAtMI(scratchRegType, &LVSetAft, 00847 CallMI, AdIBef, AdIAft); 00848 assert(scratchReg != MRI.getInvalidRegNum()); 00849 } 00850 00851 if (AdIBef.size() > 0) 00852 instrnsAfter.insert(instrnsAfter.end(), 00853 AdIBef.begin(), AdIBef.end()); 00854 00855 MRI.cpMem2RegMI(instrnsAfter, MRI.getFramePointer(), StackOff, 00856 Reg, RegType, scratchReg); 00857 00858 if (AdIAft.size() > 0) 00859 instrnsAfter.insert(instrnsAfter.end(), 00860 AdIAft.begin(), AdIAft.end()); 00861 00862 PushedRegSet.insert(Reg); 00863 00864 if(DEBUG_RA) { 00865 std::cerr << "\nFor call inst:" << *CallMI; 00866 std::cerr << " -inserted caller saving instrs: Before:\n\t "; 00867 for_each(instrnsBefore.begin(), instrnsBefore.end(), 00868 std::mem_fun(&MachineInstr::dump)); 00869 std::cerr << " -and After:\n\t "; 00870 for_each(instrnsAfter.begin(), instrnsAfter.end(), 00871 std::mem_fun(&MachineInstr::dump)); 00872 } 00873 } // if not already pushed 00874 } // if LR has a volatile color 00875 } // if LR has color 00876 } // if there is a LR for Var 00877 } // for each value in the LV set after instruction 00878 } 00879 00880 00881 /// Returns the unified register number of a temporary register to be used 00882 /// BEFORE MInst. If no register is available, it will pick one and modify 00883 /// MIBef and MIAft to contain instructions used to free up this returned 00884 /// register. 00885 /// 00886 int PhyRegAlloc::getUsableUniRegAtMI(const int RegType, 00887 const ValueSet *LVSetBef, 00888 MachineInstr *MInst, 00889 std::vector<MachineInstr*>& MIBef, 00890 std::vector<MachineInstr*>& MIAft) { 00891 RegClass* RC = getRegClassByID(MRI.getRegClassIDOfRegType(RegType)); 00892 00893 int RegU = getUnusedUniRegAtMI(RC, RegType, MInst, LVSetBef); 00894 00895 if (RegU == -1) { 00896 // we couldn't find an unused register. Generate code to free up a reg by 00897 // saving it on stack and restoring after the instruction 00898 00899 int TmpOff = MF->getInfo<SparcV9FunctionInfo>()->pushTempValue(MRI.getSpilledRegSize(RegType)); 00900 00901 RegU = getUniRegNotUsedByThisInst(RC, RegType, MInst); 00902 00903 // Check if we need a scratch register to copy this register to memory. 00904 int scratchRegType = -1; 00905 if (MRI.regTypeNeedsScratchReg(RegType, scratchRegType)) { 00906 int scratchReg = getUsableUniRegAtMI(scratchRegType, LVSetBef, 00907 MInst, MIBef, MIAft); 00908 assert(scratchReg != MRI.getInvalidRegNum()); 00909 00910 // We may as well hold the value in the scratch register instead 00911 // of copying it to memory and back. But we have to mark the 00912 // register as used by this instruction, so it does not get used 00913 // as a scratch reg. by another operand or anyone else. 00914 ScratchRegsUsed.insert(std::make_pair(MInst, scratchReg)); 00915 MRI.cpReg2RegMI(MIBef, RegU, scratchReg, RegType); 00916 MRI.cpReg2RegMI(MIAft, scratchReg, RegU, RegType); 00917 } else { // the register can be copied directly to/from memory so do it. 00918 MRI.cpReg2MemMI(MIBef, RegU, MRI.getFramePointer(), TmpOff, RegType); 00919 MRI.cpMem2RegMI(MIAft, MRI.getFramePointer(), TmpOff, RegU, RegType); 00920 } 00921 } 00922 00923 return RegU; 00924 } 00925 00926 00927 /// Returns the register-class register number of a new unused register that 00928 /// can be used to accommodate a temporary value. May be called repeatedly 00929 /// for a single MachineInstr. On each call, it finds a register which is not 00930 /// live at that instruction and which is not used by any spilled operands of 00931 /// that instruction. 00932 /// 00933 int PhyRegAlloc::getUnusedUniRegAtMI(RegClass *RC, const int RegType, 00934 const MachineInstr *MInst, 00935 const ValueSet* LVSetBef) { 00936 RC->clearColorsUsed(); // Reset array 00937 00938 if (LVSetBef == NULL) { 00939 LVSetBef = &LVI->getLiveVarSetBeforeMInst(MInst); 00940 assert(LVSetBef != NULL && "Unable to get live-var set before MInst?"); 00941 } 00942 00943 ValueSet::const_iterator LIt = LVSetBef->begin(); 00944 00945 // for each live var in live variable set after machine inst 00946 for ( ; LIt != LVSetBef->end(); ++LIt) { 00947 // Get the live range corresponding to live var, and its RegClass 00948 LiveRange *const LRofLV = LRI->getLiveRangeForValue(*LIt ); 00949 00950 // LR can be null if it is a const since a const 00951 // doesn't have a dominating def - see Assumptions above 00952 if (LRofLV && LRofLV->getRegClass() == RC && LRofLV->hasColor()) 00953 RC->markColorsUsed(LRofLV->getColor(), 00954 MRI.getRegTypeForLR(LRofLV), RegType); 00955 } 00956 00957 // It is possible that one operand of this MInst was already spilled 00958 // and it received some register temporarily. If that's the case, 00959 // it is recorded in machine operand. We must skip such registers. 00960 setRelRegsUsedByThisInst(RC, RegType, MInst); 00961 00962 int unusedReg = RC->getUnusedColor(RegType); // find first unused color 00963 if (unusedReg >= 0) 00964 return MRI.getUnifiedRegNum(RC->getID(), unusedReg); 00965 00966 return -1; 00967 } 00968 00969 00970 /// Return the unified register number of a register in class RC which is not 00971 /// used by any operands of MInst. 00972 /// 00973 int PhyRegAlloc::getUniRegNotUsedByThisInst(RegClass *RC, 00974 const int RegType, 00975 const MachineInstr *MInst) { 00976 RC->clearColorsUsed(); 00977 00978 setRelRegsUsedByThisInst(RC, RegType, MInst); 00979 00980 // find the first unused color 00981 int unusedReg = RC->getUnusedColor(RegType); 00982 assert(unusedReg >= 0 && 00983 "FATAL: No free register could be found in reg class!!"); 00984 00985 return MRI.getUnifiedRegNum(RC->getID(), unusedReg); 00986 } 00987 00988 00989 /// Modify the IsColorUsedArr of register class RC, by setting the bits 00990 /// corresponding to register RegNo. This is a helper method of 00991 /// setRelRegsUsedByThisInst(). 00992 /// 00993 static void markRegisterUsed(int RegNo, RegClass *RC, int RegType, 00994 const SparcV9RegInfo &TRI) { 00995 unsigned classId = 0; 00996 int classRegNum = TRI.getClassRegNum(RegNo, classId); 00997 if (RC->getID() == classId) 00998 RC->markColorsUsed(classRegNum, RegType, RegType); 00999 } 01000 01001 void PhyRegAlloc::setRelRegsUsedByThisInst(RegClass *RC, int RegType, 01002 const MachineInstr *MI) { 01003 assert(OperandsColoredMap[MI] == true && 01004 "Illegal to call setRelRegsUsedByThisInst() until colored operands " 01005 "are marked for an instruction."); 01006 01007 // Add the registers already marked as used by the instruction. Both 01008 // explicit and implicit operands are set. 01009 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) 01010 if (MI->getOperand(i).hasAllocatedReg()) 01011 markRegisterUsed(MI->getOperand(i).getReg(), RC, RegType,MRI); 01012 01013 for (unsigned i = 0, e = MI->getNumImplicitRefs(); i != e; ++i) 01014 if (MI->getImplicitOp(i).hasAllocatedReg()) 01015 markRegisterUsed(MI->getImplicitOp(i).getReg(), RC, RegType,MRI); 01016 01017 // Add all of the scratch registers that are used to save values across the 01018 // instruction (e.g., for saving state register values). 01019 std::pair<ScratchRegsUsedTy::iterator, ScratchRegsUsedTy::iterator> 01020 IR = ScratchRegsUsed.equal_range(MI); 01021 for (ScratchRegsUsedTy::iterator I = IR.first; I != IR.second; ++I) 01022 markRegisterUsed(I->second, RC, RegType, MRI); 01023 01024 // If there are implicit references, mark their allocated regs as well 01025 for (unsigned z=0; z < MI->getNumImplicitRefs(); z++) 01026 if (const LiveRange* 01027 LRofImpRef = LRI->getLiveRangeForValue(MI->getImplicitRef(z))) 01028 if (LRofImpRef->hasColor()) 01029 // this implicit reference is in a LR that received a color 01030 RC->markColorsUsed(LRofImpRef->getColor(), 01031 MRI.getRegTypeForLR(LRofImpRef), RegType); 01032 } 01033 01034 01035 /// If there are delay slots for an instruction, the instructions added after 01036 /// it must really go after the delayed instruction(s). So, we Move the 01037 /// InstrAfter of that instruction to the corresponding delayed instruction 01038 /// using the following method. 01039 /// 01040 void PhyRegAlloc::move2DelayedInstr(const MachineInstr *OrigMI, 01041 const MachineInstr *DelayedMI) 01042 { 01043 // "added after" instructions of the original instr 01044 std::vector<MachineInstr *> &OrigAft = AddedInstrMap[OrigMI].InstrnsAfter; 01045 01046 if (DEBUG_RA && OrigAft.size() > 0) { 01047 std::cerr << "\nRegAlloc: Moved InstrnsAfter for: " << *OrigMI; 01048 std::cerr << " to last delay slot instrn: " << *DelayedMI; 01049 } 01050 01051 // "added after" instructions of the delayed instr 01052 std::vector<MachineInstr *> &DelayedAft=AddedInstrMap[DelayedMI].InstrnsAfter; 01053 01054 // go thru all the "added after instructions" of the original instruction 01055 // and append them to the "added after instructions" of the delayed 01056 // instructions 01057 DelayedAft.insert(DelayedAft.end(), OrigAft.begin(), OrigAft.end()); 01058 01059 // empty the "added after instructions" of the original instruction 01060 OrigAft.clear(); 01061 } 01062 01063 01064 void PhyRegAlloc::colorIncomingArgs() 01065 { 01066 MRI.colorMethodArgs(Fn, *LRI, AddedInstrAtEntry.InstrnsBefore, 01067 AddedInstrAtEntry.InstrnsAfter); 01068 } 01069 01070 01071 /// Determine whether the suggested color of each live range is really usable, 01072 /// and then call its setSuggestedColorUsable() method to record the answer. A 01073 /// suggested color is NOT usable when the suggested color is volatile AND 01074 /// when there are call interferences. 01075 /// 01076 void PhyRegAlloc::markUnusableSugColors() 01077 { 01078 LiveRangeMapType::const_iterator HMI = (LRI->getLiveRangeMap())->begin(); 01079 LiveRangeMapType::const_iterator HMIEnd = (LRI->getLiveRangeMap())->end(); 01080 01081 for (; HMI != HMIEnd ; ++HMI ) { 01082 if (HMI->first) { 01083 LiveRange *L = HMI->second; // get the LiveRange 01084 if (L && L->hasSuggestedColor ()) 01085 L->setSuggestedColorUsable 01086 (!(MRI.isRegVolatile (L->getRegClassID (), L->getSuggestedColor ()) 01087 && L->isCallInterference ())); 01088 } 01089 } // for all LR's in hash map 01090 } 01091 01092 01093 /// For each live range that is spilled, allocates a new spill position on the 01094 /// stack, and set the stack offsets of the live range that will be spilled to 01095 /// that position. This must be called just after coloring the LRs. 01096 /// 01097 void PhyRegAlloc::allocateStackSpace4SpilledLRs() { 01098 if (DEBUG_RA) std::cerr << "\nSetting LR stack offsets for spills...\n"; 01099 01100 LiveRangeMapType::const_iterator HMI = LRI->getLiveRangeMap()->begin(); 01101 LiveRangeMapType::const_iterator HMIEnd = LRI->getLiveRangeMap()->end(); 01102 01103 for ( ; HMI != HMIEnd ; ++HMI) { 01104 if (HMI->first && HMI->second) { 01105 LiveRange *L = HMI->second; // get the LiveRange 01106 if (L->isMarkedForSpill()) { // NOTE: allocating size of long Type ** 01107 int stackOffset = MF->getInfo<SparcV9FunctionInfo>()->allocateSpilledValue(Type::LongTy); 01108 L->setSpillOffFromFP(stackOffset); 01109 if (DEBUG_RA) 01110 std::cerr << " LR# " << L->getUserIGNode()->getIndex() 01111 << ": stack-offset = " << stackOffset << "\n"; 01112 } 01113 } 01114 } // for all LR's in hash map 01115 } 01116 01117 01118 void PhyRegAlloc::saveStateForValue (std::vector<AllocInfo> &state, 01119 const Value *V, int Insn, int Opnd) { 01120 LiveRangeMapType::const_iterator HMI = LRI->getLiveRangeMap ()->find (V); 01121 LiveRangeMapType::const_iterator HMIEnd = LRI->getLiveRangeMap ()->end (); 01122 AllocInfo::AllocStateTy AllocState = AllocInfo::NotAllocated; 01123 int Placement = -1; 01124 if ((HMI != HMIEnd) && HMI->second) { 01125 LiveRange *L = HMI->second; 01126 assert ((L->hasColor () || L->isMarkedForSpill ()) 01127 && "Live range exists but not colored or spilled"); 01128 if (L->hasColor ()) { 01129 AllocState = AllocInfo::Allocated; 01130 Placement = MRI.getUnifiedRegNum (L->getRegClassID (), 01131 L->getColor ()); 01132 } else if (L->isMarkedForSpill ()) { 01133 AllocState = AllocInfo::Spilled; 01134 assert (L->hasSpillOffset () 01135 && "Live range marked for spill but has no spill offset"); 01136 Placement = L->getSpillOffFromFP (); 01137 } 01138 } 01139 state.push_back (AllocInfo (Insn, Opnd, AllocState, Placement)); 01140 } 01141 01142 01143 /// Save the global register allocation decisions made by the register 01144 /// allocator so that they can be accessed later (sort of like "poor man's 01145 /// debug info"). 01146 /// 01147 void PhyRegAlloc::saveState () { 01148 std::vector<AllocInfo> &state = FnAllocState[Fn]; 01149 unsigned ArgNum = 0; 01150 // Arguments encoded as instruction # -1 01151 for (Function::const_aiterator i=Fn->abegin (), e=Fn->aend (); i != e; ++i) { 01152 const Argument *Arg = &*i; 01153 saveStateForValue (state, Arg, -1, ArgNum); 01154 ++ArgNum; 01155 } 01156 unsigned InstCount = 0; 01157 // Instructions themselves encoded as operand # -1 01158 for (const_inst_iterator II=inst_begin (Fn), IE=inst_end (Fn); II!=IE; ++II){ 01159 const Instruction *Inst = &*II; 01160 saveStateForValue (state, Inst, InstCount, -1); 01161 if (isa<PHINode> (Inst)) { 01162 MachineCodeForInstruction &MCforPN = MachineCodeForInstruction::get(Inst); 01163 // Last instr should be the copy...figure out what reg it is reading from 01164 if (Value *PhiCpRes = MCforPN.back()->getOperand(0).getVRegValueOrNull()){ 01165 if (DEBUG_RA) 01166 std::cerr << "Found Phi copy result: " << PhiCpRes->getName() 01167 << " in: " << *MCforPN.back() << "\n"; 01168 saveStateForValue (state, PhiCpRes, InstCount, -2); 01169 } 01170 } 01171 ++InstCount; 01172 } 01173 } 01174 01175 01176 bool PhyRegAlloc::doFinalization (Module &M) { 01177 if (SaveRegAllocState) finishSavingState (M); 01178 return false; 01179 } 01180 01181 01182 /// Finish the job of saveState(), by collapsing FnAllocState into an LLVM 01183 /// Constant and stuffing it inside the Module. 01184 /// 01185 /// FIXME: There should be other, better ways of storing the saved 01186 /// state; this one is cumbersome and does not work well with the JIT. 01187 /// 01188 void PhyRegAlloc::finishSavingState (Module &M) { 01189 if (DEBUG_RA) 01190 std::cerr << "---- Saving reg. alloc state; SaveStateToModule = " 01191 << SaveStateToModule << " ----\n"; 01192 01193 // If saving state into the module, just copy new elements to the 01194 // correct global. 01195 if (!SaveStateToModule) { 01196 ExportedFnAllocState = FnAllocState; 01197 // FIXME: should ONLY copy new elements in FnAllocState 01198 return; 01199 } 01200 01201 // Convert FnAllocState to a single Constant array and add it 01202 // to the Module. 01203 ArrayType *AT = ArrayType::get (AllocInfo::getConstantType (), 0); 01204 std::vector<const Type *> TV; 01205 TV.push_back (Type::UIntTy); 01206 TV.push_back (AT); 01207 PointerType *PT = PointerType::get (StructType::get (TV)); 01208 01209 std::vector<Constant *> allstate; 01210 for (Module::iterator I = M.begin (), E = M.end (); I != E; ++I) { 01211 Function *F = I; 01212 if (F->isExternal ()) continue; 01213 if (FnAllocState.find (F) == FnAllocState.end ()) { 01214 allstate.push_back (ConstantPointerNull::get (PT)); 01215 } else { 01216 std::vector<AllocInfo> &state = FnAllocState[F]; 01217 01218 // Convert state into an LLVM ConstantArray, and put it in a 01219 // ConstantStruct (named S) along with its size. 01220 std::vector<Constant *> stateConstants; 01221 for (unsigned i = 0, s = state.size (); i != s; ++i) 01222 stateConstants.push_back (state[i].toConstant ()); 01223 unsigned Size = stateConstants.size (); 01224 ArrayType *AT = ArrayType::get (AllocInfo::getConstantType (), Size); 01225 std::vector<const Type *> TV; 01226 TV.push_back (Type::UIntTy); 01227 TV.push_back (AT); 01228 StructType *ST = StructType::get (TV); 01229 std::vector<Constant *> CV; 01230 CV.push_back (ConstantUInt::get (Type::UIntTy, Size)); 01231 CV.push_back (ConstantArray::get (AT, stateConstants)); 01232 Constant *S = ConstantStruct::get (ST, CV); 01233 01234 GlobalVariable *GV = 01235 new GlobalVariable (ST, true, 01236 GlobalValue::InternalLinkage, S, 01237 F->getName () + ".regAllocState", &M); 01238 01239 // Have: { uint, [Size x { uint, int, uint, int }] } * 01240 // Cast it to: { uint, [0 x { uint, int, uint, int }] } * 01241 Constant *CE = ConstantExpr::getCast (GV, PT); 01242 allstate.push_back (CE); 01243 } 01244 } 01245 01246 unsigned Size = allstate.size (); 01247 // Final structure type is: 01248 // { uint, [Size x { uint, [0 x { uint, int, uint, int }] } *] } 01249 std::vector<const Type *> TV2; 01250 TV2.push_back (Type::UIntTy); 01251 ArrayType *AT2 = ArrayType::get (PT, Size); 01252 TV2.push_back (AT2); 01253 StructType *ST2 = StructType::get (TV2); 01254 std::vector<Constant *> CV2; 01255 CV2.push_back (ConstantUInt::get (Type::UIntTy, Size)); 01256 CV2.push_back (ConstantArray::get (AT2, allstate)); 01257 new GlobalVariable (ST2, true, GlobalValue::ExternalLinkage, 01258 ConstantStruct::get (ST2, CV2), "_llvm_regAllocState", 01259 &M); 01260 } 01261 01262 01263 /// Allocate registers for the machine code previously generated for F using 01264 /// the graph-coloring algorithm. 01265 /// 01266 bool PhyRegAlloc::runOnFunction (Function &F) { 01267 if (DEBUG_RA) 01268 std::cerr << "\n********* Function "<< F.getName () << " ***********\n"; 01269 01270 Fn = &F; 01271 MF = &MachineFunction::get (Fn); 01272 LVI = &getAnalysis<FunctionLiveVarInfo> (); 01273 LRI = new LiveRangeInfo (Fn, TM, RegClassList); 01274 LoopDepthCalc = &getAnalysis<LoopInfo> (); 01275 01276 // Create each RegClass for the target machine and add it to the 01277 // RegClassList. This must be done before calling constructLiveRanges(). 01278 for (unsigned rc = 0; rc != NumOfRegClasses; ++rc) 01279 RegClassList.push_back (new RegClass (Fn, TM.getRegInfo(), 01280 MRI.getMachineRegClass(rc))); 01281 01282 LRI->constructLiveRanges(); // create LR info 01283 if (DEBUG_RA >= RA_DEBUG_LiveRanges) 01284 LRI->printLiveRanges(); 01285 01286 createIGNodeListsAndIGs(); // create IGNode list and IGs 01287 01288 buildInterferenceGraphs(); // build IGs in all reg classes 01289 01290 if (DEBUG_RA >= RA_DEBUG_LiveRanges) { 01291 // print all LRs in all reg classes 01292 for ( unsigned rc=0; rc < NumOfRegClasses ; rc++) 01293 RegClassList[rc]->printIGNodeList(); 01294 01295 // print IGs in all register classes 01296 for ( unsigned rc=0; rc < NumOfRegClasses ; rc++) 01297 RegClassList[rc]->printIG(); 01298 } 01299 01300 LRI->coalesceLRs(); // coalesce all live ranges 01301 01302 if (DEBUG_RA >= RA_DEBUG_LiveRanges) { 01303 // print all LRs in all reg classes 01304 for (unsigned rc=0; rc < NumOfRegClasses; rc++) 01305 RegClassList[rc]->printIGNodeList(); 01306 01307 // print IGs in all register classes 01308 for (unsigned rc=0; rc < NumOfRegClasses; rc++) 01309 RegClassList[rc]->printIG(); 01310 } 01311 01312 // mark un-usable suggested color before graph coloring algorithm. 01313 // When this is done, the graph coloring algo will not reserve 01314 // suggested color unnecessarily - they can be used by another LR 01315 markUnusableSugColors(); 01316 01317 // color all register classes using the graph coloring algo 01318 for (unsigned rc=0; rc < NumOfRegClasses ; rc++) 01319 RegClassList[rc]->colorAllRegs(); 01320 01321 // After graph coloring, if some LRs did not receive a color (i.e, spilled) 01322 // a position for such spilled LRs 01323 allocateStackSpace4SpilledLRs(); 01324 01325 // Reset the temp. area on the stack before use by the first instruction. 01326 // This will also happen after updating each instruction. 01327 MF->getInfo<SparcV9FunctionInfo>()->popAllTempValues(); 01328 01329 // color incoming args - if the correct color was not received 01330 // insert code to copy to the correct register 01331 colorIncomingArgs(); 01332 01333 // Save register allocation state for this function in a Constant. 01334 if (SaveRegAllocState) 01335 saveState(); 01336 01337 // Now update the machine code with register names and add any additional 01338 // code inserted by the register allocator to the instruction stream. 01339 updateMachineCode(); 01340 01341 if (SaveRegAllocState && !SaveStateToModule) 01342 finishSavingState (const_cast<Module&> (*Fn->getParent ())); 01343 01344 if (DEBUG_RA) { 01345 std::cerr << "\n**** Machine Code After Register Allocation:\n\n"; 01346 MF->dump(); 01347 } 01348 01349 // Tear down temporary data structures 01350 for (unsigned rc = 0; rc < NumOfRegClasses; ++rc) 01351 delete RegClassList[rc]; 01352 RegClassList.clear (); 01353 AddedInstrMap.clear (); 01354 OperandsColoredMap.clear (); 01355 ScratchRegsUsed.clear (); 01356 AddedInstrAtEntry.clear (); 01357 delete LRI; 01358 01359 if (DEBUG_RA) std::cerr << "\nRegister allocation complete!\n"; 01360 return false; // Function was not modified 01361 } 01362 01363 } // End llvm namespace