[DDG] Data Dependence Graph - Ordinals

[bmahjour]

Summary

This patch associates ordinal numbers to the DDG Nodes allowing the builder to order nodes within a pi-block in program order. The algorithm works by simply assuming the order in which the BBList is fed into the builder. The builder already relies on the blocks being in program order so that it can compute the dependencies correctly. Similarly the order of instructions in their parent basic blocks determine their program order.

[Meinersbur]

I do not understand why the ordinals are necessary. For deterministic behavior, the deterministic iteration order over blocks and instructions should already ensure that (unless you are iterating over DenseMaps, which does not seem the case and is easily fixed). If for correctness, do you have an illustrative example when this would be critical?

llvm/lib/Analysis/DependenceGraphBuilder.cpp

57

Did you consider string the node ordinal in the Node directly instead of using a lookup table?

[bmahjour]

In D70986#1771141, @Meinersbur wrote:

I do not understand why the ordinals are necessary. For deterministic behavior, the deterministic iteration order over blocks and instructions should already ensure that (unless you are iterating over DenseMaps, which does not seem the case and is easily fixed). If for correctness, do you have an illustrative example when this would be critical?

The nodes in a pi-block cannot be topologically sorted since they form a cycle. The ordinals help us put them in their original program order so as to preserve correctness. For example consider this case:

for (int i = 0; i < n-1; i++) {
  A[i] = B[i];
  B[i+1] = A[i];
}

There will be a pi-block consisting of all load and stores in the loop, and they cannot be sorted in the order of data dependence. We do not want to inadvertently change it to:

for (int i = 0; i < n-1; i++) {
  B[i+1] = A[i];
  A[i] = B[i];
}

llvm/lib/Analysis/DependenceGraphBuilder.cpp

57

Ordinal numbers take up space and are only needed during construction of the graph. The users of DDG don't need the ordinal, so I decided to save space and use the maps instead. The maps get cleared as soon as we are done with pi-block creation.

[bmahjour]

ping

[Meinersbur]

In D70986#1771710, @bmahjour wrote:

The nodes in a pi-block cannot be topologically sorted since they form a cycle. The ordinals help us put them in their original program order so as to preserve correctness. For example consider this case:

for (int i = 0; i < n-1; i++) {
  A[i] = B[i];
  B[i+1] = A[i];
}

There will be a pi-block consisting of all load and stores in the loop, and they cannot be sorted in the order of data dependence. We do not want to inadvertently change it to:

for (int i = 0; i < n-1; i++) {
  B[i+1] = A[i];
  A[i] = B[i];
}

What would cause the order of nodes in a pi-node to change? As it's not topologically sorted, wouldn't the order stay the order in which they were added to NodeList?

[bmahjour]

What would cause the order of nodes in a pi-node to change? As it's not topologically sorted, wouldn't the order stay the order in which they were added to NodeList?

The order is at the mercy of SCCIterator. For example if you look at the first pi-block node in basic-a.ll, you'll notice that prior to this change the %inc = add i64 %i.02, 1 was placed ahead of %i.02 = phi .

[Meinersbur]

In D70986#1790305, @bmahjour wrote:

The order is at the mercy of SCCIterator. For example if you look at the first pi-block node in basic-a.ll, you'll notice that prior to this change the %inc = add i64 %i.02, 1 was placed ahead of %i.02 = phi .

I see. Could you add that as a comment to either computeInstructionOrdinals and/or the invocation of llvm::sort.

LGTM

[bmahjour]

In D70986#1790336, @Meinersbur wrote:

In D70986#1790305, @bmahjour wrote:

The order is at the mercy of SCCIterator. For example if you look at the first pi-block node in basic-a.ll, you'll notice that prior to this change the %inc = add i64 %i.02, 1 was placed ahead of %i.02 = phi .

I see. Could you add that as a comment to either computeInstructionOrdinals and/or the invocation of llvm::sort.

Done.

llvm/include/llvm/Analysis/DependenceGraphBuilder.h

