include/llvm/Analysis/PgmDependenceGraph.h

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