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