[DDG] Data Dependence Graph Basics

[bmahjour]

Summary

This is the first patch in a series of patches that will implement data dependence graph in LLVM. Many of the ideas used in this implementation are based on the following paper:

D. J. Kuck, R. H. Kuhn, D. A. Padua, B. Leasure, and M. Wolfe (1981). DEPENDENCE GRAPHS AND COMPILER OPTIMIZATIONS.

This patch contains support for a basic DDGs containing only atomic nodes (one node for each instruction). The edges are two fold: def-use edges and memory-dependence edges. The idea behind the DependenceGraphBuilder and why we need it are summarized in https://ibm.ent.box.com/v/directed-graph-and-ddg.

The implementation takes a list of basic-blocks and only considers dependencies among instructions in those basic blocks. Any dependencies coming into or going out of instructions that do not belong to those basic blocks are ignored.

The algorithm for building the graph involves the following steps in order:

1. For each instruction in the range of basic blocks to consider, create an atomic node in the resulting graph.
2. For each node in the graph establish def-use edges to/from other nodes in the graph.
3. For each pair of nodes containing memory instruction(s) create memory edges between them. This part of the algorithm goes through the instructions in lexicographical order and creates edges in reverse order if the sink of the dependence occurs before the source of it.

[Meinersbur]

llvm/include/llvm/Analysis/DDG.h

69

[style] By LLVM's coding standard, method names start with lower case.

194

[serious] Please write something about the algorithmic complexity of this.

213–214

[style] Most often the LLVM uses the Ty suffix for typedefs/using.

230

[suggestion] Instead of marking the method as final, maybe mark the entire class as final?

274

[style] ResultTy?

299

This type is not a reference, but a pointer.

llvm/lib/Analysis/DDG.cpp

33

[nit] Parens around cast unnecessary

134

Could you either pass a non-const Function or use a list of constBasicBlock?

135

[subjective] This is a good illustration of one of the reasons why I dislike doing more than just initializing an object inside its constructor. When calling a virtual function, it will not call the overriden function of the class that will be returned, but the function that it statically resolves to.

In this case, the populateGraph method is marked as final, so there cannot be overriden in another subclass. But then, there is no point in making populateGraph virtual as it is protected and called nowhere else, not even in the base class.

My suggestion is to let a method of DDGBuilder return a populated graph instead of doing it in the constructor.

139–141

[suggestion] Instead of the long initializer expression, assign it inside the body?

158–160

[style] return DDGBase::addNode(N)

llvm/lib/Analysis/DependenceGraphBuilder.cpp

40

[style] LLVM does not make use of almost-always auto.

120

Why this const_cast? Can we avoid it?

[myhsu]

llvm/include/llvm/Analysis/DDG.h

69

Maybe we can use llvm::function_ref here?

[bmahjour]

Addressed comments from Michael and Min-Yih.

llvm/include/llvm/Analysis/DDG.h

194

Sure. I have put a comment on the populate function of AbstractDependenceGraphBuilder class.

213–214

If I change the suffix only for the usings, they would look inconsistent with the template type names. For example we'll have:

