Index: llvm/trunk/docs/DependenceGraphs/DDG.rst =================================================================== --- llvm/trunk/docs/DependenceGraphs/DDG.rst +++ llvm/trunk/docs/DependenceGraphs/DDG.rst @@ -0,0 +1,135 @@ +========================= +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 `_. + +.. _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. Index: llvm/trunk/docs/SubsystemDocumentation.rst =================================================================== --- llvm/trunk/docs/SubsystemDocumentation.rst +++ llvm/trunk/docs/SubsystemDocumentation.rst @@ -55,6 +55,7 @@ SpeculativeLoadHardening StackSafetyAnalysis LoopTerminology + DataDependenceGraphs :doc:`WritingAnLLVMPass` Information on how to write LLVM transformations and analyses. @@ -207,4 +208,7 @@ variables. :doc:`LoopTerminology` - A document describing Loops and associated terms as used in LLVM. \ No newline at end of file + A document describing Loops and associated terms as used in LLVM. + +:doc:`DataDependenceGraphs` + A description of the design of the DDG (Data Dependence Graph). Index: llvm/trunk/include/llvm/Analysis/DDG.h =================================================================== --- llvm/trunk/include/llvm/Analysis/DDG.h +++ llvm/trunk/include/llvm/Analysis/DDG.h @@ -0,0 +1,372 @@ +//===- 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 + +namespace llvm { +class DDGNode; +class DDGEdge; +using DDGNodeBase = DGNode; +using DDGEdgeBase = DGEdge; +using DDGBase = DirectedGraph; + +/// 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; + + 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 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( + static_cast(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 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 class DependenceGraphInfo { +public: + using DependenceList = SmallVector, 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; + +/// 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 { +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 { +public: + using Result = std::unique_ptr; + Result run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR); + +private: + friend AnalysisInfoMixin; + static AnalysisKey Key; +}; + +/// Textual printer pass for the DDG of a loop. +class DDGAnalysisPrinterPass : public PassInfoMixin { +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 { + using NodeRef = DDGNode *; + + static DDGNode *DDGGetTargetNode(DGEdge *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; + 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 : public GraphTraits { + 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 { + using NodeRef = const DDGNode *; + + static const DDGNode *DDGGetTargetNode(const DGEdge *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; + 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 + : public GraphTraits { + 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 Index: llvm/trunk/include/llvm/Analysis/DependenceGraphBuilder.h =================================================================== --- llvm/trunk/include/llvm/Analysis/DependenceGraphBuilder.h +++ llvm/trunk/include/llvm/Analysis/DependenceGraphBuilder.h @@ -0,0 +1,108 @@ +//===- 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 AbstractDependenceGraphBuilder { +protected: + using BasicBlockListType = SmallVectorImpl; + +private: + using NodeType = typename GraphType::NodeType; + using EdgeType = typename GraphType::EdgeType; + +public: + using ClassesType = EquivalenceClasses; + using NodeListType = SmallVector; + + 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; + + /// 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 Index: llvm/trunk/lib/Analysis/CMakeLists.txt =================================================================== --- llvm/trunk/lib/Analysis/CMakeLists.txt +++ llvm/trunk/lib/Analysis/CMakeLists.txt @@ -22,9 +22,11 @@ CostModel.cpp CodeMetrics.cpp ConstantFolding.cpp + DDG.cpp Delinearization.cpp DemandedBits.cpp DependenceAnalysis.cpp + DependenceGraphBuilder.cpp DivergenceAnalysis.cpp DomPrinter.cpp DomTreeUpdater.cpp Index: llvm/trunk/lib/Analysis/DDG.cpp =================================================================== --- llvm/trunk/lib/Analysis/DDG.cpp +++ llvm/trunk/lib/Analysis/DDG.cpp @@ -0,0 +1,181 @@ +//===- 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; +template class llvm::DGNode; +template class llvm::DirectedGraph; + +//===--------------------------------------------------------------------===// +// DDGNode implementation +//===--------------------------------------------------------------------===// +DDGNode::~DDGNode() {} + +bool DDGNode::collectInstructions( + llvm::function_ref const &Pred, + InstructionListType &IList) const { + assert(IList.empty() && "Expected the IList to be empty on entry."); + if (isa(this)) { + for (auto *I : cast(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(N)) { + OS << " Instructions:\n"; + for (auto *I : cast(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; + +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(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(L, AR); + return PreservedAnalyses::all(); +} Index: llvm/trunk/lib/Analysis/DependenceGraphBuilder.cpp =================================================================== --- llvm/trunk/lib/Analysis/DependenceGraphBuilder.cpp +++ llvm/trunk/lib/Analysis/DependenceGraphBuilder.cpp @@ -0,0 +1,200 @@ +//===- 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; + +//===--------------------------------------------------------------------===// +// AbstractDependenceGraphBuilder implementation +//===--------------------------------------------------------------------===// + +template +void AbstractDependenceGraphBuilder::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 void AbstractDependenceGraphBuilder::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 VisitedTargets; + + for (Instruction *II : SrcIList) { + for (User *U : II->users()) { + Instruction *UI = dyn_cast(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 +void AbstractDependenceGraphBuilder::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; +template class llvm::DependenceGraphInfo; Index: llvm/trunk/lib/Passes/PassBuilder.cpp =================================================================== --- llvm/trunk/lib/Passes/PassBuilder.cpp +++ llvm/trunk/lib/Passes/PassBuilder.cpp @@ -27,6 +27,7 @@ #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" Index: llvm/trunk/lib/Passes/PassRegistry.def =================================================================== --- llvm/trunk/lib/Passes/PassRegistry.def +++ llvm/trunk/lib/Passes/PassRegistry.def @@ -281,6 +281,7 @@ #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 @@ -303,6 +304,7 @@ LOOP_PASS("unroll-and-jam", LoopUnrollAndJamPass()) LOOP_PASS("unroll-full", LoopFullUnrollPass()) LOOP_PASS("print-access-info", LoopAccessInfoPrinterPass(dbgs())) +LOOP_PASS("print", DDGAnalysisPrinterPass(dbgs())) LOOP_PASS("print", IVUsersPrinterPass(dbgs())) LOOP_PASS("print", LoopCachePrinterPass(dbgs())) LOOP_PASS("loop-predication", LoopPredicationPass()) Index: llvm/trunk/test/Analysis/DDG/basic-a.ll =================================================================== --- llvm/trunk/test/Analysis/DDG/basic-a.ll +++ llvm/trunk/test/Analysis/DDG/basic-a.ll @@ -0,0 +1,189 @@ +; RUN: opt < %s -disable-output "-passes=print" 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 Index: llvm/trunk/test/Analysis/DDG/basic-b.ll =================================================================== --- llvm/trunk/test/Analysis/DDG/basic-b.ll +++ llvm/trunk/test/Analysis/DDG/basic-b.ll @@ -0,0 +1,216 @@ +; RUN: opt < %s -disable-output "-passes=print" 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 +} Index: llvm/trunk/test/Analysis/DDG/basic-loopnest.ll =================================================================== --- llvm/trunk/test/Analysis/DDG/basic-loopnest.ll +++ llvm/trunk/test/Analysis/DDG/basic-loopnest.ll @@ -0,0 +1,434 @@ +; RUN: opt < %s -disable-output "-passes=print" 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