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