diff --git a/llvm/include/llvm/Analysis/DDG.h b/llvm/include/llvm/Analysis/DDG.h --- a/llvm/include/llvm/Analysis/DDG.h +++ b/llvm/include/llvm/Analysis/DDG.h @@ -275,6 +275,12 @@ /// Return the label that is used to name this graph. const StringRef getName() const { return Name; } + /// Collect all the data dependency infos coming from any pair of memory + /// accesses in \p Src and \p Dst, and store them into \p Deps. Return true if + /// a dependence exists, and false otherwise. + bool getDependencies(const NodeType &Src, const NodeType &Dst, + DependenceList &Deps) const; + /// Return the root node of the graph. NodeType &getRoot() const { assert(Root && "Root node is not available yet. Graph construction may " @@ -423,6 +429,33 @@ raw_ostream &OS; }; +//===--------------------------------------------------------------------===// +// DependenceGraphInfo Implementation +//===--------------------------------------------------------------------===// + +template +bool DependenceGraphInfo::getDependencies( + const NodeType &Src, const NodeType &Dst, DependenceList &Deps) const { + assert(Deps.empty() && "Expected empty output list at the start."); + + // List of memory access instructions from src and dst nodes. + + SmallVector SrcIList, DstIList; + auto isMemoryAccess = [](const Instruction *I) { + return I->mayReadOrWriteMemory(); + }; + Src.collectInstructions(isMemoryAccess, SrcIList); + Dst.collectInstructions(isMemoryAccess, DstIList); + + for (auto *SrcI : SrcIList) + for (auto *DstI : DstIList) + if (auto Dep = + const_cast(&DI)->depends(SrcI, DstI, true)) + Deps.push_back(std::move(Dep)); + + return !Deps.empty(); +} + //===--------------------------------------------------------------------===// // GraphTraits specializations for the DDG //===--------------------------------------------------------------------===// diff --git a/llvm/include/llvm/Transforms/Scalar/LoopFission/FIG.h b/llvm/include/llvm/Transforms/Scalar/LoopFission/FIG.h new file mode 100644 --- /dev/null +++ b/llvm/include/llvm/Transforms/Scalar/LoopFission/FIG.h @@ -0,0 +1,497 @@ +//===- llvm/Transfors/Scalar/LoopFission/FIG.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 +// +//===----------------------------------------------------------------------===// + +//===----------------------------------------------------------------------===// +/// +/// \file +/// This file defines the Loop Fission Interference Graph (FIG). +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_FIG_H +#define LLVM_TRANSFORMS_SCALAR_FIG_H + +#include "llvm/ADT/DirectedGraph.h" +#include "llvm/ADT/SparseBitVector.h" +#include "llvm/Analysis/DDG.h" + +namespace llvm { + +class FIGNode; +class FIGEdge; +using FIGNodeBase = DGNode; +using FIGEdgeBase = DGEdge; +using FIGBase = DirectedGraph; + +/// Fission Interference Graph Node +/// The graph can represent the following types of nodes: +/// 1. Default node containing one or more DDG node. +/// 2. Root Node is a special node that connects to all components such that +/// there is always a path from it to any node in the graph. +class FIGNode : public FIGNodeBase { +public: + using DDGNodeSet = SmallPtrSet; + using InstructionListType = DDGNode::InstructionListType; + + enum class NodeKind { Default, Root }; + + FIGNode(const FIGNode &N) = delete; + FIGNode(FIGNode &&N) + : FIGNodeBase(std::move(N)), DDGNodes(std::move(N.DDGNodes)), + Kind(N.getKind()) {} + virtual ~FIGNode(); + + // Create a node containing the given DDG node \p DDGN. + static FIGNode *create(DDGNode &DDGN); + + FIGNode &operator=(const FIGNode &N) { + DGNode::operator=(N); + DDGNodes = N.DDGNodes; + Kind = N.Kind; + return *this; + } + + FIGNode &operator=(FIGNode &&N) { + DGNode::operator=(std::move(N)); + DDGNodes = std::move(N.DDGNodes); + Kind = N.Kind; + return *this; + } + + const DDGNodeSet &getNodes() const { return DDGNodes; } + NodeKind getKind() const { return Kind; } + + /// Insert the given DDG nodes \p Nodes into this FIG node. + void insertNodes(const DDGNodeSet &Nodes) { + DDGNodes.insert(Nodes.begin(), Nodes.end()); + } + + /// Return true if this FIG node contains the given DDG node \p DDGN. + bool containsNode(const DDGNode &DDGN) const { + return llvm::find(DDGNodes, &DDGN) != DDGNodes.end(); + } + + /// Populate \p IList with the instructions contained in the DDG nodes + /// associated with this node. Return true if at least one instructions was + /// collected, and false otherwise. + bool collectInstructions(InstructionListType &IList) const; + + /// Populate \p IList with the instructions contained in the DDG nodes + /// associated with this node, for which the predicate function \p Pred + /// evaluates to true. Return true if at least one instructions was collected, + /// and false otherwise. + bool collectInstructions(InstructionListType &IList, + function_ref Pred) const; + + /// Define classof to be able to use isa<>, cast<>, dyn_cast<>, etc. + static bool classof(const FIGNode *N) { + return N->getKind() == NodeKind::Default; + } + + /// Return true if DDG node \p N1 is connected to \p N2 via a path + /// containing only DDG edges of the given kind \p EK. + static bool areConnectedByPath(const DDGNode &N1, const DDGNode &N2, + DDGEdge::EdgeKind EK); + + /// Collect the DDG nodes that have an incident DDG edge of kind \p EK + /// stemming from any of the DDG nodes associated with FIG node \p N. Do not + /// consider input dependencies if \p SkipInputDependencies is true. + static bool collectTargetNodes(const FIGNode &N, DDGEdge::EdgeKind EK, + bool SkipInputDependencies, + const DataDependenceGraph &DDG, + DDGNodeSet &Targets); + +protected: + FIGNode(const NodeKind Kind) : FIGNodeBase(), Kind(Kind) {} + +private: + FIGNode(DDGNode &N) { DDGNodes.insert(&N); } + + /// Data dependence graph nodes associated with this FIG node. + DDGNodeSet DDGNodes; + + /// The node kind. + NodeKind Kind = NodeKind::Default; +}; + +/// Subclass of FIGNode representing the root node of the fission interference +/// graph. There should only be one such node in a given graph. +class RootFIGNode final : public FIGNode { +public: + RootFIGNode() : FIGNode(NodeKind::Root) {} + RootFIGNode(const RootFIGNode &) = delete; + RootFIGNode(RootFIGNode &&N) : FIGNode(std::move(N)) {} + + /// Define classof to be able to use isa<>, cast<>, dyn_cast<>, etc. + static bool classof(const FIGNode *N) { + return N->getKind() == NodeKind::Root; + } + static bool classof(const RootFIGNode *N) { return true; } +}; + +/// Fission Interefence Graph Edge. +/// Represents an edge between 2 nodes in the fission interference graph. +/// Edges are used to express data dependencies between nodes and to indicate +/// affinity between the nodes. +/// A root edge connects the root node to one of the components of the fission +/// interference graph. +class FIGEdge : public FIGEdgeBase { +public: + enum class EdgeKind { + DefUse, /// edge represents a def-use dependence + Memory, /// edge represents a data dependence + Affinity, /// edge represents the desire to keep nodes in the same loop + Root /// edge stems from the graph's root node + }; + + FIGEdge(const FIGEdge &) = delete; + FIGEdge(FIGEdge &&E) : FIGEdgeBase(std::move(E)), Kind(E.getKind()) {} + virtual ~FIGEdge() = 0; + + /// Create an edge incident to FIG node \p N with the given edge kind \p EK. + /// When building an affinity edge its weight is given by \p Weight. + static FIGEdge *create(FIGNode &N, EdgeKind EK, + Optional Weigth = None); + + FIGEdge &operator=(const FIGEdge &E) { + FIGEdgeBase::operator=(E); + Kind = E.Kind; + return *this; + } + + FIGEdge &operator=(FIGEdge &&E) { + FIGEdgeBase::operator=(std::move(E)); + Kind = E.Kind; + return *this; + } + + EdgeKind getKind() const { return Kind; } + +protected: + FIGEdge(FIGNode &N, EdgeKind Kind) : FIGEdgeBase(N), Kind(Kind) {} + +private: + EdgeKind Kind; +}; + +template class FIGEdgeOfKind final : public FIGEdge { +public: + FIGEdgeOfKind(FIGNode &N) : FIGEdge(N, EK) {} + FIGEdgeOfKind(const FIGEdgeOfKind &) = delete; + FIGEdgeOfKind(FIGEdgeOfKind &&E) : FIGEdge(std::move(E)) {} + + /// Define classof to be able to use isa<>, cast<>, dyn_cast<>, etc. + static bool classof(const FIGEdge *N) { return N->getKind() == EK; } + static bool classof(const FIGEdgeOfKind *) { return true; } +}; + +using DefUseFIGEdge = FIGEdgeOfKind; +using MemoryFIGEdge = FIGEdgeOfKind; +using RootFIGEdge = FIGEdgeOfKind; + +/// A weighted edge used to represents affinity between nodes. The greater the +/// weight the larger the affinity between the nodes connected by the edge. +class AffinityFIGEdge final : public FIGEdge { +public: + AffinityFIGEdge(FIGNode &N, int Weight) + : FIGEdge(N, EdgeKind::Affinity), Weight(Weight) { + assert(Weight != 0 && "Must have non zero weight"); + } + AffinityFIGEdge(const AffinityFIGEdge &) = delete; + AffinityFIGEdge(AffinityFIGEdge &&E) + : FIGEdge(std::move(E)), Weight(E.getWeight()) {} + + AffinityFIGEdge &operator=(const AffinityFIGEdge &E) { + FIGEdge::operator=(E); + Weight = E.Weight; + return *this; + } + + AffinityFIGEdge &operator=(AffinityFIGEdge &&E) { + FIGEdge::operator=(std::move(E)); + Weight = E.Weight; + return *this; + } + + int getWeight() const { return Weight; }; + void updateWeight(int W) { Weight += W; } + + /// Define classof to be able to use isa<>, cast<>, dyn_cast<>, etc. + static bool classof(const FIGEdge *N) { + return N->getKind() == EdgeKind::Affinity; + } + static bool classof(const AffinityFIGEdge *N) { return true; } + +private: + int Weight; +}; + +class NodeConnector; + +/// Fission Interference Graph +/// A directed acyclic graph where each node represents a set of memory +/// operations that are to be kept together in the same loop nest. The edges in +/// the graph represent the affinity between the nodes they join. +/// The interference graph can be partitioned using profitability heuristics +/// based on the weights of edges and on a correctness test based on the +/// reachability of nodes in the data dependence graph. Each partition in the +/// graph can be separated into a loop nest. +class FissionInterferenceGraph final : public FIGBase { + friend class NodeConnector; // needs to add edges to the graph (to connect nodes). + +public: + /// Map from a node to its index in the graph, and its reverse map. + using NodeToIndexMapTy = DenseMap; + using IndexToNodeMapTy = DenseMap; + + FissionInterferenceGraph() = delete; + FissionInterferenceGraph(const FissionInterferenceGraph &) = delete; + ~FissionInterferenceGraph(); + + /// Construct a fission interference graph for the loop nest rooted by \p + /// OutermostLoop, given the data dependence graph \p DDG. + static FissionInterferenceGraph *create(const DataDependenceGraph &DDG, + const Loop &OutermostLoop); + + bool hasRootNode() const { return (RootNode != nullptr); } + bool isRootNode(const FIGNode *N) const { + return (N && isa(*N) && hasRootNode() && *N == getRootNode()); + } + FIGNode &getRootNode() const { + assert(RootNode && "Root node is not available yet. Graph construction may " + "still be in progress\n"); + return *RootNode; + } + + const DirectedGraph::NodeListTy &getNodes() const { return Nodes; } + const DataDependenceGraph &getDDG() const { return DDG; } + + /// Returns the number of nodes in the graph (excluding the root node). + unsigned size() const { + return RootNode ? FIGBase::size() - 1 : FIGBase::size(); + } + + /// Retrieve the node \p N graph index. + unsigned getNodeIndex(const FIGNode &N) const { + assert(NodeToIndexMap.find(&N) != NodeToIndexMap.end() && + "Could not find node in map"); + return NodeToIndexMap.lookup(&N); + }; + + /// Retrieve a graph node given its graph index \p I. + FIGNode &getNode(unsigned I) const { + assert(IndexToNodeMap.find(I) != IndexToNodeMap.end() && + "Could not find node in map"); + return *IndexToNodeMap.lookup(I); + }; + + /// Return true if any of the DDG nodes contained in FIG node \p N reach any + /// of the DDG nodes contained in FIG node \p Other via a path containing only + /// DDG edges of the given kind \p EK. + static bool areConnectedByPath(const FIGNode &N, const FIGNode &Other, + DDGEdge::EdgeKind EK); + + /// Return true if FIG node \N has a memory dependence with FIG node \p Other. + /// Do not consider input dependencies if \p SkipInputDependencies is true. + static bool haveMemoryDependence(const FIGNode &N, const FIGNode &Other, + const DataDependenceGraph &DDG, + bool SkipInputDependencies = false); + + /// Return true FIG node \p N has a def-use dependence with \p Other. + static bool haveDefUseDependence(const FIGNode &N, const FIGNode &Other) { + return areConnectedByPath(N, Other, DDGEdge::EdgeKind::RegisterDefUse); + } + +private: + FissionInterferenceGraph(const DataDependenceGraph &DDG) + : FIGBase(), DDG(DDG) {} + + /// This member function uses the Data dependence graph (DDG) to populate the + /// interference graph. Data dependencies are enforced by connecting the graph + /// nodes with edges. After construction the interference graph is guaranteed + /// to be acyclic. Each node in the graph represents a loop nest. + /// A topological sort ensures correct loop nests generation (i.e. data + /// dependencies are preserved). + void populate(const Loop &OuterMostLoop); + + /// Add the given node \p N to the graph. + bool addNode(FIGNode &N); + + /// Connect the \p Src and \p Dst nodes using the given edge \p E. + /// Return true if the edge was added to the graph and false otherwise (an + /// existing edge was reused). + bool addEdge(FIGNode &Src, FIGNode &Dst, FIGEdge &E); + + /// Connect graph nodes with an edge that represents the data dependencies + /// between their DDG nodes. Return true if any edge was created and false + /// otherwise. + bool createDependencyEdges(); + + /// Create a root node that connects to every subgraph. For example given: + /// G: {N1-->N2, N3-->N4, N5} + /// The root node would be connected to the subgraphs rooted by N1, N3 and N5. + void createAndConnectRootNode(); + +private: + const DataDependenceGraph &DDG; + + /// The graph root node (connected to all subgraphs in the graph). + RootFIGNode *RootNode = nullptr; + + /// A map from a node to its unique graph index. + NodeToIndexMapTy NodeToIndexMap; + + /// A map from the node graph index to the node. + IndexToNodeMapTy IndexToNodeMap; + + /// Used to connect nodes in the graph. + NodeConnector *NC = nullptr; +}; + +/// A class used to connect nodes in a fission interference graph. +class NodeConnector final { + friend class FissionInterferenceGraph; + FissionInterferenceGraph &G; + +public: + NodeConnector() = delete; + NodeConnector(const NodeConnector &) = delete; + NodeConnector &operator=(const NodeConnector &) = delete; + + /// Connect nodes for which the given predicate function \p Selector evaluates + /// to true. The edges created are given the kind \p EK. + bool + connectNodes(function_ref Selector, + FIGEdge::EdgeKind EK); + + /// Connect nodes for which the given predicate function \p Selector evaluates + /// to true. The affinity edges created are given the weight returned by the + /// \p GetWeight function. + bool + connectNodes(function_ref Selector, + function_ref GetWeight); + + /// Connect nodes for which the given function \p Selector return non-zero + /// with an affinity edge having weight equal to the returned value of + /// \p Selector. + bool connectNodes( + function_ref Selector); + + /// Connect nodes \p N1 and \p N2 with a new edge of the same kind as the + /// given edge \p E. + bool connectNodes(FIGNode &N1, FIGNode &N2, const FIGEdge &E) const; + +private: + NodeConnector(FissionInterferenceGraph &G) : G(G) {} + + /// Connect nodes \p N1 and \p N2 with an edge of the given the kind \p EK. + bool connectNodes(FIGNode &N1, FIGNode &N2, FIGEdge::EdgeKind EK) const; + + /// Connect nodes \p N1 and \p N2 with an affinity edge of the weight \p + /// Weight. + bool connectNodes(FIGNode &N1, FIGNode &N2, int Weight) const; +}; + +raw_ostream &operator<<(raw_ostream &, const FIGNode &); +raw_ostream &operator<<(raw_ostream &, const FIGEdge &); +raw_ostream &operator<<(raw_ostream &, const FissionInterferenceGraph &); + +//===--------------------------------------------------------------------===// +// GraphTraits specializations for the interference graph +//===--------------------------------------------------------------------===// + +/// non-const versions of the grapth trait specializations the FIG. +template <> struct GraphTraits { + using NodeRef = FIGNode *; + + static NodeRef FIGGetTargetNode(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 = FIGNode::iterator; + + static NodeRef getEntryNode(NodeRef N) { return N; } + static ChildIteratorType child_begin(NodeRef N) { + return ChildIteratorType(N->begin(), &FIGGetTargetNode); + } + static ChildIteratorType child_end(NodeRef N) { + return ChildIteratorType(N->end(), &FIGGetTargetNode); + } + 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 NodeRef = FIGNode *; + using nodes_iterator = FissionInterferenceGraph::iterator; + + static NodeRef getEntryNode(FissionInterferenceGraph *FIG) { + return &FIG->getRootNode(); + } + static nodes_iterator nodes_begin(FissionInterferenceGraph *FIG) { + return FIG->findNode(FIG->getRootNode()); + } + static nodes_iterator nodes_end(FissionInterferenceGraph *FIG) { + return FIG->end(); + } +}; + +/// const versions of the grapth trait specializations for the FIG. +template <> struct GraphTraits { + using NodeRef = const FIGNode *; + + static NodeRef FIGGetTargetNode(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 = FIGNode::const_iterator; + + static NodeRef getEntryNode(NodeRef N) { return N; } + static ChildIteratorType child_begin(NodeRef N) { + return ChildIteratorType(N->begin(), &FIGGetTargetNode); + } + static ChildIteratorType child_end(NodeRef N) { + return ChildIteratorType(N->end(), &FIGGetTargetNode); + } + 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 NodeRef = const FIGNode *; + using nodes_iterator = FissionInterferenceGraph::const_iterator; + + static NodeRef getEntryNode(const FissionInterferenceGraph *FIG) { + return &FIG->getRootNode(); + } + static nodes_iterator nodes_begin(const FissionInterferenceGraph *FIG) { + return FIG->findNode(FIG->getRootNode()); + } + static nodes_iterator nodes_end(const FissionInterferenceGraph *FIG) { + return FIG->end(); + } +}; + +} // namespace llvm + +#endif // LLVM_TRANSFORMS_SCALAR_FIG_H diff --git a/llvm/lib/Transforms/Scalar/CMakeLists.txt b/llvm/lib/Transforms/Scalar/CMakeLists.txt --- a/llvm/lib/Transforms/Scalar/CMakeLists.txt +++ b/llvm/lib/Transforms/Scalar/CMakeLists.txt @@ -28,6 +28,7 @@ LoopDeletion.cpp LoopDataPrefetch.cpp LoopDistribute.cpp + LoopFission/FIG.cpp LoopFuse.cpp LoopIdiomRecognize.cpp LoopInstSimplify.cpp diff --git a/llvm/lib/Transforms/Scalar/LoopFission/FIG.cpp b/llvm/lib/Transforms/Scalar/LoopFission/FIG.cpp new file mode 100644 --- /dev/null +++ b/llvm/lib/Transforms/Scalar/LoopFission/FIG.cpp @@ -0,0 +1,591 @@ +//===- FIG.cpp - Loop Fission Interference 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 +// +//===----------------------------------------------------------------------===// + +//===----------------------------------------------------------------------===// +/// +/// \file +/// The implementation for the loop fission interference graph (FIG). +/// +//===----------------------------------------------------------------------===// + +#include "llvm/Transforms/Scalar/LoopFission/FIG.h" +#include "llvm/ADT/SCCIterator.h" + +using namespace llvm; + +#define DEBUG_TYPE "fig" +static const char *VerboseDebug = DEBUG_TYPE "-verbose"; + +template class llvm::DGEdge; +template class llvm::DGNode; +template class llvm::DirectedGraph; + +//===--------------------------------------------------------------------===// +// FIGNode implementation +//===--------------------------------------------------------------------===// + +FIGNode::~FIGNode() { DDGNodes.clear(); } + +FIGNode *FIGNode::create(DDGNode &DDGN) { + FIGNode *N = new FIGNode(DDGN); + return N; +} + +bool FIGNode::collectInstructions(InstructionListType &IList) const { + auto AllInstructions = [](Instruction *I) { return true; }; + return collectInstructions(IList, AllInstructions); +} + +bool FIGNode::collectInstructions( + InstructionListType &IList, function_ref Pred) const { + assert(IList.empty() && "Expecting instruction list to be empty"); + for (const DDGNode *N : DDGNodes) { + SmallVector NodeIList; + if (N->collectInstructions(Pred, NodeIList)) + IList.append(NodeIList.begin(), NodeIList.end()); + } + return !IList.empty(); +} + +bool FIGNode::areConnectedByPath(const DDGNode &N1, const DDGNode &N2, + DDGEdge::EdgeKind EK) { + SmallVector Worklist; + Worklist.push_back(&N1); + + do { + const DDGNode *N = Worklist.pop_back_val(); + for (const DDGEdge *E : N->getEdges()) { + // Consider only the edges we care about. + if (E->getKind() != EK) + continue; + + const DDGNode &Dst = E->getTargetNode(); + auto *PiBlock = dyn_cast(&Dst); + + if ((&Dst == &N2) || // N is directly connected to N2 + (PiBlock && // N is connected to a PiBlock containing N2 + any_of(PiBlock->getNodes(), + [&N2](const DDGNode *N) { return (*N == N2); }))) { + DEBUG_WITH_TYPE(VerboseDebug, { + dbgs() << "FIG: DDG node " << &N1 << " is connected to DDG node " + << &N2 << "\n"; + }); + return true; + } + + Worklist.push_back(&Dst); + } + } while (!Worklist.empty()); + + return false; +} + +bool FIGNode::collectTargetNodes(const FIGNode &N, DDGEdge::EdgeKind EK, + bool SkipInputDependencies, + const DataDependenceGraph &DDG, + DDGNodeSet &Targets) { + assert(Targets.empty() && "Expecting empty list"); + + for (const DDGNode *Src : N.getNodes()) { + for (DDGEdge *E : Src->getEdges()) { + // Consider only the edges we care about. + if (E->getKind() != EK) + continue; + + DDGNode &Dst = E->getTargetNode(); + + // Prune input memory edges if requested. + if (SkipInputDependencies && EK == DDGEdge::EdgeKind::MemoryDependence) { + DataDependenceGraph::DependenceList Deps; + + DDG.getDependencies(*Src, Dst, Deps); + if (all_of(Deps, [](const std::unique_ptr &D) { + return D->isInput(); + })) + continue; + } + + Targets.insert(&Dst); + } + } + + return !Targets.empty(); +} + +//===--------------------------------------------------------------------===// +// FIGEdge implementation +//===--------------------------------------------------------------------===// + +FIGEdge::~FIGEdge() {} + +FIGEdge *FIGEdge::create(FIGNode &N, EdgeKind EK, Optional Weight) { + FIGEdge *E = nullptr; + switch (EK) { + case FIGEdge::EdgeKind::DefUse: + E = new DefUseFIGEdge(N); + break; + case FIGEdge::EdgeKind::Memory: + E = new MemoryFIGEdge(N); + break; + case FIGEdge::EdgeKind::Root: + E = new RootFIGEdge(N); + break; + case FIGEdge::EdgeKind::Affinity: + assert(Weight.hasValue() && "Expecting a weight"); + E = new AffinityFIGEdge(N, Weight.getValue()); + break; + } + assert(E && "Failed to allocate memory for edge"); + return E; +} + +//===--------------------------------------------------------------------===// +// FissionInterferenceGraph implementation +//===--------------------------------------------------------------------===// + +FissionInterferenceGraph::~FissionInterferenceGraph() { + for (FIGNode *N : Nodes) { + for (FIGEdge *E : *N) + delete E; + delete N; + } + NodeToIndexMap.clear(); + IndexToNodeMap.clear(); + + delete NC; +} + +FissionInterferenceGraph * +FissionInterferenceGraph::create(const DataDependenceGraph &DDG, + const Loop &OutermostLoop) { + auto *FIG = new FissionInterferenceGraph(DDG); + FIG->NC = new NodeConnector(*FIG); + FIG->populate(OutermostLoop); + return FIG; +} + +bool FissionInterferenceGraph::areConnectedByPath(const FIGNode &N, + const FIGNode &Other, + DDGEdge::EdgeKind EK) { + return any_of(N.getNodes(), [&](const DDGNode *Src) { + return any_of(Other.getNodes(), [&](const DDGNode *Dst) { + return FIGNode::areConnectedByPath(*Src, *Dst, EK); + }); + }); +} + +bool FissionInterferenceGraph::haveMemoryDependence( + const FIGNode &N, const FIGNode &Other, const DataDependenceGraph &DDG, + bool SkipInputDependencies) { + FIGNode::DDGNodeSet Targets; + if (!FIGNode::collectTargetNodes(N, DDGEdge::EdgeKind::MemoryDependence, + SkipInputDependencies, DDG, Targets)) + return false; + + return any_of(Targets, [&Other](const DDGNode *T) { + auto *PiBlock = dyn_cast(T); + return ( + Other.containsNode(*T) || // T is in 'Other' + (PiBlock && // A node in the PiBlock T is in 'Other' + any_of(PiBlock->getNodes(), [&Other](const DDGNode *NodeInPiBlock) { + return Other.containsNode(*NodeInPiBlock); + }))); + }); +} + +void FissionInterferenceGraph::populate(const Loop &OuterMostLoop) { + LLVM_DEBUG(dbgs() << "FIG: Populating graph\n"); + + auto ContainsMemoryInstruction = [&](const DDGNode *N) { + auto Selector = [&](const Instruction *I) { + return I->mayReadOrWriteMemory(); + }; + + SmallVector IList; + return N->collectInstructions(Selector, IList); + }; + + DEBUG_WITH_TYPE(VerboseDebug, + { dbgs() << "Data Dependence Graph:\n" << DDG << "\n"; }); + + // Create the initial interference graph. Nodes that are in a Pi Block (in the + // DDG), and access memory, are placed into the same FIG node. Nodes that are + // not part of a Pi block, and access memory, are initially added in separate + // FIG nodes. + for (DDGNode *DDGN : DDG) { + if (isa(DDGN) || DDG.getPiBlock(*DDGN)) + continue; + if (!ContainsMemoryInstruction(DDGN)) + continue; + + auto *FIGN = FIGNode::create(*DDGN); + assert(FIGN && "Failed to allocate memory for node."); + addNode(*FIGN); + DEBUG_WITH_TYPE(VerboseDebug, + { dbgs() << "FIG: Created node " << *FIGN << "\n"; }); + } + + dbgs() << "FIG: Initial Graph:\n" << *this; + LLVM_DEBUG(dbgs() << "FIG: Initial Graph:\n" << *this); + + // Connect nodes with edges that summarize the dependencies between the DDG + // nodes they contain. + createDependencyEdges(); + + // Create a root node that connects to every subgraph. This allows us to reach + // all the nodes in the graph when using iterators. + createAndConnectRootNode(); + +#ifndef NDEBUG + // The graph should not contain duplicate edges. + assert(all_of(Nodes, + [this](const FIGNode *Curr) { + return all_of(Nodes, [&](const FIGNode *Other) { + SmallVector EL; + Curr->findEdgesTo(*Other, EL); + return (EL.size() <= 1); + }); + }) && + "Graph should not contain duplicate edges"); +#endif + + LLVM_DEBUG(dbgs() << "FIG: Populated Graph:\n" << *this); +} + +bool FissionInterferenceGraph::addNode(FIGNode &N) { + if (!FIGBase::addNode(N)) + return false; + + // Add the new node to the node index map and its reverse map. + size_t index = NodeToIndexMap.size() + 1; + NodeToIndexMap.insert(std::make_pair(&N, index)); + IndexToNodeMap.insert(std::make_pair(index, &N)); + + return true; +} + +bool FissionInterferenceGraph::addEdge(FIGNode &Src, FIGNode &Dst, FIGEdge &E) { + SmallVector EL; + + // Add a new edge if there are no existing edges between the nodes. + if (!Src.findEdgesTo(Dst, EL)) { + connect(Src, Dst, E); + return true; + } + + // Attempt to reuse an existing edge. + switch (E.getKind()) { + case FIGEdge::EdgeKind::DefUse: + case FIGEdge::EdgeKind::Memory: + case FIGEdge::EdgeKind::Root: + if (find_if(EL, [&E](const FIGEdge *EE) { + return EE->getKind() == E.getKind(); + }) == EL.end()) { + connect(Src, Dst, E); + return true; + } + break; + + case FIGEdge::EdgeKind::Affinity: { + // Update the weight of an existing affinity edge, or add the new edge. + auto IT = find_if( + EL, [&E](const FIGEdge *EE) { return EE->getKind() == E.getKind(); }); + + if (IT != EL.end()) { + AffinityFIGEdge *AE = cast(*IT); + AE->updateWeight(cast(E).getWeight()); + } else { + connect(Src, Dst, E); + return true; + } + } break; + } + + return false; +} + +bool FissionInterferenceGraph::createDependencyEdges() { + LLVM_DEBUG( + { dbgs() << "FIG: Creating edges to enforce data dependencies\n"; }); + + // Filter graph nodes that have a memory dependence between them. + auto WithMemoryDependence = [&](const FIGNode &N1, const FIGNode &N2) { + constexpr bool SkipInputDependencies = true; + bool HaveMemoryDependence = + haveMemoryDependence(N1, N2, DDG, SkipInputDependencies); + LLVM_DEBUG(if (HaveMemoryDependence) { + dbgs().indent(2) << "FIG: Node (" << getNodeIndex(N1) << ")" + << " has a memory dependence with (" << getNodeIndex(N2) + << ")\n"; + }); + return HaveMemoryDependence; + }; + + bool DidSomething = + NC->connectNodes(WithMemoryDependence, FIGEdge::EdgeKind::Memory); + + LLVM_DEBUG(dbgs() << "FIG: Creating edges for def-use dependencies\n";); + + // Filter graph nodes that have a def-use dependence between them. + auto WithDefUseDependence = [&](const FIGNode &N1, const FIGNode &N2) { + bool HaveDefUseDependence = haveDefUseDependence(N1, N2); + LLVM_DEBUG(if (HaveDefUseDependence) { + dbgs().indent(2) << "FIG: Node (" << getNodeIndex(N1) << ")" + << " has a def-use dependence with (" << getNodeIndex(N2) + << ")\n"; + }); + return HaveDefUseDependence; + }; + DidSomething |= + NC->connectNodes(WithDefUseDependence, FIGEdge::EdgeKind::DefUse); + + return DidSomething; +} + +void FissionInterferenceGraph::createAndConnectRootNode() { + LLVM_DEBUG({ dbgs() << "FIG: Creating Root Node\n"; }); + assert(!RootNode && "The graph is not expected to have a root node already"); + + RootNode = new RootFIGNode(); + assert(RootNode && "Failed to allocate memory for node."); + addNode(*RootNode); + + // Connect the root node to every subgraph. For example given the graph: + // {N1-->N2, N3-->N4, N5} + // The root node would be connected to N1, N3 and N5: + // R-->N1-->N2 + // |-->N3-->N4 + // |-->N5 + SmallPtrSet ReachableFromRoot; + for (FIGNode *N : Nodes) { + if (isRootNode(N)) + continue; + + for (const FIGNode *I : depth_first(N)) { + if (I == N) { + // Connect the root node to the subgraph rooted by N. + bool BelongsToReachableSubgraph = + (ReachableFromRoot.find(I) != ReachableFromRoot.end()); + + if (!BelongsToReachableSubgraph) { + assert(!RootNode->hasEdgeTo(*N) && "RootNode shouldn't be connected"); + auto *E = FIGEdge::create(*N, FIGEdge::EdgeKind::Root); + connect(*RootNode, *N, *E); + ReachableFromRoot.insert(I); + + DEBUG_WITH_TYPE(VerboseDebug, { + dbgs().indent(2) << "Connected Root node to: " << N << "\n"; + }); + } + + continue; + } + + ReachableFromRoot.insert(I); + + // Remove edges from the RootNode to nodes that are in an already + // connected subgraph. + if (RootNode->hasEdgeTo(*N)) { + SmallVector EL; + RootNode->findEdgesTo(*I, EL); + for (FIGEdge *E : EL) { + assert(isa(E) && "Unexpected kind of edge"); + RootNode->removeEdge(*E); + DEBUG_WITH_TYPE(VerboseDebug, { + dbgs().indent(2) << "Removed Root node edge:" << *E << "\n"; + }); + delete E; + } + } + } + } + + LLVM_DEBUG({ dbgs() << "FIG: Root node " << *RootNode << "\n"; }); +} + +//===--------------------------------------------------------------------===// +// NodeConnector implementation +//===--------------------------------------------------------------------===// + +bool NodeConnector::connectNodes( + function_ref Selector, + FIGEdge::EdgeKind EK) { + assert((EK != FIGEdge::EdgeKind::Affinity) && + "Not expecting an affinity edge"); + + // Connect all graph nodes that satisfy the 'Selector' function with an edge + // of the given kind. + bool DidSomething = false; + for (FIGNode *Curr : G.getNodes()) { + for (FIGNode *Other : G.getNodes()) + if (Other != Curr && Selector(*Curr, *Other)) + DidSomething |= connectNodes(*Curr, *Other, EK); + } + + LLVM_DEBUG({ + if (!DidSomething) + dbgs().indent(2) << "FIG: No nodes connected\n"; + }); + + return DidSomething; +} + +bool NodeConnector::connectNodes( + function_ref Selector, + function_ref GetWeight) { + + // Connect all graph nodes that satisfy the 'Selector' function with an + // affinity edge having weight given by the 'GetWeight' function. + bool DidSomething = false; + for (FIGNode *Curr : G.getNodes()) { + for (FIGNode *Other : G.getNodes()) + if (Curr != Other && Selector(*Curr, *Other)) + DidSomething |= connectNodes(*Curr, *Other, GetWeight(*Curr, *Other)); + } + + LLVM_DEBUG({ + if (!DidSomething) + dbgs().indent(2) << "FIG: No nodes connected\n"; + }); + + return DidSomething; +} + +bool NodeConnector::connectNodes( + function_ref Selector) { + + // Connect all nodes for which the given function 'Selector' return non-zero + // with an affinity edge having weight equal to the value returned. + bool DidSomething = false; + for (FIGNode *Curr : G.getNodes()) { + for (FIGNode *Other : G.getNodes()) { + if (Other == Curr) + continue; + if (int Weight = Selector(*Curr, *Other)) + DidSomething |= connectNodes(*Curr, *Other, Weight); + } + } + + LLVM_DEBUG({ + if (!DidSomething) + dbgs().indent(2) << "FIG: No nodes connected\n"; + }); + + return DidSomething; +} + +bool NodeConnector::connectNodes(FIGNode &N1, FIGNode &N2, + const FIGEdge &E) const { + return isa(E) + ? connectNodes(N1, N2, cast(E).getWeight()) + : connectNodes(N1, N2, E.getKind()); +} + +bool NodeConnector::connectNodes(FIGNode &N1, FIGNode &N2, + FIGEdge::EdgeKind EK) const { + assert((EK != FIGEdge::EdgeKind::Affinity) && "Edge kind unexpected"); + + // Create a new edge of the given kind and insert it in the graph (unless an + // existing one can be used). + auto *E = FIGEdge::create(N2, EK); + if (!G.addEdge(N1, N2, *E)) { + delete E; + return false; + } + + DEBUG_WITH_TYPE(VerboseDebug, { + dbgs().indent(2) << "FIG: Connected node " << &N1 << " with node " << &N2 + << " using edge: " << *E << "\n"; + }); + + return true; +} + +bool NodeConnector::connectNodes(FIGNode &N1, FIGNode &N2, int Weight) const { + assert(Weight != 0 && "Expecting non-zero weight"); + + // Create a new affinity edge and insert it in the graph (unless an existing + // one can be used). + auto *E = FIGEdge::create(N2, FIGEdge::EdgeKind::Affinity, Weight); + if (!G.addEdge(N1, N2, *E)) { + delete E; + return false; + } + + DEBUG_WITH_TYPE(VerboseDebug, { + dbgs().indent(2) << "FIG: Connected node " << &N1 << " with node " << &N2 + << " using edge: " << *E << "\n"; + }); + + return true; +} + +raw_ostream &llvm::operator<<(raw_ostream &OS, const FIGNode &N) { + OS.indent(2) << "Address: " << &N << "\n"; + + if (auto *RN = dyn_cast(&N)) + OS.indent(2) << "Kind: RootNode\n"; + else { + // Associated DDG nodes. + OS.indent(2) << "DDG Nodes (" << N.getNodes().size() << "):"; + for (auto *N : N.getNodes()) + OS << " " << N; + OS << "\n"; + + // Instructions. + SmallVector IList; + N.collectInstructions(IList); + + OS.indent(2) << "Instructions:\n"; + for (const auto *I : IList) + OS.indent(4) << *I << "\n"; + } + + // Outgoing edges. + OS.indent(2) << (N.getEdges().empty() ? "Edges: none\n" : "Edges:\n"); + for (auto *E : N.getEdges()) + OS.indent(4) << *E << "\n"; + + return OS; +} + +raw_ostream &llvm::operator<<(raw_ostream &OS, const FIGEdge &E) { + OS << "[" << &E.getTargetNode(); + + OS << ", Kind="; + switch (E.getKind()) { + case FIGEdge::EdgeKind::Root: + OS << "Root"; + break; + case FIGEdge::EdgeKind::DefUse: + OS << "DefUse"; + break; + case FIGEdge::EdgeKind::Memory: + OS << "Memory"; + break; + case FIGEdge::EdgeKind::Affinity: + OS << "Affinity"; + OS << ", Weight=" << cast(E).getWeight(); + break; + } + OS << "]"; + + + return OS; +} + +raw_ostream &llvm::operator<<(raw_ostream &OS, + const FissionInterferenceGraph &FIG) { + OS << "Num. of Nodes = " << FIG.size() << "\n"; + for (const FIGNode *N : FIG) { + OS << "Node (" << FIG.getNodeIndex(*N) << ")\n" << *N; + OS << "\n"; + } + + return OS; +} diff --git a/llvm/unittests/Transforms/Scalar/CMakeLists.txt b/llvm/unittests/Transforms/Scalar/CMakeLists.txt --- a/llvm/unittests/Transforms/Scalar/CMakeLists.txt +++ b/llvm/unittests/Transforms/Scalar/CMakeLists.txt @@ -19,3 +19,5 @@ if (CMAKE_COMPILER_IS_GNUCXX AND CMAKE_CXX_COMPILER_VERSION VERSION_GREATER 6.0 AND CMAKE_CXX_COMPILER_VERSION VERSION_LESS 9.0) set_source_files_properties(LoopPassManagerTest.cpp PROPERTIES COMPILE_FLAGS -Wno-unused-function) endif() + +add_subdirectory(LoopFission) diff --git a/llvm/unittests/Transforms/Scalar/LoopFission/CMakeLists.txt b/llvm/unittests/Transforms/Scalar/LoopFission/CMakeLists.txt new file mode 100644 --- /dev/null +++ b/llvm/unittests/Transforms/Scalar/LoopFission/CMakeLists.txt @@ -0,0 +1,20 @@ +set(LLVM_LINK_COMPONENTS + Analysis + AsmParser + Core + Passes + Support + ScalarOpts + TransformUtils +) + +add_llvm_unittest(LoopFissionTests + LoopFissionTest.cpp +) + +target_link_libraries(LoopFissionTests PRIVATE LLVMTestingSupport) + +# Workaround for the gcc 6.1 bug https://gcc.gnu.org/bugzilla/show_bug.cgi?id=80916. +if (CMAKE_COMPILER_IS_GNUCXX AND CMAKE_CXX_COMPILER_VERSION VERSION_GREATER 6.0 AND CMAKE_CXX_COMPILER_VERSION VERSION_LESS 9.0) + set_source_files_properties(LoopPassManagerTest.cpp PROPERTIES COMPILE_FLAGS -Wno-unused-function) +endif() diff --git a/llvm/unittests/Transforms/Scalar/LoopFission/LoopFissionTest.cpp b/llvm/unittests/Transforms/Scalar/LoopFission/LoopFissionTest.cpp new file mode 100644 --- /dev/null +++ b/llvm/unittests/Transforms/Scalar/LoopFission/LoopFissionTest.cpp @@ -0,0 +1,127 @@ +//===- LoopFissionTest.cpp - Unit tests for LoopFission -------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +#include "llvm/Analysis/TargetLibraryInfo.h" +#include "llvm/AsmParser/Parser.h" +#include "llvm/Support/SourceMgr.h" +#include "llvm/Support/TargetRegistry.h" +#include "llvm/Support/TargetSelect.h" +#include "llvm/Target/TargetMachine.h" +#include "llvm/Transforms/Scalar/LoopFission/FIG.h" +#include "gtest/gtest.h" + +using namespace llvm; + +/// Build the loop fission interferance graph for a loop nest and run the given +/// test \p Test. +static void runTest(Module &M, StringRef FuncName, + function_ref + Test) { + auto *F = M.getFunction(FuncName); + ASSERT_NE(F, nullptr) << "Could not find " << FuncName; + + TargetLibraryInfoImpl TLII; + TargetLibraryInfo TLI(TLII); + AssumptionCache AC(*F); + DominatorTree DT(*F); + LoopInfo LI(DT); + ScalarEvolution SE(*F, TLI, AC, DT, LI); + AliasAnalysis AA(TLI); + DependenceInfo DI(F, &AA, &SE, &LI); + + Test(*F, DI, LI, SE); +} + +static std::unique_ptr makeLLVMModule(LLVMContext &Context, + const char *ModuleStr) { + SMDiagnostic Err; + return parseAssemblyString(ModuleStr, Err, Context); +} + +// Test loop containing 2 nodes with a memory dependence. +// for (int i = 1; i < 100; ++i) { +// A[i] = A[i-1]; +// ============================== +// B[i] = A[i]; +TEST(LoopFissionTests, LoopCarriedDepTest1) { + const char *ModuleStr = R"( +define void @test1(i32* noalias %A, i32* noalias %B) { +entry: + br label %for.outer + +for.outer: + %i = phi i32 [ 0, %entry ], [ %inci, %for.outer ] + %sub = sub i32 %i, 1 + %arrayidx = getelementptr inbounds i32, i32* %A, i32 %sub + %0 = load i32, i32* %arrayidx, align 4 + %arrayidx1 = getelementptr inbounds i32, i32* %A, i32 %i + store i32 %0, i32* %arrayidx1, align 4 + + %arrayidx2 = getelementptr inbounds i32, i32* %A, i32 %i + %1 = load i32, i32* %arrayidx2, align 4 + %arrayidx3 = getelementptr inbounds i32, i32* %B, i32 %i + store i32 %1, i32* %arrayidx3, align 4 + %inci = add nsw i32 %i, 1 + %cmp = icmp slt i32 %inci, 100 + br i1 %cmp, label %for.outer, label %for.end + +for.end: + ret void +} +)"; + + LLVMContext Context; + std::unique_ptr M = makeLLVMModule(Context, ModuleStr); + + runTest(*M, "test1", [&](Function &F, DependenceInfo &DI, LoopInfo &LI, + ScalarEvolution &SE) { + Function::iterator FI = F.begin(); + // Skip the first basic block (entry), get to the outer loop header. + BasicBlock *Header = &*(++FI); + assert(Header->getName() == "for.outer"); + Loop *L = LI.getLoopFor(Header); + EXPECT_NE(L, nullptr); + + // Create the interference graph. + DataDependenceGraph DDG(*L, LI, DI); + auto *FIG = FissionInterferenceGraph::create(DDG, *L); + + // Ensure the graph contains a root node and 3 nodes. + EXPECT_TRUE(FIG->hasRootNode()); + EXPECT_EQ(FIG->size(), 3u); + + const FIGNode& RN = FIG->getRootNode(); + EXPECT_EQ(RN.getEdges().size(), 1ull); + + const FIGEdge *RE = RN.getEdges().front(); + EXPECT_EQ(RE->getKind(), FIGEdge::EdgeKind::Root); + + // Ensure the first node is connected to the second via memory edge. + const FIGNode &N1 = RE->getTargetNode(); + EXPECT_EQ(N1.getKind(), FIGNode::NodeKind::Default); + EXPECT_EQ(N1.getEdges().size(), 1ull); + + const FIGEdge *E1 = N1.getEdges().front(); + EXPECT_EQ(E1->getKind(), FIGEdge::EdgeKind::Memory); + + // Ensure the second node is connected to the third via memory def-use edge. + const FIGNode &N2 = E1->getTargetNode(); + EXPECT_EQ(N2.getKind(), FIGNode::NodeKind::Default); + EXPECT_EQ(N2.getEdges().size(), 1ull); + + const FIGEdge *E2 = N2.getEdges().front(); + EXPECT_EQ(E2->getKind(), FIGEdge::EdgeKind::DefUse); + + const FIGNode &N3 = E2->getTargetNode(); + EXPECT_EQ(N3.getKind(), FIGNode::NodeKind::Default); + EXPECT_TRUE(N3.getEdges().empty()); + + delete FIG; + }); +}