[DDG] Data Dependence Graph - Pi Block

[bmahjour]

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.

[etiotto]

llvm/include/llvm/Analysis/DependenceGraphBuilder.h

115

When would be not desired to create pi-blocks? Is this member function really at this point?

llvm/lib/Analysis/DDG.cpp

16

Is probably overkill to have an option to disable the creation of pi-blocks. At least at this point. Less is more :-)

215

This makes me think what happens when a node that is part of a pi-block is removed from the graph (via DirectedGraph::removeNode). We should update the PiBlockMap in that case to reflect that the node no longer exists in the graph.

[bmahjour]

llvm/include/llvm/Analysis/DependenceGraphBuilder.h

115

I added this API to allow client code to control creation of pi-blocks for debugging and experimentation purposes. Furthermore since the graph builder is meant to be more generic than just a DDG builder, having the option to control certain steps of the graph build may be useful in future, for example when we use it to create PDG or other types of dependence graphs where certain steps do not apply.

llvm/lib/Analysis/DDG.cpp

215

There is more to be considered than the map if nodes are being removed from pi-blocks. Removing a node from the pi-block may actually remove the cycle or change the SCC, but I cannot think of a practical scenario where doing so would be necessary. Do you have a practical scenario in mind?

[Meinersbur]

createPiBlocks should not handle every case with its own boilerplate code.

llvm/lib/Analysis/DDG.cpp

40

[style] Unless the type is too complex, try to avoid auto.

84

[style] Unless the type is too complex, try to avoid auto.

222

[style] Unless the type is too complex, try to avoid auto.

237–238

[style] Unless the type is too complex, try to avoid auto.

llvm/lib/Analysis/DependenceGraphBuilder.cpp

103

[suggestion] Use ListsOfSCCs.emplace_back?

106

[style] Unless the type is too complex, try to avoid auto.

110

[style] Unless the type is too complex, try to avoid auto.

125

[style] Unless the type is too complex, please try to avoid auto.

141

[serious] Should use DDGEdge::EdgeKind

159

[style] Unless the type is too complex, please try to avoid auto.

160

AFAICS, OldEdge is already of type EdgeType*, i.e. the static_cast is unnecessary.

160

[serious] Isn't there a way to simplify this chain of ifs? Such as

Kind = OldEdge->getKind();
bool &AlreadyCreated = EdgeAlreadyCreated[Dir][Kind];
if (!AlreadyCreated) 
  createEdgeOfKind(*Src, *New, Kind);
  AlreadyCreated = true;

[bmahjour]

Addressed all comments.

llvm/lib/Analysis/DDG.cpp

16

See reply above.

llvm/lib/Analysis/DependenceGraphBuilder.cpp

141

The reason I introduced a local enum in this implementation without exposing it to other parts is two fold:

1. In order to avoid type casting the enum to an integral type that can be used as an index into the boolean array, the enum used here should be an unscoped enum. The DDGEdge::EdgeKind enum is a scoped enum and it should stay that way.
2. This builder is supposed to build other types of graphs too, so it's better not to rely on the implementation specifics of one graph (DDG) to build other types of graphs (such as PDG). For example, while the def-use, memory and rooted edges are common concepts between DDG and PDG, the edge names, number of edge kinds or their orderings might be different.

[Meinersbur]

I am still unconvinced over the boilerplate createPiBlocks.

This method of de-duplication of edges assumes that edges are only defined by its kind. Is it correct that no additional properties, such as which definition of a value caused a UseDef dependency, are planned?

llvm/lib/Analysis/DependenceGraphBuilder.cpp

141

1. In order to avoid type casting the enum to an integral type that can be used as an index into the boolean array, the enum used here should be an unscoped enum. The DDGEdge::EdgeKind enum is a scoped enum and it should stay that way.

It also means we have to maintain a mapping between the two enums which are basically identical. I'd prefer the cast over this.

One can abstract away the the type-casting into a type-safe class, such as proposed here:
https://stackoverflow.com/questions/12927951/array-indexing-converting-to-integer-with-scoped-enumeration#answer-35186573

2. This builder is supposed to build other types of graphs too, so it's better not to rely on the implementation specifics of one graph (DDG) to build other types of graphs (such as PDG). For example, while the def-use, memory and rooted edges are common concepts between DDG and PDG, the edge names, number of edge kinds or their orderings might be different.

I cannot follow this argument. createPiBlocks() as-is relies on knowing all types of edges since there is no abstraction. When introducing a new type of edge, it will hit llvm_unreachable("Unsupported edge kind"). It also cannot create edges of arbitrary kind since it needs to call a createXYZEdge method. If you add a kind of edge to PDG only, it will need to call a createABCEdge method, which, if not also added to the DDG, will make the AbstractDependenceGraphBuilder uninstantiable for the DDG.

If the abstraction of node kind is important, I suggest to add a way to create edges without knowing its type, such as a clone() method on edges or promoting createEdgeOfKind to become a method of the graph builder such that subclasses can implement custom factories for their edges.

[bmahjour]

In D68827#1726300, @Meinersbur wrote:

I am still unconvinced over the boilerplate createPiBlocks.

I'm not sure what you mean by "boilerplate". Is it in reference to your concern about de-duplication of edges based on their kinds? If not, could you please elaborate?

This method of de-duplication of edges assumes that edges are only defined by its kind. Is it correct that no additional properties, such as which definition of a value caused a UseDef dependency, are planned?

Yes, this abstraction loses information about the specific origin of edges coming from inside nodes (members of a pi-block) and the specific target of edges coming from outside nodes. The idea is that since members of a pi-block are bound together by their tight dependence relationship, there is less value in maintaining the coordinates of their relationship with respect to nodes outside of the pi-block. For example, suppose instruction A and B are part of a pi-block (P) and instruction C has a flow dependence with both A and B. For the purpose of instruction ordering, C will come before (P) by the virtue of a single edge from C to that pi-block. At this point the fact that both A and B are connected to C is irrelevant/redundant.
There are cases however, where the nature of the dependence relationship is important, for example when determining if a fusion-preventing edge exists between two loops. In such cases the existence of a particular dependence relationship needs to be recomputed, however the specifics of the origin or target of that dependence is not useful. In subsequent patches I'm going to add a function getDependencies() to the DDG where given two nodes (they could be pi-blocks) it walks through their instructions and returns a vector of all the possible dependence relationships between those two nodes.

Please also note that one of the primary goals of creating pi-blocks is to turn the graph into an DAG. If we maintain edges to individual nodes of a pi-block, the cycles in the pi-blocks become exposed again and the purpose of abstraction is defeated.

If the need arises in the future to obtain the lost information, it could be dealt with by

1. recomputing the dependencies between subject nodes
2. maintaining a side table in the builder and/or DDG
3. keeping the original edges and somehow dealing with the DAG issue (not sure if possible).
4. introducing an aggregate edge that keeps track of its origins and targets.

Each approach would have its own challenges of course, but (3) is the only one that would be harder to do in the future if we continue with the proposed implementation.

Do you have a common use-case in mind where it would be important to know exactly which nodes within a pi-block have relationships with nodes that are outside?

[bmahjour]

llvm/lib/Analysis/DependenceGraphBuilder.cpp

141

I think I understand your concern now. I like the idea of a custom factory for creating all types of edges that the client cares about without making the builder know about those edges, however I think a default implementation that only handles DefUse, Memory and Rooted edges would be useful. Do you agree?
I'll work on it and upload a patch soon.

[Meinersbur]

In D68827#1728672, @bmahjour wrote:

I'm not sure what you mean by "boilerplate". Is it in reference to your concern about de-duplication of edges based on their kinds? If not, could you please elaborate?

This was to clarify my reason to not accept this patch yet.

Do you have a common use-case in mind where it would be important to know exactly which nodes within a pi-block have relationships with nodes that are outside?

