include/llvm/Analysis/PgmDependenceGraph.h

   1 //===- PgmDependenceGraph.h - Enumerate the PDG for a function --*- C++ -*-===//
   2 //
   3 // The Program Dependence Graph (PDG) for a single function represents all
   4 // data and control dependences for the function.  This file provides an
   5 // iterator to enumerate all these dependences.  In particular, it enumerates:
   6 //
   7 // -- Data dependences on memory locations, computed using the
   8 //    MemoryDepAnalysis pass;
   9 // -- Data dependences on SSA registers, directly from Def-Use edges of Values;
  10 // -- Control dependences, computed using postdominance frontiers
  11 //    (NOT YET IMPLEMENTED).
  12 //
  13 // Note that this file does not create an explicit dependence graph --
  14 // it only provides an iterator to traverse the PDG conceptually.
  15 // The MemoryDepAnalysis does build an explicit graph, which is used internally
  16 // here.  That graph could be augmented with the other dependences above if
  17 // desired, but for most uses there will be little need to do that.
  18 //
  19 // Key Classes:
  20 //
  21 // enum PDGIteratorFlags -- Specify which dependences to enumerate.
  22 //
  23 // class PDGIterator     -- The PDG iterator.  This is essentially like a
  24 //                          pointer to class Dependence, but doesn't explicitly
  25 //                          construct a Dependence object for each dependence.
  26 //
  27 // class PgmDependenceGraph -- Interface to obtain PDGIterators for each
  28 //                          instruction.
  29 //
  30 //===----------------------------------------------------------------------===//
  31
  32 #ifndef LLVM_ANALYSIS_PGMDEPENDENCEGRAPH_H
  33 #define LLVM_ANALYSIS_PGMDEPENDENCEGRAPH_H
  34
  35 #include "llvm/Analysis/DependenceGraph.h"
  36 #include "llvm/Analysis/MemoryDepAnalysis.h"
  37 /* #include "llvm/Analysis/PostDominators.h" -- see below */
  38 #include "llvm/Instruction.h"
  39 #include "llvm/Pass.h"
  40 #include <iterator>
  41
  42 class DSGraph;
  43 class DependenceGraph;
  44 class PgmDependenceGraph;
  45
  46
  47 ///---------------------------------------------------------------------------
  48 /// enum PDGIteratorFlags
  49 ///
  50 /// These bit flags specify which dependences incident on a statement are to be
  51 /// enumerated: Memory deps, SSA deps, Control deps, or any combination thereof.
  52 ///---------------------------------------------------------------------------
  53
  54 enum PDGIteratorFlags {
  55   MemoryDeps  = 0x1,                                 // load/store/call deps
  56   SSADeps     = 0x2,                                 // SSA deps (true)
  57   ControlDeps = /* 0x4*/ 0x0,                        // control dependences
  58   AllDataDeps = MemoryDeps | SSADeps,                // shorthand for data deps
  59   AllDeps     = MemoryDeps | SSADeps | ControlDeps   // shorthand for all three
  60 };
  61
  62
  63 ///---------------------------------------------------------------------------
  64 /// struct DepIterState
  65 ///
  66 /// This data type is primarily an internal implementation detail.
  67 /// It are exposed here only to give inlinable access to field dep,
  68 /// which is the representation for the current dependence pointed to by
  69 /// a PgmDependenceGraph::iterator.
  70 ///---------------------------------------------------------------------------
  71
  72 class DepIterState {
  73 private:
  74   typedef char IterStateFlags;
  75   static const IterStateFlags NoFlag, MemDone, SSADone, AllDone, FirstTimeFlag;
  76
  77 public:
  78   DepGraphNode*              depNode;        // the node being enumerated
  79   DependenceGraph::iterator  memDepIter;     // pointer to current memory dep
  80   Instruction::op_iterator   ssaInEdgeIter;  // pointer to current SSA in-dep
  81   Value::use_iterator        ssaOutEdgeIter; // pointer to current SSA out-dep
  82   DependenceGraph*           memDepGraph;    // the core dependence graph
  83   Dependence                 dep;            // the "current" dependence
  84   PDGIteratorFlags           depFlags:8;     // which deps are we enumerating?
  85   IterStateFlags             iterFlags:8;    // marking where the iter stands
  86
  87   /*ctor*/ DepIterState  (DependenceGraph* _memDepGraph,
  88                           Instruction&     I,
  89                           bool             incomingDeps,
  90                           PDGIteratorFlags whichDeps);
  91
  92   bool  operator==(const DepIterState& S) {
  93     assert(memDepGraph == S.memDepGraph &&
  94            "Incompatible iterators! This is a probable sign of something BAD.");
  95     return (iterFlags == S.iterFlags &&
  96             dep == S.dep && depFlags == S.depFlags && depNode == S.depNode &&
  97             memDepIter == S.memDepIter && ssaInEdgeIter == S.ssaInEdgeIter &&
  98             ssaOutEdgeIter == S.ssaOutEdgeIter);
  99   }
 100
 101   // Is the iteration completely done?
 102   //
 103   bool          done            () const { return iterFlags & AllDone; }
 104
 105   // Bump this iterator logically by 1 (to next dependence) and reset the
 106   // dep field to represent the new dependence if there is one.
 107   // Set done = true otherwise.
 108   //
 109   void          Next          ();
 110
 111   // Find the first memory dependence for the current Mem In/Out iterators.
 112   // Sets dep to that dependence and returns true if one is found.
 113   // Returns false and leaves dep unchanged otherwise.
 114   //
 115   bool          SetFirstMemoryDep();
 116
 117   // Find the next valid data dependence for the current SSA In/Out iterators.
 118   // A valid data dependence is one that is to/from an Instruction.
 119   // E.g., an SSA edge from a formal parameter is not a valid dependence.
 120   // Sets dep to that dependence and returns true if a valid one is found.
 121   // Returns false and leaves dep unchanged otherwise.
 122   //
 123   bool          SetFirstSSADep  ();
 124 };
 125
 126
 127 ///---------------------------------------------------------------------------
 128 /// The dependence iterator class.  This class represents a pointer to
 129 /// a single dependence in the program dependence graph.  It is essentially
 130 /// like a pointer to an object of class Dependence but it is much more
 131 /// efficient to retrieve information about the dependence directly rather
 132 /// than constructing the equivalent Dependence object (since that object
 133 /// is normally not constructed for SSA def-use dependences).
 134 ///---------------------------------------------------------------------------
 135
 136 class PDGIterator: public forward_iterator<Dependence, ptrdiff_t>
 137 {
 138   DepIterState* istate;
 139
 140 #if 0
 141   /*copy*/     PDGIterator    (const PDGIterator& I);   // do not implement!
 142   PDGIterator& operator=      (const PDGIterator& I);   // do not implement!
 143
 144   /*copy*/     PDGIterator    (PDGIterator& I) : istate(I.istate) {
 145     I.istate = NULL;                  // ensure this is not deleted twice.
 146   }
 147 #endif
 148
 149   friend class PgmDependenceGraph;
 150
 151 public:
 152   typedef PDGIterator _Self;
 153
 154   /*ctor*/      PDGIterator     (DepIterState* _istate) : istate(_istate) { }
 155   /*dtor*/     ~PDGIterator     ()                        { delete istate; }
 156
 157   /*copy*/      PDGIterator     (const PDGIterator& I)
 158     : istate(new DepIterState(*I.istate)) { }
 159
 160   PDGIterator& operator=        (const PDGIterator& I) {
 161     if (istate) delete istate;
 162     istate = new DepIterState(*I.istate);
 163     return *this;
 164   }
 165
 166   // Check if the iteration is complete
 167   //
 168   bool          fini()       const { return !istate || istate->done(); }
 169
 170   // Retrieve the underlying Dependence.  Returns NULL if fini().
 171   //
 172   Dependence*   operator*()  const { return fini() ?  NULL : &istate->dep; }
 173   Dependence*   operator->() const { assert(!fini()); return &istate->dep; }
 174
 175   // Increment the iterator
 176   //
 177   _Self&        operator++()       { if (!fini()) istate->Next(); return *this;}
 178   _Self&        operator++(int);   // do not implement!
 179
 180   // Equality comparison: a "null" state should compare equal to done
 181   // This is efficient for comparing with "end" or with itself, but could
 182   // be quite inefficient for other cases.
 183   //
 184   bool          operator==(const PDGIterator& I) const {
 185     if (I.istate == NULL)               // most common case: iter == end()
 186       return (istate == NULL || istate->done());
 187     if (istate == NULL)
 188       return (I.istate == NULL || I.istate->done());
 189     return (*istate == *I.istate);
 190   }
 191   bool          operator!=(const PDGIterator& I) const {
 192     return ! (*this == I);
 193   }
 194 };
 195
 196
 197 ///---------------------------------------------------------------------------
 198 /// class PgmDependenceGraph:
 199 ///
 200 /// This pass enumerates dependences incident on each instruction in a function.
 201 /// It can be made a FunctionPass once a Pass (such as Parallelize) is
 202 /// allowed to use a FunctionPass such as this one.
 203 ///---------------------------------------------------------------------------
 204
 205 class PgmDependenceGraph: public Pass {
 206
 207   /// Information about the function being analyzed.
 208   ///
 209   DependenceGraph* memDepGraph;
 210
 211   // print helper function.
 212   void printOutgoingSSADeps(Instruction& I, std::ostream &O);
 213
 214   // MakeIterator --
 215   // The first version creates and initializes an iterator as specified.
 216   // The second version creates a null iterator representing end-of-iteration.
 217   //
 218   PDGIterator   MakeIterator    (Instruction&     I,
 219                                  bool             incomingDeps,
 220                                  PDGIteratorFlags whichDeps);
 221
 222   PDGIterator  MakeIterator     () { return PDGIterator(NULL); }
 223
 224   friend class PDGIterator;
 225   friend class DepIterState;
 226
 227 public:
 228   typedef PDGIterator iterator;
 229   /* typedef PDGIterator<const Dependence> const iterator; */
 230
 231 public:
 232   PgmDependenceGraph() : memDepGraph(NULL) { }
 233   ~PgmDependenceGraph() { }
 234
 235   /// Iterators to enumerate the program dependence graph for a function.
 236   /// Note that this does not provide "end" iterators to check for completion.
 237   /// Instead, just use iterator::fini() or iterator::operator*() == NULL
 238   //
 239   iterator  inDepBegin(Instruction& I, PDGIteratorFlags whichDeps = AllDeps) {
 240     return MakeIterator(I, /*inDeps*/ true, whichDeps);
 241   }
 242   iterator  inDepEnd  (Instruction& I, PDGIteratorFlags whichDeps = AllDeps) {
 243     return MakeIterator();
 244   }
 245   iterator  outDepBegin(Instruction& I, PDGIteratorFlags whichDeps = AllDeps) {
 246     return MakeIterator(I, /*inDeps*/ false, whichDeps);
 247   }
 248   iterator  outDepEnd  (Instruction& I, PDGIteratorFlags whichDeps = AllDeps) {
 249     return MakeIterator();
 250   }
 251
 252   ///------------------------------------------------------------------------
 253   /// TEMPORARY FUNCTIONS TO MAKE THIS A MODULE PASS ---
 254   /// These functions will go away once this class becomes a FunctionPass.
 255
 256   /// Driver function to compute dependence graphs for every function.
 257   ///
 258   bool run(Module& M) { return true; }
 259
 260   /// getGraph() -- Retrieve the pgm dependence graph for a function.
 261   /// This is temporary and will go away once this is a FunctionPass.
 262   /// At that point, this class itself will be the PgmDependenceGraph you want.
 263   ///
 264   PgmDependenceGraph& getGraph(Function& F) {
 265     Visiting(F);
 266     return *this;
 267   }
 268
 269   private:
 270   void Visiting(Function& F) {
 271     memDepGraph = &getAnalysis<MemoryDepAnalysis>().getGraph(F);
 272   }
 273   public:
 274   ///----END TEMPORARY FUNCTIONS---------------------------------------------
 275
 276
 277   /// This initializes the program dependence graph iterator for a function.
 278   ///
 279   bool runOnFunction(Function& func) {
 280     Visiting(func);
 281     return true;
 282   }
 283
 284   /// getAnalysisUsage - This does not modify anything.
 285   /// It uses the Memory Dependence Analysis pass.
 286   /// It needs to use the PostDominanceFrontier pass, but cannot because
 287   /// that is a FunctionPass.  This means control dependence are not emumerated.
 288   ///
 289   void getAnalysisUsage(AnalysisUsage &AU) const {
 290     AU.setPreservesAll();
 291     AU.addRequired<MemoryDepAnalysis>();
 292     /* AU.addRequired<PostDominanceFrontier>(); */
 293   }
 294
 295   /// Debugging support methods
 296   ///
 297   void print(std::ostream &O) const;
 298   void dump() const;
 299 };
 300
 301
 302 //===----------------------------------------------------------------------===//
 303
 304 #endif