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