template <class GraphType> class AbstractDependenceGraphBuilder {
  using NodeTy = typename GraphType::NodeTy;

Notice GraphType vs NodeTy. Unless you'd like me to rename the template type names too, I think it looks and reads better the way it is right now. By the way, I couldn't find anything on this topic in the LLVM Coding Standards.

230

I will remove this function.

274

The pass manager interface requires each pass to have a type named Result. eg in include/llvm/IR/PassManagerInternal.h:

AnalysisResultModel<IRUnitT, PassT, typename PassT::Result

299

Again, the templated implementation of GraphTraits and related iterators require this type to be named NodeRef. Please see llvm/ADT/GraphTraits.h and llvm/ADT/SCCIterator.h for example.

llvm/lib/Analysis/DDG.cpp

134

Unfortunately many of LLVM interfaces take non-const Instructions (including DependenceInfo::depends), so even if I change the list types to be lists of const BasicBlocks and const Instructions, we would need to do a const_cast at some point to interface with the rest of LLVM. I'll change the type of the parameter F to be a non-const Function :(

135

Fair enough, I'll remove the populateGraph function all together.

139–141

Please note that I'm trying to call one of the base class constructors that takes arguments. I think the only way to call it without also calling the default constructor is to use the initializer list.

158–160

actually this function does nothing more than calling the base class addNode until we add the pi-blocks, so I'll remove it from this patch.

llvm/lib/Analysis/DependenceGraphBuilder.cpp

120

AbstractDependenceGraphBuilder holds a constant reference to the result of the dependence analysis (DI). Unfortunately DependenceInfo::depends is not marked as constant although it doesn't modify anything. A few ways to solve this:

1. Make DI a non-const reference.
2. Do a const_cast when calling depends.
3. Make depends constant (can go viral and is beyond the scope of this work)

I personally prefer (2) as it keeps the const_cast where the const chain broke down. If depends is improved and made const we just need to drop this const_cast, and in the meantime we prevent code changes that inadvertently modify DI in this implementation.

[bmahjour]

Addressed comments from Michael and Min-Yih.

[bmahjour]

A friendly reminder to kindly review and provide comments/approval. Thank you!

[Meinersbur]

LGTM, with some nitpicks.

llvm/include/llvm/Analysis/DDG.h

108

[style] Why not

return InstrList;

instead of those casts?

Additionally, I don't see the harm of returning and empty instruction list. Especially if the function is used to add instructions to the node.

118

[suggestion] There often is also static bool classof(const SimpleDDGNode *) { return true; } for the case when the compiler already knows the type.

213–214

It's not in the coding standard document, but as mentioned it is something you see a lot in the existing code base. I find it useful as the compiler would be confused if one writes e.g.

using SomeList = SmallVector<...>;
...
SomeList SomeList;

However, I see you are trying to match the template argument names (And indeed I don't see the Ty suffix in template argument names in the code base). Therefore, I think your choice makes sense here.

274

OK, didn't notice this.

299

Sorry, didn't see this as a requirement of GraphTraits

llvm/include/llvm/Analysis/DependenceGraphBuilder.h

26–27

[style] The names "BasicBlockList" and "InstructionList" a very general to be put into the entire llvm:: namespace and could conflict with other headers that use lists of instructions and BBs. Maybe move them into one of the DDG classes?

Also the Ty suffix for typedefs would apply here.

llvm/lib/Analysis/DDG.cpp

139–141

OK.

llvm/lib/Analysis/DependenceGraphBuilder.cpp

103

[style] By coding standard , the end-iterator should be cached (the list of nodes is not modified within the body, right)?

120

DI is created by this patch in DDGAnalysis::run and don't see a reason to pass it as const & if the class was not designed for it. That is, I'd prefer (1).

[fhahn]

This patch contains support for a basic DDGs containing only atomic nodes (one node for each instruction). The edges are two fold: def-use edges and memory-dependence edges. The idea behind the DependenceGraphBuilder and why we need it are summarized in https://ibm.ent.box.com/v/directed-graph-and-ddg.

I think it would be good to summarize the information in-tree as well, to ensure the information is accessible later on as well. Some of the docs fit in the headers, for some of it a new documentation page might be worth adding. Ideally it would include some info about design decisions, the intended/example uses cases and how the DDG helps and the benefits over the existing infrastructure.

A few additional questions:

I am not sure I see the direct benefit of duplicating the def-use edges in the DDG? Given a User, we already have access to its uses throughout the User itself and LLVM tries hard to maintain that relation very efficiently.

IIUC the plan is to build the DDG up front and then check the legality of a transformation on top of it. Currently, most passes bail out early once they detect a transformation cannot be applied and this helps to limit compile time. Could we do something similar with checks dependent on the DDG?

llvm/include/llvm/Analysis/DDG.h

102

Unless there is a good reason, I think it would be better to return an ArrayRef/SmallVectorImpl instead of a concrete SmallVector here (and other places, same for arguments).

200

Why do we need a copy here? Wouldn't a reference be enough?

234

Do we need dynamic memory allocation here? Can the DDG just own the nodes?

llvm/include/llvm/Analysis/DependenceGraphBuilder.h

27

The default seems a bit excessive. Do you expect most nodes to have multiple instructions?

90

Is there a reason to not use DenseMap here?

[bmahjour]

Addressed the latest round of review comments. Also merged with the latest changes from master branch.

[bmahjour]

llvm/include/llvm/Analysis/DDG.h

102

Ok, I'll change functions to work with SmallVectorImpl.

108

We could just return InstList, but since the const version is already doing this, we use this trick to avoid code duplication. It's common practice in C++ codes, and I see instances of it in LLVM as well (eg. getInlineBuckets in DenseMap.h) .

Scott Meyers encourages this practice in his book "Effective C++" in section Avoiding Duplication in const and Non-const Member Functions.

The assert is useful because we intentionally avoid constructing a SimpleDDGNode node with no instruction and none of the member functions allow removing instructions from the node.

200

The reason is that the target of the reference may go out of scope, while the DDG (as an analysis result) lives on. For instance if you look at DDGAnalysis::run, an object of DependenceInfo is created inside the function which is used to construct the DDG. The function returns a unique_ptr to that DDG. The DDG lives on and needs to answer queries about the dependencies, while the DependenceInfo object is local to the function and gets destroyed upon return of the run function.

234

I don't see how DDG can be implemented without using dynamic memory allocation. Having the DDG own the nodes also creates problems for the builder design pattern, since the creation of the objects is meant to be delegated to the builder class.

llvm/include/llvm/Analysis/DependenceGraphBuilder.h

26–27

Good point. I'll fix it.

27

The default seems a bit excessive. Do you expect most nodes to have multiple instructions?

It depends on whether the builder is used to build a DDG or a PDG. Program Dependence Graphs tend to contain coarse-grained nodes containing many instructions. Merged DDG nodes after graph simplification (not shown in this patch) usually contain 2 or 3 instructions and based on my observation they constitute about less than a third of all the nodes. PDG nodes on the other hand could easily have in the order of tens or hundreds of instructions.

I'll change it to 2 instructions for now, since PDG is farther down the road.

90

Originally I thought DenseMap was implemented as a binary search tree, but looks like it's a true hash table. I'll switch to DenseMap.

llvm/lib/Analysis/DependenceGraphBuilder.cpp

103

Right, I'll use that style for the this and the DstIt loop.

120

Ok, I'll make DI non-const.

[bmahjour]

In D65350#1636205, @fhahn wrote:

This patch contains support for a basic DDGs containing only atomic nodes (one node for each instruction). The edges are two fold: def-use edges and memory-dependence edges. The idea behind the DependenceGraphBuilder and why we need it are summarized in https://ibm.ent.box.com/v/directed-graph-and-ddg.

I think it would be good to summarize the information in-tree as well, to ensure the information is accessible later on as well. Some of the docs fit in the headers, for some of it a new documentation page might be worth adding. Ideally it would include some info about design decisions, the intended/example uses cases and how the DDG helps and the benefits over the existing infrastructure.

Sure I can create a page or two of documentation, however I'm not very familiar with the doc infrastructure in LLVM. Could you point me to some examples to follow? Would an rts file under llvm/docs/DDG be sufficient? Are they rendered by any tool and if so how can I test it?

A few additional questions:

I am not sure I see the direct benefit of duplicating the def-use edges in the DDG? Given a User, we already have access to its uses throughout the User itself and LLVM tries hard to maintain that relation very efficiently.

The def-use dependencies are important as they carry scalar dependencies but it is possible to only consider memory access instructions in the DDG and only follow def-use edges during graph construction to establish reaching defs from load-like instructions to store-like instructions. However doing that reduces the generality of DDG as transformations would need to do extra work during codegen to pull in all required instructions. If the def-use edges are explicitly represented in the graph, then codegen is simplified because a topological sort of the graph fully represents the whole program. Please note that, the DDG can potentially be used in many different transformations. Many of those transformations, such as instruction scheduling, care about all instructions (not just memory access instructions), and would not benefit from using this implementation of a DDG if a minimalistic approach is to be taken.

I actually implemented a prototype where I did the "minimal" implementation only considering memory instructions. I measured the difference in compile-time for a number of benchmarks with and without this approach, and I only noticed a small improvement. From what I observed and the feedback from several people, the gain is too small to justify the loss of generality and convenience of a full DDG.

IIUC the plan is to build the DDG up front and then check the legality of a transformation on top of it. Currently, most passes bail out early once they detect a transformation cannot be applied and this helps to limit compile time. Could we do something similar with checks dependent on the DDG?

The DDG would certainly help analyze legality of various transformations. It can go beyond answering the question of "whether a transformation is legal or not". It can actually help determine how to transform the code so that it preserves original program dependencies, a good example of this is loop distribution and loop vectorization. Other transformations, which only care about existence of a certain data dependency pattern, can use the DDG as well, but they would have to consider the benefits versus the compile-time cost of building it.

[bmahjour]

Created a documentation in tree with diagrams and words describing the high level design.

[fhahn]

In D65350#1639499, @bmahjour wrote:

In D65350#1636205, @fhahn wrote:

This patch contains support for a basic DDGs containing only atomic nodes (one node for each instruction). The edges are two fold: def-use edges and memory-dependence edges. The idea behind the DependenceGraphBuilder and why we need it are summarized in https://ibm.ent.box.com/v/directed-graph-and-ddg.

I think it would be good to summarize the information in-tree as well, to ensure the information is accessible later on as well. Some of the docs fit in the headers, for some of it a new documentation page might be worth adding. Ideally it would include some info about design decisions, the intended/example uses cases and how the DDG helps and the benefits over the existing infrastructure.

Sure I can create a page or two of documentation, however I'm not very familiar with the doc infrastructure in LLVM. Could you point me to some examples to follow? Would an rts file under llvm/docs/DDG be sufficient? Are they rendered by any tool and if so how can I test it?

Great thanks! Yep adding a .rts should be sufficient. I think you need sphinx installed to build the docs and set LLVM_BUILD_DOCS.

A few additional questions:

I am not sure I see the direct benefit of duplicating the def-use edges in the DDG? Given a User, we already have access to its uses throughout the User itself and LLVM tries hard to maintain that relation very efficiently.

The def-use dependencies are important as they carry scalar dependencies but it is possible to only consider memory access instructions in the DDG and only follow def-use edges during graph construction to establish reaching defs from load-like instructions to store-like instructions. However doing that reduces the generality of DDG as transformations would need to do extra work during codegen to pull in all required instructions. If the def-use edges are explicitly represented in the graph, then codegen is simplified because a topological sort of the graph fully represents the whole program. Please note that, the DDG can potentially be used in many different transformations. Many of those transformations, such as instruction scheduling, care about all instructions (not just memory access instructions), and would not benefit from using this implementation of a DDG if a minimalistic approach is to be taken.

Thanks for clarifying, I was not aware of the additional intended use cases.

I actually implemented a prototype where I did the "minimal" implementation only considering memory instructions. I measured the difference in compile-time for a number of benchmarks with and without this approach, and I only noticed a small improvement. From what I observed and the feedback from several people, the gain is too small to justify the loss of generality and convenience of a full DDG.

IIUC the plan is to build the DDG up front and then check the legality of a transformation on top of it. Currently, most passes bail out early once they detect a transformation cannot be applied and this helps to limit compile time. Could we do something similar with checks dependent on the DDG?

The DDG would certainly help analyze legality of various transformations. It can go beyond answering the question of "whether a transformation is legal or not". It can actually help determine how to transform the code so that it preserves original program dependencies, a good example of this is loop distribution and loop vectorization. Other transformations, which only care about existence of a certain data dependency pattern, can use the DDG as well, but they would have to consider the benefits versus the compile-time cost of building it.

llvm/include/llvm/Analysis/DDG.h

200

Ah right, it's unfortunate that the new pass manager does not really allow to get DI easily from a loop pass. I might be worth moving the DI into DependenceInfo, to make the ownership a bit more explicit.

[bmahjour]

In D65350#1652123, @fhahn wrote:

In D65350#1639499, @bmahjour wrote:

In D65350#1636205, @fhahn wrote:

This patch contains support for a basic DDGs containing only atomic nodes (one node for each instruction). The edges are two fold: def-use edges and memory-dependence edges. The idea behind the DependenceGraphBuilder and why we need it are summarized in https://ibm.ent.box.com/v/directed-graph-and-ddg.

I think it would be good to summarize the information in-tree as well, to ensure the information is accessible later on as well. Some of the docs fit in the headers, for some of it a new documentation page might be worth adding. Ideally it would include some info about design decisions, the intended/example uses cases and how the DDG helps and the benefits over the existing infrastructure.

Sure I can create a page or two of documentation, however I'm not very familiar with the doc infrastructure in LLVM. Could you point me to some examples to follow? Would an rts file under llvm/docs/DDG be sufficient? Are they rendered by any tool and if so how can I test it?

Great thanks! Yep adding a .rts should be sufficient. I think you need sphinx installed to build the docs and set LLVM_BUILD_DOCS.

No Problem. Thank you for bringing it up. The latest uploaded patch contains the .rst and the relevant images.

@fhahn @Meinersbur If there are no further comments I'd appreciate an approval so we can move on to the next patches. Thanks.

llvm/include/llvm/Analysis/DDG.h

200

might be worth moving the DI into DependenceInfo, to make the ownership a bit more explicit.

I'm not sure what you mean by moving the DI into DependenceInfo. Could you please clarify?

[Meinersbur]

Thanks for the docs! Could you clarify the difference between paper and implementation? The implementations looks fine, apart a few nits.

llvm/docs/DependenceGraphs/DDG.rst

27–31 ↗

(On Diff #217966)

[clarification needed] AFAICS, this implementation does not allow an arbitrary hierarchical depth; just one layer that allows group instructions into a single node (Could it be called a pi-node?). Could you clarify the difference between paper and implementation?

44 ↗

(On Diff #217966)

The patch currently does not apply with arcanist. I only get 0 byte files for these images.

110 ↗

(On Diff #217966)

[nit] "over-engineering" (with dash or as single word)

llvm/include/llvm/Analysis/DDG.h

114

[suggestion] getInstructions().front()

116

[suggestion] getInstructions().back()

257

[nit] Passing a NodeKind by const has no effect on the declaration.

llvm/lib/Analysis/DDG.cpp

50–52

[suggestion] Explicitly handle the NodeKind::Unknown case so the compiler can warn that about a missing switch case if the NodeKind is extended.

60

[suggestion] isa<SimpleDDGNode>(N) since there is an overload isa(const Y &Val).

62

[suggestion] cast<const SimpleDDGNode>(N).getInstructions()

[bmahjour]

In D65350#1659816, @Meinersbur wrote:

Thanks for the docs! Could you clarify the difference between paper and implementation? The implementations looks fine, apart a few nits.

No problem. I've added a section on the differences between the paper and this implementation.

llvm/docs/DependenceGraphs/DDG.rst

27–31 ↗

(On Diff #217966)

You are correct, the hierarchy is at most one level deep. There is no difference between the paper and this implementation in this regard. I'll clarify that pi-blocks cannot be nested and why.

44 ↗

(On Diff #217966)

Sorry I forgot to use --binary when creating my patch. I'll fix it.

llvm/include/llvm/Analysis/DDG.h

257

True, but I usually try to keep the signature of the declaration and definition as similar as possible for consistency. Not sure why anyone would care to have const removed from by-value parameters on declarations!

[bmahjour]

Addressed latest round of review comments.

[bmahjour]

llvm/docs/DependenceGraphs/DDG.rst

44 ↗

(On Diff #217966)

There seems to be an issue with phabricator showing binary parts of a patch. I can recreate the .png files by reapplying the patch that I uploaded to this revision, but if I "Download Raw Diff" from this revision and apply it the images are null. I see the same issue in other reviews that added images eg. https://reviews.llvm.org/D49433.

For now you can see the images here: https://ibm.box.com/v/data-dependence-graph

[bmahjour]

ping

[Meinersbur]

LGTM.

llvm/include/llvm/Analysis/DDG.h

+//===- llvm/Analysis/DDG.h --------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines the Data-Dependence Graph (DDG).
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_DDG_H
+#define LLVM_ANALYSIS_DDG_H
+
+#include "llvm/ADT/DirectedGraph.h"
+#include "llvm/Analysis/DependenceAnalysis.h"
+#include "llvm/Analysis/DependenceGraphBuilder.h"
+#include "llvm/Analysis/LoopPass.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/Transforms/Scalar/LoopPassManager.h"
+#include <unordered_map>
+
+namespace llvm {
+class DDGNode;
+class DDGEdge;
+using DDGNodeBase = DGNode<DDGNode, DDGEdge>;
+using DDGEdgeBase = DGEdge<DDGNode, DDGEdge>;
+using DDGBase = DirectedGraph<DDGNode, DDGEdge>;
+
+/// Data Dependence Graph Node
+/// The graph can represent the following types of nodes:
+/// 1. Single instruction node containing just one instruction.
+/// 2. Multiple instruction node where two or more instructions from
+///    the same basic block are merged into one node.
+class DDGNode : public DDGNodeBase {
+public:
+  using InstructionListType = SmallVectorImpl<Instruction *>;
+
+  enum class NodeKind {
+    Unknown,
+    SingleInstruction,
+    MultiInstruction,
+  };
+
+  DDGNode() = delete;
+  DDGNode(const NodeKind K) : DDGNodeBase(), Kind(K) {}
+  DDGNode(const DDGNode &N) : DDGNodeBase(N), Kind(N.Kind) {}
+  DDGNode(DDGNode &&N) : DDGNodeBase(std::move(N)), Kind(N.Kind) {}
+  virtual ~DDGNode() = 0;
+
+  DDGNode &operator=(const DDGNode &N) {
+    DGNode::operator=(N);
+    Kind = N.Kind;
+    return *this;
+  }
+
+  DDGNode &operator=(DDGNode &&N) {
+    DGNode::operator=(std::move(N));
+    Kind = N.Kind;
+    return *this;
+  }
+
+  /// Getter for the kind of this node.
+  NodeKind getKind() const { return Kind; }
+
+  /// Collect a list of instructions, in \p IList, for which predicate \p Pred
+  /// evaluates to true when iterating over instructions of this node. Return
+  /// true if at least one instruction was collected, and false otherwise.
+  bool collectInstructions(llvm::function_ref<bool(Instruction *)> const &Pred,
+                           InstructionListType &IList) const;
+
+protected:
+  /// Setter for the kind of this node.
+  void setKind(NodeKind K) { Kind = K; }
+
+private:
+  NodeKind Kind;
+};
+
+/// Subclass of DDGNode representing single or multi-instruction nodes.
+class SimpleDDGNode : public DDGNode {
+public:
+  SimpleDDGNode() = delete;
+  SimpleDDGNode(Instruction &I);
+  SimpleDDGNode(const SimpleDDGNode &N);
+  SimpleDDGNode(SimpleDDGNode &&N);
+  ~SimpleDDGNode();
+
+  SimpleDDGNode &operator=(const SimpleDDGNode &N) {
+    DDGNode::operator=(N);
+    InstList = N.InstList;
+    return *this;
+  }
+
+  SimpleDDGNode &operator=(SimpleDDGNode &&N) {
+    DDGNode::operator=(std::move(N));
+    InstList = std::move(N.InstList);
+    return *this;
+  }
+
+  /// Get the list of instructions in this node.
+  const InstructionListType &getInstructions() const {
+    assert(!InstList.empty() && "Instruction List is empty.");
+    return InstList;
+  }
+  InstructionListType &getInstructions() {
+    return const_cast<InstructionListType &>(
+        static_cast<const SimpleDDGNode *>(this)->getInstructions());
+  }
+
+  /// Get the first/last instruction in the node.
+  Instruction *getFirstInstruction() const { return getInstructions()[0]; }
+  Instruction *getLastInstruction() const {
+    return getInstructions()[InstList.size() - 1];
+  }
+
+  /// Define classof to be able to use isa<>, cast<>, dyn_cast<>, etc.
+  static bool classof(const DDGNode *N) {
+    return N->getKind() == NodeKind::SingleInstruction ||
+           N->getKind() == NodeKind::MultiInstruction;
+  }
+  static bool classof(const SimpleDDGNode *N) { return true; }
+
+private:
+  /// Append the list of instructions in \p Input to this node.
+  void appendInstructions(const InstructionListType &Input) {
+    setKind((InstList.size() == 0 && Input.size() == 1)
+                ? NodeKind::SingleInstruction
+                : NodeKind::MultiInstruction);
+    InstList.insert(InstList.end(), Input.begin(), Input.end());
+  }
+  void appendInstructions(const SimpleDDGNode &Input) {
+    appendInstructions(Input.getInstructions());
+  }
+
+  /// List of instructions associated with a single or multi-instruction node.
+  SmallVector<Instruction *, 2> InstList;
+};
+
+/// Data Dependency Graph Edge.
+/// An edge in the DDG can represent a def-use relationship or
+/// a memory dependence based on the result of DependenceAnalysis.
+class DDGEdge : public DDGEdgeBase {
+public:
+  /// The kind of edge in the DDG
+  enum class EdgeKind { Unknown, RegisterDefUse, MemoryDependence };
+
+  explicit DDGEdge(DDGNode &N) = delete;
+  DDGEdge(DDGNode &N, EdgeKind K) : DDGEdgeBase(N), Kind(K) {}
+  DDGEdge(const DDGEdge &E) : DDGEdgeBase(E), Kind(E.getKind()) {}
+  DDGEdge(DDGEdge &&E) : DDGEdgeBase(std::move(E)), Kind(E.Kind) {}
+  DDGEdge &operator=(const DDGEdge &E) {
+    DDGEdgeBase::operator=(E);
+    Kind = E.Kind;
+    return *this;
+  }
+
+  DDGEdge &operator=(DDGEdge &&E) {
+    DDGEdgeBase::operator=(std::move(E));
+    Kind = E.Kind;
+    return *this;
+  }
+
+  /// Get the edge kind
+  EdgeKind getKind() const { return Kind; };
+
+  /// Return true if this is a def-use edge, and false otherwise.
+  bool isDefUse() const { return Kind == EdgeKind::RegisterDefUse; }
+
+  /// Return true if this is a memory dependence edge, and false otherwise.
+  bool isMemoryDependence() const { return Kind == EdgeKind::MemoryDependence; }
+
+private:
+  EdgeKind Kind;
+};
+
+/// Encapsulate some common data and functionality needed for different
+/// variations of data dependence graphs.
+template <typename NodeType> class DependenceGraphInfo {
+public:
+  using DependenceList = SmallVector<std::unique_ptr<Dependence>, 1>;
+
+  DependenceGraphInfo() = delete;
+  DependenceGraphInfo(const DependenceGraphInfo &G) = delete;
+  DependenceGraphInfo(const std::string &N, const DependenceInfo &DepInfo)
+      : Name(N), DI(DepInfo) {}
+  DependenceGraphInfo(DependenceGraphInfo &&G)
+      : Name(std::move(G.Name)), DI(std::move(G.DI)) {}
+  virtual ~DependenceGraphInfo() {}
+
+  /// Return the label that is used to name this graph.
+  const StringRef getName() const { return Name; }
+
+protected:
+  // Name of the graph.
+  std::string Name;
+
+  // Store a copy of DependenceInfo in the graph, so that individual memory
+  // dependencies don't need to be stored. Instead when the dependence is
+  // queried it is recomputed using @DI.
+  const DependenceInfo DI;
+};
+
+using DDGInfo = DependenceGraphInfo<DDGNode>;
+
+/// Data Dependency Graph
+class DataDependenceGraph : public DDGBase, public DDGInfo {
+  friend class DDGBuilder;
+
+public:
+  using NodeType = DDGNode;
+  using EdgeType = DDGEdge;
+
+  DataDependenceGraph() = delete;
+  DataDependenceGraph(const DataDependenceGraph &G) = delete;
+  DataDependenceGraph(DataDependenceGraph &&G)
+      : DDGBase(std::move(G)), DDGInfo(std::move(G)) {}
+  DataDependenceGraph(Function &F, DependenceInfo &DI);
+  DataDependenceGraph(const Loop &L, DependenceInfo &DI);
+  ~DataDependenceGraph();
+};
+
+/// Concrete implementation of a pure data dependence graph builder. This class
+/// provides custom implementation for the pure-virtual functions used in the
+/// generic dependence graph build algorithm.
+///
+/// For information about time complexity of the build algorithm see the
+/// comments near the declaration of AbstractDependenceGraphBuilder.
+class DDGBuilder : public AbstractDependenceGraphBuilder<DataDependenceGraph> {
+public:
+  DDGBuilder(DataDependenceGraph &G, DependenceInfo &D,
+             const BasicBlockListType &BBs)
+      : AbstractDependenceGraphBuilder(G, D, BBs) {}
+  DDGNode &createFineGrainedNode(Instruction &I) final override {
+    auto *SN = new SimpleDDGNode(I);
+    assert(SN && "Failed to allocate memory for simple DDG node.");
+    Graph.addNode(*SN);
+    return *SN;
+  }
+  DDGEdge &createDefUseEdge(DDGNode &Src, DDGNode &Tgt) final override {
+    auto *E = new DDGEdge(Tgt, DDGEdge::EdgeKind::RegisterDefUse);
+    assert(E && "Failed to allocate memory for edge");
+    Graph.connect(Src, Tgt, *E);
+    return *E;
+  }
+  DDGEdge &createMemoryEdge(DDGNode &Src, DDGNode &Tgt) final override {
+    auto *E = new DDGEdge(Tgt, DDGEdge::EdgeKind::MemoryDependence);
+    assert(E && "Failed to allocate memory for edge");
+    Graph.connect(Src, Tgt, *E);
+    return *E;
+  }
+};
+
+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);
+
+//===--------------------------------------------------------------------===//
+// DDG Analysis Passes
+//===--------------------------------------------------------------------===//
+
+/// Analysis pass that builds the DDG for a loop.
+class DDGAnalysis : public AnalysisInfoMixin<DDGAnalysis> {
+public:
+  using Result = std::unique_ptr<DataDependenceGraph>;
+  Result run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR);
+
+private:
+  friend AnalysisInfoMixin<DDGAnalysis>;
+  static AnalysisKey Key;
+};
+
+/// Textual printer pass for the DDG of a loop.
+class DDGAnalysisPrinterPass : public PassInfoMixin<DDGAnalysisPrinterPass> {
+public:
+  explicit DDGAnalysisPrinterPass(raw_ostream &OS) : OS(OS) {}
+  PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM,
+                        LoopStandardAnalysisResults &AR, LPMUpdater &U);
+
+private:
+  raw_ostream &OS;
+};
+
+//===--------------------------------------------------------------------===//
+// GraphTraits specializations for the DDG
+//===--------------------------------------------------------------------===//
+
+/// non-const versions of the grapth trait specializations for DDG
+template <> struct GraphTraits<DDGNode *> {
+  using NodeRef = DDGNode *;
+
+  static DDGNode *DDGGetTargetNode(DGEdge<DDGNode, DDGEdge> *P) {
+    return &P->getTargetNode();
+  }
+
+  // Provide a mapped iterator so that the GraphTrait-based implementations can
+  // find the target nodes without having to explicitly go through the edges.
+  using ChildIteratorType =
+      mapped_iterator<DDGNode::iterator, decltype(&DDGGetTargetNode)>;
+  using ChildEdgeIteratorType = DDGNode::iterator;
+
+  static NodeRef getEntryNode(NodeRef N) { return N; }
+  static ChildIteratorType child_begin(NodeRef N) {
+    return ChildIteratorType(N->begin(), &DDGGetTargetNode);
+  }
+  static ChildIteratorType child_end(NodeRef N) {
+    return ChildIteratorType(N->end(), &DDGGetTargetNode);
+  }
+
+  static ChildEdgeIteratorType child_edge_begin(NodeRef N) {
+    return N->begin();
+  }
+  static ChildEdgeIteratorType child_edge_end(NodeRef N) { return N->end(); }
+};
+
+template <>
+struct GraphTraits<DataDependenceGraph *> : public GraphTraits<DDGNode *> {
+  using nodes_iterator = DataDependenceGraph::iterator;
+  static NodeRef getEntryNode(DataDependenceGraph *DG) { return *DG->begin(); }
+  static nodes_iterator nodes_begin(DataDependenceGraph *DG) {
+    return DG->begin();
+  }
+  static nodes_iterator nodes_end(DataDependenceGraph *DG) { return DG->end(); }
+};
+
+/// const versions of the grapth trait specializations for DDG
+template <> struct GraphTraits<const DDGNode *> {
+  using NodeRef = const DDGNode *;
+
+  static const DDGNode *DDGGetTargetNode(const DGEdge<DDGNode, DDGEdge> *P) {
+    return &P->getTargetNode();
+  }
+
+  // Provide a mapped iterator so that the GraphTrait-based implementations can
+  // find the target nodes without having to explicitly go through the edges.
+  using ChildIteratorType =
+      mapped_iterator<DDGNode::const_iterator, decltype(&DDGGetTargetNode)>;
+  using ChildEdgeIteratorType = DDGNode::const_iterator;
+
+  static NodeRef getEntryNode(NodeRef N) { return N; }
+  static ChildIteratorType child_begin(NodeRef N) {
+    return ChildIteratorType(N->begin(), &DDGGetTargetNode);
+  }
+  static ChildIteratorType child_end(NodeRef N) {
+    return ChildIteratorType(N->end(), &DDGGetTargetNode);
+  }
+
+  static ChildEdgeIteratorType child_edge_begin(NodeRef N) {
+    return N->begin();
+  }
+  static ChildEdgeIteratorType child_edge_end(NodeRef N) { return N->end(); }
+};
+
+template <>
+struct GraphTraits<const DataDependenceGraph *>
+    : public GraphTraits<const DDGNode *> {
+  using nodes_iterator = DataDependenceGraph::const_iterator;
+  static NodeRef getEntryNode(const DataDependenceGraph *DG) {
+    return *DG->begin();
+  }
+  static nodes_iterator nodes_begin(const DataDependenceGraph *DG) {
+    return DG->begin();
+  }
+  static nodes_iterator nodes_end(const DataDependenceGraph *DG) {
+    return DG->end();
+  }
+};
+
+} // namespace llvm
+
+#endif // LLVM_ANALYSIS_DDG_H

llvm/include/llvm/Analysis/DependenceGraphBuilder.h

+//===- llvm/Analysis/DependenceGraphBuilder.h -------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines a builder interface that can be used to populate dependence
+// graphs such as DDG and PDG.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_DEPENDENCE_GRAPH_BUILDER_H
+#define LLVM_ANALYSIS_DEPENDENCE_GRAPH_BUILDER_H
+
+#include "llvm/ADT/EquivalenceClasses.h"
+#include "llvm/Analysis/DependenceAnalysis.h"
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/Instructions.h"
+
+namespace llvm {
+
+/// This abstract builder class defines a set of high-level steps for creating
+/// DDG-like graphs. The client code is expected to inherit from this class and
+/// define concrete implementation for each of the pure virtual functions used
+/// in the high-level algorithm.
+template <class GraphType> class AbstractDependenceGraphBuilder {
+protected:
+  using BasicBlockListType = SmallVectorImpl<BasicBlock *>;
+
+private:
+  using NodeType = typename GraphType::NodeType;
+  using EdgeType = typename GraphType::EdgeType;
+
+public:
+  using ClassesType = EquivalenceClasses<BasicBlock *>;
+  using NodeListType = SmallVector<NodeType *, 4>;
+
+  AbstractDependenceGraphBuilder(GraphType &G, DependenceInfo &D,
+                                 const BasicBlockListType &BBs)
+      : Graph(G), DI(D), BBList(BBs) {}
+  virtual ~AbstractDependenceGraphBuilder() {}
+
+  /// The main entry to the graph construction algorithm. It starts by
+  /// creating nodes in increasing order of granularity and then
+  /// adds def-use and memory edges.
+  ///
+  /// The algorithmic complexity of this implementation is O(V^2 * I^2), where V
+  /// is the number of vertecies (nodes) and I is the number of instructions in
+  /// each node. The total number of instructions, N, is equal to V * I,
+  /// therefore the worst-case time complexity is O(N^2). The average time
+  /// complexity is O((N^2)/2).
+  void populate() {
+    createFineGrainedNodes();
+    createDefUseEdges();
+    createMemoryDependencyEdges();
+  }
+
+  /// Create fine grained nodes. These are typically atomic nodes that
+  /// consist of a single instruction.
+  void createFineGrainedNodes();
+
+  /// Analyze the def-use chains and create edges from the nodes containing
+  /// definitions to the nodes containing the uses.
+  void createDefUseEdges();
+
+  /// Analyze data dependencies that exist between memory loads or stores,
+  /// in the graph nodes and create edges between them.
+  void createMemoryDependencyEdges();
+
+protected:
+  /// Create an atomic node in the graph given a single instruction.
+  virtual NodeType &createFineGrainedNode(Instruction &I) = 0;
+
+  /// Create a def-use edge going from \p Src to \p Tgt.
+  virtual EdgeType &createDefUseEdge(NodeType &Src, NodeType &Tgt) = 0;
+
+  /// Create a memory dependence edge going from \p Src to \p Tgt.
+  virtual EdgeType &createMemoryEdge(NodeType &Src, NodeType &Tgt) = 0;
+
+  /// Deallocate memory of edge \p E.
+  virtual void destroyEdge(EdgeType &E) { delete &E; }
+
+  /// Deallocate memory of node \p N.
+  virtual void destroyNode(NodeType &N) { delete &N; }
+
+  /// Map types to map instructions to nodes used when populating the graph.
+  using InstToNodeMap = DenseMap<Instruction *, NodeType *>;
+
+  /// Reference to the graph that gets built by a concrete implementation of
+  /// this builder.
+  GraphType &Graph;
+
+  /// Dependence information used to create memory dependence edges in the
+  /// 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;
+};
+
+} // namespace llvm
+
+#endif // LLVM_ANALYSIS_DEPENDENCE_GRAPH_BUILDER_H

llvm/lib/Analysis/CMakeLists.txt

add_llvm_library(LLVMAnalysis
   CallGraph.cpp
   CallGraphSCCPass.cpp
   CallPrinter.cpp
   CaptureTracking.cpp
   CmpInstAnalysis.cpp
   CostModel.cpp
   CodeMetrics.cpp
   ConstantFolding.cpp
+  DDG.cpp
   Delinearization.cpp
   DemandedBits.cpp
   DependenceAnalysis.cpp
+  DependenceGraphBuilder.cpp
   DivergenceAnalysis.cpp
   DomPrinter.cpp
   DomTreeUpdater.cpp
   DominanceFrontier.cpp
   EHPersonalities.cpp
   GlobalsModRef.cpp
   GuardUtils.cpp
   IVDescriptors.cpp

llvm/lib/Analysis/DDG.cpp

+//===- DDG.cpp - Data Dependence Graph -------------------------------------==//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// The implementation for the data dependence graph.
+//===----------------------------------------------------------------------===//
+#include "llvm/Analysis/DDG.h"
+#include "llvm/Analysis/LoopInfo.h"
+
+using namespace llvm;
+
+#define DEBUG_TYPE "ddg"
+
+template class llvm::DGEdge<DDGNode, DDGEdge>;
+template class llvm::DGNode<DDGNode, DDGEdge>;
+template class llvm::DirectedGraph<DDGNode, DDGEdge>;
+
+//===--------------------------------------------------------------------===//
+// DDGNode implementation
+//===--------------------------------------------------------------------===//
+DDGNode::~DDGNode() {}
+
+bool DDGNode::collectInstructions(
+    llvm::function_ref<bool(Instruction *)> const &Pred,
+    InstructionListType &IList) const {
+  assert(IList.empty() && "Expected the IList to be empty on entry.");
+  if (isa<SimpleDDGNode>(this)) {
+    for (auto *I : cast<const SimpleDDGNode>(this)->getInstructions())
+      if (Pred(I))
+        IList.push_back(I);
+  } else
+    llvm_unreachable("unimplemented type of node");
+  return !IList.empty();
+}
+
+raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGNode::NodeKind K) {
+  const char *Out;
+  switch (K) {
+  case DDGNode::NodeKind::SingleInstruction:
+    Out = "single-instruction";
+    break;
+  case DDGNode::NodeKind::MultiInstruction:
+    Out = "multi-instruction";
+    break;
+  default:
+    Out = "??";
+    break;
+  }
+  OS << Out;
+  return OS;
+}
+
+raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGNode &N) {
+  OS << "Node Address:" << &N << ":" << N.getKind() << "\n";
+  if (isa<SimpleDDGNode>(&N)) {
+    OS << " Instructions:\n";
+    for (auto *I : cast<const SimpleDDGNode>(&N)->getInstructions())
+      OS.indent(2) << *I << "\n";
+  } else
+    llvm_unreachable("unimplemented type of node");
+
+  OS << (N.getEdges().empty() ? " Edges:none!\n" : " Edges:\n");
+  for (auto &E : N.getEdges())
+    OS.indent(2) << *E;
+  return OS;
+}
+
+//===--------------------------------------------------------------------===//
+// SimpleDDGNode implementation
+//===--------------------------------------------------------------------===//
+
+SimpleDDGNode::SimpleDDGNode(Instruction &I)
+  : DDGNode(NodeKind::SingleInstruction), InstList() {
+  assert(InstList.empty() && "Expected empty list.");
+  InstList.push_back(&I);
+}
+
+SimpleDDGNode::SimpleDDGNode(const SimpleDDGNode &N)
+    : DDGNode(N), InstList(N.InstList) {
+  assert(((getKind() == NodeKind::SingleInstruction && InstList.size() == 1) ||
+          (getKind() == NodeKind::MultiInstruction && InstList.size() > 1)) &&
+         "constructing from invalid simple node.");
+}
+
+SimpleDDGNode::SimpleDDGNode(SimpleDDGNode &&N)
+    : DDGNode(std::move(N)), InstList(std::move(N.InstList)) {
+  assert(((getKind() == NodeKind::SingleInstruction && InstList.size() == 1) ||
+          (getKind() == NodeKind::MultiInstruction && InstList.size() > 1)) &&
+         "constructing from invalid simple node.");
+}
+
+SimpleDDGNode::~SimpleDDGNode() { InstList.clear(); }
+
+//===--------------------------------------------------------------------===//
+// DDGEdge implementation
+//===--------------------------------------------------------------------===//
+
+raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGEdge::EdgeKind K) {
+  const char *Out;
+  switch (K) {
+  case DDGEdge::EdgeKind::RegisterDefUse:
+    Out = "def-use";
+    break;
+  case DDGEdge::EdgeKind::MemoryDependence:
+    Out = "memory";
+    break;
+  default:
+    Out = "??";
+    break;
+  }
+  OS << Out;
+  return OS;
+}
+
+raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGEdge &E) {
+  OS << "[" << E.getKind() << "] to " << &E.getTargetNode() << "\n";
+  return OS;
+}
+
+//===--------------------------------------------------------------------===//
+// DataDependenceGraph implementation
+//===--------------------------------------------------------------------===//
+using BasicBlockListType = SmallVector<BasicBlock *, 8>;
+
+DataDependenceGraph::DataDependenceGraph(Function &F, DependenceInfo &D)
+    : DependenceGraphInfo(F.getName().str(), D) {
+  BasicBlockListType BBList;
+  for (auto &BB : F.getBasicBlockList())
+    BBList.push_back(&BB);
+  DDGBuilder(*this, D, BBList).populate();
+}
+
+DataDependenceGraph::DataDependenceGraph(const Loop &L, DependenceInfo &D)
+    : DependenceGraphInfo(Twine(L.getHeader()->getParent()->getName() + "." +
+                                L.getHeader()->getName())
+                              .str(),
+                          D) {
+  BasicBlockListType BBList;
+  for (BasicBlock *BB : L.blocks())
+    BBList.push_back(BB);
+  DDGBuilder(*this, D, BBList).populate();
+}
+
+DataDependenceGraph::~DataDependenceGraph() {
+  for (auto *N : Nodes) {
+    for (auto *E : *N)
+      delete E;
+    delete N;
+  }
+}
+
+raw_ostream &llvm::operator<<(raw_ostream &OS, const DataDependenceGraph &G) {
+  for (auto *Node : G)
+    OS << *Node << "\n";
+  return OS;
+}
+
+//===--------------------------------------------------------------------===//
+// DDG Analysis Passes
+//===--------------------------------------------------------------------===//
+
+/// DDG as a loop pass.
+DDGAnalysis::Result DDGAnalysis::run(Loop &L, LoopAnalysisManager &AM,
+                                     LoopStandardAnalysisResults &AR) {
+  Function *F = L.getHeader()->getParent();
+  DependenceInfo DI(F, &AR.AA, &AR.SE, &AR.LI);
+  return std::make_unique<DataDependenceGraph>(L, DI);
+}
+AnalysisKey DDGAnalysis::Key;
+
+PreservedAnalyses DDGAnalysisPrinterPass::run(Loop &L, LoopAnalysisManager &AM,
+                                              LoopStandardAnalysisResults &AR,
+                                              LPMUpdater &U) {
+  OS << "'DDG' for loop '" << L.getHeader()->getName() << "':\n";
+  OS << *AM.getResult<DDGAnalysis>(L, AR);
+  return PreservedAnalyses::all();
+}

llvm/lib/Analysis/DependenceGraphBuilder.cpp

+//===- DependenceGraphBuilder.cpp ------------------------------------------==//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+// This file implements common steps of the build algorithm for construction
+// of dependence graphs such as DDG and PDG.
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/DependenceGraphBuilder.h"
+#include "llvm/ADT/SCCIterator.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/DDG.h"
+
+using namespace llvm;
+
+#define DEBUG_TYPE "dgb"
+
+STATISTIC(TotalGraphs, "Number of dependence graphs created.");
+STATISTIC(TotalDefUseEdges, "Number of def-use edges created.");
+STATISTIC(TotalMemoryEdges, "Number of memory dependence edges created.");
+STATISTIC(TotalFineGrainedNodes, "Number of fine-grained nodes created.");
+STATISTIC(TotalConfusedEdges,
+          "Number of confused memory dependencies between two nodes.");
+STATISTIC(TotalEdgeReversals,
+          "Number of times the source and sink of dependence was reversed to "
+          "expose cycles in the graph.");
+
+using InstructionListType = SmallVector<Instruction *, 2>;
+
+//===--------------------------------------------------------------------===//
+// AbstractDependenceGraphBuilder implementation
+//===--------------------------------------------------------------------===//
+
+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));
+      ++TotalFineGrainedNodes;
+    }
+}
+
+template <class G> void AbstractDependenceGraphBuilder<G>::createDefUseEdges() {
+  for (NodeType *N : Graph) {
+    InstructionListType SrcIList;
+    N->collectInstructions([](const Instruction *I) { return true; }, SrcIList);
+
+    // Use a set to mark the targets that we link to N, so we don't add
+    // duplicate def-use edges when more than one instruction in a target node
+    // use results of instructions that are contained in N.
+    SmallPtrSet<NodeType *, 4> VisitedTargets;
+
+    for (Instruction *II : SrcIList) {
+      for (User *U : II->users()) {
+        Instruction *UI = dyn_cast<Instruction>(U);
+        if (!UI)
+          continue;
+        NodeType *DstNode = nullptr;
+        if (IMap.find(UI) != IMap.end())
+          DstNode = IMap.find(UI)->second;
+
+        // In the case of loops, the scope of the subgraph is all the
+        // basic blocks (and instructions within them) belonging to the loop. We
+        // simply ignore all the edges coming from (or going into) instructions
+        // or basic blocks outside of this range.
+        if (!DstNode) {
+          LLVM_DEBUG(
+              dbgs()
+              << "skipped def-use edge since the sink" << *UI
+              << " is outside the range of instructions being considered.\n");
+          continue;
+        }
+
+        // Self dependencies are ignored because they are redundant and
+        // uninteresting.
+        if (DstNode == N) {
+          LLVM_DEBUG(dbgs()
+                     << "skipped def-use edge since the sink and the source ("
+                     << N << ") are the same.\n");
+          continue;
+        }
+
+        if (VisitedTargets.insert(DstNode).second) {
+          createDefUseEdge(*N, *DstNode);
+          ++TotalDefUseEdges;
+        }
+      }
+    }
+  }
+}
+
+template <class G>
+void AbstractDependenceGraphBuilder<G>::createMemoryDependencyEdges() {
+  using DGIterator = typename G::iterator;
+  auto isMemoryAccess = [](const Instruction *I) {
+    return I->mayReadOrWriteMemory();
+  };
+  for (DGIterator SrcIt = Graph.begin(), E = Graph.end(); SrcIt != E; ++SrcIt) {
+    InstructionListType SrcIList;
+    (*SrcIt)->collectInstructions(isMemoryAccess, SrcIList);
+    if (SrcIList.empty())
+      continue;
+
+    for (DGIterator DstIt = SrcIt; DstIt != E; ++DstIt) {
+      if (**SrcIt == **DstIt)
+        continue;
+      InstructionListType DstIList;
+      (*DstIt)->collectInstructions(isMemoryAccess, DstIList);
+      if (DstIList.empty())
+        continue;
+      bool ForwardEdgeCreated = false;
+      bool BackwardEdgeCreated = false;
+      for (Instruction *ISrc : SrcIList) {
+        for (Instruction *IDst : DstIList) {
+          auto D = DI.depends(ISrc, IDst, true);
+          if (!D)
+            continue;
+
+          // If we have a dependence with its left-most non-'=' direction
+          // being '>' we need to reverse the direction of the edge, because
+          // the source of the dependence cannot occur after the sink. For
+          // confused dependencies, we will create edges in both directions to
+          // represent the possibility of a cycle.
+
+          auto createConfusedEdges = [&](NodeType &Src, NodeType &Dst) {
+            if (!ForwardEdgeCreated) {
+              createMemoryEdge(Src, Dst);
+              ++TotalMemoryEdges;
+            }
+            if (!BackwardEdgeCreated) {
+              createMemoryEdge(Dst, Src);
+              ++TotalMemoryEdges;
+            }
+            ForwardEdgeCreated = BackwardEdgeCreated = true;
+            ++TotalConfusedEdges;
+          };
+
+          auto createForwardEdge = [&](NodeType &Src, NodeType &Dst) {
+            if (!ForwardEdgeCreated) {
+              createMemoryEdge(Src, Dst);
+              ++TotalMemoryEdges;
+            }
+            ForwardEdgeCreated = true;
+          };
+
+          auto createBackwardEdge = [&](NodeType &Src, NodeType &Dst) {
+            if (!BackwardEdgeCreated) {
+              createMemoryEdge(Dst, Src);
+              ++TotalMemoryEdges;
+            }
+            BackwardEdgeCreated = true;
+          };
+
+          if (D->isConfused())
+            createConfusedEdges(**SrcIt, **DstIt);
+          else if (D->isOrdered() && !D->isLoopIndependent()) {
+            bool ReversedEdge = false;
+            for (unsigned Level = 1; Level <= D->getLevels(); ++Level) {
+              if (D->getDirection(Level) == Dependence::DVEntry::EQ)
+                continue;
+              else if (D->getDirection(Level) == Dependence::DVEntry::GT) {
+                createBackwardEdge(**SrcIt, **DstIt);
+                ReversedEdge = true;
+                ++TotalEdgeReversals;
+                break;
+              } else if (D->getDirection(Level) == Dependence::DVEntry::LT)
+                break;
+              else {
+                createConfusedEdges(**SrcIt, **DstIt);
+                break;
+              }
+            }
+            if (!ReversedEdge)
+              createForwardEdge(**SrcIt, **DstIt);
+          } else
+            createForwardEdge(**SrcIt, **DstIt);
+
+          // Avoid creating duplicate edges.
+          if (ForwardEdgeCreated && BackwardEdgeCreated)
+            break;
+        }
+
+        // If we've created edges in both directions, there is no more
+        // unique edge that we can create between these two nodes, so we
+        // can exit early.
+        if (ForwardEdgeCreated && BackwardEdgeCreated)
+          break;
+      }
+    }
+  }
+}
+
+template class llvm::AbstractDependenceGraphBuilder<DataDependenceGraph>;
+template class llvm::DependenceGraphInfo<DDGNode>;

