lib/CodeGen/InstrSched/SchedGraph.cpp

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