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   virtual void print(std::ostream &os) const = 0;
  74   void print(std::ostream *os) const { if (os) print(*os); }
  75
  76 protected:
  77   friend class SchedGraphCommon;
  78   friend class SchedGraphEdge;   // give access for adding edges
  79
  80
  81   // disable default constructor and provide a ctor for single-block graphs
  82   SchedGraphNodeCommon();  // DO NOT IMPLEMENT
  83
  84   inline SchedGraphNodeCommon(unsigned Id, int index, int late=0) : 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 // SchedGraphEdge - Edge class to represent dependencies
 105 //
 106 class SchedGraphEdge {
 107 public:
 108   enum SchedGraphEdgeDepType {
 109     CtrlDep, MemoryDep, ValueDep, MachineRegister, MachineResource
 110   };
 111   enum DataDepOrderType {
 112     TrueDep = 0x1, AntiDep=0x2, OutputDep=0x4, NonDataDep=0x8
 113   };
 114
 115 protected:
 116   SchedGraphNodeCommon* src;
 117   SchedGraphNodeCommon* sink;
 118   SchedGraphEdgeDepType depType;
 119   unsigned int depOrderType;
 120   int minDelay; // cached latency (assumes fixed target arch)
 121   int iteDiff;
 122
 123   union {
 124     const Value* val;
 125     int          machineRegNum;
 126     ResourceId   resourceId;
 127   };
 128
 129 public:
 130   // For all constructors, if minDelay is unspecified, minDelay is
 131   // set to _src->getLatency().
 132
 133   // constructor for CtrlDep or MemoryDep edges, selected by 3rd argument
 134   SchedGraphEdge(SchedGraphNodeCommon* _src, SchedGraphNodeCommon* _sink,
 135                  SchedGraphEdgeDepType _depType, unsigned int _depOrderType,
 136                  int _minDelay = -1);
 137
 138   // constructor for explicit value dependence (may be true/anti/output)
 139   SchedGraphEdge(SchedGraphNodeCommon* _src, SchedGraphNodeCommon* _sink,
 140                  const Value* _val, unsigned int _depOrderType,
 141                  int _minDelay = -1);
 142
 143   // constructor for machine register dependence
 144   SchedGraphEdge(SchedGraphNodeCommon* _src,SchedGraphNodeCommon* _sink,
 145                  unsigned int _regNum, unsigned int _depOrderType,
 146                  int _minDelay = -1);
 147
 148   // constructor for any other machine resource dependences.
 149   // DataDepOrderType is always NonDataDep.  It it not an argument to
 150   // avoid overloading ambiguity with previous constructor.
 151   SchedGraphEdge(SchedGraphNodeCommon* _src, SchedGraphNodeCommon* _sink,
 152                  ResourceId _resourceId, int _minDelay = -1);
 153
 154   ~SchedGraphEdge() {}
 155
 156   SchedGraphNodeCommon* getSrc() const { return src; }
 157   SchedGraphNodeCommon* getSink() const { return sink; }
 158   int getMinDelay() const { return minDelay; }
 159   SchedGraphEdgeDepType getDepType() const { return depType; }
 160   unsigned int getDepOrderType() const { return depOrderType; }
 161
 162   const Value* getValue() const {
 163     assert(depType == ValueDep); return val;
 164   }
 165
 166   int getMachineReg() const {
 167     assert(depType == MachineRegister); return machineRegNum;
 168   }
 169
 170   int getResourceId() const {
 171     assert(depType == MachineResource); return resourceId;
 172   }
 173
 174   void setIteDiff(int _iteDiff) {
 175     iteDiff = _iteDiff;
 176   }
 177
 178   int getIteDiff() {
 179     return iteDiff;
 180   }
 181
 182 public:
 183   // Debugging support
 184   void print(std::ostream &os) const;
 185   void print(std::ostream *os) const { if (os) print(*os); }
 186   void dump(int indent=0) const;
 187
 188 private:
 189   // disable default ctor
 190   SchedGraphEdge(); // DO NOT IMPLEMENT
 191 };
 192
 193 // ostream << operator for SchedGraphNode class
 194 inline std::ostream &operator<<(std::ostream &os, const SchedGraphEdge &edge) {
 195   edge.print(os);
 196   return os;
 197 }
 198
 199 class SchedGraphCommon {
 200
 201 protected:
 202   SchedGraphNodeCommon* graphRoot;     // the root and leaf are not inserted
 203   SchedGraphNodeCommon* graphLeaf;     //  in the hash_map (see getNumNodes())
 204
 205 public:
 206   //
 207   // Accessor methods
 208   //
 209   SchedGraphNodeCommon* getRoot() const { return graphRoot; }
 210   SchedGraphNodeCommon* getLeaf() const { return graphLeaf; }
 211
 212   //
 213   // Delete nodes or edges from the graph.
 214   //
 215   void eraseNode(SchedGraphNodeCommon* node);
 216   void eraseIncomingEdges(SchedGraphNodeCommon* node, bool addDummyEdges = true);
 217   void eraseOutgoingEdges(SchedGraphNodeCommon* node, bool addDummyEdges = true);
 218   void eraseIncidentEdges(SchedGraphNodeCommon* node, bool addDummyEdges = true);
 219
 220   SchedGraphCommon() {}
 221   ~SchedGraphCommon();
 222 };
 223
 224
 225 //********************** Sched Graph Iterators *****************************/
 226
 227 // Ok to make it a template because it shd get instantiated at most twice:
 228 // for <SchedGraphNode, SchedGraphNode::iterator> and
 229 // for <const SchedGraphNode, SchedGraphNode::const_iterator>.
 230 //
 231 template <class _NodeType, class _EdgeType, class _EdgeIter>
 232 class SGPredIterator: public bidirectional_iterator<_NodeType, ptrdiff_t> {
 233 protected:
 234   _EdgeIter oi;
 235 public:
 236   typedef SGPredIterator<_NodeType, _EdgeType, _EdgeIter> _Self;
 237
 238   inline SGPredIterator(_EdgeIter startEdge) : oi(startEdge) {}
 239
 240   inline bool operator==(const _Self& x) const { return oi == x.oi; }
 241   inline bool operator!=(const _Self& x) const { return !operator==(x); }
 242
 243   // operator*() differs for pred or succ iterator
 244   inline _NodeType* operator*() const { return (_NodeType*)(*oi)->getSrc(); }
 245   inline _NodeType* operator->() const { return operator*(); }
 246
 247   inline _EdgeType* getEdge() const { return *(oi); }
 248
 249   inline _Self &operator++() { ++oi; return *this; }    // Preincrement
 250   inline _Self operator++(int) {                        // Postincrement
 251     _Self tmp(*this); ++*this; return tmp;
 252   }
 253
 254   inline _Self &operator--() { --oi; return *this; }    // Predecrement
 255   inline _Self operator--(int) {                        // Postdecrement
 256     _Self tmp = *this; --*this; return tmp;
 257   }
 258 };
 259
 260 template <class _NodeType, class _EdgeType, class _EdgeIter>
 261 class SGSuccIterator : public bidirectional_iterator<_NodeType, ptrdiff_t> {
 262 protected:
 263   _EdgeIter oi;
 264 public:
 265   typedef SGSuccIterator<_NodeType, _EdgeType, _EdgeIter> _Self;
 266
 267   inline SGSuccIterator(_EdgeIter startEdge) : oi(startEdge) {}
 268
 269   inline bool operator==(const _Self& x) const { return oi == x.oi; }
 270   inline bool operator!=(const _Self& x) const { return !operator==(x); }
 271
 272   inline _NodeType* operator*() const { return (_NodeType*)(*oi)->getSink(); }
 273   inline _NodeType* operator->() const { return operator*(); }
 274
 275   inline _EdgeType* getEdge() const { return *(oi); }
 276
 277   inline _Self &operator++() { ++oi; return *this; }    // Preincrement
 278   inline _Self operator++(int) {                        // Postincrement
 279     _Self tmp(*this); ++*this; return tmp;
 280   }
 281
 282   inline _Self &operator--() { --oi; return *this; }    // Predecrement
 283   inline _Self operator--(int) {                        // Postdecrement
 284     _Self tmp = *this; --*this; return tmp;
 285   }
 286 };
 287 } // End llvm namespace
 288
 289 #endif