[LoopFission]: Loop Fission Interference Graph (FIG)

[etiotto]

Summary

SUMMARY
The Loop Fission Interference Graph (FIG) is generated with the nodes of the data dependence graph (DDG). Weights are generated for the edges of the interference graph reflecting the affinity between statements represented by the nodes joined by the edges. Nodes in the interference graph are given weights reflecting resource usage by the statements associated with the nodes. The interference graph is partitioned using a profitability test based on the weights of edges and nodes in the data dependence graph. Code (e.g. loops) is emitted based on the partitioned interference graph.

PATCH DESCRIPTION
In this first patch we introduce the basic components of the Loop Fission Interference Graph:

• the FIGNode (and derived class) representing nodes in the graph
• and the FIGEdge (and its derived classes) representing edges in the graph

The graph is constructed based on the DDG for a loop. Each interference graph node encapsulates one or more DDG nodes.
Edges connect the nodes in the interference and are used to enforce data dependencies.
A unit test is provided to test the graph structure and ensure nodes are connected properly.

FUTURE PATCHES
In future patches we plan to:

• add the ability to merge nodes in the interference graph
• summarize node connectivity informations and use the the information to prevent merging nodes that would create cycles in the graph

Merged nodes will represent the largest unit of code that can be distributed into a loop without violating data dependencies.

Afterward we will start to add to the graph the infrastructure needed to develop a cost model which will be used to determine which nodes should be merged to achieve data reuse.
Nodes found to exhibit data reuse will be connected by affinity edges with a weight that represent the desirability to merge them.
Nodes will also be given a set of Resources to represent the computational resource the code in the node consumes (e.g. code size, HW streams, etc...).

[Meinersbur]

[not a review] The established term in the code base for the transformation is (Loop-)Distribution. Could we use the same term here?

[etiotto]

I choose to name the pass Loop Fission to avoid confusion with the existing LoopDistribution pass (eventually Loop Fission should replace that pass). Also Loop Fission is the opposite of Loop Fusion :-) ?

[Meinersbur]

The FIG recreate a dependency graph from the DDG. I strongly suggest to traverse the nodes/edges from the DDG instead of iterating over all pairs of nodes and asking the DDG 'does this edge exist?' That's supposed to be done just once (by the DDG) and I hope it can be optimized later to reduce the burden of O(n^2). Maybe even derive from the DDG and only change the parts that are difference in the FIG.

Otherwise, I don't see that many differences between the DDG and FIG with a subset of dependencies (and later added affinity 'dependencies'). Why can other dependency (DDGEdge::Unknown) just be ignored?

llvm/include/llvm/Analysis/DDG.h

450–451

[style] LLVM does not use almost-always-auto

llvm/include/llvm/Transforms/Scalar/LoopFission/FIG.h

113

AFICS each FIG node is backed by exactly one DDGNode. Why is it a SmallPtrSet?

137

[typo] Intereference

222

[serious] With "update", I'd expect Weight = W (and maybe some updating logic, it would be setWeight otherwise). Suggestion: "addWeight".

408

[typo] grapth (copy-and-pasted from DDG.h)

451

[typo] grapth

llvm/lib/Transforms/Scalar/CMakeLists.txt

31

[serious] It is unusual to place component files into subdirectory and I don't see a reason to deviate from established practice. Maybe put it into the LLVMAnalysis like the DDG?

llvm/lib/Transforms/Scalar/LoopFission/FIG.cpp

22

In release mode, I get a warning warning: ‘VerboseDebug’ defined but not used.

106

[serious] This calls DependenceInfo::depends (a really expensive call) again on each edge after DDG already has done so. Maybe cache in the DDG?

108

[serious] I think being an input dependence does not, in principle, exclude also being another type of dependence (e.g. a dependence between function calls that read and write (conditionally) a location). Maybe isOrdered() is what you are looking for.

IIUC, DependenceInfo does not even report a dependence if it is input-only (and make me wonder why isInput even exists).

124

This is weird: ~FIGEdge is defined as abstract (=0), but there is an implementation here. Seems to work in that it makes the base class abstract, but still allows derived classed to call the dtor.

https://stackoverflow.com/questions/24316700/c-abstract-class-destructor#answer-24317666

139

