LLVM API Documentation
00001 //===-- MSchedGraph.cpp - Scheduling Graph ----------------------*- C++ -*-===// 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 // A graph class for dependencies. This graph only contains true, anti, and 00011 // output data dependencies for a given MachineBasicBlock. Dependencies 00012 // across iterations are also computed. Unless data dependence analysis 00013 // is provided, a conservative approach of adding dependencies between all 00014 // loads and stores is taken. 00015 //===----------------------------------------------------------------------===// 00016 00017 #define DEBUG_TYPE "ModuloSched" 00018 #include "MSchedGraph.h" 00019 #include "../SparcV9RegisterInfo.h" 00020 #include "../MachineCodeForInstruction.h" 00021 #include "llvm/BasicBlock.h" 00022 #include "llvm/Constants.h" 00023 #include "llvm/Instructions.h" 00024 #include "llvm/Type.h" 00025 #include "llvm/CodeGen/MachineBasicBlock.h" 00026 #include "llvm/Target/TargetInstrInfo.h" 00027 #include "llvm/Support/Debug.h" 00028 #include <cstdlib> 00029 #include <algorithm> 00030 #include <set> 00031 #include <iostream> 00032 using namespace llvm; 00033 00034 //MSchedGraphNode constructor 00035 MSchedGraphNode::MSchedGraphNode(const MachineInstr* inst, 00036 MSchedGraph *graph, unsigned idx, 00037 unsigned late, bool isBranch) 00038 : Inst(inst), Parent(graph), index(idx), latency(late), 00039 isBranchInstr(isBranch) { 00040 00041 //Add to the graph 00042 graph->addNode(inst, this); 00043 } 00044 00045 //MSchedGraphNode copy constructor 00046 MSchedGraphNode::MSchedGraphNode(const MSchedGraphNode &N) 00047 : Predecessors(N.Predecessors), Successors(N.Successors) { 00048 00049 Inst = N.Inst; 00050 Parent = N.Parent; 00051 index = N.index; 00052 latency = N.latency; 00053 isBranchInstr = N.isBranchInstr; 00054 00055 } 00056 00057 //Print the node (instruction and latency) 00058 void MSchedGraphNode::print(std::ostream &os) const { 00059 os << "MSchedGraphNode: Inst=" << *Inst << ", latency= " << latency << "\n"; 00060 } 00061 00062 00063 //Get the edge from a predecessor to this node 00064 MSchedGraphEdge MSchedGraphNode::getInEdge(MSchedGraphNode *pred) { 00065 //Loop over all the successors of our predecessor 00066 //return the edge the corresponds to this in edge 00067 for (MSchedGraphNode::succ_iterator I = pred->succ_begin(), 00068 E = pred->succ_end(); I != E; ++I) { 00069 if (*I == this) 00070 return I.getEdge(); 00071 } 00072 assert(0 && "Should have found edge between this node and its predecessor!"); 00073 abort(); 00074 } 00075 00076 //Get the iteration difference for the edge from this node to its successor 00077 unsigned MSchedGraphNode::getIteDiff(MSchedGraphNode *succ) { 00078 for(std::vector<MSchedGraphEdge>::iterator I = Successors.begin(), 00079 E = Successors.end(); 00080 I != E; ++I) { 00081 if(I->getDest() == succ) 00082 return I->getIteDiff(); 00083 } 00084 return 0; 00085 } 00086 00087 //Get the index into the vector of edges for the edge from pred to this node 00088 unsigned MSchedGraphNode::getInEdgeNum(MSchedGraphNode *pred) { 00089 //Loop over all the successors of our predecessor 00090 //return the edge the corresponds to this in edge 00091 int count = 0; 00092 for(MSchedGraphNode::succ_iterator I = pred->succ_begin(), 00093 E = pred->succ_end(); 00094 I != E; ++I) { 00095 if(*I == this) 00096 return count; 00097 count++; 00098 } 00099 assert(0 && "Should have found edge between this node and its predecessor!"); 00100 abort(); 00101 } 00102 00103 //Determine if succ is a successor of this node 00104 bool MSchedGraphNode::isSuccessor(MSchedGraphNode *succ) { 00105 for(succ_iterator I = succ_begin(), E = succ_end(); I != E; ++I) 00106 if(*I == succ) 00107 return true; 00108 return false; 00109 } 00110 00111 //Dtermine if pred is a predecessor of this node 00112 bool MSchedGraphNode::isPredecessor(MSchedGraphNode *pred) { 00113 if(std::find( Predecessors.begin(), Predecessors.end(), 00114 pred) != Predecessors.end()) 00115 return true; 00116 else 00117 return false; 00118 } 00119 00120 //Add a node to the graph 00121 void MSchedGraph::addNode(const MachineInstr *MI, 00122 MSchedGraphNode *node) { 00123 00124 //Make sure node does not already exist 00125 assert(GraphMap.find(MI) == GraphMap.end() 00126 && "New MSchedGraphNode already exists for this instruction"); 00127 00128 GraphMap[MI] = node; 00129 } 00130 00131 //Delete a node to the graph 00132 void MSchedGraph::deleteNode(MSchedGraphNode *node) { 00133 00134 //Delete the edge to this node from all predecessors 00135 while(node->pred_size() > 0) { 00136 //DEBUG(std::cerr << "Delete edge from: " << **P << " to " << *node << "\n"); 00137 MSchedGraphNode *pred = *(node->pred_begin()); 00138 pred->deleteSuccessor(node); 00139 } 00140 00141 //Remove this node from the graph 00142 GraphMap.erase(node->getInst()); 00143 00144 } 00145 00146 00147 //Create a graph for a machine block. The ignoreInstrs map is so that 00148 //we ignore instructions associated to the index variable since this 00149 //is a special case in Modulo Scheduling. We only want to deal with 00150 //the body of the loop. 00151 MSchedGraph::MSchedGraph(const MachineBasicBlock *bb, 00152 const TargetMachine &targ, 00153 std::map<const MachineInstr*, unsigned> &ignoreInstrs, 00154 DependenceAnalyzer &DA, 00155 std::map<MachineInstr*, Instruction*> &machineTollvm) 00156 : Target(targ) { 00157 00158 //Make sure BB is not null, 00159 assert(bb != NULL && "Basic Block is null"); 00160 00161 BBs.push_back(bb); 00162 00163 //Create nodes and edges for this BB 00164 buildNodesAndEdges(ignoreInstrs, DA, machineTollvm); 00165 00166 //Experimental! 00167 //addBranchEdges(); 00168 } 00169 00170 //Create a graph for a machine block. The ignoreInstrs map is so that 00171 //we ignore instructions associated to the index variable since this 00172 //is a special case in Modulo Scheduling. We only want to deal with 00173 //the body of the loop. 00174 MSchedGraph::MSchedGraph(std::vector<const MachineBasicBlock*> &bbs, 00175 const TargetMachine &targ, 00176 std::map<const MachineInstr*, unsigned> &ignoreInstrs, 00177 DependenceAnalyzer &DA, 00178 std::map<MachineInstr*, Instruction*> &machineTollvm) 00179 : BBs(bbs), Target(targ) { 00180 00181 //Make sure there is at least one BB and it is not null, 00182 assert(((bbs.size() >= 1) && bbs[1] != NULL) && "Basic Block is null"); 00183 00184 //Create nodes and edges for this BB 00185 buildNodesAndEdges(ignoreInstrs, DA, machineTollvm); 00186 00187 //Experimental! 00188 //addBranchEdges(); 00189 } 00190 00191 00192 //Copies the graph and keeps a map from old to new nodes 00193 MSchedGraph::MSchedGraph(const MSchedGraph &G, 00194 std::map<MSchedGraphNode*, MSchedGraphNode*> &newNodes) 00195 : Target(G.Target) { 00196 00197 BBs = G.BBs; 00198 00199 std::map<MSchedGraphNode*, MSchedGraphNode*> oldToNew; 00200 //Copy all nodes 00201 for(MSchedGraph::const_iterator N = G.GraphMap.begin(), 00202 NE = G.GraphMap.end(); N != NE; ++N) { 00203 00204 MSchedGraphNode *newNode = new MSchedGraphNode(*(N->second)); 00205 oldToNew[&*(N->second)] = newNode; 00206 newNodes[newNode] = &*(N->second); 00207 GraphMap[&*(N->first)] = newNode; 00208 } 00209 00210 //Loop over nodes and update edges to point to new nodes 00211 for(MSchedGraph::iterator N = GraphMap.begin(), NE = GraphMap.end(); 00212 N != NE; ++N) { 00213 00214 //Get the node we are dealing with 00215 MSchedGraphNode *node = &*(N->second); 00216 00217 node->setParent(this); 00218 00219 //Loop over nodes successors and predecessors and update to the new nodes 00220 for(unsigned i = 0; i < node->pred_size(); ++i) { 00221 node->setPredecessor(i, oldToNew[node->getPredecessor(i)]); 00222 } 00223 00224 for(unsigned i = 0; i < node->succ_size(); ++i) { 00225 MSchedGraphEdge *edge = node->getSuccessor(i); 00226 MSchedGraphNode *oldDest = edge->getDest(); 00227 edge->setDest(oldToNew[oldDest]); 00228 } 00229 } 00230 } 00231 00232 //Deconstructor, deletes all nodes in the graph 00233 MSchedGraph::~MSchedGraph () { 00234 for(MSchedGraph::iterator I = GraphMap.begin(), E = GraphMap.end(); 00235 I != E; ++I) 00236 delete I->second; 00237 } 00238 00239 //Print out graph 00240 void MSchedGraph::print(std::ostream &os) const { 00241 for(MSchedGraph::const_iterator N = GraphMap.begin(), NE = GraphMap.end(); 00242 N != NE; ++N) { 00243 00244 //Get the node we are dealing with 00245 MSchedGraphNode *node = &*(N->second); 00246 00247 os << "Node Start\n"; 00248 node->print(os); 00249 os << "Successors:\n"; 00250 //print successors 00251 for(unsigned i = 0; i < node->succ_size(); ++i) { 00252 MSchedGraphEdge *edge = node->getSuccessor(i); 00253 MSchedGraphNode *oldDest = edge->getDest(); 00254 oldDest->print(os); 00255 } 00256 os << "Node End\n"; 00257 } 00258 } 00259 00260 //Calculate total delay 00261 int MSchedGraph::totalDelay() { 00262 int sum = 0; 00263 00264 for(MSchedGraph::const_iterator N = GraphMap.begin(), NE = GraphMap.end(); 00265 N != NE; ++N) { 00266 00267 //Get the node we are dealing with 00268 MSchedGraphNode *node = &*(N->second); 00269 sum += node->getLatency(); 00270 } 00271 return sum; 00272 } 00273 //Experimental code to add edges from the branch to all nodes dependent upon it. 00274 void hasPath(MSchedGraphNode *node, std::set<MSchedGraphNode*> &visited, 00275 std::set<MSchedGraphNode*> &branches, MSchedGraphNode *startNode, 00276 std::set<std::pair<MSchedGraphNode*,MSchedGraphNode*> > &newEdges ) { 00277 00278 visited.insert(node); 00279 DEBUG(std::cerr << "Visiting: " << *node << "\n"); 00280 //Loop over successors 00281 for(unsigned i = 0; i < node->succ_size(); ++i) { 00282 MSchedGraphEdge *edge = node->getSuccessor(i); 00283 MSchedGraphNode *dest = edge->getDest(); 00284 if(branches.count(dest)) 00285 newEdges.insert(std::make_pair(dest, startNode)); 00286 00287 //only visit if we have not already 00288 else if(!visited.count(dest)) { 00289 if(edge->getIteDiff() == 0) 00290 hasPath(dest, visited, branches, startNode, newEdges);} 00291 00292 } 00293 00294 } 00295 00296 //Experimental code to add edges from the branch to all nodes dependent upon it. 00297 void MSchedGraph::addBranchEdges() { 00298 std::set<MSchedGraphNode*> branches; 00299 std::set<MSchedGraphNode*> nodes; 00300 00301 for(MSchedGraph::iterator I = GraphMap.begin(), E = GraphMap.end(); 00302 I != E; ++I) { 00303 if(I->second->isBranch()) 00304 if(I->second->hasPredecessors()) 00305 branches.insert(I->second); 00306 } 00307 00308 //See if there is a path first instruction to the branches, if so, add an 00309 //iteration dependence between that node and the branch 00310 std::set<std::pair<MSchedGraphNode*, MSchedGraphNode*> > newEdges; 00311 for(MSchedGraph::iterator I = GraphMap.begin(), E = GraphMap.end(); 00312 I != E; ++I) { 00313 std::set<MSchedGraphNode*> visited; 00314 hasPath((I->second), visited, branches, (I->second), newEdges); 00315 } 00316 00317 //Spit out all edges we are going to add 00318 unsigned min = GraphMap.size(); 00319 if(newEdges.size() == 1) { 00320 ((newEdges.begin())->first)->addOutEdge(((newEdges.begin())->second), 00321 MSchedGraphEdge::BranchDep, 00322 MSchedGraphEdge::NonDataDep, 1); 00323 } 00324 else { 00325 00326 unsigned count = 0; 00327 MSchedGraphNode *start; 00328 MSchedGraphNode *end; 00329 for(std::set<std::pair<MSchedGraphNode*, MSchedGraphNode*> >::iterator I = newEdges.begin(), E = newEdges.end(); I != E; ++I) { 00330 00331 DEBUG(std::cerr << "Branch Edge from: " << *(I->first) << " to " << *(I->second) << "\n"); 00332 00333 // if(I->second->getIndex() <= min) { 00334 start = I->first; 00335 end = I->second; 00336 //min = I->second->getIndex(); 00337 //} 00338 start->addOutEdge(end, 00339 MSchedGraphEdge::BranchDep, 00340 MSchedGraphEdge::NonDataDep, 1); 00341 } 00342 } 00343 } 00344 00345 00346 //Add edges between the nodes 00347 void MSchedGraph::buildNodesAndEdges(std::map<const MachineInstr*, unsigned> &ignoreInstrs, 00348 DependenceAnalyzer &DA, 00349 std::map<MachineInstr*, Instruction*> &machineTollvm) { 00350 00351 00352 //Get Machine target information for calculating latency 00353 const TargetInstrInfo *MTI = Target.getInstrInfo(); 00354 00355 std::vector<MSchedGraphNode*> memInstructions; 00356 std::map<int, std::vector<OpIndexNodePair> > regNumtoNodeMap; 00357 std::map<const Value*, std::vector<OpIndexNodePair> > valuetoNodeMap; 00358 00359 //Save PHI instructions to deal with later 00360 std::vector<const MachineInstr*> phiInstrs; 00361 unsigned index = 0; 00362 00363 for(std::vector<const MachineBasicBlock*>::iterator B = BBs.begin(), 00364 BE = BBs.end(); B != BE; ++B) { 00365 00366 const MachineBasicBlock *BB = *B; 00367 00368 //Loop over instructions in MBB and add nodes and edges 00369 for (MachineBasicBlock::const_iterator MI = BB->begin(), e = BB->end(); 00370 MI != e; ++MI) { 00371 00372 //Ignore indvar instructions 00373 if(ignoreInstrs.count(MI)) { 00374 ++index; 00375 continue; 00376 } 00377 00378 //Get each instruction of machine basic block, get the delay 00379 //using the op code, create a new node for it, and add to the 00380 //graph. 00381 00382 MachineOpCode opCode = MI->getOpcode(); 00383 int delay; 00384 00385 #if 0 // FIXME: LOOK INTO THIS 00386 //Check if subsequent instructions can be issued before 00387 //the result is ready, if so use min delay. 00388 if(MTI->hasResultInterlock(MIopCode)) 00389 delay = MTI->minLatency(MIopCode); 00390 else 00391 #endif 00392 //Get delay 00393 delay = MTI->maxLatency(opCode); 00394 00395 //Create new node for this machine instruction and add to the graph. 00396 //Create only if not a nop 00397 if(MTI->isNop(opCode)) 00398 continue; 00399 00400 //Sparc BE does not use PHI opcode, so assert on this case 00401 assert(opCode != TargetInstrInfo::PHI && "Did not expect PHI opcode"); 00402 00403 bool isBranch = false; 00404 00405 //We want to flag the branch node to treat it special 00406 if(MTI->isBranch(opCode)) 00407 isBranch = true; 00408 00409 //Node is created and added to the graph automatically 00410 MSchedGraphNode *node = new MSchedGraphNode(MI, this, index, delay, 00411 isBranch); 00412 00413 DEBUG(std::cerr << "Created Node: " << *node << "\n"); 00414 00415 //Check OpCode to keep track of memory operations to add memory 00416 //dependencies later. 00417 if(MTI->isLoad(opCode) || MTI->isStore(opCode)) 00418 memInstructions.push_back(node); 00419 00420 //Loop over all operands, and put them into the register number to 00421 //graph node map for determining dependencies 00422 //If an operands is a use/def, we have an anti dependence to itself 00423 for(unsigned i=0; i < MI->getNumOperands(); ++i) { 00424 //Get Operand 00425 const MachineOperand &mOp = MI->getOperand(i); 00426 00427 //Check if it has an allocated register 00428 if(mOp.hasAllocatedReg()) { 00429 int regNum = mOp.getReg(); 00430 00431 if(regNum != SparcV9::g0) { 00432 //Put into our map 00433 regNumtoNodeMap[regNum].push_back(std::make_pair(i, node)); 00434 } 00435 continue; 00436 } 00437 00438 00439 //Add virtual registers dependencies 00440 //Check if any exist in the value map already and create dependencies 00441 //between them. 00442 if(mOp.getType() == MachineOperand::MO_VirtualRegister 00443 || mOp.getType() == MachineOperand::MO_CCRegister) { 00444 00445 //Make sure virtual register value is not null 00446 assert((mOp.getVRegValue() != NULL) && "Null value is defined"); 00447 00448 //Check if this is a read operation in a phi node, if so DO NOT PROCESS 00449 if(mOp.isUse() && (opCode == TargetInstrInfo::PHI)) { 00450 DEBUG(std::cerr << "Read Operation in a PHI node\n"); 00451 continue; 00452 } 00453 00454 if (const Value* srcI = mOp.getVRegValue()) { 00455 00456 //Find value in the map 00457 std::map<const Value*, std::vector<OpIndexNodePair> >::iterator V 00458 = valuetoNodeMap.find(srcI); 00459 00460 //If there is something in the map already, add edges from 00461 //those instructions 00462 //to this one we are processing 00463 if(V != valuetoNodeMap.end()) { 00464 addValueEdges(V->second, node, mOp.isUse(), mOp.isDef(), phiInstrs); 00465 00466 //Add to value map 00467 V->second.push_back(std::make_pair(i,node)); 00468 } 00469 //Otherwise put it in the map 00470 else 00471 //Put into value map 00472 valuetoNodeMap[mOp.getVRegValue()].push_back(std::make_pair(i, node)); 00473 } 00474 } 00475 } 00476 ++index; 00477 } 00478 00479 //Loop over LLVM BB, examine phi instructions, and add them to our 00480 //phiInstr list to process 00481 const BasicBlock *llvm_bb = BB->getBasicBlock(); 00482 for(BasicBlock::const_iterator I = llvm_bb->begin(), E = llvm_bb->end(); 00483 I != E; ++I) { 00484 if(const PHINode *PN = dyn_cast<PHINode>(I)) { 00485 MachineCodeForInstruction & tempMvec = MachineCodeForInstruction::get(PN); 00486 for (unsigned j = 0; j < tempMvec.size(); j++) { 00487 if(!ignoreInstrs.count(tempMvec[j])) { 00488 DEBUG(std::cerr << "Inserting phi instr into map: " << *tempMvec[j] << "\n"); 00489 phiInstrs.push_back((MachineInstr*) tempMvec[j]); 00490 } 00491 } 00492 } 00493 00494 } 00495 00496 addMemEdges(memInstructions, DA, machineTollvm); 00497 addMachRegEdges(regNumtoNodeMap); 00498 00499 //Finally deal with PHI Nodes and Value* 00500 for(std::vector<const MachineInstr*>::iterator I = phiInstrs.begin(), 00501 E = phiInstrs.end(); I != E; ++I) { 00502 00503 //Get Node for this instruction 00504 std::map<const MachineInstr*, MSchedGraphNode*>::iterator X; 00505 X = find(*I); 00506 00507 if(X == GraphMap.end()) 00508 continue; 00509 00510 MSchedGraphNode *node = X->second; 00511 00512 DEBUG(std::cerr << "Adding ite diff edges for node: " << *node << "\n"); 00513 00514 //Loop over operands for this instruction and add value edges 00515 for(unsigned i=0; i < (*I)->getNumOperands(); ++i) { 00516 //Get Operand 00517 const MachineOperand &mOp = (*I)->getOperand(i); 00518 if((mOp.getType() == MachineOperand::MO_VirtualRegister 00519 || mOp.getType() == MachineOperand::MO_CCRegister) && mOp.isUse()) { 00520 00521 //find the value in the map 00522 if (const Value* srcI = mOp.getVRegValue()) { 00523 00524 //Find value in the map 00525 std::map<const Value*, std::vector<OpIndexNodePair> >::iterator V 00526 = valuetoNodeMap.find(srcI); 00527 00528 //If there is something in the map already, add edges from 00529 //those instructions 00530 //to this one we are processing 00531 if(V != valuetoNodeMap.end()) { 00532 addValueEdges(V->second, node, mOp.isUse(), mOp.isDef(), 00533 phiInstrs, 1); 00534 } 00535 } 00536 } 00537 } 00538 } 00539 } 00540 } 00541 //Add dependencies for Value*s 00542 void MSchedGraph::addValueEdges(std::vector<OpIndexNodePair> &NodesInMap, 00543 MSchedGraphNode *destNode, bool nodeIsUse, 00544 bool nodeIsDef, std::vector<const MachineInstr*> &phiInstrs, int diff) { 00545 00546 for(std::vector<OpIndexNodePair>::iterator I = NodesInMap.begin(), 00547 E = NodesInMap.end(); I != E; ++I) { 00548 00549 //Get node in vectors machine operand that is the same value as node 00550 MSchedGraphNode *srcNode = I->second; 00551 MachineOperand mOp = srcNode->getInst()->getOperand(I->first); 00552 00553 if(diff > 0) 00554 if(std::find(phiInstrs.begin(), phiInstrs.end(), srcNode->getInst()) == phiInstrs.end()) 00555 continue; 00556 00557 //Node is a Def, so add output dep. 00558 if(nodeIsDef) { 00559 if(mOp.isUse()) { 00560 DEBUG(std::cerr << "Edge from " << *srcNode << " to " << *destNode << " (itediff=" << diff << ", type=anti)\n"); 00561 srcNode->addOutEdge(destNode, MSchedGraphEdge::ValueDep, 00562 MSchedGraphEdge::AntiDep, diff); 00563 } 00564 if(mOp.isDef()) { 00565 DEBUG(std::cerr << "Edge from " << *srcNode << " to " << *destNode << " (itediff=" << diff << ", type=output)\n"); 00566 srcNode->addOutEdge(destNode, MSchedGraphEdge::ValueDep, 00567 MSchedGraphEdge::OutputDep, diff); 00568 } 00569 } 00570 if(nodeIsUse) { 00571 if(mOp.isDef()) { 00572 DEBUG(std::cerr << "Edge from " << *srcNode << " to " << *destNode << " (itediff=" << diff << ", type=true)\n"); 00573 srcNode->addOutEdge(destNode, MSchedGraphEdge::ValueDep, 00574 MSchedGraphEdge::TrueDep, diff); 00575 } 00576 } 00577 } 00578 } 00579 00580 //Add dependencies for machine registers across iterations 00581 void MSchedGraph::addMachRegEdges(std::map<int, std::vector<OpIndexNodePair> >& regNumtoNodeMap) { 00582 //Loop over all machine registers in the map, and add dependencies 00583 //between the instructions that use it 00584 typedef std::map<int, std::vector<OpIndexNodePair> > regNodeMap; 00585 for(regNodeMap::iterator I = regNumtoNodeMap.begin(); 00586 I != regNumtoNodeMap.end(); ++I) { 00587 //Get the register number 00588 int regNum = (*I).first; 00589 00590 //Get Vector of nodes that use this register 00591 std::vector<OpIndexNodePair> Nodes = (*I).second; 00592 00593 //Loop over nodes and determine the dependence between the other 00594 //nodes in the vector 00595 for(unsigned i =0; i < Nodes.size(); ++i) { 00596 00597 //Get src node operator index that uses this machine register 00598 int srcOpIndex = Nodes[i].first; 00599 00600 //Get the actual src Node 00601 MSchedGraphNode *srcNode = Nodes[i].second; 00602 00603 //Get Operand 00604 const MachineOperand &srcMOp = srcNode->getInst()->getOperand(srcOpIndex); 00605 00606 bool srcIsUseandDef = srcMOp.isDef() && srcMOp.isUse(); 00607 bool srcIsUse = srcMOp.isUse() && !srcMOp.isDef(); 00608 00609 00610 //Look at all instructions after this in execution order 00611 for(unsigned j=i+1; j < Nodes.size(); ++j) { 00612 00613 //Sink node is a write 00614 if(Nodes[j].second->getInst()->getOperand(Nodes[j].first).isDef()) { 00615 //Src only uses the register (read) 00616 if(srcIsUse) 00617 srcNode->addOutEdge(Nodes[j].second, 00618 MSchedGraphEdge::MachineRegister, 00619 MSchedGraphEdge::AntiDep); 00620 00621 else if(srcIsUseandDef) { 00622 srcNode->addOutEdge(Nodes[j].second, 00623 MSchedGraphEdge::MachineRegister, 00624 MSchedGraphEdge::AntiDep); 00625 00626 srcNode->addOutEdge(Nodes[j].second, 00627 MSchedGraphEdge::MachineRegister, 00628 MSchedGraphEdge::OutputDep); 00629 } 00630 else 00631 srcNode->addOutEdge(Nodes[j].second, 00632 MSchedGraphEdge::MachineRegister, 00633 MSchedGraphEdge::OutputDep); 00634 } 00635 //Dest node is a read 00636 else { 00637 if(!srcIsUse || srcIsUseandDef) 00638 srcNode->addOutEdge(Nodes[j].second, 00639 MSchedGraphEdge::MachineRegister, 00640 MSchedGraphEdge::TrueDep); 00641 } 00642 00643 } 00644 00645 //Look at all the instructions before this one since machine registers 00646 //could live across iterations. 00647 for(unsigned j = 0; j < i; ++j) { 00648 //Sink node is a write 00649 if(Nodes[j].second->getInst()->getOperand(Nodes[j].first).isDef()) { 00650 //Src only uses the register (read) 00651 if(srcIsUse) 00652 srcNode->addOutEdge(Nodes[j].second, 00653 MSchedGraphEdge::MachineRegister, 00654 MSchedGraphEdge::AntiDep, 1); 00655 else if(srcIsUseandDef) { 00656 srcNode->addOutEdge(Nodes[j].second, 00657 MSchedGraphEdge::MachineRegister, 00658 MSchedGraphEdge::AntiDep, 1); 00659 00660 srcNode->addOutEdge(Nodes[j].second, 00661 MSchedGraphEdge::MachineRegister, 00662 MSchedGraphEdge::OutputDep, 1); 00663 } 00664 else 00665 srcNode->addOutEdge(Nodes[j].second, 00666 MSchedGraphEdge::MachineRegister, 00667 MSchedGraphEdge::OutputDep, 1); 00668 } 00669 //Dest node is a read 00670 else { 00671 if(!srcIsUse || srcIsUseandDef) 00672 srcNode->addOutEdge(Nodes[j].second, 00673 MSchedGraphEdge::MachineRegister, 00674 MSchedGraphEdge::TrueDep,1 ); 00675 } 00676 00677 00678 } 00679 00680 } 00681 00682 } 00683 00684 } 00685 00686 //Add edges between all loads and stores 00687 //Can be less strict with alias analysis and data dependence analysis. 00688 void MSchedGraph::addMemEdges(const std::vector<MSchedGraphNode*>& memInst, 00689 DependenceAnalyzer &DA, 00690 std::map<MachineInstr*, Instruction*> &machineTollvm) { 00691 00692 //Get Target machine instruction info 00693 const TargetInstrInfo *TMI = Target.getInstrInfo(); 00694 00695 //Loop over all memory instructions in the vector 00696 //Knowing that they are in execution, add true, anti, and output dependencies 00697 for (unsigned srcIndex = 0; srcIndex < memInst.size(); ++srcIndex) { 00698 00699 MachineInstr *srcInst = (MachineInstr*) memInst[srcIndex]->getInst(); 00700 00701 //Get the machine opCode to determine type of memory instruction 00702 MachineOpCode srcNodeOpCode = srcInst->getOpcode(); 00703 00704 //All instructions after this one in execution order have an 00705 //iteration delay of 0 00706 for(unsigned destIndex = 0; destIndex < memInst.size(); ++destIndex) { 00707 00708 //No self loops 00709 if(destIndex == srcIndex) 00710 continue; 00711 00712 MachineInstr *destInst = (MachineInstr*) memInst[destIndex]->getInst(); 00713 00714 DEBUG(std::cerr << "MInst1: " << *srcInst << "\n"); 00715 DEBUG(std::cerr << "MInst2: " << *destInst << "\n"); 00716 00717 //Assuming instructions without corresponding llvm instructions 00718 //are from constant pools. 00719 if (!machineTollvm.count(srcInst) || !machineTollvm.count(destInst)) 00720 continue; 00721 00722 bool useDepAnalyzer = true; 00723 00724 //Some machine loads and stores are generated by casts, so be 00725 //conservative and always add deps 00726 Instruction *srcLLVM = machineTollvm[srcInst]; 00727 Instruction *destLLVM = machineTollvm[destInst]; 00728 if(!isa<LoadInst>(srcLLVM) 00729 && !isa<StoreInst>(srcLLVM)) { 00730 if(isa<BinaryOperator>(srcLLVM)) { 00731 if(isa<ConstantFP>(srcLLVM->getOperand(0)) || isa<ConstantFP>(srcLLVM->getOperand(1))) 00732 continue; 00733 } 00734 useDepAnalyzer = false; 00735 } 00736 if(!isa<LoadInst>(destLLVM) 00737 && !isa<StoreInst>(destLLVM)) { 00738 if(isa<BinaryOperator>(destLLVM)) { 00739 if(isa<ConstantFP>(destLLVM->getOperand(0)) || isa<ConstantFP>(destLLVM->getOperand(1))) 00740 continue; 00741 } 00742 useDepAnalyzer = false; 00743 } 00744 00745 //Use dep analysis when we have corresponding llvm loads/stores 00746 if(useDepAnalyzer) { 00747 bool srcBeforeDest = true; 00748 if(destIndex < srcIndex) 00749 srcBeforeDest = false; 00750 00751 DependenceResult dr = DA.getDependenceInfo(machineTollvm[srcInst], 00752 machineTollvm[destInst], 00753 srcBeforeDest); 00754 00755 for(std::vector<Dependence>::iterator d = dr.dependences.begin(), 00756 de = dr.dependences.end(); d != de; ++d) { 00757 //Add edge from load to store 00758 memInst[srcIndex]->addOutEdge(memInst[destIndex], 00759 MSchedGraphEdge::MemoryDep, 00760 d->getDepType(), d->getIteDiff()); 00761 00762 } 00763 } 00764 //Otherwise, we can not do any further analysis and must make a dependence 00765 else { 00766 00767 //Get the machine opCode to determine type of memory instruction 00768 MachineOpCode destNodeOpCode = destInst->getOpcode(); 00769 00770 //Get the Value* that we are reading from the load, always the first op 00771 const MachineOperand &mOp = srcInst->getOperand(0); 00772 const MachineOperand &mOp2 = destInst->getOperand(0); 00773 00774 if(mOp.hasAllocatedReg()) 00775 if(mOp.getReg() == SparcV9::g0) 00776 continue; 00777 if(mOp2.hasAllocatedReg()) 00778 if(mOp2.getReg() == SparcV9::g0) 00779 continue; 00780 00781 DEBUG(std::cerr << "Adding dependence for machine instructions\n"); 00782 //Load-Store deps 00783 if(TMI->isLoad(srcNodeOpCode)) { 00784 00785 if(TMI->isStore(destNodeOpCode)) 00786 memInst[srcIndex]->addOutEdge(memInst[destIndex], 00787 MSchedGraphEdge::MemoryDep, 00788 MSchedGraphEdge::AntiDep, 0); 00789 } 00790 else if(TMI->isStore(srcNodeOpCode)) { 00791 if(TMI->isStore(destNodeOpCode)) 00792 memInst[srcIndex]->addOutEdge(memInst[destIndex], 00793 MSchedGraphEdge::MemoryDep, 00794 MSchedGraphEdge::OutputDep, 0); 00795 00796 else 00797 memInst[srcIndex]->addOutEdge(memInst[destIndex], 00798 MSchedGraphEdge::MemoryDep, 00799 MSchedGraphEdge::TrueDep, 0); 00800 } 00801 } 00802 } 00803 } 00804 }