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