[DDG] Data Dependence Graph - Topological Sort

[bmahjour]

Summary

In this patch the DDG DAG is sorted topologically to put the nodes in the graph in the order that would satisfy all dependencies. This helps transformations that would like to generate code based on the DDG. Since the DDG is a DAG a reverse-post-order traversal would give us the topological ordering. This patch also sorts the basic blocks passed to the builder based on program order to ensure that the dependencies are computed in the correct direction.

[Meinersbur]

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

50

[design question] def-uses only manifest as flow-dependency, but no anti- or output dependencies. Looking only at the dependencies, a loop distribution pass could conclude that the computation of e.g. %arrayidx2 could be split from the load/store pi-node. However, this is not possible without storing the values in an intermediate array.

My question is how the loop distribution pass should handle the situation? Will anti- and output dependencies for registers added later? Does the pass have to check on its own that no def-use chain would be separated into different loops?

[bmahjour]

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

50

In general, loop distribution would have to consider def-use dependencies the same way it handles scalar dependencies, ie make sure that those edges do not get split. Some def-use dependencies can be ignored if they can be rematerialized (eg if they are just part of the loop structure).

[bmahjour]

One of the sanitizer builds failed due to a memory leak issue. http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-bootstrap/builds/14902
The reason for the leak is that when sorting I did not consider the nodes inside of the pi-block so they got removed from the DirectedGraph's list of nodes, and did not get freed when the DDG destructor got called.
I've updated the patch to fix the leak and reopened this revision for review.

[Meinersbur]

llvm/lib/Analysis/DependenceGraphBuilder.cpp

369

[suggestion] Consider adding a comment that pi-nodes are appended to the end of the node list (and why).

374

[serious] This will a emit warning "unused value" in non-assert builds.

376

[style] Use llvm::reverse

for (NodeType *N : reverse(NodesInPO))

[Meinersbur]

[suggestion] Could you add a test case with a reduction (not necessarily in this patch), such as

double sum = 0;
for (int i = 0; i < n; i+=1)
  sum+=A[i];
return sum;

I am interested in what happens in self-recursive phi dependencies that are not induction variables. Note that GVN LoadPRE and LICM register promotion can create those as well. Another interesting case would be a nested reduction:

for (int j = 0; j < m; j+=1) {
  double sum = 0;
  for (int i = 0; i < n; i+=1)
    sum += A[i][j];
  B[j] = sum;
}

The motivation is that reductions usually are optimized differently than flow dependencies.

[bmahjour]

In D70609#1765480, @Meinersbur wrote:

[suggestion] Could you add a test case with a reduction (not necessarily in this patch), such as

double sum = 0;
for (int i = 0; i < n; i+=1)
  sum+=A[i];
return sum;

I am interested in what happens in self-recursive phi dependencies that are not induction variables. Note that GVN LoadPRE and LICM register promotion can create those as well. Another interesting case would be a nested reduction:

for (int j = 0; j < m; j+=1) {
  double sum = 0;
  for (int i = 0; i < n; i+=1)
    sum += A[i][j];
  B[j] = sum;
}

The motivation is that reductions usually are optimized differently than flow dependencies.

I'm planning to add more tests later. I have two more patches that would cause reordering in the LIT tests so I'm waiting for us to get those in before adding more maintenance. I've noted the reduction case and will add that to the list of tests.

[Meinersbur]

In D70609#1765666, @bmahjour wrote:

I'm planning to add more tests later. I have two more patches that would cause reordering in the LIT tests so I'm waiting for us to get those in before adding more maintenance. I've noted the reduction case and will add that to the list of tests.

Thanks

[Meinersbur]

LGTM assuming this fixes the leak (and the unused value warning).

[bmahjour]

Addressed Michael's comments.

llvm/include/llvm/Analysis/DDG.h

protected:
   // the graph, to ensure all nodes are reachable in a graph walk.
   NodeType *Root = nullptr;
 };
 
 using DDGInfo = DependenceGraphInfo<DDGNode>;
 
 /// Data Dependency Graph
 class DataDependenceGraph : public DDGBase, public DDGInfo {
+  friend AbstractDependenceGraphBuilder<DataDependenceGraph>;
   friend class DDGBuilder;
 
 public:
   using NodeType = DDGNode;
   using EdgeType = DDGEdge;
 
   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(Loop &L, LoopInfo &LI, 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
public:
   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;
   }
 
+  const NodeListType &getNodesInPiBlock(const DDGNode &N) final override {
+    auto *PiNode = dyn_cast<const PiBlockDDGNode>(&N);
+    assert(PiNode && "Expected a pi-block node.");
+    return PiNode->getNodes();
+  }
+
   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:
   /// 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();
+    sortNodesTopologically();
   }
 
   /// 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.
