An explicit representation of dependence graphs, and a pass that

computes a dependence graph for data dependences on memory locations
using interprocedural Mod/Ref information.


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

2 files changed, 365 insertions, 0 deletions

diff --git a/include/llvm/Analysis/DependenceGraph.h b/include/llvm/Analysis/DependenceGraph.h
new file mode 100644
index 0000000..9c803f0
--- /dev/null
+++ b/include/llvm/Analysis/DependenceGraph.h
@@ -0,0 +1,250 @@
+//===- DependenceGraph.h - Dependence graph for a function ------*- C++ -*-===//
+//
+// This file provides an explicit representation for the dependence graph
+// of a function, with one node per instruction and one edge per dependence.
+// Dependences include both data and control dependences.
+// 
+// Each dep. graph node (class DepGraphNode) keeps lists of incoming and
+// outgoing dependence edges.
+// 
+// Each dep. graph edge (class Dependence) keeps a pointer to one end-point
+// of the dependence.  This saves space and is important because dep. graphs
+// can grow quickly.  It works just fine because the standard idiom is to
+// start with a known node and enumerate the dependences to or from that node.
+//===----------------------------------------------------------------------===//
+
+
+#ifndef LLVM_ANALYSIS_DEPENDENCEGRAPH_H
+#define LLVM_ANALYSIS_DEPENDENCEGRAPH_H
+
+
+#include <Support/NonCopyable.h>
+#include <Support/hash_map>
+#include <iosfwd>
+#include <vector>
+#include <utility>
+
+class Instruction;
+class Function;
+class Dependence;
+class DepGraphNode;
+class DependenceGraph;
+
+
+//----------------------------------------------------------------------------
+// enum DependenceType: The standard data dependence types.
+//----------------------------------------------------------------------------
+
+enum DependenceType {
+  NoDependence       = 0x0,
+  TrueDependence     = 0x1,
+  AntiDependence     = 0x2,
+  OutputDependence   = 0x4,
+  ControlDependence  = 0x8,         // from a terminator to some other instr.
+  IncomingFlag       = 0x10         // is this an incoming or outgoing dep?
+};
+
+#undef SUPPORTING_LOOP_DEPENDENCES
+#ifdef SUPPORTING_LOOP_DEPENDENCES
+typedef int   DependenceDistance;       // negative means unknown distance
+typedef short DependenceLevel;          // 0 means global level outside loops
+#endif
+
+
+//----------------------------------------------------------------------------
+// class Dependence:
+// 
+// A representation of a simple (non-loop-related) dependence.
+//----------------------------------------------------------------------------
+
+class Dependence {
+  DepGraphNode*   toOrFromNode;
+  DependenceType  depType:8;
+
+public:
+  /*ctor*/      Dependence      (DepGraphNode* toOrFromN,
+                                 DependenceType type,
+                                 bool isIncoming)
+    : toOrFromNode(toOrFromN),
+      depType(type | (isIncoming? IncomingFlag : 0x0)) { }
+
+  /* copy ctor*/ Dependence     (const Dependence& D)
+    : toOrFromNode(D.toOrFromNode),
+      depType(D.depType) { }
+
+  bool operator==(const Dependence& D) {
+    return toOrFromNode == D.toOrFromNode && depType == D.depType;
+  }
+
+  /// Get information about the type of dependence.
+  /// 
+  DependenceType  getDepType() {
+    return depType;
+  }
+
+  /// Get source or sink depending on what type of node this is!
+  /// 
+  DepGraphNode*  getSrc() {
+    assert(depType & IncomingFlag); return toOrFromNode;
+  }
+  const DepGraphNode*  getSrc() const {
+    assert(depType & IncomingFlag); return toOrFromNode;
+  }
+
+  DepGraphNode*  getSink() {
+    assert(! (depType & IncomingFlag)); return toOrFromNode;
+  }
+  const DepGraphNode*  getSink() const {
+    assert(! (depType & IncomingFlag)); return toOrFromNode;
+  }
+
+  /// Debugging support methods
+  /// 
+  void print(std::ostream &O) const;
+
+  // Default constructor: Do not use directly except for graph builder code
+  // 
+  /*ctor*/ Dependence() : toOrFromNode(NULL), depType(NoDependence) { }
+};
+
+
+#ifdef SUPPORTING_LOOP_DEPENDENCES
+struct LoopDependence: public Dependence {
+  DependenceDirection dir;
+  DependenceDistance  distance;
+  DependenceLevel     level;
+  LoopInfo*           enclosingLoop;
+};
+#endif
+
+
+//----------------------------------------------------------------------------
+// class DepGraphNode:
+// 
+// A representation of a single node in a dependence graph, corresponding
+// to a single instruction.
+//----------------------------------------------------------------------------
+
+class DepGraphNode {
+  Instruction*  instr;
+  std::vector<Dependence>  inDeps;
+  std::vector<Dependence>  outDeps;
+  friend class DependenceGraph;
+  
+  typedef std::vector<Dependence>::      iterator       iterator;
+  typedef std::vector<Dependence>::const_iterator const_iterator;
+
+        iterator           inDepBegin()         { return inDeps.begin(); }
+  const_iterator           inDepBegin()   const { return inDeps.begin(); }
+        iterator           inDepEnd()           { return inDeps.end(); }
+  const_iterator           inDepEnd()     const { return inDeps.end(); }
+  
+        iterator           outDepBegin()        { return outDeps.begin(); }
+  const_iterator           outDepBegin()  const { return outDeps.begin(); }
+        iterator           outDepEnd()          { return outDeps.end(); }
+  const_iterator           outDepEnd()    const { return outDeps.end(); }
+
+public:
+
+  DepGraphNode(Instruction& I) : instr(&I) { }
+
+        Instruction&       getInstr()           { return *instr; }
+  const Instruction&       getInstr()     const { return *instr; }
+
+  /// Debugging support methods
+  /// 
+  void print(std::ostream &O) const;
+};
+
+
+//----------------------------------------------------------------------------
+// class DependenceGraph:
+// 
+// A representation of a dependence graph for a procedure.
+// The primary query operation here is to look up a DepGraphNode for
+// a particular instruction, and then use the in/out dependence iterators
+// for the node.
+//----------------------------------------------------------------------------
+
+class DependenceGraph: public NonCopyable {
+  typedef hash_map<Instruction*, DepGraphNode*> DepNodeMapType;
+  typedef DepNodeMapType::      iterator       map_iterator;
+  typedef DepNodeMapType::const_iterator const_map_iterator;
+
+  DepNodeMapType depNodeMap;
+
+  inline DepGraphNode* getNodeInternal(Instruction& inst,
+                                       bool  createIfMissing = false) {
+    map_iterator I = depNodeMap.find(&inst);
+    if (I == depNodeMap.end())
+      return (!createIfMissing)? NULL :
+        depNodeMap.insert(
+            std::make_pair(&inst, new DepGraphNode(inst))).first->second;
+    else
+      return I->second;
+  }
+
+public:
+  typedef std::vector<Dependence>::      iterator       iterator;
+  typedef std::vector<Dependence>::const_iterator const_iterator;
+
+public:
+  DependenceGraph() { }
+  ~DependenceGraph();
+
+  /// Get the graph node for an instruction.  There will be one if and
+  /// only if there are any dependences incident on this instruction.
+  /// If there is none, these methods will return NULL.
+  /// 
+  DepGraphNode* getNode(Instruction& inst, bool createIfMissing = false) {
+    return getNodeInternal(inst, createIfMissing);
+  }
+  const DepGraphNode* getNode(const Instruction& inst) const {
+    return const_cast<DependenceGraph*>(this)
+      ->getNodeInternal(const_cast<Instruction&>(inst));
+  }
+
+        iterator inDepBegin (      DepGraphNode& T)       { return T.inDeps.begin(); }
+  const_iterator inDepBegin (const DepGraphNode& T) const { return T.inDeps.begin(); }
+
+        iterator inDepEnd   (      DepGraphNode& T)       { return T.inDeps.end(); }
+  const_iterator inDepEnd   (const DepGraphNode& T) const { return T.inDeps.end(); }
+
+        iterator outDepBegin(      DepGraphNode& F)       { return F.outDeps.begin();}
+  const_iterator outDepBegin(const DepGraphNode& F) const { return F.outDeps.begin();}
+
+        iterator outDepEnd  (      DepGraphNode& F)       { return F.outDeps.end(); }
+  const_iterator outDepEnd  (const DepGraphNode& F) const { return F.outDeps.end(); }
+
+  /// Debugging support methods
+  /// 
+  void print(const Function& func, std::ostream &O) const;
+
+public:
+  /// Functions for adding and modifying the dependence graph.
+  /// These should to be used only by dependence analysis implementations.
+  void AddSimpleDependence(Instruction& fromI,
+                           Instruction& toI,
+                           DependenceType depType) {
+    DepGraphNode* fromNode = getNodeInternal(fromI, /*create*/ true);
+    DepGraphNode* toNode   = getNodeInternal(toI,   /*create*/ true);
+    fromNode->outDeps.push_back(Dependence(toNode, depType, false));
+    toNode->  inDeps. push_back(Dependence(fromNode, depType, true));
+  }
+
+#ifdef SUPPORTING_LOOP_DEPENDENCES
+  /// This interface is a placeholder to show what information is needed.
+  /// It will probably change when it starts being used.
+  void AddLoopDependence(Instruction&  fromI,
+                         Instruction&  toI,
+                         DependenceType      depType,
+                         DependenceDirection dir,
+                         DependenceDistance  distance,
+                         DependenceLevel     level,
+                         LoopInfo*           enclosingLoop);
+#endif // SUPPORTING_LOOP_DEPENDENCES
+};
+
+//===----------------------------------------------------------------------===//
+
+#endif
diff --git a/include/llvm/Analysis/MemoryDepAnalysis.h b/include/llvm/Analysis/MemoryDepAnalysis.h
new file mode 100644
index 0000000..965a2f4
--- /dev/null
+++ b/include/llvm/Analysis/MemoryDepAnalysis.h
@@ -0,0 +1,115 @@
+//===- MemoryDepAnalysis.h - Compute dep graph for memory ops ---*- C++ -*-===//
+//
+// This file provides a pass (MemoryDepAnalysis) that computes memory-based
+// data dependences between instructions for each function in a module.  
+// Memory-based dependences occur due to load and store operations, but
+// also the side-effects of call instructions.
+//
+// The result of this pass is a DependenceGraph for each function
+// representing the memory-based data dependences between instructions.
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_MEMORYDEPANALYSIS_H
+#define LLVM_ANALYSIS_MEMORYDEPANALYSIS_H
+
+#include "llvm/Analysis/DependenceGraph.h"
+#include "llvm/Analysis/IPModRef.h"
+#include "llvm/Analysis/DataStructure.h"
+#include "llvm/Pass.h"
+#include "Support/TarjanSCCIterator.h"
+#include "Support/NonCopyable.h"
+#include "Support/hash_map"
+
+
+class Instruction;
+class Function;
+class DSGraph;
+class ModRefTable;
+
+
+///---------------------------------------------------------------------------
+/// class MemoryDepGraph:
+///   Dependence analysis for load/store/call instructions using IPModRef info
+///   computed at the granularity of individual DSGraph nodes.
+///
+/// This pass computes memory dependences for each function in a module.
+/// It can be made a FunctionPass once a Pass (such as Parallelize) is
+/// allowed to use a FunctionPass such as this one.
+///---------------------------------------------------------------------------
+
+class MemoryDepAnalysis: /* Use if FunctionPass: public DependenceGraph, */
+                         public Pass {
+  /// The following map and depGraph pointer are temporary until this class
+  /// becomes a FunctionPass instead of a module Pass. */
+  hash_map<Function*, DependenceGraph*> funcMap;
+  DependenceGraph* funcDepGraph;
+
+  /// Information about one function being analyzed.
+  const DSGraph*  funcGraph;
+  const FunctionModRefInfo* funcModRef;
+
+  /// Internal routine that processes each SCC of the CFG.
+  void MemoryDepAnalysis::ProcessSCC(SCC<Function*>& S,
+                                     ModRefTable& ModRefAfter);
+
+  friend class PgmDependenceGraph;
+
+public:
+  MemoryDepAnalysis()
+    : /*DependenceGraph(),*/ funcDepGraph(NULL),
+      funcGraph(NULL), funcModRef(NULL) { }
+  ~MemoryDepAnalysis();
+
+  ///------------------------------------------------------------------------
+  /// 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);
+
+  /// getGraph() -- Retrieve the dependence graph for a function.
+  /// This is temporary and will go away once this is a FunctionPass.
+  /// At that point, this class should directly inherit from DependenceGraph.
+  /// 
+  DependenceGraph& getGraph(Function& F) {
+    hash_map<Function*, DependenceGraph*>::iterator I = funcMap.find(&F);
+    assert(I != funcMap.end());
+    return *I->second;
+  }
+  const DependenceGraph& getGraph(Function& F) const {
+    hash_map<Function*, DependenceGraph*>::const_iterator
+      I = funcMap.find(&F);
+    assert(I != funcMap.end());
+    return *I->second;
+  }
+
+  /// Release depGraphs held in the Function -> DepGraph map.
+  /// 
+  virtual void releaseMemory();
+
+  ///----END TEMPORARY FUNCTIONS---------------------------------------------
+
+
+  /// Driver functions to compute the Load/Store Dep. Graph per function.
+  /// 
+  bool runOnFunction(Function& _func);
+
+  /// getAnalysisUsage - This does not modify anything.
+  /// It uses the Top-Down DS Graph and IPModRef.
+  ///
+  void getAnalysisUsage(AnalysisUsage &AU) const {
+    AU.setPreservesAll();
+    AU.addRequired<TDDataStructures>();
+    AU.addRequired<IPModRef>();
+  }
+
+  /// Debugging support methods
+  /// 
+  void print(std::ostream &O) const;
+  void dump() const;
+};
+
+
+//===----------------------------------------------------------------------===//
+
+#endif