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