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