public:
   /// that use dependence graphs.
   ///
   /// The algorithmic complexity of this implementation is O(V^2 * I^2), where V
   /// is the number of vertecies (nodes) and I is the number of instructions in
   /// each node. The total number of instructions, N, is equal to V * I,
   /// therefore the worst-case time complexity is O(N^2). The average time
   /// complexity is O((N^2)/2).
   void populate() {
+    computeInstructionOrdinals();
     createFineGrainedNodes();
     createDefUseEdges();
     createMemoryDependencyEdges();
     createAndConnectRootNode();
     createPiBlocks();
     sortNodesTopologically();
   }
 
+  /// Compute ordinal numbers for each instruction and store them in a map for
+  /// future look up. These ordinals are used to compute node ordinals which are
+  /// in turn used to order nodes that are part of a cycle.
+  /// Instruction ordinals are assigned based on lexical program order.
+  void computeInstructionOrdinals();
+
   /// Create fine grained nodes. These are typically atomic nodes that
   /// consist of a single instruction.
   void createFineGrainedNodes();
 
   /// Analyze the def-use chains and create edges from the nodes containing
   /// definitions to the nodes containing the uses.
   void createDefUseEdges();
 
protected:
 
   /// Deallocate memory of node \p N.
   virtual void destroyNode(NodeType &N) { delete &N; }
 
   /// Return true if creation of pi-blocks are supported and desired,
   /// and false otherwise.
   virtual bool shouldCreatePiBlocks() const { return true; }
 
+  /// Given an instruction \p I return its associated ordinal number.
+  size_t getOrdinal(Instruction &I) {
+    assert(InstOrdinalMap.find(&I) != InstOrdinalMap.end() &&
+           "No ordinal computed for this instruction.");
+    return InstOrdinalMap[&I];
+  }
+
+  /// Given a node \p N return its associated ordinal number.
+  size_t getOrdinal(NodeType &N) {
+    assert(NodeOrdinalMap.find(&N) != NodeOrdinalMap.end() &&
+           "No ordinal computed for this node.");
+    return NodeOrdinalMap[&N];
+  }
+
   /// Map types to map instructions to nodes used when populating the graph.
   using InstToNodeMap = DenseMap<Instruction *, NodeType *>;
 
+  /// Map Types to map instruction/nodes to an ordinal number.
+  using InstToOrdinalMap = DenseMap<Instruction *, size_t>;
+  using NodeToOrdinalMap = DenseMap<NodeType *, size_t>;
+
   /// Reference to the graph that gets built by a concrete implementation of
   /// this builder.
   GraphType &Graph;
 
   /// Dependence information used to create memory dependence edges in the
   /// graph.
   DependenceInfo &DI;
 
   /// The list of basic blocks to consider when building the graph.
   const BasicBlockListType &BBList;
 
   /// A mapping from instructions to the corresponding nodes in the graph.
   InstToNodeMap IMap;
+
+  /// A mapping from each instruction to an ordinal number. This map is used to 
+  /// populate the \p NodeOrdinalMap.
+  InstToOrdinalMap InstOrdinalMap;
+
+  /// A mapping from nodes to an ordinal number. This map is used to sort nodes
+  /// in a pi-block based on program order.
+  NodeToOrdinalMap NodeOrdinalMap;
 };
 
 } // namespace llvm
 
 #endif // LLVM_ANALYSIS_DEPENDENCE_GRAPH_BUILDER_H

llvm/lib/Analysis/DependenceGraphBuilder.cpp

 
 using InstructionListType = SmallVector<Instruction *, 2>;
 
 //===--------------------------------------------------------------------===//
 // AbstractDependenceGraphBuilder implementation
 //===--------------------------------------------------------------------===//
 
 template <class G>
