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 "llvm/iOther.h"
  25 #include <algorithm>
  26
  27
  28 //*********************** Internal Data Structures *************************/
  29
  30 typedef vector< pair<SchedGraphNode*, unsigned int> > RefVec;
  31
  32 // The following needs to be a class, not a typedef, so we can use
  33 // an opaque declaration in SchedGraph.h
  34 class RegToRefVecMap: public hash_map<int, RefVec> {
  35   typedef hash_map<int, RefVec>::      iterator iterator;
  36   typedef hash_map<int, RefVec>::const_iterator const_iterator;
  37 };
  38
  39 //
  40 // class SchedGraphEdge
  41 //
  42
  43 /*ctor*/
  44 SchedGraphEdge::SchedGraphEdge(SchedGraphNode* _src,
  45                                SchedGraphNode* _sink,
  46                                SchedGraphEdgeDepType _depType,
  47                                DataDepOrderType _depOrderType,
  48                                int _minDelay)
  49   : src(_src),
  50     sink(_sink),
  51     depType(_depType),
  52     depOrderType(_depOrderType),
  53     val(NULL),
  54     minDelay((_minDelay >= 0)? _minDelay : _src->getLatency())
  55 {
  56   src->addOutEdge(this);
  57   sink->addInEdge(this);
  58 }
  59
  60
  61 /*ctor*/
  62 SchedGraphEdge::SchedGraphEdge(SchedGraphNode*  _src,
  63                                SchedGraphNode*  _sink,
  64                                const Value*     _val,
  65                                DataDepOrderType _depOrderType,
  66                                int              _minDelay)
  67   : src(_src),
  68     sink(_sink),
  69     depType(DefUseDep),
  70     depOrderType(_depOrderType),
  71     val(_val),
  72     minDelay((_minDelay >= 0)? _minDelay : _src->getLatency())
  73 {
  74   src->addOutEdge(this);
  75   sink->addInEdge(this);
  76 }
  77
  78
  79 /*ctor*/
  80 SchedGraphEdge::SchedGraphEdge(SchedGraphNode*  _src,
  81                                SchedGraphNode*  _sink,
  82                                unsigned int     _regNum,
  83                                DataDepOrderType _depOrderType,
  84                                int             _minDelay)
  85   : src(_src),
  86     sink(_sink),
  87     depType(MachineRegister),
  88     depOrderType(_depOrderType),
  89     minDelay((_minDelay >= 0)? _minDelay : _src->getLatency()),
  90     machineRegNum(_regNum)
  91 {
  92   src->addOutEdge(this);
  93   sink->addInEdge(this);
  94 }
  95
  96
  97 /*ctor*/
  98 SchedGraphEdge::SchedGraphEdge(SchedGraphNode* _src,
  99                                SchedGraphNode* _sink,
 100                                ResourceId      _resourceId,
 101                                int             _minDelay)
 102   : src(_src),
 103     sink(_sink),
 104     depType(MachineResource),
 105     depOrderType(NonDataDep),
 106     minDelay((_minDelay >= 0)? _minDelay : _src->getLatency()),
 107     resourceId(_resourceId)
 108 {
 109   src->addOutEdge(this);
 110   sink->addInEdge(this);
 111 }
 112
 113 /*dtor*/
 114 SchedGraphEdge::~SchedGraphEdge()
 115 {
 116 }
 117
 118 void SchedGraphEdge::dump(int indent=0) const {
 119   printIndent(indent); cout << *this;
 120 }
 121
 122
 123 //
 124 // class SchedGraphNode
 125 //
 126
 127 /*ctor*/
 128 SchedGraphNode::SchedGraphNode(unsigned int _nodeId,
 129                                const Instruction* _instr,
 130                                const MachineInstr* _minstr,
 131                                const TargetMachine& target)
 132   : nodeId(_nodeId),
 133     instr(_instr),
 134     minstr(_minstr),
 135     latency(0)
 136 {
 137   if (minstr)
 138     {
 139       MachineOpCode mopCode = minstr->getOpCode();
 140       latency = target.getInstrInfo().hasResultInterlock(mopCode)
 141         ? target.getInstrInfo().minLatency(mopCode)
 142         : target.getInstrInfo().maxLatency(mopCode);
 143     }
 144 }
 145
 146
 147 /*dtor*/
 148 SchedGraphNode::~SchedGraphNode()
 149 {
 150 }
 151
 152 void SchedGraphNode::dump(int indent=0) const {
 153   printIndent(indent); cout << *this;
 154 }
 155
 156
 157 inline void
 158 SchedGraphNode::addInEdge(SchedGraphEdge* edge)
 159 {
 160   inEdges.push_back(edge);
 161 }
 162
 163
 164 inline void
 165 SchedGraphNode::addOutEdge(SchedGraphEdge* edge)
 166 {
 167   outEdges.push_back(edge);
 168 }
 169
 170 inline void
 171 SchedGraphNode::removeInEdge(const SchedGraphEdge* edge)
 172 {
 173   assert(edge->getSink() == this);
 174
 175   for (iterator I = beginInEdges(); I != endInEdges(); ++I)
 176     if ((*I) == edge)
 177       {
 178         inEdges.erase(I);
 179         break;
 180       }
 181 }
 182
 183 inline void
 184 SchedGraphNode::removeOutEdge(const SchedGraphEdge* edge)
 185 {
 186   assert(edge->getSrc() == this);
 187
 188   for (iterator I = beginOutEdges(); I != endOutEdges(); ++I)
 189     if ((*I) == edge)
 190       {
 191         outEdges.erase(I);
 192         break;
 193       }
 194 }
 195
 196
 197 //
 198 // class SchedGraph
 199 //
 200
 201
 202 /*ctor*/
 203 SchedGraph::SchedGraph(const BasicBlock* bb,
 204                        const TargetMachine& target)
 205 {
 206   bbVec.push_back(bb);
 207   this->buildGraph(target);
 208 }
 209
 210
 211 /*dtor*/
 212 SchedGraph::~SchedGraph()
 213 {
 214   for (iterator I=begin(); I != end(); ++I)
 215     {
 216       SchedGraphNode* node = (*I).second;
 217
 218       // for each node, delete its out-edges
 219       for (SchedGraphNode::iterator I = node->beginOutEdges();
 220            I != node->endOutEdges(); ++I)
 221         delete *I;
 222
 223       // then delete the node itself.
 224       delete node;
 225     }
 226 }
 227
 228
 229 void
 230 SchedGraph::dump() const
 231 {
 232   cout << "  Sched Graph for Basic Blocks: ";
 233   for (unsigned i=0, N=bbVec.size(); i < N; i++)
 234     {
 235       cout << (bbVec[i]->hasName()? bbVec[i]->getName() : "block")
 236            << " (" << bbVec[i] << ")"
 237            << ((i == N-1)? "" : ", ");
 238     }
 239
 240   cout << endl << endl << "    Actual Root nodes : ";
 241   for (unsigned i=0, N=graphRoot->outEdges.size(); i < N; i++)
 242     cout << graphRoot->outEdges[i]->getSink()->getNodeId()
 243          << ((i == N-1)? "" : ", ");
 244
 245   cout << endl << "    Graph Nodes:" << endl;
 246   for (const_iterator I=begin(); I != end(); ++I)
 247     cout << endl << * (*I).second;
 248
 249   cout << endl;
 250 }
 251
 252
 253 void
 254 SchedGraph::eraseIncomingEdges(SchedGraphNode* node, bool addDummyEdges)
 255 {
 256   // Delete and disconnect all in-edges for the node
 257   for (SchedGraphNode::iterator I = node->beginInEdges();
 258        I != node->endInEdges(); ++I)
 259     {
 260       SchedGraphNode* srcNode = (*I)->getSrc();
 261       srcNode->removeOutEdge(*I);
 262       delete *I;
 263
 264       if (addDummyEdges &&
 265           srcNode != getRoot() &&
 266           srcNode->beginOutEdges() == srcNode->endOutEdges())
 267         { // srcNode has no more out edges, so add an edge to dummy EXIT node
 268           assert(node != getLeaf() && "Adding edge that was just removed?");
 269           (void) new SchedGraphEdge(srcNode, getLeaf(),
 270                     SchedGraphEdge::CtrlDep, SchedGraphEdge::NonDataDep, 0);
 271         }
 272     }
 273
 274   node->inEdges.clear();
 275 }
 276
 277 void
 278 SchedGraph::eraseOutgoingEdges(SchedGraphNode* node, bool addDummyEdges)
 279 {
 280   // Delete and disconnect all out-edges for the node
 281   for (SchedGraphNode::iterator I = node->beginOutEdges();
 282        I != node->endOutEdges(); ++I)
 283     {
 284       SchedGraphNode* sinkNode = (*I)->getSink();
 285       sinkNode->removeInEdge(*I);
 286       delete *I;
 287
 288       if (addDummyEdges &&
 289           sinkNode != getLeaf() &&
 290           sinkNode->beginInEdges() == sinkNode->endInEdges())
 291         { //sinkNode has no more in edges, so add an edge from dummy ENTRY node
 292           assert(node != getRoot() && "Adding edge that was just removed?");
 293           (void) new SchedGraphEdge(getRoot(), sinkNode,
 294                     SchedGraphEdge::CtrlDep, SchedGraphEdge::NonDataDep, 0);
 295         }
 296     }
 297
 298   node->outEdges.clear();
 299 }
 300
 301 void
 302 SchedGraph::eraseIncidentEdges(SchedGraphNode* node, bool addDummyEdges)
 303 {
 304   this->eraseIncomingEdges(node, addDummyEdges);
 305   this->eraseOutgoingEdges(node, addDummyEdges);
 306 }
 307
 308
 309 void
 310 SchedGraph::addDummyEdges()
 311 {
 312   assert(graphRoot->outEdges.size() == 0);
 313
 314   for (const_iterator I=begin(); I != end(); ++I)
 315     {
 316       SchedGraphNode* node = (*I).second;
 317       assert(node != graphRoot && node != graphLeaf);
 318       if (node->beginInEdges() == node->endInEdges())
 319         (void) new SchedGraphEdge(graphRoot, node, SchedGraphEdge::CtrlDep,
 320                                   SchedGraphEdge::NonDataDep, 0);
 321       if (node->beginOutEdges() == node->endOutEdges())
 322         (void) new SchedGraphEdge(node, graphLeaf, SchedGraphEdge::CtrlDep,
 323                                   SchedGraphEdge::NonDataDep, 0);
 324     }
 325 }
 326
 327
 328 void
 329 SchedGraph::addCDEdges(const TerminatorInst* term,
 330                        const TargetMachine& target)
 331 {
 332   const MachineInstrInfo& mii = target.getInstrInfo();
 333   MachineCodeForVMInstr& termMvec = term->getMachineInstrVec();
 334
 335   // Find the first branch instr in the sequence of machine instrs for term
 336   //
 337   unsigned first = 0;
 338   while (! mii.isBranch(termMvec[first]->getOpCode()))
 339     ++first;
 340   assert(first < termMvec.size() &&
 341          "No branch instructions for BR?  Ok, but weird!  Delete assertion.");
 342   if (first == termMvec.size())
 343     return;
 344
 345   SchedGraphNode* firstBrNode = this->getGraphNodeForInstr(termMvec[first]);
 346
 347   // Add CD edges from each instruction in the sequence to the
 348   // *last preceding* branch instr. in the sequence
 349   //
 350   for (int i = (int) termMvec.size()-1; i > (int) first; i--)
 351     {
 352       SchedGraphNode* toNode = this->getGraphNodeForInstr(termMvec[i]);
 353       assert(toNode && "No node for instr generated for branch?");
 354
 355       for (int j = i-1; j >= 0; j--)
 356         if (mii.isBranch(termMvec[j]->getOpCode()))
 357           {
 358             SchedGraphNode* brNode = this->getGraphNodeForInstr(termMvec[j]);
 359             assert(brNode && "No node for instr generated for branch?");
 360             (void) new SchedGraphEdge(brNode, toNode, SchedGraphEdge::CtrlDep,
 361                                       SchedGraphEdge::NonDataDep, 0);
 362             break;                      // only one incoming edge is enough
 363           }
 364     }
 365
 366   // Add CD edges from each instruction preceding the first branch
 367   // to the first branch
 368   //
 369   for (int i = first-1; i >= 0; i--)
 370     {
 371       SchedGraphNode* fromNode = this->getGraphNodeForInstr(termMvec[i]);
 372       assert(fromNode && "No node for instr generated for branch?");
 373       (void) new SchedGraphEdge(fromNode, firstBrNode, SchedGraphEdge::CtrlDep,
 374                                 SchedGraphEdge::NonDataDep, 0);
 375     }
 376
 377   // Now add CD edges to the first branch instruction in the sequence
 378   // from all preceding instructions in the basic block.
 379   //
 380   const BasicBlock* bb = term->getParent();
 381   for (BasicBlock::const_iterator II = bb->begin(); II != bb->end(); ++II)
 382     {
 383       if ((*II) == (const Instruction*) term)   // special case, handled above
 384         continue;
 385
 386       assert(! (*II)->isTerminator() && "Two terminators in basic block?");
 387
 388       const MachineCodeForVMInstr& mvec = (*II)->getMachineInstrVec();
 389       for (unsigned i=0, N=mvec.size(); i < N; i++)
 390         {
 391           SchedGraphNode* fromNode = this->getGraphNodeForInstr(mvec[i]);
 392           if (fromNode == NULL)
 393             continue;                   // dummy instruction, e.g., PHI
 394
 395           (void) new SchedGraphEdge(fromNode, firstBrNode,
 396                                     SchedGraphEdge::CtrlDep,
 397                                     SchedGraphEdge::NonDataDep, 0);
 398
 399           // If we find any other machine instructions (other than due to
 400           // the terminator) that also have delay slots, add an outgoing edge
 401           // from the instruction to the instructions in the delay slots.
 402           //
 403           unsigned d = mii.getNumDelaySlots(mvec[i]->getOpCode());
 404           assert(i+d < N && "Insufficient delay slots for instruction?");
 405
 406           for (unsigned j=1; j <= d; j++)
 407             {
 408               SchedGraphNode* toNode = this->getGraphNodeForInstr(mvec[i+j]);
 409               assert(toNode && "No node for machine instr in delay slot?");
 410               (void) new SchedGraphEdge(fromNode, toNode,
 411                                         SchedGraphEdge::CtrlDep,
 412                                       SchedGraphEdge::NonDataDep, 0);
 413             }
 414         }
 415     }
 416 }
 417
 418
 419 void
 420 SchedGraph::addMemEdges(const vector<const Instruction*>& memVec,
 421                         const TargetMachine& target)
 422 {
 423   const MachineInstrInfo& mii = target.getInstrInfo();
 424
 425   for (unsigned im=0, NM=memVec.size(); im < NM; im++)
 426     {
 427       const Instruction* fromInstr = memVec[im];
 428       bool fromIsLoad = fromInstr->getOpcode() == Instruction::Load;
 429
 430       for (unsigned jm=im+1; jm < NM; jm++)
 431         {
 432           const Instruction* toInstr = memVec[jm];
 433           bool toIsLoad = toInstr->getOpcode() == Instruction::Load;
 434           SchedGraphEdge::DataDepOrderType depOrderType;
 435
 436           if (fromIsLoad)
 437             {
 438               if (toIsLoad) continue;   // both instructions are loads
 439               depOrderType = SchedGraphEdge::AntiDep;
 440             }
 441           else
 442             {
 443               depOrderType = (toIsLoad)? SchedGraphEdge::TrueDep
 444                 : SchedGraphEdge::OutputDep;
 445             }
 446
 447           MachineCodeForVMInstr& fromInstrMvec=fromInstr->getMachineInstrVec();
 448           MachineCodeForVMInstr& toInstrMvec = toInstr->getMachineInstrVec();
 449
 450           // We have two VM memory instructions, and at least one is a store.
 451           // Add edges between all machine load/store instructions.
 452           //
 453           for (unsigned i=0, N=fromInstrMvec.size(); i < N; i++)
 454             {
 455               MachineOpCode fromOpCode = fromInstrMvec[i]->getOpCode();
 456               if (mii.isLoad(fromOpCode) || mii.isStore(fromOpCode))
 457                 {
 458                   SchedGraphNode* fromNode =
 459                     this->getGraphNodeForInstr(fromInstrMvec[i]);
 460                   assert(fromNode && "No node for memory instr?");
 461
 462                   for (unsigned j=0, M=toInstrMvec.size(); j < M; j++)
 463                     {
 464                       MachineOpCode toOpCode = toInstrMvec[j]->getOpCode();
 465                       if (mii.isLoad(toOpCode) || mii.isStore(toOpCode))
 466                         {
 467                           SchedGraphNode* toNode =
 468                             this->getGraphNodeForInstr(toInstrMvec[j]);
 469                           assert(toNode && "No node for memory instr?");
 470
 471                           (void) new SchedGraphEdge(fromNode, toNode,
 472                                                     SchedGraphEdge::MemoryDep,
 473                                                     depOrderType, 1);
 474                         }
 475                     }
 476                 }
 477             }
 478         }
 479     }
 480 }
 481
 482
 483 void
 484 SchedGraph::addMachineRegEdges(RegToRefVecMap& regToRefVecMap,
 485                                const TargetMachine& target)
 486 {
 487   assert(bbVec.size() == 1 && "Only handling a single basic block here");
 488
 489   // This assumes that such hardwired registers are never allocated
 490   // to any LLVM value (since register allocation happens later), i.e.,
 491   // any uses or defs of this register have been made explicit!
 492   // Also assumes that two registers with different numbers are
 493   // not aliased!
 494   //
 495   for (RegToRefVecMap::iterator I = regToRefVecMap.begin();
 496        I != regToRefVecMap.end(); ++I)
 497     {
 498       int regNum        = (*I).first;
 499       RefVec& regRefVec = (*I).second;
 500
 501       // regRefVec is ordered by control flow order in the basic block
 502       for (unsigned i=0; i < regRefVec.size(); ++i)
 503         {
 504           SchedGraphNode* node = regRefVec[i].first;
 505           unsigned int opNum   = regRefVec[i].second;
 506           bool isDef = node->getMachineInstr()->operandIsDefined(opNum);
 507
 508           for (unsigned p=0; p < i; ++p)
 509             {
 510               SchedGraphNode* prevNode = regRefVec[p].first;
 511               if (prevNode != node)
 512                 {
 513                   unsigned int prevOpNum = regRefVec[p].second;
 514                   bool prevIsDef =
 515                     prevNode->getMachineInstr()->operandIsDefined(prevOpNum);
 516
 517                   if (isDef)
 518                     new SchedGraphEdge(prevNode, node, regNum,
 519                                        (prevIsDef)? SchedGraphEdge::OutputDep
 520                                                   : SchedGraphEdge::AntiDep);
 521                   else if (prevIsDef)
 522                     new SchedGraphEdge(prevNode, node, regNum,
 523                                        SchedGraphEdge::TrueDep);
 524                 }
 525             }
 526         }
 527     }
 528 }
 529
 530
 531 void
 532 SchedGraph::addSSAEdge(SchedGraphNode* node,
 533                        const Value* val,
 534                        const TargetMachine& target)
 535 {
 536   if (!isa<Instruction>(val)) return;
 537
 538   const Instruction* thisVMInstr = node->getInstr();
 539   const Instruction* defVMInstr  = cast<const Instruction>(val);
 540
 541   // Phi instructions are the only ones that produce a value but don't get
 542   // any non-dummy machine instructions.  Return here as an optimization.
 543   //
 544   if (isa<PHINode>(defVMInstr))
 545     return;
 546
 547   // Now add the graph edge for the appropriate machine instruction(s).
 548   // Note that multiple machine instructions generated for the
 549   // def VM instruction may modify the register for the def value.
 550   //
 551   MachineCodeForVMInstr& defMvec = defVMInstr->getMachineInstrVec();
 552   const MachineInstrInfo& mii = target.getInstrInfo();
 553
 554   for (unsigned i=0, N=defMvec.size(); i < N; i++)
 555     for (int o=0, N = mii.getNumOperands(defMvec[i]->getOpCode()); o < N; o++)
 556       {
 557         const MachineOperand& defOp = defMvec[i]->getOperand(o);
 558
 559         if (defOp.opIsDef()
 560             && (defOp.getOperandType() == MachineOperand::MO_VirtualRegister
 561                 || defOp.getOperandType() == MachineOperand::MO_CCRegister)
 562             && (defOp.getVRegValue() == val))
 563           {
 564             // this instruction does define value `val'.
 565             // if there is a node for it in the same graph, add an edge.
 566             SchedGraphNode* defNode = this->getGraphNodeForInstr(defMvec[i]);
 567             if (defNode != NULL && defNode != node)
 568               (void) new SchedGraphEdge(defNode, node, val);
 569           }
 570       }
 571 }
 572
 573
 574 void
 575 SchedGraph::addEdgesForInstruction(const MachineInstr& minstr,
 576                                    RegToRefVecMap& regToRefVecMap,
 577                                    const TargetMachine& target)
 578 {
 579   SchedGraphNode* node = this->getGraphNodeForInstr(&minstr);
 580   if (node == NULL)
 581     return;
 582
 583   assert(node->getInstr() && "Should be no dummy nodes here!");
 584   const Instruction& instr = * node->getInstr();
 585
 586   // Add edges for all operands of the machine instruction.
 587   // Also, record all machine register references to add reg. deps. later.
 588   //
 589   for (unsigned i=0, numOps=minstr.getNumOperands(); i < numOps; i++)
 590     {
 591       const MachineOperand& mop = minstr.getOperand(i);
 592
 593       // if this writes to a machine register other than the hardwired
 594       // "zero" register, record the reference.
 595       if (mop.getOperandType() == MachineOperand::MO_MachineRegister
 596           && (mop.getMachineRegNum()
 597               != (unsigned) target.getRegInfo().getZeroRegNum()))
 598         {
 599           regToRefVecMap[mop.getMachineRegNum()].push_back(make_pair(node, i));
 600         }
 601
 602       // ignore all other def operands
 603       if (minstr.operandIsDefined(i))
 604         continue;
 605
 606       switch(mop.getOperandType())
 607         {
 608         case MachineOperand::MO_VirtualRegister:
 609         case MachineOperand::MO_CCRegister:
 610           if (mop.getVRegValue())
 611             addSSAEdge(node, mop.getVRegValue(), target);
 612           break;
 613
 614         case MachineOperand::MO_MachineRegister:
 615           break;
 616
 617         case MachineOperand::MO_SignExtendedImmed:
 618         case MachineOperand::MO_UnextendedImmed:
 619         case MachineOperand::MO_PCRelativeDisp:
 620           break;        // nothing to do for immediate fields
 621
 622         default:
 623           assert(0 && "Unknown machine operand type in SchedGraph builder");
 624           break;
 625         }
 626     }
 627
 628   // Add edges for values implicitly used by the machine instruction sequence
 629   // for the VM instruction but not made explicit operands.  Examples include
 630   // function arguments to a Call instructions or the return value of a Ret
 631   // instruction.  We'll conservatively add the dependences to every machine
 632   // machine instruction in the instruction sequence for this VM instr
 633   // (at least for now, there is never more than one machine instr).
 634   //
 635   const vector<const Value*>& implicitUses =
 636     instr.getMachineInstrVec().getImplicitUses();
 637   for (unsigned i=0; i < implicitUses.size(); ++i)
 638     addSSAEdge(node, implicitUses[i], target);
 639 }
 640
 641
 642 void
 643 SchedGraph::addNonSSAEdgesForValue(const Instruction* instr,
 644                                    const TargetMachine& target)
 645 {
 646   if (isa<PHINode>(instr))
 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 }