1 //===- SchedGraphCommon.cpp - Scheduling Graphs Base Class- ---------------===//
3 // The LLVM Compiler Infrastructure
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.
8 //===----------------------------------------------------------------------===//
10 // Scheduling graph base class that contains common information for SchedGraph
11 // and ModuloSchedGraph scheduling graphs.
13 //===----------------------------------------------------------------------===//
15 #include "llvm/CodeGen/SchedGraphCommon.h"
16 #include "Support/STLExtras.h"
18 class SchedGraphCommon;
21 // class SchedGraphEdge
23 SchedGraphEdge::SchedGraphEdge(SchedGraphNodeCommon* _src,
24 SchedGraphNodeCommon* _sink,
25 SchedGraphEdgeDepType _depType,
26 unsigned int _depOrderType,
28 : src(_src), sink(_sink), depType(_depType), depOrderType(_depOrderType),
29 minDelay((_minDelay >= 0)? _minDelay : _src->getLatency()), val(NULL) {
32 assert(src != sink && "Self-loop in scheduling graph!");
33 src->addOutEdge(this);
34 sink->addInEdge(this);
37 SchedGraphEdge::SchedGraphEdge(SchedGraphNodeCommon* _src,
38 SchedGraphNodeCommon* _sink,
40 unsigned int _depOrderType,
42 : src(_src), sink(_sink), depType(ValueDep), depOrderType(_depOrderType),
43 minDelay((_minDelay >= 0)? _minDelay : _src->getLatency()), val(_val) {
45 assert(src != sink && "Self-loop in scheduling graph!");
46 src->addOutEdge(this);
47 sink->addInEdge(this);
50 SchedGraphEdge::SchedGraphEdge(SchedGraphNodeCommon* _src,
51 SchedGraphNodeCommon* _sink,
53 unsigned int _depOrderType,
55 : src(_src), sink(_sink), depType(MachineRegister),
56 depOrderType(_depOrderType),
57 minDelay((_minDelay >= 0)? _minDelay : _src->getLatency()),
58 machineRegNum(_regNum) {
60 assert(src != sink && "Self-loop in scheduling graph!");
61 src->addOutEdge(this);
62 sink->addInEdge(this);
65 SchedGraphEdge::SchedGraphEdge(SchedGraphNodeCommon* _src,
66 SchedGraphNodeCommon* _sink,
67 ResourceId _resourceId,
69 : src(_src), sink(_sink), depType(MachineResource), depOrderType(NonDataDep),
70 minDelay((_minDelay >= 0)? _minDelay : _src->getLatency()),
71 resourceId(_resourceId) {
73 assert(src != sink && "Self-loop in scheduling graph!");
74 src->addOutEdge(this);
75 sink->addInEdge(this);
81 void SchedGraphEdge::dump(int indent) const {
82 std::cerr << std::string(indent*2, ' ') << *this;
86 SchedGraphNodeCommon::~SchedGraphNodeCommon()
88 // for each node, delete its out-edges
89 std::for_each(beginOutEdges(), endOutEdges(),
90 deleter<SchedGraphEdge>);
93 void SchedGraphNodeCommon::removeInEdge(const SchedGraphEdge* edge) {
94 assert(edge->getSink() == this);
96 for (iterator I = beginInEdges(); I != endInEdges(); ++I)
103 void SchedGraphNodeCommon::removeOutEdge(const SchedGraphEdge* edge) {
104 assert(edge->getSrc() == this);
106 for (iterator I = beginOutEdges(); I != endOutEdges(); ++I)
113 void SchedGraphNodeCommon::dump(int indent) const {
114 std::cerr << std::string(indent*2, ' ') << *this;
117 //class SchedGraphCommon
119 SchedGraphCommon::~SchedGraphCommon() {
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);
134 if (addDummyEdges && srcNode != getRoot() &&
135 srcNode->beginOutEdges() == srcNode->endOutEdges()) {
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);
145 node->inEdges.clear();
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);
158 sinkNode != getLeaf() &&
159 sinkNode->beginInEdges() == sinkNode->endInEdges()) {
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);
169 node->outEdges.clear();
172 void SchedGraphCommon::eraseIncidentEdges(SchedGraphNodeCommon* node,
173 bool addDummyEdges) {
174 this->eraseIncomingEdges(node, addDummyEdges);
175 this->eraseOutgoingEdges(node, addDummyEdges);