In Polly, the question about what caused a dependency comes up regularly (https://github.com/llvm/llvm-project/blob/master/polly/include/polly/DependenceInfo.h#L40). A use case is to privatize the memory causing a false dependency.

Just asking what is being considered for the future.

llvm/lib/Analysis/DependenceGraphBuilder.cpp

141

If this is just an implementation that have these three kinds of edges, there is even less of a reason to not use the EdgeKind that comes with it.

Do you think of a use case where there is an dependence graph with an EdgeKind that is never used (at least not before createPiBlocks?). The worst that happens here is you have unused elements in EdgeAlreadyCreated.

I generally don't like complicating things before the extra complexity becomes necessary.

[bmahjour]

llvm/lib/Analysis/DependenceGraphBuilder.cpp

141

The worst that happens here is you have unused elements in EdgeAlreadyCreated.

Unused elements can happen too, but the worst that can happen is edge kinds getting misinterpreted because they don't end up with the same enumeration value. eg:

class DDGEdge : public DDGEdgeBase {
public:
  enum class EdgeKind { Unknown, RegisterDefUse, MemoryDependence, Rooted };
...
};

class PDGEdge : public PDGEdgeBase {
public:
  enum class EdgeKind { Unknown, MemoryDependence, RegisterDefUse, Control, Rooted };
...
};

[Meinersbur]

llvm/lib/Analysis/DependenceGraphBuilder.cpp

141

Within AbstractDependenceGraphBuilder<GraphType>::createPiBlocks, only one EdgeType = typename GraphType::EdgeType would ever be valid.

Do you foresee functions using DDG and PDG nodes/edges at the same time? Even if so, mixing scoped enum values of different type is an error, except when casted to get an array index, which use case can be made type safe with EnumeratedArray. I think EnumeratedArray would be a great addition to ADT.

[bmahjour]

Created EnumeratedArray ADT (with unit tests), added Count to the edge enums and changed EdgeAlreadyCreated matrix to use EnumeratedArray.

[Meinersbur]

llvm/include/llvm/ADT/EnumeratedArray.h

22

Thanks a lot!

Could we change Enumeration::Count to Enumaration::Last? The reason is that ::Count introduces a new element that compilers warn about if unhanded in switch statements. That is, instead of

enum class E {
  One,
  Two,
  Count
};

switch (e) {
case E::One:
case E::Two:
  break;
}

warning: enumerator 'E::Count' in switch of enum 'E' is not handled

use

enum class E {
  One,
  Two,
  Last = Two
};

switch (e) {
case E::One:
case E::Two:
  break;
}

[bmahjour]

Changed the enum array to use "Last" instead of "Count"

llvm/include/llvm/ADT/EnumeratedArray.h

22

Sure, will do.

llvm/lib/Analysis/DependenceGraphBuilder.cpp

141

Ok, I've added EnumeratedArray and changed EdgesAlreadyCreated to use it.

[Meinersbur]

LGTM

llvm/include/llvm/ADT/EnumeratedArray.h

22

@jdoerfert made me aware of the existence of IndexedMap. In contrast to EnumeratedArray it uses a SmallVector as storage (but 0 inline-storage), so I think EnumeratedArray has its own use-case.

llvm/include/llvm/ADT/EnumeratedArray.h

+//===- llvm/ADT/EnumeratedArray.h - Enumerated Array-------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines an array type that can be indexed using scoped enum values.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ADT_ENUMERATEDARRAY_H
+#define LLVM_ADT_ENUMERATEDARRAY_H
+
+#include <cassert>
+
+namespace llvm {
+
+template <typename ValueType, typename Enumeration,
+          Enumeration LargestEnum = Enumeration::Last, typename IndexType = int,
+          IndexType Size = 1 + static_cast<IndexType>(LargestEnum)>
+class EnumeratedArray {
+public:
+  EnumeratedArray() = default;
+  EnumeratedArray(ValueType V) {
+    for (IndexType IX = 0; IX < Size; ++IX) {
+      Underlying[IX] = V;
+    }
+  }
+  inline const ValueType &operator[](const Enumeration Index) const {
+    auto IX = static_cast<const IndexType>(Index);
+    assert(IX >= 0 && IX < Size && "Index is out of bounds.");
+    return Underlying[IX];
+  }
+  inline ValueType &operator[](const Enumeration Index) {
+    return const_cast<ValueType &>(
+        static_cast<const EnumeratedArray<ValueType, Enumeration, LargestEnum,
+                                          IndexType, Size> &>(*this)[Index]);
+  }
+
+private:
+  ValueType Underlying[Size];
+};
+
+} // namespace llvm
+
+#endif // LLVM_ADT_ENUMERATEDARRAY_H

llvm/include/llvm/Analysis/DDG.h

 //===- llvm/Analysis/DDG.h --------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file defines the Data-Dependence Graph (DDG).
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_DDG_H
 #define LLVM_ANALYSIS_DDG_H
 
+#include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DirectedGraph.h"
 #include "llvm/Analysis/DependenceAnalysis.h"
 #include "llvm/Analysis/DependenceGraphBuilder.h"
 #include "llvm/Analysis/LoopAnalysisManager.h"
 #include "llvm/IR/Instructions.h"
-#include <unordered_map>
 
 namespace llvm {
 class DDGNode;
 class DDGEdge;
 using DDGNodeBase = DGNode<DDGNode, DDGEdge>;
 using DDGEdgeBase = DGEdge<DDGNode, DDGEdge>;
 using DDGBase = DirectedGraph<DDGNode, DDGEdge>;
 class LPMUpdater;
 
 /// Data Dependence Graph Node
 /// The graph can represent the following types of nodes:
 /// 1. Single instruction node containing just one instruction.
 /// 2. Multiple instruction node where two or more instructions from
 ///    the same basic block are merged into one node.
-/// 3. Root node is a special node that connects to all components such that
+/// 3. Pi-block node which is a group of other DDG nodes that are part of a
+///    strongly-connected component of the graph.
+///    A pi-block node contains more than one single or multiple instruction
+///    nodes. The root node cannot be part of a pi-block.
+/// 4. Root node is a special node that connects to all components such that
 ///    there is always a path from it to any node in the graph.
 class DDGNode : public DDGNodeBase {
 public:
   using InstructionListType = SmallVectorImpl<Instruction *>;
 
   enum class NodeKind {
     Unknown,
     SingleInstruction,
     MultiInstruction,
+    PiBlock,
     Root,
   };
 
   DDGNode() = delete;
   DDGNode(const NodeKind K) : DDGNodeBase(), Kind(K) {}
   DDGNode(const DDGNode &N) : DDGNodeBase(N), Kind(N.Kind) {}
   DDGNode(DDGNode &&N) : DDGNodeBase(std::move(N)), Kind(N.Kind) {}
   virtual ~DDGNode() = 0;
private:
   void appendInstructions(const SimpleDDGNode &Input) {
     appendInstructions(Input.getInstructions());
   }
 
   /// List of instructions associated with a single or multi-instruction node.
   SmallVector<Instruction *, 2> InstList;
 };
 
+/// Subclass of DDGNode representing a pi-block. 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}
+class PiBlockDDGNode : public DDGNode {
+public:
+  using PiNodeList = SmallVector<DDGNode *, 4>;
+
+  PiBlockDDGNode() = delete;
+  PiBlockDDGNode(const PiNodeList &List);
+  PiBlockDDGNode(const PiBlockDDGNode &N);
+  PiBlockDDGNode(PiBlockDDGNode &&N);
+  ~PiBlockDDGNode();
+
+  PiBlockDDGNode &operator=(const PiBlockDDGNode &N) {
+    DDGNode::operator=(N);
+    NodeList = N.NodeList;
+    return *this;
+  }
+
+  PiBlockDDGNode &operator=(PiBlockDDGNode &&N) {
+    DDGNode::operator=(std::move(N));
+    NodeList = std::move(N.NodeList);
+    return *this;
+  }
+
+  /// Get the list of nodes in this pi-block.
+  const PiNodeList &getNodes() const {
+    assert(!NodeList.empty() && "Node list is empty.");
+    return NodeList;
+  }
+  PiNodeList &getNodes() {
+    return const_cast<PiNodeList &>(
+        static_cast<const PiBlockDDGNode *>(this)->getNodes());
+  }
+
+  /// Define classof to be able to use isa<>, cast<>, dyn_cast<>, etc.
+  static bool classof(const DDGNode *N) {
+    return N->getKind() == NodeKind::PiBlock;
+  }
+
+private:
+  /// List of nodes in this pi-block.
+  PiNodeList NodeList;
+};
+
 /// Data Dependency Graph Edge.
 /// An edge in the DDG can represent a def-use relationship or
 /// a memory dependence based on the result of DependenceAnalysis.
 /// A rooted edge connects the root node to one of the components
 /// of the graph.
 class DDGEdge : public DDGEdgeBase {
 public:
   /// The kind of edge in the DDG
-  enum class EdgeKind { Unknown, RegisterDefUse, MemoryDependence, Rooted };
+  enum class EdgeKind {
+    Unknown,
+    RegisterDefUse,
+    MemoryDependence,
+    Rooted,
+    Last = Rooted // Must be equal to the largest enum value.
+  };
 
   explicit DDGEdge(DDGNode &N) = delete;
   DDGEdge(DDGNode &N, EdgeKind K) : DDGEdgeBase(N), Kind(K) {}
   DDGEdge(const DDGEdge &E) : DDGEdgeBase(E), Kind(E.getKind()) {}
   DDGEdge(DDGEdge &&E) : DDGEdgeBase(std::move(E)), Kind(E.Kind) {}
   DDGEdge &operator=(const DDGEdge &E) {
     DDGEdgeBase::operator=(E);
     Kind = E.Kind;
public:
   DataDependenceGraph() = delete;
   DataDependenceGraph(const DataDependenceGraph &G) = delete;
   DataDependenceGraph(DataDependenceGraph &&G)
       : DDGBase(std::move(G)), DDGInfo(std::move(G)) {}
   DataDependenceGraph(Function &F, DependenceInfo &DI);
   DataDependenceGraph(const Loop &L, DependenceInfo &DI);
   ~DataDependenceGraph();
 
+  /// If node \p N belongs to a pi-block return a pointer to the pi-block,
+  /// otherwise return null.
+  const PiBlockDDGNode *getPiBlock(const NodeType &N) const;
+
 protected:
-  /// Add node \p N to the graph, if it's not added yet, and keep track of
-  /// the root node. Return true if node is successfully added.
+  /// Add node \p N to the graph, if it's not added yet, and keep track of the
+  /// root node as well as pi-blocks and their members. Return true if node is
+  /// successfully added.
   bool addNode(NodeType &N);
 
+private:
+  using PiBlockMapType = DenseMap<const NodeType *, const PiBlockDDGNode *>;
+
+  /// Mapping from graph nodes to their containing pi-blocks. If a node is not
+  /// part of a pi-block, it will not appear in this map.
+  PiBlockMapType PiBlockMap;
 };
 
 /// Concrete implementation of a pure data dependence graph builder. This class
 /// provides custom implementation for the pure-virtual functions used in the
 /// generic dependence graph build algorithm.
 ///
 /// For information about time complexity of the build algorithm see the
 /// comments near the declaration of AbstractDependenceGraphBuilder.
DDGNode &createRootNode() final override {
     return *RN;
   }
   DDGNode &createFineGrainedNode(Instruction &I) final override {
     auto *SN = new SimpleDDGNode(I);
     assert(SN && "Failed to allocate memory for simple DDG node.");
     Graph.addNode(*SN);
     return *SN;
   }
+  DDGNode &createPiBlock(const NodeListType &L) final override {
+    auto *Pi = new PiBlockDDGNode(L);
+    assert(Pi && "Failed to allocate memory for pi-block node.");
+    Graph.addNode(*Pi);
+    return *Pi;
+  }
   DDGEdge &createDefUseEdge(DDGNode &Src, DDGNode &Tgt) final override {
     auto *E = new DDGEdge(Tgt, DDGEdge::EdgeKind::RegisterDefUse);
     assert(E && "Failed to allocate memory for edge");
     Graph.connect(Src, Tgt, *E);
     return *E;
   }
   DDGEdge &createMemoryEdge(DDGNode &Src, DDGNode &Tgt) final override {
     auto *E = new DDGEdge(Tgt, DDGEdge::EdgeKind::MemoryDependence);
     assert(E && "Failed to allocate memory for edge");
     Graph.connect(Src, Tgt, *E);
     return *E;
   }
   DDGEdge &createRootedEdge(DDGNode &Src, DDGNode &Tgt) final override {
     auto *E = new DDGEdge(Tgt, DDGEdge::EdgeKind::Rooted);
     assert(E && "Failed to allocate memory for edge");
     assert(isa<RootDDGNode>(Src) && "Expected root node");
     Graph.connect(Src, Tgt, *E);
     return *E;
   }
 
+  bool shouldCreatePiBlocks() const final override;
 };
 
 raw_ostream &operator<<(raw_ostream &OS, const DDGNode &N);
 raw_ostream &operator<<(raw_ostream &OS, const DDGNode::NodeKind K);
 raw_ostream &operator<<(raw_ostream &OS, const DDGEdge &E);
 raw_ostream &operator<<(raw_ostream &OS, const DDGEdge::EdgeKind K);
 raw_ostream &operator<<(raw_ostream &OS, const DataDependenceGraph &G);
 

llvm/include/llvm/Analysis/DependenceGraphBuilder.h

public:
 
   AbstractDependenceGraphBuilder(GraphType &G, DependenceInfo &D,
                                  const BasicBlockListType &BBs)
       : Graph(G), DI(D), BBList(BBs) {}
   virtual ~AbstractDependenceGraphBuilder() {}
 
   /// 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
   /// each node. The total number of instructions, N, is equal to V * I,
   /// therefore the worst-case time complexity is O(N^2). The average time
   /// complexity is O((N^2)/2).
   void populate() {
     createFineGrainedNodes();
     createDefUseEdges();
     createMemoryDependencyEdges();
     createAndConnectRootNode();
+    createPiBlocks();
   }
 
   /// Create fine grained nodes. These are typically atomic nodes that
   /// consist of a single instruction.
   void createFineGrainedNodes();
 
   /// Analyze the def-use chains and create edges from the nodes containing
   /// definitions to the nodes containing the uses.
   void createDefUseEdges();
 
   /// Analyze data dependencies that exist between memory loads or stores,
   /// in the graph nodes and create edges between them.
   void createMemoryDependencyEdges();
 
   /// Create a root node and add edges such that each node in the graph is
   /// 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();
+
 protected:
   /// Create the root node of the graph.
   virtual NodeType &createRootNode() = 0;
 
   /// 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;
 
   /// Create a memory dependence edge going from \p Src to \p Tgt.
   virtual EdgeType &createMemoryEdge(NodeType &Src, NodeType &Tgt) = 0;
 
   /// Create a rooted edge going from \p Src to \p Tgt .
   virtual EdgeType &createRootedEdge(NodeType &Src, NodeType &Tgt) = 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; }
+
   /// Map types to map instructions to nodes used when populating the graph.
   using InstToNodeMap = DenseMap<Instruction *, NodeType *>;
 
   /// Reference to the graph that gets built by a concrete implementation of
   /// this builder.
   GraphType &Graph;
 
   /// Dependence information used to create memory dependence edges in the

llvm/lib/Analysis/DDG.cpp

 //===- DDG.cpp - Data Dependence Graph -------------------------------------==//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // The implementation for the data dependence graph.
 //===----------------------------------------------------------------------===//
 #include "llvm/Analysis/DDG.h"
 #include "llvm/Analysis/LoopInfo.h"
 
 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>;
 template class llvm::DGNode<DDGNode, DDGEdge>;
 template class llvm::DirectedGraph<DDGNode, DDGEdge>;
 
 //===--------------------------------------------------------------------===//
 // DDGNode implementation
 //===--------------------------------------------------------------------===//
 DDGNode::~DDGNode() {}
 
 bool DDGNode::collectInstructions(
     llvm::function_ref<bool(Instruction *)> const &Pred,
     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();
 }
 
 raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGNode::NodeKind K) {
   const char *Out;
   switch (K) {
   case DDGNode::NodeKind::SingleInstruction:
     Out = "single-instruction";
     break;
   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;
   return OS;
 }
 
 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");
 
   OS << (N.getEdges().empty() ? " Edges:none!\n" : " Edges:\n");
   for (auto &E : N.getEdges())
     OS.indent(2) << *E;
   return OS;
 }
