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