LLVM API Documentation

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. 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 }