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(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 @@
   }
 }
 
+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;