LLVM API Documentation
00001 //===- SchedGraphCommon.cpp - Scheduling Graphs Base Class- ---------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // Scheduling graph base class that contains common information for SchedGraph 00011 // and ModuloSchedGraph scheduling graphs. 00012 // 00013 //===----------------------------------------------------------------------===// 00014 00015 #include "llvm/CodeGen/SchedGraphCommon.h" 00016 #include "llvm/ADT/STLExtras.h" 00017 #include <algorithm> 00018 #include <iostream> 00019 00020 namespace llvm { 00021 00022 class SchedGraphCommon; 00023 00024 // 00025 // class SchedGraphEdge 00026 // 00027 SchedGraphEdge::SchedGraphEdge(SchedGraphNodeCommon* _src, 00028 SchedGraphNodeCommon* _sink, 00029 SchedGraphEdgeDepType _depType, 00030 unsigned int _depOrderType, 00031 int _minDelay) 00032 : src(_src), sink(_sink), depType(_depType), depOrderType(_depOrderType), 00033 minDelay((_minDelay >= 0)? _minDelay : _src->getLatency()), val(NULL) { 00034 00035 iteDiff=0; 00036 assert(src != sink && "Self-loop in scheduling graph!"); 00037 src->addOutEdge(this); 00038 sink->addInEdge(this); 00039 } 00040 00041 SchedGraphEdge::SchedGraphEdge(SchedGraphNodeCommon* _src, 00042 SchedGraphNodeCommon* _sink, 00043 const Value* _val, 00044 unsigned int _depOrderType, 00045 int _minDelay) 00046 : src(_src), sink(_sink), depType(ValueDep), depOrderType(_depOrderType), 00047 minDelay((_minDelay >= 0)? _minDelay : _src->getLatency()), val(_val) { 00048 iteDiff=0; 00049 assert(src != sink && "Self-loop in scheduling graph!"); 00050 src->addOutEdge(this); 00051 sink->addInEdge(this); 00052 } 00053 00054 SchedGraphEdge::SchedGraphEdge(SchedGraphNodeCommon* _src, 00055 SchedGraphNodeCommon* _sink, 00056 unsigned int _regNum, 00057 unsigned int _depOrderType, 00058 int _minDelay) 00059 : src(_src), sink(_sink), depType(MachineRegister), 00060 depOrderType(_depOrderType), 00061 minDelay((_minDelay >= 0)? _minDelay : _src->getLatency()), 00062 machineRegNum(_regNum) { 00063 iteDiff=0; 00064 assert(src != sink && "Self-loop in scheduling graph!"); 00065 src->addOutEdge(this); 00066 sink->addInEdge(this); 00067 } 00068 00069 SchedGraphEdge::SchedGraphEdge(SchedGraphNodeCommon* _src, 00070 SchedGraphNodeCommon* _sink, 00071 ResourceId _resourceId, 00072 int _minDelay) 00073 : src(_src), sink(_sink), depType(MachineResource), depOrderType(NonDataDep), 00074 minDelay((_minDelay >= 0)? _minDelay : _src->getLatency()), 00075 resourceId(_resourceId) { 00076 iteDiff=0; 00077 assert(src != sink && "Self-loop in scheduling graph!"); 00078 src->addOutEdge(this); 00079 sink->addInEdge(this); 00080 } 00081 00082 00083 void SchedGraphEdge::dump(int indent) const { 00084 std::cerr << std::string(indent*2, ' ') << *this; 00085 } 00086 00087 /*dtor*/ 00088 SchedGraphNodeCommon::~SchedGraphNodeCommon() 00089 { 00090 // for each node, delete its out-edges 00091 std::for_each(beginOutEdges(), endOutEdges(), 00092 deleter<SchedGraphEdge>); 00093 } 00094 00095 void SchedGraphNodeCommon::removeInEdge(const SchedGraphEdge* edge) { 00096 assert(edge->getSink() == this); 00097 00098 for (iterator I = beginInEdges(); I != endInEdges(); ++I) 00099 if ((*I) == edge) { 00100 inEdges.erase(I); 00101 break; 00102 } 00103 } 00104 00105 void SchedGraphNodeCommon::removeOutEdge(const SchedGraphEdge* edge) { 00106 assert(edge->getSrc() == this); 00107 00108 for (iterator I = beginOutEdges(); I != endOutEdges(); ++I) 00109 if ((*I) == edge) { 00110 outEdges.erase(I); 00111 break; 00112 } 00113 } 00114 00115 void SchedGraphNodeCommon::dump(int indent) const { 00116 std::cerr << std::string(indent*2, ' ') << *this; 00117 } 00118 00119 //class SchedGraphCommon 00120 00121 SchedGraphCommon::~SchedGraphCommon() { 00122 delete graphRoot; 00123 delete graphLeaf; 00124 } 00125 00126 00127 void SchedGraphCommon::eraseIncomingEdges(SchedGraphNodeCommon* node, 00128 bool addDummyEdges) { 00129 // Delete and disconnect all in-edges for the node 00130 for (SchedGraphNodeCommon::iterator I = node->beginInEdges(); 00131 I != node->endInEdges(); ++I) { 00132 SchedGraphNodeCommon* srcNode = (*I)->getSrc(); 00133 srcNode->removeOutEdge(*I); 00134 delete *I; 00135 00136 if (addDummyEdges && srcNode != getRoot() && 00137 srcNode->beginOutEdges() == srcNode->endOutEdges()) { 00138 00139 // srcNode has no more out edges, so add an edge to dummy EXIT node 00140 assert(node != getLeaf() && "Adding edge that was just removed?"); 00141 (void) new SchedGraphEdge(srcNode, getLeaf(), 00142 SchedGraphEdge::CtrlDep, 00143 SchedGraphEdge::NonDataDep, 0); 00144 } 00145 } 00146 00147 node->inEdges.clear(); 00148 } 00149 00150 void SchedGraphCommon::eraseOutgoingEdges(SchedGraphNodeCommon* node, 00151 bool addDummyEdges) { 00152 // Delete and disconnect all out-edges for the node 00153 for (SchedGraphNodeCommon::iterator I = node->beginOutEdges(); 00154 I != node->endOutEdges(); ++I) { 00155 SchedGraphNodeCommon* sinkNode = (*I)->getSink(); 00156 sinkNode->removeInEdge(*I); 00157 delete *I; 00158 00159 if (addDummyEdges && 00160 sinkNode != getLeaf() && 00161 sinkNode->beginInEdges() == sinkNode->endInEdges()) { 00162 00163 //sinkNode has no more in edges, so add an edge from dummy ENTRY node 00164 assert(node != getRoot() && "Adding edge that was just removed?"); 00165 (void) new SchedGraphEdge(getRoot(), sinkNode, 00166 SchedGraphEdge::CtrlDep, 00167 SchedGraphEdge::NonDataDep, 0); 00168 } 00169 } 00170 00171 node->outEdges.clear(); 00172 } 00173 00174 void SchedGraphCommon::eraseIncidentEdges(SchedGraphNodeCommon* node, 00175 bool addDummyEdges) { 00176 this->eraseIncomingEdges(node, addDummyEdges); 00177 this->eraseOutgoingEdges(node, addDummyEdges); 00178 } 00179 00180 } // End llvm namespace