SimpleDDGNode::SimpleDDGNode(SimpleDDGNode &&N)
   assert(((getKind() == NodeKind::SingleInstruction && InstList.size() == 1) ||
           (getKind() == NodeKind::MultiInstruction && InstList.size() > 1)) &&
          "constructing from invalid simple node.");
 }
 
 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
 //===--------------------------------------------------------------------===//
 
 raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGEdge::EdgeKind K) {
   const char *Out;
   switch (K) {
   case DDGEdge::EdgeKind::RegisterDefUse:
     Out = "def-use";
     break;
   case DDGEdge::EdgeKind::MemoryDependence:
     Out = "memory";
     break;
   case DDGEdge::EdgeKind::Rooted:
     Out = "rooted";
     break;
   case DDGEdge::EdgeKind::Unknown:
-    Out = "??";
+    Out = "?? (error)";
     break;
   }
   OS << Out;
   return OS;
 }
 
 raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGEdge &E) {
   OS << "[" << E.getKind() << "] to " << &E.getTargetNode() << "\n";
DataDependenceGraph::~DataDependenceGraph() {
   }
 }
 
 bool DataDependenceGraph::addNode(DDGNode &N) {
   if (!DDGBase::addNode(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)
+  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
 //===--------------------------------------------------------------------===//
 
 /// DDG as a loop pass.
 DDGAnalysis::Result DDGAnalysis::run(Loop &L, LoopAnalysisManager &AM,
                                      LoopStandardAnalysisResults &AR) {
   Function *F = L.getHeader()->getParent();

llvm/lib/Analysis/DependenceGraphBuilder.cpp

 //===- DependenceGraphBuilder.cpp ------------------------------------------==//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 // This file implements common steps of the build algorithm for construction
 // of dependence graphs such as DDG and PDG.
 //===----------------------------------------------------------------------===//
 
 #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"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "dgb"
 
 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,
           "Number of times the source and sink of dependence was reversed to "
           "expose cycles in the graph.");
 
 using InstructionListType = SmallVector<Instruction *, 2>;
 
for (auto *N : Graph) {
     if (*N == RootNode)
       continue;
     for (auto I : depth_first_ext(N, Visited))
       if (I == N)
         createRootedEdge(RootNode, *N);
   }
 }
 
+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;
     N->collectInstructions([](const Instruction *I) { return true; }, SrcIList);
 
     // Use a set to mark the targets that we link to N, so we don't add
     // duplicate def-use edges when more than one instruction in a target node
     // use results of instructions that are contained in N.

llvm/test/Analysis/DDG/basic-a.ll

 ; RUN: opt < %s -disable-output "-passes=print<ddg>" 2>&1 | FileCheck %s
 
 ; CHECK-LABEL: 'DDG' for loop 'test1.for.body':
 ; CHECK: Node Address:[[N1:0x[0-9a-f]*]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %i.02 = phi i64 [ %inc, %test1.for.body ], [ 0, %test1.for.body.preheader ]
-; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N2:0x[0-9a-f]*]]
-; CHECK-NEXT:  [def-use] to [[N3:0x[0-9a-f]*]]
-; CHECK-NEXT:  [def-use] to [[N4:0x[0-9a-f]*]]
-
-; CHECK: Node Address:[[N4]]:single-instruction
-; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %arrayidx = getelementptr inbounds float, float* %b, i64 %i.02
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N5:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N2:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N5]]:single-instruction
+; CHECK: Node Address:[[N2]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %0 = load float, float* %arrayidx, align 4
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N6:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N3:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N7:0x[0-9a-f]*]]:single-instruction
+; CHECK: Node Address:[[N4:0x[0-9a-f]*]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %conv = uitofp i64 %n to float
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N6]]
+; CHECK-NEXT:  [def-use] to [[N3]]
 
