lib/CodeGen/InstrSched/SchedGraph.cpp

   1 /*
   2  ****************************************************************************
   3  * File:
   4  *      SchedGraph.cpp
   5  *
   6  * Purpose:
   7  *      Scheduling graph based on SSA graph plus extra dependence edges
   8  *      capturing dependences due to machine resources (machine registers,
   9  *      CC registers, and any others).
  10  *
  11  * History:
  12  *      7/20/01  -  Vikram Adve  -  Created
  13  ***************************************************************************/
  14
  15 #include "llvm/InstrTypes.h"
  16 #include "llvm/Instruction.h"
  17 #include "llvm/BasicBlock.h"
  18 #include "llvm/Method.h"
  19 #include "llvm/CodeGen/SchedGraph.h"
  20 #include "llvm/CodeGen/MachineInstr.h"
  21 #include "llvm/Target/Machine.h"
  22 #include "llvm/Support/StringExtras.h"
  23 #include <algorithm>
  24
  25 //************************* Class Implementations **************************/
  26
  27 //
  28 // class SchedGraphEdge
  29 //
  30
  31 /*ctor*/
  32 SchedGraphEdge::SchedGraphEdge(SchedGraphNode* _src,
  33                                SchedGraphNode* _sink,
  34                                SchedGraphEdgeDepType _depType,
  35                                DataDepOrderType _depOrderType,
  36                                int _minDelay)
  37   : src(_src),
  38     sink(_sink),
  39     depType(_depType),
  40     depOrderType(_depOrderType),
  41     val(NULL),
  42     minDelay((_minDelay >= 0)? _minDelay : _src->getLatency())
  43 {
  44   src->addOutEdge(this);
  45   sink->addInEdge(this);
  46 }
  47
  48
  49 /*ctor*/
  50 SchedGraphEdge::SchedGraphEdge(SchedGraphNode* _src,
  51                                SchedGraphNode* _sink,
  52                                Value* _val,
  53                                DataDepOrderType _depOrderType,
  54                                int _minDelay)
  55   : src(_src),
  56     sink(_sink),
  57     depType(DefUseDep),
  58     depOrderType(_depOrderType),
  59     val(_val),
  60     minDelay((_minDelay >= 0)? _minDelay : _src->getLatency())
  61 {
  62   src->addOutEdge(this);
  63   sink->addInEdge(this);
  64 }
  65
  66
  67 /*ctor*/
  68 SchedGraphEdge::SchedGraphEdge(SchedGraphNode* _src,
  69                                SchedGraphNode* _sink,
  70                                unsigned int    _regNum,
  71                                DataDepOrderType _depOrderType,
  72                                int _minDelay)
  73   : src(_src),
  74     sink(_sink),
  75     depType(MachineRegister),
  76     depOrderType(_depOrderType),
  77     minDelay((_minDelay >= 0)? _minDelay : _src->getLatency()),
  78     machineRegNum(_regNum)
  79 {
  80   src->addOutEdge(this);
  81   sink->addInEdge(this);
  82 }
  83
  84
  85 /*ctor*/
  86 SchedGraphEdge::SchedGraphEdge(SchedGraphNode* _src,
  87                                SchedGraphNode* _sink,
  88                                ResourceId      _resourceId,
  89                                int _minDelay)
  90   : src(_src),
  91     sink(_sink),
  92     depType(MachineResource),
  93     depOrderType(NonDataDep),
  94     minDelay((_minDelay >= 0)? _minDelay : _src->getLatency()),
  95     resourceId(_resourceId)
  96 {
  97   src->addOutEdge(this);
  98   sink->addInEdge(this);
  99 }
 100
 101 void SchedGraphEdge::dump(int indent=0) const {
 102   printIndent(indent); cout << *this;
 103 }
 104
 105
 106 //
 107 // class SchedGraphNode
 108 //
 109
 110 /*ctor*/
 111 SchedGraphNode::SchedGraphNode(unsigned int _nodeId,
 112                                const Instruction* _instr,
 113                                const MachineInstr* _minstr,
 114                                const TargetMachine& target)
 115   : nodeId(_nodeId),
 116     instr(_instr),
 117     minstr(_minstr),
 118     latency(0)
 119 {
 120   if (minstr)
 121     {
 122       MachineOpCode mopCode = minstr->getOpCode();
 123       latency = target.getInstrInfo().hasResultInterlock(mopCode)
 124         ? target.getInstrInfo().minLatency(mopCode)
 125         : target.getInstrInfo().maxLatency(mopCode);
 126     }
 127 }
 128
 129
 130 /*dtor*/
 131 SchedGraphNode::~SchedGraphNode()
 132 {
 133   // a node deletes its outgoing edges only
 134   for (unsigned i=0, N=outEdges.size(); i < N; i++)
 135     delete outEdges[i];
 136 }
 137
 138 void SchedGraphNode::dump(int indent=0) const {
 139   printIndent(indent); cout << *this;
 140 }
 141
 142
 143 inline void
 144 SchedGraphNode::addInEdge(SchedGraphEdge* edge)
 145 {
 146   inEdges.push_back(edge);
 147 }
 148
 149
 150 inline void
 151 SchedGraphNode::addOutEdge(SchedGraphEdge* edge)
 152 {
 153   outEdges.push_back(edge);
 154 }
 155
 156 inline void
 157 SchedGraphNode::removeInEdge(const SchedGraphEdge* edge)
 158 {
 159   assert(edge->getSink() == this);
 160   for (iterator I = beginInEdges(); I != endInEdges(); ++I)
 161     if ((*I) == edge)
 162       {
 163         inEdges.erase(I);
 164         break;
 165       }
 166 }
 167
 168 inline void
 169 SchedGraphNode::removeOutEdge(const SchedGraphEdge* edge)
 170 {
 171   assert(edge->getSrc() == this);
 172   for (iterator I = beginOutEdges(); I != endOutEdges(); ++I)
 173     if ((*I) == edge)
 174       {
 175         outEdges.erase(I);
 176         break;
 177       }
 178 }
 179
 180 void
 181 SchedGraphNode::eraseAllEdges()
 182 {
 183   // Disconnect and delete all in-edges and out-edges for the node.
 184   // Note that we delete the in-edges too since they have been
 185   // disconnected from the source node and will not be deleted there.
 186   for (iterator I = beginInEdges(); I != endInEdges(); ++I)
 187     {
 188       (*I)->getSrc()->removeOutEdge(*I);
 189       delete *I;
 190     }
 191   for (iterator I = beginOutEdges(); I != endOutEdges(); ++I)
 192     {
 193       (*I)->getSink()->removeInEdge(*I);
 194       delete *I;
 195     }
 196   inEdges.clear();
 197   outEdges.clear();
 198 }
 199
 200
 201 //
 202 // class SchedGraph
 203 //
 204
 205
 206 /*ctor*/
 207 SchedGraph::SchedGraph(const BasicBlock* bb,
 208                        const TargetMachine& target)
 209 {
 210   bbVec.push_back(bb);
 211   this->buildGraph(target);
 212 }
 213
 214
 215 /*dtor*/
 216 SchedGraph::~SchedGraph()
 217 {
 218   // delete all the nodes.  each node deletes its out-edges.
 219   for (iterator I=begin(); I != end(); ++I)
 220     delete (*I).second;
 221 }
 222
 223
 224 void
 225 SchedGraph::dump() const
 226 {
 227   cout << "  Sched Graph for Basic Blocks: ";
 228   for (unsigned i=0, N=bbVec.size(); i < N; i++)
 229     {
 230       cout << (bbVec[i]->hasName()? bbVec[i]->getName() : "block")
 231            << " (" << bbVec[i] << ")"
 232            << ((i == N-1)? "" : ", ");
 233     }
 234
 235   cout << endl << endl << "    Actual Root nodes : ";
 236   for (unsigned i=0, N=graphRoot->outEdges.size(); i < N; i++)
 237     cout << graphRoot->outEdges[i]->getSink()->getNodeId()
 238          << ((i == N-1)? "" : ", ");
 239
 240   cout << endl << "    Graph Nodes:" << endl;
 241   for (const_iterator I=begin(); I != end(); ++I)
 242     cout << endl << * (*I).second;
 243
 244   cout << endl;
 245 }
 246
 247
 248 void
 249 SchedGraph::addDummyEdges()
 250 {
 251   assert(graphRoot->outEdges.size() == 0);
 252
 253   for (const_iterator I=begin(); I != end(); ++I)
 254     {
 255       SchedGraphNode* node = (*I).second;
 256       assert(node != graphRoot && node != graphLeaf);
 257       if (node->beginInEdges() == node->endInEdges())
 258         (void) new SchedGraphEdge(graphRoot, node, SchedGraphEdge::CtrlDep,
 259                                   SchedGraphEdge::NonDataDep, 0);
 260       if (node->beginOutEdges() == node->endOutEdges())
 261         (void) new SchedGraphEdge(node, graphLeaf, SchedGraphEdge::CtrlDep,
 262                                   SchedGraphEdge::NonDataDep, 0);
 263     }
 264 }
 265
 266
 267 void
 268 SchedGraph::addCDEdges(const TerminatorInst* term,
 269                        const TargetMachine& target)
 270 {
 271   const MachineInstrInfo& mii = target.getInstrInfo();
 272   MachineCodeForVMInstr& termMvec = term->getMachineInstrVec();
 273
 274   // Find the first branch instr in the sequence of machine instrs for term
 275   //
 276   unsigned first = 0;
 277   while (! mii.isBranch(termMvec[first]->getOpCode()))
 278     ++first;
 279   assert(first < termMvec.size() &&
 280          "No branch instructions for BR?  Ok, but weird!  Delete assertion.");
 281   if (first == termMvec.size())
 282     return;
 283
 284   SchedGraphNode* firstBrNode = this->getGraphNodeForInstr(termMvec[first]);
 285
 286   // Add CD edges from each instruction in the sequence to the
 287   // *last preceding* branch instr. in the sequence
 288   //
 289   for (int i = (int) termMvec.size()-1; i > (int) first; i--)
 290     {
 291       SchedGraphNode* toNode = this->getGraphNodeForInstr(termMvec[i]);
 292       assert(toNode && "No node for instr generated for branch?");
 293
 294       for (int j = i-1; j >= 0; j--)
 295         if (mii.isBranch(termMvec[j]->getOpCode()))
 296           {
 297             SchedGraphNode* brNode = this->getGraphNodeForInstr(termMvec[j]);
 298             assert(brNode && "No node for instr generated for branch?");
 299             (void) new SchedGraphEdge(brNode, toNode, SchedGraphEdge::CtrlDep,
 300                                       SchedGraphEdge::NonDataDep, 0);
 301             break;                      // only one incoming edge is enough
 302           }
 303     }
 304
 305   // Add CD edges from each instruction preceding the first branch
 306   // to the first branch
 307   //
 308   for (int i = first-1; i >= 0; i--)
 309     {
 310       SchedGraphNode* fromNode = this->getGraphNodeForInstr(termMvec[i]);
 311       assert(fromNode && "No node for instr generated for branch?");
 312       (void) new SchedGraphEdge(fromNode, firstBrNode, SchedGraphEdge::CtrlDep,
 313                                 SchedGraphEdge::NonDataDep, 0);
 314     }
 315
 316   // Now add CD edges to the first branch instruction in the sequence
 317   // from all preceding instructions in the basic block.
 318   //
 319   const BasicBlock* bb = term->getParent();
 320   for (BasicBlock::const_iterator II = bb->begin(); II != bb->end(); ++II)
 321     {
 322       if ((*II) == (const Instruction*) term)   // special case, handled above
 323         continue;
 324
 325       assert(! (*II)->isTerminator() && "Two terminators in basic block?");
 326
 327       const MachineCodeForVMInstr& mvec = (*II)->getMachineInstrVec();
 328       for (unsigned i=0, N=mvec.size(); i < N; i++)
 329         {
 330           SchedGraphNode* fromNode = this->getGraphNodeForInstr(mvec[i]);
 331           if (fromNode == NULL)
 332             continue;                   // dummy instruction, e.g., PHI
 333
 334           (void) new SchedGraphEdge(fromNode, firstBrNode,
 335                                     SchedGraphEdge::CtrlDep,
 336                                     SchedGraphEdge::NonDataDep, 0);
 337
 338           // If we find any other machine instructions (other than due to
 339           // the terminator) that also have delay slots, add an outgoing edge
 340           // from the instruction to the instructions in the delay slots.
 341           //
 342           unsigned d = mii.getNumDelaySlots(mvec[i]->getOpCode());
 343           assert(i+d < N && "Insufficient delay slots for instruction?");
 344
 345           for (unsigned j=1; j <= d; j++)
 346             {
 347               SchedGraphNode* toNode = this->getGraphNodeForInstr(mvec[i+j]);
 348               assert(toNode && "No node for machine instr in delay slot?");
 349               (void) new SchedGraphEdge(fromNode, toNode,
 350                                         SchedGraphEdge::CtrlDep,
 351                                       SchedGraphEdge::NonDataDep, 0);
 352             }
 353         }
 354     }
 355 }
 356
 357
 358 void
 359 SchedGraph::addMemEdges(const vector<const Instruction*>& memVec,
 360                         const TargetMachine& target)
 361 {
 362   const MachineInstrInfo& mii = target.getInstrInfo();
 363
 364   for (unsigned im=0, NM=memVec.size(); im < NM; im++)
 365     {
 366       const Instruction* fromInstr = memVec[im];
 367       bool fromIsLoad = fromInstr->getOpcode() == Instruction::Load;
 368
 369       for (unsigned jm=im+1; jm < NM; jm++)
 370         {
 371           const Instruction* toInstr = memVec[jm];
 372           bool toIsLoad = toInstr->getOpcode() == Instruction::Load;
 373           SchedGraphEdge::DataDepOrderType depOrderType;
 374
 375           if (fromIsLoad)
 376             {
 377               if (toIsLoad) continue;   // both instructions are loads
 378               depOrderType = SchedGraphEdge::AntiDep;
 379             }
 380           else
 381             {
 382               depOrderType = (toIsLoad)? SchedGraphEdge::TrueDep
 383                 : SchedGraphEdge::OutputDep;
 384             }
 385
 386           MachineCodeForVMInstr& fromInstrMvec=fromInstr->getMachineInstrVec();
 387           MachineCodeForVMInstr& toInstrMvec = toInstr->getMachineInstrVec();
 388
 389           // We have two VM memory instructions, and at least one is a store.
 390           // Add edges between all machine load/store instructions.
 391           //
 392           for (unsigned i=0, N=fromInstrMvec.size(); i < N; i++)
 393             {
 394               MachineOpCode fromOpCode = fromInstrMvec[i]->getOpCode();
 395               if (mii.isLoad(fromOpCode) || mii.isStore(fromOpCode))
 396                 {
 397                   SchedGraphNode* fromNode =
 398                     this->getGraphNodeForInstr(fromInstrMvec[i]);
 399                   assert(fromNode && "No node for memory instr?");
 400
 401                   for (unsigned j=0, M=toInstrMvec.size(); j < M; j++)
 402                     {
 403                       MachineOpCode toOpCode = toInstrMvec[j]->getOpCode();
 404                       if (mii.isLoad(toOpCode) || mii.isStore(toOpCode))
 405                         {
 406                           SchedGraphNode* toNode =
 407                             this->getGraphNodeForInstr(toInstrMvec[j]);
 408                           assert(toNode && "No node for memory instr?");
 409
 410                           (void) new SchedGraphEdge(fromNode, toNode,
 411                                                     SchedGraphEdge::MemoryDep,
 412                                                     depOrderType, 1);
 413                         }
 414                     }
 415                 }
 416             }
 417         }
 418     }
 419 }
 420
 421
 422 typedef vector< pair<SchedGraphNode*, unsigned int> > RegRefVec;
 423
 424 // The following needs to be a class, not a typedef, so we can use
 425 // an opaque declaration in SchedGraph.h
 426 class NodeToRegRefMap: public hash_map<int, RegRefVec> {
 427   typedef hash_map<int, RegRefVec>::      iterator iterator;
 428   typedef hash_map<int, RegRefVec>::const_iterator const_iterator;
 429 };
 430
 431
 432 void
 433 SchedGraph::addMachineRegEdges(NodeToRegRefMap& regToRefVecMap,
 434                                const TargetMachine& target)
 435 {
 436   assert(bbVec.size() == 1 && "Only handling a single basic block here");
 437
 438   // This assumes that such hardwired registers are never allocated
 439   // to any LLVM value (since register allocation happens later), i.e.,
 440   // any uses or defs of this register have been made explicit!
 441   // Also assumes that two registers with different numbers are
 442   // not aliased!
 443   //
 444   for (NodeToRegRefMap::iterator I = regToRefVecMap.begin();
 445        I != regToRefVecMap.end(); ++I)
 446     {
 447       int regNum           = (*I).first;
 448       RegRefVec& regRefVec = (*I).second;
 449
 450       // regRefVec is ordered by control flow order in the basic block
 451       int lastDefIdx = -1;
 452       for (unsigned i=0; i < regRefVec.size(); ++i)
 453         {
 454           SchedGraphNode* node = regRefVec[i].first;
 455           bool isDef           = regRefVec[i].second;
 456
 457           if (isDef)
 458             { // Each def gets an output edge from the last def
 459               if (lastDefIdx > 0)
 460                 new SchedGraphEdge(regRefVec[lastDefIdx].first, node, regNum,
 461                                    SchedGraphEdge::OutputDep);
 462
 463               // Also, an anti edge from all uses *since* the last def,
 464               // But don't add edge from an instruction to itself!
 465               for (int u = 1 + lastDefIdx; u < (int) i; u++)
 466                 if (regRefVec[u].first != node)
 467                   new SchedGraphEdge(regRefVec[u].first, node, regNum,
 468                                      SchedGraphEdge::AntiDep);
 469             }
 470           else
 471             { // Each use gets a true edge from the last def
 472               if (lastDefIdx > 0)
 473                 new SchedGraphEdge(regRefVec[lastDefIdx].first, node, regNum);
 474             }
 475         }
 476     }
 477 }
 478
 479
 480 void
 481 SchedGraph::addSSAEdge(SchedGraphNode* node,
 482                        Value* val,
 483                        const TargetMachine& target)
 484 {
 485   if (!val->isInstruction()) return;
 486
 487   const Instruction* thisVMInstr = node->getInstr();
 488   const Instruction* defVMInstr  = (const Instruction*) val;
 489
 490   // Phi instructions are the only ones that produce a value but don't get
 491   // any non-dummy machine instructions.  Return here as an optimization.
 492   //
 493   if (defVMInstr->isPHINode())
 494     return;
 495
 496   // Now add the graph edge for the appropriate machine instruction(s).
 497   // Note that multiple machine instructions generated for the
 498   // def VM instruction may modify the register for the def value.
 499   //
 500   MachineCodeForVMInstr& defMvec = defVMInstr->getMachineInstrVec();
 501   const MachineInstrInfo& mii = target.getInstrInfo();
 502
 503   for (unsigned i=0, N=defMvec.size(); i < N; i++)
 504     for (int o=0, N = mii.getNumOperands(defMvec[i]->getOpCode()); o < N; o++)
 505       {
 506         const MachineOperand& defOp = defMvec[i]->getOperand(o);
 507
 508         if (defOp.opIsDef()
 509             && (defOp.getOperandType() == MachineOperand::MO_VirtualRegister
 510                 || defOp.getOperandType() == MachineOperand::MO_CCRegister)
 511             && (defOp.getVRegValue() == val))
 512           {
 513             // this instruction does define value `val'.
 514             // if there is a node for it in the same graph, add an edge.
 515             SchedGraphNode* defNode = this->getGraphNodeForInstr(defMvec[i]);
 516             if (defNode != NULL)
 517               (void) new SchedGraphEdge(defNode, node, val);
 518           }
 519       }
 520 }
 521
 522
 523 void
 524 SchedGraph::addEdgesForInstruction(SchedGraphNode* node,
 525                                    NodeToRegRefMap& regToRefVecMap,
 526                                    const TargetMachine& target)
 527 {
 528   const Instruction& instr = * node->getInstr();        // No dummy nodes here!
 529   const MachineInstr& minstr = * node->getMachineInstr();
 530
 531   // Add incoming edges for the following:
 532   // (1) operands of the machine instruction, including hidden operands
 533   // (2) machine register dependences
 534   // (3) other resource dependences for the machine instruction, if any
 535   // Also, note any uses or defs of machine registers.
 536   //
 537   for (unsigned i=0, numOps=minstr.getNumOperands(); i < numOps; i++)
 538     {
 539       const MachineOperand& mop = minstr.getOperand(i);
 540
 541       // if this writes to a machine register other than the hardwired
 542       // "zero" register used on many processors, record the reference.
 543       if (mop.getOperandType() == MachineOperand::MO_MachineRegister
 544           && (! (target.zeroRegNum >= 0
 545                  && mop.getMachineRegNum()==(unsigned) target.zeroRegNum)))
 546         {
 547           regToRefVecMap[mop.getMachineRegNum()].
 548             push_back(make_pair(node, i));
 549         }
 550
 551       // ignore all other def operands
 552       if (minstr.operandIsDefined(i))
 553         continue;
 554
 555       switch(mop.getOperandType())
 556         {
 557         case MachineOperand::MO_VirtualRegister:
 558         case MachineOperand::MO_CCRegister:
 559           if (mop.getVRegValue())
 560             addSSAEdge(node, mop.getVRegValue(), target);
 561           break;
 562
 563         case MachineOperand::MO_MachineRegister:
 564           break;
 565
 566         case MachineOperand::MO_SignExtendedImmed:
 567         case MachineOperand::MO_UnextendedImmed:
 568         case MachineOperand::MO_PCRelativeDisp:
 569           break;        // nothing to do for immediate fields
 570
 571         default:
 572           assert(0 && "Unknown machine operand type in SchedGraph builder");
 573           break;
 574         }
 575     }
 576
 577   // add all true, anti,
 578   // and output dependences for this register.  but ignore
 579
 580 }
 581
 582
 583 void
 584 SchedGraph::buildGraph(const TargetMachine& target)
 585 {
 586   const MachineInstrInfo& mii = target.getInstrInfo();
 587   const BasicBlock* bb = bbVec[0];
 588
 589   assert(bbVec.size() == 1 && "Only handling a single basic block here");
 590
 591   // Use this data structures to note all LLVM memory instructions.
 592   // We use this to add memory dependence edges without a second full walk.
 593   //
 594   vector<const Instruction*> memVec;
 595
 596   // Use this data structures to note any uses or definitions of
 597   // machine registers so we can add edges for those later without
 598   // extra passes over the nodes.
 599   // The vector holds an ordered list of references to the machine reg,
 600   // ordered according to control-flow order.  This only works for a
 601   // single basic block, hence the assertion.  Each reference is identified
 602   // by the pair: <node, operand-number>.
 603   //
 604   NodeToRegRefMap regToRefVecMap;
 605
 606   // Make a dummy root node.  We'll add edges to the real roots later.
 607   graphRoot = new SchedGraphNode(0, NULL, NULL, target);
 608   graphLeaf = new SchedGraphNode(1, NULL, NULL, target);
 609
 610   //----------------------------------------------------------------
 611   // First add nodes for all the machine instructions in the basic block.
 612   // This greatly simplifies identifing which edges to add.
 613   // Also, remember the load/store instructions to add memory deps later.
 614   //----------------------------------------------------------------
 615
 616   for (BasicBlock::const_iterator II = bb->begin(); II != bb->end(); ++II)
 617     {
 618       const Instruction *instr = *II;
 619       const MachineCodeForVMInstr& mvec = instr->getMachineInstrVec();
 620       for (unsigned i=0, N=mvec.size(); i < N; i++)
 621         if (! mii.isDummyPhiInstr(mvec[i]->getOpCode()))
 622           {
 623             SchedGraphNode* node = new SchedGraphNode(getNumNodes(),
 624                                                       instr, mvec[i], target);
 625             this->noteGraphNodeForInstr(mvec[i], node);
 626           }
 627
 628       if (instr->getOpcode() == Instruction::Load ||
 629           instr->getOpcode() == Instruction::Store)
 630         memVec.push_back(instr);
 631     }
 632
 633   //----------------------------------------------------------------
 634   // Now add the edges.
 635   //----------------------------------------------------------------
 636
 637   // First, add edges to the terminator instruction of the basic block.
 638   this->addCDEdges(bb->getTerminator(), target);
 639
 640   // Then add memory dep edges: store->load, load->store, and store->store
 641   this->addMemEdges(memVec, target);
 642
 643   // Then add other edges for all instructions in the block.
 644   for (SchedGraph::iterator GI = this->begin(); GI != this->end(); ++GI)
 645     {
 646       SchedGraphNode* node = (*GI).second;
 647       addEdgesForInstruction(node, regToRefVecMap, target);
 648     }
 649
 650   // Then add edges for dependences on machine registers
 651   this->addMachineRegEdges(regToRefVecMap, target);
 652
 653   // Finally, add edges from the dummy root and to dummy leaf
 654   this->addDummyEdges();
 655 }
 656
 657
 658 //
 659 // class SchedGraphSet
 660 //
 661
 662 /*ctor*/
 663 SchedGraphSet::SchedGraphSet(const Method* _method,
 664                              const TargetMachine& target) :
 665   method(_method)
 666 {
 667   buildGraphsForMethod(method, target);
 668 }
 669
 670
 671 /*dtor*/
 672 SchedGraphSet::~SchedGraphSet()
 673 {
 674   // delete all the graphs
 675   for (iterator I=begin(); I != end(); ++I)
 676     delete (*I).second;
 677 }
 678
 679
 680 void
 681 SchedGraphSet::dump() const
 682 {
 683   cout << "======== Sched graphs for method `"
 684        << (method->hasName()? method->getName() : "???")
 685        << "' ========" << endl << endl;
 686
 687   for (const_iterator I=begin(); I != end(); ++I)
 688     (*I).second->dump();
 689
 690   cout << endl << "====== End graphs for method `"
 691        << (method->hasName()? method->getName() : "")
 692        << "' ========" << endl << endl;
 693 }
 694
 695
 696 void
 697 SchedGraphSet::buildGraphsForMethod(const Method *method,
 698                                     const TargetMachine& target)
 699 {
 700   for (Method::const_iterator BI = method->begin(); BI != method->end(); ++BI)
 701     {
 702       SchedGraph* graph = new SchedGraph(*BI, target);
 703       this->noteGraphForBlock(*BI, graph);
 704     }
 705 }
 706
 707
 708
 709 ostream&
 710 operator<<(ostream& os, const SchedGraphEdge& edge)
 711 {
 712   os << "edge [" << edge.src->getNodeId() << "] -> ["
 713      << edge.sink->getNodeId() << "] : ";
 714
 715   switch(edge.depType) {
 716   case SchedGraphEdge::CtrlDep:         os<< "Control Dep"; break;
 717   case SchedGraphEdge::DefUseDep:       os<< "Reg Value " << edge.val; break;
 718   case SchedGraphEdge::MemoryDep:       os<< "Mem Value " << edge.val; break;
 719   case SchedGraphEdge::MachineRegister: os<< "Reg " <<edge.machineRegNum;break;
 720   case SchedGraphEdge::MachineResource: os<<"Resource "<<edge.resourceId;break;
 721   default: assert(0); break;
 722   }
 723
 724   os << " : delay = " << edge.minDelay << endl;
 725
 726   return os;
 727 }
 728
 729 ostream&
 730 operator<<(ostream& os, const SchedGraphNode& node)
 731 {
 732   printIndent(4, os);
 733   os << "Node " << node.nodeId << " : "
 734      << "latency = " << node.latency << endl;
 735
 736   printIndent(6, os);
 737
 738   if (node.getMachineInstr() == NULL)
 739     os << "(Dummy node)" << endl;
 740   else
 741     {
 742       os << *node.getMachineInstr() << endl;
 743
 744       printIndent(6, os);
 745       os << node.inEdges.size() << " Incoming Edges:" << endl;
 746       for (unsigned i=0, N=node.inEdges.size(); i < N; i++)
 747         {
 748           printIndent(8, os);
 749           os << * node.inEdges[i];
 750         }
 751
 752       printIndent(6, os);
 753       os << node.outEdges.size() << " Outgoing Edges:" << endl;
 754       for (unsigned i=0, N=node.outEdges.size(); i < N; i++)
 755         {
 756           printIndent(8, os);
 757           os << * node.outEdges[i];
 758         }
 759     }
 760
 761   return os;
 762 }