lib/CodeGen/InstrSched/SchedGraph.cpp

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