lib/CodeGen/InstrSched/SchedGraphCommon.cpp

   1 //===- SchedGraphCommon.cpp - Scheduling Graphs Base Class- ---------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // Scheduling graph base class that contains common information for SchedGraph
  11 // and ModuloSchedGraph scheduling graphs.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "llvm/CodeGen/SchedGraphCommon.h"
  16 #include "Support/STLExtras.h"
  17
  18 class SchedGraphCommon;
  19
  20 //
  21 // class SchedGraphEdge
  22 //
  23 SchedGraphEdge::SchedGraphEdge(SchedGraphNodeCommon* _src,
  24                                SchedGraphNodeCommon* _sink,
  25                                SchedGraphEdgeDepType _depType,
  26                                unsigned int     _depOrderType,
  27                                int _minDelay)
  28   : src(_src), sink(_sink), depType(_depType), depOrderType(_depOrderType),
  29     minDelay((_minDelay >= 0)? _minDelay : _src->getLatency()), val(NULL) {
  30
  31   iteDiff=0;
  32   assert(src != sink && "Self-loop in scheduling graph!");
  33   src->addOutEdge(this);
  34   sink->addInEdge(this);
  35 }
  36
  37 SchedGraphEdge::SchedGraphEdge(SchedGraphNodeCommon*  _src,
  38                                SchedGraphNodeCommon*  _sink,
  39                                const Value*     _val,
  40                                unsigned int     _depOrderType,
  41                                int              _minDelay)
  42   : src(_src), sink(_sink), depType(ValueDep), depOrderType(_depOrderType),
  43     minDelay((_minDelay >= 0)? _minDelay : _src->getLatency()), val(_val) {
  44   iteDiff=0;
  45   assert(src != sink && "Self-loop in scheduling graph!");
  46   src->addOutEdge(this);
  47   sink->addInEdge(this);
  48 }
  49
  50 SchedGraphEdge::SchedGraphEdge(SchedGraphNodeCommon*  _src,
  51                                SchedGraphNodeCommon*  _sink,
  52                                unsigned int     _regNum,
  53                                unsigned int     _depOrderType,
  54                                int             _minDelay)
  55   : src(_src), sink(_sink), depType(MachineRegister),
  56     depOrderType(_depOrderType),
  57     minDelay((_minDelay >= 0)? _minDelay : _src->getLatency()),
  58     machineRegNum(_regNum) {
  59   iteDiff=0;
  60   assert(src != sink && "Self-loop in scheduling graph!");
  61   src->addOutEdge(this);
  62   sink->addInEdge(this);
  63 }
  64
  65 SchedGraphEdge::SchedGraphEdge(SchedGraphNodeCommon* _src,
  66                                SchedGraphNodeCommon* _sink,
  67                                ResourceId      _resourceId,
  68                                int             _minDelay)
  69   : src(_src), sink(_sink), depType(MachineResource), depOrderType(NonDataDep),
  70     minDelay((_minDelay >= 0)? _minDelay : _src->getLatency()),
  71     resourceId(_resourceId) {
  72   iteDiff=0;
  73   assert(src != sink && "Self-loop in scheduling graph!");
  74   src->addOutEdge(this);
  75   sink->addInEdge(this);
  76 }
  77
  78
  79
  80
  81 void SchedGraphEdge::dump(int indent) const {
  82   std::cerr << std::string(indent*2, ' ') << *this;
  83 }
  84
  85 /*dtor*/
  86 SchedGraphNodeCommon::~SchedGraphNodeCommon()
  87 {
  88   // for each node, delete its out-edges
  89   std::for_each(beginOutEdges(), endOutEdges(),
  90                 deleter<SchedGraphEdge>);
  91 }
  92
  93 void SchedGraphNodeCommon::removeInEdge(const SchedGraphEdge* edge) {
  94   assert(edge->getSink() == this);
  95
  96   for (iterator I = beginInEdges(); I != endInEdges(); ++I)
  97     if ((*I) == edge) {
  98       inEdges.erase(I);
  99       break;
 100     }
 101 }
 102
 103 void SchedGraphNodeCommon::removeOutEdge(const SchedGraphEdge* edge) {
 104   assert(edge->getSrc() == this);
 105
 106   for (iterator I = beginOutEdges(); I != endOutEdges(); ++I)
 107     if ((*I) == edge) {
 108       outEdges.erase(I);
 109       break;
 110     }
 111 }
 112
 113 void SchedGraphNodeCommon::dump(int indent) const {
 114   std::cerr << std::string(indent*2, ' ') << *this;
 115 }
 116
 117 //class SchedGraphCommon
 118
 119 SchedGraphCommon::~SchedGraphCommon() {
 120   delete graphRoot;
 121   delete graphLeaf;
 122 }
 123
 124
 125 void SchedGraphCommon::eraseIncomingEdges(SchedGraphNodeCommon* node,
 126                                           bool addDummyEdges) {
 127   // Delete and disconnect all in-edges for the node
 128   for (SchedGraphNodeCommon::iterator I = node->beginInEdges();
 129        I != node->endInEdges(); ++I) {
 130     SchedGraphNodeCommon* srcNode = (*I)->getSrc();
 131     srcNode->removeOutEdge(*I);
 132     delete *I;
 133
 134     if (addDummyEdges && srcNode != getRoot() &&
 135         srcNode->beginOutEdges() == srcNode->endOutEdges()) {
 136
 137       // srcNode has no more out edges, so add an edge to dummy EXIT node
 138       assert(node != getLeaf() && "Adding edge that was just removed?");
 139       (void) new SchedGraphEdge(srcNode, getLeaf(),
 140                                 SchedGraphEdge::CtrlDep,
 141                                 SchedGraphEdge::NonDataDep, 0);
 142     }
 143   }
 144
 145   node->inEdges.clear();
 146 }
 147
 148 void SchedGraphCommon::eraseOutgoingEdges(SchedGraphNodeCommon* node,
 149                                           bool addDummyEdges) {
 150   // Delete and disconnect all out-edges for the node
 151   for (SchedGraphNodeCommon::iterator I = node->beginOutEdges();
 152        I != node->endOutEdges(); ++I) {
 153     SchedGraphNodeCommon* sinkNode = (*I)->getSink();
 154     sinkNode->removeInEdge(*I);
 155     delete *I;
 156
 157     if (addDummyEdges &&
 158         sinkNode != getLeaf() &&
 159         sinkNode->beginInEdges() == sinkNode->endInEdges()) {
 160
 161       //sinkNode has no more in edges, so add an edge from dummy ENTRY node
 162       assert(node != getRoot() && "Adding edge that was just removed?");
 163       (void) new SchedGraphEdge(getRoot(), sinkNode,
 164                                 SchedGraphEdge::CtrlDep,
 165                                 SchedGraphEdge::NonDataDep, 0);
 166     }
 167   }
 168
 169   node->outEdges.clear();
 170 }
 171
 172 void SchedGraphCommon::eraseIncidentEdges(SchedGraphNodeCommon* node,
 173                                           bool addDummyEdges) {
 174   this->eraseIncomingEdges(node, addDummyEdges);
 175   this->eraseOutgoingEdges(node, addDummyEdges);
 176 }
 177