LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

PgmDependenceGraph.h

Go to the documentation of this file.
00001 //===- PgmDependenceGraph.h - Enumerate the PDG for a function --*- C++ -*-===//
00002 // 
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 // 
00008 //===----------------------------------------------------------------------===//
00009 // 
00010 // The Program Dependence Graph (PDG) for a single function represents all
00011 // data and control dependences for the function.  This file provides an
00012 // iterator to enumerate all these dependences.  In particular, it enumerates:
00013 // 
00014 // -- Data dependences on memory locations, computed using the
00015 //    MemoryDepAnalysis pass;
00016 // -- Data dependences on SSA registers, directly from Def-Use edges of Values;
00017 // -- Control dependences, computed using postdominance frontiers
00018 //    (NOT YET IMPLEMENTED).
00019 // 
00020 // Note that this file does not create an explicit dependence graph --
00021 // it only provides an iterator to traverse the PDG conceptually.
00022 // The MemoryDepAnalysis does build an explicit graph, which is used internally
00023 // here.  That graph could be augmented with the other dependences above if
00024 // desired, but for most uses there will be little need to do that.
00025 // 
00026 // Key Classes:
00027 // 
00028 // enum PDGIteratorFlags -- Specify which dependences to enumerate.
00029 // 
00030 // class PDGIterator     -- The PDG iterator.  This is essentially like a
00031 //                          pointer to class Dependence, but doesn't explicitly
00032 //                          construct a Dependence object for each dependence.
00033 //
00034 // class PgmDependenceGraph -- Interface to obtain PDGIterators for each
00035 //                          instruction.
00036 //
00037 //===----------------------------------------------------------------------===//
00038 
00039 #ifndef LLVM_ANALYSIS_PGMDEPENDENCEGRAPH_H
00040 #define LLVM_ANALYSIS_PGMDEPENDENCEGRAPH_H
00041 
00042 #include "MemoryDepAnalysis.h"
00043 /* #include "llvm/Analysis/PostDominators.h" -- see below */
00044 #include "llvm/Instruction.h"
00045 #include "llvm/Pass.h"
00046 #include "llvm/ADT/iterator"
00047 
00048 namespace llvm {
00049 
00050 class DSGraph;
00051 class DependenceGraph;
00052 class PgmDependenceGraph;
00053 
00054 //---------------------------------------------------------------------------
00055 /// enum PDGIteratorFlags - specify which dependences incident on a statement
00056 /// are to be enumerated: Memory deps, SSA deps, Control deps, or any
00057 /// combination thereof.
00058 ///
00059 enum PDGIteratorFlags {
00060   MemoryDeps  = 0x1,                                 // load/store/call deps
00061   SSADeps     = 0x2,                                 // SSA deps (true)
00062   ControlDeps = /* 0x4*/ 0x0,                        // control dependences
00063   AllDataDeps = MemoryDeps | SSADeps,                // shorthand for data deps
00064   AllDeps     = MemoryDeps | SSADeps | ControlDeps   // shorthand for all three
00065 };
00066 
00067 //---------------------------------------------------------------------------
00068 /// struct DepIterState - an internal implementation detail.
00069 /// It are exposed here only to give inlinable access to field dep,
00070 /// which is the representation for the current dependence pointed to by
00071 /// a PgmDependenceGraph::iterator.
00072 ///
00073 class DepIterState {
00074 private:
00075   typedef char IterStateFlags;
00076   static const IterStateFlags NoFlag, MemDone, SSADone, AllDone, FirstTimeFlag;
00077 
00078 public:
00079   DepGraphNode*              depNode;        // the node being enumerated
00080   DependenceGraph::iterator  memDepIter;     // pointer to current memory dep
00081   Instruction::op_iterator   ssaInEdgeIter;  // pointer to current SSA in-dep
00082   Value::use_iterator        ssaOutEdgeIter; // pointer to current SSA out-dep
00083   DependenceGraph*           memDepGraph;    // the core dependence graph
00084   Dependence                 dep;            // the "current" dependence
00085   PDGIteratorFlags           depFlags:8;     // which deps are we enumerating?
00086   IterStateFlags             iterFlags:8;    // marking where the iter stands
00087 
00088   DepIterState(DependenceGraph* _memDepGraph,
00089                Instruction&     I, 
00090                bool             incomingDeps,
00091                PDGIteratorFlags whichDeps);
00092 
00093   bool operator==(const DepIterState& S) {
00094     assert(memDepGraph == S.memDepGraph &&
00095            "Incompatible iterators! This is a probable sign of something BAD.");
00096     return (iterFlags == S.iterFlags &&
00097             dep == S.dep && depFlags == S.depFlags && depNode == S.depNode &&
00098             memDepIter == S.memDepIter && ssaInEdgeIter == S.ssaInEdgeIter &&
00099             ssaOutEdgeIter == S.ssaOutEdgeIter);
00100   }
00101 
00102   // Is the iteration completely done?
00103   // 
00104   bool done() const { return iterFlags & AllDone; }
00105 
00106   /// Next - Bump this iterator logically by 1 (to next dependence) and reset
00107   /// the dep field to represent the new dependence if there is one.
00108   /// Set done = true otherwise.
00109   /// 
00110   void Next();
00111 
00112   /// SetFirstMemoryDep - Find the first memory dependence for the current Mem
00113   /// In/Out iterators. Sets dep to that dependence and returns true if one is
00114   /// found. Returns false and leaves dep unchanged otherwise.
00115   /// 
00116   bool SetFirstMemoryDep();
00117 
00118   /// SetFirstSSADep - Find the next valid data dependence for the current SSA
00119   /// In/Out iterators. A valid data dependence is one that is to/from an
00120   /// Instruction. E.g., an SSA edge from a formal parameter is not a valid
00121   /// dependence. Sets dep to that dependence and returns true if a valid one is
00122   /// found. Returns false and leaves dep unchanged otherwise.
00123   ///
00124   bool SetFirstSSADep();
00125 };
00126 
00127 
00128 //---------------------------------------------------------------------------
00129 /// PDGIterator Class - represents a pointer to a single dependence in the
00130 /// program dependence graph.  It is essentially like a pointer to an object of
00131 /// class Dependence but it is much more efficient to retrieve information about
00132 /// the dependence directly rather than constructing the equivalent Dependence
00133 /// object (since that object is normally not constructed for SSA def-use
00134 /// dependences).
00135 ///
00136 class PDGIterator: public forward_iterator<Dependence, ptrdiff_t> {
00137   DepIterState* istate;
00138 
00139 #if 0
00140   /*copy*/     PDGIterator    (const PDGIterator& I);   // do not implement!
00141   PDGIterator& operator=      (const PDGIterator& I);   // do not implement!
00142 
00143   /*copy*/     PDGIterator    (PDGIterator& I) : istate(I.istate) {
00144     I.istate = NULL;                  // ensure this is not deleted twice.
00145   }
00146 #endif
00147 
00148   friend class PgmDependenceGraph;
00149 
00150 public:
00151   typedef PDGIterator _Self;
00152 
00153   PDGIterator(DepIterState* _istate) : istate(_istate) {}
00154   ~PDGIterator() { delete istate; }
00155 
00156   PDGIterator(const PDGIterator& I) :istate(new DepIterState(*I.istate)) {}
00157 
00158   PDGIterator& operator=(const PDGIterator& I) {
00159     if (istate) delete istate;
00160     istate = new DepIterState(*I.istate);
00161     return *this;
00162   }
00163 
00164   /// fini - check if the iteration is complete
00165   /// 
00166   bool fini() const { return !istate || istate->done(); }
00167 
00168   // Retrieve the underlying Dependence.  Returns NULL if fini().
00169   // 
00170   Dependence* operator*()  const { return fini() ?  NULL : &istate->dep; }
00171   Dependence* operator->() const { assert(!fini()); return &istate->dep; }
00172 
00173   // Increment the iterator
00174   // 
00175   _Self& operator++() { if (!fini()) istate->Next(); return *this;}
00176   _Self& operator++(int);   // do not implement!
00177 
00178   // Equality comparison: a "null" state should compare equal to done
00179   // This is efficient for comparing with "end" or with itself, but could
00180   // be quite inefficient for other cases.
00181   // 
00182   bool operator==(const PDGIterator& I) const {
00183     if (I.istate == NULL)               // most common case: iter == end()
00184       return (istate == NULL || istate->done());
00185     if (istate == NULL)
00186       return (I.istate == NULL || I.istate->done());
00187     return (*istate == *I.istate);
00188   }
00189   bool operator!=(const PDGIterator& I) const {
00190     return ! (*this == I);
00191   }
00192 };
00193 
00194 
00195 ///---------------------------------------------------------------------------
00196 /// class PgmDependenceGraph:
00197 ///
00198 /// This pass enumerates dependences incident on each instruction in a function.
00199 /// It can be made a FunctionPass once a Pass (such as Parallelize) is
00200 /// allowed to use a FunctionPass such as this one.
00201 ///---------------------------------------------------------------------------
00202 
00203 class PgmDependenceGraph: public ModulePass {
00204 
00205   /// Information about the function being analyzed.
00206   /// 
00207   DependenceGraph* memDepGraph;
00208   
00209   // print helper function.
00210   void printOutgoingSSADeps(Instruction& I, std::ostream &O);
00211 
00212   /// MakeIterator - creates and initializes an iterator as specified.
00213   ///
00214   PDGIterator   MakeIterator(Instruction&     I,
00215                              bool             incomingDeps,
00216                              PDGIteratorFlags whichDeps);
00217   
00218   /// MakeIterator - creates a null iterator representing end-of-iteration.
00219   /// 
00220   PDGIterator  MakeIterator() { return PDGIterator(NULL); }
00221 
00222   friend class PDGIterator;
00223   friend class DepIterState;
00224 
00225 public:
00226   typedef PDGIterator iterator;
00227   /* typedef PDGIterator<const Dependence> const iterator; */
00228 
00229 public:
00230   PgmDependenceGraph() : memDepGraph(NULL) {}
00231   ~PgmDependenceGraph() {}
00232 
00233   /// Iterators to enumerate the program dependence graph for a function.
00234   /// Note that this does not provide "end" iterators to check for completion.
00235   /// Instead, just use iterator::fini() or iterator::operator*() == NULL
00236   ///
00237   iterator  inDepBegin(Instruction& I, PDGIteratorFlags whichDeps = AllDeps) {
00238     return MakeIterator(I, /*inDeps*/ true, whichDeps);
00239   }
00240   iterator  inDepEnd  (Instruction& I, PDGIteratorFlags whichDeps = AllDeps) {
00241     return MakeIterator();
00242   }
00243   iterator  outDepBegin(Instruction& I, PDGIteratorFlags whichDeps = AllDeps) {
00244     return MakeIterator(I, /*inDeps*/ false, whichDeps);
00245   }
00246   iterator  outDepEnd  (Instruction& I, PDGIteratorFlags whichDeps = AllDeps) {
00247     return MakeIterator();
00248   }
00249 
00250   //------------------------------------------------------------------------
00251   /// TEMPORARY FUNCTIONS TO MAKE THIS A MODULE PASS ---
00252   /// These functions will go away once this class becomes a FunctionPass.
00253 
00254   /// Driver function to compute dependence graphs for every function.
00255   /// 
00256   bool runOnModule(Module& M) { return true; }
00257 
00258   /// getGraph() -- Retrieve the pgm dependence graph for a function.
00259   /// This is temporary and will go away once this is a FunctionPass.
00260   /// At that point, this class itself will be the PgmDependenceGraph you want.
00261   /// 
00262   PgmDependenceGraph& getGraph(Function& F) {
00263     Visiting(F);
00264     return *this;
00265   }
00266 
00267   private:
00268   void Visiting(Function& F) {
00269     memDepGraph = &getAnalysis<MemoryDepAnalysis>().getGraph(F);
00270   }
00271   public:
00272   ///----END TEMPORARY FUNCTIONS---------------------------------------------
00273 
00274 
00275   /// This initializes the program dependence graph iterator for a function.
00276   /// 
00277   bool runOnFunction(Function& func) {
00278     Visiting(func);
00279     return true;
00280   }
00281 
00282   /// getAnalysisUsage - This does not modify anything.
00283   /// It uses the Memory Dependence Analysis pass.
00284   /// It needs to use the PostDominanceFrontier pass, but cannot because
00285   /// that is a FunctionPass.  This means control dependence are not emumerated.
00286   ///
00287   void getAnalysisUsage(AnalysisUsage &AU) const {
00288     AU.setPreservesAll();
00289     AU.addRequired<MemoryDepAnalysis>();
00290     /* AU.addRequired<PostDominanceFrontier>(); */
00291   }
00292 
00293   /// Debugging support methods
00294   /// 
00295   void print(std::ostream &O) const;
00296   void dump() const;
00297 };
00298 
00299 } // End llvm namespace
00300 
00301 #endif