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