lib/Target/SparcV9/InstrSched/SchedGraph.cpp

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