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