public:
 
   /// Apply graph abstraction to groups of nodes that belong to a strongly
   /// connected component of the graph to create larger compound nodes
   /// called pi-blocks. The purpose of this abstraction is to isolate sets of
   /// program elements that need to stay together during codegen and turn
   /// the dependence graph into an acyclic graph.
   void createPiBlocks();
 
+  /// Topologically sort the graph nodes.
+  void sortNodesTopologically();
+
 protected:
   /// Create the root node of the graph.
   virtual NodeType &createRootNode() = 0;
 
   /// 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;
 
+  /// Given a pi-block node, return a vector of all the nodes contained within
+  /// it.
+  virtual const NodeListType &getNodesInPiBlock(const NodeType &N) = 0;
+
   /// Deallocate memory of edge \p E.
   virtual void destroyEdge(EdgeType &E) { delete &E; }
 
   /// Deallocate memory of node \p N.
   virtual void destroyNode(NodeType &N) { delete &N; }
 
   /// Return true if creation of pi-blocks are supported and desired,
   /// and false otherwise.

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/ADT/SCCIterator.h"
 #include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/LoopIterator.h"
 #include "llvm/Support/CommandLine.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."));
 

 
 //===--------------------------------------------------------------------===//
 // DataDependenceGraph implementation
 //===--------------------------------------------------------------------===//
 using BasicBlockListType = SmallVector<BasicBlock *, 8>;
 
 DataDependenceGraph::DataDependenceGraph(Function &F, DependenceInfo &D)
     : DependenceGraphInfo(F.getName().str(), D) {
+  // Put the basic blocks in program order for correct dependence
+  // directions.
   BasicBlockListType BBList;
-  for (auto &BB : F.getBasicBlockList())
-    BBList.push_back(&BB);
+  for (auto &SCC : make_range(scc_begin(&F), scc_end(&F)))
+    for (BasicBlock * BB : SCC)
+      BBList.push_back(BB);
+  std::reverse(BBList.begin(), BBList.end());
   DDGBuilder(*this, D, BBList).populate();
 }
 
-DataDependenceGraph::DataDependenceGraph(const Loop &L, DependenceInfo &D)
+DataDependenceGraph::DataDependenceGraph(Loop &L, LoopInfo &LI,
+                                         DependenceInfo &D)
     : DependenceGraphInfo(Twine(L.getHeader()->getParent()->getName() + "." +
                                 L.getHeader()->getName())
                               .str(),
                           D) {
+  // Put the basic blocks in program order for correct dependence
+  // directions.
+  LoopBlocksDFS DFS(&L);
+  DFS.perform(&LI);
   BasicBlockListType BBList;
-  for (BasicBlock *BB : L.blocks())
+  for (BasicBlock *BB : make_range(DFS.beginRPO(), DFS.endRPO()))
     BBList.push_back(BB);
   DDGBuilder(*this, D, BBList).populate();
 }
 
 DataDependenceGraph::~DataDependenceGraph() {
   for (auto *N : Nodes) {
     for (auto *E : *N)
       delete E;

 // DDG Analysis Passes
 //===--------------------------------------------------------------------===//
 
 /// DDG as a loop pass.
 DDGAnalysis::Result DDGAnalysis::run(Loop &L, LoopAnalysisManager &AM,
                                      LoopStandardAnalysisResults &AR) {
   Function *F = L.getHeader()->getParent();
   DependenceInfo DI(F, &AR.AA, &AR.SE, &AR.LI);
-  return std::make_unique<DataDependenceGraph>(L, DI);
+  return std::make_unique<DataDependenceGraph>(L, AR.LI, DI);
 }
 AnalysisKey DDGAnalysis::Key;
 
 PreservedAnalyses DDGAnalysisPrinterPass::run(Loop &L, LoopAnalysisManager &AM,
                                               LoopStandardAnalysisResults &AR,
                                               LPMUpdater &U) {
   OS << "'DDG' for loop '" << L.getHeader()->getName() << "':\n";
   OS << *AM.getResult<DDGAnalysis>(L, AR);
   return PreservedAnalyses::all();
 }

llvm/lib/Analysis/DependenceGraphBuilder.cpp

for (DGIterator DstIt = SrcIt; DstIt != E; ++DstIt) {
         // can exit early.
         if (ForwardEdgeCreated && BackwardEdgeCreated)
           break;
       }
     }
   }
 }
 