llvm/lib/Passes/PassBuilder.cpp

 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/BlockFrequencyInfo.h"
 #include "llvm/Analysis/BranchProbabilityInfo.h"
 #include "llvm/Analysis/CFGPrinter.h"
 #include "llvm/Analysis/CFLAndersAliasAnalysis.h"
 #include "llvm/Analysis/CFLSteensAliasAnalysis.h"
 #include "llvm/Analysis/CGSCCPassManager.h"
 #include "llvm/Analysis/CallGraph.h"
+#include "llvm/Analysis/DDG.h"
 #include "llvm/Analysis/DemandedBits.h"
 #include "llvm/Analysis/DependenceAnalysis.h"
 #include "llvm/Analysis/DominanceFrontier.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/IVUsers.h"
 #include "llvm/Analysis/LazyCallGraph.h"
 #include "llvm/Analysis/LazyValueInfo.h"
 #include "llvm/Analysis/LoopAccessAnalysis.h"

llvm/lib/Passes/PassRegistry.def

FUNCTION_PASS_WITH_PARAMS("loop-vectorize",
                            parseLoopVectorizeOptions)
 #undef FUNCTION_PASS_WITH_PARAMS
 
 #ifndef LOOP_ANALYSIS
 #define LOOP_ANALYSIS(NAME, CREATE_PASS)
 #endif
 LOOP_ANALYSIS("no-op-loop", NoOpLoopAnalysis())
 LOOP_ANALYSIS("access-info", LoopAccessAnalysis())
