include/llvm/CodeGen/SchedGraphCommon.h

   1 //===-- SchedGraphCommon.h - Scheduling Base Graph --------------*- C++ -*-===//
   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 // A common graph class that is based on the SSA graph. It includes
  11 // extra dependencies that are caused by machine resources.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef LLVM_CODEGEN_SCHEDGRAPHCOMMON_H
  16 #define LLVM_CODEGEN_SCHEDGRAPHCOMMON_H
  17
  18 #include "llvm/Value.h"
  19 #include "llvm/ADT/iterator"
  20 #include "llvm/Support/Streams.h"
  21 #include <vector>
  22
  23 namespace llvm {
  24
  25 class SchedGraphEdge;
  26 class SchedGraphNode;
  27
  28 /******************** Exported Data Types and Constants ********************/
  29
  30 typedef int ResourceId;
  31 const ResourceId InvalidRID        = -1;
  32 const ResourceId MachineCCRegsRID  = -2; // use +ve numbers for actual regs
  33 const ResourceId MachineIntRegsRID = -3; // use +ve numbers for actual regs
  34 const ResourceId MachineFPRegsRID  = -4; // use +ve numbers for actual regs
  35
  36
  37 //*********************** Public Class Declarations ************************/
  38 class SchedGraphNodeCommon {
  39 protected:
  40   unsigned ID;
  41   std::vector<SchedGraphEdge*> inEdges;
  42   std::vector<SchedGraphEdge*> outEdges;
  43   int latency;
  44   int origIndexInBB;            // original position of instr in BB
  45
  46 public:
  47   typedef std::vector<SchedGraphEdge*>::iterator iterator;
  48   typedef std::vector<SchedGraphEdge*>::const_iterator const_iterator;
  49   typedef std::vector<SchedGraphEdge*>::reverse_iterator reverse_iterator;
  50   typedef std::vector<SchedGraphEdge*>::const_reverse_iterator const_reverse_iterator;
  51
  52   // Accessor methods
  53   unsigned getNodeId() const { return ID; }
  54   int getLatency() const { return latency; }
  55   unsigned getNumInEdges() const { return inEdges.size(); }
  56   unsigned getNumOutEdges() const { return outEdges.size(); }
  57   int getOrigIndexInBB() const { return origIndexInBB; }
  58
  59   // Iterators
  60   iterator beginInEdges() { return inEdges.begin(); }
  61   iterator endInEdges() { return inEdges.end(); }
  62   iterator beginOutEdges() { return outEdges.begin(); }
  63   iterator endOutEdges() { return outEdges.end(); }
  64
  65   const_iterator beginInEdges() const { return inEdges.begin(); }
  66   const_iterator endInEdges() const { return inEdges.end(); }
  67   const_iterator beginOutEdges() const { return outEdges.begin(); }
  68   const_iterator endOutEdges() const { return outEdges.end(); }
  69
  70   void dump(int indent=0) const;
  71
  72   // Debugging support
  73   void print(OStream &os) const {
  74     if (os.stream()) print(*os.stream());
  75   }
  76   virtual void print(std::ostream &os) const = 0;
  77
  78 protected:
  79   friend class SchedGraphCommon;
  80   friend class SchedGraphEdge;   // give access for adding edges
  81
  82
  83   // disable default constructor and provide a ctor for single-block graphs
  84   SchedGraphNodeCommon();  // DO NOT IMPLEMENT
  85
  86   inline SchedGraphNodeCommon(unsigned Id, int index, int late=0) : ID(Id), latency(late), origIndexInBB(index) {}
  87
  88   virtual ~SchedGraphNodeCommon();
  89
  90   //Functions to add and remove edges
  91   inline void addInEdge(SchedGraphEdge* edge) { inEdges.push_back(edge); }
  92   inline void addOutEdge(SchedGraphEdge* edge) { outEdges.push_back(edge); }
  93   void removeInEdge(const SchedGraphEdge* edge);
  94   void removeOutEdge(const SchedGraphEdge* edge);
  95
  96 };
  97
  98 // ostream << operator for SchedGraphNode class
  99 inline OStream &operator<<(OStream &os,
 100                            const SchedGraphNodeCommon &node) {
 101   node.print(os);
 102   return os;
 103 }
 104 inline std::ostream &operator<<(std::ostream &os,
 105                                 const SchedGraphNodeCommon &node) {
 106   node.print(os);
 107   return os;
 108 }
 109
 110 //
 111 // SchedGraphEdge - Edge class to represent dependencies
 112 //
 113 class SchedGraphEdge {
 114 public:
 115   enum SchedGraphEdgeDepType {
 116     CtrlDep, MemoryDep, ValueDep, MachineRegister, MachineResource
 117   };
 118   enum DataDepOrderType {
 119     TrueDep = 0x1, AntiDep=0x2, OutputDep=0x4, NonDataDep=0x8
 120   };
 121
 122 protected:
 123   SchedGraphNodeCommon* src;
 124   SchedGraphNodeCommon* sink;
 125   SchedGraphEdgeDepType depType;
 126   unsigned int depOrderType;
 127   int minDelay; // cached latency (assumes fixed target arch)
 128   int iteDiff;
 129
 130   union {
 131     const Value* val;
 132     int          machineRegNum;
 133     ResourceId   resourceId;
 134   };
 135
 136 public:
 137   // For all constructors, if minDelay is unspecified, minDelay is
 138   // set to _src->getLatency().
 139
 140   // constructor for CtrlDep or MemoryDep edges, selected by 3rd argument
 141   SchedGraphEdge(SchedGraphNodeCommon* _src, SchedGraphNodeCommon* _sink,
 142                  SchedGraphEdgeDepType _depType, unsigned int _depOrderType,
 143                  int _minDelay = -1);
 144
 145   // constructor for explicit value dependence (may be true/anti/output)
 146   SchedGraphEdge(SchedGraphNodeCommon* _src, SchedGraphNodeCommon* _sink,
 147                  const Value* _val, unsigned int _depOrderType,
 148                  int _minDelay = -1);
 149
 150   // constructor for machine register dependence
 151   SchedGraphEdge(SchedGraphNodeCommon* _src,SchedGraphNodeCommon* _sink,
 152                  unsigned int _regNum, unsigned int _depOrderType,
 153                  int _minDelay = -1);
 154
 155   // constructor for any other machine resource dependences.
 156   // DataDepOrderType is always NonDataDep.  It it not an argument to
 157   // avoid overloading ambiguity with previous constructor.
 158   SchedGraphEdge(SchedGraphNodeCommon* _src, SchedGraphNodeCommon* _sink,
 159                  ResourceId _resourceId, int _minDelay = -1);
 160
 161   ~SchedGraphEdge() {}
 162
 163   SchedGraphNodeCommon* getSrc() const { return src; }
 164   SchedGraphNodeCommon* getSink() const { return sink; }
 165   int getMinDelay() const { return minDelay; }
 166   SchedGraphEdgeDepType getDepType() const { return depType; }
 167   unsigned int getDepOrderType() const { return depOrderType; }
 168
 169   const Value* getValue() const {
 170     assert(depType == ValueDep); return val;
 171   }
 172
 173   int getMachineReg() const {
 174     assert(depType == MachineRegister); return machineRegNum;
 175   }
 176
 177   int getResourceId() const {
 178     assert(depType == MachineResource); return resourceId;
 179   }
 180
 181   void setIteDiff(int _iteDiff) {
 182     iteDiff = _iteDiff;
 183   }
 184
 185   int getIteDiff() {
 186     return iteDiff;
 187   }
 188
 189 public:
 190   // Debugging support
 191   void print(OStream &os) const {
 192     if (os.stream()) print(*os.stream());
 193   }
 194   void print(std::ostream &os) const;
 195   void dump(int indent=0) const;
 196
 197 private:
 198   // disable default ctor
 199   SchedGraphEdge(); // DO NOT IMPLEMENT
 200 };
 201
 202 // ostream << operator for SchedGraphNode class
 203 inline OStream &operator<<(OStream &os, const SchedGraphEdge &edge) {
 204   edge.print(os);
 205   return os;
 206 }
 207 inline std::ostream &operator<<(std::ostream &os, const SchedGraphEdge &edge) {
 208   edge.print(os);
 209   return os;
 210 }
 211
 212 class SchedGraphCommon {
 213
 214 protected:
 215   SchedGraphNodeCommon* graphRoot;     // the root and leaf are not inserted
 216   SchedGraphNodeCommon* graphLeaf;     //  in the hash_map (see getNumNodes())
 217
 218 public:
 219   //
 220   // Accessor methods
 221   //
 222   SchedGraphNodeCommon* getRoot() const { return graphRoot; }
 223   SchedGraphNodeCommon* getLeaf() const { return graphLeaf; }
 224
 225   //
 226   // Delete nodes or edges from the graph.
 227   //
 228   void eraseNode(SchedGraphNodeCommon* node);
 229   void eraseIncomingEdges(SchedGraphNodeCommon* node, bool addDummyEdges = true);
 230   void eraseOutgoingEdges(SchedGraphNodeCommon* node, bool addDummyEdges = true);
 231   void eraseIncidentEdges(SchedGraphNodeCommon* node, bool addDummyEdges = true);
 232
 233   SchedGraphCommon() {}
 234   ~SchedGraphCommon();
 235 };
 236
 237
 238 //********************** Sched Graph Iterators *****************************/
 239
 240 // Ok to make it a template because it shd get instantiated at most twice:
 241 // for <SchedGraphNode, SchedGraphNode::iterator> and
 242 // for <const SchedGraphNode, SchedGraphNode::const_iterator>.
 243 //
 244 template <class _NodeType, class _EdgeType, class _EdgeIter>
 245 class SGPredIterator: public bidirectional_iterator<_NodeType, ptrdiff_t> {
 246 protected:
 247   _EdgeIter oi;
 248 public:
 249   typedef SGPredIterator<_NodeType, _EdgeType, _EdgeIter> _Self;
 250
 251   inline SGPredIterator(_EdgeIter startEdge) : oi(startEdge) {}
 252
 253   inline bool operator==(const _Self& x) const { return oi == x.oi; }
 254   inline bool operator!=(const _Self& x) const { return !operator==(x); }
 255
 256   // operator*() differs for pred or succ iterator
 257   inline _NodeType* operator*() const { return (_NodeType*)(*oi)->getSrc(); }
 258   inline _NodeType* operator->() const { return operator*(); }
 259
 260   inline _EdgeType* getEdge() const { return *(oi); }
 261
 262   inline _Self &operator++() { ++oi; return *this; }    // Preincrement
 263   inline _Self operator++(int) {                        // Postincrement
 264     _Self tmp(*this); ++*this; return tmp;
 265   }
 266
 267   inline _Self &operator--() { --oi; return *this; }    // Predecrement
 268   inline _Self operator--(int) {                        // Postdecrement
 269     _Self tmp = *this; --*this; return tmp;
 270   }
 271 };
 272
 273 template <class _NodeType, class _EdgeType, class _EdgeIter>
 274 class SGSuccIterator : public bidirectional_iterator<_NodeType, ptrdiff_t> {
 275 protected:
 276   _EdgeIter oi;
 277 public:
 278   typedef SGSuccIterator<_NodeType, _EdgeType, _EdgeIter> _Self;
 279
 280   inline SGSuccIterator(_EdgeIter startEdge) : oi(startEdge) {}
 281
 282   inline bool operator==(const _Self& x) const { return oi == x.oi; }
 283   inline bool operator!=(const _Self& x) const { return !operator==(x); }
 284
 285   inline _NodeType* operator*() const { return (_NodeType*)(*oi)->getSink(); }
 286   inline _NodeType* operator->() const { return operator*(); }
 287
 288   inline _EdgeType* getEdge() const { return *(oi); }
 289
 290   inline _Self &operator++() { ++oi; return *this; }    // Preincrement
 291   inline _Self operator++(int) {                        // Postincrement
 292     _Self tmp(*this); ++*this; return tmp;
 293   }
 294
 295   inline _Self &operator--() { --oi; return *this; }    // Predecrement
 296   inline _Self operator--(int) {                        // Postdecrement
 297     _Self tmp = *this; --*this; return tmp;
 298   }
 299 };
 300 } // End llvm namespace
 301
 302 #endif