-; CHECK: Node Address:[[N6]]:single-instruction
+; CHECK: Node Address:[[N3]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %add = fadd float %0, %conv
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N8:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N5:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N3]]:single-instruction
+; CHECK: Node Address:[[N6:0x[0-9a-f]*]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %arrayidx1 = getelementptr inbounds float, float* %a, i64 %i.02
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N8]]
+; CHECK-NEXT:  [def-use] to [[N5]]
 
-; CHECK: Node Address:[[N8]]:single-instruction
+; CHECK: Node Address:[[N5]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    store float %add, float* %arrayidx1, align 4
 ; CHECK-NEXT: Edges:none!
 
-; CHECK: Node Address:[[N2]]:single-instruction
-; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %inc = add i64 %i.02, 1
-; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N9:0x[0-9a-f]*]]
-; CHECK-NEXT:  [def-use] to [[N1]]
-
-; CHECK: Node Address:[[N9]]:single-instruction
+; CHECK: Node Address:[[N7:0x[0-9a-f]*]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %exitcond = icmp ne i64 %inc, %n
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N10:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N8:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N10]]:single-instruction
+; CHECK: Node Address:[[N8]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    br i1 %exitcond, label %test1.for.body, label %for.end.loopexit
 ; CHECK-NEXT: Edges:none!
 
+; CHECK: Node Address:[[N9:0x[0-9a-f]*]]:pi-block
+; CHECK-NEXT: --- start of nodes in pi-block ---
+; CHECK-NEXT: Node Address:[[N10:0x[0-9a-f]*]]:single-instruction
+; CHECK-NEXT: Instructions:
+; CHECK-NEXT:    %inc = add i64 %i.02, 1
+; CHECK-NEXT: Edges:
+; CHECK-NEXT:  [def-use] to [[N11:0x[0-9a-f]*]]
+
+; CHECK: Node Address:[[N11]]:single-instruction
+; CHECK-NEXT: Instructions:
+; CHECK-NEXT:    %i.02 = phi i64 [ %inc, %test1.for.body ], [ 0, %test1.for.body.preheader ]
+; CHECK-NEXT: Edges:
+; CHECK-NEXT:  [def-use] to [[N10]]
+; CHECK-NEXT: --- end of nodes in pi-block ---
+; CHECK-NEXT: Edges:
+; CHECK-NEXT:  [def-use] to [[N1]]
+; CHECK-NEXT:  [def-use] to [[N6]]
+; CHECK-NEXT:  [def-use] to [[N7]]
+
+
 ;; No memory dependencies.
 ;; void test1(unsigned long n, float * restrict a, float * restrict b) {
 ;;  for (unsigned long i = 0; i < n; i++)
 ;;    a[i] = b[i] + n;
 ;; }
 
 define void @test1(i64 %n, float* noalias %a, float* noalias %b) {
 entry:

 for.end:                                          ; preds = %test1.for.body, %entry
   ret void
 }
 
 
 ; CHECK-LABEL: 'DDG' for loop 'test2.for.body':
 ; CHECK: Node Address:[[N1:0x[0-9a-f]*]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %i.02 = phi i64 [ %inc, %test2.for.body ], [ 0, %test2.for.body.preheader ]
-; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N2:0x[0-9a-f]*]]
-; CHECK-NEXT:  [def-use] to [[N3:0x[0-9a-f]*]]
-; CHECK-NEXT:  [def-use] to [[N4:0x[0-9a-f]*]]
-; CHECK-NEXT:  [def-use] to [[N5:0x[0-9a-f]*]]
-
-; CHECK: Node Address:[[N5]]:single-instruction
-; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %arrayidx = getelementptr inbounds float, float* %b, i64 %i.02
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N6:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N2:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N6]]:single-instruction
+; CHECK: Node Address:[[N2]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %0 = load float, float* %arrayidx, align 4
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N7:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N3:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N4]]:single-instruction
+; CHECK: Node Address:[[N4:0x[0-9a-f]*]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %arrayidx1 = getelementptr inbounds float, float* %a, i64 %i.02
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N8:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N5:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N8]]:single-instruction
+; CHECK: Node Address:[[N5]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %1 = load float, float* %arrayidx1, align 4
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N7]]
-; CHECK-NEXT:  [memory] to [[N9:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N3]]
+; CHECK-NEXT:  [memory] to [[N6:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N7]]:single-instruction
+; CHECK: Node Address:[[N3]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %add = fadd float %0, %1
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N9]]
+; CHECK-NEXT:  [def-use] to [[N6]]
 
-; CHECK: Node Address:[[N3]]:single-instruction
+; CHECK: Node Address:[[N7:0x[0-9a-f]*]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %arrayidx2 = getelementptr inbounds float, float* %a, i64 %i.02
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N9]]
+; CHECK-NEXT:  [def-use] to [[N6]]
 
-; CHECK: Node Address:[[N9]]:single-instruction
+; CHECK: Node Address:[[N6]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    store float %add, float* %arrayidx2, align 4
 ; CHECK-NEXT: Edges:none!
 
-; CHECK: Node Address:[[N2]]:single-instruction
-; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %inc = add i64 %i.02, 1
-; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N10:0x[0-9a-f]*]]
-; CHECK-NEXT:  [def-use] to [[N1]]
-
-; CHECK: Node Address:[[N10]]:single-instruction
+; CHECK: Node Address:[[N8:0x[0-9a-f]*]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %exitcond = icmp ne i64 %inc, %n
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N11:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N9:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N11]]:single-instruction
+; CHECK: Node Address:[[N9]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    br i1 %exitcond, label %test2.for.body, label %for.end.loopexit
 ; CHECK-NEXT: Edges:none!
 
+; CHECK: Node Address:[[N10:0x[0-9a-f]*]]:pi-block
+; CHECK-NEXT: --- start of nodes in pi-block ---
+; CHECK: Node Address:[[N11:0x[0-9a-f]*]]:single-instruction
+; CHECK-NEXT: Instructions:
+; CHECK-NEXT:    %inc = add i64 %i.02, 1
+; CHECK-NEXT: Edges:
+; CHECK-NEXT:  [def-use] to [[N12:0x[0-9a-f]*]]
+
+; CHECK: Node Address:[[N12]]:single-instruction
+; CHECK-NEXT: Instructions:
+; CHECK-NEXT:    %i.02 = phi i64 [ %inc, %test2.for.body ], [ 0, %test2.for.body.preheader ]
+; CHECK-NEXT: Edges:
+; CHECK-NEXT:  [def-use] to [[N11]]
+; CHECK-NEXT: --- end of nodes in pi-block ---
+; CHECK-NEXT: Edges:
+; CHECK-NEXT:  [def-use] to [[N1]]
+; CHECK-NEXT:  [def-use] to [[N4]]
+; CHECK-NEXT:  [def-use] to [[N7]]
+; CHECK-NEXT:  [def-use] to [[N8]]
+
+
 ;; Loop-independent memory dependencies.
 ;; void test2(unsigned long n, float * restrict a, float * restrict b) {
 ;;  for (unsigned long i = 0; i < n; i++)
 ;;    a[i] = b[i] + a[i];
 ;; }
 
 define void @test2(i64 %n, float* noalias %a, float* noalias %b) {
 entry:
test2.for.body:                                         ; preds = %entry, %test2.for.body
   store float %add, float* %arrayidx2, align 4
   %inc = add i64 %i.02, 1
   %exitcond = icmp ne i64 %inc, %n
   br i1 %exitcond, label %test2.for.body, label %for.end
 
 for.end:                                          ; preds = %test2.for.body, %entry
   ret void
 }
 No newline at end of file

llvm/test/Analysis/DDG/basic-b.ll

 ; RUN: opt < %s -disable-output "-passes=print<ddg>" 2>&1 | FileCheck %s
 
 ; CHECK-LABEL: 'DDG' for loop 'test1.for.body':
 ; CHECK: Node Address:[[N1:0x[0-9a-f]*]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %i.02 = phi i64 [ %inc, %test1.for.body ], [ 1, %test1.for.body.preheader ]
+; CHECK-NEXT:    %arrayidx = getelementptr inbounds float, float* %b, i64 %i.02
 ; CHECK-NEXT: Edges:
 ; CHECK-NEXT:  [def-use] to [[N2:0x[0-9a-f]*]]
+
+; CHECK: Node Address:[[N2]]:single-instruction
+; CHECK-NEXT: Instructions:
+; CHECK-NEXT:    %0 = load float, float* %arrayidx, align 4
+; CHECK-NEXT: Edges:
 ; CHECK-NEXT:  [def-use] to [[N3:0x[0-9a-f]*]]
-; CHECK-NEXT:  [def-use] to [[N4:0x[0-9a-f]*]]
+
+; CHECK: Node Address:[[N4:0x[0-9a-f]*]]:single-instruction
+; CHECK-NEXT: Instructions:
+; CHECK-NEXT:    %sub1 = add i64 %i.02, -1
+; CHECK-NEXT: Edges:
 ; CHECK-NEXT:  [def-use] to [[N5:0x[0-9a-f]*]]
 
 ; CHECK: Node Address:[[N5]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %arrayidx = getelementptr inbounds float, float* %b, i64 %i.02
+; CHECK-NEXT:    %arrayidx2 = getelementptr inbounds float, float* %a, i64 %sub1
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N6:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N3]]
 
-; CHECK: Node Address:[[N6]]:single-instruction
+; CHECK: Node Address:[[N6:0x[0-9a-f]*]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %0 = load float, float* %arrayidx, align 4
+; CHECK-NEXT:    %arrayidx3 = getelementptr inbounds float, float* %a, i64 %i.02
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N7:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N3]]
 
