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 #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/CodeGen/TargetMachine.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->getValueType() != Value::InstructionVal)
 486     return;
 487
 488   const Instruction* thisVMInstr = node->getInstr();
 489   const Instruction* defVMInstr  = (const Instruction*) val;
 490
 491   // Phi instructions are the only ones that produce a value but don't get
 492   // any non-dummy machine instructions.  Return here as an optimization.
 493   //
 494   if (defVMInstr->isPHINode())
 495     return;
 496
 497   // Now add the graph edge for the appropriate machine instruction(s).
 498   // Note that multiple machine instructions generated for the
 499   // def VM instruction may modify the register for the def value.
 500   //
 501   MachineCodeForVMInstr& defMvec = defVMInstr->getMachineInstrVec();
 502   const MachineInstrInfo& mii = target.getInstrInfo();
 503
 504   for (unsigned i=0, N=defMvec.size(); i < N; i++)
 505     for (int o=0, N = mii.getNumOperands(defMvec[i]->getOpCode()); o < N; o++)
 506       {
 507         const MachineOperand& defOp = defMvec[i]->getOperand(o);
 508
 509         if (defOp.opIsDef()
 510             && (defOp.getOperandType() == MachineOperand::MO_VirtualRegister
 511                 || defOp.getOperandType() == MachineOperand::MO_CCRegister)
 512             && (defOp.getVRegValue() == val))
 513           {
 514             // this instruction does define value `val'.
 515             // if there is a node for it in the same graph, add an edge.
 516             SchedGraphNode* defNode = this->getGraphNodeForInstr(defMvec[i]);
 517             if (defNode != NULL)
 518               (void) new SchedGraphEdge(defNode, node, val);
 519           }
 520       }
 521 }
 522
 523
 524 void
 525 SchedGraph::addEdgesForInstruction(SchedGraphNode* node,
 526                                    NodeToRegRefMap& regToRefVecMap,
 527                                    const TargetMachine& target)
 528 {
 529   const Instruction& instr = * node->getInstr();        // No dummy nodes here!
 530   const MachineInstr& minstr = * node->getMachineInstr();
 531
 532   // Add incoming edges for the following:
 533   // (1) operands of the machine instruction, including hidden operands
 534   // (2) machine register dependences
 535   // (3) other resource dependences for the machine instruction, if any
 536   // Also, note any uses or defs of machine registers.
 537   //
 538   for (unsigned i=0, numOps=minstr.getNumOperands(); i < numOps; i++)
 539     {
 540       const MachineOperand& mop = minstr.getOperand(i);
 541
 542       // if this writes to a machine register other than the hardwired
 543       // "zero" register used on many processors, record the reference.
 544       if (mop.getOperandType() == MachineOperand::MO_MachineRegister
 545           && (! (target.zeroRegNum >= 0
 546                  && mop.getMachineRegNum()==(unsigned) target.zeroRegNum)))
 547         {
 548           regToRefVecMap[mop.getMachineRegNum()].
 549             push_back(make_pair(node, i));
 550         }
 551
 552       // ignore all other def operands
 553       if (minstr.operandIsDefined(i))
 554         continue;
 555
 556       switch(mop.getOperandType())
 557         {
 558         case MachineOperand::MO_VirtualRegister:
 559         case MachineOperand::MO_CCRegister:
 560           if (mop.getVRegValue())
 561             addSSAEdge(node, mop.getVRegValue(), target);
 562           break;
 563
 564         case MachineOperand::MO_MachineRegister:
 565           break;
 566
 567         case MachineOperand::MO_SignExtendedImmed:
 568         case MachineOperand::MO_UnextendedImmed:
 569         case MachineOperand::MO_PCRelativeDisp:
 570           break;        // nothing to do for immediate fields
 571
 572         default:
 573           assert(0 && "Unknown machine operand type in SchedGraph builder");
 574           break;
 575         }
 576     }
 577
 578   // add all true, anti,
 579   // and output dependences for this register.  but ignore
 580
 581 }
 582
 583
 584 void
 585 SchedGraph::buildGraph(const TargetMachine& target)
 586 {
 587   const MachineInstrInfo& mii = target.getInstrInfo();
 588   const BasicBlock* bb = bbVec[0];
 589
 590   assert(bbVec.size() == 1 && "Only handling a single basic block here");
 591
 592   // Use this data structures to note all LLVM memory instructions.
 593   // We use this to add memory dependence edges without a second full walk.
 594   //
 595   vector<const Instruction*> memVec;
 596
 597   // Use this data structures to note any uses or definitions of
 598   // machine registers so we can add edges for those later without
 599   // extra passes over the nodes.
 600   // The vector holds an ordered list of references to the machine reg,
 601   // ordered according to control-flow order.  This only works for a
 602   // single basic block, hence the assertion.  Each reference is identified
 603   // by the pair: <node, operand-number>.
 604   //
 605   NodeToRegRefMap regToRefVecMap;
 606
 607   // Make a dummy root node.  We'll add edges to the real roots later.
 608   graphRoot = new SchedGraphNode(0, NULL, NULL, target);
 609   graphLeaf = new SchedGraphNode(1, NULL, NULL, target);
 610
 611   //----------------------------------------------------------------
 612   // First add nodes for all the machine instructions in the basic block.
 613   // This greatly simplifies identifing which edges to add.
 614   // Also, remember the load/store instructions to add memory deps later.
 615   //----------------------------------------------------------------
 616
 617   for (BasicBlock::const_iterator II = bb->begin(); II != bb->end(); ++II)
 618     {
 619       const Instruction *instr = *II;
 620       const MachineCodeForVMInstr& mvec = instr->getMachineInstrVec();
 621       for (unsigned i=0, N=mvec.size(); i < N; i++)
 622         if (! mii.isDummyPhiInstr(mvec[i]->getOpCode()))
 623           {
 624             SchedGraphNode* node = new SchedGraphNode(getNumNodes(),
 625                                                       instr, mvec[i], target);
 626             this->noteGraphNodeForInstr(mvec[i], node);
 627           }
 628
 629       if (instr->getOpcode() == Instruction::Load ||
 630           instr->getOpcode() == Instruction::Store)
 631         memVec.push_back(instr);
 632     }
 633
 634   //----------------------------------------------------------------
 635   // Now add the edges.
 636   //----------------------------------------------------------------
 637
 638   // First, add edges to the terminator instruction of the basic block.
 639   this->addCDEdges(bb->getTerminator(), target);
 640
 641   // Then add memory dep edges: store->load, load->store, and store->store
 642   this->addMemEdges(memVec, target);
 643
 644   // Then add other edges for all instructions in the block.
 645   for (SchedGraph::iterator GI = this->begin(); GI != this->end(); ++GI)
 646     {
 647       SchedGraphNode* node = (*GI).second;
 648       addEdgesForInstruction(node, regToRefVecMap, target);
 649     }
 650
 651   // Then add edges for dependences on machine registers
 652   this->addMachineRegEdges(regToRefVecMap, target);
 653
 654   // Finally, add edges from the dummy root and to dummy leaf
 655   this->addDummyEdges();
 656 }
 657
 658
 659 //
 660 // class SchedGraphSet
 661 //
 662
 663 /*ctor*/
 664 SchedGraphSet::SchedGraphSet(const Method* _method,
 665                              const TargetMachine& target) :
 666   method(_method)
 667 {
 668   buildGraphsForMethod(method, target);
 669 }
 670
 671
 672 /*dtor*/
 673 SchedGraphSet::~SchedGraphSet()
 674 {
 675   // delete all the graphs
 676   for (iterator I=begin(); I != end(); ++I)
 677     delete (*I).second;
 678 }
 679
 680
 681 void
 682 SchedGraphSet::dump() const
 683 {
 684   cout << "======== Sched graphs for method `"
 685        << (method->hasName()? method->getName() : "???")
 686        << "' ========" << endl << endl;
 687
 688   for (const_iterator I=begin(); I != end(); ++I)
 689     (*I).second->dump();
 690
 691   cout << endl << "====== End graphs for method `"
 692        << (method->hasName()? method->getName() : "")
 693        << "' ========" << endl << endl;
 694 }
 695
 696
 697 void
 698 SchedGraphSet::buildGraphsForMethod(const Method *method,
 699                                     const TargetMachine& target)
 700 {
 701   for (Method::const_iterator BI = method->begin(); BI != method->end(); ++BI)
 702     {
 703       SchedGraph* graph = new SchedGraph(*BI, target);
 704       this->noteGraphForBlock(*BI, graph);
 705     }
 706 }
 707
 708
 709
 710 ostream&
 711 operator<<(ostream& os, const SchedGraphEdge& edge)
 712 {
 713   os << "edge [" << edge.src->getNodeId() << "] -> ["
 714      << edge.sink->getNodeId() << "] : ";
 715
 716   switch(edge.depType) {
 717   case SchedGraphEdge::CtrlDep:         os<< "Control Dep"; break;
 718   case SchedGraphEdge::DefUseDep:       os<< "Reg Value " << edge.val; break;
 719   case SchedGraphEdge::MemoryDep:       os<< "Mem Value " << edge.val; break;
 720   case SchedGraphEdge::MachineRegister: os<< "Reg " <<edge.machineRegNum;break;
 721   case SchedGraphEdge::MachineResource: os<<"Resource "<<edge.resourceId;break;
 722   default: assert(0); break;
 723   }
 724
 725   os << " : delay = " << edge.minDelay << endl;
 726
 727   return os;
 728 }
 729
 730 ostream&
 731 operator<<(ostream& os, const SchedGraphNode& node)
 732 {
 733   printIndent(4, os);
 734   os << "Node " << node.nodeId << " : "
 735      << "latency = " << node.latency << endl;
 736
 737   printIndent(6, os);
 738
 739   if (node.getMachineInstr() == NULL)
 740     os << "(Dummy node)" << endl;
 741   else
 742     {
 743       os << *node.getMachineInstr() << endl;
 744
 745       printIndent(6, os);
 746       os << node.inEdges.size() << " Incoming Edges:" << endl;
 747       for (unsigned i=0, N=node.inEdges.size(); i < N; i++)
 748         {
 749           printIndent(8, os);
 750           os << * node.inEdges[i];
 751         }
 752
 753       printIndent(6, os);
 754       os << node.outEdges.size() << " Outgoing Edges:" << endl;
 755       for (unsigned i=0, N=node.outEdges.size(); i < N; i++)
 756         {
 757           printIndent(8, os);
 758           os << * node.outEdges[i];
 759         }
 760     }
 761
 762   return os;
 763 }