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 <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, int late=0) : ID(Id), latency(late), origIndexInBB(index) {}
  83
  84   virtual ~SchedGraphNodeCommon();
  85
  86   //Functions to add and remove edges
  87   inline void addInEdge(SchedGraphEdge* edge) { inEdges.push_back(edge); }
  88   inline void addOutEdge(SchedGraphEdge* edge) { outEdges.push_back(edge); }
  89   void removeInEdge(const SchedGraphEdge* edge);
  90   void removeOutEdge(const SchedGraphEdge* edge);
  91
  92 };
  93
  94 // ostream << operator for SchedGraphNode class
  95 inline std::ostream &operator<<(std::ostream &os,
  96                                 const SchedGraphNodeCommon &node) {
  97   node.print(os);
  98   return os;
  99 }
 100
 101
 102
 103
 104 //
 105 // SchedGraphEdge - Edge class to represent dependencies
 106 //
 107 class SchedGraphEdge {
 108 public:
 109   enum SchedGraphEdgeDepType {
 110     CtrlDep, MemoryDep, ValueDep, MachineRegister, MachineResource
 111   };
 112   enum DataDepOrderType {
 113     TrueDep = 0x1, AntiDep=0x2, OutputDep=0x4, NonDataDep=0x8
 114   };
 115
 116 protected:
 117   SchedGraphNodeCommon* src;
 118   SchedGraphNodeCommon* sink;
 119   SchedGraphEdgeDepType depType;
 120   unsigned int depOrderType;
 121   int minDelay; // cached latency (assumes fixed target arch)
 122   int iteDiff;
 123
 124   union {
 125     const Value* val;
 126     int          machineRegNum;
 127     ResourceId   resourceId;
 128   };
 129
 130 public:
 131   // For all constructors, if minDelay is unspecified, minDelay is
 132   // set to _src->getLatency().
 133
 134   // constructor for CtrlDep or MemoryDep edges, selected by 3rd argument
 135   SchedGraphEdge(SchedGraphNodeCommon* _src, SchedGraphNodeCommon* _sink,
 136                  SchedGraphEdgeDepType _depType, unsigned int _depOrderType,
 137                  int _minDelay = -1);
 138
 139   // constructor for explicit value dependence (may be true/anti/output)
 140   SchedGraphEdge(SchedGraphNodeCommon* _src, SchedGraphNodeCommon* _sink,
 141                  const Value* _val, unsigned int _depOrderType,
 142                  int _minDelay = -1);
 143
 144   // constructor for machine register dependence
 145   SchedGraphEdge(SchedGraphNodeCommon* _src,SchedGraphNodeCommon* _sink,
 146                  unsigned int _regNum, unsigned int _depOrderType,
 147                  int _minDelay = -1);
 148
 149   // constructor for any other machine resource dependences.
 150   // DataDepOrderType is always NonDataDep.  It it not an argument to
 151   // avoid overloading ambiguity with previous constructor.
 152   SchedGraphEdge(SchedGraphNodeCommon* _src, SchedGraphNodeCommon* _sink,
 153                  ResourceId _resourceId, int _minDelay = -1);
 154
 155   ~SchedGraphEdge() {}
 156
 157   SchedGraphNodeCommon* getSrc() const { return src; }
 158   SchedGraphNodeCommon* getSink() const { return sink; }
 159   int getMinDelay() const { return minDelay; }
 160   SchedGraphEdgeDepType getDepType() const { return depType; }
 161   unsigned int getDepOrderType() const { return depOrderType; }
 162
 163   const Value* getValue() const {
 164     assert(depType == ValueDep); return val;
 165   }
 166
 167   int getMachineReg() const {
 168     assert(depType == MachineRegister); return machineRegNum;
 169   }
 170
 171   int getResourceId() const {
 172     assert(depType == MachineResource); return resourceId;
 173   }
 174
 175   void setIteDiff(int _iteDiff) {
 176     iteDiff = _iteDiff;
 177   }
 178
 179   int getIteDiff() {
 180     return iteDiff;
 181   }
 182
 183 public:
 184   // Debugging support
 185   void print(std::ostream &os) const;
 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