+void AbstractDependenceGraphBuilder<G>::computeInstructionOrdinals() {
+  
+  // The BBList is expected to be in program order.
+  size_t NextOrdinal = 1;
+  for (auto *BB : BBList)
+    for (auto &I : *BB)
+      InstOrdinalMap.insert(std::make_pair(&I, NextOrdinal++));
+}
+
+template <class G>
 void AbstractDependenceGraphBuilder<G>::createFineGrainedNodes() {
   ++TotalGraphs;
   assert(IMap.empty() && "Expected empty instruction map at start");
   for (BasicBlock *BB : BBList)
     for (Instruction &I : *BB) {
       auto &NewNode = createFineGrainedNode(I);
       IMap.insert(std::make_pair(&I, &NewNode));
+      NodeOrdinalMap.insert(std::make_pair(&NewNode, getOrdinal(I)));
       ++TotalFineGrainedNodes;
     }
 }
 
 template <class G>
 void AbstractDependenceGraphBuilder<G>::createAndConnectRootNode() {
   // Create a root node that connects to every connected component of the graph.
   // This is done to allow graph iterators to visit all the disjoint components
for (auto &SCC : make_range(scc_begin(&Graph), scc_end(&Graph))) {
     if (SCC.size() > 1)
       ListOfSCCs.emplace_back(SCC.begin(), SCC.end());
   }
 
   for (NodeListType &NL : ListOfSCCs) {
     LLVM_DEBUG(dbgs() << "Creating pi-block node with " << NL.size()
                       << " nodes in it.\n");
 
+    // Sort the list of nodes that will be placed in the pi-block based on
+    // ordinal numbers computed earlier.
+    llvm::sort(NL, [&](NodeType *LHS, NodeType *RHS) {
+      return getOrdinal(*LHS) < getOrdinal(*RHS);
+    });
+
     NodeType &PiNode = createPiBlock(NL);
     ++TotalPiBlockNodes;
 
     // Build a set to speed up the lookup for edges whose targets
     // are inside the SCC.
     SmallPtrSet<NodeType *, 4> NodesInSCC(NL.begin(), NL.end());
 
     // We have the set of nodes in the SCC. We go through the set of nodes
for (NodeType *N : Graph) {
         reconnectEdges(N, SCCNode, &PiNode, Direction::Incoming);
 
         // Process edges that are coming out of the pi-block node.
         reconnectEdges(SCCNode, N, &PiNode, Direction::Outgoing);
       }
     }
   }
 
+  // Ordinal maps are no longer needed.
+  InstOrdinalMap.clear();
+  NodeOrdinalMap.clear();
+  
   LLVM_DEBUG(dbgs() << "==== End of Creation of Pi-Blocks ===\n");
 }
 
 template <class G> void AbstractDependenceGraphBuilder<G>::createDefUseEdges() {
   for (NodeType *N : Graph) {
     InstructionListType SrcIList;
     N->collectInstructions([](const Instruction *I) { return true; }, SrcIList);
 

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:[[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: Node Address:[[N1:0x[0-9a-f]*]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %inc = add i64 %i.02, 1
+; CHECK-NEXT:    %i.02 = phi i64 [ %inc, %test1.for.body ], [ 0, %test1.for.body.preheader ]
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N11:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N2:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N11]]:single-instruction
+; CHECK: Node Address:[[N2]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %i.02 = phi i64 [ %inc, %test1.for.body ], [ 0, %test1.for.body.preheader ]
+; CHECK-NEXT:    %inc = add i64 %i.02, 1
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N10]]
+; CHECK-NEXT:  [def-use] to [[N1]]
 ; 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-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:[[N7]]:single-instruction
+; CHECK: Node Address:[[N5]]: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-NEXT:  [def-use] to [[N6:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N8]]:single-instruction
+; CHECK: Node Address:[[N6]]: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: Node Address:[[N4]]: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-NEXT:  [def-use] to [[N7:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N1]]:single-instruction
+; CHECK: Node Address:[[N3]]: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-NEXT:  [def-use] to [[N8:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N2]]:single-instruction
+; CHECK: Node Address:[[N8]]: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 [[N9:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N4:0x[0-9a-f]*]]:single-instruction
+; CHECK: Node Address:[[N10: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-NEXT:  [def-use] to [[N9]]
 
-; CHECK: Node Address:[[N3]]:single-instruction
+; CHECK: Node Address:[[N9]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %add = fadd float %0, %conv
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N5]]
+; CHECK-NEXT:  [def-use] to [[N7]]
 
-; CHECK: Node Address:[[N5]]:single-instruction
+; CHECK: Node Address:[[N7]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    store float %add, float* %arrayidx1, align 4
 ; CHECK-NEXT: Edges:none!
 
 
 ;; No memory dependencies.
 ;; void test1(unsigned long n, float * restrict a, float * restrict b) {
 ;;  for (unsigned long i = 0; i < n; i++)
for.end:                                          ; preds = %test1.for.body, %entry
   ret void
 }
 
 
 ; CHECK-LABEL: 'DDG' for loop 'test2.for.body':
 
 ; 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: Node Address:[[N1:0x[0-9a-f]*]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %inc = add i64 %i.02, 1
+; CHECK-NEXT:    %i.02 = phi i64 [ %inc, %test2.for.body ], [ 0, %test2.for.body.preheader ]
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N12:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N2:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N12]]:single-instruction
+; CHECK: Node Address:[[N2]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %i.02 = phi i64 [ %inc, %test2.for.body ], [ 0, %test2.for.body.preheader ]
+; CHECK-NEXT:    %inc = add i64 %i.02, 1
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N11]]
+; CHECK-NEXT:  [def-use] to [[N1]]
 ; 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 [[N3: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-NEXT:  [def-use] to [[N5:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N6:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N8]]:single-instruction
+; CHECK: Node Address:[[N6]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %exitcond = icmp ne i64 %inc, %n
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N9:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N7:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N9]]:single-instruction
+; CHECK: Node Address:[[N7]]: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:[[N7]]:single-instruction
+; CHECK: Node Address:[[N5]]: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:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N8:0x[0-9a-f]*]]
 
 ; CHECK: Node Address:[[N4]]: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-NEXT:  [def-use] to [[N9:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N5]]:single-instruction
+; CHECK: Node Address:[[N9]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %1 = load float, float* %arrayidx1, align 4
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N3:0x[0-9a-f]*]]
-; CHECK-NEXT:  [memory] to [[N6]]
+; CHECK-NEXT:  [def-use] to [[N20:0x[0-9a-f]*]]
+; CHECK-NEXT:  [memory] to [[N8]]
 
