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 00011 // 00012 //===----------------------------------------------------------------------===// 00013 #define DEBUG_TYPE "ModuloSched" 00014 00015 #include "MSchedGraph.h" 00016 #include "../SparcV9RegisterInfo.h" 00017 #include "llvm/CodeGen/MachineBasicBlock.h" 00018 #include "llvm/Target/TargetInstrInfo.h" 00019 #include "llvm/Support/Debug.h" 00020 #include <cstdlib> 00021 #include <algorithm> 00022 using namespace llvm; 00023 00024 MSchedGraphNode::MSchedGraphNode(const MachineInstr* inst, 00025 MSchedGraph *graph, unsigned idx, 00026 unsigned late, bool isBranch) 00027 : Inst(inst), Parent(graph), index(idx), latency(late), isBranchInstr(isBranch) { 00028 00029 //Add to the graph 00030 graph->addNode(inst, this); 00031 } 00032 00033 void MSchedGraphNode::print(std::ostream &os) const { 00034 os << "MSchedGraphNode: Inst=" << *Inst << ", latency= " << latency << "\n"; 00035 } 00036 00037 MSchedGraphEdge MSchedGraphNode::getInEdge(MSchedGraphNode *pred) { 00038 //Loop over all the successors of our predecessor 00039 //return the edge the corresponds to this in edge 00040 for (MSchedGraphNode::succ_iterator I = pred->succ_begin(), 00041 E = pred->succ_end(); I != E; ++I) { 00042 if (*I == this) 00043 return I.getEdge(); 00044 } 00045 assert(0 && "Should have found edge between this node and its predecessor!"); 00046 abort(); 00047 } 00048 00049 unsigned MSchedGraphNode::getInEdgeNum(MSchedGraphNode *pred) { 00050 //Loop over all the successors of our predecessor 00051 //return the edge the corresponds to this in edge 00052 int count = 0; 00053 for(MSchedGraphNode::succ_iterator I = pred->succ_begin(), E = pred->succ_end(); 00054 I != E; ++I) { 00055 if(*I == this) 00056 return count; 00057 count++; 00058 } 00059 assert(0 && "Should have found edge between this node and its predecessor!"); 00060 abort(); 00061 } 00062 bool MSchedGraphNode::isSuccessor(MSchedGraphNode *succ) { 00063 for(succ_iterator I = succ_begin(), E = succ_end(); I != E; ++I) 00064 if(*I == succ) 00065 return true; 00066 return false; 00067 } 00068 00069 00070 bool MSchedGraphNode::isPredecessor(MSchedGraphNode *pred) { 00071 if(std::find( Predecessors.begin(), Predecessors.end(), pred) != Predecessors.end()) 00072 return true; 00073 else 00074 return false; 00075 } 00076 00077 00078 void MSchedGraph::addNode(const MachineInstr *MI, 00079 MSchedGraphNode *node) { 00080 00081 //Make sure node does not already exist 00082 assert(GraphMap.find(MI) == GraphMap.end() 00083 && "New MSchedGraphNode already exists for this instruction"); 00084 00085 GraphMap[MI] = node; 00086 } 00087 00088 MSchedGraph::MSchedGraph(const MachineBasicBlock *bb, const TargetMachine &targ) 00089 : BB(bb), Target(targ) { 00090 00091 //Make sure BB is not null, 00092 assert(BB != NULL && "Basic Block is null"); 00093 00094 //DEBUG(std::cerr << "Constructing graph for " << bb << "\n"); 00095 00096 //Create nodes and edges for this BB 00097 buildNodesAndEdges(); 00098 } 00099 00100 MSchedGraph::~MSchedGraph () { 00101 for(MSchedGraph::iterator I = GraphMap.begin(), E = GraphMap.end(); I != E; ++I) 00102 delete I->second; 00103 } 00104 00105 void MSchedGraph::buildNodesAndEdges() { 00106 00107 //Get Machine target information for calculating latency 00108 const TargetInstrInfo *MTI = Target.getInstrInfo(); 00109 00110 std::vector<MSchedGraphNode*> memInstructions; 00111 std::map<int, std::vector<OpIndexNodePair> > regNumtoNodeMap; 00112 std::map<const Value*, std::vector<OpIndexNodePair> > valuetoNodeMap; 00113 00114 //Save PHI instructions to deal with later 00115 std::vector<const MachineInstr*> phiInstrs; 00116 unsigned index = 0; 00117 //Loop over instructions in MBB and add nodes and edges 00118 for (MachineBasicBlock::const_iterator MI = BB->begin(), e = BB->end(); MI != e; ++MI) { 00119 //Get each instruction of machine basic block, get the delay 00120 //using the op code, create a new node for it, and add to the 00121 //graph. 00122 00123 MachineOpCode opCode = MI->getOpcode(); 00124 int delay; 00125 00126 #if 0 // FIXME: LOOK INTO THIS 00127 //Check if subsequent instructions can be issued before 00128 //the result is ready, if so use min delay. 00129 if(MTI->hasResultInterlock(MIopCode)) 00130 delay = MTI->minLatency(MIopCode); 00131 else 00132 #endif 00133 //Get delay 00134 delay = MTI->maxLatency(opCode); 00135 00136 //Create new node for this machine instruction and add to the graph. 00137 //Create only if not a nop 00138 if(MTI->isNop(opCode)) 00139 continue; 00140 00141 //Add PHI to phi instruction list to be processed later 00142 if (opCode == TargetInstrInfo::PHI) 00143 phiInstrs.push_back(MI); 00144 00145 bool isBranch = false; 00146 00147 //We want to flag the branch node to treat it special 00148 if(MTI->isBranch(opCode)) 00149 isBranch = true; 00150 00151 //Node is created and added to the graph automatically 00152 MSchedGraphNode *node = new MSchedGraphNode(MI, this, index, delay, isBranch); 00153 00154 DEBUG(std::cerr << "Created Node: " << *node << "\n"); 00155 00156 //Check OpCode to keep track of memory operations to add memory dependencies later. 00157 if(MTI->isLoad(opCode) || MTI->isStore(opCode)) 00158 memInstructions.push_back(node); 00159 00160 //Loop over all operands, and put them into the register number to 00161 //graph node map for determining dependencies 00162 //If an operands is a use/def, we have an anti dependence to itself 00163 for(unsigned i=0; i < MI->getNumOperands(); ++i) { 00164 //Get Operand 00165 const MachineOperand &mOp = MI->getOperand(i); 00166 00167 //Check if it has an allocated register 00168 if(mOp.hasAllocatedReg()) { 00169 int regNum = mOp.getReg(); 00170 00171 if(regNum != SparcV9::g0) { 00172 //Put into our map 00173 regNumtoNodeMap[regNum].push_back(std::make_pair(i, node)); 00174 } 00175 continue; 00176 } 00177 00178 00179 //Add virtual registers dependencies 00180 //Check if any exist in the value map already and create dependencies 00181 //between them. 00182 if(mOp.getType() == MachineOperand::MO_VirtualRegister || mOp.getType() == MachineOperand::MO_CCRegister) { 00183 00184 //Make sure virtual register value is not null 00185 assert((mOp.getVRegValue() != NULL) && "Null value is defined"); 00186 00187 //Check if this is a read operation in a phi node, if so DO NOT PROCESS 00188 if(mOp.isUse() && (opCode == TargetInstrInfo::PHI)) 00189 continue; 00190 00191 00192 if (const Value* srcI = mOp.getVRegValue()) { 00193 00194 //Find value in the map 00195 std::map<const Value*, std::vector<OpIndexNodePair> >::iterator V 00196 = valuetoNodeMap.find(srcI); 00197 00198 //If there is something in the map already, add edges from 00199 //those instructions 00200 //to this one we are processing 00201 if(V != valuetoNodeMap.end()) { 00202 addValueEdges(V->second, node, mOp.isUse(), mOp.isDef()); 00203 00204 //Add to value map 00205 V->second.push_back(std::make_pair(i,node)); 00206 } 00207 //Otherwise put it in the map 00208 else 00209 //Put into value map 00210 valuetoNodeMap[mOp.getVRegValue()].push_back(std::make_pair(i, node)); 00211 } 00212 } 00213 } 00214 ++index; 00215 } 00216 addMemEdges(memInstructions); 00217 addMachRegEdges(regNumtoNodeMap); 00218 00219 //Finally deal with PHI Nodes and Value* 00220 for(std::vector<const MachineInstr*>::iterator I = phiInstrs.begin(), E = phiInstrs.end(); I != E; ++I) { 00221 //Get Node for this instruction 00222 MSchedGraphNode *node = find(*I)->second; 00223 00224 //Loop over operands for this instruction and add value edges 00225 for(unsigned i=0; i < (*I)->getNumOperands(); ++i) { 00226 //Get Operand 00227 const MachineOperand &mOp = (*I)->getOperand(i); 00228 if((mOp.getType() == MachineOperand::MO_VirtualRegister || mOp.getType() == MachineOperand::MO_CCRegister) && mOp.isUse()) { 00229 //find the value in the map 00230 if (const Value* srcI = mOp.getVRegValue()) { 00231 00232 //Find value in the map 00233 std::map<const Value*, std::vector<OpIndexNodePair> >::iterator V 00234 = valuetoNodeMap.find(srcI); 00235 00236 //If there is something in the map already, add edges from 00237 //those instructions 00238 //to this one we are processing 00239 if(V != valuetoNodeMap.end()) { 00240 addValueEdges(V->second, node, mOp.isUse(), mOp.isDef(), 1); 00241 } 00242 } 00243 } 00244 } 00245 } 00246 } 00247 00248 void MSchedGraph::addValueEdges(std::vector<OpIndexNodePair> &NodesInMap, 00249 MSchedGraphNode *destNode, bool nodeIsUse, 00250 bool nodeIsDef, int diff) { 00251 00252 for(std::vector<OpIndexNodePair>::iterator I = NodesInMap.begin(), 00253 E = NodesInMap.end(); I != E; ++I) { 00254 00255 //Get node in vectors machine operand that is the same value as node 00256 MSchedGraphNode *srcNode = I->second; 00257 MachineOperand mOp = srcNode->getInst()->getOperand(I->first); 00258 00259 //Node is a Def, so add output dep. 00260 if(nodeIsDef) { 00261 if(mOp.isUse()) 00262 srcNode->addOutEdge(destNode, MSchedGraphEdge::ValueDep, 00263 MSchedGraphEdge::AntiDep, diff); 00264 if(mOp.isDef()) 00265 srcNode->addOutEdge(destNode, MSchedGraphEdge::ValueDep, 00266 MSchedGraphEdge::OutputDep, diff); 00267 00268 } 00269 if(nodeIsUse) { 00270 if(mOp.isDef()) 00271 srcNode->addOutEdge(destNode, MSchedGraphEdge::ValueDep, 00272 MSchedGraphEdge::TrueDep, diff); 00273 } 00274 } 00275 } 00276 00277 00278 void MSchedGraph::addMachRegEdges(std::map<int, std::vector<OpIndexNodePair> >& regNumtoNodeMap) { 00279 //Loop over all machine registers in the map, and add dependencies 00280 //between the instructions that use it 00281 typedef std::map<int, std::vector<OpIndexNodePair> > regNodeMap; 00282 for(regNodeMap::iterator I = regNumtoNodeMap.begin(); I != regNumtoNodeMap.end(); ++I) { 00283 //Get the register number 00284 int regNum = (*I).first; 00285 00286 //Get Vector of nodes that use this register 00287 std::vector<OpIndexNodePair> Nodes = (*I).second; 00288 00289 //Loop over nodes and determine the dependence between the other 00290 //nodes in the vector 00291 for(unsigned i =0; i < Nodes.size(); ++i) { 00292 00293 //Get src node operator index that uses this machine register 00294 int srcOpIndex = Nodes[i].first; 00295 00296 //Get the actual src Node 00297 MSchedGraphNode *srcNode = Nodes[i].second; 00298 00299 //Get Operand 00300 const MachineOperand &srcMOp = srcNode->getInst()->getOperand(srcOpIndex); 00301 00302 bool srcIsUseandDef = srcMOp.isDef() && srcMOp.isUse(); 00303 bool srcIsUse = srcMOp.isUse() && !srcMOp.isDef(); 00304 00305 00306 //Look at all instructions after this in execution order 00307 for(unsigned j=i+1; j < Nodes.size(); ++j) { 00308 00309 //Sink node is a write 00310 if(Nodes[j].second->getInst()->getOperand(Nodes[j].first).isDef()) { 00311 //Src only uses the register (read) 00312 if(srcIsUse) 00313 srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister, 00314 MSchedGraphEdge::AntiDep); 00315 00316 else if(srcIsUseandDef) { 00317 srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister, 00318 MSchedGraphEdge::AntiDep); 00319 00320 srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister, 00321 MSchedGraphEdge::OutputDep); 00322 } 00323 else 00324 srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister, 00325 MSchedGraphEdge::OutputDep); 00326 } 00327 //Dest node is a read 00328 else { 00329 if(!srcIsUse || srcIsUseandDef) 00330 srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister, 00331 MSchedGraphEdge::TrueDep); 00332 } 00333 00334 } 00335 00336 //Look at all the instructions before this one since machine registers 00337 //could live across iterations. 00338 for(unsigned j = 0; j < i; ++j) { 00339 //Sink node is a write 00340 if(Nodes[j].second->getInst()->getOperand(Nodes[j].first).isDef()) { 00341 //Src only uses the register (read) 00342 if(srcIsUse) 00343 srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister, 00344 MSchedGraphEdge::AntiDep, 1); 00345 00346 else if(srcIsUseandDef) { 00347 srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister, 00348 MSchedGraphEdge::AntiDep, 1); 00349 00350 srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister, 00351 MSchedGraphEdge::OutputDep, 1); 00352 } 00353 else 00354 srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister, 00355 MSchedGraphEdge::OutputDep, 1); 00356 } 00357 //Dest node is a read 00358 else { 00359 if(!srcIsUse || srcIsUseandDef) 00360 srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister, 00361 MSchedGraphEdge::TrueDep,1 ); 00362 } 00363 00364 00365 } 00366 00367 } 00368 00369 } 00370 00371 } 00372 00373 void MSchedGraph::addMemEdges(const std::vector<MSchedGraphNode*>& memInst) { 00374 00375 //Get Target machine instruction info 00376 const TargetInstrInfo *TMI = Target.getInstrInfo(); 00377 00378 //Loop over all memory instructions in the vector 00379 //Knowing that they are in execution, add true, anti, and output dependencies 00380 for (unsigned srcIndex = 0; srcIndex < memInst.size(); ++srcIndex) { 00381 00382 //Get the machine opCode to determine type of memory instruction 00383 MachineOpCode srcNodeOpCode = memInst[srcIndex]->getInst()->getOpcode(); 00384 00385 //All instructions after this one in execution order have an iteration delay of 0 00386 for(unsigned destIndex = srcIndex + 1; destIndex < memInst.size(); ++destIndex) { 00387 00388 //source is a Load, so add anti-dependencies (store after load) 00389 if(TMI->isLoad(srcNodeOpCode)) 00390 if(TMI->isStore(memInst[destIndex]->getInst()->getOpcode())) 00391 memInst[srcIndex]->addOutEdge(memInst[destIndex], 00392 MSchedGraphEdge::MemoryDep, 00393 MSchedGraphEdge::AntiDep); 00394 00395 //If source is a store, add output and true dependencies 00396 if(TMI->isStore(srcNodeOpCode)) { 00397 if(TMI->isStore(memInst[destIndex]->getInst()->getOpcode())) 00398 memInst[srcIndex]->addOutEdge(memInst[destIndex], 00399 MSchedGraphEdge::MemoryDep, 00400 MSchedGraphEdge::OutputDep); 00401 else 00402 memInst[srcIndex]->addOutEdge(memInst[destIndex], 00403 MSchedGraphEdge::MemoryDep, 00404 MSchedGraphEdge::TrueDep); 00405 } 00406 } 00407 00408 //All instructions before the src in execution order have an iteration delay of 1 00409 for(unsigned destIndex = 0; destIndex < srcIndex; ++destIndex) { 00410 //source is a Load, so add anti-dependencies (store after load) 00411 if(TMI->isLoad(srcNodeOpCode)) 00412 if(TMI->isStore(memInst[destIndex]->getInst()->getOpcode())) 00413 memInst[srcIndex]->addOutEdge(memInst[destIndex], 00414 MSchedGraphEdge::MemoryDep, 00415 MSchedGraphEdge::AntiDep, 1); 00416 if(TMI->isStore(srcNodeOpCode)) { 00417 if(TMI->isStore(memInst[destIndex]->getInst()->getOpcode())) 00418 memInst[srcIndex]->addOutEdge(memInst[destIndex], 00419 MSchedGraphEdge::MemoryDep, 00420 MSchedGraphEdge::OutputDep, 1); 00421 else 00422 memInst[srcIndex]->addOutEdge(memInst[destIndex], 00423 MSchedGraphEdge::MemoryDep, 00424 MSchedGraphEdge::TrueDep, 1); 00425 } 00426 00427 } 00428 00429 } 00430 }