Iterator that enumerates the ProgramDependenceGraph (PDG) for a function,

i.e., enumerates all data and control dependences for the function.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@4958 91177308-0d34-0410-b5e6-96231b3b80d8

3 files changed, 808 insertions, 0 deletions

diff --git a/include/llvm/Analysis/PgmDependenceGraph.h b/include/llvm/Analysis/PgmDependenceGraph.h
new file mode 100644
index 0000000..778ee78
--- /dev/null
+++ b/include/llvm/Analysis/PgmDependenceGraph.h
@@ -0,0 +1,308 @@
+//===- PgmDependenceGraph.h - Enumerate the PDG for a function --*- C++ -*-===//
+// 
+// The Program Dependence Graph (PDG) for a single function represents all
+// data and control dependences for the function.  This file provides an
+// iterator to enumerate all these dependences.  In particular, it enumerates:
+// 
+// -- Data dependences on memory locations, computed using the
+//    MemoryDepAnalysis pass;
+// -- Data dependences on SSA registers, directly from Def-Use edges of Values;
+// -- Control dependences, computed using postdominance frontiers
+//    (NOT YET IMPLEMENTED).
+// 
+// Note that this file does not create an explicit dependence graph --
+// it only provides an iterator to traverse the PDG conceptually.
+// The MemoryDepAnalysis does build an explicit graph, which is used internally
+// here.  That graph could be augmented with the other dependences above if
+// desired, but for most uses there will be little need to do that.
+// 
+// Key Classes:
+// 
+// enum PDGIteratorFlags -- Specify which dependences to enumerate.
+// 
+// class PDGIterator     -- The PDG iterator.  This is essentially like a
+//                          pointer to class Dependence, but doesn't explicitly
+//                          construct a Dependence object for each dependence.
+//
+// class PgmDependenceGraph -- Interface to obtain PDGIterators for each
+//                          instruction.
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_PGMDEPENDENCEGRAPH_H
+#define LLVM_ANALYSIS_PGMDEPENDENCEGRAPH_H
+
+#include "llvm/Analysis/DependenceGraph.h"
+#include "llvm/Analysis/MemoryDepAnalysis.h"
+/* #include "llvm/Analysis/PostDominators.h" -- see below */
+#include "llvm/Instruction.h"
+#include "llvm/Value.h"
+#include "llvm/Pass.h"
+#include "Support/NonCopyable.h"
+#include <iterator>
+
+
+class Instruction;
+class Function;
+class DSGraph;
+class DependenceGraph;
+class PgmDependenceGraph;
+
+
+///---------------------------------------------------------------------------
+/// enum PDGIteratorFlags
+/// 
+/// These bit flags specify which dependences incident on a statement are to be
+/// enumerated: Memory deps, SSA deps, Control deps, or any combination thereof.
+///---------------------------------------------------------------------------
+
+enum PDGIteratorFlags {
+  MemoryDeps  = 0x1,                                 // load/store/call deps
+  SSADeps     = 0x2,                                 // SSA deps (true)
+  ControlDeps = /* 0x4*/ 0x0,                        // control dependences
+  AllDataDeps = MemoryDeps | SSADeps,                // shorthand for data deps
+  AllDeps     = MemoryDeps | SSADeps | ControlDeps   // shorthand for all three
+};
+
+
+///---------------------------------------------------------------------------
+/// struct DepIterState
+/// 
+/// This data type is primarily an internal implementation detail.
+/// It are exposed here only to give inlinable access to field dep,
+/// which is the representation for the current dependence pointed to by
+/// a PgmDependenceGraph::iterator.
+///---------------------------------------------------------------------------
+
+class DepIterState {
+private:
+  typedef char IterStateFlags;
+  static const IterStateFlags NoFlag, MemDone, SSADone, AllDone, FirstTimeFlag;
+
+public:
+  DepGraphNode*              depNode;        // the node being enumerated
+  DependenceGraph::iterator  memDepIter;     // pointer to current memory dep
+  Instruction::op_iterator   ssaInEdgeIter;  // pointer to current SSA in-dep
+  Value::use_iterator        ssaOutEdgeIter; // pointer to current SSA out-dep
+  DependenceGraph*           memDepGraph;    // the core dependence graph
+  Dependence                 dep;            // the "current" dependence
+  PDGIteratorFlags           depFlags:8;     // which deps are we enumerating?
+  IterStateFlags             iterFlags:8;    // marking where the iter stands
+
+  /*ctor*/ DepIterState  (DependenceGraph* _memDepGraph,
+                          Instruction&     I, 
+                          bool             incomingDeps,
+                          PDGIteratorFlags whichDeps);
+
+  bool  operator==(const DepIterState& S) {
+    assert(memDepGraph == S.memDepGraph &&
+           "Incompatible iterators! This is a probable sign of something BAD.");
+    return (iterFlags == S.iterFlags &&
+            dep == S.dep && depFlags == S.depFlags && depNode == S.depNode &&
+            memDepIter == S.memDepIter && ssaInEdgeIter == S.ssaInEdgeIter &&
+            ssaOutEdgeIter == S.ssaOutEdgeIter);
+  }
+
+  // Is the iteration completely done?
+  // 
+  bool          done            () const { return iterFlags & AllDone; }
+
+  // Bump this iterator logically by 1 (to next dependence) and reset the
+  // dep field to represent the new dependence if there is one.
+  // Set done = true otherwise.
+  // 
+  void          Next          ();
+
+  // Find the first memory dependence for the current Mem In/Out iterators.
+  // Sets dep to that dependence and returns true if one is found.
+  // Returns false and leaves dep unchanged otherwise.
+  // 
+  bool          SetFirstMemoryDep();
+
+  // Find the next valid data dependence for the current SSA In/Out iterators.
+  // A valid data dependence is one that is to/from an Instruction.
+  // E.g., an SSA edge from a formal parameter is not a valid dependence.
+  // Sets dep to that dependence and returns true if a valid one is found.
+  // Returns false and leaves dep unchanged otherwise.
+  // 
+  bool          SetFirstSSADep  ();
+};
+
+
+///---------------------------------------------------------------------------
+/// The dependence iterator class.  This class represents a pointer to
+/// a single dependence in the program dependence graph.  It is essentially
+/// like a pointer to an object of class Dependence but it is much more
+/// efficient to retrieve information about the dependence directly rather
+/// than constructing the equivalent Dependence object (since that object
+/// is normally not constructed for SSA def-use dependences).
+///---------------------------------------------------------------------------
+
+class PDGIterator: public forward_iterator<Dependence, ptrdiff_t>
+{
+  DepIterState* istate;
+
+#if 0
+  /*copy*/     PDGIterator    (const PDGIterator& I);   // do not implement!
+  PDGIterator& operator=      (const PDGIterator& I);   // do not implement!
+
+  /*copy*/     PDGIterator    (PDGIterator& I) : istate(I.istate) {
+    I.istate = NULL;                  // ensure this is not deleted twice.
+  }
+#endif
+
+  friend class PgmDependenceGraph;
+
+public:
+  typedef PDGIterator _Self;
+
+  /*ctor*/      PDGIterator     (DepIterState* _istate) : istate(_istate) { }
+  /*dtor*/     ~PDGIterator     ()                        { delete istate; }
+
+  /*copy*/      PDGIterator     (const PDGIterator& I)
+    : istate(new DepIterState(*I.istate)) { }
+
+  PDGIterator& operator=        (const PDGIterator& I) {
+    if (istate) delete istate;
+    istate = new DepIterState(*I.istate);
+    return *this;
+  }
+
+  // Check if the iteration is complete
+  // 
+  bool          fini()       const { return !istate || istate->done(); }
+
+  // Retrieve the underlying Dependence.  Returns NULL if fini().
+  // 
+  Dependence*   operator*()  const { return fini() ?  NULL : &istate->dep; }
+  Dependence*   operator->() const { assert(!fini()); return &istate->dep; }
+
+  // Increment the iterator
+  // 
+  _Self&        operator++()       { if (!fini()) istate->Next(); return *this;}
+  _Self&        operator++(int);   // do not implement!
+
+  // Equality comparison: a "null" state should compare equal to done
+  // This is efficient for comparing with "end" or with itself, but could
+  // be quite inefficient for other cases.
+  // 
+  bool          operator==(const PDGIterator& I) const {
+    if (I.istate == NULL)               // most common case: iter == end()
+      return (istate == NULL || istate->done());
+    if (istate == NULL)
+      return (I.istate == NULL || I.istate->done());
+    return (*istate == *I.istate);
+  }
+  bool          operator!=(const PDGIterator& I) const {
+    return ! (*this == I);
+  }
+};
+
+
+///---------------------------------------------------------------------------
+/// class PgmDependenceGraph:
+///
+/// This pass enumerates dependences incident on each instruction in a function.
+/// It can be made a FunctionPass once a Pass (such as Parallelize) is
+/// allowed to use a FunctionPass such as this one.
+///---------------------------------------------------------------------------
+
+class PgmDependenceGraph: public Pass {
+
+  /// Information about the function being analyzed.
+  /// 
+  DependenceGraph* memDepGraph;
+  
+  // print helper function.
+  void printOutgoingSSADeps(Instruction& I, std::ostream &O);
+
+  // MakeIterator --
+  // The first version creates and initializes an iterator as specified.
+  // The second version creates a null iterator representing end-of-iteration.
+  // 
+  PDGIterator   MakeIterator    (Instruction&     I,
+                                 bool             incomingDeps,
+                                 PDGIteratorFlags whichDeps);
+  
+  PDGIterator  MakeIterator     () { return PDGIterator(NULL); }
+
+  friend class PDGIterator;
+  friend class DepIterState;
+
+public:
+  typedef PDGIterator iterator;
+  /* typedef PDGIterator<const Dependence> const iterator; */
+
+public:
+  PgmDependenceGraph() : memDepGraph(NULL) { }
+  ~PgmDependenceGraph() { }
+
+  /// Iterators to enumerate the program dependence graph for a function.
+  /// Note that this does not provide "end" iterators to check for completion.
+  /// Instead, just use iterator::fini() or iterator::operator*() == NULL
+  // 
+  iterator  inDepBegin(Instruction& I, PDGIteratorFlags whichDeps = AllDeps) {
+    return MakeIterator(I, /*inDeps*/ true, whichDeps);
+  }
+  iterator  inDepEnd  (Instruction& I, PDGIteratorFlags whichDeps = AllDeps) {
+    return MakeIterator();
+  }
+  iterator  outDepBegin(Instruction& I, PDGIteratorFlags whichDeps = AllDeps) {
+    return MakeIterator(I, /*inDeps*/ false, whichDeps);
+  }
+  iterator  outDepEnd  (Instruction& I, PDGIteratorFlags whichDeps = AllDeps) {
+    return MakeIterator();
+  }
+
+  ///------------------------------------------------------------------------
+  /// TEMPORARY FUNCTIONS TO MAKE THIS A MODULE PASS ---
+  /// These functions will go away once this class becomes a FunctionPass.
+
+  /// Driver function to compute dependence graphs for every function.
+  /// 
+  bool run(Module& M) { return true; }
+
+  /// getGraph() -- Retrieve the pgm dependence graph for a function.
+  /// This is temporary and will go away once this is a FunctionPass.
+  /// At that point, this class itself will be the PgmDependenceGraph you want.
+  /// 
+  PgmDependenceGraph& getGraph(Function& F) {
+    Visiting(F);
+    return *this;
+  }
+
+  private:
+  void Visiting(Function& F) {
+    memDepGraph = &getAnalysis<MemoryDepAnalysis>().getGraph(F);
+  }
+  public:
+  ///----END TEMPORARY FUNCTIONS---------------------------------------------
+
+
+  /// This initializes the program dependence graph iterator for a function.
+  /// 
+  bool runOnFunction(Function& func) {
+    Visiting(func);
+    return true;
+  }
+
+  /// getAnalysisUsage - This does not modify anything.
+  /// It uses the Memory Dependence Analysis pass.
+  /// It needs to use the PostDominanceFrontier pass, but cannot because
+  /// that is a FunctionPass.  This means control dependence are not emumerated.
+  ///
+  void getAnalysisUsage(AnalysisUsage &AU) const {
+    AU.setPreservesAll();
+    AU.addRequired<MemoryDepAnalysis>();
+    /* AU.addRequired<PostDominanceFrontier>(); */
+  }
+
+  /// Debugging support methods
+  /// 
+  void print(std::ostream &O) const;
+  void dump() const;
+};
+
+
+//===----------------------------------------------------------------------===//
+
+#endif
diff --git a/lib/Analysis/DataStructure/PgmDependenceGraph.cpp b/lib/Analysis/DataStructure/PgmDependenceGraph.cpp
new file mode 100644
index 0000000..63a0cdf
--- /dev/null
+++ b/lib/Analysis/DataStructure/PgmDependenceGraph.cpp
@@ -0,0 +1,250 @@
+//===- PgmDependenceGraph.cpp - Enumerate PDG for a function ----*- C++ -*-===//
+// 
+// The Program Dependence Graph (PDG) for a single function represents all
+// data and control dependences for the function.  This file provides an
+// iterator to enumerate all these dependences.  In particular, it enumerates:
+// 
+// -- Data dependences on memory locations, computed using the
+//    MemoryDepAnalysis pass;
+// -- Data dependences on SSA registers, directly from Def-Use edges of Values;
+// -- Control dependences, computed using postdominance frontiers
+//    (NOT YET IMPLEMENTED).
+// 
+// Note that this file does not create an explicit dependence graph --
+// it only provides an iterator to traverse the PDG conceptually.
+// The MemoryDepAnalysis does build an explicit graph, which is used internally
+// here.  That graph could be augmented with the other dependences above if
+// desired, but for most uses there will be little need to do that.
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/PgmDependenceGraph.h"
+#include "llvm/Analysis/MemoryDepAnalysis.h"
+#include "llvm/Analysis/PostDominators.h"
+#include "llvm/Function.h"
+#include "llvm/BasicBlock.h"
+#include "llvm/Instruction.h"
+
+
+
+//----------------------------------------------------------------------------
+// class DepIterState
+//----------------------------------------------------------------------------
+
+const DepIterState::IterStateFlags DepIterState::NoFlag  = 0x0;
+const DepIterState::IterStateFlags DepIterState::MemDone = 0x1;
+const DepIterState::IterStateFlags DepIterState::SSADone = 0x2;
+const DepIterState::IterStateFlags DepIterState::AllDone = 0x4;
+const DepIterState::IterStateFlags DepIterState::FirstTimeFlag= 0x8;
+
+// Find the first memory dependence for the current Mem In/Out iterators.
+// Find the first memory dependence for the current Mem In/Out iterators.
+// Sets dep to that dependence and returns true if one is found.
+// 
+bool DepIterState::SetFirstMemoryDep()
+{
+  if (! (depFlags & MemoryDeps))
+    return false;
+
+  bool doIncomingDeps = dep.getDepType() & IncomingFlag;
+
+  if (( doIncomingDeps && memDepIter == memDepGraph->inDepEnd( *depNode)) ||
+      (!doIncomingDeps && memDepIter == memDepGraph->outDepEnd(*depNode)))
+    {
+      iterFlags |= MemDone;
+      return false;
+    }
+
+  dep = *memDepIter;     // simple copy from dependence in memory DepGraph
+
+  return true;
+}
+
+
+// Find the first valid data dependence for the current SSA In/Out iterators.
+// A valid data dependence is one that is to/from an Instruction.
+// E.g., an SSA edge from a formal parameter is not a valid dependence.
+// Sets dep to that dependence and returns true if a valid one is found.
+// Returns false and leaves dep unchanged otherwise.
+// 
+bool DepIterState::SetFirstSSADep()
+{
+  if (! (depFlags & SSADeps))
+    return false;
+
+  bool doIncomingDeps = dep.getDepType() & IncomingFlag;
+  Instruction* firstTarget = NULL;
+
+  // Increment the In or Out iterator till it runs out or we find a valid dep
+  if (doIncomingDeps)
+    for (Instruction::op_iterator E = depNode->getInstr().op_end();
+         ssaInEdgeIter != E &&
+           (firstTarget = dyn_cast<Instruction>(ssaInEdgeIter->get()))== NULL; )
+      ++ssaInEdgeIter;
+  else
+    for (Value::use_iterator E = depNode->getInstr().use_end();
+         ssaOutEdgeIter != E &&
+           (firstTarget = dyn_cast<Instruction>(*ssaOutEdgeIter)) == NULL; )
+      ++ssaOutEdgeIter;
+
+  // If the iterator ran out before we found a valid dep, there isn't one.
+  if (!firstTarget)
+    {
+      iterFlags |= SSADone;
+      return false;
+    }
+
+  // Create a simple dependence object to represent this SSA dependence.
+  dep = Dependence(memDepGraph->getNode(*firstTarget, /*create*/ true),
+                   TrueDependence, doIncomingDeps);
+
+  return true;
+}
+
+
+DepIterState::DepIterState(DependenceGraph* _memDepGraph,
+                           Instruction&     I, 
+                           bool             incomingDeps,
+                           PDGIteratorFlags whichDeps)
+  : memDepGraph(_memDepGraph),
+    depFlags(whichDeps),
+    iterFlags(NoFlag)
+{
+  depNode = memDepGraph->getNode(I, /*create*/ true);
+
+  if (incomingDeps)
+    {
+      if (whichDeps & MemoryDeps) memDepIter= memDepGraph->inDepBegin(*depNode);
+      if (whichDeps & SSADeps)    ssaInEdgeIter = I.op_begin();
+      /* Initialize control dependence iterator here. */
+    }
+  else
+    {
+      if (whichDeps & MemoryDeps) memDepIter=memDepGraph->outDepBegin(*depNode);
+      if (whichDeps & SSADeps)    ssaOutEdgeIter = I.use_begin();
+      /* Initialize control dependence iterator here. */
+    }
+
+  // Set the dependence to the first of a memory dep or an SSA dep
+  // and set the done flag if either is found.  Otherwise, set the
+  // init flag to indicate that the iterators have just been initialized.
+  // 
+  if (!SetFirstMemoryDep() && !SetFirstSSADep())
+    iterFlags |= AllDone;
+  else
+    iterFlags |= FirstTimeFlag;
+}
+
+
+// Helper function for ++ operator that bumps iterator by 1 (to next
+// dependence) and resets the dep field to represent the new dependence.
+// 
+void DepIterState::Next()
+{
+  // firstMemDone and firstSsaDone are used to indicate when the memory or
+  // SSA iterators just ran out, or when this is the very first increment.
+  // In either case, the next iterator (if any) should not be incremented.
+  // 
+  bool firstMemDone = iterFlags & FirstTimeFlag;
+  bool firstSsaDone = iterFlags & FirstTimeFlag;
+  bool doIncomingDeps = dep.getDepType() & IncomingFlag;
+
+  if (depFlags & MemoryDeps && ! (iterFlags & MemDone))
+    {
+      iterFlags &= ~FirstTimeFlag;           // clear "firstTime" flag
+      ++memDepIter;
+      if (SetFirstMemoryDep())
+        return;
+      firstMemDone = true;              // flags that we _just_ rolled over
+    }
+
+  if (depFlags & SSADeps && ! (iterFlags & SSADone))
+    {
+      // Don't increment the SSA iterator if we either just rolled over from
+      // the memory dep iterator, or if the SSA iterator is already done.
+      iterFlags &= ~FirstTimeFlag;           // clear "firstTime" flag
+      if (! firstMemDone)
+        if (doIncomingDeps) ++ssaInEdgeIter;
+        else ++ssaOutEdgeIter;
+      if (SetFirstSSADep())
+        return;
+      firstSsaDone = true;                   // flags if we just rolled over
+    } 
+
+  if (depFlags & ControlDeps != 0)
+    {
+      assert(0 && "Cannot handle control deps");
+      // iterFlags &= ~FirstTimeFlag;           // clear "firstTime" flag
+    }
+
+  // This iterator is now complete.
+  iterFlags |= AllDone;
+}
+
+
+//----------------------------------------------------------------------------
+// class PgmDependenceGraph
+//----------------------------------------------------------------------------
+
+
+// MakeIterator -- Create and initialize an iterator as specified.
+// 
+PDGIterator PgmDependenceGraph::MakeIterator(Instruction& I,
+                                             bool incomingDeps,
+                                             PDGIteratorFlags whichDeps)
+{
+  assert(memDepGraph && "Function not initialized!");
+  return PDGIterator(new DepIterState(memDepGraph, I, incomingDeps, whichDeps));
+}
+
+
+void PgmDependenceGraph::printOutgoingSSADeps(Instruction& I,
+                                              std::ostream &O)
+{
+  iterator SI = this->outDepBegin(I, SSADeps);
+  iterator SE = this->outDepEnd(I, SSADeps);
+  if (SI == SE)
+    return;
+
+  O << "\n    Outgoing SSA dependences:\n";
+  for ( ; SI != SE; ++SI)
+    {
+      O << "\t";
+      SI->print(O);
+      O << " to instruction:";
+      O << SI->getSink()->getInstr();
+    }
+}
+
+
+void PgmDependenceGraph::print(std::ostream &O) const
+{
+  MemoryDepAnalysis& graphSet = getAnalysis<MemoryDepAnalysis>();
+
+  // TEMPORARY LOOP
+  for (hash_map<Function*, DependenceGraph*>::iterator
+         I = graphSet.funcMap.begin(), E = graphSet.funcMap.end();
+       I != E; ++I)
+    {
+      Function* func = I->first;
+      DependenceGraph* depGraph = I->second;
+      const_cast<PgmDependenceGraph*>(this)->runOnFunction(*func);
+
+  O << "DEPENDENCE GRAPH FOR FUNCTION " << func->getName() << ":\n";
+  for (Function::iterator BB=func->begin(), FE=func->end(); BB != FE; ++BB)
+    for (BasicBlock::iterator II=BB->begin(), IE=BB->end(); II !=IE; ++II)
+      {
+        DepGraphNode* dgNode = depGraph->getNode(*II, /*create*/ true);
+        dgNode->print(O);
+        const_cast<PgmDependenceGraph*>(this)->printOutgoingSSADeps(*II, O);
+      }
+    } // END TEMPORARY LOOP
+}
+
+
+void PgmDependenceGraph::dump() const
+{
+  this->print(std::cerr);
+}
+
+static RegisterAnalysis<PgmDependenceGraph>
+Z("pgmdep", "Enumerate Program Dependence Graph (data and control)");
diff --git a/lib/Analysis/IPA/PgmDependenceGraph.cpp b/lib/Analysis/IPA/PgmDependenceGraph.cpp
new file mode 100644
index 0000000..63a0cdf
--- /dev/null
+++ b/lib/Analysis/IPA/PgmDependenceGraph.cpp
@@ -0,0 +1,250 @@
+//===- PgmDependenceGraph.cpp - Enumerate PDG for a function ----*- C++ -*-===//
+// 
+// The Program Dependence Graph (PDG) for a single function represents all
+// data and control dependences for the function.  This file provides an
+// iterator to enumerate all these dependences.  In particular, it enumerates:
+// 
+// -- Data dependences on memory locations, computed using the
+//    MemoryDepAnalysis pass;
+// -- Data dependences on SSA registers, directly from Def-Use edges of Values;
+// -- Control dependences, computed using postdominance frontiers
+//    (NOT YET IMPLEMENTED).
+// 
+// Note that this file does not create an explicit dependence graph --
+// it only provides an iterator to traverse the PDG conceptually.
+// The MemoryDepAnalysis does build an explicit graph, which is used internally
+// here.  That graph could be augmented with the other dependences above if
+// desired, but for most uses there will be little need to do that.
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/PgmDependenceGraph.h"
+#include "llvm/Analysis/MemoryDepAnalysis.h"
+#include "llvm/Analysis/PostDominators.h"
+#include "llvm/Function.h"
+#include "llvm/BasicBlock.h"
+#include "llvm/Instruction.h"
+
+
+
+//----------------------------------------------------------------------------
+// class DepIterState
+//----------------------------------------------------------------------------
+
+const DepIterState::IterStateFlags DepIterState::NoFlag  = 0x0;
+const DepIterState::IterStateFlags DepIterState::MemDone = 0x1;
+const DepIterState::IterStateFlags DepIterState::SSADone = 0x2;
+const DepIterState::IterStateFlags DepIterState::AllDone = 0x4;
+const DepIterState::IterStateFlags DepIterState::FirstTimeFlag= 0x8;
+
+// Find the first memory dependence for the current Mem In/Out iterators.
+// Find the first memory dependence for the current Mem In/Out iterators.
+// Sets dep to that dependence and returns true if one is found.
+// 
+bool DepIterState::SetFirstMemoryDep()
+{
+  if (! (depFlags & MemoryDeps))
+    return false;
+
+  bool doIncomingDeps = dep.getDepType() & IncomingFlag;
+
+  if (( doIncomingDeps && memDepIter == memDepGraph->inDepEnd( *depNode)) ||
+      (!doIncomingDeps && memDepIter == memDepGraph->outDepEnd(*depNode)))
+    {
+      iterFlags |= MemDone;
+      return false;
+    }
+
+  dep = *memDepIter;     // simple copy from dependence in memory DepGraph
+
+  return true;
+}
+
+
+// Find the first valid data dependence for the current SSA In/Out iterators.
+// A valid data dependence is one that is to/from an Instruction.
+// E.g., an SSA edge from a formal parameter is not a valid dependence.
+// Sets dep to that dependence and returns true if a valid one is found.
+// Returns false and leaves dep unchanged otherwise.
+// 
+bool DepIterState::SetFirstSSADep()
+{
+  if (! (depFlags & SSADeps))
+    return false;
+
+  bool doIncomingDeps = dep.getDepType() & IncomingFlag;
+  Instruction* firstTarget = NULL;
+
+  // Increment the In or Out iterator till it runs out or we find a valid dep
+  if (doIncomingDeps)
+    for (Instruction::op_iterator E = depNode->getInstr().op_end();
+         ssaInEdgeIter != E &&
+           (firstTarget = dyn_cast<Instruction>(ssaInEdgeIter->get()))== NULL; )
+      ++ssaInEdgeIter;
+  else
+    for (Value::use_iterator E = depNode->getInstr().use_end();
+         ssaOutEdgeIter != E &&
+           (firstTarget = dyn_cast<Instruction>(*ssaOutEdgeIter)) == NULL; )
+      ++ssaOutEdgeIter;
+
+  // If the iterator ran out before we found a valid dep, there isn't one.
+  if (!firstTarget)
+    {
+      iterFlags |= SSADone;
+      return false;
+    }
+
+  // Create a simple dependence object to represent this SSA dependence.
+  dep = Dependence(memDepGraph->getNode(*firstTarget, /*create*/ true),
+                   TrueDependence, doIncomingDeps);
+
+  return true;
+}
+
+
+DepIterState::DepIterState(DependenceGraph* _memDepGraph,
+                           Instruction&     I, 
+                           bool             incomingDeps,
+                           PDGIteratorFlags whichDeps)
+  : memDepGraph(_memDepGraph),
+    depFlags(whichDeps),
+    iterFlags(NoFlag)
+{
+  depNode = memDepGraph->getNode(I, /*create*/ true);
+
+  if (incomingDeps)
+    {
+      if (whichDeps & MemoryDeps) memDepIter= memDepGraph->inDepBegin(*depNode);
+      if (whichDeps & SSADeps)    ssaInEdgeIter = I.op_begin();
+      /* Initialize control dependence iterator here. */
+    }
+  else
+    {
+      if (whichDeps & MemoryDeps) memDepIter=memDepGraph->outDepBegin(*depNode);
+      if (whichDeps & SSADeps)    ssaOutEdgeIter = I.use_begin();
+      /* Initialize control dependence iterator here. */
+    }
+
+  // Set the dependence to the first of a memory dep or an SSA dep
+  // and set the done flag if either is found.  Otherwise, set the
+  // init flag to indicate that the iterators have just been initialized.
+  // 
+  if (!SetFirstMemoryDep() && !SetFirstSSADep())
+    iterFlags |= AllDone;
+  else
+    iterFlags |= FirstTimeFlag;
+}
+
+
+// Helper function for ++ operator that bumps iterator by 1 (to next
+// dependence) and resets the dep field to represent the new dependence.
+// 
+void DepIterState::Next()
+{
+  // firstMemDone and firstSsaDone are used to indicate when the memory or
+  // SSA iterators just ran out, or when this is the very first increment.
+  // In either case, the next iterator (if any) should not be incremented.
+  // 
+  bool firstMemDone = iterFlags & FirstTimeFlag;
+  bool firstSsaDone = iterFlags & FirstTimeFlag;
+  bool doIncomingDeps = dep.getDepType() & IncomingFlag;
+
+  if (depFlags & MemoryDeps && ! (iterFlags & MemDone))
+    {
+      iterFlags &= ~FirstTimeFlag;           // clear "firstTime" flag
+      ++memDepIter;
+      if (SetFirstMemoryDep())
+        return;
+      firstMemDone = true;              // flags that we _just_ rolled over
+    }
+
+  if (depFlags & SSADeps && ! (iterFlags & SSADone))
+    {
+      // Don't increment the SSA iterator if we either just rolled over from
+      // the memory dep iterator, or if the SSA iterator is already done.
+      iterFlags &= ~FirstTimeFlag;           // clear "firstTime" flag
+      if (! firstMemDone)
+        if (doIncomingDeps) ++ssaInEdgeIter;
+        else ++ssaOutEdgeIter;
+      if (SetFirstSSADep())
+        return;
+      firstSsaDone = true;                   // flags if we just rolled over
+    } 
+
+  if (depFlags & ControlDeps != 0)
+    {
+      assert(0 && "Cannot handle control deps");
+      // iterFlags &= ~FirstTimeFlag;           // clear "firstTime" flag
+    }
+
+  // This iterator is now complete.
+  iterFlags |= AllDone;
+}
+
+
+//----------------------------------------------------------------------------
+// class PgmDependenceGraph
+//----------------------------------------------------------------------------
+
+
+// MakeIterator -- Create and initialize an iterator as specified.
+// 
+PDGIterator PgmDependenceGraph::MakeIterator(Instruction& I,
+                                             bool incomingDeps,
+                                             PDGIteratorFlags whichDeps)
+{
+  assert(memDepGraph && "Function not initialized!");
+  return PDGIterator(new DepIterState(memDepGraph, I, incomingDeps, whichDeps));
+}
+
+
+void PgmDependenceGraph::printOutgoingSSADeps(Instruction& I,
+                                              std::ostream &O)
+{
+  iterator SI = this->outDepBegin(I, SSADeps);
+  iterator SE = this->outDepEnd(I, SSADeps);
+  if (SI == SE)
+    return;
+
+  O << "\n    Outgoing SSA dependences:\n";
+  for ( ; SI != SE; ++SI)
+    {
+      O << "\t";
+      SI->print(O);
+      O << " to instruction:";
+      O << SI->getSink()->getInstr();
+    }
+}
+
+
+void PgmDependenceGraph::print(std::ostream &O) const
+{
+  MemoryDepAnalysis& graphSet = getAnalysis<MemoryDepAnalysis>();
+
+  // TEMPORARY LOOP
+  for (hash_map<Function*, DependenceGraph*>::iterator
+         I = graphSet.funcMap.begin(), E = graphSet.funcMap.end();
+       I != E; ++I)
+    {
+      Function* func = I->first;
+      DependenceGraph* depGraph = I->second;
+      const_cast<PgmDependenceGraph*>(this)->runOnFunction(*func);
+
+  O << "DEPENDENCE GRAPH FOR FUNCTION " << func->getName() << ":\n";
+  for (Function::iterator BB=func->begin(), FE=func->end(); BB != FE; ++BB)
+    for (BasicBlock::iterator II=BB->begin(), IE=BB->end(); II !=IE; ++II)
+      {
+        DepGraphNode* dgNode = depGraph->getNode(*II, /*create*/ true);
+        dgNode->print(O);
+        const_cast<PgmDependenceGraph*>(this)->printOutgoingSSADeps(*II, O);
+      }
+    } // END TEMPORARY LOOP
+}
+
+
+void PgmDependenceGraph::dump() const
+{
+  this->print(std::cerr);
+}
+
+static RegisterAnalysis<PgmDependenceGraph>
+Z("pgmdep", "Enumerate Program Dependence Graph (data and control)");