+template <class G>
+void AbstractDependenceGraphBuilder<G>::sortNodesTopologically() {
+
+  // If we don't create pi-blocks, then we may not have a DAG.
+  if (!shouldCreatePiBlocks())
+    return;
+
+  SmallVector<NodeType *, 64> NodesInPO;
+  using NodeKind = typename NodeType::NodeKind;
+  for (NodeType *N : post_order(&Graph)) {
+    if (N->getKind() == NodeKind::PiBlock) {
+      // Put members of the pi-block right after the pi-block itself, for
+      // convenience.
+      const NodeListType &PiBlockMembers = getNodesInPiBlock(*N);
+      NodesInPO.insert(NodesInPO.end(), PiBlockMembers.begin(),
+                       PiBlockMembers.end());
+    }
+    NodesInPO.push_back(N);
+  }
+
+  size_t OldSize = Graph.Nodes.size();
+  Graph.Nodes.clear();
+  for (NodeType *N : reverse(NodesInPO))
+    Graph.Nodes.push_back(N);
+  if (Graph.Nodes.size() != OldSize)
+    assert(false &&
+           "Expected the number of nodes to stay the same after the sort");
+}
+
 template class llvm::AbstractDependenceGraphBuilder<DataDependenceGraph>;
 template class llvm::DependenceGraphInfo<DDGNode>;

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: Node Address:[[PI: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:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N6:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N7:0x[0-9a-f]*]]
+
+; CHECK: Node Address:[[N7]]:single-instruction
+; CHECK-NEXT: Instructions:
+; CHECK-NEXT:    %exitcond = icmp ne i64 %inc, %n
+; CHECK-NEXT: Edges:
+; CHECK-NEXT:  [def-use] to [[N8:0x[0-9a-f]*]]
+
+; 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:[[N6]]:single-instruction
+; CHECK-NEXT: Instructions:
+; CHECK-NEXT:    %arrayidx1 = getelementptr inbounds float, float* %a, i64 %i.02
+; CHECK-NEXT: Edges:
+; CHECK-NEXT:  [def-use] to [[N5:0x[0-9a-f]*]]
+
+; CHECK: Node Address:[[N1]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; 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: 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 [[N3]]
 
 ; CHECK: Node Address:[[N3]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %add = fadd float %0, %conv
 ; CHECK-NEXT: Edges:
-; 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:    %arrayidx1 = getelementptr inbounds float, float* %a, i64 %i.02
-; CHECK-NEXT: Edges:
 ; CHECK-NEXT:  [def-use] to [[N5]]
 
 ; 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:[[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 [[N8:0x[0-9a-f]*]]
-
-; 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) {
test1.for.body:                                         ; preds = %entry, %test1.for.body
   br i1 %exitcond, 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:    %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: Node Address:[[PI: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:    %0 = load float, float* %arrayidx, align 4
+; CHECK-NEXT:    %inc = add i64 %i.02, 1
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N3:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N12:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N4:0x[0-9a-f]*]]:single-instruction
+; CHECK: Node Address:[[N12]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %arrayidx1 = getelementptr inbounds float, float* %a, i64 %i.02
+; CHECK-NEXT:    %i.02 = phi i64 [ %inc, %test2.for.body ], [ 0, %test2.for.body.preheader ]
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N5:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N11]]
+; CHECK-NEXT: --- end of nodes in pi-block ---
+; CHECK-NEXT: Edges:
+; CHECK-NEXT:  [def-use] to [[N1:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N4:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N7:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N8:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N5]]:single-instruction
+; CHECK: Node Address:[[N8]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %1 = load float, float* %arrayidx1, align 4
+; CHECK-NEXT:    %exitcond = icmp ne i64 %inc, %n
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N3]]
-; CHECK-NEXT:  [memory] to [[N6:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N9:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N3]]:single-instruction
+; CHECK: Node Address:[[N9]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %add = fadd float %0, %1
-; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N6]]
+; CHECK-NEXT:    br i1 %exitcond, label %test2.for.body, label %for.end.loopexit
+; CHECK-NEXT: Edges:none!
 
-; CHECK: Node Address:[[N7:0x[0-9a-f]*]]:single-instruction
+; CHECK: Node Address:[[N7]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %arrayidx2 = getelementptr inbounds float, float* %a, i64 %i.02
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N6]]
+; CHECK-NEXT:  [def-use] to [[N6:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N6]]:single-instruction
+; CHECK: Node Address:[[N4]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    store float %add, float* %arrayidx2, align 4
-; CHECK-NEXT: Edges:none!
+; CHECK-NEXT:    %arrayidx1 = getelementptr inbounds float, float* %a, i64 %i.02
+; CHECK-NEXT: Edges:
+; CHECK-NEXT:  [def-use] to [[N5:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N8:0x[0-9a-f]*]]:single-instruction
+; CHECK: Node Address:[[N5]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %exitcond = icmp ne i64 %inc, %n
+; CHECK-NEXT:    %1 = load float, float* %arrayidx1, align 4
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N9:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N3:0x[0-9a-f]*]]
+; CHECK-NEXT:  [memory] to [[N6]]
 
