[DDG] Data Dependence Graph - Pi Block

    Summary:
    This patch adds Pi Blocks to the DDG. A pi-block represents a group of DDG
    nodes that are part of a strongly-connected component of the graph.
    Replacing all the SCCs with pi-blocks results in an acyclic representation
    of the DDG. For example if we have:
       {a -> b}, {b -> c, d}, {c -> a}
    the cycle a -> b -> c -> a is abstracted into a pi-block "p" as follows:
       {p -> d} with "p" containing: {a -> b}, {b -> c}, {c -> a}
    In this implementation the edges between nodes that are part of the pi-block
    are preserved. The crossing edges (edges where one end of the edge is in the
    set of nodes belonging to an SCC and the other end is outside that set) are
    replaced with corresponding edges to/from the pi-block node instead.

    Authored By: bmahjour

    Reviewer: Meinersbur, fhahn, myhsu, xtian, dmgreen, kbarton, jdoerfert

    Reviewed By: Meinersbur

    Subscribers: ychen, arphaman, simoll, a.elovikov, mgorny, hiraditya, jfb, wuzish, llvm-commits, jsji, Whitney, etiotto, ppc-slack

    Tag: #llvm

    Differential Revision: https://reviews.llvm.org/D68827

1 files changed, 129 insertions, 0 deletions

diff --git a/llvm/lib/Analysis/DependenceGraphBuilder.cpp b/llvm/lib/Analysis/DependenceGraphBuilder.cpp
index ed1d8351b2f..115f5d6e814 100644
--- a/llvm/lib/Analysis/DependenceGraphBuilder.cpp
+++ b/llvm/lib/Analysis/DependenceGraphBuilder.cpp
@@ -10,6 +10,7 @@
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/DependenceGraphBuilder.h"
+#include "llvm/ADT/EnumeratedArray.h"
 #include "llvm/ADT/SCCIterator.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/DDG.h"
@@ -22,6 +23,7 @@ STATISTIC(TotalGraphs, "Number of dependence graphs created.");
 STATISTIC(TotalDefUseEdges, "Number of def-use edges created.");
 STATISTIC(TotalMemoryEdges, "Number of memory dependence edges created.");
 STATISTIC(TotalFineGrainedNodes, "Number of fine-grained nodes created.");
+STATISTIC(TotalPiBlockNodes, "Number of pi-block nodes created.");
 STATISTIC(TotalConfusedEdges,
           "Number of confused memory dependencies between two nodes.");
 STATISTIC(TotalEdgeReversals,
@@ -74,6 +76,133 @@ void AbstractDependenceGraphBuilder<G>::createAndConnectRootNode() {
   }
 }
 
