lib/Target/SparcV9/ModuloScheduling/MSchedGraph.cpp

   1 //===-- MSchedGraph.cpp - Scheduling Graph ----------------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // A graph class for dependencies. This graph only contains true, anti, and
  11 // output data dependencies for a given MachineBasicBlock. Dependencies
  12 // across iterations are also computed. Unless data dependence analysis
  13 // is provided, a conservative approach of adding dependencies between all
  14 // loads and stores is taken.
  15 //===----------------------------------------------------------------------===//
  16 #define DEBUG_TYPE "ModuloSched"
  17
  18 #include "MSchedGraph.h"
  19 #include "../SparcV9RegisterInfo.h"
  20 #include "../MachineCodeForInstruction.h"
  21 #include "llvm/BasicBlock.h"
  22 #include "llvm/Constants.h"
  23 #include "llvm/Instructions.h"
  24 #include "llvm/Type.h"
  25 #include "llvm/CodeGen/MachineBasicBlock.h"
  26 #include "llvm/Target/TargetInstrInfo.h"
  27 #include "llvm/Support/Debug.h"
  28 #include <cstdlib>
  29 #include <algorithm>
  30 #include <set>
  31
  32 using namespace llvm;
  33
  34 //MSchedGraphNode constructor
  35 MSchedGraphNode::MSchedGraphNode(const MachineInstr* inst,
  36                                  MSchedGraph *graph, unsigned idx,
  37                                  unsigned late, bool isBranch)
  38   : Inst(inst), Parent(graph), index(idx), latency(late),
  39     isBranchInstr(isBranch) {
  40
  41   //Add to the graph
  42   graph->addNode(inst, this);
  43 }
  44
  45 //MSchedGraphNode copy constructor
  46 MSchedGraphNode::MSchedGraphNode(const MSchedGraphNode &N)
  47   : Predecessors(N.Predecessors), Successors(N.Successors) {
  48
  49   Inst = N.Inst;
  50   Parent = N.Parent;
  51   index = N.index;
  52   latency = N.latency;
  53   isBranchInstr = N.isBranchInstr;
  54
  55 }
  56
  57 //Print the node (instruction and latency)
  58 void MSchedGraphNode::print(std::ostream &os) const {
  59   os << "MSchedGraphNode: Inst=" << *Inst << ", latency= " << latency << "\n";
  60 }
  61
  62
  63 //Get the edge from a predecessor to this node
  64 MSchedGraphEdge MSchedGraphNode::getInEdge(MSchedGraphNode *pred) {
  65   //Loop over all the successors of our predecessor
  66   //return the edge the corresponds to this in edge
  67   for (MSchedGraphNode::succ_iterator I = pred->succ_begin(),
  68          E = pred->succ_end(); I != E; ++I) {
  69     if (*I == this)
  70       return I.getEdge();
  71   }
  72   assert(0 && "Should have found edge between this node and its predecessor!");
  73   abort();
  74 }
  75
  76 //Get the iteration difference for the edge from this node to its successor
  77 unsigned MSchedGraphNode::getIteDiff(MSchedGraphNode *succ) {
  78   for(std::vector<MSchedGraphEdge>::iterator I = Successors.begin(),
  79         E = Successors.end();
  80       I != E; ++I) {
  81     if(I->getDest() == succ)
  82       return I->getIteDiff();
  83   }
  84   return 0;
  85 }
  86
  87 //Get the index into the vector of edges for the edge from pred to this node
  88 unsigned MSchedGraphNode::getInEdgeNum(MSchedGraphNode *pred) {
  89   //Loop over all the successors of our predecessor
  90   //return the edge the corresponds to this in edge
  91   int count = 0;
  92   for(MSchedGraphNode::succ_iterator I = pred->succ_begin(),
  93         E = pred->succ_end();
  94       I != E; ++I) {
  95     if(*I == this)
  96       return count;
  97     count++;
  98   }
  99   assert(0 && "Should have found edge between this node and its predecessor!");
 100   abort();
 101 }
 102
 103 //Determine if succ is a successor of this node
 104 bool MSchedGraphNode::isSuccessor(MSchedGraphNode *succ) {
 105   for(succ_iterator I = succ_begin(), E = succ_end(); I != E; ++I)
 106     if(*I == succ)
 107       return true;
 108   return false;
 109 }
 110
 111 //Dtermine if pred is a predecessor of this node
 112 bool MSchedGraphNode::isPredecessor(MSchedGraphNode *pred) {
 113   if(std::find( Predecessors.begin(),  Predecessors.end(),
 114                 pred) !=   Predecessors.end())
 115     return true;
 116   else
 117     return false;
 118 }
 119
 120 //Add a node to the graph
 121 void MSchedGraph::addNode(const MachineInstr *MI,
 122                           MSchedGraphNode *node) {
 123
 124   //Make sure node does not already exist
 125   assert(GraphMap.find(MI) == GraphMap.end()
 126          && "New MSchedGraphNode already exists for this instruction");
 127
 128   GraphMap[MI] = node;
 129 }
 130
 131 //Delete a node to the graph
 132 void MSchedGraph::deleteNode(MSchedGraphNode *node) {
 133
 134   //Delete the edge to this node from all predecessors
 135   while(node->pred_size() > 0) {
 136     //DEBUG(std::cerr << "Delete edge from: " << **P << " to " << *node << "\n");
 137     MSchedGraphNode *pred = *(node->pred_begin());
 138     pred->deleteSuccessor(node);
 139   }
 140
 141   //Remove this node from the graph
 142   GraphMap.erase(node->getInst());
 143
 144 }
 145
 146
 147 //Create a graph for a machine block. The ignoreInstrs map is so that
 148 //we ignore instructions associated to the index variable since this
 149 //is a special case in Modulo Scheduling.  We only want to deal with
 150 //the body of the loop.
 151 MSchedGraph::MSchedGraph(const MachineBasicBlock *bb,
 152                          const TargetMachine &targ,
 153                          std::map<const MachineInstr*, unsigned> &ignoreInstrs,
 154                          DependenceAnalyzer &DA,
 155                          std::map<MachineInstr*, Instruction*> &machineTollvm)
 156   : Target(targ) {
 157
 158   //Make sure BB is not null,
 159   assert(bb != NULL && "Basic Block is null");
 160
 161   BBs.push_back(bb);
 162
 163   //Create nodes and edges for this BB
 164   buildNodesAndEdges(ignoreInstrs, DA, machineTollvm);
 165
 166   //Experimental!
 167   //addBranchEdges();
 168 }
 169
 170 //Create a graph for a machine block. The ignoreInstrs map is so that
 171 //we ignore instructions associated to the index variable since this
 172 //is a special case in Modulo Scheduling.  We only want to deal with
 173 //the body of the loop.
 174 MSchedGraph::MSchedGraph(std::vector<const MachineBasicBlock*> &bbs,
 175                          const TargetMachine &targ,
 176                          std::map<const MachineInstr*, unsigned> &ignoreInstrs,
 177                          DependenceAnalyzer &DA,
 178                          std::map<MachineInstr*, Instruction*> &machineTollvm)
 179   : BBs(bbs), Target(targ) {
 180
 181   //Make sure there is at least one BB and it is not null,
 182   assert(((bbs.size() >= 1) &&  bbs[1] != NULL) && "Basic Block is null");
 183
 184   //Create nodes and edges for this BB
 185   buildNodesAndEdges(ignoreInstrs, DA, machineTollvm);
 186
 187   //Experimental!
 188   //addBranchEdges();
 189 }
 190
 191
 192 //Copies the graph and keeps a map from old to new nodes
 193 MSchedGraph::MSchedGraph(const MSchedGraph &G,
 194                          std::map<MSchedGraphNode*, MSchedGraphNode*> &newNodes)
 195   : Target(G.Target) {
 196
 197   BBs = G.BBs;
 198
 199   std::map<MSchedGraphNode*, MSchedGraphNode*> oldToNew;
 200   //Copy all nodes
 201   for(MSchedGraph::const_iterator N = G.GraphMap.begin(),
 202         NE = G.GraphMap.end(); N != NE; ++N) {
 203
 204     MSchedGraphNode *newNode = new MSchedGraphNode(*(N->second));
 205     oldToNew[&*(N->second)] = newNode;
 206     newNodes[newNode] = &*(N->second);
 207     GraphMap[&*(N->first)] = newNode;
 208   }
 209
 210   //Loop over nodes and update edges to point to new nodes
 211   for(MSchedGraph::iterator N = GraphMap.begin(), NE = GraphMap.end();
 212       N != NE; ++N) {
 213
 214     //Get the node we are dealing with
 215     MSchedGraphNode *node = &*(N->second);
 216
 217     node->setParent(this);
 218
 219     //Loop over nodes successors and predecessors and update to the new nodes
 220     for(unsigned i = 0; i < node->pred_size(); ++i) {
 221       node->setPredecessor(i, oldToNew[node->getPredecessor(i)]);
 222     }
 223
 224     for(unsigned i = 0; i < node->succ_size(); ++i) {
 225       MSchedGraphEdge *edge = node->getSuccessor(i);
 226       MSchedGraphNode *oldDest = edge->getDest();
 227       edge->setDest(oldToNew[oldDest]);
 228     }
 229   }
 230 }
 231
 232 //Deconstructor, deletes all nodes in the graph
 233 MSchedGraph::~MSchedGraph () {
 234   for(MSchedGraph::iterator I = GraphMap.begin(), E = GraphMap.end();
 235       I != E; ++I)
 236     delete I->second;
 237 }
 238
 239 //Print out graph
 240 void MSchedGraph::print(std::ostream &os) const {
 241   for(MSchedGraph::const_iterator N = GraphMap.begin(), NE = GraphMap.end();
 242       N != NE; ++N) {
 243
 244     //Get the node we are dealing with
 245     MSchedGraphNode *node = &*(N->second);
 246
 247     os << "Node Start\n";
 248     node->print(os);
 249     os << "Successors:\n";
 250     //print successors
 251     for(unsigned i = 0; i < node->succ_size(); ++i) {
 252       MSchedGraphEdge *edge = node->getSuccessor(i);
 253       MSchedGraphNode *oldDest = edge->getDest();
 254       oldDest->print(os);
 255     }
 256     os << "Node End\n";
 257   }
 258 }
 259
 260 //Calculate total delay
 261 int MSchedGraph::totalDelay() {
 262   int sum = 0;
 263
 264   for(MSchedGraph::const_iterator N = GraphMap.begin(), NE = GraphMap.end();
 265       N != NE; ++N) {
 266
 267     //Get the node we are dealing with
 268     MSchedGraphNode *node = &*(N->second);
 269     sum += node->getLatency();
 270   }
 271   return sum;
 272 }
 273 //Experimental code to add edges from the branch to all nodes dependent upon it.
 274 void hasPath(MSchedGraphNode *node, std::set<MSchedGraphNode*> &visited,
 275            std::set<MSchedGraphNode*> &branches, MSchedGraphNode *startNode,
 276            std::set<std::pair<MSchedGraphNode*,MSchedGraphNode*> > &newEdges ) {
 277
 278   visited.insert(node);
 279   DEBUG(std::cerr << "Visiting: " << *node << "\n");
 280   //Loop over successors
 281   for(unsigned i = 0; i < node->succ_size(); ++i) {
 282     MSchedGraphEdge *edge = node->getSuccessor(i);
 283     MSchedGraphNode *dest = edge->getDest();
 284     if(branches.count(dest))
 285       newEdges.insert(std::make_pair(dest, startNode));
 286
 287     //only visit if we have not already
 288     else if(!visited.count(dest)) {
 289       if(edge->getIteDiff() == 0)
 290         hasPath(dest, visited, branches, startNode, newEdges);}
 291
 292   }
 293
 294 }
 295
 296 //Experimental code to add edges from the branch to all nodes dependent upon it.
 297 void MSchedGraph::addBranchEdges() {
 298   std::set<MSchedGraphNode*> branches;
 299   std::set<MSchedGraphNode*> nodes;
 300
 301   for(MSchedGraph::iterator I = GraphMap.begin(), E = GraphMap.end();
 302       I != E; ++I) {
 303     if(I->second->isBranch())
 304       if(I->second->hasPredecessors())
 305         branches.insert(I->second);
 306   }
 307
 308   //See if there is a path first instruction to the branches, if so, add an
 309   //iteration dependence between that node and the branch
 310   std::set<std::pair<MSchedGraphNode*, MSchedGraphNode*> > newEdges;
 311   for(MSchedGraph::iterator I = GraphMap.begin(), E = GraphMap.end();
 312       I != E; ++I) {
 313     std::set<MSchedGraphNode*> visited;
 314     hasPath((I->second), visited, branches, (I->second), newEdges);
 315   }
 316
 317   //Spit out all edges we are going to add
 318   unsigned min = GraphMap.size();
 319   if(newEdges.size() == 1) {
 320     ((newEdges.begin())->first)->addOutEdge(((newEdges.begin())->second),
 321                            MSchedGraphEdge::BranchDep,
 322                            MSchedGraphEdge::NonDataDep, 1);
 323   }
 324   else {
 325
 326     unsigned count = 0;
 327     MSchedGraphNode *start;
 328     MSchedGraphNode *end;
 329     for(std::set<std::pair<MSchedGraphNode*, MSchedGraphNode*> >::iterator I = newEdges.begin(), E = newEdges.end(); I != E; ++I) {
 330
 331       DEBUG(std::cerr << "Branch Edge from: " << *(I->first) << " to " << *(I->second) << "\n");
 332
 333       //      if(I->second->getIndex() <= min) {
 334         start = I->first;
 335         end = I->second;
 336         //min = I->second->getIndex();
 337         //}
 338         start->addOutEdge(end,
 339                           MSchedGraphEdge::BranchDep,
 340                           MSchedGraphEdge::NonDataDep, 1);
 341     }
 342   }
 343 }
 344
 345
 346 //Add edges between the nodes
 347 void MSchedGraph::buildNodesAndEdges(std::map<const MachineInstr*, unsigned> &ignoreInstrs,
 348                                      DependenceAnalyzer &DA,
 349                        std::map<MachineInstr*, Instruction*> &machineTollvm) {
 350
 351
 352   //Get Machine target information for calculating latency
 353   const TargetInstrInfo *MTI = Target.getInstrInfo();
 354
 355   std::vector<MSchedGraphNode*> memInstructions;
 356   std::map<int, std::vector<OpIndexNodePair> > regNumtoNodeMap;
 357   std::map<const Value*, std::vector<OpIndexNodePair> > valuetoNodeMap;
 358
 359   //Save PHI instructions to deal with later
 360   std::vector<const MachineInstr*> phiInstrs;
 361   unsigned index = 0;
 362
 363   for(std::vector<const MachineBasicBlock*>::iterator B = BBs.begin(),
 364         BE = BBs.end(); B != BE; ++B) {
 365
 366     const MachineBasicBlock *BB = *B;
 367
 368     //Loop over instructions in MBB and add nodes and edges
 369     for (MachineBasicBlock::const_iterator MI = BB->begin(), e = BB->end();
 370          MI != e; ++MI) {
 371
 372       //Ignore indvar instructions
 373       if(ignoreInstrs.count(MI)) {
 374         ++index;
 375         continue;
 376       }
 377
 378       //Get each instruction of machine basic block, get the delay
 379       //using the op code, create a new node for it, and add to the
 380       //graph.
 381
 382       MachineOpCode opCode = MI->getOpcode();
 383       int delay;
 384
 385 #if 0  // FIXME: LOOK INTO THIS
 386       //Check if subsequent instructions can be issued before
 387       //the result is ready, if so use min delay.
 388       if(MTI->hasResultInterlock(MIopCode))
 389         delay = MTI->minLatency(MIopCode);
 390       else
 391 #endif
 392         //Get delay
 393         delay = MTI->maxLatency(opCode);
 394
 395       //Create new node for this machine instruction and add to the graph.
 396       //Create only if not a nop
 397       if(MTI->isNop(opCode))
 398         continue;
 399
 400       //Sparc BE does not use PHI opcode, so assert on this case
 401       assert(opCode != TargetInstrInfo::PHI && "Did not expect PHI opcode");
 402
 403       bool isBranch = false;
 404
 405       //We want to flag the branch node to treat it special
 406       if(MTI->isBranch(opCode))
 407         isBranch = true;
 408
 409       //Node is created and added to the graph automatically
 410       MSchedGraphNode *node =  new MSchedGraphNode(MI, this, index, delay,
 411                                                    isBranch);
 412
 413       DEBUG(std::cerr << "Created Node: " << *node << "\n");
 414
 415       //Check OpCode to keep track of memory operations to add memory
 416       //dependencies later.
 417       if(MTI->isLoad(opCode) || MTI->isStore(opCode))
 418         memInstructions.push_back(node);
 419
 420       //Loop over all operands, and put them into the register number to
 421       //graph node map for determining dependencies
 422       //If an operands is a use/def, we have an anti dependence to itself
 423       for(unsigned i=0; i < MI->getNumOperands(); ++i) {
 424         //Get Operand
 425         const MachineOperand &mOp = MI->getOperand(i);
 426
 427         //Check if it has an allocated register
 428         if(mOp.hasAllocatedReg()) {
 429           int regNum = mOp.getReg();
 430
 431           if(regNum != SparcV9::g0) {
 432             //Put into our map
 433             regNumtoNodeMap[regNum].push_back(std::make_pair(i, node));
 434           }
 435           continue;
 436         }
 437
 438
 439         //Add virtual registers dependencies
 440         //Check if any exist in the value map already and create dependencies
 441         //between them.
 442         if(mOp.getType() == MachineOperand::MO_VirtualRegister
 443            ||  mOp.getType() == MachineOperand::MO_CCRegister) {
 444
 445           //Make sure virtual register value is not null
 446           assert((mOp.getVRegValue() != NULL) && "Null value is defined");
 447
 448           //Check if this is a read operation in a phi node, if so DO NOT PROCESS
 449           if(mOp.isUse() && (opCode == TargetInstrInfo::PHI)) {
 450             DEBUG(std::cerr << "Read Operation in a PHI node\n");
 451             continue;
 452           }
 453
 454           if (const Value* srcI = mOp.getVRegValue()) {
 455
 456             //Find value in the map
 457             std::map<const Value*, std::vector<OpIndexNodePair> >::iterator V
 458               = valuetoNodeMap.find(srcI);
 459
 460             //If there is something in the map already, add edges from
 461             //those instructions
 462             //to this one we are processing
 463             if(V != valuetoNodeMap.end()) {
 464               addValueEdges(V->second, node, mOp.isUse(), mOp.isDef(), phiInstrs);
 465
 466               //Add to value map
 467               V->second.push_back(std::make_pair(i,node));
 468             }
 469             //Otherwise put it in the map
 470             else
 471               //Put into value map
 472               valuetoNodeMap[mOp.getVRegValue()].push_back(std::make_pair(i, node));
 473           }
 474         }
 475       }
 476       ++index;
 477     }
 478
 479     //Loop over LLVM BB, examine phi instructions, and add them to our
 480     //phiInstr list to process
 481     const BasicBlock *llvm_bb = BB->getBasicBlock();
 482     for(BasicBlock::const_iterator I = llvm_bb->begin(), E = llvm_bb->end();
 483         I != E; ++I) {
 484       if(const PHINode *PN = dyn_cast<PHINode>(I)) {
 485         MachineCodeForInstruction & tempMvec = MachineCodeForInstruction::get(PN);
 486         for (unsigned j = 0; j < tempMvec.size(); j++) {
 487           if(!ignoreInstrs.count(tempMvec[j])) {
 488             DEBUG(std::cerr << "Inserting phi instr into map: " << *tempMvec[j] << "\n");
 489             phiInstrs.push_back((MachineInstr*) tempMvec[j]);
 490           }
 491         }
 492       }
 493
 494     }
 495
 496     addMemEdges(memInstructions, DA, machineTollvm);
 497     addMachRegEdges(regNumtoNodeMap);
 498
 499     //Finally deal with PHI Nodes and Value*
 500     for(std::vector<const MachineInstr*>::iterator I = phiInstrs.begin(),
 501           E = phiInstrs.end(); I != E;  ++I) {
 502
 503       //Get Node for this instruction
 504       std::map<const MachineInstr*, MSchedGraphNode*>::iterator X;
 505       X = find(*I);
 506
 507       if(X == GraphMap.end())
 508         continue;
 509
 510       MSchedGraphNode *node = X->second;
 511
 512       DEBUG(std::cerr << "Adding ite diff edges for node: " << *node << "\n");
 513
 514       //Loop over operands for this instruction and add value edges
 515       for(unsigned i=0; i < (*I)->getNumOperands(); ++i) {
 516         //Get Operand
 517         const MachineOperand &mOp = (*I)->getOperand(i);
 518         if((mOp.getType() == MachineOperand::MO_VirtualRegister
 519             ||  mOp.getType() == MachineOperand::MO_CCRegister) && mOp.isUse()) {
 520
 521           //find the value in the map
 522           if (const Value* srcI = mOp.getVRegValue()) {
 523
 524             //Find value in the map
 525             std::map<const Value*, std::vector<OpIndexNodePair> >::iterator V
 526               = valuetoNodeMap.find(srcI);
 527
 528             //If there is something in the map already, add edges from
 529             //those instructions
 530             //to this one we are processing
 531             if(V != valuetoNodeMap.end()) {
 532               addValueEdges(V->second, node, mOp.isUse(), mOp.isDef(),
 533                             phiInstrs, 1);
 534             }
 535           }
 536         }
 537       }
 538     }
 539   }
 540 }
 541 //Add dependencies for Value*s
 542 void MSchedGraph::addValueEdges(std::vector<OpIndexNodePair> &NodesInMap,
 543                                 MSchedGraphNode *destNode, bool nodeIsUse,
 544                                 bool nodeIsDef, std::vector<const MachineInstr*> &phiInstrs, int diff) {
 545
 546   for(std::vector<OpIndexNodePair>::iterator I = NodesInMap.begin(),
 547         E = NodesInMap.end(); I != E; ++I) {
 548
 549     //Get node in vectors machine operand that is the same value as node
 550     MSchedGraphNode *srcNode = I->second;
 551     MachineOperand mOp = srcNode->getInst()->getOperand(I->first);
 552
 553     if(diff > 0)
 554       if(std::find(phiInstrs.begin(), phiInstrs.end(), srcNode->getInst()) == phiInstrs.end())
 555         continue;
 556
 557     //Node is a Def, so add output dep.
 558     if(nodeIsDef) {
 559       if(mOp.isUse()) {
 560         DEBUG(std::cerr << "Edge from " << *srcNode << " to " << *destNode << " (itediff=" << diff << ", type=anti)\n");
 561         srcNode->addOutEdge(destNode, MSchedGraphEdge::ValueDep,
 562                             MSchedGraphEdge::AntiDep, diff);
 563       }
 564       if(mOp.isDef()) {
 565         DEBUG(std::cerr << "Edge from " << *srcNode << " to " << *destNode << " (itediff=" << diff << ", type=output)\n");
 566         srcNode->addOutEdge(destNode, MSchedGraphEdge::ValueDep,
 567                             MSchedGraphEdge::OutputDep, diff);
 568       }
 569     }
 570     if(nodeIsUse) {
 571       if(mOp.isDef()) {
 572         DEBUG(std::cerr << "Edge from " << *srcNode << " to " << *destNode << " (itediff=" << diff << ", type=true)\n");
 573         srcNode->addOutEdge(destNode, MSchedGraphEdge::ValueDep,
 574                             MSchedGraphEdge::TrueDep, diff);
 575       }
 576     }
 577   }
 578 }
 579
 580 //Add dependencies for machine registers across iterations
 581 void MSchedGraph::addMachRegEdges(std::map<int, std::vector<OpIndexNodePair> >& regNumtoNodeMap) {
 582   //Loop over all machine registers in the map, and add dependencies
 583   //between the instructions that use it
 584   typedef std::map<int, std::vector<OpIndexNodePair> > regNodeMap;
 585   for(regNodeMap::iterator I = regNumtoNodeMap.begin();
 586       I != regNumtoNodeMap.end(); ++I) {
 587     //Get the register number
 588     int regNum = (*I).first;
 589
 590     //Get Vector of nodes that use this register
 591     std::vector<OpIndexNodePair> Nodes = (*I).second;
 592
 593     //Loop over nodes and determine the dependence between the other
 594     //nodes in the vector
 595     for(unsigned i =0; i < Nodes.size(); ++i) {
 596
 597       //Get src node operator index that uses this machine register
 598       int srcOpIndex = Nodes[i].first;
 599
 600       //Get the actual src Node
 601       MSchedGraphNode *srcNode = Nodes[i].second;
 602
 603       //Get Operand
 604       const MachineOperand &srcMOp = srcNode->getInst()->getOperand(srcOpIndex);
 605
 606       bool srcIsUseandDef = srcMOp.isDef() && srcMOp.isUse();
 607       bool srcIsUse = srcMOp.isUse() && !srcMOp.isDef();
 608
 609
 610       //Look at all instructions after this in execution order
 611       for(unsigned j=i+1; j < Nodes.size(); ++j) {
 612
 613         //Sink node is a write
 614         if(Nodes[j].second->getInst()->getOperand(Nodes[j].first).isDef()) {
 615                       //Src only uses the register (read)
 616             if(srcIsUse)
 617               srcNode->addOutEdge(Nodes[j].second,
 618                                   MSchedGraphEdge::MachineRegister,
 619                                   MSchedGraphEdge::AntiDep);
 620
 621             else if(srcIsUseandDef) {
 622               srcNode->addOutEdge(Nodes[j].second,
 623                                   MSchedGraphEdge::MachineRegister,
 624                                   MSchedGraphEdge::AntiDep);
 625
 626               srcNode->addOutEdge(Nodes[j].second,
 627                                   MSchedGraphEdge::MachineRegister,
 628                                   MSchedGraphEdge::OutputDep);
 629             }
 630             else
 631               srcNode->addOutEdge(Nodes[j].second,
 632                                   MSchedGraphEdge::MachineRegister,
 633                                   MSchedGraphEdge::OutputDep);
 634         }
 635         //Dest node is a read
 636         else {
 637           if(!srcIsUse || srcIsUseandDef)
 638             srcNode->addOutEdge(Nodes[j].second,
 639                                 MSchedGraphEdge::MachineRegister,
 640                                 MSchedGraphEdge::TrueDep);
 641         }
 642
 643       }
 644
 645       //Look at all the instructions before this one since machine registers
 646       //could live across iterations.
 647       for(unsigned j = 0; j < i; ++j) {
 648                 //Sink node is a write
 649         if(Nodes[j].second->getInst()->getOperand(Nodes[j].first).isDef()) {
 650                       //Src only uses the register (read)
 651             if(srcIsUse)
 652               srcNode->addOutEdge(Nodes[j].second,
 653                                   MSchedGraphEdge::MachineRegister,
 654                                   MSchedGraphEdge::AntiDep, 1);
 655             else if(srcIsUseandDef) {
 656               srcNode->addOutEdge(Nodes[j].second,
 657                                   MSchedGraphEdge::MachineRegister,
 658                                   MSchedGraphEdge::AntiDep, 1);
 659
 660               srcNode->addOutEdge(Nodes[j].second,
 661                                   MSchedGraphEdge::MachineRegister,
 662                                   MSchedGraphEdge::OutputDep, 1);
 663             }
 664             else
 665               srcNode->addOutEdge(Nodes[j].second,
 666                                   MSchedGraphEdge::MachineRegister,
 667                                   MSchedGraphEdge::OutputDep, 1);
 668         }
 669         //Dest node is a read
 670         else {
 671           if(!srcIsUse || srcIsUseandDef)
 672             srcNode->addOutEdge(Nodes[j].second,
 673                                 MSchedGraphEdge::MachineRegister,
 674                                 MSchedGraphEdge::TrueDep,1 );
 675         }
 676
 677
 678       }
 679
 680     }
 681
 682   }
 683
 684 }
 685
 686 //Add edges between all loads and stores
 687 //Can be less strict with alias analysis and data dependence analysis.
 688 void MSchedGraph::addMemEdges(const std::vector<MSchedGraphNode*>& memInst,
 689                       DependenceAnalyzer &DA,
 690                       std::map<MachineInstr*, Instruction*> &machineTollvm) {
 691
 692   //Get Target machine instruction info
 693   const TargetInstrInfo *TMI = Target.getInstrInfo();
 694
 695   //Loop over all memory instructions in the vector
 696   //Knowing that they are in execution, add true, anti, and output dependencies
 697   for (unsigned srcIndex = 0; srcIndex < memInst.size(); ++srcIndex) {
 698
 699     MachineInstr *srcInst = (MachineInstr*) memInst[srcIndex]->getInst();
 700
 701     //Get the machine opCode to determine type of memory instruction
 702     MachineOpCode srcNodeOpCode = srcInst->getOpcode();
 703
 704     //All instructions after this one in execution order have an
 705     //iteration delay of 0
 706     for(unsigned destIndex = 0; destIndex < memInst.size(); ++destIndex) {
 707
 708       //No self loops
 709       if(destIndex == srcIndex)
 710         continue;
 711
 712       MachineInstr *destInst = (MachineInstr*) memInst[destIndex]->getInst();
 713
 714       DEBUG(std::cerr << "MInst1: " << *srcInst << "\n");
 715       DEBUG(std::cerr << "MInst2: " << *destInst << "\n");
 716
 717       //Assuming instructions without corresponding llvm instructions
 718       //are from constant pools.
 719       if (!machineTollvm.count(srcInst) || !machineTollvm.count(destInst))
 720         continue;
 721
 722       bool useDepAnalyzer = true;
 723
 724       //Some machine loads and stores are generated by casts, so be
 725       //conservative and always add deps
 726       Instruction *srcLLVM = machineTollvm[srcInst];
 727       Instruction *destLLVM = machineTollvm[destInst];
 728       if(!isa<LoadInst>(srcLLVM)
 729          && !isa<StoreInst>(srcLLVM)) {
 730         if(isa<BinaryOperator>(srcLLVM)) {
 731           if(isa<ConstantFP>(srcLLVM->getOperand(0)) || isa<ConstantFP>(srcLLVM->getOperand(1)))
 732             continue;
 733         }
 734         useDepAnalyzer = false;
 735       }
 736       if(!isa<LoadInst>(destLLVM)
 737          && !isa<StoreInst>(destLLVM)) {
 738         if(isa<BinaryOperator>(destLLVM)) {
 739           if(isa<ConstantFP>(destLLVM->getOperand(0)) || isa<ConstantFP>(destLLVM->getOperand(1)))
 740             continue;
 741         }
 742         useDepAnalyzer = false;
 743       }
 744
 745       //Use dep analysis when we have corresponding llvm loads/stores
 746       if(useDepAnalyzer) {
 747         bool srcBeforeDest = true;
 748         if(destIndex < srcIndex)
 749           srcBeforeDest = false;
 750
 751         DependenceResult dr = DA.getDependenceInfo(machineTollvm[srcInst],
 752                                                    machineTollvm[destInst],
 753                                                    srcBeforeDest);
 754
 755         for(std::vector<Dependence>::iterator d = dr.dependences.begin(),
 756               de = dr.dependences.end(); d != de; ++d) {
 757           //Add edge from load to store
 758           memInst[srcIndex]->addOutEdge(memInst[destIndex],
 759                                         MSchedGraphEdge::MemoryDep,
 760                                         d->getDepType(), d->getIteDiff());
 761
 762         }
 763       }
 764       //Otherwise, we can not do any further analysis and must make a dependence
 765       else {
 766
 767         //Get the machine opCode to determine type of memory instruction
 768         MachineOpCode destNodeOpCode = destInst->getOpcode();
 769
 770         //Get the Value* that we are reading from the load, always the first op
 771         const MachineOperand &mOp = srcInst->getOperand(0);
 772         const MachineOperand &mOp2 = destInst->getOperand(0);
 773
 774         if(mOp.hasAllocatedReg())
 775           if(mOp.getReg() == SparcV9::g0)
 776             continue;
 777         if(mOp2.hasAllocatedReg())
 778           if(mOp2.getReg() == SparcV9::g0)
 779             continue;
 780
 781         DEBUG(std::cerr << "Adding dependence for machine instructions\n");
 782         //Load-Store deps
 783         if(TMI->isLoad(srcNodeOpCode)) {
 784
 785           if(TMI->isStore(destNodeOpCode))
 786             memInst[srcIndex]->addOutEdge(memInst[destIndex],
 787                                           MSchedGraphEdge::MemoryDep,
 788                                           MSchedGraphEdge::AntiDep, 0);
 789         }
 790         else if(TMI->isStore(srcNodeOpCode)) {
 791           if(TMI->isStore(destNodeOpCode))
 792             memInst[srcIndex]->addOutEdge(memInst[destIndex],
 793                                           MSchedGraphEdge::MemoryDep,
 794                                           MSchedGraphEdge::OutputDep, 0);
 795
 796           else
 797             memInst[srcIndex]->addOutEdge(memInst[destIndex],
 798                                           MSchedGraphEdge::MemoryDep,
 799                                           MSchedGraphEdge::TrueDep, 0);
 800         }
 801       }
 802     }
 803   }
 804 }