-; CHECK: Node Address:[[N9]]:single-instruction
+; CHECK: Node Address:[[N1]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    br i1 %exitcond, label %test2.for.body, label %for.end.loopexit
-; CHECK-NEXT: Edges:none!
+; 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:[[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: Node Address:[[N2]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %inc = add i64 %i.02, 1
+; CHECK-NEXT:    %0 = load float, float* %arrayidx, align 4
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N12:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N3]]
 
-; CHECK: Node Address:[[N12]]:single-instruction
+; CHECK: Node Address:[[N3]]: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:    %add = fadd float %0, %1
 ; 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]]
+; CHECK-NEXT:  [def-use] to [[N6]]
+
+; CHECK: Node Address:[[N6]]:single-instruction
+; CHECK-NEXT: Instructions:
+; CHECK-NEXT:    store float %add, float* %arrayidx2, align 4
+; CHECK-NEXT: Edges:none!
+
 
 
 ;; 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];
 ;; }
 
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: 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:    %arrayidx = getelementptr inbounds float, float* %b, i64 %i.02
+; CHECK-NEXT:    %inc = add i64 %i.02, 1
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N2:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N14:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N2]]:single-instruction
+; CHECK: Node Address:[[N14]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %0 = load float, float* %arrayidx, align 4
+; 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 [[N1:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N4:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N6:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N7:0x[0-9a-f]*]]
+
+; CHECK: Node Address:[[N7]]:single-instruction
+; CHECK-NEXT: Instructions:
+; 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:    br i1 %cmp, label %test1.for.body, label %for.end.loopexit
+; CHECK-NEXT: Edges:none!
+
+; CHECK: Node Address:[[N6]]:single-instruction
+; CHECK-NEXT: Instructions:
+; CHECK-NEXT:    %arrayidx3 = getelementptr inbounds float, float* %a, i64 %i.02
 ; CHECK-NEXT: Edges:
 ; CHECK-NEXT:  [def-use] to [[N3:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N4:0x[0-9a-f]*]]:single-instruction
+; CHECK: Node Address:[[N4]]: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:    %arrayidx2 = getelementptr inbounds float, float* %a, i64 %sub1
 ; CHECK-NEXT: Edges:
 ; CHECK-NEXT:  [def-use] to [[N3]]
 
-; CHECK: Node Address:[[N6:0x[0-9a-f]*]]:single-instruction
+; CHECK: Node Address:[[N1]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %arrayidx3 = getelementptr inbounds float, float* %a, i64 %i.02
+; CHECK-NEXT:    %arrayidx = getelementptr inbounds float, float* %b, i64 %i.02
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N3]]
+; CHECK-NEXT:  [def-use] to [[N2:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N7:0x[0-9a-f]*]]:single-instruction
+; CHECK: Node Address:[[N2]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %cmp = icmp ult i64 %inc, %sub
+; CHECK-NEXT:    %0 = load float, float* %arrayidx, align 4
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N8:0x[0-9a-f]*]]
-
-; CHECK: Node Address:[[N8]]:single-instruction
-; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    br i1 %cmp, label %test1.for.body, label %for.end.loopexit
-; CHECK-NEXT: Edges:none!
+; CHECK-NEXT:  [def-use] to [[N3]]
 
 ; 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 [[N11:0x[0-9a-f]*]]
 
 ; CHECK: Node Address:[[N12:0x[0-9a-f]*]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %1 = load float, float* %arrayidx2, align 4
 ; CHECK-NEXT: Edges:
 ; CHECK-NEXT:  [def-use] to [[N10]]
 
 ; 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 [[N12]]
 ; CHECK-NEXT:--- end of nodes in pi-block ---
 ; CHECK-NEXT: Edges:none!
 
-; 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 [[N14:0x[0-9a-f]*]]
-
-; CHECK: Node Address:[[N14]]:single-instruction
-; CHECK-NEXT: Instructions:
-; 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 [[N1]]
-; CHECK-NEXT:  [def-use] to [[N4]]
-; CHECK-NEXT:  [def-use] to [[N6]]
-; CHECK-NEXT:  [def-use] to [[N7]]
 
 
 ;; 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
   %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: 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:    %arrayidx = getelementptr inbounds float, float* %b, i64 %i.02
+; CHECK-NEXT:    %inc = add i64 %i.02, 1
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N2:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N13:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N2]]:single-instruction
+; CHECK: Node Address:[[N13]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %0 = load float, float* %arrayidx, align 4
+; CHECK-NEXT:    %i.02 = phi i64 [ %inc, %test2.for.body ], [ 1, %test2.for.body.preheader ]
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N3:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N12]]
+; CHECK-NEXT:--- end of nodes in pi-block ---
+; CHECK-NEXT: Edges:
+; CHECK-NEXT:  [def-use] to [[N1:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N4:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N8:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N9:0x[0-9a-f]*]]
+
+; CHECK: Node Address:[[N9]]:single-instruction
+; CHECK-NEXT: Instructions:
+; CHECK-NEXT:    %cmp = icmp ult i64 %inc, %sub
+; CHECK-NEXT: Edges:
+; CHECK-NEXT:  [def-use] to [[N10:0x[0-9a-f]*]]
+
+; 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:[[N8]]:single-instruction
+; CHECK-NEXT: Instructions:
+; 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: Node Address:[[N4:0x[0-9a-f]*]]:single-instruction
+; CHECK: Node Address:[[N4]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %add1 = 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:    %arrayidx2 = getelementptr inbounds float, float* %a, i64 %add1
 ; CHECK-NEXT: Edges:
 ; CHECK-NEXT:  [def-use] to [[N6:0x[0-9a-f]*]]
 
 ; 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 [[N3]]
-; CHECK-NEXT:  [memory] to [[N7:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N3:0x[0-9a-f]*]]
+; CHECK-NEXT:  [memory] to [[N7]]
 
-; CHECK: Node Address:[[N3]]:single-instruction
+; CHECK: Node Address:[[N1]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %add = fadd float %0, %1
+; CHECK-NEXT:    %arrayidx = getelementptr inbounds float, float* %b, i64 %i.02
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N7]]
+; CHECK-NEXT:  [def-use] to [[N2:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N8:0x[0-9a-f]*]]:single-instruction
+; CHECK: Node Address:[[N2]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %arrayidx3 = getelementptr inbounds float, float* %a, i64 %i.02
+; CHECK-NEXT:    %0 = load float, float* %arrayidx, align 4
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N7]]
+; CHECK-NEXT:  [def-use] to [[N3]]
 
