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