-; CHECK: Node Address:[[N1]]:single-instruction
+; CHECK: Node Address:[[N3]]: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-NEXT:  [def-use] to [[N10:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N2]]:single-instruction
+; CHECK: Node Address:[[N10]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %0 = load float, float* %arrayidx, align 4
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N3]]
+; CHECK-NEXT:  [def-use] to [[N20]]
 
-; CHECK: Node Address:[[N3]]:single-instruction
+; CHECK: Node Address:[[N20]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %add = fadd float %0, %1
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N6]]
+; CHECK-NEXT:  [def-use] to [[N8]]
 
-; CHECK: Node Address:[[N6]]:single-instruction
+; CHECK: Node Address:[[N8]]: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) {
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:[[N9:0x[0-9a-f]*]]:pi-block
+; CHECK: Node Address:[[N1: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: Node Address:[[N2:0x[0-9a-f]*]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %inc = add i64 %i.02, 1
+; CHECK-NEXT:    %i.02 = phi i64 [ %inc, %test1.for.body ], [ 1, %test1.for.body.preheader ]
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N14:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N3:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N14]]:single-instruction
+; CHECK: Node Address:[[N3]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %i.02 = phi i64 [ %inc, %test1.for.body ], [ 1, %test1.for.body.preheader ]
+; CHECK-NEXT:    %inc = add i64 %i.02, 1
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N13]]
+; CHECK-NEXT:  [def-use] to [[N2]]
 ; 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 [[N5: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-NEXT:  [def-use] to [[N9:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N4]]:single-instruction
+; CHECK: Node Address:[[N5]]: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-NEXT:  [def-use] to [[N10:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N5]]:single-instruction
+; CHECK: Node Address:[[N10]]: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-NEXT:  [def-use] to [[N9]]
 
-; CHECK: Node Address:[[N1]]:single-instruction
+; 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 [[N2:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N11:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N2]]:single-instruction
+; CHECK: Node Address:[[N11]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %0 = load float, float* %arrayidx, align 4
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N3]]
+; CHECK-NEXT:  [def-use] to [[N9]]
 
-; CHECK: Node Address:[[N3]]:pi-block
+; CHECK: Node Address:[[N9]]:pi-block
 ; CHECK-NEXT: --- start of nodes in pi-block ---
-; CHECK: Node Address:[[N10:0x[0-9a-f]*]]:single-instruction
+; CHECK: Node Address:[[N12:0x[0-9a-f]*]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %add = fadd float %0, %1
+; CHECK-NEXT:    %1 = load float, float* %arrayidx2, align 4
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N11:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N13:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N12:0x[0-9a-f]*]]:single-instruction
+; CHECK: Node Address:[[N13]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %1 = load float, float* %arrayidx2, align 4
+; CHECK-NEXT:    %add = fadd float %0, %1
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N10]]
+; 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:    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!
 
 
test1.for.body:                                         ; preds = %entry, %test1.for.body
   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:[[N11:0x[0-9a-f]*]]:pi-block