[suggestion] Also assert that no Weight is set for the other types.

318

[style] constexpr?

Suggestion: haveMemoryDependence(N1, N2, DDG, /*SkipInputDependencies=*/true)

424–425

[serious] This is at least O(n^2)

This iterates over all pairs of nodes
  then over all outgoing edges of the src node
    to find a match in the underlying DDG
    and potentially calls `getDependencies` for each edge

For nodes with multiple outgoing edges (=d), this calls getDependencies O(d^2) times on the same edge for some information that the DDG already queried.

To summarize, this code does not scale.

531

[style] RN is unused; use isa<RootFIGNode>

[Meinersbur]

Do you plan to support lexical forward dependencies?

[fhahn]

I think it would be great if the patch that uses the infrastructure added here would also be available for review, to get a better idea how it is actually used. It also makes testing much easier.

I choose to name the pass Loop Fission to avoid confusion with the existing LoopDistribution pass (eventually Loop Fission should replace that pass). Also Loop Fission is the opposite of Loop Fusion :-) ?

I think adding this as separate pass with a slightly different name also causes a bunch of confusion and potentially split the development effort, in case people improve the existing LoopDistribute. Is there a reason for adding a completely new pass, rather than working on improving/replacing the existing LoopDistribute? I am a bit worried that in the end we end up with 2 passes that are not used/enabled. Would it not be possible/easier to add an option to use the FIG for partition in LoopDistribute and incrementally improve LoopDistribute?

[Meinersbur]

llvm/lib/Transforms/Scalar/LoopFission/FIG.cpp

108

Seems I was wrong here and DependenceInfo::depends does return input dependencies. The check is only !(Src->mayReadOrWriteMemory() && Dst->mayReadOrWriteMemory()), i.e. whether some memory is accesses at all, not what kind of access it is.

[bmahjour]

llvm/lib/Transforms/Scalar/LoopFission/FIG.cpp

106

The DDG would have to search through every pair of instructions in the loop. The set of instructions being iterated here is much more reduced than what the DDG goes through, because we only consider instructions that actually have a memory dependence between them (previously detected). On the other hand, depends is more expensive to compute when there is actual memory dependencies so the concern you raise is still valid.

When designing the DDG we opted for lazy evaluation of dependencies instead of caching the results due to memory consumption concerns. I think we should revisit these trade offs at some point. I'm just not sure this is the right time, given that the algorithms and the implementation is being changed, so any data we collect could go stale and become irrelevant very quickly.

[Meinersbur]

Question regarding input dependencies inherited from the DDG:

for (int i = 0; i < b; ++i) {
  B[i] = f(A[i-1] + A[i]);
  C[i] = g(A[i]);
}

IIUC, the DDG will contain the input dependencies B->C and C->B (loop-carried). Since this results in a cycle, those will be combined in a Pi-node. The FIG treats Pi-nodes atomically, hence will not be able to fission/distribute the loop. Is this correct? Having read-read dependencies in the DDG still feels strange to me.

llvm/lib/Transforms/Scalar/LoopFission/FIG.cpp

106

Did you consider adding a TODO in the source about low hanging fruits to improve performance?

[bmahjour]

In D73801#1894384, @Meinersbur wrote:

Question regarding input dependencies inherited from the DDG:

for (int i = 0; i < b; ++i) {
  B[i] = f(A[i-1] + A[i]);
  C[i] = g(A[i]);
}

IIUC, the DDG will contain the input dependencies B->C and C->B (loop-carried). Since this results in a cycle, those will be combined in a Pi-node. The FIG treats Pi-nodes atomically, hence will not be able to fission/distribute the loop. Is this correct? Having read-read dependencies in the DDG still feels strange to me.

The dependence graph builder only does edge reversal on ordered dependencies, and since input dependencies are not ordered the above example will not cause a cycle since all input dependence edges flow from the first statement to the second (there will be no back edge).
While I think input dependencies can cause cycles in theory, I don't think they'll be common in our LLVM implementation because the dependencies are modeled at a higher granularity than statement level. I tried to engineer an example that would introduce a cycle with input dependency being a critical edge, but I failed. If you have such an example it would be interesting to look at.
Input dependencies may be uninteresting to loop fission (at least for enforcing legality constraints) but would be useful in other cases such as modeling data reuse. In fact loop fission could also use those edges to establish weights on the affinity edges. For that reason I'd argue there is value in keeping them in the DDG, even if it means giving up on some rare opportunities.
Another possibility might be to have two flavors of the DDG; one that models the input dependencies and one that doesn't, assuming that a motivating case for loop fission can be found.

