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