+template <class G> void AbstractDependenceGraphBuilder<G>::createPiBlocks() {
+  if (!shouldCreatePiBlocks())
+    return;
+
+  LLVM_DEBUG(dbgs() << "==== Start of Creation of Pi-Blocks ===\n");
+
+  // The overall algorithm is as follows:
+  // 1. Identify SCCs and for each SCC create a pi-block node containing all
+  //    the nodes in that SCC.
+  // 2. Identify incoming edges incident to the nodes inside of the SCC and
+  //    reconnect them to the pi-block node.
+  // 3. Identify outgoing edges from the nodes inside of the SCC to nodes
+  //    outside of it and reconnect them so that the edges are coming out of the
+  //    SCC node instead.
+
+  // Adding nodes as we iterate through the SCCs cause the SCC
+  // iterators to get invalidated. To prevent this invalidation, we first
+  // collect a list of nodes that are part of an SCC, and then iterate over
+  // those lists to create the pi-block nodes. Each element of the list is a
+  // list of nodes in an SCC. Note: trivial SCCs containing a single node are
+  // ignored.
+  SmallVector<NodeListType, 4> ListOfSCCs;
+  for (auto &SCC : make_range(scc_begin(&Graph), scc_end(&Graph))) {
+    if (SCC.size() > 1)
+      ListOfSCCs.emplace_back(SCC.begin(), SCC.end());
+  }
+
+  for (NodeListType &NL : ListOfSCCs) {
+    LLVM_DEBUG(dbgs() << "Creating pi-block node with " << NL.size()
+                      << " nodes in it.\n");
+
+    NodeType &PiNode = createPiBlock(NL);
+    ++TotalPiBlockNodes;
+
+    // Build a set to speed up the lookup for edges whose targets
+    // are inside the SCC.
+    SmallPtrSet<NodeType *, 4> NodesInSCC(NL.begin(), NL.end());
+
+    // We have the set of nodes in the SCC. We go through the set of nodes
+    // that are outside of the SCC and look for edges that cross the two sets.
+    for (NodeType *N : Graph) {
+
+      // Skip the SCC node and all the nodes inside of it.
+      if (*N == PiNode || NodesInSCC.count(N))
+        continue;
+
+      for (NodeType *SCCNode : NL) {
+
+        enum Direction {
+          Incoming,      // Incoming edges to the SCC
+          Outgoing,      // Edges going ot of the SCC
+          DirectionCount // To make the enum usable as an array index.
+        };
+
+        // Use these flags to help us avoid creating redundant edges. If there
+        // are more than one edges from an outside node to inside nodes, we only
+        // keep one edge from that node to the pi-block node. Similarly, if
+        // there are more than one edges from inside nodes to an outside node,
+        // we only keep one edge from the pi-block node to the outside node.
+        // There is a flag defined for each direction (incoming vs outgoing) and
+        // for each type of edge supported, using a two-dimensional boolean
+        // array.
+        using EdgeKind = typename EdgeType::EdgeKind;
+        EnumeratedArray<bool, EdgeKind> EdgeAlreadyCreated[DirectionCount]{
+            false, false};
+
+        auto createEdgeOfKind = [this](NodeType &Src, NodeType &Dst,
+                                       const EdgeKind K) {
+          switch (K) {
+          case EdgeKind::RegisterDefUse:
+            createDefUseEdge(Src, Dst);
+            break;
+          case EdgeKind::MemoryDependence:
+            createMemoryEdge(Src, Dst);
+            break;
+          case EdgeKind::Rooted:
+            createRootedEdge(Src, Dst);
+            break;
+          default:
+            llvm_unreachable("Unsupported type of edge.");
+          }
+        };
+
+        auto reconnectEdges = [&](NodeType *Src, NodeType *Dst, NodeType *New,
+                                  const Direction Dir) {
+          if (!Src->hasEdgeTo(*Dst))
+            return;
+          LLVM_DEBUG(dbgs()
+                     << "reconnecting("
+                     << (Dir == Direction::Incoming ? "incoming)" : "outgoing)")
+                     << ":\nSrc:" << *Src << "\nDst:" << *Dst
+                     << "\nNew:" << *New << "\n");
+          assert((Dir == Direction::Incoming || Dir == Direction::Outgoing) &&
+                 "Invalid direction.");
+
+          SmallVector<EdgeType *, 10> EL;
+          Src->findEdgesTo(*Dst, EL);
+          for (EdgeType *OldEdge : EL) {
+            EdgeKind Kind = OldEdge->getKind();
+            if (!EdgeAlreadyCreated[Dir][Kind]) {
+              if (Dir == Direction::Incoming) {
+                createEdgeOfKind(*Src, *New, Kind);
+                LLVM_DEBUG(dbgs() << "created edge from Src to New.\n");
+              } else if (Dir == Direction::Outgoing) {
+                createEdgeOfKind(*New, *Dst, Kind);
+                LLVM_DEBUG(dbgs() << "created edge from New to Dst.\n");
+              }
+              EdgeAlreadyCreated[Dir][Kind] = true;
+            }
+            Src->removeEdge(*OldEdge);
+            destroyEdge(*OldEdge);
+            LLVM_DEBUG(dbgs() << "removed old edge between Src and Dst.\n\n");
+          }
+        };
+
+        // Process incoming edges incident to the pi-block node.
+        reconnectEdges(N, SCCNode, &PiNode, Direction::Incoming);
+
+        // Process edges that are coming out of the pi-block node.
+        reconnectEdges(SCCNode, N, &PiNode, Direction::Outgoing);
+      }
+    }
+  }
+
+  LLVM_DEBUG(dbgs() << "==== End of Creation of Pi-Blocks ===\n");
+}
+
 template <class G> void AbstractDependenceGraphBuilder<G>::createDefUseEdges() {
   for (NodeType *N : Graph) {
     InstructionListType SrcIList;