lib/Target/SparcV9/InstrSched/SchedGraph.cpp

   1 /****************************************************************************
   2  * File:
   3  *      SchedGraph.cpp
   4  *
   5  * Purpose:
   6  *      Scheduling graph based on SSA graph plus extra dependence edges
   7  *      capturing dependences due to machine resources (machine registers,
   8  *      CC registers, and any others).
   9  *
  10  * History:
  11  *      7/20/01  -  Vikram Adve  -  Created
  12  ***************************************************************************/
  13
  14 #include "SchedGraph.h"
  15 #include "llvm/InstrTypes.h"
  16 #include "llvm/Instruction.h"
  17 #include "llvm/BasicBlock.h"
  18 #include "llvm/Method.h"
  19 #include "llvm/CodeGen/MachineInstr.h"
  20 #include "llvm/Target/InstInfo.h"
  21 #include "llvm/Support/StringExtras.h"
  22 #include <algorithm>
  23
  24 //
  25 // class SchedGraphEdge
  26 //
  27
  28 /*ctor*/
  29 SchedGraphEdge::SchedGraphEdge(SchedGraphNode* _src,
  30                                SchedGraphNode* _sink,
  31                                SchedGraphEdgeDepType _depType,
  32                                DataDepOrderType _depOrderType,
  33                                int _minDelay)
  34   : src(_src),
  35     sink(_sink),
  36     depType(_depType),
  37     depOrderType(_depOrderType),
  38     val(NULL),
  39     minDelay((_minDelay >= 0)? _minDelay : _src->getLatency())
  40 {
  41   src->addOutEdge(this);
  42   sink->addInEdge(this);
  43 }
  44
  45
  46 /*ctor*/
  47 SchedGraphEdge::SchedGraphEdge(SchedGraphNode* _src,
  48                                SchedGraphNode* _sink,
  49                                Value* _val,
  50                                DataDepOrderType _depOrderType,
  51                                int _minDelay)
  52   : src(_src),
  53     sink(_sink),
  54     depType(DefUseDep),
  55     depOrderType(_depOrderType),
  56     val(_val),
  57     minDelay((_minDelay >= 0)? _minDelay : _src->getLatency())
  58 {
  59   src->addOutEdge(this);
  60   sink->addInEdge(this);
  61 }
  62
  63
  64 /*ctor*/
  65 SchedGraphEdge::SchedGraphEdge(SchedGraphNode* _src,
  66                                SchedGraphNode* _sink,
  67                                unsigned int    _regNum,
  68                                DataDepOrderType _depOrderType,
  69                                int _minDelay)
  70   : src(_src),
  71     sink(_sink),
  72     depType(MachineRegister),
  73     depOrderType(_depOrderType),
  74     minDelay((_minDelay >= 0)? _minDelay : _src->getLatency()),
  75     machineRegNum(_regNum)
  76 {
  77   src->addOutEdge(this);
  78   sink->addInEdge(this);
  79 }
  80
  81
  82 /*ctor*/
  83 SchedGraphEdge::SchedGraphEdge(SchedGraphNode* _src,
  84                                SchedGraphNode* _sink,
  85                                ResourceId      _resourceId,
  86                                int _minDelay)
  87   : src(_src),
  88     sink(_sink),
  89     depType(MachineResource),
  90     depOrderType(NonDataDep),
  91     minDelay((_minDelay >= 0)? _minDelay : _src->getLatency()),
  92     resourceId(_resourceId)
  93 {
  94   src->addOutEdge(this);
  95   sink->addInEdge(this);
  96 }
  97
  98 void SchedGraphEdge::dump(int indent=0) const {
  99   printIndent(indent); cout << *this;
 100 }
 101
 102
 103 //
 104 // class SchedGraphNode
 105 //
 106
 107 /*ctor*/
 108 SchedGraphNode::SchedGraphNode(unsigned int _nodeId,
 109                                const Instruction* _instr,
 110                                const MachineInstr* _minstr,
 111                                const TargetMachine& target)
 112   : nodeId(_nodeId),
 113     instr(_instr),
 114     minstr(_minstr),
 115     latency(0)
 116 {
 117   if (minstr)
 118     {
 119       MachineOpCode mopCode = minstr->getOpCode();
 120       latency = target.getInstrInfo().hasResultInterlock(mopCode)
 121         ? target.getInstrInfo().minLatency(mopCode)
 122         : target.getInstrInfo().maxLatency(mopCode);
 123     }
 124 }
 125
 126
 127 /*dtor*/
 128 SchedGraphNode::~SchedGraphNode()
 129 {
 130   // a node deletes its outgoing edges only
 131   for (unsigned i=0, N=outEdges.size(); i < N; i++)
 132     delete outEdges[i];
 133 }
 134
 135 void SchedGraphNode::dump(int indent=0) const {
 136   printIndent(indent); cout << *this;
 137 }
 138
 139
 140 inline void
 141 SchedGraphNode::addInEdge(SchedGraphEdge* edge)
 142 {
 143   inEdges.push_back(edge);
 144 }
 145
 146
 147 inline void
 148 SchedGraphNode::addOutEdge(SchedGraphEdge* edge)
 149 {
 150   outEdges.push_back(edge);
 151 }
 152
 153 inline void
 154 SchedGraphNode::removeInEdge(const SchedGraphEdge* edge)
 155 {
 156   assert(edge->getSink() == this);
 157   for (iterator I = beginInEdges(); I != endInEdges(); ++I)
 158     if ((*I) == edge)
 159       {
 160         inEdges.erase(I);
 161         break;
 162       }
 163 }
 164
 165 inline void
 166 SchedGraphNode::removeOutEdge(const SchedGraphEdge* edge)
 167 {
 168   assert(edge->getSrc() == this);
 169   for (iterator I = beginOutEdges(); I != endOutEdges(); ++I)
 170     if ((*I) == edge)
 171       {
 172         outEdges.erase(I);
 173         break;
 174       }
 175 }
 176
 177 void
 178 SchedGraphNode::eraseAllEdges()
 179 {
 180   // Disconnect and delete all in-edges and out-edges for the node.
 181   // Note that we delete the in-edges too since they have been
 182   // disconnected from the source node and will not be deleted there.
 183   for (iterator I = beginInEdges(); I != endInEdges(); ++I)
 184     {
 185       (*I)->getSrc()->removeOutEdge(*I);
 186       delete *I;
 187     }
 188   for (iterator I = beginOutEdges(); I != endOutEdges(); ++I)
 189     {
 190       (*I)->getSink()->removeInEdge(*I);
 191       delete *I;
 192     }
 193   inEdges.clear();
 194   outEdges.clear();
 195 }
 196
 197
 198 //
 199 // class SchedGraph
 200 //
 201
 202
 203 /*ctor*/
 204 SchedGraph::SchedGraph(const BasicBlock* bb,
 205                        const TargetMachine& target)
 206 {
 207   bbVec.push_back(bb);
 208   this->buildGraph(target);
 209 }
 210
 211
 212 /*dtor*/
 213 SchedGraph::~SchedGraph()
 214 {
 215   // delete all the nodes.  each node deletes its out-edges.
 216   for (iterator I=begin(); I != end(); ++I)
 217     delete (*I).second;
 218 }
 219
 220
 221 void
 222 SchedGraph::dump() const
 223 {
 224   cout << "  Sched Graph for Basic Blocks: ";
 225   for (unsigned i=0, N=bbVec.size(); i < N; i++)
 226     {
 227       cout << (bbVec[i]->hasName()? bbVec[i]->getName() : "block")
 228            << " (" << bbVec[i] << ")"
 229            << ((i == N-1)? "" : ", ");
 230     }
 231
 232   cout << endl << endl << "    Actual Root nodes : ";
 233   for (unsigned i=0, N=graphRoot->outEdges.size(); i < N; i++)
 234     cout << graphRoot->outEdges[i]->getSink()->getNodeId()
 235          << ((i == N-1)? "" : ", ");
 236
 237   cout << endl << "    Graph Nodes:" << endl;
 238   for (const_iterator I=begin(); I != end(); ++I)
 239     cout << endl << * (*I).second;
 240
 241   cout << endl;
 242 }
 243
 244
 245 void
 246 SchedGraph::addDummyEdges()
 247 {
 248   assert(graphRoot->outEdges.size() == 0);
 249
 250   for (const_iterator I=begin(); I != end(); ++I)
 251     {
 252       SchedGraphNode* node = (*I).second;
 253       assert(node != graphRoot && node != graphLeaf);
 254       if (node->beginInEdges() == node->endInEdges())
 255         (void) new SchedGraphEdge(graphRoot, node, SchedGraphEdge::CtrlDep,
 256                                   SchedGraphEdge::NonDataDep, 0);
 257       if (node->beginOutEdges() == node->endOutEdges())
 258         (void) new SchedGraphEdge(node, graphLeaf, SchedGraphEdge::CtrlDep,
 259                                   SchedGraphEdge::NonDataDep, 0);
 260     }
 261 }
 262
 263
 264 void
 265 SchedGraph::addCDEdges(const TerminatorInst* term,
 266                        const TargetMachine& target)
 267 {
 268   const MachineInstrInfo& mii = target.getInstrInfo();
 269   MachineCodeForVMInstr& termMvec = term->getMachineInstrVec();
 270
 271   // Find the first branch instr in the sequence of machine instrs for term
 272   //
 273   unsigned first = 0;
 274   while (! mii.isBranch(termMvec[first]->getOpCode()))
 275     ++first;
 276   assert(first < termMvec.size() &&
 277          "No branch instructions for BR?  Ok, but weird!  Delete assertion.");
 278   if (first == termMvec.size())
 279     return;
 280
 281   SchedGraphNode* firstBrNode = this->getGraphNodeForInstr(termMvec[first]);
 282
 283   // Add CD edges from each instruction in the sequence to the
 284   // *last preceding* branch instr. in the sequence
 285   //
 286   for (int i = (int) termMvec.size()-1; i > (int) first; i--)
 287     {
 288       SchedGraphNode* toNode = this->getGraphNodeForInstr(termMvec[i]);
 289       assert(toNode && "No node for instr generated for branch?");
 290
 291       for (int j = i-1; j >= 0; j--)
 292         if (mii.isBranch(termMvec[j]->getOpCode()))
 293           {
 294             SchedGraphNode* brNode = this->getGraphNodeForInstr(termMvec[j]);
 295             assert(brNode && "No node for instr generated for branch?");
 296             (void) new SchedGraphEdge(brNode, toNode, SchedGraphEdge::CtrlDep,
 297                                       SchedGraphEdge::NonDataDep, 0);
 298             break;                      // only one incoming edge is enough
 299           }
 300     }
 301
 302   // Add CD edges from each instruction preceding the first branch
 303   // to the first branch
 304   //
 305   for (int i = first-1; i >= 0; i--)
 306     {
 307       SchedGraphNode* fromNode = this->getGraphNodeForInstr(termMvec[i]);
 308       assert(fromNode && "No node for instr generated for branch?");
 309       (void) new SchedGraphEdge(fromNode, firstBrNode, SchedGraphEdge::CtrlDep,
 310                                 SchedGraphEdge::NonDataDep, 0);
 311     }
 312
 313   // Now add CD edges to the first branch instruction in the sequence
 314   // from all preceding instructions in the basic block.
 315   //
 316   const BasicBlock* bb = term->getParent();
 317   for (BasicBlock::const_iterator II = bb->begin(); II != bb->end(); ++II)
 318     {
 319       if ((*II) == (const Instruction*) term)   // special case, handled above
 320         continue;
 321
 322       assert(! (*II)->isTerminator() && "Two terminators in basic block?");
 323
 324       const MachineCodeForVMInstr& mvec = (*II)->getMachineInstrVec();
 325       for (unsigned i=0, N=mvec.size(); i < N; i++)
 326         {
 327           SchedGraphNode* fromNode = this->getGraphNodeForInstr(mvec[i]);
 328           if (fromNode == NULL)
 329             continue;                   // dummy instruction, e.g., PHI
 330
 331           (void) new SchedGraphEdge(fromNode, firstBrNode,
 332                                     SchedGraphEdge::CtrlDep,
 333                                     SchedGraphEdge::NonDataDep, 0);
 334
 335           // If we find any other machine instructions (other than due to
 336           // the terminator) that also have delay slots, add an outgoing edge
 337           // from the instruction to the instructions in the delay slots.
 338           //
 339           unsigned d = mii.getNumDelaySlots(mvec[i]->getOpCode());
 340           assert(i+d < N && "Insufficient delay slots for instruction?");
 341
 342           for (unsigned j=1; j <= d; j++)
 343             {
 344               SchedGraphNode* toNode = this->getGraphNodeForInstr(mvec[i+j]);
 345               assert(toNode && "No node for machine instr in delay slot?");
 346               (void) new SchedGraphEdge(fromNode, toNode,
 347                                         SchedGraphEdge::CtrlDep,
 348                                       SchedGraphEdge::NonDataDep, 0);
 349             }
 350         }
 351     }
 352 }
 353
 354
 355 void
 356 SchedGraph::addMemEdges(const vector<const Instruction*>& memVec,
 357                         const TargetMachine& target)
 358 {
 359   const MachineInstrInfo& mii = target.getInstrInfo();
 360
 361   for (unsigned im=0, NM=memVec.size(); im < NM; im++)
 362     {
 363       const Instruction* fromInstr = memVec[im];
 364       bool fromIsLoad = fromInstr->getOpcode() == Instruction::Load;
 365
 366       for (unsigned jm=im+1; jm < NM; jm++)
 367         {
 368           const Instruction* toInstr = memVec[jm];
 369           bool toIsLoad = toInstr->getOpcode() == Instruction::Load;
 370           SchedGraphEdge::DataDepOrderType depOrderType;
 371
 372           if (fromIsLoad)
 373             {
 374               if (toIsLoad) continue;   // both instructions are loads
 375               depOrderType = SchedGraphEdge::AntiDep;
 376             }
 377           else
 378             {
 379               depOrderType = (toIsLoad)? SchedGraphEdge::TrueDep
 380                 : SchedGraphEdge::OutputDep;
 381             }
 382
 383           MachineCodeForVMInstr& fromInstrMvec=fromInstr->getMachineInstrVec();
 384           MachineCodeForVMInstr& toInstrMvec = toInstr->getMachineInstrVec();
 385
 386           // We have two VM memory instructions, and at least one is a store.
 387           // Add edges between all machine load/store instructions.
 388           //
 389           for (unsigned i=0, N=fromInstrMvec.size(); i < N; i++)
 390             {
 391               MachineOpCode fromOpCode = fromInstrMvec[i]->getOpCode();
 392               if (mii.isLoad(fromOpCode) || mii.isStore(fromOpCode))
 393                 {
 394                   SchedGraphNode* fromNode =
 395                     this->getGraphNodeForInstr(fromInstrMvec[i]);
 396                   assert(fromNode && "No node for memory instr?");
 397
 398                   for (unsigned j=0, M=toInstrMvec.size(); j < M; j++)
 399                     {
 400                       MachineOpCode toOpCode = toInstrMvec[j]->getOpCode();
 401                       if (mii.isLoad(toOpCode) || mii.isStore(toOpCode))
 402                         {
 403                           SchedGraphNode* toNode =
 404                             this->getGraphNodeForInstr(toInstrMvec[j]);
 405                           assert(toNode && "No node for memory instr?");
 406
 407                           (void) new SchedGraphEdge(fromNode, toNode,
 408                                                     SchedGraphEdge::MemoryDep,
 409                                                     depOrderType, 1);
 410                         }
 411                     }
 412                 }
 413             }
 414         }
 415     }
 416 }
 417
 418
 419 typedef vector< pair<SchedGraphNode*, unsigned int> > RegRefVec;
 420
 421 // The following needs to be a class, not a typedef, so we can use
 422 // an opaque declaration in SchedGraph.h
 423 class NodeToRegRefMap: public hash_map<int, RegRefVec> {
 424   typedef hash_map<int, RegRefVec>::      iterator iterator;
 425   typedef hash_map<int, RegRefVec>::const_iterator const_iterator;
 426 };
 427
 428
 429 void
 430 SchedGraph::addMachineRegEdges(NodeToRegRefMap& regToRefVecMap,
 431                                const TargetMachine& target)
 432 {
 433   assert(bbVec.size() == 1 && "Only handling a single basic block here");
 434
 435   // This assumes that such hardwired registers are never allocated
 436   // to any LLVM value (since register allocation happens later), i.e.,
 437   // any uses or defs of this register have been made explicit!
 438   // Also assumes that two registers with different numbers are
 439   // not aliased!
 440   //
 441   for (NodeToRegRefMap::iterator I = regToRefVecMap.begin();
 442        I != regToRefVecMap.end(); ++I)
 443     {
 444       int regNum           = (*I).first;
 445       RegRefVec& regRefVec = (*I).second;
 446
 447       // regRefVec is ordered by control flow order in the basic block
 448       int lastDefIdx = -1;
 449       for (unsigned i=0; i < regRefVec.size(); ++i)
 450         {
 451           SchedGraphNode* node = regRefVec[i].first;
 452           bool isDef           = regRefVec[i].second;
 453
 454           if (isDef)
 455             { // Each def gets an output edge from the last def
 456               if (lastDefIdx > 0)
 457                 new SchedGraphEdge(regRefVec[lastDefIdx].first, node, regNum,
 458                                    SchedGraphEdge::OutputDep);
 459
 460               // Also, an anti edge from all uses *since* the last def,
 461               // But don't add edge from an instruction to itself!
 462               for (int u = 1 + lastDefIdx; u < (int) i; u++)
 463                 if (regRefVec[u].first != node)
 464                   new SchedGraphEdge(regRefVec[u].first, node, regNum,
 465                                      SchedGraphEdge::AntiDep);
 466             }
 467           else
 468             { // Each use gets a true edge from the last def
 469               if (lastDefIdx > 0)
 470                 new SchedGraphEdge(regRefVec[lastDefIdx].first, node, regNum);
 471             }
 472         }
 473     }
 474 }
 475
 476
 477 void
 478 SchedGraph::addSSAEdge(SchedGraphNode* node,
 479                        Value* val,
 480                        const TargetMachine& target)
 481 {
 482   if (!val->isInstruction()) 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 }