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