-; CHECK: Node Address:[[N4]]:single-instruction
+; CHECK: Node Address:[[N7:0x[0-9a-f]*]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %sub1 = add i64 %i.02, -1
+; CHECK-NEXT:    %cmp = icmp ult i64 %inc, %sub
 ; CHECK-NEXT: Edges:
 ; CHECK-NEXT:  [def-use] to [[N8:0x[0-9a-f]*]]
 
 ; CHECK: Node Address:[[N8]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %arrayidx2 = getelementptr inbounds float, float* %a, i64 %sub1
-; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N9:0x[0-9a-f]*]]
-
-; CHECK: Node Address:[[N9]]:single-instruction
-; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %1 = load float, float* %arrayidx2, align 4
-; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N7]]
+; CHECK-NEXT:    br i1 %cmp, label %test1.for.body, label %for.end.loopexit
+; CHECK-NEXT: Edges:none!
 
-; CHECK: Node Address:[[N7]]:single-instruction
+; CHECK: Node Address:[[N3]]:pi-block
+; CHECK-NEXT: --- start of nodes in pi-block ---
+; CHECK: Node Address:[[N10:0x[0-9a-f]*]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %add = fadd float %0, %1
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N10:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N11:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N3]]:single-instruction
+; CHECK: Node Address:[[N12:0x[0-9a-f]*]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %arrayidx3 = getelementptr inbounds float, float* %a, i64 %i.02
+; CHECK-NEXT:    %1 = load float, float* %arrayidx2, align 4
 ; CHECK-NEXT: Edges:
 ; CHECK-NEXT:  [def-use] to [[N10]]
 
-; CHECK: Node Address:[[N10]]:single-instruction
+; CHECK: Node Address:[[N11]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    store float %add, float* %arrayidx3, align 4
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [memory] to [[N9]]
+; CHECK-NEXT:  [memory] to [[N12]]
+; CHECK-NEXT:--- end of nodes in pi-block ---
+; CHECK-NEXT: Edges:none!
 
-; CHECK: Node Address:[[N2]]:single-instruction
+; CHECK: Node Address:[[N9:0x[0-9a-f]*]]:pi-block
+; CHECK-NEXT:--- start of nodes in pi-block ---
+; CHECK: Node Address:[[N13:0x[0-9a-f]*]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %inc = add i64 %i.02, 1
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N11:0x[0-9a-f]*]]
-; CHECK-NEXT:  [def-use] to [[N1]]
+; CHECK-NEXT:  [def-use] to [[N14:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N11]]:single-instruction
+; CHECK: Node Address:[[N14]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %cmp = icmp ult i64 %inc, %sub
+; CHECK-NEXT:    %i.02 = phi i64 [ %inc, %test1.for.body ], [ 1, %test1.for.body.preheader ]
+; CHECK-NEXT: Edges:
+; CHECK-NEXT:  [def-use] to [[N13]]
+; CHECK-NEXT:--- end of nodes in pi-block ---
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N12:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N1]]
+; CHECK-NEXT:  [def-use] to [[N4]]
+; CHECK-NEXT:  [def-use] to [[N6]]
+; CHECK-NEXT:  [def-use] to [[N7]]
 
-; CHECK: Node Address:[[N12]]:single-instruction
-; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    br i1 %cmp, label %test1.for.body, label %for.end.loopexit
-; CHECK-NEXT: Edges:none!
 
 ;; Loop-carried dependence requiring edge-reversal to expose a cycle
 ;; in the graph.
 ;; void test(unsigned long n, float * restrict a, float * restrict b) {
 ;;  for (unsigned long i = 1; i < n-1; i++)
 ;;    a[i] = b[i] + a[i-1];
 ;; }
 
test1.for.body:                                         ; preds = %entry, %test1.for.body
   %inc = add i64 %i.02, 1
   %cmp = icmp ult i64 %inc, %sub
   br i1 %cmp, label %test1.for.body, label %for.end
 
 for.end:                                          ; preds = %test1.for.body, %entry
   ret void
 }
 
-
 ; CHECK-LABEL: 'DDG' for loop 'test2.for.body':
 ; CHECK: Node Address:[[N1:0x[0-9a-f]*]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %i.02 = phi i64 [ %inc, %test2.for.body ], [ 1, %test2.for.body.preheader ]
-; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N2:0x[0-9a-f]*]]
-; CHECK-NEXT:  [def-use] to [[N3:0x[0-9a-f]*]]
-; CHECK-NEXT:  [def-use] to [[N4:0x[0-9a-f]*]]
-; CHECK-NEXT:  [def-use] to [[N5:0x[0-9a-f]*]]
-
-; CHECK: Node Address:[[N5]]:single-instruction
-; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %arrayidx = getelementptr inbounds float, float* %b, i64 %i.02
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N6:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N2:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N6]]:single-instruction
+; CHECK: Node Address:[[N2]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %0 = load float, float* %arrayidx, align 4
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N7:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N3:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N4]]:single-instruction
+; CHECK: Node Address:[[N4:0x[0-9a-f]*]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %add1 = add i64 %i.02, 1
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N8:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N5:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N8]]:single-instruction
+; CHECK: Node Address:[[N5]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %arrayidx2 = getelementptr inbounds float, float* %a, i64 %add1
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N9:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N6:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N9]]:single-instruction
+; CHECK: Node Address:[[N6]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %1 = load float, float* %arrayidx2, align 4
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N7]]
-; CHECK-NEXT:  [memory] to [[N10:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N3]]
+; CHECK-NEXT:  [memory] to [[N7:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N7]]:single-instruction
+; CHECK: Node Address:[[N3]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %add = fadd float %0, %1
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N10]]
+; CHECK-NEXT:  [def-use] to [[N7]]
 
-; CHECK: Node Address:[[N3]]:single-instruction
+; CHECK: Node Address:[[N8:0x[0-9a-f]*]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %arrayidx3 = getelementptr inbounds float, float* %a, i64 %i.02
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N10]]
+; CHECK-NEXT:  [def-use] to [[N7]]
 