+LOOP_ANALYSIS("ddg", DDGAnalysis())
 LOOP_ANALYSIS("ivusers", IVUsersAnalysis())
 LOOP_ANALYSIS("pass-instrumentation", PassInstrumentationAnalysis(PIC))
 #undef LOOP_ANALYSIS
 
 #ifndef LOOP_PASS
 #define LOOP_PASS(NAME, CREATE_PASS)
 #endif
 LOOP_PASS("invalidate<all>", InvalidateAllAnalysesPass())
 LOOP_PASS("licm", LICMPass())
 LOOP_PASS("loop-idiom", LoopIdiomRecognizePass())
 LOOP_PASS("loop-instsimplify", LoopInstSimplifyPass())
 LOOP_PASS("rotate", LoopRotatePass())
 LOOP_PASS("no-op-loop", NoOpLoopPass())
 LOOP_PASS("print", PrintLoopPass(dbgs()))
 LOOP_PASS("loop-deletion", LoopDeletionPass())
 LOOP_PASS("simplify-cfg", LoopSimplifyCFGPass())
 LOOP_PASS("strength-reduce", LoopStrengthReducePass())
 LOOP_PASS("indvars", IndVarSimplifyPass())
 LOOP_PASS("irce", IRCEPass())
 LOOP_PASS("unroll-and-jam", LoopUnrollAndJamPass())
 LOOP_PASS("unroll-full", LoopFullUnrollPass())
 LOOP_PASS("print-access-info", LoopAccessInfoPrinterPass(dbgs()))
+LOOP_PASS("print<ddg>", DDGAnalysisPrinterPass(dbgs()))
 LOOP_PASS("print<ivusers>", IVUsersPrinterPass(dbgs()))
 LOOP_PASS("print<loop-cache-cost>", LoopCachePrinterPass(dbgs()))
 LOOP_PASS("loop-predication", LoopPredicationPass())
 LOOP_PASS("guard-widening", GuardWideningPass())
 #undef LOOP_PASS
 
 #ifndef LOOP_PASS_WITH_PARAMS
 #define LOOP_PASS_WITH_PARAMS(NAME, CREATE_PASS, PARSER)
 #endif
 LOOP_PASS_WITH_PARAMS("unswitch",
                            [](bool NonTrivial) {
                              return SimpleLoopUnswitchPass(NonTrivial);
                            },
                            parseLoopUnswitchOptions)
 #undef LOOP_PASS_WITH_PARAMS

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

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

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

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

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

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