Revert "Data Dependence Graph Basics"

This reverts commit c98ec60993a7aa65073692b62f6d728b36e68ccd, which broke the sphinx-docs build.

llvm-svn: 372168

16 files changed, 1 insertions, 1845 deletions

diff --git a/llvm/docs/DependenceGraphs/DDG.rst b/llvm/docs/DependenceGraphs/DDG.rst
deleted file mode 100644
index b07b5cbe495..00000000000
--- a/llvm/docs/DependenceGraphs/DDG.rst
+++ /dev/null
@@ -1,135 +0,0 @@
-=========================
-Dependence Graphs in LLVM
-=========================
-
-.. contents::
-   :local:
-
-Dependence graphs are useful tools in compilers for analyzing relationships
-between various program elements to help guide optimizations. The ideas
-behind these graphs are described in the following two papers:
-
-.. [1] "D. J. Kuck, R. H. Kuhn, D. A. Padua, B. Leasure, and M. Wolfe (1981). DEPENDENCE GRAPHS AND COMPILER OPTIMIZATIONS."
-.. [2] "J. FERRANTE (IBM), K. J. OTTENSTEIN (Michigan Technological University) and JOE D. WARREN (Rice University), 1987. The Program Dependence Graph and Its Use in Optimization."
-
-The implementation of these ideas in LLVM may be slightly different than
-what is mentioned in the papers. These differences are documented in
-the `implementation details <implementation-details_>`_.
-
-.. _DataDependenceGraph:
-
-Data Dependence Graph
-=====================
-In its simplest form the Data Dependence Graph (or DDG) represents data
-dependencies between individual instructions. Each node in such a graph
-represents a single instruction and is referred to as an "atomic" node.
-It is also possible to combine some atomic nodes that have a simple
-def-use dependency between them into larger nodes that contain multiple-
-instructions.
-
-As described in [1]_ the DDG uses graph abstraction to group nodes
-that are part of a strongly connected component of the graph 
-into special nodes called pi-blocks. pi-blocks represent cycles of data
-dependency that prevent reordering transformations. Since any strongly
-connected component of the graph is a maximal subgraph of all the nodes
-that form a cycle, pi-blocks are at most one level deep. In other words,
-no pi-blocks are nested inside another pi-block, resulting in a 
-hierarchical representation that is at most one level deep.
-
-
-For example, consider the following:
-
-.. code-block:: c++
-
-  for (int i = 1; i < n; i++) {
-    b[i] = c[i] + b[i-1];
-  }
-
-This code contains a statement that has a loop carried dependence on
-itself creating a cycle in the DDG. The figure bellow illustrates
-how the cycle of dependency is carried through multiple def-use relations
-and a memory access dependency.
-
-.. image:: cycle.png
-
-The DDG corresponding to this example would have a pi-block that contains
-all the nodes participating in the cycle, as shown bellow:
-
-.. image:: cycle_pi.png
-
-Program Dependence Graph
-========================
-
-The Program Dependence Graph (or PDG) has a similar structure as the
-DDG, but it is capable of representing both data dependencies and
-control-flow dependencies between program elements such as
-instructions, groups of instructions, basic blocks or groups of
-basic blocks.
-
-High-Level Design
-=================
-
-The DDG and the PDG are both directed graphs and they extend the
-``DirectedGraph`` class. Each implementation extends its corresponding
-node and edge types resulting in the inheritance relationship depicted
-in the UML diagram bellow:
-
-.. image:: uml_nodes_and_edges.png
-
-Graph Construction
-------------------
-
-The graph build algorithm considers dependencies between elements of
-a given set of instructions or basic blocks. Any dependencies coming
-into or going out of instructions that do not belong to that range
-are ignored. The steps in the build algorithm for the DDG are very
-similar to the steps in the build algorithm for the PDG. As such,
-one of the design goals is to reuse the build algorithm code to
-allow creation of both DDG and PDG representations while allowing
-the two implementations to define their own distinct and independent
-node and edge types. This is achieved by using the well-known builder
-design pattern to isolate the construction of the dependence graph
-from its concrete representation.
-
-The following UML diagram depicts the overall structure of the design
-pattern as it applies to the dependence graph implementation.
-
-.. image:: uml_builder_pattern.png
-
-Notice that the common code for building the two types of graphs are
-provided in the ``DependenceGraphBuilder`` class, while the ``DDGBuilder``
-and ``PDGBuilder`` control some aspects of how the graph is constructed
-by the way of overriding virtual methods defined in ``DependenceGraphBuilder``.
-
-Note also that the steps and the names used in this diagram are for
-illustrative purposes and may be different from those in the actual
-implementation.
-
-Design Trade-offs
------------------
-
-Advantages:
-^^^^^^^^^^^
-  - Builder allows graph construction code to be reused for DDG and PDG.
-  - Builder allows us to create DDG and PDG as separate graphs.
-  - DDG nodes and edges are completely disjoint from PDG nodes and edges allowing them to change easily and independently.
-
-Disadvantages:
-^^^^^^^^^^^^^^
-  - Builder may be perceived as over-engineering at first.
-  - There are some similarities between DDG nodes and edges compared to PDG nodes and edges, but there is little reuse of the class definitions.
-
-    - This is tolerable given that the node and edge types are fairly simple and there is little code reuse opportunity anyway.
-
-
-.. _implementation-details:
-
-Implementation Details
-======================
-
-The current implementation of DDG differs slightly from the dependence
-graph described in [1]_ in the following ways:
-
-  1. The graph nodes in the paper represent three main program components, namely *assignment statements*, *for loop headers* and *while loop headers*. In this implementation, DDG nodes naturally represent LLVM IR instructions. An assignment statement in this implementation typically involves a node representing the ``store`` instruction along with a number of individual nodes computing the right-hand-side of the assignment that connect to the ``store`` node via a def-use edge.  The loop header instructions are not represented as special nodes in this implementation because they have limited uses and can be easily identified, for example, through ``LoopAnalysis``.
-  2. The paper describes five types of dependency edges between nodes namely *loop dependency*, *flow-*, *anti-*, *output-*, and *input-* dependencies. In this implementation *memory* edges represent the *flow-*, *anti-*, *output-*, and *input-* dependencies. However, *loop dependencies* are not made explicit, because they mainly represent association between a loop structure and the program elements inside the loop and this association is fairly obvious in LLVM IR itself. 
-  3. The paper describes two types of pi-blocks; *recurrences* whose bodies are SCCs and *IN* nodes whose bodies are not part of any SCC. In this impelmentation, pi-blocks are only created for *recurrences*. *IN* nodes remain as simple DDG nodes in the graph.
diff --git a/llvm/docs/DependenceGraphs/cycle.png b/llvm/docs/DependenceGraphs/cycle.png
deleted file mode 100644
index 8099c416654..00000000000
--- a/llvm/docs/DependenceGraphs/cycle.png
+++ /dev/null
diff --git a/llvm/docs/DependenceGraphs/cycle_pi.png b/llvm/docs/DependenceGraphs/cycle_pi.png
deleted file mode 100644
index ce69fd36a07..00000000000
--- a/llvm/docs/DependenceGraphs/cycle_pi.png
+++ /dev/null
diff --git a/llvm/docs/DependenceGraphs/uml_builder_pattern.png b/llvm/docs/DependenceGraphs/uml_builder_pattern.png
deleted file mode 100644
index 1651f9141de..00000000000
--- a/llvm/docs/DependenceGraphs/uml_builder_pattern.png
+++ /dev/null
diff --git a/llvm/docs/DependenceGraphs/uml_nodes_and_edges.png b/llvm/docs/DependenceGraphs/uml_nodes_and_edges.png
deleted file mode 100644
index c0ffacafca7..00000000000
--- a/llvm/docs/DependenceGraphs/uml_nodes_and_edges.png
+++ /dev/null
diff --git a/llvm/docs/SubsystemDocumentation.rst b/llvm/docs/SubsystemDocumentation.rst
index 463a17aa427..005d541ceb3 100644
--- a/llvm/docs/SubsystemDocumentation.rst
+++ b/llvm/docs/SubsystemDocumentation.rst
@@ -55,7 +55,6 @@ For API clients and LLVM developers.
    SpeculativeLoadHardening

    StackSafetyAnalysis

    LoopTerminology