-; CHECK: Node Address:[[N10]]:single-instruction
+; CHECK: Node Address:[[N7]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    store float %add, float* %arrayidx3, align 4
 ; CHECK-NEXT: Edges:none!
 
-; CHECK: Node Address:[[N2]]:single-instruction
-; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %inc = add i64 %i.02, 1
-; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N11:0x[0-9a-f]*]]
-; CHECK-NEXT:  [def-use] to [[N1]]
-
-; CHECK: Node Address:[[N11]]:single-instruction
+; CHECK: Node Address:[[N9:0x[0-9a-f]*]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %cmp = icmp ult i64 %inc, %sub
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N12:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N10:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N12]]:single-instruction
+; CHECK: Node Address:[[N10]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    br i1 %cmp, label %test2.for.body, label %for.end.loopexit
 ; CHECK-NEXT: Edges:none!
 
+; CHECK: Node Address:[[N11:0x[0-9a-f]*]]:pi-block
+; CHECK-NEXT:--- start of nodes in pi-block ---
+; CHECK: Node Address:[[N12:0x[0-9a-f]*]]:single-instruction
+; CHECK-NEXT: Instructions:
+; CHECK-NEXT:    %inc = add i64 %i.02, 1
+; CHECK-NEXT: Edges:
+; CHECK-NEXT:  [def-use] to [[N13:0x[0-9a-f]*]]
+
+; CHECK: Node Address:[[N13]]:single-instruction
+; CHECK-NEXT: Instructions:
+; CHECK-NEXT:    %i.02 = phi i64 [ %inc, %test2.for.body ], [ 1, %test2.for.body.preheader ]
+; CHECK-NEXT: Edges:
+; CHECK-NEXT:  [def-use] to [[N12]]
+; CHECK-NEXT:--- end of nodes in pi-block ---
+; CHECK-NEXT: Edges:
+; CHECK-NEXT:  [def-use] to [[N1]]
+; CHECK-NEXT:  [def-use] to [[N4]]
+; CHECK-NEXT:  [def-use] to [[N8]]
+; CHECK-NEXT:  [def-use] to [[N9]]
+
 
 ;; Forward loop-carried dependence *not* causing a cycle.
 ;; void test2(unsigned long n, float * restrict a, float * restrict b) {
 ;;  for (unsigned long i = 1; i < n-1; i++)
 ;;    a[i] = b[i] + a[i+1];
 ;; }
 
 define void @test2(i64 %n, float* noalias %a, float* noalias %b) {

llvm/test/Analysis/DDG/basic-loopnest.ll

 ; RUN: opt < %s -disable-output "-passes=print<ddg>" 2>&1 | FileCheck %s
 
 
 ; CHECK-LABEL: 'DDG' for loop 'test1.for.cond1.preheader':
 ; CHECK: Node Address:[[N1:0x[0-9a-f]*]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:   %i.04 = phi i64 [ %inc13, %for.inc12 ], [ 0, %test1.for.cond1.preheader.preheader ]
+; CHECK-NEXT:    %sub = add i64 %n, -1
 ; CHECK-NEXT: Edges:
 ; CHECK-NEXT:  [def-use] to [[N2:0x[0-9a-f]*]]
 ; CHECK-NEXT:  [def-use] to [[N3:0x[0-9a-f]*]]
-; CHECK-NEXT:  [def-use] to [[N4:0x[0-9a-f]*]]
-; CHECK-NEXT:  [def-use] to [[N5:0x[0-9a-f]*]]
-
-; CHECK: Node Address:[[N6:0x[0-9a-f]*]]:single-instruction
-; CHECK-NEXT: Instructions:
-; CHECK-NEXT:   %sub = add i64 %n, -1
-; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N7:0x[0-9a-f]*]]
-; CHECK-NEXT:  [def-use] to [[N8:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N8]]:single-instruction
+; CHECK: Node Address:[[N3]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:   %cmp21 = icmp ult i64 1, %sub
+; CHECK-NEXT:    %cmp21 = icmp ult i64 1, %sub
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N9:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N4:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N9]]:single-instruction
+; CHECK: Node Address:[[N4]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:   br i1 %cmp21, label %for.body4.preheader, label %for.inc12
+; CHECK-NEXT:    br i1 %cmp21, label %for.body4.preheader, label %for.inc12
 ; CHECK-NEXT: Edges:none!
 
-; CHECK: Node Address:[[N10:0x[0-9a-f]*]]:single-instruction
-; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %j.02 = phi i64 [ %inc, %for.body4 ], [ 1, %for.body4.preheader ]
-; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N11:0x[0-9a-f]*]]
-; CHECK-NEXT:  [def-use] to [[N12:0x[0-9a-f]*]]
-; CHECK-NEXT:  [def-use] to [[N13:0x[0-9a-f]*]]
-; CHECK-NEXT:  [def-use] to [[N14:0x[0-9a-f]*]]
-
-; CHECK: Node Address:[[N5]]:single-instruction
+; CHECK: Node Address:[[N5:0x[0-9a-f]*]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %0 = mul nsw i64 %i.04, %n
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N15:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N6:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N15]]:single-instruction
+; CHECK: Node Address:[[N6]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %arrayidx = getelementptr inbounds float, float* %b, i64 %0
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N14]]
+; CHECK-NEXT:  [def-use] to [[N7:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N14]]:single-instruction
+; CHECK: Node Address:[[N7]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %arrayidx5 = getelementptr inbounds float, float* %arrayidx, i64 %j.02
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N16:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N8:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N16]]:single-instruction
+; CHECK: Node Address:[[N8]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %1 = load float, float* %arrayidx5, align 4
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N17:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N9:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N4]]:single-instruction
+; CHECK: Node Address:[[N10:0x[0-9a-f]*]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %2 = mul nsw i64 %i.04, %n
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N18:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N11:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N18]]:single-instruction
-; CHECK-NEXT: Instructions: 
-; CHECK-NEXT:   %arrayidx6 = getelementptr inbounds float, float* %a, i64 %2
+; CHECK: Node Address:[[N11]]:single-instruction
+; CHECK-NEXT: Instructions:
+; CHECK-NEXT:    %arrayidx6 = getelementptr inbounds float, float* %a, i64 %2
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N19:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N12:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N13]]:single-instruction
+; CHECK: Node Address:[[N13:0x[0-9a-f]*]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %sub7 = add i64 %j.02, -1
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N19]]
+; CHECK-NEXT:  [def-use] to [[N12]]
 
-; CHECK: Node Address:[[N19]]:single-instruction
+; CHECK: Node Address:[[N12]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %arrayidx8 = getelementptr inbounds float, float* %arrayidx6, i64 %sub7
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N20:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N9]]
 
-; CHECK: Node Address:[[N20]]:single-instruction
+; CHECK: Node Address:[[N14:0x[0-9a-f]*]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %3 = load float, float* %arrayidx8, align 4
+; CHECK-NEXT:    %4 = mul nsw i64 %i.04, %n
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N17]]
+; CHECK-NEXT:  [def-use] to [[N15:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N17]]:single-instruction
+; CHECK: Node Address:[[N15]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %add = fadd float %1, %3
+; CHECK-NEXT:    %arrayidx10 = getelementptr inbounds float, float* %a, i64 %4
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N26:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N16:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N3]]:single-instruction
+; CHECK: Node Address:[[N16]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %4 = mul nsw i64 %i.04, %n
+; CHECK-NEXT:    %arrayidx11 = getelementptr inbounds float, float* %arrayidx10, i64 %j.02
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N27:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N9]]
 
-; CHECK: Node Address:[[N27]]:single-instruction
+; CHECK: Node Address:[[N2]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %arrayidx10 = getelementptr inbounds float, float* %a, i64 %4
+; CHECK-NEXT:    %cmp2 = icmp ult i64 %inc, %sub
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N12]]
+; CHECK-NEXT:  [def-use] to [[N17:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N12]]:single-instruction
+; CHECK: Node Address:[[N17]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %arrayidx11 = getelementptr inbounds float, float* %arrayidx10, i64 %j.02
-; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N26]]
+; CHECK-NEXT:    br i1 %cmp2, label %for.body4, label %for.inc12.loopexit
+; CHECK-NEXT: Edges:none!
 
-; CHECK: Node Address:[[N26]]:single-instruction
+; CHECK: Node Address:[[N18:0x[0-9a-f]*]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    store float %add, float* %arrayidx11, align 4
+; CHECK-NEXT:    %exitcond = icmp ne i64 %inc13, %n
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [memory] to [[N20]]
+; CHECK-NEXT:  [def-use] to [[N19:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N11]]:single-instruction
+; CHECK: Node Address:[[N19]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %inc = add i64 %j.02, 1
-; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N7]]
-; CHECK-NEXT:  [def-use] to [[N10]]
+; CHECK-NEXT:    br i1 %exitcond, label %test1.for.cond1.preheader, label %for.end14.loopexit
+; CHECK-NEXT: Edges:none!
 
-; CHECK: Node Address:[[N7]]:single-instruction
+; CHECK: Node Address:[[N20:0x[0-9a-f]*]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %cmp2 = icmp ult i64 %inc, %sub
-; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N21:0x[0-9a-f]*]]
+; CHECK-NEXT:    br label %for.body4
+; CHECK-NEXT: Edges:none!
 