+; CHECK: Node Address:[[N1: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: Node Address:[[N2:0x[0-9a-f]*]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %inc = add i64 %i.02, 1
+; CHECK-NEXT:    %i.02 = phi i64 [ %inc, %test2.for.body ], [ 1, %test2.for.body.preheader ]
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N13:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N3:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N13]]:single-instruction
+; CHECK: Node Address:[[N3]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %i.02 = phi i64 [ %inc, %test2.for.body ], [ 1, %test2.for.body.preheader ]
+; CHECK-NEXT:    %inc = add i64 %i.02, 1
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N12]]
+; CHECK-NEXT:  [def-use] to [[N2]]
 ; 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-NEXT:  [def-use] to [[N5: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:[[N9]]:single-instruction
+; 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 [[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 %cmp, label %test2.for.body, label %for.end.loopexit
 ; CHECK-NEXT: Edges:none!
 
-; CHECK: Node Address:[[N8]]:single-instruction
+; 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 [[N7:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N9:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N4]]:single-instruction
+; CHECK: Node Address:[[N5]]: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-NEXT:  [def-use] to [[N10:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N5]]:single-instruction
+; CHECK: Node Address:[[N10]]: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-NEXT:  [def-use] to [[N11:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N6]]:single-instruction
+; CHECK: Node Address:[[N11]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %1 = load float, float* %arrayidx2, align 4
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N3:0x[0-9a-f]*]]
-; CHECK-NEXT:  [memory] to [[N7]]
+; CHECK-NEXT:  [def-use] to [[N12:0x[0-9a-f]*]]
+; CHECK-NEXT:  [memory] to [[N9]]
 
-; CHECK: Node Address:[[N1]]:single-instruction
+; 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 [[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: Edges:
-; CHECK-NEXT:  [def-use] to [[N3]]
+; CHECK-NEXT:  [def-use] to [[N12]]
 
 
-; CHECK: Node Address:[[N3]]:single-instruction
+; CHECK: Node Address:[[N12]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %add = fadd float %0, %1
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N7]]
+; CHECK-NEXT:  [def-use] to [[N9]]
 
-; CHECK: Node Address:[[N7]]:single-instruction
+; CHECK: Node Address:[[N9]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    store float %add, float* %arrayidx3, align 4
 ; CHECK-NEXT: Edges:none!
 
 
 ;; 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++)

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

 }
 
 
 
 ; CHECK-LABEL: 'DDG' for loop 'test2.for.cond1.preheader':
 
 ; 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: Node Address:[[N1:0x[0-9a-f]*]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %inc = add i64 %j.02, 1
+; CHECK-NEXT:    %j.02 = phi i64 [ %inc, %for.body4 ], [ 1, %for.body4.preheader ]
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N29:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N2:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N29]]:single-instruction
+; CHECK: Node Address:[[N2]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %j.02 = phi i64 [ %inc, %for.body4 ], [ 1, %for.body4.preheader ]
+; CHECK-NEXT:    %inc = add i64 %j.02, 1
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N28]]
+; CHECK-NEXT:  [def-use] to [[N1]]
 ; 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-NEXT:  [def-use] to [[N4:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N5:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N6:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N13]]:single-instruction
+; CHECK: Node Address:[[N4]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %add7 = add i64 %j.02, 1
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N12:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N7:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N24:0x[0-9a-f]*]]:pi-block
+; CHECK: Node Address:[[N8: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:[[N9:0x[0-9a-f]*]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %inc13 = add i64 %i.04, 1
+; CHECK-NEXT:    %i.04 = phi i64 [ %inc13, %for.inc12 ], [ 0, %test2.for.cond1.preheader.preheader ]
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N26:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N10:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N26]]:single-instruction
+; CHECK: Node Address:[[N10]]:single-instruction
 ; CHECK-NEXT: Instructions:
-; CHECK-NEXT:    %i.04 = phi i64 [ %inc13, %for.inc12 ], [ 0, %test2.for.cond1.preheader.preheader ]
+; CHECK-NEXT:    %inc13 = add i64 %i.04, 1
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N25]]
+; CHECK-NEXT:  [def-use] to [[N9]]
 ; 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-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:[[N20]]:single-instruction