-   DataDependenceGraphs

 

 :doc:`WritingAnLLVMPass`

    Information on how to write LLVM transformations and analyses.

@@ -208,7 +207,4 @@ For API clients and LLVM developers.
   variables.

 

 :doc:`LoopTerminology`

-  A document describing Loops and associated terms as used in LLVM.

-

-:doc:`DataDependenceGraphs`

-  A description of the design of the DDG (Data Dependence Graph).

+  A document describing Loops and associated terms as used in LLVM.
\ No newline at end of file
diff --git a/llvm/include/llvm/Analysis/DDG.h b/llvm/include/llvm/Analysis/DDG.h
deleted file mode 100644
index 9f28c3178fc..00000000000
--- a/llvm/include/llvm/Analysis/DDG.h
+++ /dev/null
@@ -1,372 +0,0 @@
-//===- 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().front(); }
-  Instruction *getLastInstruction() const { return getInstructions().back(); }
-
-  /// 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
diff --git a/llvm/include/llvm/Analysis/DependenceGraphBuilder.h b/llvm/include/llvm/Analysis/DependenceGraphBuilder.h
deleted file mode 100644
index b61aeb645a5..00000000000
--- a/llvm/include/llvm/Analysis/DependenceGraphBuilder.h
+++ /dev/null
@@ -1,108 +0,0 @@
-//===- 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
diff --git a/llvm/lib/Analysis/CMakeLists.txt b/llvm/lib/Analysis/CMakeLists.txt
index 3d4920e5ead..1dc9544120e 100644
--- a/llvm/lib/Analysis/CMakeLists.txt
+++ b/llvm/lib/Analysis/CMakeLists.txt
@@ -22,11 +22,9 @@ add_llvm_library(LLVMAnalysis
   CostModel.cpp
   CodeMetrics.cpp
   ConstantFolding.cpp
-  DDG.cpp
   Delinearization.cpp
   DemandedBits.cpp
   DependenceAnalysis.cpp
-  DependenceGraphBuilder.cpp
   DivergenceAnalysis.cpp
   DomPrinter.cpp
   DomTreeUpdater.cpp
diff --git a/llvm/lib/Analysis/DDG.cpp b/llvm/lib/Analysis/DDG.cpp
deleted file mode 100644
index 29778b3e0d6..00000000000
--- a/llvm/lib/Analysis/DDG.cpp
+++ /dev/null
@@ -1,181 +0,0 @@
-//===- 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;
-  case DDGNode::NodeKind::Unknown:
-    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;
-  case DDGEdge::EdgeKind::Unknown:
-    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();
-}
diff --git a/llvm/lib/Analysis/DependenceGraphBuilder.cpp b/llvm/lib/Analysis/DependenceGraphBuilder.cpp
deleted file mode 100644
index ed21cc7134f..00000000000
--- a/llvm/lib/Analysis/DependenceGraphBuilder.cpp
+++ /dev/null
@@ -1,200 +0,0 @@
-//===- 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>;
diff --git a/llvm/lib/Passes/PassBuilder.cpp b/llvm/lib/Passes/PassBuilder.cpp
index 12c4dcb86ce..460992207e6 100644
--- a/llvm/lib/Passes/PassBuilder.cpp
+++ b/llvm/lib/Passes/PassBuilder.cpp
@@ -27,7 +27,6 @@
 #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"