-; 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:[[N9:0x[0-9a-f]*]]:single-instruction
+; CHECK: Node Address:[[N3]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %cmp = icmp ult i64 %inc, %sub
+; 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 [[N7]]
 
-; CHECK: Node Address:[[N10]]:single-instruction
+; CHECK: Node Address:[[N7]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    br i1 %cmp, label %test2.for.body, label %for.end.loopexit
+; CHECK-NEXT:    store float %add, float* %arrayidx3, align 4
 ; 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:    %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: Node Address:[[N3]]:single-instruction
+; 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:    %cmp21 = icmp ult i64 1, %sub
+; CHECK-NEXT:    %inc = add i64 %j.02, 1
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N4:0x[0-9a-f]*]]
-
-; CHECK: Node Address:[[N4]]:single-instruction
-; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    br i1 %cmp21, label %for.body4.preheader, label %for.inc12
-; CHECK-NEXT: Edges:none!
+; CHECK-NEXT:  [def-use] to [[N30:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N5:0x[0-9a-f]*]]:single-instruction
+; CHECK: Node Address:[[N30]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %0 = mul nsw i64 %i.04, %n
+; CHECK-NEXT:    %j.02 = phi i64 [ %inc, %for.body4 ], [ 1, %for.body4.preheader ]
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N6:0x[0-9a-f]*]]
-
-; CHECK: Node Address:[[N6]]:single-instruction
-; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %arrayidx = getelementptr inbounds float, float* %b, i64 %0
+; CHECK-NEXT:  [def-use] to [[N29]]
+; CHECK-NEXT:--- end of nodes in pi-block ---
 ; CHECK-NEXT: Edges:
 ; CHECK-NEXT:  [def-use] to [[N7:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N13:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N16:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N2:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N7]]:single-instruction
