1 files changed, 60 insertions, 1 deletions

diff --git a/llvm/include/llvm/Analysis/DependenceGraphBuilder.h b/llvm/include/llvm/Analysis/DependenceGraphBuilder.h
index 5f4bdb47043b..08a13d967da2 100644
--- a/llvm/include/llvm/Analysis/DependenceGraphBuilder.h
+++ b/llvm/include/llvm/Analysis/DependenceGraphBuilder.h
@@ -44,7 +44,9 @@ public:
 
   /// The main entry to the graph construction algorithm. It starts by
   /// creating nodes in increasing order of granularity and then
-  /// adds def-use and memory edges.
+  /// adds def-use and memory edges. As one of the final stages, it
+  /// also creates pi-block nodes to facilitate codegen in transformations
+  /// that use dependence graphs.
   ///
   /// The algorithmic complexity of this implementation is O(V^2 * I^2), where V
   /// is the number of vertecies (nodes) and I is the number of instructions in
@@ -52,12 +54,21 @@ public:
   /// therefore the worst-case time complexity is O(N^2). The average time
   /// complexity is O((N^2)/2).
   void populate() {
+    computeInstructionOrdinals();
     createFineGrainedNodes();
     createDefUseEdges();
     createMemoryDependencyEdges();
     createAndConnectRootNode();
+    createPiBlocks();
+    sortNodesTopologically();
   }
 
+  /// Compute ordinal numbers for each instruction and store them in a map for
+  /// future look up. These ordinals are used to compute node ordinals which are
+  /// in turn used to order nodes that are part of a cycle.
+  /// Instruction ordinals are assigned based on lexical program order.
+  void computeInstructionOrdinals();
+
   /// Create fine grained nodes. These are typically atomic nodes that
   /// consist of a single instruction.
   void createFineGrainedNodes();
@@ -74,6 +85,16 @@ public:
   /// reachable from the root.
   void createAndConnectRootNode();
 
+  /// Apply graph abstraction to groups of nodes that belong to a strongly
+  /// connected component of the graph to create larger compound nodes
+  /// called pi-blocks. The purpose of this abstraction is to isolate sets of
+  /// program elements that need to stay together during codegen and turn
+  /// the dependence graph into an acyclic graph.
+  void createPiBlocks();
+
+  /// Topologically sort the graph nodes.
+  void sortNodesTopologically();
+
 protected:
   /// Create the root node of the graph.
   virtual NodeType &createRootNode() = 0;
@@ -81,6 +102,10 @@ protected:
   /// Create an atomic node in the graph given a single instruction.
   virtual NodeType &createFineGrainedNode(Instruction &I) = 0;
 
+  /// Create a pi-block node in the graph representing a group of nodes in an
+  /// SCC of the graph.
+  virtual NodeType &createPiBlock(const NodeListType &L) = 0;
+
   /// Create a def-use edge going from \p Src to \p Tgt.
   virtual EdgeType &createDefUseEdge(NodeType &Src, NodeType &Tgt) = 0;
 
@@ -90,15 +115,41 @@ protected:
   /// Create a rooted edge going from \p Src to \p Tgt .
   virtual EdgeType &createRootedEdge(NodeType &Src, NodeType &Tgt) = 0;
 
+  /// Given a pi-block node, return a vector of all the nodes contained within
+  /// it.
+  virtual const NodeListType &getNodesInPiBlock(const NodeType &N) = 0;
+
   /// Deallocate memory of edge \p E.
   virtual void destroyEdge(EdgeType &E) { delete &E; }
 
   /// Deallocate memory of node \p N.
   virtual void destroyNode(NodeType &N) { delete &N; }
 
+  /// Return true if creation of pi-blocks are supported and desired,
+  /// and false otherwise.
+  virtual bool shouldCreatePiBlocks() const { return true; }
+
+  /// Given an instruction \p I return its associated ordinal number.
+  size_t getOrdinal(Instruction &I) {
+    assert(InstOrdinalMap.find(&I) != InstOrdinalMap.end() &&
+           "No ordinal computed for this instruction.");
+    return InstOrdinalMap[&I];
+  }
+
+  /// Given a node \p N return its associated ordinal number.
+  size_t getOrdinal(NodeType &N) {
+    assert(NodeOrdinalMap.find(&N) != NodeOrdinalMap.end() &&
+           "No ordinal computed for this node.");
+    return NodeOrdinalMap[&N];
+  }
+
   /// Map types to map instructions to nodes used when populating the graph.
   using InstToNodeMap = DenseMap<Instruction *, NodeType *>;
 
+  /// Map Types to map instruction/nodes to an ordinal number.
+  using InstToOrdinalMap = DenseMap<Instruction *, size_t>;
+  using NodeToOrdinalMap = DenseMap<NodeType *, size_t>;
+
   /// Reference to the graph that gets built by a concrete implementation of
   /// this builder.
   GraphType &Graph;
@@ -112,6 +163,14 @@ protected:
 
   /// A mapping from instructions to the corresponding nodes in the graph.
   InstToNodeMap IMap;
+
+  /// A mapping from each instruction to an ordinal number. This map is used to
+  /// populate the \p NodeOrdinalMap.
+  InstToOrdinalMap InstOrdinalMap;
+
+  /// A mapping from nodes to an ordinal number. This map is used to sort nodes
+  /// in a pi-block based on program order.
+  NodeToOrdinalMap NodeOrdinalMap;
 };
 
 } // namespace llvm