1 files changed, 28 insertions, 3 deletions
diff --git a/llvm/include/llvm/Analysis/DependenceGraphBuilder.h b/llvm/include/llvm/Analysis/DependenceGraphBuilder.h
index 08a13d967da2..6f4e1be94164 100644
--- a/llvm/include/llvm/Analysis/DependenceGraphBuilder.h
+++ b/llvm/include/llvm/Analysis/DependenceGraphBuilder.h
@@ -14,13 +14,16 @@
 #ifndef LLVM_ANALYSIS_DEPENDENCE_GRAPH_BUILDER_H
 #define LLVM_ANALYSIS_DEPENDENCE_GRAPH_BUILDER_H
 
+#include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/EquivalenceClasses.h"
-#include "llvm/Analysis/DependenceAnalysis.h"
-#include "llvm/IR/BasicBlock.h"
-#include "llvm/IR/Instructions.h"
+#include "llvm/ADT/SmallVector.h"
 
 namespace llvm {
 
+class BasicBlock;
+class DependenceInfo;
+class Instruction;
+
 /// This abstract builder class defines a set of high-level steps for creating
 /// DDG-like graphs. The client code is expected to inherit from this class and
 /// define concrete implementation for each of the pure virtual functions used
@@ -58,6 +61,7 @@ public:
     createFineGrainedNodes();
     createDefUseEdges();
     createMemoryDependencyEdges();
+    simplify();
     createAndConnectRootNode();
     createPiBlocks();
     sortNodesTopologically();
@@ -92,6 +96,15 @@ public:
   /// the dependence graph into an acyclic graph.
   void createPiBlocks();
 
+  /// Go through all the nodes in the graph and collapse any two nodes
+  /// 'a' and 'b' if all of the following are true:
+  ///   - the only edge from 'a' is a def-use edge to 'b' and
+  ///   - the only edge to 'b' is a def-use edge from 'a' and
+  ///   - there is no cyclic edge from 'b' to 'a' and
+  ///   - all instructions in 'a' and 'b' belong to the same basic block and
+  ///   - both 'a' and 'b' are simple (single or multi instruction) nodes.
+  void simplify();
+
   /// Topologically sort the graph nodes.
   void sortNodesTopologically();
 
@@ -129,6 +142,18 @@ protected:
   /// and false otherwise.
   virtual bool shouldCreatePiBlocks() const { return true; }
 
+  /// Return true if graph simplification step is requested, and false
+  /// otherwise.
+  virtual bool shouldSimplify() const { return true; }
+
+  /// Return true if it's safe to merge the two nodes.
+  virtual bool areNodesMergeable(const NodeType &A,
+                                 const NodeType &B) const = 0;
+
+  /// Append the content of node \p B into node \p A and remove \p B and
+  /// the edge between \p A and \p B from the graph.
+  virtual void mergeNodes(NodeType &A, NodeType &B) = 0;
+
   /// Given an instruction \p I return its associated ordinal number.
   size_t getOrdinal(Instruction &I) {
     assert(InstOrdinalMap.find(&I) != InstOrdinalMap.end() &&