diff --git a/llvm/lib/Passes/PassRegistry.def b/llvm/lib/Passes/PassRegistry.def
index 4cd05ee11f6..b943e9c75ed 100644
--- a/llvm/lib/Passes/PassRegistry.def
+++ b/llvm/lib/Passes/PassRegistry.def
@@ -281,7 +281,6 @@ FUNCTION_PASS_WITH_PARAMS("mldst-motion",
 #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
@@ -304,7 +303,6 @@ 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())
diff --git a/llvm/test/Analysis/DDG/basic-a.ll b/llvm/test/Analysis/DDG/basic-a.ll
deleted file mode 100644
index 4c05259a886..00000000000
--- a/llvm/test/Analysis/DDG/basic-a.ll
+++ /dev/null
@@ -1,189 +0,0 @@
-; 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
diff --git a/llvm/test/Analysis/DDG/basic-b.ll b/llvm/test/Analysis/DDG/basic-b.ll
deleted file mode 100644
index 2a90d028a6f..00000000000
--- a/llvm/test/Analysis/DDG/basic-b.ll
+++ /dev/null
@@ -1,216 +0,0 @@
-; 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
-}
diff --git a/llvm/test/Analysis/DDG/basic-loopnest.ll b/llvm/test/Analysis/DDG/basic-loopnest.ll
deleted file mode 100644
index a2abbf8c09b..00000000000
--- a/llvm/test/Analysis/DDG/basic-loopnest.ll
+++ /dev/null
@@ -1,434 +0,0 @@
-; 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