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