[DDG] Data Dependence Graph - Graph Simplification

[bmahjour]

Summary

This is the last functional patch affecting the representation of DDG. Here we try to simplify the DDG to reduce the number of nodes and edges by iteratively merging pairs of nodes that satisfy the following conditions, until no such pair can be identified. A pair of nodes consisting of a and b can be merged if:

1. the only edge from a is a def-use edge to b and
2. the only edge to b is a def-use edge from a and
3. there is no cyclic edge from b to a and
4. all instructions in a and b belong to the same basic block and
5. both a and b are simple (single or multi instruction) nodes.

These criteria allow us to fold many uninteresting def-use edges that commonly exist in the graph while avoiding the risk of introducing dependencies that didn't exist before. For example consider a graph G defined as: { (a)->(b), (b)->(c), (a)->(d) }
The edge in between (b) and (c) can be folded to give us { (a)->(bc), (a)->(d) }
Note that folding any of the other edges is not legal. For example if the edge between (a) and (b) is folded, then a new (incorrect) dependence between (b) and (d) is introduced due to the dependency between (a) and (d).

[Meinersbur]

llvm/include/llvm/Analysis/DDG.h

394

[style] Function names should start with the verb: areMergableNodes

llvm/lib/Analysis/DDG.cpp

278–281

[nit] Looks line an anti-pattern. Did you consider

return SimpleSrc->getLastInstruction()->getParent() == SimpleTgt->getFirstInstruction()->getParent();

or add an empty line before return true to make it distinct as the "all tests passed" action?

llvm/lib/Analysis/DependenceGraphBuilder.cpp

423

[serious] This is an O(V^2*max(E)) worst case algorithm (hasEdgeTo is a linear search) reinvoked over each fixpoint round, i.e. potentially quadratic (maybe less because of the EC.second > 1 bailout and fixpoint probably not linear over node count). To count the number of incoming edges, iterate over all edges, lookup the target node in CandidateSrcNodes and increase its counter. That's just O(E). To further reduce computation time, CandidateSrcNodes could be updated when nodes are merged instead of recomputing it.

452

I wonder whether a fixpoint is even necessary. In what cases would we need a second round?

[bmahjour]

llvm/lib/Analysis/DependenceGraphBuilder.cpp

423

The DirectedGraph implementation does not hold a list of all edges (to save space), so we first need to compute it. Note that in the worst case (where the graph is complete) walking over all edges has O(V^2) complexity, so the whole algorithm will have O(V^2 + V) complexity.

Note also that the CandidateSrcNodes map is a map from the candidate source nodes (not the target nodes), so we would need another map to store the incoming edge count of all nodes and then cross reference it as we walk CandidateSrcNodes and update it.

We would need to introduce a map and a list with worst-case space complexities O(V) and O(V^2) respectively. Having said that in the case of complete graphs, we have max(E) == V so in comparison with the above algorithm, it would still be an improvement in terms of computation.

If you still think the additional memory complexity increase is justified, I can change it as described.

452

It's meant to catch cases like this:

{(a)->(b), (b)->(c), (c)->(d), (e)->(d)}

the goal is to turn it into:

{(a,b,c)->(d), (e)->(d)}

I think I can get rid of the fixpoint algorithm by making use of the CandidateSrcNodes as a worklist. I'll post an update soon.

[Meinersbur]

llvm/lib/Analysis/DependenceGraphBuilder.cpp

423

I'd expect a typical dependence graph to be a sequence of use-def chains: a->b->c->d->e->f->... . This would already have O(V) for your algorithm as CandidateSrcNodes contains all nodes except the last. Compete graphs should be collapsed to a sing Pi node and we may consider removing transitive dependencies such that these chains are more likely.

Additional O(V) space allocations (A DenseMap<NodeType>) should be less important since already storing the nodes takes O(V) space. I don't understand where the O(V^2) comes from.

I think of the following:

DenseMap<NodeType> NumberOfIncomingEdges;
for (NodeType *N : Graph)
  for (EdgeType *E: N)
    NumberOfIncomingEdges[E->getTargetNode()] += 1;