-; CHECK: Node Address:[[N21]]:single-instruction
+; CHECK: Node Address:[[N21:0x[0-9a-f]*]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    br i1 %cmp2, label %for.body4, label %for.inc12.loopexit
+; CHECK-NEXT:    br label %for.inc12
 ; CHECK-NEXT: Edges:none!
 
-; CHECK: Node Address:[[N2]]:single-instruction
+; CHECK: Node Address:[[N9]]:pi-block
+; CHECK-NEXT:--- start of nodes in pi-block ---
+; CHECK: Node Address:[[N22:0x[0-9a-f]*]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %inc13 = add i64 %i.04, 1
+; CHECK-NEXT:    %add = fadd float %1, %3
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N22:0x[0-9a-f]*]]
-; CHECK-NEXT:  [def-use] to [[N1]]
+; CHECK-NEXT:  [def-use] to [[N23:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N22]]:single-instruction
+; CHECK: Node Address:[[N24:0x[0-9a-f]*]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %exitcond = icmp ne i64 %inc13, %n
+; CHECK-NEXT:    %3 = load float, float* %arrayidx8, align 4
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N23:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N22]]
 
 ; CHECK: Node Address:[[N23]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    br i1 %exitcond, label %test1.for.cond1.preheader, label %for.end14.loopexit
+; CHECK-NEXT:    store float %add, float* %arrayidx11, align 4
+; CHECK-NEXT: Edges:
+; CHECK-NEXT:  [memory] to [[N24]]
+; CHECK-NEXT:--- end of nodes in pi-block ---
 ; CHECK-NEXT: Edges:none!
 
-; CHECK: Node Address:[[N24:0x[0-9a-f]*]]:single-instruction
+; CHECK: Node Address:[[N25:0x[0-9a-f]*]]:pi-block
+; CHECK-NEXT:--- start of nodes in pi-block ---
+; CHECK: Node Address:[[N26:0x[0-9a-f]*]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    br label %for.body4
-; CHECK-NEXT: Edges:none!
+; CHECK-NEXT:    %inc13 = add i64 %i.04, 1
+; CHECK-NEXT: Edges:
+; CHECK-NEXT:  [def-use] to [[N27:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N25:0x[0-9a-f]*]]:single-instruction
+; CHECK: Node Address:[[N27]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    br label %for.inc12
-; CHECK-NEXT: Edges:none!
+; CHECK-NEXT:    %i.04 = phi i64 [ %inc13, %for.inc12 ], [ 0, %test1.for.cond1.preheader.preheader ]
+; CHECK-NEXT: Edges:
+; CHECK-NEXT:  [def-use] to [[N26]]
+; CHECK-NEXT:--- end of nodes in pi-block ---
+; CHECK-NEXT: Edges:
+; CHECK-NEXT:  [def-use] to [[N5]]
+; CHECK-NEXT:  [def-use] to [[N10]]
+; CHECK-NEXT:  [def-use] to [[N14]]
+; CHECK-NEXT:  [def-use] to [[N18]]
+
+; CHECK: Node Address:[[N28:0x[0-9a-f]*]]:pi-block
+; CHECK-NEXT:--- start of nodes in pi-block ---
+; CHECK: Node Address:[[N29:0x[0-9a-f]*]]:single-instruction
+; CHECK-NEXT: Instructions:
+; CHECK-NEXT:    %inc = add i64 %j.02, 1
+; CHECK-NEXT: Edges:
+; CHECK-NEXT:  [def-use] to [[N30:0x[0-9a-f]*]]
+
+; CHECK: Node Address:[[N30]]:single-instruction
+; CHECK-NEXT: Instructions:
+; CHECK-NEXT:    %j.02 = phi i64 [ %inc, %for.body4 ], [ 1, %for.body4.preheader ]
+; CHECK-NEXT: Edges:
+; CHECK-NEXT:  [def-use] to [[N29]]
+; CHECK-NEXT:--- end of nodes in pi-block ---
+; CHECK-NEXT: Edges:
+; CHECK-NEXT:  [def-use] to [[N7]]
+; CHECK-NEXT:  [def-use] to [[N13]]
+; CHECK-NEXT:  [def-use] to [[N16]]
+; CHECK-NEXT:  [def-use] to [[N2]]
 
 
 
 ;; This test has a cycle.
 ;; void test1(unsigned long n, float a[][n], float b[][n]) {
 ;;  for (unsigned long i = 0; i < n; i++)
 ;;    for (unsigned long j = 1; j < n-1; j++)
 ;;      a[i][j] = b[i][j] + a[i][j-1];
for.end14:                                        ; preds = %for.inc12, %entry
   ret void
 }
 
 
 
 ; CHECK-LABEL: 'DDG' for loop 'test2.for.cond1.preheader':
 ; CHECK: Node Address:[[N1:0x[0-9a-f]*]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:   %i.04 = phi i64 [ %inc13, %for.inc12 ], [ 0, %test2.for.cond1.preheader.preheader ]
+; CHECK-NEXT:    %sub = add i64 %n, -1
 ; CHECK-NEXT: Edges:
 ; CHECK-NEXT:  [def-use] to [[N2:0x[0-9a-f]*]]
 ; CHECK-NEXT:  [def-use] to [[N3:0x[0-9a-f]*]]
-; CHECK-NEXT:  [def-use] to [[N4:0x[0-9a-f]*]]
-; CHECK-NEXT:  [def-use] to [[N5:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N6:0x[0-9a-f]*]]:single-instruction
-; CHECK-NEXT: Instructions:
-; CHECK-NEXT:   %sub = add i64 %n, -1
-; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N7:0x[0-9a-f]*]]
-; CHECK-NEXT:  [def-use] to [[N8:0x[0-9a-f]*]]
-
-; CHECK: Node Address:[[N8]]:single-instruction
+; CHECK: Node Address:[[N3]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:   %cmp21 = icmp ult i64 1, %sub
+; CHECK-NEXT:    %cmp21 = icmp ult i64 1, %sub
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N9:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N4:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N9]]:single-instruction
+; CHECK: Node Address:[[N4]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:   br i1 %cmp21, label %for.body4.preheader, label %for.inc12
+; CHECK-NEXT:    br i1 %cmp21, label %for.body4.preheader, label %for.inc12
 ; CHECK-NEXT: Edges:none!
 
-; CHECK: Node Address:[[N10:0x[0-9a-f]*]]:single-instruction
-; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %j.02 = phi i64 [ %inc, %for.body4 ], [ 1, %for.body4.preheader ]
-; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N11:0x[0-9a-f]*]]
-; CHECK-NEXT:  [def-use] to [[N12:0x[0-9a-f]*]]
-; CHECK-NEXT:  [def-use] to [[N13:0x[0-9a-f]*]]
-; CHECK-NEXT:  [def-use] to [[N14:0x[0-9a-f]*]]
-
-; CHECK: Node Address:[[N5]]:single-instruction
+; CHECK: Node Address:[[N5:0x[0-9a-f]*]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %0 = mul nsw i64 %i.04, %n
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N15:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N6:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N15]]:single-instruction
+; CHECK: Node Address:[[N6]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %arrayidx = getelementptr inbounds float, float* %b, i64 %0
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N14]]
+; CHECK-NEXT:  [def-use] to [[N7:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N14]]:single-instruction
+; CHECK: Node Address:[[N7]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %arrayidx5 = getelementptr inbounds float, float* %arrayidx, i64 %j.02
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N16:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N8:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N16]]:single-instruction
+; CHECK: Node Address:[[N8]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %1 = load float, float* %arrayidx5, align 4
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N17:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N9:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N4]]:single-instruction
+; CHECK: Node Address:[[N10:0x[0-9a-f]*]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %2 = mul nsw i64 %i.04, %n
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N18:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N11:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N18]]:single-instruction
-; CHECK-NEXT: Instructions: 
-; CHECK-NEXT:   %arrayidx6 = getelementptr inbounds float, float* %a, i64 %2
+; CHECK: Node Address:[[N11]]:single-instruction
+; CHECK-NEXT: Instructions:
+; CHECK-NEXT:    %arrayidx6 = getelementptr inbounds float, float* %a, i64 %2
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N19:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N12:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N13]]:single-instruction
+; CHECK: Node Address:[[N13:0x[0-9a-f]*]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %add7 = add i64 %j.02, 1
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N19]]
+; CHECK-NEXT:  [def-use] to [[N12]]
 
-; CHECK: Node Address:[[N19]]:single-instruction
+; CHECK: Node Address:[[N12]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %arrayidx8 = getelementptr inbounds float, float* %arrayidx6, i64 %add7
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N20:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N14:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N20]]:single-instruction
+; CHECK: Node Address:[[N14]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %3 = load float, float* %arrayidx8, align 4
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N17]]
-; CHECK-NEXT:  [memory] to [[N26:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N9]]
+; CHECK-NEXT:  [memory] to [[N15:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N17]]:single-instruction
+; CHECK: Node Address:[[N9]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %add = fadd float %1, %3
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N26]]
+; CHECK-NEXT:  [def-use] to [[N15]]
 
-; CHECK: Node Address:[[N3]]:single-instruction
+; CHECK: Node Address:[[N16:0x[0-9a-f]*]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %4 = mul nsw i64 %i.04, %n
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N27:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N17:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N27]]:single-instruction
+; CHECK: Node Address:[[N17]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %arrayidx10 = getelementptr inbounds float, float* %a, i64 %4
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N12]]
+; CHECK-NEXT:  [def-use] to [[N18:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N12]]:single-instruction
+; CHECK: Node Address:[[N18]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %arrayidx11 = getelementptr inbounds float, float* %arrayidx10, i64 %j.02
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N26]]
+; CHECK-NEXT:  [def-use] to [[N15]]
 
