LLVM API Documentation

SchedGraphCommon.cpp

Go to the documentation of this file.
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