lib/CodeGen/InstrSched/SchedGraph.cpp

   1 // $Id$
   2 //***************************************************************************
   3 // File:
   4 //      SchedGraph.cpp
   5 //
   6 // Purpose:
   7 //      Scheduling graph based on SSA graph plus extra dependence edges
   8 //      capturing dependences due to machine resources (machine registers,
   9 //      CC registers, and any others).
  10 //
  11 // History:
  12 //      7/20/01  -  Vikram Adve  -  Created
  13 //**************************************************************************/
  14
  15 #include "SchedGraph.h"
  16 #include "llvm/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                                DataDepOrderType _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                                DataDepOrderType _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                                DataDepOrderType _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   //
 351   for (int i = (int) termMvec.size()-1; i > (int) first; i--)
 352     {
 353       SchedGraphNode* toNode = this->getGraphNodeForInstr(termMvec[i]);
 354       assert(toNode && "No node for instr generated for branch?");
 355
 356       for (int j = i-1; j >= 0; j--)
 357         if (mii.isBranch(termMvec[j]->getOpCode()))
 358           {
 359             SchedGraphNode* brNode = this->getGraphNodeForInstr(termMvec[j]);
 360             assert(brNode && "No node for instr generated for branch?");
 361             (void) new SchedGraphEdge(brNode, toNode, SchedGraphEdge::CtrlDep,
 362                                       SchedGraphEdge::NonDataDep, 0);
 363             break;                      // only one incoming edge is enough
 364           }
 365     }
 366
 367   // Add CD edges from each instruction preceding the first branch
 368   // to the first branch
 369   //
 370   for (int i = first-1; i >= 0; i--)
 371     {
 372       SchedGraphNode* fromNode = this->getGraphNodeForInstr(termMvec[i]);
 373       assert(fromNode && "No node for instr generated for branch?");
 374       (void) new SchedGraphEdge(fromNode, firstBrNode, SchedGraphEdge::CtrlDep,
 375                                 SchedGraphEdge::NonDataDep, 0);
 376     }
 377
 378   // Now add CD edges to the first branch instruction in the sequence
 379   // from all preceding instructions in the basic block.
 380   //
 381   const BasicBlock* bb = term->getParent();
 382   for (BasicBlock::const_iterator II = bb->begin(); II != bb->end(); ++II)
 383     {
 384       if ((*II) == (const Instruction*) term)   // special case, handled above
 385         continue;
 386
 387       assert(! (*II)->isTerminator() && "Two terminators in basic block?");
 388
 389       const MachineCodeForVMInstr& mvec = (*II)->getMachineInstrVec();
 390       for (unsigned i=0, N=mvec.size(); i < N; i++)
 391         {
 392           SchedGraphNode* fromNode = this->getGraphNodeForInstr(mvec[i]);
 393           if (fromNode == NULL)
 394             continue;                   // dummy instruction, e.g., PHI
 395
 396           (void) new SchedGraphEdge(fromNode, firstBrNode,
 397                                     SchedGraphEdge::CtrlDep,
 398                                     SchedGraphEdge::NonDataDep, 0);
 399
 400           // If we find any other machine instructions (other than due to
 401           // the terminator) that also have delay slots, add an outgoing edge
 402           // from the instruction to the instructions in the delay slots.
 403           //
 404           unsigned d = mii.getNumDelaySlots(mvec[i]->getOpCode());
 405           assert(i+d < N && "Insufficient delay slots for instruction?");
 406
 407           for (unsigned j=1; j <= d; j++)
 408             {
 409               SchedGraphNode* toNode = this->getGraphNodeForInstr(mvec[i+j]);
 410               assert(toNode && "No node for machine instr in delay slot?");
 411               (void) new SchedGraphEdge(fromNode, toNode,
 412                                         SchedGraphEdge::CtrlDep,
 413                                       SchedGraphEdge::NonDataDep, 0);
 414             }
 415         }
 416     }
 417 }
 418
 419
 420 void
 421 SchedGraph::addMemEdges(const vector<const Instruction*>& memVec,
 422                         const TargetMachine& target)
 423 {
 424   const MachineInstrInfo& mii = target.getInstrInfo();
 425
 426   for (unsigned im=0, NM=memVec.size(); im < NM; im++)
 427     {
 428       const Instruction* fromInstr = memVec[im];
 429       bool fromIsLoad = fromInstr->getOpcode() == Instruction::Load;
 430
 431       for (unsigned jm=im+1; jm < NM; jm++)
 432         {
 433           const Instruction* toInstr = memVec[jm];
 434           bool toIsLoad = toInstr->getOpcode() == Instruction::Load;
 435           SchedGraphEdge::DataDepOrderType depOrderType;
 436
 437           if (fromIsLoad)
 438             {
 439               if (toIsLoad) continue;   // both instructions are loads
 440               depOrderType = SchedGraphEdge::AntiDep;
 441             }
 442           else
 443             {
 444               depOrderType = (toIsLoad)? SchedGraphEdge::TrueDep
 445                 : SchedGraphEdge::OutputDep;
 446             }
 447
 448           MachineCodeForVMInstr& fromInstrMvec=fromInstr->getMachineInstrVec();
 449           MachineCodeForVMInstr& toInstrMvec = toInstr->getMachineInstrVec();
 450
 451           // We have two VM memory instructions, and at least one is a store.
 452           // Add edges between all machine load/store instructions.
 453           //
 454           for (unsigned i=0, N=fromInstrMvec.size(); i < N; i++)
 455             {
 456               MachineOpCode fromOpCode = fromInstrMvec[i]->getOpCode();
 457               if (mii.isLoad(fromOpCode) || mii.isStore(fromOpCode))
 458                 {
 459                   SchedGraphNode* fromNode =
 460                     this->getGraphNodeForInstr(fromInstrMvec[i]);
 461                   assert(fromNode && "No node for memory instr?");
 462
 463                   for (unsigned j=0, M=toInstrMvec.size(); j < M; j++)
 464                     {
 465                       MachineOpCode toOpCode = toInstrMvec[j]->getOpCode();
 466                       if (mii.isLoad(toOpCode) || mii.isStore(toOpCode))
 467                         {
 468                           SchedGraphNode* toNode =
 469                             this->getGraphNodeForInstr(toInstrMvec[j]);
 470                           assert(toNode && "No node for memory instr?");
 471
 472                           (void) new SchedGraphEdge(fromNode, toNode,
 473                                                     SchedGraphEdge::MemoryDep,
 474                                                     depOrderType, 1);
 475                         }
 476                     }
 477                 }
 478             }
 479         }
 480     }
 481 }
 482
 483
 484 void
 485 SchedGraph::addMachineRegEdges(RegToRefVecMap& regToRefVecMap,
 486                                const TargetMachine& target)
 487 {
 488   assert(bbVec.size() == 1 && "Only handling a single basic block here");
 489
 490   // This assumes that such hardwired registers are never allocated
 491   // to any LLVM value (since register allocation happens later), i.e.,
 492   // any uses or defs of this register have been made explicit!
 493   // Also assumes that two registers with different numbers are
 494   // not aliased!
 495   //
 496   for (RegToRefVecMap::iterator I = regToRefVecMap.begin();
 497        I != regToRefVecMap.end(); ++I)
 498     {
 499       int regNum        = (*I).first;
 500       RefVec& regRefVec = (*I).second;
 501
 502       // regRefVec is ordered by control flow order in the basic block
 503       for (unsigned i=0; i < regRefVec.size(); ++i)
 504         {
 505           SchedGraphNode* node = regRefVec[i].first;
 506           unsigned int opNum   = regRefVec[i].second;
 507           bool isDef = node->getMachineInstr()->operandIsDefined(opNum);
 508
 509           for (unsigned p=0; p < i; ++p)
 510             {
 511               SchedGraphNode* prevNode = regRefVec[p].first;
 512               if (prevNode != node)
 513                 {
 514                   unsigned int prevOpNum = regRefVec[p].second;
 515                   bool prevIsDef =
 516                     prevNode->getMachineInstr()->operandIsDefined(prevOpNum);
 517
 518                   if (isDef)
 519                     new SchedGraphEdge(prevNode, node, regNum,
 520                                        (prevIsDef)? SchedGraphEdge::OutputDep
 521                                                   : SchedGraphEdge::AntiDep);
 522                   else if (prevIsDef)
 523                     new SchedGraphEdge(prevNode, node, regNum,
 524                                        SchedGraphEdge::TrueDep);
 525                 }
 526             }
 527         }
 528     }
 529 }
 530
 531
 532 inline void
 533 CreateSSAEdge(SchedGraph* graph,
 534               MachineInstr* defInstr,
 535               SchedGraphNode* node,
 536               const Value* val)
 537 {
 538   // this instruction does define value `val'.
 539   // if there is a node for it in the same graph, add an edge.
 540   SchedGraphNode* defNode = graph->getGraphNodeForInstr(defInstr);
 541   if (defNode != NULL && defNode != node)
 542     (void) new SchedGraphEdge(defNode, node, val);
 543 }
 544
 545
 546 void
 547 SchedGraph::addSSAEdge(SchedGraphNode* destNode,
 548                        const Instruction* defVMInstr,
 549                        const Value* defValue,
 550                        const TargetMachine& target)
 551 {
 552   // Phi instructions are the only ones that produce a value but don't get
 553   // any non-dummy machine instructions.  Return here as an optimization.
 554   //
 555   if (isa<PHINode>(defVMInstr))
 556     return;
 557
 558   // Now add the graph edge for the appropriate machine instruction(s).
 559   // Note that multiple machine instructions generated for the
 560   // def VM instruction may modify the register for the def value.
 561   //
 562   MachineCodeForVMInstr& defMvec = defVMInstr->getMachineInstrVec();
 563   const MachineInstrInfo& mii = target.getInstrInfo();
 564
 565   for (unsigned i=0, N=defMvec.size(); i < N; i++)
 566     {
 567       bool edgeAddedForInstr = false;
 568
 569       // First check the explicit operands
 570       for (int o=0, N=mii.getNumOperands(defMvec[i]->getOpCode()); o < N; o++)
 571         {
 572           const MachineOperand& defOp = defMvec[i]->getOperand(o);
 573
 574           if (defOp.opIsDef()
 575               && (defOp.getOperandType() == MachineOperand::MO_VirtualRegister
 576                   || defOp.getOperandType() == MachineOperand::MO_CCRegister)
 577               && (defOp.getVRegValue() == defValue))
 578             {
 579               CreateSSAEdge(this, defMvec[i], destNode, defValue);
 580               edgeAddedForInstr = true;
 581               break;
 582             }
 583         }
 584
 585       // Then check the implicit operands
 586       if (! edgeAddedForInstr)
 587         {
 588           for (unsigned o=0, N=defMvec[i]->getNumImplicitRefs(); o < N; ++o)
 589             if (defMvec[i]->implicitRefIsDefined(o) &&
 590                 defMvec[i]->getImplicitRef(o) == defValue)
 591               {
 592                 CreateSSAEdge(this, defMvec[i], destNode, defValue);
 593                 edgeAddedForInstr = true;
 594                 break;
 595               }
 596         }
 597     }
 598 }
 599
 600
 601 void
 602 SchedGraph::addEdgesForInstruction(const MachineInstr& minstr,
 603                                    RegToRefVecMap& regToRefVecMap,
 604                                    const TargetMachine& target)
 605 {
 606   SchedGraphNode* node = this->getGraphNodeForInstr(&minstr);
 607   if (node == NULL)
 608     return;
 609
 610   assert(node->getInstr() && "Should be no dummy nodes here!");
 611   const Instruction* instr = node->getInstr();
 612
 613   // Add edges for all operands of the machine instruction.
 614   // Also, record all machine register references to add reg. deps. later.
 615   //
 616   for (unsigned i=0, numOps=minstr.getNumOperands(); i < numOps; i++)
 617     {
 618       const MachineOperand& mop = minstr.getOperand(i);
 619
 620       // if this writes to a machine register other than the hardwired
 621       // "zero" register, record the reference.
 622       if (mop.getOperandType() == MachineOperand::MO_MachineRegister
 623           && (mop.getMachineRegNum()
 624               != (unsigned) target.getRegInfo().getZeroRegNum()))
 625         {
 626           regToRefVecMap[mop.getMachineRegNum()].push_back(make_pair(node, i));
 627         }
 628
 629       // ignore all other def operands
 630       if (minstr.operandIsDefined(i))
 631         continue;
 632
 633       switch(mop.getOperandType())
 634         {
 635         case MachineOperand::MO_VirtualRegister:
 636         case MachineOperand::MO_CCRegister:
 637           if (const Instruction* srcI =
 638               dyn_cast_or_null<Instruction>(mop.getVRegValue()))
 639             {
 640               if (srcI->getOpcode() == TMP_INSTRUCTION_OPCODE)
 641                 srcI = instr;
 642               addSSAEdge(node, srcI, mop.getVRegValue(), target);
 643             }
 644           break;
 645
 646         case MachineOperand::MO_MachineRegister:
 647           break;
 648
 649         case MachineOperand::MO_SignExtendedImmed:
 650         case MachineOperand::MO_UnextendedImmed:
 651         case MachineOperand::MO_PCRelativeDisp:
 652           break;        // nothing to do for immediate fields
 653
 654         default:
 655           assert(0 && "Unknown machine operand type in SchedGraph builder");
 656           break;
 657         }
 658     }
 659
 660   // Add edges for values implicitly used by the machine instruction.
 661   // Examples include function arguments to a Call instructions or the return
 662   // value of a Ret instruction.
 663   //
 664   for (unsigned i=0, N=minstr.getNumImplicitRefs(); i < N; ++i)
 665     if (! minstr.implicitRefIsDefined(i))
 666       if (const Instruction* srcI =
 667           dyn_cast_or_null<Instruction>(minstr.getImplicitRef(i)))
 668         {
 669           if (srcI->getOpcode() == TMP_INSTRUCTION_OPCODE)
 670             srcI = instr;
 671           addSSAEdge(node, srcI, minstr.getImplicitRef(i), target);
 672         }
 673 }
 674
 675
 676 void
 677 SchedGraph::addNonSSAEdgesForValue(const Instruction* instr,
 678                                    const TargetMachine& target)
 679 {
 680   if (isa<PHINode>(instr))
 681     return;
 682
 683   MachineCodeForVMInstr& mvec = instr->getMachineInstrVec();
 684   const MachineInstrInfo& mii = target.getInstrInfo();
 685   RefVec refVec;
 686
 687   for (unsigned i=0, N=mvec.size(); i < N; i++)
 688     for (int o=0, N = mii.getNumOperands(mvec[i]->getOpCode()); o < N; o++)
 689       {
 690         const MachineOperand& op = mvec[i]->getOperand(o);
 691
 692         if ((op.getOperandType() == MachineOperand::MO_VirtualRegister ||
 693              op.getOperandType() == MachineOperand::MO_CCRegister)
 694             && op.getVRegValue() == (Value*) instr)
 695           {
 696             // this operand is a definition or use of value `instr'
 697             SchedGraphNode* node = this->getGraphNodeForInstr(mvec[i]);
 698             assert(node && "No node for machine instruction in this BB?");
 699             refVec.push_back(make_pair(node, o));
 700           }
 701       }
 702
 703   // refVec is ordered by control flow order of the machine instructions
 704   for (unsigned i=0; i < refVec.size(); ++i)
 705     {
 706       SchedGraphNode* node = refVec[i].first;
 707       unsigned int   opNum = refVec[i].second;
 708       bool isDef = node->getMachineInstr()->operandIsDefined(opNum);
 709
 710       if (isDef)
 711         // add output and/or anti deps to this definition
 712         for (unsigned p=0; p < i; ++p)
 713           {
 714             SchedGraphNode* prevNode = refVec[p].first;
 715             if (prevNode != node)
 716               {
 717                 bool prevIsDef = prevNode->getMachineInstr()->
 718                   operandIsDefined(refVec[p].second);
 719                 new SchedGraphEdge(prevNode, node, SchedGraphEdge::DefUseDep,
 720                                    (prevIsDef)? SchedGraphEdge::OutputDep
 721                                               : SchedGraphEdge::AntiDep);
 722               }
 723           }
 724     }
 725 }
 726
 727
 728 void
 729 SchedGraph::buildNodesforVMInstr(const TargetMachine& target,
 730                                  const Instruction* instr)
 731 {
 732   const MachineInstrInfo& mii = target.getInstrInfo();
 733   const MachineCodeForVMInstr& mvec = instr->getMachineInstrVec();
 734   for (unsigned i=0; i < mvec.size(); i++)
 735     if (! mii.isDummyPhiInstr(mvec[i]->getOpCode()))
 736       {
 737         SchedGraphNode* node = new SchedGraphNode(getNumNodes(),
 738                                                   instr, mvec[i], target);
 739         this->noteGraphNodeForInstr(mvec[i], node);
 740       }
 741 }
 742
 743
 744 void
 745 SchedGraph::buildGraph(const TargetMachine& target)
 746 {
 747   const MachineInstrInfo& mii = target.getInstrInfo();
 748   const BasicBlock* bb = bbVec[0];
 749
 750   assert(bbVec.size() == 1 && "Only handling a single basic block here");
 751
 752   // Use this data structures to note all LLVM memory instructions.
 753   // We use this to add memory dependence edges without a second full walk.
 754   //
 755   vector<const Instruction*> memVec;
 756
 757   // Use this data structures to note any uses or definitions of
 758   // machine registers so we can add edges for those later without
 759   // extra passes over the nodes.
 760   // The vector holds an ordered list of references to the machine reg,
 761   // ordered according to control-flow order.  This only works for a
 762   // single basic block, hence the assertion.  Each reference is identified
 763   // by the pair: <node, operand-number>.
 764   //
 765   RegToRefVecMap regToRefVecMap;
 766
 767   // Make a dummy root node.  We'll add edges to the real roots later.
 768   graphRoot = new SchedGraphNode(0, NULL, NULL, target);
 769   graphLeaf = new SchedGraphNode(1, NULL, NULL, target);
 770
 771   //----------------------------------------------------------------
 772   // First add nodes for all the machine instructions in the basic block
 773   // because this greatly simplifies identifying which edges to add.
 774   // Do this one VM instruction at a time since the SchedGraphNode needs that.
 775   // Also, remember the load/store instructions to add memory deps later.
 776   //----------------------------------------------------------------
 777
 778   for (BasicBlock::const_iterator II = bb->begin(); II != bb->end(); ++II)
 779     {
 780       const Instruction *instr = *II;
 781
 782       // Build graph nodes for this VM instruction
 783       buildNodesforVMInstr(target, instr);
 784
 785       // Remember the load/store instructions to add memory deps later.
 786       if (instr->getOpcode() == Instruction::Load ||
 787           instr->getOpcode() == Instruction::Store)
 788         memVec.push_back(instr);
 789     }
 790
 791   //----------------------------------------------------------------
 792   // Now add edges for the following (all are incoming edges except (4)):
 793   // (1) operands of the machine instruction, including hidden operands
 794   // (2) machine register dependences
 795   // (3) memory load/store dependences
 796   // (3) other resource dependences for the machine instruction, if any
 797   // (4) output dependences when multiple machine instructions define the
 798   //     same value; all must have been generated from a single VM instrn
 799   // (5) control dependences to branch instructions generated for the
 800   //     terminator instruction of the BB. Because of delay slots and
 801   //     2-way conditional branches, multiple CD edges are needed
 802   //     (see addCDEdges for details).
 803   // Also, note any uses or defs of machine registers.
 804   //
 805   //----------------------------------------------------------------
 806
 807   // First, add edges to the terminator instruction of the basic block.
 808   this->addCDEdges(bb->getTerminator(), target);
 809
 810   // Then add memory dep edges: store->load, load->store, and store->store
 811   this->addMemEdges(memVec, target);
 812
 813   // Then add other edges for all instructions in the block.
 814   // Do this in machine code order and find all references to machine regs.
 815   MachineCodeForBasicBlock& mvec = bb->getMachineInstrVec();
 816   for (unsigned i=0, N=mvec.size(); i < N; i++)
 817     addEdgesForInstruction(*mvec[i], regToRefVecMap, target);
 818
 819   // Since the code is no longer in SSA form, add output dep. edges
 820   // between machine instructions that define the same Value, and anti-dep.
 821   // edges from those to other machine instructions for the same VM instr.
 822   // We assume that all machine instructions that define a value are
 823   // generated from the VM instruction corresponding to that value.
 824   //
 825   for (BasicBlock::const_iterator II = bb->begin(); II != bb->end(); ++II)
 826     {
 827       const Instruction *instr = *II;
 828       this->addNonSSAEdgesForValue(instr, target);
 829     }
 830
 831   // Then add edges for dependences on machine registers
 832   this->addMachineRegEdges(regToRefVecMap, target);
 833
 834   // Finally, add edges from the dummy root and to dummy leaf
 835   this->addDummyEdges();
 836 }
 837
 838
 839 //
 840 // class SchedGraphSet
 841 //
 842
 843 /*ctor*/
 844 SchedGraphSet::SchedGraphSet(const Method* _method,
 845                              const TargetMachine& target) :
 846   method(_method)
 847 {
 848   buildGraphsForMethod(method, target);
 849 }
 850
 851
 852 /*dtor*/
 853 SchedGraphSet::~SchedGraphSet()
 854 {
 855   // delete all the graphs
 856   for (iterator I=begin(); I != end(); ++I)
 857     delete (*I).second;
 858 }
 859
 860
 861 void
 862 SchedGraphSet::dump() const
 863 {
 864   cout << "======== Sched graphs for method `"
 865        << (method->hasName()? method->getName() : "???")
 866        << "' ========" << endl << endl;
 867
 868   for (const_iterator I=begin(); I != end(); ++I)
 869     (*I).second->dump();
 870
 871   cout << endl << "====== End graphs for method `"
 872        << (method->hasName()? method->getName() : "")
 873        << "' ========" << endl << endl;
 874 }
 875
 876
 877 void
 878 SchedGraphSet::buildGraphsForMethod(const Method *method,
 879                                     const TargetMachine& target)
 880 {
 881   for (Method::const_iterator BI = method->begin(); BI != method->end(); ++BI)
 882     {
 883       SchedGraph* graph = new SchedGraph(*BI, target);
 884       this->noteGraphForBlock(*BI, graph);
 885     }
 886 }
 887
 888
 889
 890 ostream&
 891 operator<<(ostream& os, const SchedGraphEdge& edge)
 892 {
 893   os << "edge [" << edge.src->getNodeId() << "] -> ["
 894      << edge.sink->getNodeId() << "] : ";
 895
 896   switch(edge.depType) {
 897   case SchedGraphEdge::CtrlDep:         os<< "Control Dep"; break;
 898   case SchedGraphEdge::DefUseDep:       os<< "Reg Value " << edge.val; break;
 899   case SchedGraphEdge::MemoryDep:       os<< "Mem Value " << edge.val; break;
 900   case SchedGraphEdge::MachineRegister: os<< "Reg " <<edge.machineRegNum;break;
 901   case SchedGraphEdge::MachineResource: os<<"Resource "<<edge.resourceId;break;
 902   default: assert(0); break;
 903   }
 904
 905   os << " : delay = " << edge.minDelay << endl;
 906
 907   return os;
 908 }
 909
 910 ostream&
 911 operator<<(ostream& os, const SchedGraphNode& node)
 912 {
 913   printIndent(4, os);
 914   os << "Node " << node.nodeId << " : "
 915      << "latency = " << node.latency << endl;
 916
 917   printIndent(6, os);
 918
 919   if (node.getMachineInstr() == NULL)
 920     os << "(Dummy node)" << endl;
 921   else
 922     {
 923       os << *node.getMachineInstr() << endl;
 924
 925       printIndent(6, os);
 926       os << node.inEdges.size() << " Incoming Edges:" << endl;
 927       for (unsigned i=0, N=node.inEdges.size(); i < N; i++)
 928         {
 929           printIndent(8, os);
 930           os << * node.inEdges[i];
 931         }
 932
 933       printIndent(6, os);
 934       os << node.outEdges.size() << " Outgoing Edges:" << endl;
 935       for (unsigned i=0, N=node.outEdges.size(); i < N; i++)
 936         {
 937           printIndent(8, os);
 938           os << * node.outEdges[i];
 939         }
 940     }
 941
 942   return os;
 943 }