-; CHECK: Node Address:[[N26]]:single-instruction
+; CHECK: Node Address:[[N15]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    store float %add, float* %arrayidx11, align 4
 ; CHECK-NEXT: Edges:none!
 
-; CHECK: Node Address:[[N11]]:single-instruction
-; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %inc = add i64 %j.02, 1
-; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N7]]
-; CHECK-NEXT:  [def-use] to [[N10]]
-
-; CHECK: Node Address:[[N7]]:single-instruction
+; CHECK: Node Address:[[N2]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %cmp2 = icmp ult i64 %inc, %sub
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N21:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N19:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N21]]:single-instruction
+; CHECK: Node Address:[[N19]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    br i1 %cmp2, label %for.body4, label %for.inc12.loopexit
 ; CHECK-NEXT: Edges:none!
 
-; CHECK: Node Address:[[N2]]:single-instruction
-; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %inc13 = add i64 %i.04, 1
-; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N22:0x[0-9a-f]*]]
-; CHECK-NEXT:  [def-use] to [[N1]]
-
-; CHECK: Node Address:[[N22]]:single-instruction
+; CHECK: Node Address:[[N20:0x[0-9a-f]*]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %exitcond = icmp ne i64 %inc13, %n
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N23:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N21:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N23]]:single-instruction
+; CHECK: Node Address:[[N21]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    br i1 %exitcond, label %test2.for.cond1.preheader, label %for.end14.loopexit
 ; CHECK-NEXT: Edges:none!
 
-; CHECK: Node Address:[[N24:0x[0-9a-f]*]]:single-instruction
+; CHECK: Node Address:[[N22:0x[0-9a-f]*]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    br label %for.body4
 ; CHECK-NEXT: Edges:none!
 
-; CHECK: Node Address:[[N25:0x[0-9a-f]*]]:single-instruction
+; CHECK: Node Address:[[N23:0x[0-9a-f]*]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    br label %for.inc12
 ; CHECK-NEXT: Edges:none!
 
+; CHECK: Node Address:[[N24:0x[0-9a-f]*]]:pi-block
+; CHECK-NEXT:--- start of nodes in pi-block ---
+; CHECK: Node Address:[[N25:0x[0-9a-f]*]]:single-instruction
+; CHECK-NEXT: Instructions:
+; CHECK-NEXT:    %inc13 = add i64 %i.04, 1
+; CHECK-NEXT: Edges:
+; CHECK-NEXT:  [def-use] to [[N26:0x[0-9a-f]*]]
+
+; CHECK: Node Address:[[N26]]:single-instruction
+; CHECK-NEXT: Instructions:
+; CHECK-NEXT:    %i.04 = phi i64 [ %inc13, %for.inc12 ], [ 0, %test2.for.cond1.preheader.preheader ]
+; CHECK-NEXT: Edges:
+; CHECK-NEXT:  [def-use] to [[N25]]
+; CHECK-NEXT:--- end of nodes in pi-block ---
+; CHECK-NEXT: Edges:
+; CHECK-NEXT:  [def-use] to [[N5]]
+; CHECK-NEXT:  [def-use] to [[N10]]
+; CHECK-NEXT:  [def-use] to [[N16]]
+; CHECK-NEXT:  [def-use] to [[N20]]
+
+; CHECK: Node Address:[[N27:0x[0-9a-f]*]]:pi-block
+; CHECK-NEXT:--- start of nodes in pi-block ---
+; CHECK: Node Address:[[N28:0x[0-9a-f]*]]:single-instruction
+; CHECK-NEXT: Instructions:
+; CHECK-NEXT:    %inc = add i64 %j.02, 1
+; CHECK-NEXT: Edges:
+; CHECK-NEXT:  [def-use] to [[N29:0x[0-9a-f]*]]
+
+; CHECK: Node Address:[[N29]]:single-instruction
+; CHECK-NEXT: Instructions:
+; CHECK-NEXT:    %j.02 = phi i64 [ %inc, %for.body4 ], [ 1, %for.body4.preheader ]
+; CHECK-NEXT: Edges:
+; CHECK-NEXT:  [def-use] to [[N28]]
+; CHECK-NEXT:--- end of nodes in pi-block ---
+; CHECK-NEXT: Edges:
+; CHECK-NEXT:  [def-use] to [[N7]]
+; CHECK-NEXT:  [def-use] to [[N13]]
+; CHECK-NEXT:  [def-use] to [[N18]]
+; CHECK-NEXT:  [def-use] to [[N2]]
+
+
 ;; This test has no cycles.
 ;; void test2(unsigned long n, float a[][n], float b[][n]) {
 ;;  for (unsigned long i = 0; i < n; i++)
 ;;    for (unsigned long j = 1; j < n-1; j++)
 ;;      a[i][j] = b[i][j] + a[i][j+1];
 ;; }
 
 define void @test2(i64 %n, float* noalias %a, float* noalias %b) {

 for.inc12:                                        ; preds = %for.body4, %test2.for.cond1.preheader
   %inc13 = add i64 %i.04, 1
   %exitcond = icmp ne i64 %inc13, %n
   br i1 %exitcond, label %test2.for.cond1.preheader, label %for.end14
 
 for.end14:                                        ; preds = %for.inc12, %entry
   ret void
 }
 No newline at end of file

llvm/test/Analysis/DDG/root-node.ll

 ; RUN: opt < %s -disable-output "-passes=print<ddg>" 2>&1 | FileCheck %s
 
 ; CHECK-LABEL: 'DDG' for loop 'test1.for.body':
 
-; CHECK: Node Address:[[N1:0x[0-9a-f]*]]:single-instruction
-; CHECK-NEXT: Instructions:
-; CHECK-NEXT:   %i2.03 = phi i64 [ 0, %for.body.lr.ph ], [ %inc2, %test1.for.body ]
-
-; CHECK: Node Address:[[N2:0x[0-9a-f]*]]:single-instruction
-; CHECK-NEXT: Instructions:
-; CHECK-NEXT:   %i1.02 = phi i64 [ 0, %for.body.lr.ph ], [ %inc, %test1.for.body ]
-
 ; CHECK: Node Address:[[ROOT:0x[0-9a-f]*]]:root
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [rooted] to [[N1]]
-; CHECK-NEXT:  [rooted] to [[N2]]
+; CHECK-NEXT:  [rooted] to [[N1:0x[0-9a-f]*]]
+; CHECK-NEXT:  [rooted] to [[N2:0x[0-9a-f]*]]
+
+; CHECK: Node Address:[[N1]]:pi-block
+; CHECK: %i2.03 = phi i64 [ 0, %for.body.lr.ph ], [ %inc2, %test1.for.body ]
+
+; CHECK: Node Address:[[N2]]:pi-block
+; CHECK: %i1.02 = phi i64 [ 0, %for.body.lr.ph ], [ %inc, %test1.for.body ]
 
 
 ;; // Two separate components in the graph. Root node must link to both.
 ;; void test1(unsigned long n, float * restrict a, float * restrict b) {
 ;;   for (unsigned long i1 = 0, i2 = 0; i1 < n; i1++, i2++) {
 ;;     a[i1] = 1;
 ;;     b[i2] = -1;
 ;;   }

llvm/unittests/ADT/CMakeLists.txt

add_llvm_unittest(ADTTests
   BreadthFirstIteratorTest.cpp
   BumpPtrListTest.cpp
   DAGDeltaAlgorithmTest.cpp
   DeltaAlgorithmTest.cpp
   DenseMapTest.cpp
   DenseSetTest.cpp
   DepthFirstIteratorTest.cpp
   DirectedGraphTest.cpp
+  EnumeratedArrayTest.cpp
   EquivalenceClassesTest.cpp
   FallibleIteratorTest.cpp
   FoldingSet.cpp
   FunctionExtrasTest.cpp
   FunctionRefTest.cpp
   HashingTest.cpp
   IListBaseTest.cpp
   IListIteratorTest.cpp

llvm/unittests/ADT/EnumeratedArrayTest.cpp

+//===- llvm/unittest/ADT/EnumeratedArrayTest.cpp ----------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// EnumeratedArray unit tests.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/EnumeratedArray.h"
+#include "gtest/gtest.h"
+
+namespace llvm {
+
+//===--------------------------------------------------------------------===//
+// Test initialization and use of operator[] for both read and write.
+//===--------------------------------------------------------------------===//
+
+TEST(EnumeratedArray, InitAndIndex) {
+
+  enum class Colors { Red, Blue, Green, Last = Green };
+
+  EnumeratedArray<float, Colors, Colors::Last, size_t> Array1;
+
+  Array1[Colors::Red] = 1.0;
+  Array1[Colors::Blue] = 2.0;
+  Array1[Colors::Green] = 3.0;
+
+  EXPECT_EQ(Array1[Colors::Red], 1.0);
+  EXPECT_EQ(Array1[Colors::Blue], 2.0);
+  EXPECT_EQ(Array1[Colors::Green], 3.0);
+
+  EnumeratedArray<bool, Colors> Array2(true);
+
+  EXPECT_TRUE(Array2[Colors::Red]);
+  EXPECT_TRUE(Array2[Colors::Blue]);
+  EXPECT_TRUE(Array2[Colors::Green]);
+
+  Array2[Colors::Red] = true;
+  Array2[Colors::Blue] = false;
+  Array2[Colors::Green] = true;
+
+  EXPECT_TRUE(Array2[Colors::Red]);
+  EXPECT_FALSE(Array2[Colors::Blue]);
+  EXPECT_TRUE(Array2[Colors::Green]);
+}
+
+} // namespace llvm