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 BasicBlock*   _bb,
 142                                const MachineInstr* _minstr,
 143                                int   indexInBB,
 144                                const TargetMachine& target)
 145   : nodeId(_nodeId),
 146     bb(_bb),
 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   // Add edges for all operands of the machine instruction.
 607   //
 608   for (unsigned i=0, numOps=minstr.getNumOperands(); i < numOps; i++)
 609     {
 610       // ignore def operands here
 611       if (minstr.operandIsDefined(i))
 612         continue;
 613
 614       const MachineOperand& mop = minstr.getOperand(i);
 615
 616       switch(mop.getOperandType())
 617         {
 618         case MachineOperand::MO_VirtualRegister:
 619         case MachineOperand::MO_CCRegister:
 620           if (const Instruction* srcI =
 621               dyn_cast_or_null<Instruction>(mop.getVRegValue()))
 622             {
 623               ValueToDefVecMap::const_iterator I = valueToDefVecMap.find(srcI);
 624               if (I != valueToDefVecMap.end())
 625                 addSSAEdge(node, (*I).second, mop.getVRegValue(), target);
 626             }
 627           break;
 628
 629         case MachineOperand::MO_MachineRegister:
 630           break;
 631
 632         case MachineOperand::MO_SignExtendedImmed:
 633         case MachineOperand::MO_UnextendedImmed:
 634         case MachineOperand::MO_PCRelativeDisp:
 635           break;        // nothing to do for immediate fields
 636
 637         default:
 638           assert(0 && "Unknown machine operand type in SchedGraph builder");
 639           break;
 640         }
 641     }
 642
 643   // Add edges for values implicitly used by the machine instruction.
 644   // Examples include function arguments to a Call instructions or the return
 645   // value of a Ret instruction.
 646   //
 647   for (unsigned i=0, N=minstr.getNumImplicitRefs(); i < N; ++i)
 648     if (! minstr.implicitRefIsDefined(i))
 649       if (const Instruction* srcI =
 650           dyn_cast_or_null<Instruction>(minstr.getImplicitRef(i)))
 651         {
 652           ValueToDefVecMap::const_iterator I = valueToDefVecMap.find(srcI);
 653           if (I != valueToDefVecMap.end())
 654             addSSAEdge(node, (*I).second, minstr.getImplicitRef(i), target);
 655         }
 656 }
 657
 658
 659 void
 660 SchedGraph::addNonSSAEdgesForValue(const Instruction* instr,
 661                                    const TargetMachine& target)
 662 {
 663   if (isa<PHINode>(instr))
 664     return;
 665
 666   MachineCodeForVMInstr& mvec = instr->getMachineInstrVec();
 667   const MachineInstrInfo& mii = target.getInstrInfo();
 668   RefVec refVec;
 669
 670   for (unsigned i=0, N=mvec.size(); i < N; i++)
 671     for (int o=0, N = mii.getNumOperands(mvec[i]->getOpCode()); o < N; o++)
 672       {
 673         const MachineOperand& mop = mvec[i]->getOperand(o);
 674
 675         if ((mop.getOperandType() == MachineOperand::MO_VirtualRegister ||
 676              mop.getOperandType() == MachineOperand::MO_CCRegister)
 677             && mop.getVRegValue() == (Value*) instr)
 678           {
 679             // this operand is a definition or use of value `instr'
 680             SchedGraphNode* node = this->getGraphNodeForInstr(mvec[i]);
 681             assert(node && "No node for machine instruction in this BB?");
 682             refVec.push_back(make_pair(node, o));
 683           }
 684       }
 685
 686   // refVec is ordered by control flow order of the machine instructions
 687   for (unsigned i=0; i < refVec.size(); ++i)
 688     {
 689       SchedGraphNode* node = refVec[i].first;
 690       unsigned int   opNum = refVec[i].second;
 691       bool isDef = node->getMachineInstr()->operandIsDefined(opNum);
 692
 693       if (isDef)
 694         // add output and/or anti deps to this definition
 695         for (unsigned p=0; p < i; ++p)
 696           {
 697             SchedGraphNode* prevNode = refVec[p].first;
 698             if (prevNode != node)
 699               {
 700                 bool prevIsDef = prevNode->getMachineInstr()->
 701                   operandIsDefined(refVec[p].second);
 702                 new SchedGraphEdge(prevNode, node, SchedGraphEdge::DefUseDep,
 703                                    (prevIsDef)? SchedGraphEdge::OutputDep
 704                                               : SchedGraphEdge::AntiDep);
 705               }
 706           }
 707     }
 708 }
 709
 710
 711 void
 712 SchedGraph::findDefUseInfoAtInstr(const TargetMachine& target,
 713                                   SchedGraphNode* node,
 714                                   vector<SchedGraphNode*>& memNodeVec,
 715                                   RegToRefVecMap& regToRefVecMap,
 716                                   ValueToDefVecMap& valueToDefVecMap)
 717 {
 718   const MachineInstrInfo& mii = target.getInstrInfo();
 719
 720
 721   MachineOpCode opCode = node->getOpCode();
 722   if (mii.isLoad(opCode) || mii.isStore(opCode) || mii.isCall(opCode))
 723     memNodeVec.push_back(node);
 724
 725   // Collect the register references and value defs. for explicit operands
 726   //
 727   const MachineInstr& minstr = * node->getMachineInstr();
 728   for (int i=0, numOps = (int) minstr.getNumOperands(); i < numOps; i++)
 729     {
 730       const MachineOperand& mop = minstr.getOperand(i);
 731
 732       // if this references a register other than the hardwired
 733       // "zero" register, record the reference.
 734       if (mop.getOperandType() == MachineOperand::MO_MachineRegister)
 735         {
 736           int regNum = mop.getMachineRegNum();
 737           if (regNum != target.getRegInfo().getZeroRegNum())
 738             regToRefVecMap[mop.getMachineRegNum()].push_back(make_pair(node,
 739                                                                        i));
 740           continue;                     // nothing more to do
 741         }
 742
 743       // ignore all other non-def operands
 744       if (! minstr.operandIsDefined(i))
 745         continue;
 746
 747       // We must be defining a value.
 748       assert((mop.getOperandType() == MachineOperand::MO_VirtualRegister ||
 749               mop.getOperandType() == MachineOperand::MO_CCRegister)
 750              && "Do not expect any other kind of operand to be defined!");
 751
 752       const Instruction* defInstr = cast<Instruction>(mop.getVRegValue());
 753       valueToDefVecMap[defInstr].push_back(make_pair(node, i));
 754     }
 755
 756   //
 757   // Collect value defs. for implicit operands.  The interface to extract
 758   // them assumes they must be virtual registers!
 759   //
 760   for (int i=0, N = (int) minstr.getNumImplicitRefs(); i < N; ++i)
 761     if (minstr.implicitRefIsDefined(i))
 762       if (const Instruction* defInstr =
 763           dyn_cast_or_null<Instruction>(minstr.getImplicitRef(i)))
 764         {
 765           valueToDefVecMap[defInstr].push_back(make_pair(node, -i));
 766         }
 767 }
 768
 769
 770 void
 771 SchedGraph::buildNodesforBB(const TargetMachine& target,
 772                             const BasicBlock* bb,
 773                             vector<SchedGraphNode*>& memNodeVec,
 774                             RegToRefVecMap& regToRefVecMap,
 775                             ValueToDefVecMap& valueToDefVecMap)
 776 {
 777   const MachineInstrInfo& mii = target.getInstrInfo();
 778
 779   // Build graph nodes for each VM instruction and gather def/use info.
 780   // Do both those together in a single pass over all machine instructions.
 781   const MachineCodeForBasicBlock& mvec = bb->getMachineInstrVec();
 782   for (unsigned i=0; i < mvec.size(); i++)
 783     if (! mii.isDummyPhiInstr(mvec[i]->getOpCode()))
 784       {
 785         SchedGraphNode* node = new SchedGraphNode(getNumNodes(), bb,
 786                                                   mvec[i], i, target);
 787         this->noteGraphNodeForInstr(mvec[i], node);
 788
 789         // Remember all register references and value defs
 790         findDefUseInfoAtInstr(target, node,
 791                               memNodeVec, regToRefVecMap,valueToDefVecMap);
 792       }
 793
 794 #undef REALLY_NEED_TO_SEARCH_SUCCESSOR_PHIS
 795 #ifdef REALLY_NEED_TO_SEARCH_SUCCESSOR_PHIS
 796   // This is a BIG UGLY HACK.  IT NEEDS TO BE ELIMINATED.
 797   // Look for copy instructions inserted in this BB due to Phi instructions
 798   // in the successor BBs.
 799   // There MUST be exactly one copy per Phi in successor nodes.
 800   //
 801   for (BasicBlock::succ_const_iterator SI=bb->succ_begin(), SE=bb->succ_end();
 802        SI != SE; ++SI)
 803     for (BasicBlock::const_iterator PI=(*SI)->begin(), PE=(*SI)->end();
 804          PI != PE; ++PI)
 805       {
 806         if ((*PI)->getOpcode() != Instruction::PHINode)
 807           break;                        // No more Phis in this successor
 808
 809         // Find the incoming value from block bb to block (*SI)
 810         int bbIndex = cast<PHINode>(*PI)->getBasicBlockIndex(bb);
 811         assert(bbIndex >= 0 && "But I know bb is a predecessor of (*SI)?");
 812         Value* inVal = cast<PHINode>(*PI)->getIncomingValue(bbIndex);
 813         assert(inVal != NULL && "There must be an in-value on every edge");
 814
 815         // Find the machine instruction that makes a copy of inval to (*PI).
 816         // This must be in the current basic block (bb).
 817         const MachineCodeForVMInstr& mvec = (*PI)->getMachineInstrVec();
 818         const MachineInstr* theCopy = NULL;
 819         for (unsigned i=0; i < mvec.size() && theCopy == NULL; i++)
 820           if (! mii.isDummyPhiInstr(mvec[i]->getOpCode()))
 821             // not a Phi: assume this is a copy and examine its operands
 822             for (int o=0, N=(int) mvec[i]->getNumOperands(); o < N; o++)
 823               {
 824                 const MachineOperand& mop = mvec[i]->getOperand(o);
 825                 if (mvec[i]->operandIsDefined(o))
 826                   assert(mop.getVRegValue() == (*PI) && "dest shd be my Phi");
 827                 else if (mop.getVRegValue() == inVal)
 828                   { // found the copy!
 829                     theCopy = mvec[i];
 830                     break;
 831                   }
 832               }
 833
 834         // Found the dang instruction.  Now create a node and do the rest...
 835         if (theCopy != NULL)
 836           {
 837             SchedGraphNode* node = new SchedGraphNode(getNumNodes(), bb,
 838                                             theCopy, origIndexInBB++, target);
 839             this->noteGraphNodeForInstr(theCopy, node);
 840             findDefUseInfoAtInstr(target, node,
 841                                   memNodeVec, regToRefVecMap,valueToDefVecMap);
 842           }
 843       }
 844 #endif  REALLY_NEED_TO_SEARCH_SUCCESSOR_PHIS
 845 }
 846
 847
 848 void
 849 SchedGraph::buildGraph(const TargetMachine& target)
 850 {
 851   const MachineInstrInfo& mii = target.getInstrInfo();
 852   const BasicBlock* bb = bbVec[0];
 853
 854   assert(bbVec.size() == 1 && "Only handling a single basic block here");
 855
 856   // Use this data structure to note all machine operands that compute
 857   // ordinary LLVM values.  These must be computed defs (i.e., instructions).
 858   // Note that there may be multiple machine instructions that define
 859   // each Value.
 860   ValueToDefVecMap valueToDefVecMap;
 861
 862   // Use this data structure to note all memory instructions.
 863   // We use this to add memory dependence edges without a second full walk.
 864   //
 865   // vector<const Instruction*> memVec;
 866   vector<SchedGraphNode*> memNodeVec;
 867
 868   // Use this data structure to note any uses or definitions of
 869   // machine registers so we can add edges for those later without
 870   // extra passes over the nodes.
 871   // The vector holds an ordered list of references to the machine reg,
 872   // ordered according to control-flow order.  This only works for a
 873   // single basic block, hence the assertion.  Each reference is identified
 874   // by the pair: <node, operand-number>.
 875   //
 876   RegToRefVecMap regToRefVecMap;
 877
 878   // Make a dummy root node.  We'll add edges to the real roots later.
 879   graphRoot = new SchedGraphNode(0, NULL, NULL, -1, target);
 880   graphLeaf = new SchedGraphNode(1, NULL, NULL, -1, target);
 881
 882   //----------------------------------------------------------------
 883   // First add nodes for all the machine instructions in the basic block
 884   // because this greatly simplifies identifying which edges to add.
 885   // Do this one VM instruction at a time since the SchedGraphNode needs that.
 886   // Also, remember the load/store instructions to add memory deps later.
 887   //----------------------------------------------------------------
 888
 889   buildNodesforBB(target, bb, memNodeVec, regToRefVecMap, valueToDefVecMap);
 890
 891   //----------------------------------------------------------------
 892   // Now add edges for the following (all are incoming edges except (4)):
 893   // (1) operands of the machine instruction, including hidden operands
 894   // (2) machine register dependences
 895   // (3) memory load/store dependences
 896   // (3) other resource dependences for the machine instruction, if any
 897   // (4) output dependences when multiple machine instructions define the
 898   //     same value; all must have been generated from a single VM instrn
 899   // (5) control dependences to branch instructions generated for the
 900   //     terminator instruction of the BB. Because of delay slots and
 901   //     2-way conditional branches, multiple CD edges are needed
 902   //     (see addCDEdges for details).
 903   // Also, note any uses or defs of machine registers.
 904   //
 905   //----------------------------------------------------------------
 906
 907   MachineCodeForBasicBlock& bbMvec = bb->getMachineInstrVec();
 908
 909   // First, add edges to the terminator instruction of the basic block.
 910   this->addCDEdges(bb->getTerminator(), target);
 911
 912   // Then add memory dep edges: store->load, load->store, and store->store.
 913   // Call instructions are treated as both load and store.
 914   this->addMemEdges(memNodeVec, target);
 915
 916   // Then add edges between call instructions and CC set/use instructions
 917   this->addCallCCEdges(memNodeVec, bbMvec, target);
 918
 919   // Then add incoming def-use (SSA) edges for each machine instruction.
 920   for (unsigned i=0, N=bbMvec.size(); i < N; i++)
 921     addEdgesForInstruction(*bbMvec[i], valueToDefVecMap, target);
 922
 923   // Then add non-SSA edges for all VM instructions in the block.
 924   // We assume that all machine instructions that define a value are
 925   // generated from the VM instruction corresponding to that value.
 926   // TODO: This could probably be done much more efficiently.
 927   for (BasicBlock::const_iterator II = bb->begin(); II != bb->end(); ++II)
 928     this->addNonSSAEdgesForValue(*II, target);
 929
 930   // Then add edges for dependences on machine registers
 931   this->addMachineRegEdges(regToRefVecMap, target);
 932
 933   // Finally, add edges from the dummy root and to dummy leaf
 934   this->addDummyEdges();
 935 }
 936
 937
 938 //
 939 // class SchedGraphSet
 940 //
 941
 942 /*ctor*/
 943 SchedGraphSet::SchedGraphSet(const Method* _method,
 944                              const TargetMachine& target) :
 945   method(_method)
 946 {
 947   buildGraphsForMethod(method, target);
 948 }
 949
 950
 951 /*dtor*/
 952 SchedGraphSet::~SchedGraphSet()
 953 {
 954   // delete all the graphs
 955   for (iterator I=begin(); I != end(); ++I)
 956     delete (*I).second;
 957 }
 958
 959
 960 void
 961 SchedGraphSet::dump() const
 962 {
 963   cout << "======== Sched graphs for method `"
 964        << (method->hasName()? method->getName() : "???")
 965        << "' ========" << endl << endl;
 966
 967   for (const_iterator I=begin(); I != end(); ++I)
 968     (*I).second->dump();
 969
 970   cout << endl << "====== End graphs for method `"
 971        << (method->hasName()? method->getName() : "")
 972        << "' ========" << endl << endl;
 973 }
 974
 975
 976 void
 977 SchedGraphSet::buildGraphsForMethod(const Method *method,
 978                                     const TargetMachine& target)
 979 {
 980   for (Method::const_iterator BI = method->begin(); BI != method->end(); ++BI)
 981     {
 982       SchedGraph* graph = new SchedGraph(*BI, target);
 983       this->noteGraphForBlock(*BI, graph);
 984     }
 985 }
 986
 987
 988
 989 ostream&
 990 operator<<(ostream& os, const SchedGraphEdge& edge)
 991 {
 992   os << "edge [" << edge.src->getNodeId() << "] -> ["
 993      << edge.sink->getNodeId() << "] : ";
 994
 995   switch(edge.depType) {
 996   case SchedGraphEdge::CtrlDep:         os<< "Control Dep"; break;
 997   case SchedGraphEdge::DefUseDep:       os<< "Reg Value " << edge.val; break;
 998   case SchedGraphEdge::MemoryDep:       os<< "Mem Value " << edge.val; break;
 999   case SchedGraphEdge::MachineRegister: os<< "Reg " <<edge.machineRegNum;break;
1000   case SchedGraphEdge::MachineResource: os<<"Resource "<<edge.resourceId;break;
1001   default: assert(0); break;
1002   }
1003
1004   os << " : delay = " << edge.minDelay << endl;
1005
1006   return os;
1007 }
1008
1009 ostream&
1010 operator<<(ostream& os, const SchedGraphNode& node)
1011 {
1012   printIndent(4, os);
1013   os << "Node " << node.nodeId << " : "
1014      << "latency = " << node.latency << endl;
1015
1016   printIndent(6, os);
1017
1018   if (node.getMachineInstr() == NULL)
1019     os << "(Dummy node)" << endl;
1020   else
1021     {
1022       os << *node.getMachineInstr() << endl;
1023
1024       printIndent(6, os);
1025       os << node.inEdges.size() << " Incoming Edges:" << endl;
1026       for (unsigned i=0, N=node.inEdges.size(); i < N; i++)
1027         {
1028           printIndent(8, os);
1029           os << * node.inEdges[i];
1030         }
1031
1032       printIndent(6, os);
1033       os << node.outEdges.size() << " Outgoing Edges:" << endl;
1034       for (unsigned i=0, N=node.outEdges.size(); i < N; i++)
1035         {
1036           printIndent(8, os);
1037           os << * node.outEdges[i];
1038         }
1039     }
1040
1041   return os;
1042 }