LLVM API Documentation

MSchedGraphSB.cpp

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