include/llvm/CodeGen/SchedGraphCommon.h

   1 //===-- SchedGraphCommon.h - Scheduling Base Graph ---------------*- C++ -*---=//
   2 //
   3 // A common graph class that is based on the SSA graph. It includes
   4 // extra dependencies that are caused by machine resources.
   5 //
   6 //===-------------------------------------------------------------------------=//
   7
   8 #ifndef LLVM_CODEGEN_SCHEDGRAPHCOMMON_H
   9 #define LLVM_CODEGEN_SCHEDGRAPHCOMMON_H
  10
  11 #include "llvm/Value.h"
  12
  13 class SchedGraphEdge;
  14 class SchedGraphNode;
  15
  16 /******************** Exported Data Types and Constants ********************/
  17
  18 typedef int ResourceId;
  19 const ResourceId InvalidRID        = -1;
  20 const ResourceId MachineCCRegsRID  = -2; // use +ve numbers for actual regs
  21 const ResourceId MachineIntRegsRID = -3; // use +ve numbers for actual regs
  22 const ResourceId MachineFPRegsRID  = -4; // use +ve numbers for actual regs
  23
  24
  25 //*********************** Public Class Declarations ************************/
  26 class SchedGraphNodeCommon {
  27 protected:
  28   unsigned ID;
  29   std::vector<SchedGraphEdge*> inEdges;
  30   std::vector<SchedGraphEdge*> outEdges;
  31   int latency;
  32
  33 public:
  34   typedef std::vector<SchedGraphEdge*>::iterator iterator;
  35   typedef std::vector<SchedGraphEdge*>::const_iterator const_iterator;
  36   typedef std::vector<SchedGraphEdge*>::reverse_iterator reverse_iterator;
  37   typedef std::vector<SchedGraphEdge*>::const_reverse_iterator const_reverse_iterator;
  38
  39   // Accessor methods
  40   unsigned getNodeId() const { return ID; }
  41   int getLatency() const { return latency; }
  42   unsigned getNumInEdges() const { return inEdges.size(); }
  43   unsigned getNumOutEdges() const { return outEdges.size(); }
  44
  45
  46   // Iterators
  47   iterator beginInEdges() { return inEdges.begin(); }
  48   iterator endInEdges()  { return inEdges.end(); }
  49   iterator beginOutEdges() { return outEdges.begin(); }
  50   iterator endOutEdges() { return outEdges.end(); }
  51
  52   const_iterator beginInEdges() const { return inEdges.begin(); }
  53   const_iterator endInEdges() const { return inEdges.end(); }
  54   const_iterator beginOutEdges() const { return outEdges.begin(); }
  55   const_iterator endOutEdges() const { return outEdges.end(); }
  56
  57   void dump(int indent=0) const;
  58
  59   // Debugging support
  60   virtual void print(std::ostream &os) const = 0;
  61
  62 protected:
  63   friend class SchedGraph;
  64   friend class SchedGraphCommon;
  65   friend class SchedGraphEdge;          // give access for adding edges
  66
  67
  68   // disable default constructor and provide a ctor for single-block graphs
  69   SchedGraphNodeCommon();       // DO NOT IMPLEMENT
  70
  71   inline SchedGraphNodeCommon(unsigned Id) : ID(Id), latency(0) {}
  72   virtual ~SchedGraphNodeCommon();
  73
  74   //Functions to add and remove edges
  75   inline void addInEdge(SchedGraphEdge* edge) { inEdges.push_back(edge); }
  76   inline void addOutEdge(SchedGraphEdge* edge) { outEdges.push_back(edge); }
  77   void removeInEdge(const SchedGraphEdge* edge);
  78   void removeOutEdge(const SchedGraphEdge* edge);
  79 };
  80
  81 // ostream << operator for SchedGraphNode class
  82 inline std::ostream &operator<<(std::ostream &os,
  83                                 const SchedGraphNodeCommon &node) {
  84   node.print(os);
  85   return os;
  86 }
  87
  88
  89
  90
  91 //
  92 // SchedGraphEdge - Edge class to represent dependencies
  93 //
  94 class SchedGraphEdge {
  95 public:
  96   enum SchedGraphEdgeDepType {
  97     CtrlDep, MemoryDep, ValueDep, MachineRegister, MachineResource
  98   };
  99   enum DataDepOrderType {
 100     TrueDep = 0x1, AntiDep=0x2, OutputDep=0x4, NonDataDep=0x8
 101   };
 102
 103 protected:
 104   SchedGraphNodeCommon* src;
 105   SchedGraphNodeCommon* sink;
 106   SchedGraphEdgeDepType depType;
 107   unsigned int depOrderType;
 108   int minDelay; // cached latency (assumes fixed target arch)
 109   int iteDiff;
 110
 111   union {
 112     const Value* val;
 113     int          machineRegNum;
 114     ResourceId   resourceId;
 115   };
 116
 117 public:
 118   // For all constructors, if minDelay is unspecified, minDelay is
 119   // set to _src->getLatency().
 120
 121   // constructor for CtrlDep or MemoryDep edges, selected by 3rd argument
 122   SchedGraphEdge(SchedGraphNodeCommon* _src, SchedGraphNodeCommon* _sink,
 123                  SchedGraphEdgeDepType _depType, unsigned int _depOrderType,
 124                  int _minDelay = -1);
 125
 126   // constructor for explicit value dependence (may be true/anti/output)
 127   SchedGraphEdge(SchedGraphNodeCommon* _src, SchedGraphNodeCommon* _sink,
 128                  const Value* _val, unsigned int _depOrderType,
 129                  int _minDelay = -1);
 130
 131   // constructor for machine register dependence
 132   SchedGraphEdge(SchedGraphNodeCommon* _src,SchedGraphNodeCommon* _sink,
 133                  unsigned int _regNum, unsigned int _depOrderType,
 134                  int _minDelay = -1);
 135
 136   // constructor for any other machine resource dependences.
 137   // DataDepOrderType is always NonDataDep.  It it not an argument to
 138   // avoid overloading ambiguity with previous constructor.
 139   SchedGraphEdge(SchedGraphNodeCommon* _src, SchedGraphNodeCommon* _sink,
 140                  ResourceId _resourceId, int _minDelay = -1);
 141
 142   ~SchedGraphEdge() {}
 143
 144   SchedGraphNodeCommon* getSrc() const { return src; }
 145   SchedGraphNodeCommon* getSink() const { return sink; }
 146   int getMinDelay() const { return minDelay; }
 147   SchedGraphEdgeDepType getDepType() const { return depType; }
 148
 149   const Value* getValue() const {
 150     assert(depType == ValueDep); return val;
 151   }
 152
 153   int getMachineReg() const {
 154     assert(depType == MachineRegister); return machineRegNum;
 155   }
 156
 157   int getResourceId() const {
 158     assert(depType == MachineResource); return resourceId;
 159   }
 160
 161   void setIteDiff(int _iteDiff) {
 162     iteDiff = _iteDiff;
 163   }
 164
 165   int getIteDiff() {
 166     return iteDiff;
 167   }
 168
 169 public:
 170   // Debugging support
 171   void print(std::ostream &os) const;
 172   void dump(int indent=0) const;
 173
 174 private:
 175   // disable default ctor
 176   SchedGraphEdge();     // DO NOT IMPLEMENT
 177 };
 178
 179 // ostream << operator for SchedGraphNode class
 180 inline std::ostream &operator<<(std::ostream &os, const SchedGraphEdge &edge) {
 181   edge.print(os);
 182   return os;
 183 }
 184
 185 class SchedGraphCommon {
 186
 187 protected:
 188   SchedGraphNodeCommon* graphRoot;     // the root and leaf are not inserted
 189   SchedGraphNodeCommon* graphLeaf;     //  in the hash_map (see getNumNodes())
 190
 191 public:
 192   //
 193   // Accessor methods
 194   //
 195   SchedGraphNodeCommon* getRoot() const { return graphRoot; }
 196   SchedGraphNodeCommon* getLeaf() const { return graphLeaf; }
 197
 198   //
 199   // Delete nodes or edges from the graph.
 200   //
 201   void eraseNode(SchedGraphNodeCommon* node);
 202   void eraseIncomingEdges(SchedGraphNodeCommon* node, bool addDummyEdges = true);
 203   void eraseOutgoingEdges(SchedGraphNodeCommon* node, bool addDummyEdges = true);
 204   void eraseIncidentEdges(SchedGraphNodeCommon* node, bool addDummyEdges = true);
 205
 206   SchedGraphCommon() {}
 207   ~SchedGraphCommon();
 208 };
 209
 210 #endif