[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

2 files changed, 207 insertions, 11 deletions

diff --git a/llvm/lib/Analysis/DDG.cpp b/llvm/lib/Analysis/DDG.cpp
index b5c3c76..010b14d 100644
--- a/llvm/lib/Analysis/DDG.cpp
+++ b/llvm/lib/Analysis/DDG.cpp
@@ -13,6 +13,10 @@
 
 using namespace llvm;
 
+static cl::opt<bool>
+    CreatePiBlocks("ddg-pi-blocks", cl::init(true), cl::Hidden, cl::ZeroOrMore,
+                   cl::desc("Create pi-block nodes."));
+
 #define DEBUG_TYPE "ddg"
 
 template class llvm::DGEdge<DDGNode, DDGEdge>;
@@ -29,9 +33,16 @@ bool DDGNode::collectInstructions(
     InstructionListType &IList) const {
   assert(IList.empty() && "Expected the IList to be empty on entry.");
   if (isa<SimpleDDGNode>(this)) {
-    for (auto *I : cast<const SimpleDDGNode>(this)->getInstructions())
+    for (Instruction *I : cast<const SimpleDDGNode>(this)->getInstructions())
       if (Pred(I))
         IList.push_back(I);
+  } else if (isa<PiBlockDDGNode>(this)) {
+    for (const DDGNode *PN : cast<const PiBlockDDGNode>(this)->getNodes()) {
+      assert(!isa<PiBlockDDGNode>(PN) && "Nested PiBlocks are not supported.");
+      SmallVector<Instruction *, 8> TmpIList;
+      PN->collectInstructions(Pred, TmpIList);
+      IList.insert(IList.end(), TmpIList.begin(), TmpIList.end());
+    }
   } else
     llvm_unreachable("unimplemented type of node");
   return !IList.empty();
@@ -46,11 +57,14 @@ raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGNode::NodeKind K) {
   case DDGNode::NodeKind::MultiInstruction:
     Out = "multi-instruction";
     break;
+  case DDGNode::NodeKind::PiBlock:
+    Out = "pi-block";
+    break;
   case DDGNode::NodeKind::Root:
     Out = "root";
     break;
   case DDGNode::NodeKind::Unknown:
-    Out = "??";
+    Out = "?? (error)";
     break;
   }
   OS << Out;
@@ -61,8 +75,15 @@ raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGNode &N) {
   OS << "Node Address:" << &N << ":" << N.getKind() << "\n";
   if (isa<SimpleDDGNode>(N)) {
     OS << " Instructions:\n";
-    for (auto *I : cast<const SimpleDDGNode>(N).getInstructions())
+    for (const Instruction *I : cast<const SimpleDDGNode>(N).getInstructions())
       OS.indent(2) << *I << "\n";
+  } else if (isa<PiBlockDDGNode>(&N)) {
+    OS << "--- start of nodes in pi-block ---\n";
+    auto &Nodes = cast<const PiBlockDDGNode>(&N)->getNodes();
+    unsigned Count = 0;
+    for (const DDGNode *N : Nodes)
+      OS << *N << (++Count == Nodes.size() ? "" : "\n");
+    OS << "--- end of nodes in pi-block ---\n";
   } else if (!isa<RootDDGNode>(N))
     llvm_unreachable("unimplemented type of node");
 
@@ -99,6 +120,29 @@ SimpleDDGNode::SimpleDDGNode(SimpleDDGNode &&N)
 SimpleDDGNode::~SimpleDDGNode() { InstList.clear(); }
 
 //===--------------------------------------------------------------------===//
+// PiBlockDDGNode implementation
+//===--------------------------------------------------------------------===//
+
+PiBlockDDGNode::PiBlockDDGNode(const PiNodeList &List)
+    : DDGNode(NodeKind::PiBlock), NodeList(List) {
+  assert(!NodeList.empty() && "pi-block node constructed with an empty list.");
+}
+
+PiBlockDDGNode::PiBlockDDGNode(const PiBlockDDGNode &N)
+    : DDGNode(N), NodeList(N.NodeList) {
+  assert(getKind() == NodeKind::PiBlock && !NodeList.empty() &&
+         "constructing from invalid pi-block node.");
+}
+
+PiBlockDDGNode::PiBlockDDGNode(PiBlockDDGNode &&N)
+    : DDGNode(std::move(N)), NodeList(std::move(N.NodeList)) {
+  assert(getKind() == NodeKind::PiBlock && !NodeList.empty() &&
+         "constructing from invalid pi-block node.");
+}
+
+PiBlockDDGNode::~PiBlockDDGNode() { NodeList.clear(); }
+
+//===--------------------------------------------------------------------===//
 // DDGEdge implementation
 //===--------------------------------------------------------------------===//
 
@@ -115,7 +159,7 @@ raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGEdge::EdgeKind K) {
     Out = "rooted";
     break;
   case DDGEdge::EdgeKind::Unknown:
-    Out = "??";
+    Out = "?? (error)";
     break;
   }
   OS << Out;
@@ -164,23 +208,46 @@ bool DataDependenceGraph::addNode(DDGNode &N) {
     return false;
 
   // In general, if the root node is already created and linked, it is not safe
-  // to add new nodes since they may be unreachable by the root.
-  // TODO: Allow adding Pi-block nodes after root is created. Pi-blocks are an
-  // exception because they represent components that are already reachable by
-  // root.
-  assert(!Root && "Root node is already added. No more nodes can be added.");
+  // to add new nodes since they may be unreachable by the root. However,
+  // pi-block nodes need to be added after the root node is linked, and they are
+  // always reachable by the root, because they represent components that are
+  // already reachable by root.
+  auto *Pi = dyn_cast<PiBlockDDGNode>(&N);
+  assert(!Root || Pi && "Root node is already added. No more nodes can be added.");
+
   if (isa<RootDDGNode>(N))
     Root = &N;
 
+  if (Pi)
+    for (DDGNode *NI : Pi->getNodes())
+      PiBlockMap.insert(std::make_pair(NI, Pi));
+
   return true;
 }
 
+const PiBlockDDGNode *DataDependenceGraph::getPiBlock(const NodeType &N) const {
+  if (PiBlockMap.find(&N) == PiBlockMap.end())
+    return nullptr;
+  auto *Pi = PiBlockMap.find(&N)->second;
+  assert(PiBlockMap.find(Pi) == PiBlockMap.end() &&
+         "Nested pi-blocks detected.");
+  return Pi;
+}
+
 raw_ostream &llvm::operator<<(raw_ostream &OS, const DataDependenceGraph &G) {
-  for (auto *Node : G)
-    OS << *Node << "\n";
+  for (DDGNode *Node : G)
+    // Avoid printing nodes that are part of a pi-block twice. They will get
+    // printed when the pi-block is printed.
+    if (!G.getPiBlock(*Node))
+      OS << *Node << "\n";
+  OS << "\n";
   return OS;
 }
 
+bool DDGBuilder::shouldCreatePiBlocks() const {
+  return CreatePiBlocks;
+}
+
 //===--------------------------------------------------------------------===//
 // DDG Analysis Passes
 //===--------------------------------------------------------------------===//
diff --git a/llvm/lib/Analysis/DependenceGraphBuilder.cpp b/llvm/lib/Analysis/DependenceGraphBuilder.cpp
index ed1d835..115f5d6 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;