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