and the requirement then be checked on the fly:

for (NodeType *Src : Graph) {
  if (Src->getEdges().size() != 1)
    continue;
  EdgeType *E = Src.back();
  if (!E->isUseDef())
    continue;
  NodeType *Tgt = E->getTargetNode();
  if (NumberOfIncomingEdges[Tgt] != 1)
    continue;

First part is O(V+E) (or just E assuming that E>V), second is O(V).

We could even compute CandidateSrcNodes` using NumberOfIncomingEdges with fewer operations:

for (NodeType *N : Graph) {
  if (N->getEdges().size() != 1)
    continue;
  for (EdgeType *E: N)
    CandidateSrcNodes[N] += NumberOfIncomingEdges[E->getTargetNode()].
}

with O(V+E).

But also also think you put more thoughts into it than I just did, so what am I missing?

452

In this example a->b and b->c can both be merged in the same round and with a bit of care, the merge of one of the would not inhibit merging the other in the same round.

[bmahjour]

Address review comments.

[bmahjour]

llvm/lib/Analysis/DependenceGraphBuilder.cpp

423

Compete graphs should be collapsed to a sing Pi node and we may consider removing transitive dependencies such that these chains are more likely.

In this patch simplify() is done before pi-block creation, so that the SCC walks can benefit from the reduction of node/edges as a result of simplification.

I don't understand where the O(V^2) comes from

The number of edges in a complete graph is equal to V(V-1)/2, which leads to the quadratic complexity in number of nodes if we walk over it.

452

Please take a look at the updated patch, where I removed the fix point iteration. Does that look good to you?

[bmahjour]

@Meinersbur this update should address your concern regarding time complexity. I've also tried to limit the additional memory usage by only keeping track of incoming edge counts for nodes that are targets of candidate source nodes.

[bmahjour]

@Meinersbur have you had a chance to see my latest changes yet?

[bmahjour]

ping

[Meinersbur]

llvm/include/llvm/Analysis/DDG.h

394

[bikeshedding] areNodesMergable?

llvm/lib/Analysis/DependenceGraphBuilder.cpp

415–417

[style] This does two DenseMap lookups. Did you consider using the iterator returned by DenseMap::find to access the element?

431

[serious] Since DenseMap::erase replaces the item with a tombstone, searching for the next non-tombstone (DenseMap::begin) will be linear in time. That is, this while-loop takes O(n^2) just for iterating over the elements.

Maybe have a separate worklist+hastable for marking elements already processed?

453

[typo] cancidate

[Meinersbur]

llvm/lib/Analysis/DependenceGraphBuilder.cpp

406–410

[style] Can you enclose the inner of LLVM_DEBUG into braces such that clang-format formats it nicer?

LLVM_DEBUG({
  ...
});

[bmahjour]

llvm/lib/Analysis/DependenceGraphBuilder.cpp

431

I was trying to avoid a second container to avoid memory waste, but since the worklist is transient and typically small, duplicating it should be fine. I've also found a bug where (depending on the order) merging nodes can trigger the "Expected a single edge from the candidate src node." assert. I've fixed this as well and added comments.

[Meinersbur]

LGTM

llvm/lib/Analysis/DependenceGraphBuilder.cpp

431

It would have been a good idea of there wasn't the downside of O(n^2).

As you noticed, iterating over a DenseMap can lead to non-deterministic behavior (There's MapVector to avoid this).

llvm/include/llvm/Analysis/DDG.h

public:
   static bool classof(const DDGNode *N) {
     return N->getKind() == NodeKind::Root;
   }
   static bool classof(const RootDDGNode *N) { return true; }
 };
 
 /// Subclass of DDGNode representing single or multi-instruction nodes.
 class SimpleDDGNode : public DDGNode {
+  friend class DDGBuilder;
 public:
   SimpleDDGNode() = delete;
   SimpleDDGNode(Instruction &I);
   SimpleDDGNode(const SimpleDDGNode &N);
   SimpleDDGNode(SimpleDDGNode &&N);
   ~SimpleDDGNode();
 
   SimpleDDGNode &operator=(const SimpleDDGNode &N) {
public:
   }
 
   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();
   }
 
+  /// Return true if the two nodes \pSrc and \pTgt are both simple nodes and
+  /// the consecutive instructions after merging belong to the same basic block.
+  bool areNodesMergeable(const DDGNode &Src,
+                         const DDGNode &Tgt) const final override;
+  void mergeNodes(DDGNode &Src, DDGNode &Tgt) final override;
+  bool shouldSimplify() const final override;
   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:
   /// 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();
+    simplify();
     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.
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();
 
+  /// Go through all the nodes in the graph and collapse any two nodes
+  /// 'a' and 'b' if all of the following are true:
+  ///   - the only edge from 'a' is a def-use edge to 'b' and
+  ///   - the only edge to 'b' is a def-use edge from 'a' and
+  ///   - there is no cyclic edge from 'b' to 'a' and
+  ///   - all instructions in 'a' and 'b' belong to the same basic block and
+  ///   - both 'a' and 'b' are simple (single or multi instruction) nodes.
+  void simplify();
+
   /// 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.
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; }
 
+  /// Return true if graph simplification step is requested, and false
+  /// otherwise.
+  virtual bool shouldSimplify() const { return true; }
+
+  /// Return true if it's safe to merge the two nodes.
+  virtual bool areNodesMergeable(const NodeType &A, const NodeType &B) const = 0;
+
+  /// Append the content of node \p B into node \p A and remove \p B and
+  /// the edge between \p A and \p B from the graph.
+  virtual void mergeNodes(NodeType &A, NodeType &B) = 0;
+
   /// 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.

llvm/lib/Analysis/DDG.cpp

 #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> SimplifyDDG(
+    "ddg-simplify", cl::init(true), cl::Hidden, cl::ZeroOrMore,
+    cl::desc(
+        "Simplify DDG by merging nodes that have less interesting edges."));
+
 static cl::opt<bool>
     CreatePiBlocks("ddg-pi-blocks", cl::init(true), cl::Hidden, cl::ZeroOrMore,
                    cl::desc("Create pi-block nodes."));
 
 #define DEBUG_TYPE "ddg"
 
 template class llvm::DGEdge<DDGNode, DDGEdge>;
 template class llvm::DGNode<DDGNode, DDGEdge>;
for (DDGNode *Node : G)
     // Avoid printing nodes that are part of a pi-block twice. They will get
     // printed when the pi-block is printed.
     if (!G.getPiBlock(*Node))
       OS << *Node << "\n";
   OS << "\n";
   return OS;
 }
 
+//===--------------------------------------------------------------------===//
+// DDGBuilder implementation
+//===--------------------------------------------------------------------===//
+
+bool DDGBuilder::areNodesMergeable(const DDGNode &Src,
+                                   const DDGNode &Tgt) const {
+  // Only merge two nodes if they are both simple nodes and the consecutive
+  // instructions after merging belong to the same BB.
+  auto *SimpleSrc = dyn_cast<const SimpleDDGNode>(&Src);
+  auto *SimpleTgt = dyn_cast<const SimpleDDGNode>(&Tgt);
+  if (!SimpleSrc || !SimpleTgt)
+    return false;
+
+  return SimpleSrc->getLastInstruction()->getParent() ==
+         SimpleTgt->getFirstInstruction()->getParent();
+}
+
+void DDGBuilder::mergeNodes(DDGNode &A, DDGNode &B) {
+  DDGEdge &EdgeToFold = A.back();
+  assert(A.getEdges().size() == 1 && EdgeToFold.getTargetNode() == B &&
+         "Expected A to have a single edge to B.");
+  assert(isa<SimpleDDGNode>(&A) && isa<SimpleDDGNode>(&B) &&
+         "Expected simple nodes");
+
+  // Copy instructions from B to the end of A.
+  cast<SimpleDDGNode>(&A)->appendInstructions(*cast<SimpleDDGNode>(&B));
+
+  // Move to A any outgoing edges from B.
+  for (DDGEdge *BE : B)
+    Graph.connect(A, BE->getTargetNode(), *BE);
+
+  A.removeEdge(EdgeToFold);
+  destroyEdge(EdgeToFold);
+  Graph.removeNode(B);
+  destroyNode(B);
+}
+
+bool DDGBuilder::shouldSimplify() const {
+  return SimplifyDDG;
+}
+
 bool DDGBuilder::shouldCreatePiBlocks() const {
   return CreatePiBlocks;
 }
 
 //===--------------------------------------------------------------------===//
 // DDG Analysis Passes
 //===--------------------------------------------------------------------===//
 

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>::simplify() {
+  if (!shouldSimplify())
+    return;
+  LLVM_DEBUG(dbgs() << "==== Start of Graph Simplification ===\n");
+
+  // This algorithm works by first collecting a set of candidate nodes that have
+  // an out-degree of one (in terms of def-use edges), and then ignoring those
+  // whose targets have an in-degree more than one. Each node in the resulting
+  // set can then be merged with its corresponding target and put back into the
+  // worklist until no further merge candidates are available.
+  SmallPtrSet<NodeType *, 32> CandidateSourceNodes;
+
+  // A mapping between nodes and their in-degree. To save space, this map
+  // only contains nodes that are targets of nodes in the CandidateSourceNodes.
+  DenseMap<NodeType *, unsigned> TargetInDegreeMap;
+
+  for (NodeType *N : Graph) {
+    if (N->getEdges().size() != 1)
+      continue;
+    EdgeType &Edge = N->back();
+    if (!Edge.isDefUse())
+      continue;
+    CandidateSourceNodes.insert(N);
+
+    // Insert an element into the in-degree map and initialize to zero. The
+    // count will get updated in the next step.
+    TargetInDegreeMap.insert({&Edge.getTargetNode(), 0});
+  }
+
+  LLVM_DEBUG({
+    dbgs() << "Size of candidate src node list:" << CandidateSourceNodes.size()
+           << "\nNode with single outgoing def-use edge:\n";
+    for (NodeType *N : CandidateSourceNodes) {
+      dbgs() << N << "\n";
+    }
+  });
+
+  for (NodeType *N : Graph) {
+    for (EdgeType *E : *N) {
+      NodeType *Tgt = &E->getTargetNode();
+      auto TgtIT = TargetInDegreeMap.find(Tgt);
+      if (TgtIT != TargetInDegreeMap.end())
+        ++(TgtIT->second);
+    }
+  }
+
+  LLVM_DEBUG({
+    dbgs() << "Size of target in-degree map:" << TargetInDegreeMap.size()
+           << "\nContent of in-degree map:\n";
+    for (auto &I : TargetInDegreeMap) {
+      dbgs() << I.first << " --> " << I.second << "\n";
+    }
+  });
+
+  SmallVector<NodeType *, 32> Worklist(CandidateSourceNodes.begin(),
+                                       CandidateSourceNodes.end());
+  while (!Worklist.empty()) {
+    NodeType &Src = *Worklist.pop_back_val();
+    // As nodes get merged, we need to skip any node that has been removed from
+    // the candidate set (see below).
+    if (CandidateSourceNodes.find(&Src) == CandidateSourceNodes.end())
+      continue;
+    CandidateSourceNodes.erase(&Src);
+
+    assert(Src.getEdges().size() == 1 &&
+           "Expected a single edge from the candidate src node.");
+    NodeType &Tgt = Src.back().getTargetNode();
+    assert(TargetInDegreeMap.find(&Tgt) != TargetInDegreeMap.end() &&
+           "Expected target to be in the in-degree map.");
+
+    if (TargetInDegreeMap[&Tgt] != 1)
+      continue;
+
+    if (!areNodesMergeable(Src, Tgt))
+      continue;
+
+    // Do not merge if there is also an edge from target to src (immediate
+    // cycle).
+    if (Tgt.hasEdgeTo(Src))
+      continue;
+
+    LLVM_DEBUG(dbgs() << "Merging:" << Src << "\nWith:" << Tgt << "\n");
+
+    mergeNodes(Src, Tgt);
+
+    // If the target node is in the candidate set itself, we need to put the
+    // src node back into the worklist again so it gives the target a chance
+    // to get merged into it. For example if we have:
+    // {(a)->(b), (b)->(c), (c)->(d), ...} and the worklist is initially {b, a},
+    // then after merging (a) and (b) together, we need to put (a,b) back in
+    // the worklist so that (c) can get merged in as well resulting in
+    // {(a,b,c) -> d}
+    // We also need to remove the old target (b), from the worklist. We first
+    // remove it from the candidate set here, and skip any item from the
+    // worklist that is not in the set.
+    if (CandidateSourceNodes.find(&Tgt) != CandidateSourceNodes.end()) {
+      Worklist.push_back(&Src);
+      CandidateSourceNodes.insert(&Src);
+      CandidateSourceNodes.erase(&Tgt);
+      LLVM_DEBUG(dbgs() << "Putting " << &Src << " back in the worklist.\n");
+    }
+  }
+  LLVM_DEBUG(dbgs() << "=== End of Graph Simplification ===\n");
+}
+
 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;

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

 ; CHECK-NEXT: Edges:
 ; CHECK-NEXT:  [def-use] to [[N1]]
 ; CHECK-NEXT: --- end of nodes in pi-block ---
 ; CHECK-NEXT: Edges:
 ; 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: Node Address:[[N5]]:multi-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %exitcond = icmp ne i64 %inc, %n
-; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N6:0x[0-9a-f]*]]
-
-; 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:[[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 [[N7:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N6:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N3]]:single-instruction
+; CHECK: Node Address:[[N3]]:multi-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %arrayidx = getelementptr inbounds float, float* %b, i64 %i.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:    %0 = load float, float* %arrayidx, align 4
 ; 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:[[N10:0x[0-9a-f]*]]:single-instruction
+; CHECK: Node Address:[[N8: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 [[N9]]
+; CHECK-NEXT:  [def-use] to [[N7]]
 
-; CHECK: Node Address:[[N9]]:single-instruction
+; CHECK: Node Address:[[N7]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %add = fadd float %0, %conv
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N7]]
+; CHECK-NEXT:  [def-use] to [[N6]]
 
-; CHECK: Node Address:[[N7]]:single-instruction
+; CHECK: Node Address:[[N6]]: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++)

 ; CHECK-NEXT:  [def-use] to [[N1]]
 ; CHECK-NEXT: --- end of nodes in pi-block ---
 ; CHECK-NEXT: Edges:
 ; 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:[[N6]]:single-instruction
+; CHECK: Node Address:[[N6]]:multi-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %exitcond = icmp ne i64 %inc, %n
-; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N7:0x[0-9a-f]*]]
-
-; 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:[[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 [[N8:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N7:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N4]]:single-instruction
+; CHECK: Node Address:[[N4]]:multi-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %arrayidx1 = getelementptr inbounds float, float* %a, i64 %i.02
-; 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* %arrayidx1, align 4
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N20:0x[0-9a-f]*]]
-; CHECK-NEXT:  [memory] to [[N8]]
+; CHECK-NEXT:  [def-use] to [[N8:0x[0-9a-f]*]]
+; CHECK-NEXT:  [memory] to [[N7]]
 
-; CHECK: Node Address:[[N3]]:single-instruction
+; CHECK: Node Address:[[N3]]:multi-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %arrayidx = getelementptr inbounds float, float* %b, i64 %i.02
-; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N10:0x[0-9a-f]*]]
-
-; 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 [[N20]]
+; CHECK-NEXT:  [def-use] to [[N8]]
 
-; CHECK: Node Address:[[N20]]:single-instruction
+; CHECK: Node Address:[[N8]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %add = fadd float %0, %1
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N8]]
+; CHECK-NEXT:  [def-use] to [[N7]]
 
-; CHECK: Node Address:[[N8]]:single-instruction
+; CHECK: Node Address:[[N7]]: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

 ; 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: Node Address:[[N7]]:single-instruction
+; CHECK: Node Address:[[N7]]:multi-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 [[N9:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N8:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N5]]:single-instruction
+; CHECK: Node Address:[[N5]]:multi-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %sub1 = add i64 %i.02, -1
-; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N10:0x[0-9a-f]*]]
-
-; 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 [[N9]]
+; CHECK-NEXT:  [def-use] to [[N8]]
 
-; CHECK: Node Address:[[N4]]:single-instruction
+; CHECK: Node Address:[[N4]]:multi-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %arrayidx = getelementptr inbounds float, float* %b, i64 %i.02
-; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N11:0x[0-9a-f]*]]
-
-; 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 [[N9]]
+; CHECK-NEXT:  [def-use] to [[N8]]
 
-; CHECK: Node Address:[[N9]]:pi-block
+; CHECK: Node Address:[[N8]]:pi-block
 ; CHECK-NEXT: --- start of nodes in pi-block ---
-; CHECK: Node Address:[[N12:0x[0-9a-f]*]]:single-instruction
+; CHECK: Node Address:[[N9: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 [[N13:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N10:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N13]]:single-instruction
+; CHECK: Node Address:[[N10]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %add = fadd float %0, %1
 ; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N14:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N11:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N14]]: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 [[N12]]
+; CHECK-NEXT:  [memory] to [[N9]]
 ; CHECK-NEXT:--- end of nodes in pi-block ---
 ; CHECK-NEXT: Edges:none!
 
 
 
 ;; Loop-carried dependence requiring edge-reversal to expose a cycle
 ;; in the graph.
 ;; void test(unsigned long n, float * restrict a, float * restrict b) {

 ; 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: Node Address:[[N7]]:single-instruction
+; CHECK: Node Address:[[N7]]:multi-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 %test2.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 [[N9:0x[0-9a-f]*]]
+; CHECK-NEXT:  [def-use] to [[N8:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N5]]:single-instruction
+; CHECK: Node Address:[[N5]]:multi-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %add1 = add i64 %i.02, 1
-; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N10:0x[0-9a-f]*]]
-
-; 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 [[N11:0x[0-9a-f]*]]
-
-; 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 [[N12:0x[0-9a-f]*]]
-; CHECK-NEXT:  [memory] to [[N9]]
+; CHECK-NEXT:  [def-use] to [[N9:0x[0-9a-f]*]]
+; CHECK-NEXT:  [memory] to [[N8]]
 
-; CHECK: Node Address:[[N4]]:single-instruction
+; CHECK: Node Address:[[N4]]:multi-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %arrayidx = getelementptr inbounds float, float* %b, i64 %i.02
-; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N13:0x[0-9a-f]*]]
-
-; 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 [[N12]]
-
+; CHECK-NEXT:  [def-use] to [[N9]]
 
-; CHECK: Node Address:[[N12]]: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 [[N9]]
+; CHECK-NEXT:  [def-use] to [[N8]]
 
-; CHECK: Node Address:[[N9]]:single-instruction
+; CHECK: Node Address:[[N8]]: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

 ; CHECK-NEXT:  [def-use] to [[N10]]
 ; 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 [[N13:0x[0-9a-f]*]]
 ; CHECK-NEXT:  [def-use] to [[N14:0x[0-9a-f]*]]
 ; CHECK-NEXT:  [def-use] to [[N15:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N15]]:single-instruction
+; CHECK: Node Address:[[N15]]:multi-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %exitcond = icmp ne i64 %inc13, %n
-; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N16:0x[0-9a-f]*]]
-
-; 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: Node Address:[[N14]]:multi-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: 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 [[N6]]
 
 ; 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 [[N18:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N13]]:single-instruction
+; CHECK: Node Address:[[N13]]:multi-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %2 = mul nsw i64 %i.04, %n
-; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N19:0x[0-9a-f]*]]
-
-; 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 [[N8]]
 
 ; 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 [[N18]]
 
-; CHECK: Node Address:[[N12]]:single-instruction
+; CHECK: Node Address:[[N12]]:multi-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %0 = mul nsw i64 %i.04, %n
-; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N20:0x[0-9a-f]*]]
-
-; 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 [[N4]]
 
-; CHECK: Node Address:[[N4]]:single-instruction
+; CHECK: Node Address:[[N4]]:multi-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %arrayidx5 = getelementptr inbounds float, float* %arrayidx, i64 %j.02
-; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N21:0x[0-9a-f]*]]
-
-; 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 [[N18]]
 
 ; 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: 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 [[N7]]
 ; CHECK-NEXT:  [def-use] to [[N28:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N28]]:single-instruction
+; CHECK: Node Address:[[N28]]:multi-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %cmp21 = icmp ult i64 1, %sub
-; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N29:0x[0-9a-f]*]]
-
-; 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:[[N7]]:single-instruction
+; CHECK: Node Address:[[N7]]:multi-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %cmp2 = icmp ult i64 %inc, %sub
-; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N30:0x[0-9a-f]*]]
-
-; 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++)
 ;;    for (unsigned long j = 1; j < n-1; j++)

 ; CHECK-NEXT:  [def-use] to [[N9]]
 ; CHECK-NEXT:--- end of nodes in pi-block ---
 ; 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:[[N14]]:single-instruction
+; CHECK: Node Address:[[N14]]:multi-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %exitcond = icmp ne i64 %inc13, %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:    br i1 %exitcond, label %test2.for.cond1.preheader, label %for.end14.loopexit
 ; CHECK-NEXT: Edges:none!
 
-; CHECK: Node Address:[[N13]]:single-instruction
+; CHECK: Node Address:[[N13]]:multi-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %4 = mul nsw i64 %i.04, %n
-; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N16:0x[0-9a-f]*]]
-
-; 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 [[N5]]
 
 ; 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 [[N17:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N12]]:single-instruction
+; CHECK: Node Address:[[N12]]:multi-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: 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 [[N7]]
 
-; CHECK: Node Address:[[N7]]:single-instruction
+; CHECK: Node Address:[[N7]]:multi-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %arrayidx8 = getelementptr inbounds float, float* %arrayidx6, i64 %add7
-; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N19:0x[0-9a-f]*]]
-
-; 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 [[N20:0x[0-9a-f]*]]
 ; CHECK-NEXT:  [memory] to [[N17]]
 
-; CHECK: Node Address:[[N11]]:single-instruction
+; CHECK: Node Address:[[N11]]:multi-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %0 = mul nsw i64 %i.04, %n
-; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N21:0x[0-9a-f]*]]
-
-; 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 [[N3]]
 
-; CHECK: Node Address:[[N3]]:single-instruction
+; CHECK: Node Address:[[N3]]:multi-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %arrayidx5 = getelementptr inbounds float, float* %arrayidx, i64 %j.02
-; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N22:0x[0-9a-f]*]]
-
-; 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 [[N20]]
 
 ; CHECK: Node Address:[[N20]]:single-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %add = fadd float %1, %3
 ; CHECK-NEXT: Edges:

 
 ; 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 [[N6]]
 ; CHECK-NEXT:  [def-use] to [[N26:0x[0-9a-f]*]]
 
-; CHECK: Node Address:[[N26]]:single-instruction
+; CHECK: Node Address:[[N26]]:multi-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %cmp21 = icmp ult i64 1, %sub
-; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N27:0x[0-9a-f]*]]
-
-; 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:[[N6]]:single-instruction
+; CHECK: Node Address:[[N6]]:multi-instruction
 ; CHECK-NEXT: Instructions:
 ; CHECK-NEXT:    %cmp2 = icmp ult i64 %inc, %sub
-; CHECK-NEXT: Edges:
-; CHECK-NEXT:  [def-use] to [[N28:0x[0-9a-f]*]]
-
-; 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 (unsigned long j = 1; j < n-1; j++)

 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