LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

MSchedGraph.cpp

Go to the documentation of this file.
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 }