+; CHECK: Node Address:[[N13]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %arrayidx5 = getelementptr inbounds float, float* %arrayidx, i64 %j.02
+; CHECK-NEXT:    %sub7 = add i64 %j.02, -1
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N8:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N12:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N8]]: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:    %1 = load float, float* %arrayidx5, align 4
+; CHECK-NEXT:    %inc13 = add i64 %i.04, 1
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N9:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N27:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N10:0x[0-9a-f]*]]:single-instruction
+; CHECK: Node Address:[[N27]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %2 = mul nsw i64 %i.04, %n
+; CHECK-NEXT:    %i.04 = phi i64 [ %inc13, %for.inc12 ], [ 0, %test1.for.cond1.preheader.preheader ]
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N11:0x[0-9a-f]*]]
-
-; CHECK: Node Address:[[N11]]:single-instruction
-; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %arrayidx6 = getelementptr inbounds float, float* %a, i64 %2
+; CHECK-NEXT:  [def-use] to [[N26]]
+; 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 [[N5:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N10:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N14:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N18:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N13:0x[0-9a-f]*]]:single-instruction
+; CHECK: Node Address:[[N18]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %sub7 = add i64 %j.02, -1
+; CHECK-NEXT:    %exitcond = icmp ne i64 %inc13, %n
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N12]]
+; CHECK-NEXT:  [def-use] to [[N19:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N12]]:single-instruction
+; CHECK: Node Address:[[N19]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %arrayidx8 = getelementptr inbounds float, float* %arrayidx6, i64 %sub7
-; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N9]]
+; CHECK-NEXT:    br i1 %exitcond, label %test1.for.cond1.preheader, label %for.end14.loopexit
+; CHECK-NEXT: Edges:none!
 
-; CHECK: Node Address:[[N14:0x[0-9a-f]*]]:single-instruction
+; CHECK: Node Address:[[N14]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %4 = mul nsw i64 %i.04, %n
 ; CHECK-NEXT: Edges:
 ; CHECK-NEXT:  [def-use] to [[N15:0x[0-9a-f]*]]
 
 ; CHECK: Node Address:[[N15]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %arrayidx10 = getelementptr inbounds float, float* %a, i64 %4
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N16:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N16]]
 
 ; CHECK: Node Address:[[N16]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %arrayidx11 = getelementptr inbounds float, float* %arrayidx10, i64 %j.02
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N9]]
+; CHECK-NEXT:  [def-use] to [[N9:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N2]]:single-instruction
+; CHECK: Node Address:[[N10]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %cmp2 = icmp ult i64 %inc, %sub
+; CHECK-NEXT:    %2 = mul nsw i64 %i.04, %n
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N17:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N11:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N17]]:single-instruction
+; CHECK: Node Address:[[N11]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    br i1 %cmp2, label %for.body4, label %for.inc12.loopexit
-; CHECK-NEXT: Edges:none!
+; CHECK-NEXT:    %arrayidx6 = getelementptr inbounds float, float* %a, i64 %2
+; CHECK-NEXT: Edges:
+; CHECK-NEXT:  [def-use] to [[N12]]
 
-; CHECK: Node Address:[[N18:0x[0-9a-f]*]]:single-instruction
+; CHECK: Node Address:[[N12]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %exitcond = icmp ne i64 %inc13, %n
+; CHECK-NEXT:    %arrayidx8 = getelementptr inbounds float, float* %arrayidx6, i64 %sub7
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N19:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N9]]
 
