LLVM API Documentation
00001 //===- SchedGraph.cpp - Scheduling Graph Implementation -------------------===// 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 // Scheduling graph based on SSA graph plus extra dependence edges capturing 00011 // dependences due to machine resources (machine registers, CC registers, and 00012 // any others). 00013 // 00014 //===----------------------------------------------------------------------===// 00015 00016 #include "SchedGraph.h" 00017 #include "llvm/Function.h" 00018 #include "llvm/Instructions.h" 00019 #include "llvm/CodeGen/MachineFunction.h" 00020 #include "llvm/Target/TargetInstrInfo.h" 00021 #include "llvm/Target/TargetMachine.h" 00022 #include "../MachineCodeForInstruction.h" 00023 #include "../SparcV9RegInfo.h" 00024 #include "../SparcV9InstrInfo.h" 00025 #include "llvm/ADT/STLExtras.h" 00026 #include <iostream> 00027 00028 namespace llvm { 00029 00030 //*********************** Internal Data Structures *************************/ 00031 00032 // The following two types need to be classes, not typedefs, so we can use 00033 // opaque declarations in SchedGraph.h 00034 // 00035 struct RefVec: public std::vector<std::pair<SchedGraphNode*, int> > { 00036 typedef std::vector<std::pair<SchedGraphNode*,int> >::iterator iterator; 00037 typedef 00038 std::vector<std::pair<SchedGraphNode*,int> >::const_iterator const_iterator; 00039 }; 00040 00041 struct RegToRefVecMap: public hash_map<int, RefVec> { 00042 typedef hash_map<int, RefVec>:: iterator iterator; 00043 typedef hash_map<int, RefVec>::const_iterator const_iterator; 00044 }; 00045 00046 struct ValueToDefVecMap: public hash_map<const Value*, RefVec> { 00047 typedef hash_map<const Value*, RefVec>:: iterator iterator; 00048 typedef hash_map<const Value*, RefVec>::const_iterator const_iterator; 00049 }; 00050 00051 00052 // 00053 // class SchedGraphNode 00054 // 00055 00056 SchedGraphNode::SchedGraphNode(unsigned NID, MachineBasicBlock *mbb, 00057 int indexInBB, const TargetMachine& Target) 00058 : SchedGraphNodeCommon(NID,indexInBB), MBB(mbb), MI(0) { 00059 if (mbb) { 00060 MachineBasicBlock::iterator I = MBB->begin(); 00061 std::advance(I, indexInBB); 00062 MI = I; 00063 00064 MachineOpCode mopCode = MI->getOpcode(); 00065 latency = Target.getInstrInfo()->hasResultInterlock(mopCode) 00066 ? Target.getInstrInfo()->minLatency(mopCode) 00067 : Target.getInstrInfo()->maxLatency(mopCode); 00068 } 00069 } 00070 00071 // 00072 // Method: SchedGraphNode Destructor 00073 // 00074 // Description: 00075 // Free memory allocated by the SchedGraphNode object. 00076 // 00077 // Notes: 00078 // Do not delete the edges here. The base class will take care of that. 00079 // Only handle subclass specific stuff here (where currently there is 00080 // none). 00081 // 00082 SchedGraphNode::~SchedGraphNode() { 00083 } 00084 00085 // 00086 // class SchedGraph 00087 // 00088 SchedGraph::SchedGraph(MachineBasicBlock &mbb, const TargetMachine& target) 00089 : MBB(mbb) { 00090 buildGraph(target); 00091 } 00092 00093 // 00094 // Method: SchedGraph Destructor 00095 // 00096 // Description: 00097 // This method deletes memory allocated by the SchedGraph object. 00098 // 00099 // Notes: 00100 // Do not delete the graphRoot or graphLeaf here. The base class handles 00101 // that bit of work. 00102 // 00103 SchedGraph::~SchedGraph() { 00104 for (const_iterator I = begin(); I != end(); ++I) 00105 delete I->second; 00106 } 00107 00108 void SchedGraph::dump() const { 00109 std::cerr << " Sched Graph for Basic Block: " 00110 << MBB.getBasicBlock()->getName() 00111 << " (" << *MBB.getBasicBlock() << ")" 00112 << "\n\n Actual Root nodes: "; 00113 for (SchedGraphNodeCommon::const_iterator I = graphRoot->beginOutEdges(), 00114 E = graphRoot->endOutEdges(); 00115 I != E; ++I) { 00116 std::cerr << (*I)->getSink ()->getNodeId (); 00117 if (I + 1 != E) { std::cerr << ", "; } 00118 } 00119 std::cerr << "\n Graph Nodes:\n"; 00120 for (const_iterator I = begin(), E = end(); I != E; ++I) 00121 std::cerr << "\n" << *I->second; 00122 std::cerr << "\n"; 00123 } 00124 00125 void SchedGraph::addDummyEdges() { 00126 assert(graphRoot->getNumOutEdges() == 0); 00127 00128 for (const_iterator I=begin(); I != end(); ++I) { 00129 SchedGraphNode* node = (*I).second; 00130 assert(node != graphRoot && node != graphLeaf); 00131 if (node->beginInEdges() == node->endInEdges()) 00132 (void) new SchedGraphEdge(graphRoot, node, SchedGraphEdge::CtrlDep, 00133 SchedGraphEdge::NonDataDep, 0); 00134 if (node->beginOutEdges() == node->endOutEdges()) 00135 (void) new SchedGraphEdge(node, graphLeaf, SchedGraphEdge::CtrlDep, 00136 SchedGraphEdge::NonDataDep, 0); 00137 } 00138 } 00139 00140 00141 void SchedGraph::addCDEdges(const TerminatorInst* term, 00142 const TargetMachine& target) { 00143 const TargetInstrInfo& mii = *target.getInstrInfo(); 00144 MachineCodeForInstruction &termMvec = MachineCodeForInstruction::get(term); 00145 00146 // Find the first branch instr in the sequence of machine instrs for term 00147 // 00148 unsigned first = 0; 00149 while (! mii.isBranch(termMvec[first]->getOpcode()) && 00150 ! mii.isReturn(termMvec[first]->getOpcode())) 00151 ++first; 00152 assert(first < termMvec.size() && 00153 "No branch instructions for terminator? Ok, but weird!"); 00154 if (first == termMvec.size()) 00155 return; 00156 00157 SchedGraphNode* firstBrNode = getGraphNodeForInstr(termMvec[first]); 00158 00159 // Add CD edges from each instruction in the sequence to the 00160 // *last preceding* branch instr. in the sequence 00161 // Use a latency of 0 because we only need to prevent out-of-order issue. 00162 // 00163 for (unsigned i = termMvec.size(); i > first+1; --i) { 00164 SchedGraphNode* toNode = getGraphNodeForInstr(termMvec[i-1]); 00165 assert(toNode && "No node for instr generated for branch/ret?"); 00166 00167 for (unsigned j = i-1; j != 0; --j) 00168 if (mii.isBranch(termMvec[j-1]->getOpcode()) || 00169 mii.isReturn(termMvec[j-1]->getOpcode())) { 00170 SchedGraphNode* brNode = getGraphNodeForInstr(termMvec[j-1]); 00171 assert(brNode && "No node for instr generated for branch/ret?"); 00172 (void) new SchedGraphEdge(brNode, toNode, SchedGraphEdge::CtrlDep, 00173 SchedGraphEdge::NonDataDep, 0); 00174 break; // only one incoming edge is enough 00175 } 00176 } 00177 00178 // Add CD edges from each instruction preceding the first branch 00179 // to the first branch. Use a latency of 0 as above. 00180 // 00181 for (unsigned i = first; i != 0; --i) { 00182 SchedGraphNode* fromNode = getGraphNodeForInstr(termMvec[i-1]); 00183 assert(fromNode && "No node for instr generated for branch?"); 00184 (void) new SchedGraphEdge(fromNode, firstBrNode, SchedGraphEdge::CtrlDep, 00185 SchedGraphEdge::NonDataDep, 0); 00186 } 00187 00188 // Now add CD edges to the first branch instruction in the sequence from 00189 // all preceding instructions in the basic block. Use 0 latency again. 00190 // 00191 for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E; ++I){ 00192 if (&*I == termMvec[first]) // reached the first branch 00193 break; 00194 00195 SchedGraphNode* fromNode = getGraphNodeForInstr(I); 00196 if (fromNode == NULL) 00197 continue; // dummy instruction, e.g., PHI 00198 00199 (void) new SchedGraphEdge(fromNode, firstBrNode, 00200 SchedGraphEdge::CtrlDep, 00201 SchedGraphEdge::NonDataDep, 0); 00202 00203 // If we find any other machine instructions (other than due to 00204 // the terminator) that also have delay slots, add an outgoing edge 00205 // from the instruction to the instructions in the delay slots. 00206 // 00207 unsigned d = mii.getNumDelaySlots(I->getOpcode()); 00208 00209 MachineBasicBlock::iterator J = I; ++J; 00210 for (unsigned j=1; j <= d; j++, ++J) { 00211 SchedGraphNode* toNode = this->getGraphNodeForInstr(J); 00212 assert(toNode && "No node for machine instr in delay slot?"); 00213 (void) new SchedGraphEdge(fromNode, toNode, 00214 SchedGraphEdge::CtrlDep, 00215 SchedGraphEdge::NonDataDep, 0); 00216 } 00217 } 00218 } 00219 00220 static const int SG_LOAD_REF = 0; 00221 static const int SG_STORE_REF = 1; 00222 static const int SG_CALL_REF = 2; 00223 00224 static const unsigned int SG_DepOrderArray[][3] = { 00225 { SchedGraphEdge::NonDataDep, 00226 SchedGraphEdge::AntiDep, 00227 SchedGraphEdge::AntiDep }, 00228 { SchedGraphEdge::TrueDep, 00229 SchedGraphEdge::OutputDep, 00230 SchedGraphEdge::TrueDep | SchedGraphEdge::OutputDep }, 00231 { SchedGraphEdge::TrueDep, 00232 SchedGraphEdge::AntiDep | SchedGraphEdge::OutputDep, 00233 SchedGraphEdge::TrueDep | SchedGraphEdge::AntiDep 00234 | SchedGraphEdge::OutputDep } 00235 }; 00236 00237 00238 // Add a dependence edge between every pair of machine load/store/call 00239 // instructions, where at least one is a store or a call. 00240 // Use latency 1 just to ensure that memory operations are ordered; 00241 // latency does not otherwise matter (true dependences enforce that). 00242 // 00243 void SchedGraph::addMemEdges(const std::vector<SchedGraphNode*>& memNodeVec, 00244 const TargetMachine& target) { 00245 const TargetInstrInfo& mii = *target.getInstrInfo(); 00246 00247 // Instructions in memNodeVec are in execution order within the basic block, 00248 // so simply look at all pairs <memNodeVec[i], memNodeVec[j: j > i]>. 00249 // 00250 for (unsigned im=0, NM=memNodeVec.size(); im < NM; im++) { 00251 MachineOpCode fromOpCode = memNodeVec[im]->getOpcode(); 00252 int fromType = (mii.isCall(fromOpCode)? SG_CALL_REF 00253 : (mii.isLoad(fromOpCode)? SG_LOAD_REF 00254 : SG_STORE_REF)); 00255 for (unsigned jm=im+1; jm < NM; jm++) { 00256 MachineOpCode toOpCode = memNodeVec[jm]->getOpcode(); 00257 int toType = (mii.isCall(toOpCode)? SG_CALL_REF 00258 : (mii.isLoad(toOpCode)? SG_LOAD_REF 00259 : SG_STORE_REF)); 00260 00261 if (fromType != SG_LOAD_REF || toType != SG_LOAD_REF) 00262 (void) new SchedGraphEdge(memNodeVec[im], memNodeVec[jm], 00263 SchedGraphEdge::MemoryDep, 00264 SG_DepOrderArray[fromType][toType], 1); 00265 } 00266 } 00267 } 00268 00269 // Add edges from/to CC reg instrs to/from call instrs. 00270 // Essentially this prevents anything that sets or uses a CC reg from being 00271 // reordered w.r.t. a call. 00272 // Use a latency of 0 because we only need to prevent out-of-order issue, 00273 // like with control dependences. 00274 // 00275 void SchedGraph::addCallDepEdges(const std::vector<SchedGraphNode*>& callDepNodeVec, 00276 const TargetMachine& target) { 00277 const TargetInstrInfo& mii = *target.getInstrInfo(); 00278 00279 // Instructions in memNodeVec are in execution order within the basic block, 00280 // so simply look at all pairs <memNodeVec[i], memNodeVec[j: j > i]>. 00281 // 00282 for (unsigned ic=0, NC=callDepNodeVec.size(); ic < NC; ic++) 00283 if (mii.isCall(callDepNodeVec[ic]->getOpcode())) { 00284 // Add SG_CALL_REF edges from all preds to this instruction. 00285 for (unsigned jc=0; jc < ic; jc++) 00286 (void) new SchedGraphEdge(callDepNodeVec[jc], callDepNodeVec[ic], 00287 SchedGraphEdge::MachineRegister, 00288 MachineIntRegsRID, 0); 00289 00290 // And do the same from this instruction to all successors. 00291 for (unsigned jc=ic+1; jc < NC; jc++) 00292 (void) new SchedGraphEdge(callDepNodeVec[ic], callDepNodeVec[jc], 00293 SchedGraphEdge::MachineRegister, 00294 MachineIntRegsRID, 0); 00295 } 00296 00297 #ifdef CALL_DEP_NODE_VEC_CANNOT_WORK 00298 // Find the call instruction nodes and put them in a vector. 00299 std::vector<SchedGraphNode*> callNodeVec; 00300 for (unsigned im=0, NM=memNodeVec.size(); im < NM; im++) 00301 if (mii.isCall(memNodeVec[im]->getOpcode())) 00302 callNodeVec.push_back(memNodeVec[im]); 00303 00304 // Now walk the entire basic block, looking for CC instructions *and* 00305 // call instructions, and keep track of the order of the instructions. 00306 // Use the call node vec to quickly find earlier and later call nodes 00307 // relative to the current CC instruction. 00308 // 00309 int lastCallNodeIdx = -1; 00310 for (unsigned i=0, N=bbMvec.size(); i < N; i++) 00311 if (mii.isCall(bbMvec[i]->getOpcode())) { 00312 ++lastCallNodeIdx; 00313 for ( ; lastCallNodeIdx < (int)callNodeVec.size(); ++lastCallNodeIdx) 00314 if (callNodeVec[lastCallNodeIdx]->getMachineInstr() == bbMvec[i]) 00315 break; 00316 assert(lastCallNodeIdx < (int)callNodeVec.size() && "Missed Call?"); 00317 } 00318 else if (mii.isCCInstr(bbMvec[i]->getOpcode())) { 00319 // Add incoming/outgoing edges from/to preceding/later calls 00320 SchedGraphNode* ccNode = this->getGraphNodeForInstr(bbMvec[i]); 00321 int j=0; 00322 for ( ; j <= lastCallNodeIdx; j++) 00323 (void) new SchedGraphEdge(callNodeVec[j], ccNode, 00324 MachineCCRegsRID, 0); 00325 for ( ; j < (int) callNodeVec.size(); j++) 00326 (void) new SchedGraphEdge(ccNode, callNodeVec[j], 00327 MachineCCRegsRID, 0); 00328 } 00329 #endif 00330 } 00331 00332 00333 void SchedGraph::addMachineRegEdges(RegToRefVecMap& regToRefVecMap, 00334 const TargetMachine& target) { 00335 // This code assumes that two registers with different numbers are 00336 // not aliased! 00337 // 00338 for (RegToRefVecMap::iterator I = regToRefVecMap.begin(); 00339 I != regToRefVecMap.end(); ++I) { 00340 int regNum = (*I).first; 00341 RefVec& regRefVec = (*I).second; 00342 00343 // regRefVec is ordered by control flow order in the basic block 00344 for (unsigned i=0; i < regRefVec.size(); ++i) { 00345 SchedGraphNode* node = regRefVec[i].first; 00346 unsigned int opNum = regRefVec[i].second; 00347 const MachineOperand& mop = 00348 node->getMachineInstr()->getExplOrImplOperand(opNum); 00349 bool isDef = mop.isDef() && !mop.isUse(); 00350 bool isDefAndUse = mop.isDef() && mop.isUse(); 00351 00352 for (unsigned p=0; p < i; ++p) { 00353 SchedGraphNode* prevNode = regRefVec[p].first; 00354 if (prevNode != node) { 00355 unsigned int prevOpNum = regRefVec[p].second; 00356 const MachineOperand& prevMop = 00357 prevNode->getMachineInstr()->getExplOrImplOperand(prevOpNum); 00358 bool prevIsDef = prevMop.isDef() && !prevMop.isUse(); 00359 bool prevIsDefAndUse = prevMop.isDef() && prevMop.isUse(); 00360 if (isDef) { 00361 if (prevIsDef) 00362 new SchedGraphEdge(prevNode, node, regNum, 00363 SchedGraphEdge::OutputDep); 00364 if (!prevIsDef || prevIsDefAndUse) 00365 new SchedGraphEdge(prevNode, node, regNum, 00366 SchedGraphEdge::AntiDep); 00367 } 00368 00369 if (prevIsDef) 00370 if (!isDef || isDefAndUse) 00371 new SchedGraphEdge(prevNode, node, regNum, 00372 SchedGraphEdge::TrueDep); 00373 } 00374 } 00375 } 00376 } 00377 } 00378 00379 00380 // Adds dependences to/from refNode from/to all other defs 00381 // in the basic block. refNode may be a use, a def, or both. 00382 // We do not consider other uses because we are not building use-use deps. 00383 // 00384 void SchedGraph::addEdgesForValue(SchedGraphNode* refNode, 00385 const RefVec& defVec, 00386 const Value* defValue, 00387 bool refNodeIsDef, 00388 bool refNodeIsUse, 00389 const TargetMachine& target) { 00390 // Add true or output dep edges from all def nodes before refNode in BB. 00391 // Add anti or output dep edges to all def nodes after refNode. 00392 for (RefVec::const_iterator I=defVec.begin(), E=defVec.end(); I != E; ++I) { 00393 if ((*I).first == refNode) 00394 continue; // Dont add any self-loops 00395 00396 if ((*I).first->getOrigIndexInBB() < refNode->getOrigIndexInBB()) { 00397 // (*).first is before refNode 00398 if (refNodeIsDef && !refNodeIsUse) 00399 (void) new SchedGraphEdge((*I).first, refNode, defValue, 00400 SchedGraphEdge::OutputDep); 00401 if (refNodeIsUse) 00402 (void) new SchedGraphEdge((*I).first, refNode, defValue, 00403 SchedGraphEdge::TrueDep); 00404 } else { 00405 // (*).first is after refNode 00406 if (refNodeIsDef && !refNodeIsUse) 00407 (void) new SchedGraphEdge(refNode, (*I).first, defValue, 00408 SchedGraphEdge::OutputDep); 00409 if (refNodeIsUse) 00410 (void) new SchedGraphEdge(refNode, (*I).first, defValue, 00411 SchedGraphEdge::AntiDep); 00412 } 00413 } 00414 } 00415 00416 00417 void SchedGraph::addEdgesForInstruction(const MachineInstr& MI, 00418 const ValueToDefVecMap& valueToDefVecMap, 00419 const TargetMachine& target) { 00420 SchedGraphNode* node = getGraphNodeForInstr(&MI); 00421 if (node == NULL) 00422 return; 00423 00424 // Add edges for all operands of the machine instruction. 00425 // 00426 for (unsigned i = 0, numOps = MI.getNumOperands(); i != numOps; ++i) { 00427 switch (MI.getOperand(i).getType()) { 00428 case MachineOperand::MO_VirtualRegister: 00429 case MachineOperand::MO_CCRegister: 00430 if (const Value* srcI = MI.getOperand(i).getVRegValue()) { 00431 ValueToDefVecMap::const_iterator I = valueToDefVecMap.find(srcI); 00432 if (I != valueToDefVecMap.end()) 00433 addEdgesForValue(node, I->second, srcI, 00434 MI.getOperand(i).isDef(), MI.getOperand(i).isUse(), 00435 target); 00436 } 00437 break; 00438 00439 case MachineOperand::MO_MachineRegister: 00440 break; 00441 00442 case MachineOperand::MO_SignExtendedImmed: 00443 case MachineOperand::MO_UnextendedImmed: 00444 case MachineOperand::MO_PCRelativeDisp: 00445 case MachineOperand::MO_ConstantPoolIndex: 00446 break; // nothing to do for immediate fields 00447 00448 default: 00449 assert(0 && "Unknown machine operand type in SchedGraph builder"); 00450 break; 00451 } 00452 } 00453 00454 // Add edges for values implicitly used by the machine instruction. 00455 // Examples include function arguments to a Call instructions or the return 00456 // value of a Ret instruction. 00457 // 00458 for (unsigned i=0, N=MI.getNumImplicitRefs(); i < N; ++i) 00459 if (MI.getImplicitOp(i).isUse()) 00460 if (const Value* srcI = MI.getImplicitRef(i)) { 00461 ValueToDefVecMap::const_iterator I = valueToDefVecMap.find(srcI); 00462 if (I != valueToDefVecMap.end()) 00463 addEdgesForValue(node, I->second, srcI, 00464 MI.getImplicitOp(i).isDef(), 00465 MI.getImplicitOp(i).isUse(), target); 00466 } 00467 } 00468 00469 00470 void SchedGraph::findDefUseInfoAtInstr(const TargetMachine& target, 00471 SchedGraphNode* node, 00472 std::vector<SchedGraphNode*>& memNodeVec, 00473 std::vector<SchedGraphNode*>& callDepNodeVec, 00474 RegToRefVecMap& regToRefVecMap, 00475 ValueToDefVecMap& valueToDefVecMap) { 00476 const TargetInstrInfo& mii = *target.getInstrInfo(); 00477 00478 MachineOpCode opCode = node->getOpcode(); 00479 00480 if (mii.isCall(opCode) || mii.isCCInstr(opCode)) 00481 callDepNodeVec.push_back(node); 00482 00483 if (mii.isLoad(opCode) || mii.isStore(opCode) || mii.isCall(opCode)) 00484 memNodeVec.push_back(node); 00485 00486 // Collect the register references and value defs. for explicit operands 00487 // 00488 const MachineInstr& MI = *node->getMachineInstr(); 00489 for (int i=0, numOps = (int) MI.getNumOperands(); i < numOps; i++) { 00490 const MachineOperand& mop = MI.getOperand(i); 00491 00492 // if this references a register other than the hardwired 00493 // "zero" register, record the reference. 00494 if (mop.hasAllocatedReg()) { 00495 unsigned regNum = mop.getReg(); 00496 00497 // If this is not a dummy zero register, record the reference in order 00498 if (regNum != target.getRegInfo()->getZeroRegNum()) 00499 regToRefVecMap[mop.getReg()] 00500 .push_back(std::make_pair(node, i)); 00501 00502 // If this is a volatile register, add the instruction to callDepVec 00503 // (only if the node is not already on the callDepVec!) 00504 if (callDepNodeVec.size() == 0 || callDepNodeVec.back() != node) 00505 { 00506 unsigned rcid; 00507 int regInClass = target.getRegInfo()->getClassRegNum(regNum, rcid); 00508 if (target.getRegInfo()->getMachineRegClass(rcid) 00509 ->isRegVolatile(regInClass)) 00510 callDepNodeVec.push_back(node); 00511 } 00512 00513 continue; // nothing more to do 00514 } 00515 00516 // ignore all other non-def operands 00517 if (!MI.getOperand(i).isDef()) 00518 continue; 00519 00520 // We must be defining a value. 00521 assert((mop.getType() == MachineOperand::MO_VirtualRegister || 00522 mop.getType() == MachineOperand::MO_CCRegister) 00523 && "Do not expect any other kind of operand to be defined!"); 00524 assert(mop.getVRegValue() != NULL && "Null value being defined?"); 00525 00526 valueToDefVecMap[mop.getVRegValue()].push_back(std::make_pair(node, i)); 00527 } 00528 00529 // 00530 // Collect value defs. for implicit operands. They may have allocated 00531 // physical registers also. 00532 // 00533 for (unsigned i=0, N = MI.getNumImplicitRefs(); i != N; ++i) { 00534 const MachineOperand& mop = MI.getImplicitOp(i); 00535 if (mop.hasAllocatedReg()) { 00536 unsigned regNum = mop.getReg(); 00537 if (regNum != target.getRegInfo()->getZeroRegNum()) 00538 regToRefVecMap[mop.getReg()] 00539 .push_back(std::make_pair(node, i + MI.getNumOperands())); 00540 continue; // nothing more to do 00541 } 00542 00543 if (mop.isDef()) { 00544 assert(MI.getImplicitRef(i) != NULL && "Null value being defined?"); 00545 valueToDefVecMap[MI.getImplicitRef(i)].push_back( 00546 std::make_pair(node, -i)); 00547 } 00548 } 00549 } 00550 00551 00552 void SchedGraph::buildNodesForBB(const TargetMachine& target, 00553 MachineBasicBlock& MBB, 00554 std::vector<SchedGraphNode*>& memNodeVec, 00555 std::vector<SchedGraphNode*>& callDepNodeVec, 00556 RegToRefVecMap& regToRefVecMap, 00557 ValueToDefVecMap& valueToDefVecMap) { 00558 const TargetInstrInfo& mii = *target.getInstrInfo(); 00559 00560 // Build graph nodes for each VM instruction and gather def/use info. 00561 // Do both those together in a single pass over all machine instructions. 00562 unsigned i = 0; 00563 for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E; 00564 ++I, ++i) 00565 if (I->getOpcode() != V9::PHI) { 00566 SchedGraphNode* node = new SchedGraphNode(getNumNodes(), &MBB, i, target); 00567 noteGraphNodeForInstr(I, node); 00568 00569 // Remember all register references and value defs 00570 findDefUseInfoAtInstr(target, node, memNodeVec, callDepNodeVec, 00571 regToRefVecMap, valueToDefVecMap); 00572 } 00573 } 00574 00575 00576 void SchedGraph::buildGraph(const TargetMachine& target) { 00577 // Use this data structure to note all machine operands that compute 00578 // ordinary LLVM values. These must be computed defs (i.e., instructions). 00579 // Note that there may be multiple machine instructions that define 00580 // each Value. 00581 ValueToDefVecMap valueToDefVecMap; 00582 00583 // Use this data structure to note all memory instructions. 00584 // We use this to add memory dependence edges without a second full walk. 00585 std::vector<SchedGraphNode*> memNodeVec; 00586 00587 // Use this data structure to note all instructions that access physical 00588 // registers that can be modified by a call (including call instructions) 00589 std::vector<SchedGraphNode*> callDepNodeVec; 00590 00591 // Use this data structure to note any uses or definitions of 00592 // machine registers so we can add edges for those later without 00593 // extra passes over the nodes. 00594 // The vector holds an ordered list of references to the machine reg, 00595 // ordered according to control-flow order. This only works for a 00596 // single basic block, hence the assertion. Each reference is identified 00597 // by the pair: <node, operand-number>. 00598 // 00599 RegToRefVecMap regToRefVecMap; 00600 00601 // Make a dummy root node. We'll add edges to the real roots later. 00602 graphRoot = new SchedGraphNode(0, NULL, -1, target); 00603 graphLeaf = new SchedGraphNode(1, NULL, -1, target); 00604 00605 //---------------------------------------------------------------- 00606 // First add nodes for all the machine instructions in the basic block 00607 // because this greatly simplifies identifying which edges to add. 00608 // Do this one VM instruction at a time since the SchedGraphNode needs that. 00609 // Also, remember the load/store instructions to add memory deps later. 00610 //---------------------------------------------------------------- 00611 00612 buildNodesForBB(target, MBB, memNodeVec, callDepNodeVec, 00613 regToRefVecMap, valueToDefVecMap); 00614 00615 //---------------------------------------------------------------- 00616 // Now add edges for the following (all are incoming edges except (4)): 00617 // (1) operands of the machine instruction, including hidden operands 00618 // (2) machine register dependences 00619 // (3) memory load/store dependences 00620 // (3) other resource dependences for the machine instruction, if any 00621 // (4) output dependences when multiple machine instructions define the 00622 // same value; all must have been generated from a single VM instrn 00623 // (5) control dependences to branch instructions generated for the 00624 // terminator instruction of the BB. Because of delay slots and 00625 // 2-way conditional branches, multiple CD edges are needed 00626 // (see addCDEdges for details). 00627 // Also, note any uses or defs of machine registers. 00628 // 00629 //---------------------------------------------------------------- 00630 00631 // First, add edges to the terminator instruction of the basic block. 00632 this->addCDEdges(MBB.getBasicBlock()->getTerminator(), target); 00633 00634 // Then add memory dep edges: store->load, load->store, and store->store. 00635 // Call instructions are treated as both load and store. 00636 this->addMemEdges(memNodeVec, target); 00637 00638 // Then add edges between call instructions and CC set/use instructions 00639 this->addCallDepEdges(callDepNodeVec, target); 00640 00641 // Then add incoming def-use (SSA) edges for each machine instruction. 00642 for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E; ++I) 00643 addEdgesForInstruction(*I, valueToDefVecMap, target); 00644 00645 // Then add edges for dependences on machine registers 00646 this->addMachineRegEdges(regToRefVecMap, target); 00647 00648 // Finally, add edges from the dummy root and to dummy leaf 00649 this->addDummyEdges(); 00650 } 00651 00652 00653 // 00654 // class SchedGraphSet 00655 // 00656 SchedGraphSet::SchedGraphSet(const Function* _function, 00657 const TargetMachine& target) : 00658 function(_function) { 00659 buildGraphsForMethod(function, target); 00660 } 00661 00662 SchedGraphSet::~SchedGraphSet() { 00663 // delete all the graphs 00664 for(iterator I = begin(), E = end(); I != E; ++I) 00665 delete *I; // destructor is a friend 00666 } 00667 00668 00669 void SchedGraphSet::dump() const { 00670 std::cerr << "======== Sched graphs for function `" << function->getName() 00671 << "' ========\n\n"; 00672 00673 for (const_iterator I=begin(); I != end(); ++I) 00674 (*I)->dump(); 00675 00676 std::cerr << "\n====== End graphs for function `" << function->getName() 00677 << "' ========\n\n"; 00678 } 00679 00680 00681 void SchedGraphSet::buildGraphsForMethod(const Function *F, 00682 const TargetMachine& target) { 00683 MachineFunction &MF = MachineFunction::get(F); 00684 for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) 00685 addGraph(new SchedGraph(*I, target)); 00686 } 00687 00688 00689 void SchedGraphEdge::print(std::ostream &os) const { 00690 os << "edge [" << src->getNodeId() << "] -> [" 00691 << sink->getNodeId() << "] : "; 00692 00693 switch(depType) { 00694 case SchedGraphEdge::CtrlDep: 00695 os<< "Control Dep"; 00696 break; 00697 case SchedGraphEdge::ValueDep: 00698 os<< "Reg Value " << *val; 00699 break; 00700 case SchedGraphEdge::MemoryDep: 00701 os<< "Memory Dep"; 00702 break; 00703 case SchedGraphEdge::MachineRegister: 00704 os<< "Reg " << machineRegNum; 00705 break; 00706 case SchedGraphEdge::MachineResource: 00707 os<<"Resource "<< resourceId; 00708 break; 00709 default: 00710 assert(0); 00711 break; 00712 } 00713 00714 os << " : delay = " << minDelay << "\n"; 00715 } 00716 00717 void SchedGraphNode::print(std::ostream &os) const { 00718 os << std::string(8, ' ') 00719 << "Node " << ID << " : " 00720 << "latency = " << latency << "\n" << std::string(12, ' '); 00721 00722 if (getMachineInstr() == NULL) 00723 os << "(Dummy node)\n"; 00724 else { 00725 os << *getMachineInstr() << "\n" << std::string(12, ' '); 00726 os << inEdges.size() << " Incoming Edges:\n"; 00727 for (unsigned i=0, N = inEdges.size(); i < N; i++) 00728 os << std::string(16, ' ') << *inEdges[i]; 00729 00730 os << std::string(12, ' ') << outEdges.size() 00731 << " Outgoing Edges:\n"; 00732 for (unsigned i=0, N= outEdges.size(); i < N; i++) 00733 os << std::string(16, ' ') << *outEdges[i]; 00734 } 00735 } 00736 00737 } // End llvm namespace