+; CHECK: Node Address:[[N14]]: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-NEXT:  [def-use] to [[N15:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N21]]:single-instruction
+; CHECK: Node Address:[[N15]]: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:[[N16]]:single-instruction
+; CHECK: Node Address:[[N13]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %4 = mul nsw i64 %i.04, %n
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N17:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N16:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N17]]:single-instruction
+; CHECK: Node Address:[[N16]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %arrayidx10 = getelementptr inbounds float, float* %a, i64 %4
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N18]]
+; CHECK-NEXT:  [def-use] to [[N5]]
 
-; CHECK: Node Address:[[N18]]:single-instruction
+; CHECK: Node Address:[[N5]]: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-NEXT:  [def-use] to [[N17:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N10]]:single-instruction
+; CHECK: Node Address:[[N12]]: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-NEXT:  [def-use] to [[N18:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N11]]:single-instruction
+; CHECK: Node Address:[[N18]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %arrayidx6 = getelementptr inbounds float, float* %a, i64 %2
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N12]]
+; CHECK-NEXT:  [def-use] to [[N7]]
 
-; CHECK: Node Address:[[N12]]:single-instruction
+; CHECK: Node Address:[[N7]]: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-NEXT:  [def-use] to [[N19:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N14]]:single-instruction
+; CHECK: Node Address:[[N19]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %3 = load float, float* %arrayidx8, align 4
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N9:0x[0-9a-f]*]]
-; CHECK-NEXT:  [memory] to [[N15]]
+; CHECK-NEXT:  [def-use] to [[N20:0x[0-9a-f]*]]
+; CHECK-NEXT:  [memory] to [[N17]]
 
-; CHECK: Node Address:[[N5]]:single-instruction
+; CHECK: Node Address:[[N11]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %0 = mul nsw i64 %i.04, %n
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N6:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N21:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N6]]:single-instruction
+; CHECK: Node Address:[[N21]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %arrayidx = getelementptr inbounds float, float* %b, i64 %0
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N7]]
+; CHECK-NEXT:  [def-use] to [[N3]]
 
-; CHECK: Node Address:[[N7]]:single-instruction
+; CHECK: Node Address:[[N3]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; 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-NEXT:  [def-use] to [[N22:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N8]]:single-instruction
+; CHECK: Node Address:[[N22]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %1 = load float, float* %arrayidx5, align 4
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N9]]
+; CHECK-NEXT:  [def-use] to [[N20]]
 
-; CHECK: Node Address:[[N9]]:single-instruction
+; CHECK: Node Address:[[N20]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %add = fadd float %1, %3
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N15]]
+; CHECK-NEXT:  [def-use] to [[N17]]
 
-; CHECK: Node Address:[[N15]]:single-instruction
+; CHECK: Node Address:[[N17]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    store float %add, float* %arrayidx11, align 4
 ; CHECK-NEXT: Edges:none!
 
 ; 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:[[N22:0x[0-9a-f]*]]:single-instruction
+; CHECK: Node Address:[[N24:0x[0-9a-f]*]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    br label %for.body4
 ; CHECK-NEXT: Edges:none!
 
-; CHECK: Node Address:[[N1:0x[0-9a-f]*]]:single-instruction
+; CHECK: Node Address:[[N25: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]]
-; CHECK-NEXT:  [def-use] to [[N3:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N6]]
+; CHECK-NEXT:  [def-use] to [[N26:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N3]]:single-instruction
+; CHECK: Node Address:[[N26]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %cmp21 = icmp ult i64 1, %sub
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N4:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N27:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N4]]:single-instruction
+; CHECK: Node Address:[[N27]]: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: Node Address:[[N6]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %cmp2 = icmp ult i64 %inc, %sub
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N19:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N28:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N19]]:single-instruction
+; CHECK: Node Address:[[N28]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; 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.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