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