[bmahjour]

In D73801#1879917, @Meinersbur wrote:

Do you plan to support lexical forward dependencies?

Those should already be covered by the DDG.

[Meinersbur]

In D73801#1901817, @bmahjour wrote:

I tried to engineer an example that would introduce a cycle with input dependency being a critical edge, but I failed. If you have such an example it would be interesting to look at.

for (int i = ...) {
  p = A[i-1];
  x = load *p;    

  y = load *q;
  A[i] = y;
}

Lets assume AA knows that A and {q,p} do not alias (e.g. TBAA). It is legal to distribute to

for (int i = ...) {
  y = load *q;
  A[i] = y;
}
for (int i = ...) {
  p = A[i-1];
  x = load *p;    
}

There is a dependency chain y = load *q; ->A[i] = y; -> p = A[i-1]; -> x = load *p;. The input dependency x = load *p; -> y = load *q; closes the cycle. It should be even easier to do with instructions that read and write at the same time (e.g. call to memcpy), but DependencyInfo does not support them.

What's even weirder is that this depends on the instruction order on the IR. If we reorder x = load *p and y = load *q, and (IIUC) DDG only adds unordered (= input) dependencies in forward direction, we get the dependency y = load *q; -> x = load *p;, which is transitively redundant.

I strongly feel that input dependencies should not be part of the DDG.

llvm/include/llvm/Analysis/DDG.h

DependenceGraphInfo(const std::string &N, const DependenceInfo &DepInfo)
       : Name(N), DI(DepInfo), Root(nullptr) {}
   DependenceGraphInfo(DependenceGraphInfo &&G)
       : Name(std::move(G.Name)), DI(std::move(G.DI)), Root(G.Root) {}
   virtual ~DependenceGraphInfo() {}
 
   /// 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 "
                    "still be in progress\n");
     return *Root;
   }
 
 protected:
public:
   PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM,
                         LoopStandardAnalysisResults &AR, LPMUpdater &U);
 
 private:
   raw_ostream &OS;
 };
 
 //===--------------------------------------------------------------------===//