-; CHECK: Node Address:[[N19]]:single-instruction
+; CHECK: Node Address:[[N5]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    br i1 %exitcond, label %test1.for.cond1.preheader, label %for.end14.loopexit
-; CHECK-NEXT: Edges:none!
+; CHECK-NEXT:    %0 = mul nsw i64 %i.04, %n
+; CHECK-NEXT: Edges:
+; CHECK-NEXT:  [def-use] to [[N6:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N20:0x[0-9a-f]*]]:single-instruction
+; CHECK: Node Address:[[N6]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    br label %for.body4
-; CHECK-NEXT: Edges:none!
+; CHECK-NEXT:    %arrayidx = getelementptr inbounds float, float* %b, i64 %0
+; CHECK-NEXT: Edges:
+; CHECK-NEXT:  [def-use] to [[N7]]
 
-; CHECK: Node Address:[[N21:0x[0-9a-f]*]]:single-instruction
+; CHECK: Node Address:[[N7]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    br label %for.inc12
-; CHECK-NEXT: Edges:none!
+; CHECK-NEXT:    %arrayidx5 = getelementptr inbounds float, float* %arrayidx, i64 %j.02
+; CHECK-NEXT: Edges:
+; CHECK-NEXT:  [def-use] to [[N8:0x[0-9a-f]*]]
+
+; 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 [[N9]]
 
 ; 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:    %add = fadd float %1, %3
 ; CHECK-NEXT: Edges:
 ; CHECK-NEXT:  [def-use] to [[N23:0x[0-9a-f]*]]
 
 ; CHECK: Node Address:[[N24:0x[0-9a-f]*]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %3 = load float, float* %arrayidx8, align 4
 ; CHECK-NEXT: Edges:
 ; CHECK-NEXT:  [def-use] to [[N22]]
 
 ; CHECK: Node Address:[[N23]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; 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:[[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: Node Address:[[N21: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 [[N27:0x[0-9a-f]*]]
+; CHECK-NEXT:    br label %for.inc12
+; CHECK-NEXT: Edges:none!
 
-; CHECK: Node Address:[[N27]]:single-instruction
+; CHECK: Node Address:[[N20: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: 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-NEXT:    br label %for.body4
+; CHECK-NEXT: Edges:none!
 
-; 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: Node Address:[[N1:0x[0-9a-f]*]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %inc = add i64 %j.02, 1
+; CHECK-NEXT:    %sub = add i64 %n, -1
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N30:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N2]]
+; CHECK-NEXT:  [def-use] to [[N3:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N30]]:single-instruction
+; CHECK: Node Address:[[N3]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %j.02 = phi i64 [ %inc, %for.body4 ], [ 1, %for.body4.preheader ]
+; CHECK-NEXT:    %cmp21 = icmp ult i64 1, %sub
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N29]]
-; CHECK-NEXT:--- end of nodes in pi-block ---
+; CHECK-NEXT:  [def-use] to [[N4:0x[0-9a-f]*]]
+
+; CHECK: Node Address:[[N4]]:single-instruction
+; CHECK-NEXT: Instructions:
+; CHECK-NEXT:    br i1 %cmp21, label %for.body4.preheader, label %for.inc12
+; CHECK-NEXT: Edges:none!
+
+; 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 [[N7]]
-; CHECK-NEXT:  [def-use] to [[N13]]
-; CHECK-NEXT:  [def-use] to [[N16]]
-; CHECK-NEXT:  [def-use] to [[N2]]
+; CHECK-NEXT:  [def-use] to [[N17:0x[0-9a-f]*]]
 
+; CHECK: Node Address:[[N17]]:single-instruction
+; CHECK-NEXT: Instructions:
+; CHECK-NEXT:    br i1 %cmp2, label %for.body4, label %for.inc12.loopexit
+; CHECK-NEXT: Edges:none!
 
 
 ;; 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: Node Address:[[PI1: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:    %sub = add i64 %n, -1
+; 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:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N13:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N18:0x[0-9a-f]*]]
 ; CHECK-NEXT:  [def-use] to [[N2:0x[0-9a-f]*]]
-; CHECK-NEXT:  [def-use] to [[N3:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N3]]:single-instruction
+; CHECK: Node Address:[[N13]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %cmp21 = icmp ult i64 1, %sub
+; CHECK-NEXT:    %add7 = add i64 %j.02, 1
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N4:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N12:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N4]]:single-instruction
+; 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:    br i1 %cmp21, label %for.body4.preheader, label %for.inc12
-; CHECK-NEXT: Edges:none!
+; CHECK-NEXT:    %inc13 = add i64 %i.04, 1
+; CHECK-NEXT: Edges:
+; CHECK-NEXT:  [def-use] to [[N26:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N5:0x[0-9a-f]*]]:single-instruction
+; CHECK: Node Address:[[N26]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %0 = mul nsw i64 %i.04, %n
+; CHECK-NEXT:    %i.04 = phi i64 [ %inc13, %for.inc12 ], [ 0, %test2.for.cond1.preheader.preheader ]
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N6:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N25]]
+; CHECK-NEXT:--- end of nodes in pi-block ---
+; CHECK-NEXT: Edges:
+; CHECK-NEXT:  [def-use] to [[N5:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N10:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N16:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N20:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N6]]:single-instruction
+; CHECK: Node Address:[[N20]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %arrayidx = getelementptr inbounds float, float* %b, i64 %0
+; CHECK-NEXT:    %exitcond = icmp ne i64 %inc13, %n
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N7:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N21:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N7]]:single-instruction
+; CHECK: Node Address:[[N21]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %arrayidx5 = getelementptr inbounds float, float* %arrayidx, i64 %j.02
+; CHECK-NEXT:    br i1 %exitcond, label %test2.for.cond1.preheader, label %for.end14.loopexit
+; CHECK-NEXT: Edges:none!
+
+; CHECK: Node Address:[[N16]]:single-instruction
+; CHECK-NEXT: Instructions:
+; CHECK-NEXT:    %4 = mul nsw i64 %i.04, %n
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N8:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N17:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N8]]:single-instruction
+; CHECK: Node Address:[[N17]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %1 = load float, float* %arrayidx5, align 4
+; CHECK-NEXT:    %arrayidx10 = getelementptr inbounds float, float* %a, i64 %4
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N9:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N18]]
 
-; CHECK: Node Address:[[N10:0x[0-9a-f]*]]: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 [[N15:0x[0-9a-f]*]]
+
+; CHECK: Node Address:[[N10]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %2 = mul nsw i64 %i.04, %n
 ; CHECK-NEXT: Edges:
 ; CHECK-NEXT:  [def-use] to [[N11:0x[0-9a-f]*]]
 
 ; 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 [[N12:0x[0-9a-f]*]]
-
-; 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 [[N12]]
 
 ; 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 [[N14:0x[0-9a-f]*]]
 
 ; 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 [[N9]]
-; CHECK-NEXT:  [memory] to [[N15:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N9:0x[0-9a-f]*]]
+; CHECK-NEXT:  [memory] to [[N15]]
 
-; CHECK: Node Address:[[N9]]:single-instruction
+; CHECK: Node Address:[[N5]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %add = fadd float %1, %3
+; CHECK-NEXT:    %0 = mul nsw i64 %i.04, %n
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N15]]
+; CHECK-NEXT:  [def-use] to [[N6:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N16:0x[0-9a-f]*]]:single-instruction
+; CHECK: Node Address:[[N6]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %4 = mul nsw i64 %i.04, %n
+; CHECK-NEXT:    %arrayidx = getelementptr inbounds float, float* %b, i64 %0
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N17:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N7]]
 
-; CHECK: Node Address:[[N17]]:single-instruction
+; CHECK: Node Address:[[N7]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %arrayidx10 = getelementptr inbounds float, float* %a, i64 %4
+; CHECK-NEXT:    %arrayidx5 = getelementptr inbounds float, float* %arrayidx, i64 %j.02
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N18:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N8:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N18]]:single-instruction
+; CHECK: Node Address:[[N8]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %arrayidx11 = getelementptr inbounds float, float* %arrayidx10, i64 %j.02
+; CHECK-NEXT:    %1 = load float, float* %arrayidx5, align 4
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N15]]
-
-; CHECK: Node Address:[[N15]]:single-instruction
-; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    store float %add, float* %arrayidx11, align 4
-; CHECK-NEXT: Edges:none!
+; CHECK-NEXT:  [def-use] to [[N9]]
 
-; CHECK: Node Address:[[N2]]:single-instruction
+; CHECK: Node Address:[[N9]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %cmp2 = icmp ult i64 %inc, %sub
+; CHECK-NEXT:    %add = fadd float %1, %3
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N19:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N15]]
 
