lib/CodeGen/InstrSched/SchedGraphCommon.cpp

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