[DDG] Data Dependence Graph - Pi Block

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

    Authored By: bmahjour

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

    Reviewed By: Meinersbur

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

    Tag: #llvm

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

4 files changed, 342 insertions, 301 deletions

diff --git a/llvm/test/Analysis/DDG/basic-a.ll b/llvm/test/Analysis/DDG/basic-a.ll
index 4c05259a886..920e71f6717 100644
--- a/llvm/test/Analysis/DDG/basic-a.ll
+++ b/llvm/test/Analysis/DDG/basic-a.ll
@@ -3,65 +3,70 @@
 ; 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++)
@@ -93,73 +98,78 @@ for.end:                                          ; preds = %test1.for.body, %en
 ; 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++)
diff --git a/llvm/test/Analysis/DDG/basic-b.ll b/llvm/test/Analysis/DDG/basic-b.ll
index 2a90d028a6f..f83f7fe92f3 100644
--- a/llvm/test/Analysis/DDG/basic-b.ll
+++ b/llvm/test/Analysis/DDG/basic-b.ll
@@ -3,78 +3,87 @@
 ; 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.
@@ -107,83 +116,86 @@ for.end:                                          ; preds = %test1.for.body, %en
   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) {
diff --git a/llvm/test/Analysis/DDG/basic-loopnest.ll b/llvm/test/Analysis/DDG/basic-loopnest.ll
index a2abbf8c09b..aded488ef23 100644
--- a/llvm/test/Analysis/DDG/basic-loopnest.ll
+++ b/llvm/test/Analysis/DDG/basic-loopnest.ll
@@ -4,169 +4,181 @@
 ; 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]]
 
 
 
@@ -222,170 +234,179 @@ for.end14:                                        ; preds = %for.inc12, %entry
 ; 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++)
diff --git a/llvm/test/Analysis/DDG/root-node.ll b/llvm/test/Analysis/DDG/root-node.ll
index 1175796e3c2..34d6437ef9c 100644
--- a/llvm/test/Analysis/DDG/root-node.ll
+++ b/llvm/test/Analysis/DDG/root-node.ll
@@ -2,18 +2,16 @@
 
 ; 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.