include/llvm/Analysis/DependenceGraph.h

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