-; CHECK: Node Address:[[N19]]:single-instruction
+; CHECK: Node Address:[[N15]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    br i1 %cmp2, label %for.body4, label %for.inc12.loopexit
+; CHECK-NEXT:    store float %add, float* %arrayidx11, align 4
 ; CHECK-NEXT: Edges:none!
 
-; 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 [[N21:0x[0-9a-f]*]]
-
-; CHECK: Node Address:[[N21]]:single-instruction
+; CHECK: Node Address:[[N23:0x[0-9a-f]*]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    br i1 %exitcond, label %test2.for.cond1.preheader, label %for.end14.loopexit
+; CHECK-NEXT:    br label %for.inc12
 ; CHECK-NEXT: Edges:none!
 
 ; 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:[[N23:0x[0-9a-f]*]]:single-instruction
+; CHECK: Node Address:[[N1:0x[0-9a-f]*]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    br label %for.inc12
-; CHECK-NEXT: Edges:none!
+; CHECK-NEXT:    %sub = add i64 %n, -1
+; CHECK-NEXT: Edges:
+; CHECK-NEXT:  [def-use] to [[N2]]
+; CHECK-NEXT:  [def-use] to [[N3:0x[0-9a-f]*]]
 
-; 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: Node Address:[[N3]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %inc13 = add i64 %i.04, 1
+; CHECK-NEXT:    %cmp21 = icmp ult i64 1, %sub
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N26:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N4:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N26]]:single-instruction
+; CHECK: Node Address:[[N4]]: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-NEXT:    br i1 %cmp21, label %for.body4.preheader, label %for.inc12
+; CHECK-NEXT: Edges:none!
 
-; 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: Node Address:[[N2]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %inc = add i64 %j.02, 1
+; CHECK-NEXT:    %cmp2 = icmp ult i64 %inc, %sub
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N29:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N19:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N29]]:single-instruction
+; CHECK: Node Address:[[N19]]: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]]
+; CHECK-NEXT:    br i1 %cmp2, label %for.body4, label %for.inc12.loopexit
+; CHECK-NEXT: Edges:none!
 
 
 ;; 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];
 ;; }

 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:[[ROOT:0x[0-9a-f]*]]:root
 ; CHECK-NEXT: Edges:
 ; 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 ]
 
+; CHECK: Node Address:[[N1]]:pi-block
+; CHECK: %i2.03 = phi i64 [ 0, %for.body.lr.ph ], [ %inc2, %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;
 ;;   }
 ;; }