include/llvm/Analysis/DependenceGraph.h

   1 //===- DependenceGraph.h - Dependence graph for a function ------*- C++ -*-===//
   2 //
   3 // This file provides an explicit representation for the dependence graph
   4 // of a function, with one node per instruction and one edge per dependence.
   5 // Dependences include both data and control dependences.
   6 //
   7 // Each dep. graph node (class DepGraphNode) keeps lists of incoming and
   8 // outgoing dependence edges.
   9 //
  10 // Each dep. graph edge (class Dependence) keeps a pointer to one end-point
  11 // of the dependence.  This saves space and is important because dep. graphs
  12 // can grow quickly.  It works just fine because the standard idiom is to
  13 // start with a known node and enumerate the dependences to or from that node.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17
  18 #ifndef LLVM_ANALYSIS_DEPENDENCEGRAPH_H
  19 #define LLVM_ANALYSIS_DEPENDENCEGRAPH_H
  20
  21 #include "Support/hash_map"
  22 #include <iosfwd>
  23 #include <vector>
  24 #include <utility>
  25
  26 #include <assert.h>
  27
  28 class Instruction;
  29 class Function;
  30 class Dependence;
  31 class DepGraphNode;
  32 class DependenceGraph;
  33
  34
  35 //----------------------------------------------------------------------------
  36 // enum DependenceType: The standard data dependence types.
  37 //----------------------------------------------------------------------------
  38
  39 enum DependenceType {
  40   NoDependence       = 0x0,
  41   TrueDependence     = 0x1,
  42   AntiDependence     = 0x2,
  43   OutputDependence   = 0x4,
  44   ControlDependence  = 0x8,         // from a terminator to some other instr.
  45   IncomingFlag       = 0x10         // is this an incoming or outgoing dep?
  46 };
  47
  48
  49 //----------------------------------------------------------------------------
  50 // class Dependence:
  51 //
  52 // A representation of a simple (non-loop-related) dependence.
  53 //----------------------------------------------------------------------------
  54
  55 class Dependence {
  56   DepGraphNode*   toOrFromNode;
  57   unsigned char  depType;
  58
  59 public:
  60   Dependence(DepGraphNode* toOrFromN, DependenceType type, bool isIncoming)
  61     : toOrFromNode(toOrFromN),
  62       depType(type | (isIncoming? IncomingFlag : 0x0)) { }
  63
  64   /* copy ctor*/ Dependence     (const Dependence& D)
  65     : toOrFromNode(D.toOrFromNode),
  66       depType(D.depType) { }
  67
  68   bool operator==(const Dependence& D) const {
  69     return toOrFromNode == D.toOrFromNode && depType == D.depType;
  70   }
  71
  72   /// Get information about the type of dependence.
  73   ///
  74   unsigned getDepType() const {
  75     return depType;
  76   }
  77
  78   /// Get source or sink depending on what type of node this is!
  79   ///
  80   DepGraphNode*  getSrc() {
  81     assert(depType & IncomingFlag); return toOrFromNode;
  82   }
  83   const DepGraphNode*  getSrc() const {
  84     assert(depType & IncomingFlag); return toOrFromNode;
  85   }
  86
  87   DepGraphNode*  getSink() {
  88     assert(! (depType & IncomingFlag)); return toOrFromNode;
  89   }
  90   const DepGraphNode*  getSink() const {
  91     assert(! (depType & IncomingFlag)); return toOrFromNode;
  92   }
  93
  94   /// Debugging support methods
  95   ///
  96   void print(std::ostream &O) const;
  97
  98   // Default constructor: Do not use directly except for graph builder code
  99   //
 100   /*ctor*/ Dependence() : toOrFromNode(NULL), depType(NoDependence) { }
 101 };
 102
 103
 104 #ifdef SUPPORTING_LOOP_DEPENDENCES
 105 struct LoopDependence: public Dependence {
 106   DependenceDirection dir;
 107   int                 distance;
 108   short               level;
 109   LoopInfo*           enclosingLoop;
 110 };
 111 #endif
 112
 113
 114 //----------------------------------------------------------------------------
 115 // class DepGraphNode:
 116 //
 117 // A representation of a single node in a dependence graph, corresponding
 118 // to a single instruction.
 119 //----------------------------------------------------------------------------
 120
 121 class DepGraphNode {
 122   Instruction*  instr;
 123   std::vector<Dependence>  inDeps;
 124   std::vector<Dependence>  outDeps;
 125   friend class DependenceGraph;
 126
 127   typedef std::vector<Dependence>::      iterator       iterator;
 128   typedef std::vector<Dependence>::const_iterator const_iterator;
 129
 130         iterator           inDepBegin()         { return inDeps.begin(); }
 131   const_iterator           inDepBegin()   const { return inDeps.begin(); }
 132         iterator           inDepEnd()           { return inDeps.end(); }
 133   const_iterator           inDepEnd()     const { return inDeps.end(); }
 134
 135         iterator           outDepBegin()        { return outDeps.begin(); }
 136   const_iterator           outDepBegin()  const { return outDeps.begin(); }
 137         iterator           outDepEnd()          { return outDeps.end(); }
 138   const_iterator           outDepEnd()    const { return outDeps.end(); }
 139
 140 public:
 141
 142   DepGraphNode(Instruction& I) : instr(&I) { }
 143
 144         Instruction&       getInstr()           { return *instr; }
 145   const Instruction&       getInstr()     const { return *instr; }
 146
 147   /// Debugging support methods
 148   ///
 149   void print(std::ostream &O) const;
 150 };
 151
 152
 153 //----------------------------------------------------------------------------
 154 // class DependenceGraph:
 155 //
 156 // A representation of a dependence graph for a procedure.
 157 // The primary query operation here is to look up a DepGraphNode for
 158 // a particular instruction, and then use the in/out dependence iterators
 159 // for the node.
 160 //----------------------------------------------------------------------------
 161
 162 class DependenceGraph {
 163   DependenceGraph(const DependenceGraph&); // DO NOT IMPLEMENT
 164   void operator=(const DependenceGraph&);  // DO NOT IMPLEMENT
 165
 166   typedef hash_map<Instruction*, DepGraphNode*> DepNodeMapType;
 167   typedef DepNodeMapType::      iterator       map_iterator;
 168   typedef DepNodeMapType::const_iterator const_map_iterator;
 169
 170   DepNodeMapType depNodeMap;
 171
 172   inline DepGraphNode* getNodeInternal(Instruction& inst,
 173                                        bool  createIfMissing = false) {
 174     map_iterator I = depNodeMap.find(&inst);
 175     if (I == depNodeMap.end())
 176       return (!createIfMissing)? NULL :
 177         depNodeMap.insert(
 178             std::make_pair(&inst, new DepGraphNode(inst))).first->second;
 179     else
 180       return I->second;
 181   }
 182
 183 public:
 184   typedef std::vector<Dependence>::      iterator       iterator;
 185   typedef std::vector<Dependence>::const_iterator const_iterator;
 186
 187 public:
 188   DependenceGraph() { }
 189   ~DependenceGraph();
 190
 191   /// Get the graph node for an instruction.  There will be one if and
 192   /// only if there are any dependences incident on this instruction.
 193   /// If there is none, these methods will return NULL.
 194   ///
 195   DepGraphNode* getNode(Instruction& inst, bool createIfMissing = false) {
 196     return getNodeInternal(inst, createIfMissing);
 197   }
 198   const DepGraphNode* getNode(const Instruction& inst) const {
 199     return const_cast<DependenceGraph*>(this)
 200       ->getNodeInternal(const_cast<Instruction&>(inst));
 201   }
 202
 203   iterator inDepBegin(DepGraphNode& T) {
 204     return T.inDeps.begin();
 205   }
 206   const_iterator inDepBegin (const DepGraphNode& T) const {
 207     return T.inDeps.begin();
 208   }
 209
 210   iterator inDepEnd(DepGraphNode& T) {
 211     return T.inDeps.end();
 212   }
 213   const_iterator inDepEnd(const DepGraphNode& T) const {
 214     return T.inDeps.end();
 215   }
 216
 217   iterator outDepBegin(DepGraphNode& F) {
 218     return F.outDeps.begin();
 219   }
 220   const_iterator outDepBegin(const DepGraphNode& F) const {
 221     return F.outDeps.begin();
 222   }
 223
 224   iterator outDepEnd(DepGraphNode& F) {
 225     return F.outDeps.end();
 226   }
 227   const_iterator outDepEnd(const DepGraphNode& F) const {
 228     return F.outDeps.end();
 229   }
 230
 231   /// Debugging support methods
 232   ///
 233   void print(const Function& func, std::ostream &O) const;
 234
 235 public:
 236   /// Functions for adding and modifying the dependence graph.
 237   /// These should to be used only by dependence analysis implementations.
 238   void AddSimpleDependence(Instruction& fromI,
 239                            Instruction& toI,
 240                            DependenceType depType) {
 241     DepGraphNode* fromNode = getNodeInternal(fromI, /*create*/ true);
 242     DepGraphNode* toNode   = getNodeInternal(toI,   /*create*/ true);
 243     fromNode->outDeps.push_back(Dependence(toNode, depType, false));
 244     toNode->  inDeps. push_back(Dependence(fromNode, depType, true));
 245   }
 246
 247 #ifdef SUPPORTING_LOOP_DEPENDENCES
 248   /// This interface is a placeholder to show what information is needed.
 249   /// It will probably change when it starts being used.
 250   void AddLoopDependence(Instruction&  fromI,
 251                          Instruction&  toI,
 252                          DependenceType      depType,
 253                          DependenceDirection dir,
 254                          int                 distance,
 255                          short               level,
 256                          LoopInfo*           enclosingLoop);
 257 #endif // SUPPORTING_LOOP_DEPENDENCES
 258 };
 259
 260 //===----------------------------------------------------------------------===//
 261
 262 #endif