+// DependenceGraphInfo Implementation
+//===--------------------------------------------------------------------===//
+
+template <typename NodeType>
+bool DependenceGraphInfo<NodeType>::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<Instruction *, 8> 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<DependenceInfo *>(&DI)->depends(SrcI, DstI, true))
+        Deps.push_back(std::move(Dep));
+
+  return !Deps.empty();
+}
+
+//===--------------------------------------------------------------------===//
 // GraphTraits specializations for the DDG
 //===--------------------------------------------------------------------===//
 
 /// non-const versions of the grapth trait specializations for DDG
 template <> struct GraphTraits<DDGNode *> {
   using NodeRef = DDGNode *;
 
   static DDGNode *DDGGetTargetNode(DGEdge<DDGNode, DDGEdge> *P) {

llvm/include/llvm/Transforms/Scalar/LoopFission/FIG.h

+//===- 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<FIGNode, FIGEdge>;
+using FIGEdgeBase = DGEdge<FIGNode, FIGEdge>;
+using FIGBase = DirectedGraph<FIGNode, FIGEdge>;
+
+/// 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<DDGNode *, 4>;
+  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<bool(Instruction *)> 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<unsigned> 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 <FIGEdge::EdgeKind EK> 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<FIGEdge::EdgeKind::DefUse>;
+using MemoryFIGEdge = FIGEdgeOfKind<FIGEdge::EdgeKind::Memory>;
+using RootFIGEdge = FIGEdgeOfKind<FIGEdge::EdgeKind::Root>;
+
+/// 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<FIGNode *, unsigned>;
+  using IndexToNodeMapTy = DenseMap<unsigned, FIGNode *>;
+
+  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<RootFIGNode>(*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<bool(const FIGNode &, const FIGNode &)> 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<bool(const FIGNode &, const FIGNode &)> Selector,
+               function_ref<int(const FIGNode &, const FIGNode &)> 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<int(const FIGNode &N1, const FIGNode &N2)> 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<FIGNode *> {
+  using NodeRef = FIGNode *;
+
+  static NodeRef FIGGetTargetNode(DGEdge<FIGNode, FIGEdge> *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<FIGNode::iterator, decltype(&FIGGetTargetNode)>;
+  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<FissionInterferenceGraph *> : public GraphTraits<FIGNode *> {
+  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<const FIGNode *> {
+  using NodeRef = const FIGNode *;
+
+  static NodeRef FIGGetTargetNode(const DGEdge<FIGNode, FIGEdge> *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<FIGNode::const_iterator, decltype(&FIGGetTargetNode)>;
+  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<const FissionInterferenceGraph *>
+    : public GraphTraits<const FIGNode *> {
+  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

llvm/lib/Transforms/Scalar/CMakeLists.txt

add_llvm_component_library(LLVMScalarOpts
   InstSimplifyPass.cpp
   JumpThreading.cpp
   LICM.cpp
   LoopAccessAnalysisPrinter.cpp
   LoopSink.cpp
   LoopDeletion.cpp
   LoopDataPrefetch.cpp
   LoopDistribute.cpp
+  LoopFission/FIG.cpp
   LoopFuse.cpp
   LoopIdiomRecognize.cpp
   LoopInstSimplify.cpp
   LoopInterchange.cpp
   LoopLoadElimination.cpp
   LoopPassManager.cpp
   LoopPredication.cpp
   LoopRerollPass.cpp

llvm/lib/Transforms/Scalar/LoopFission/FIG.cpp

+//===- 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<FIGNode, FIGEdge>;
+template class llvm::DGNode<FIGNode, FIGEdge>;
+template class llvm::DirectedGraph<FIGNode, FIGEdge>;
+
+//===--------------------------------------------------------------------===//
+// 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<bool(Instruction *)> Pred) const {
+  assert(IList.empty() && "Expecting instruction list to be empty");
+  for (const DDGNode *N : DDGNodes) {
+    SmallVector<Instruction *, 4> 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<const DDGNode *, 8> 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<PiBlockDDGNode>(&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<Dependence> &D) {
+              return D->isInput();
+            }))
+          continue;
+      }
+
+      Targets.insert(&Dst);
+    }
+  }
+
+  return !Targets.empty();
+}
+
+//===--------------------------------------------------------------------===//
+// FIGEdge implementation
+//===--------------------------------------------------------------------===//
+
+FIGEdge::~FIGEdge() {}
+
+FIGEdge *FIGEdge::create(FIGNode &N, EdgeKind EK, Optional<unsigned> 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<PiBlockDDGNode>(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<Instruction *, 4> 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<RootDDGNode>(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<FIGEdge *, 10> 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<FIGEdge *, 10> 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<AffinityFIGEdge>(*IT);
+      AE->updateWeight(cast<AffinityFIGEdge>(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<const FIGNode *, 10> 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<FIGEdge *, 10> EL;
+        RootNode->findEdgesTo(*I, EL);
+        for (FIGEdge *E : EL) {
+          assert(isa<RootFIGEdge>(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<bool(const FIGNode &, const FIGNode &)> 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<bool(const FIGNode &, const FIGNode &)> Selector,
+    function_ref<int(const FIGNode &, const FIGNode &)> 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<int(const FIGNode &N1, const FIGNode &N2)> 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<AffinityFIGEdge>(E)
+             ? connectNodes(N1, N2, cast<AffinityFIGEdge>(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<RootFIGNode>(&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<Instruction *, 8> 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<AffinityFIGEdge>(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;
+}

llvm/unittests/Transforms/Scalar/CMakeLists.txt

add_llvm_unittest(ScalarTests
   )
 
 target_link_libraries(ScalarTests 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()
+
+add_subdirectory(LoopFission)

llvm/unittests/Transforms/Scalar/LoopFission/CMakeLists.txt

+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()

llvm/unittests/Transforms/Scalar/LoopFission/LoopFissionTest.cpp

+//===- 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<void(Function &F, DependenceInfo &DI,
+                                      LoopInfo &LI, ScalarEvolution &SE)>
+                        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<Module> 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<Module> 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;
+  });
+}