[DDG] Data Dependence Graph - Root Node

[bmahjour]

Summary

This patch adds Root Node to the DDG. The purpose of the root node is to create a single entry node that allows graph walk iterators to iterate through all nodes of the graph, making sure that no node is left unvisited during a graph walk (eg. SCC or DFS). Once the DDG is fully constructed it will have exactly one root node. Every node in the graph is reachable from the root. The algorithm for connecting the root node is based on depth-first-search that keeps track of visited nodes to try to avoid creating unnecessary edges.

Previous related revisions:
https://reviews.llvm.org/D65350

[Meinersbur]

Do I understand it correctly, that this node is added to avoid having to deal with forests?

Introducing a createAndConnectRootNode step creates the problem that if a node is added afterwards, it will not be connected. Could you add an assertion that checks that no nodes are added once the root node is created?

[suggestion] We could create a root node at the graph's construction and connect it when nodes are created. Instead of redundantly storing a list in DirectedGraph, we could use that root node's connections to iterate over all nodes.

[suggestion] Another special node could point from ever node in the graph. I have used this to represent dependencies from code before the analyzed region respectively to code after the region. Could it be useful to create such a node es well? (I called them \top and \bottom).

llvm/lib/Analysis/DependenceGraphBuilder.cpp

60 ↗

(On Diff #221543)

The algorithm here seems to add redundant edges depending on the iteration order over the node list (for a graph "A -> B", an edge from the root node is added to both if B is visited before A).

Please add some comment lines about how this algorithm works. The way it is written is somewhat confusing. depth_first_ext will always visit N first if not yet in the visited list. This makes I = N is a test for whether N has been visited yet.

61 ↗

(On Diff #221543)

[serious] It's not a def-use chain based dependency.

[bmahjour]

Do I understand it correctly, that this node is added to avoid having to deal with forests?

Kind of. The graph prior to creation of pi-blocks is not a DAG and may have disjoint components. The root node is needed to turn it into a "rooted digraph" making it easier to compute all the strongly connected components. Prior to creating the root, the graph is similar to a forest, but technically speaking it's not a forest because the components may not be trees.

Introducing a createAndConnectRootNode step creates the problem that if a node is added afterwards, it will not be connected. Could you add an assertion that checks that no nodes are added once the root node is created?

In general it would be unsafe to add new nodes after the root is established, but there is an exception. In the next patch I'll be adding pi-blocks which are hierarchical nodes representing strongly-connected components of the graph. Since these components are already reachable by root they are safe to be added after the root is established. Note also that the root node needs to be established before pi-blocks can be identified. I'll add an assert for now and a todo to exclude pi-blocks later.

[suggestion] We could create a root node at the graph's construction and connect it when nodes are created. Instead of redundantly storing a list in DirectedGraph, we could use that root node's connections to iterate over all nodes.

If we connect the root node as we add nodes we have two choices: 1) blindly connect the root to every new node 2) compute reachability and avoid creating an edge when the root can already reach the new node. The first approach obviously creates too many edges, and the second approach is less efficient than the algorithm used here (because we keep track of and ignore visited nodes in this patch). Also the list of nodes will be needed for topological sort of the graph anyway, so it's desirable to keep it.

[suggestion] Another special node could point from ever node in the graph. I have used this to represent dependencies from code before the analyzed region respectively to code after the region. Could it be useful to create such a node es well? (I called them \top and \bottom).

I cannot think of a utility for the bottom node. Even the root node has limited uses as the DDG is mainly used to reason about properties of dependence within a given set of program elements and ignores dependencies outside of that range.

llvm/lib/Analysis/DependenceGraphBuilder.cpp

60 ↗

(On Diff #221543)

Yes it's possible to add redundant edges depending on the order. This algorithm does not result in minimal edges from the root node but it does try to reduce redundant edges to some extent. An algorithm that would result in truly minimal number of edges from the root would be more complicated requiring more cpu cycles. I used this algorithm because it seems to be a reasonable compromise between compute cost and number of edges created. Please let me know if you don't agree with this approach, otherwise I'll add a comment to clarify.

61 ↗

(On Diff #221543)

I will create a dedicated type of edge and add it to the builder interface.

[Meinersbur]

llvm/lib/Analysis/DependenceGraphBuilder.cpp

60 ↗

(On Diff #221543)

Thanks for adding some documentation.

llvm/trunk/include/llvm/Analysis/DDG.h

 using DDGBase = DirectedGraph<DDGNode, DDGEdge>;
 class LPMUpdater;
 
 /// Data Dependence Graph Node
 /// The graph can represent the following types of nodes:
 /// 1. Single instruction node containing just one instruction.
 /// 2. Multiple instruction node where two or more instructions from
 ///    the same basic block are merged into one node.
+/// 3. 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 DDGNode : public DDGNodeBase {
 public:
   using InstructionListType = SmallVectorImpl<Instruction *>;
 
   enum class NodeKind {
     Unknown,
     SingleInstruction,
     MultiInstruction,
+    Root,
   };
 
   DDGNode() = delete;
   DDGNode(const NodeKind K) : DDGNodeBase(), Kind(K) {}
   DDGNode(const DDGNode &N) : DDGNodeBase(N), Kind(N.Kind) {}
   DDGNode(DDGNode &&N) : DDGNodeBase(std::move(N)), Kind(N.Kind) {}
   virtual ~DDGNode() = 0;
 

 protected:
   /// Setter for the kind of this node.
   void setKind(NodeKind K) { Kind = K; }
 
 private:
   NodeKind Kind;
 };
 
+/// Subclass of DDGNode representing the root node of the graph.
+/// There should only be one such node in a given graph.
+class RootDDGNode : public DDGNode {
+public:
+  RootDDGNode() : DDGNode(NodeKind::Root) {}
+  RootDDGNode(const RootDDGNode &N) = delete;
+  RootDDGNode(RootDDGNode &&N) : DDGNode(std::move(N)) {}
+  ~RootDDGNode() {}
+
+  /// Define classof to be able to use isa<>, cast<>, dyn_cast<>, etc.
+  static bool classof(const DDGNode *N) {
+    return N->getKind() == NodeKind::Root;
+  }
+  static bool classof(const RootDDGNode *N) { return true; }
+};
+
 /// Subclass of DDGNode representing single or multi-instruction nodes.
 class SimpleDDGNode : public DDGNode {
 public:
   SimpleDDGNode() = delete;
   SimpleDDGNode(Instruction &I);
   SimpleDDGNode(const SimpleDDGNode &N);
   SimpleDDGNode(SimpleDDGNode &&N);
   ~SimpleDDGNode();
private:
 
   /// List of instructions associated with a single or multi-instruction node.
   SmallVector<Instruction *, 2> InstList;
 };
 
 /// Data Dependency Graph Edge.
 /// An edge in the DDG can represent a def-use relationship or
 /// a memory dependence based on the result of DependenceAnalysis.
+/// A rooted edge connects the root node to one of the components
+/// of the graph.
 class DDGEdge : public DDGEdgeBase {
 public:
   /// The kind of edge in the DDG
-  enum class EdgeKind { Unknown, RegisterDefUse, MemoryDependence };
+  enum class EdgeKind { Unknown, RegisterDefUse, MemoryDependence, Rooted };
 
   explicit DDGEdge(DDGNode &N) = delete;
   DDGEdge(DDGNode &N, EdgeKind K) : DDGEdgeBase(N), Kind(K) {}
   DDGEdge(const DDGEdge &E) : DDGEdgeBase(E), Kind(E.getKind()) {}
   DDGEdge(DDGEdge &&E) : DDGEdgeBase(std::move(E)), Kind(E.Kind) {}
   DDGEdge &operator=(const DDGEdge &E) {
     DDGEdgeBase::operator=(E);
     Kind = E.Kind;
public:
   EdgeKind getKind() const { return Kind; };
 
   /// Return true if this is a def-use edge, and false otherwise.
   bool isDefUse() const { return Kind == EdgeKind::RegisterDefUse; }
 
   /// Return true if this is a memory dependence edge, and false otherwise.
   bool isMemoryDependence() const { return Kind == EdgeKind::MemoryDependence; }
 
+  /// Return true if this is an edge stemming from the root node, and false
+  /// otherwise.
+  bool isRooted() const { return Kind == EdgeKind::Rooted; }
+
 private:
   EdgeKind Kind;
 };
 
 /// Encapsulate some common data and functionality needed for different
 /// variations of data dependence graphs.
 template <typename NodeType> class DependenceGraphInfo {
 public:
   using DependenceList = SmallVector<std::unique_ptr<Dependence>, 1>;
 
   DependenceGraphInfo() = delete;
   DependenceGraphInfo(const DependenceGraphInfo &G) = delete;
   DependenceGraphInfo(const std::string &N, const DependenceInfo &DepInfo)
-      : Name(N), DI(DepInfo) {}
+      : Name(N), DI(DepInfo), Root(nullptr) {}
   DependenceGraphInfo(DependenceGraphInfo &&G)
-      : Name(std::move(G.Name)), DI(std::move(G.DI)) {}
+      : 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; }
 
+  /// 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:
   // Name of the graph.
   std::string Name;
 
   // Store a copy of DependenceInfo in the graph, so that individual memory
   // dependencies don't need to be stored. Instead when the dependence is
   // queried it is recomputed using @DI.
   const DependenceInfo DI;
+
+  // A special node in the graph that has an edge to every connected component of
+  // the graph, to ensure all nodes are reachable in a graph walk.
+  NodeType *Root = nullptr;
 };
 
 using DDGInfo = DependenceGraphInfo<DDGNode>;
 
 /// Data Dependency Graph
 class DataDependenceGraph : public DDGBase, public DDGInfo {
   friend class DDGBuilder;
 
 public:
   using NodeType = DDGNode;
   using EdgeType = DDGEdge;
 
   DataDependenceGraph() = delete;
   DataDependenceGraph(const DataDependenceGraph &G) = delete;
   DataDependenceGraph(DataDependenceGraph &&G)
       : DDGBase(std::move(G)), DDGInfo(std::move(G)) {}
   DataDependenceGraph(Function &F, DependenceInfo &DI);
   DataDependenceGraph(const Loop &L, DependenceInfo &DI);
   ~DataDependenceGraph();
+
+protected:
+  /// Add node \p N to the graph, if it's not added yet, and keep track of
+  /// the root node. Return true if node is successfully added.
+  bool addNode(NodeType &N);
+
 };
 
 /// Concrete implementation of a pure data dependence graph builder. This class
 /// provides custom implementation for the pure-virtual functions used in the
 /// generic dependence graph build algorithm.
 ///
 /// For information about time complexity of the build algorithm see the
 /// comments near the declaration of AbstractDependenceGraphBuilder.
 class DDGBuilder : public AbstractDependenceGraphBuilder<DataDependenceGraph> {
 public:
   DDGBuilder(DataDependenceGraph &G, DependenceInfo &D,
              const BasicBlockListType &BBs)
       : AbstractDependenceGraphBuilder(G, D, BBs) {}
+  DDGNode &createRootNode() final override {
+    auto *RN = new RootDDGNode();
+    assert(RN && "Failed to allocate memory for DDG root node.");
+    Graph.addNode(*RN);
+    return *RN;
+  }
   DDGNode &createFineGrainedNode(Instruction &I) final override {
     auto *SN = new SimpleDDGNode(I);
     assert(SN && "Failed to allocate memory for simple DDG node.");
     Graph.addNode(*SN);
     return *SN;
   }
   DDGEdge &createDefUseEdge(DDGNode &Src, DDGNode &Tgt) final override {
     auto *E = new DDGEdge(Tgt, DDGEdge::EdgeKind::RegisterDefUse);
     assert(E && "Failed to allocate memory for edge");
     Graph.connect(Src, Tgt, *E);
     return *E;
   }
   DDGEdge &createMemoryEdge(DDGNode &Src, DDGNode &Tgt) final override {
     auto *E = new DDGEdge(Tgt, DDGEdge::EdgeKind::MemoryDependence);
     assert(E && "Failed to allocate memory for edge");
     Graph.connect(Src, Tgt, *E);
     return *E;
   }
+  DDGEdge &createRootedEdge(DDGNode &Src, DDGNode &Tgt) final override {
+    auto *E = new DDGEdge(Tgt, DDGEdge::EdgeKind::Rooted);
+    assert(E && "Failed to allocate memory for edge");
+    assert(isa<RootDDGNode>(Src) && "Expected root node");
+    Graph.connect(Src, Tgt, *E);
+    return *E;
+  }
+
 };
 
 raw_ostream &operator<<(raw_ostream &OS, const DDGNode &N);
 raw_ostream &operator<<(raw_ostream &OS, const DDGNode::NodeKind K);
 raw_ostream &operator<<(raw_ostream &OS, const DDGEdge &E);
 raw_ostream &operator<<(raw_ostream &OS, const DDGEdge::EdgeKind K);
 raw_ostream &operator<<(raw_ostream &OS, const DataDependenceGraph &G);
 
static ChildEdgeIteratorType child_edge_begin(NodeRef N) {
     return N->begin();
   }
   static ChildEdgeIteratorType child_edge_end(NodeRef N) { return N->end(); }
 };
 
 template <>
 struct GraphTraits<DataDependenceGraph *> : public GraphTraits<DDGNode *> {
   using nodes_iterator = DataDependenceGraph::iterator;
-  static NodeRef getEntryNode(DataDependenceGraph *DG) { return *DG->begin(); }
+  static NodeRef getEntryNode(DataDependenceGraph *DG) {
+    return &DG->getRoot();
+  }
   static nodes_iterator nodes_begin(DataDependenceGraph *DG) {
     return DG->begin();
   }
   static nodes_iterator nodes_end(DataDependenceGraph *DG) { return DG->end(); }
 };
 
 /// const versions of the grapth trait specializations for DDG
 template <> struct GraphTraits<const DDGNode *> {
template <> struct GraphTraits<const DDGNode *> {
   static ChildEdgeIteratorType child_edge_end(NodeRef N) { return N->end(); }
 };
 
 template <>
 struct GraphTraits<const DataDependenceGraph *>
     : public GraphTraits<const DDGNode *> {
   using nodes_iterator = DataDependenceGraph::const_iterator;
   static NodeRef getEntryNode(const DataDependenceGraph *DG) {
-    return *DG->begin();
+    return &DG->getRoot();
   }
   static nodes_iterator nodes_begin(const DataDependenceGraph *DG) {
     return DG->begin();
   }
   static nodes_iterator nodes_end(const DataDependenceGraph *DG) {
     return DG->end();
   }
 };
 
 } // namespace llvm
 
 #endif // LLVM_ANALYSIS_DDG_H

llvm/trunk/include/llvm/Analysis/DependenceGraphBuilder.h

public:
   /// is the number of vertecies (nodes) and I is the number of instructions in
   /// each node. The total number of instructions, N, is equal to V * I,
   /// therefore the worst-case time complexity is O(N^2). The average time
   /// complexity is O((N^2)/2).
   void populate() {
     createFineGrainedNodes();
     createDefUseEdges();
     createMemoryDependencyEdges();
+    createAndConnectRootNode();
   }
 
   /// Create fine grained nodes. These are typically atomic nodes that
   /// consist of a single instruction.
   void createFineGrainedNodes();
 
   /// Analyze the def-use chains and create edges from the nodes containing
   /// definitions to the nodes containing the uses.
   void createDefUseEdges();
 
   /// Analyze data dependencies that exist between memory loads or stores,
   /// in the graph nodes and create edges between them.
   void createMemoryDependencyEdges();
 
+  /// Create a root node and add edges such that each node in the graph is
+  /// reachable from the root.
+  void createAndConnectRootNode();
+
 protected:
+  /// Create the root node of the graph.
+  virtual NodeType &createRootNode() = 0;
+
   /// Create an atomic node in the graph given a single instruction.
   virtual NodeType &createFineGrainedNode(Instruction &I) = 0;
 
   /// Create a def-use edge going from \p Src to \p Tgt.
   virtual EdgeType &createDefUseEdge(NodeType &Src, NodeType &Tgt) = 0;
 
   /// Create a memory dependence edge going from \p Src to \p Tgt.
   virtual EdgeType &createMemoryEdge(NodeType &Src, NodeType &Tgt) = 0;
 
+  /// Create a rooted edge going from \p Src to \p Tgt .
+  virtual EdgeType &createRootedEdge(NodeType &Src, NodeType &Tgt) = 0;
+
   /// Deallocate memory of edge \p E.
   virtual void destroyEdge(EdgeType &E) { delete &E; }
 
   /// Deallocate memory of node \p N.
   virtual void destroyNode(NodeType &N) { delete &N; }
 
   /// Map types to map instructions to nodes used when populating the graph.
   using InstToNodeMap = DenseMap<Instruction *, NodeType *>;

llvm/trunk/lib/Analysis/DDG.cpp

raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGNode::NodeKind K) {
   const char *Out;
   switch (K) {
   case DDGNode::NodeKind::SingleInstruction:
     Out = "single-instruction";
     break;
   case DDGNode::NodeKind::MultiInstruction:
     Out = "multi-instruction";
     break;
+  case DDGNode::NodeKind::Root:
+    Out = "root";
+    break;
   case DDGNode::NodeKind::Unknown:
     Out = "??";
     break;
   }
   OS << Out;
   return OS;
 }
 
 raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGNode &N) {
   OS << "Node Address:" << &N << ":" << N.getKind() << "\n";
   if (isa<SimpleDDGNode>(N)) {
     OS << " Instructions:\n";
     for (auto *I : cast<const SimpleDDGNode>(N).getInstructions())
       OS.indent(2) << *I << "\n";
-  } else
+  } else if (!isa<RootDDGNode>(N))
     llvm_unreachable("unimplemented type of node");
 
   OS << (N.getEdges().empty() ? " Edges:none!\n" : " Edges:\n");
   for (auto &E : N.getEdges())
     OS.indent(2) << *E;
   return OS;
 }
 
raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGEdge::EdgeKind K) {
   const char *Out;
   switch (K) {
   case DDGEdge::EdgeKind::RegisterDefUse:
     Out = "def-use";
     break;
   case DDGEdge::EdgeKind::MemoryDependence:
     Out = "memory";
     break;
+  case DDGEdge::EdgeKind::Rooted:
+    Out = "rooted";
+    break;
   case DDGEdge::EdgeKind::Unknown:
     Out = "??";
     break;
   }
   OS << Out;
   return OS;
 }
 

 DataDependenceGraph::~DataDependenceGraph() {
   for (auto *N : Nodes) {
     for (auto *E : *N)
       delete E;
     delete N;
   }
 }
 
+bool DataDependenceGraph::addNode(DDGNode &N) {
+  if (!DDGBase::addNode(N))
+    return false;
+
+  // In general, if the root node is already created and linked, it is not safe
+  // to add new nodes since they may be unreachable by the root.
+  // TODO: Allow adding Pi-block nodes after root is created. Pi-blocks are an
+  // exception because they represent components that are already reachable by
+  // root.
+  assert(!Root && "Root node is already added. No more nodes can be added.");
+  if (isa<RootDDGNode>(N))
+    Root = &N;
+
+  return true;
+}
+
 raw_ostream &llvm::operator<<(raw_ostream &OS, const DataDependenceGraph &G) {
   for (auto *Node : G)
     OS << *Node << "\n";
   return OS;
 }
 
 //===--------------------------------------------------------------------===//
 // DDG Analysis Passes

llvm/trunk/lib/Analysis/DependenceGraphBuilder.cpp

void AbstractDependenceGraphBuilder<G>::createFineGrainedNodes() {
   for (BasicBlock *BB : BBList)
     for (Instruction &I : *BB) {
       auto &NewNode = createFineGrainedNode(I);
       IMap.insert(std::make_pair(&I, &NewNode));
       ++TotalFineGrainedNodes;
     }
 }
 
+template <class G>
+void AbstractDependenceGraphBuilder<G>::createAndConnectRootNode() {
+  // Create a root node that connects to every connected component of the graph.
+  // This is done to allow graph iterators to visit all the disjoint components
+  // of the graph, in a single walk.
+  //
+  // This algorithm works by going through each node of the graph and for each
+  // node N, do a DFS starting from N. A rooted edge is established between the
+  // root node and N (if N is not yet visited). All the nodes reachable from N
+  // are marked as visited and are skipped in the DFS of subsequent nodes.
+  //
+  // Note: This algorithm tries to limit the number of edges out of the root
+  // node to some extent, but there may be redundant edges created depending on
+  // the iteration order. For example for a graph {A -> B}, an edge from the
+  // root node is added to both nodes if B is visited before A. While it does
+  // not result in minimal number of edges, this approach saves compile-time
+  // while keeping the number of edges in check.
+  auto &RootNode = createRootNode();
+  df_iterator_default_set<const NodeType *, 4> Visited;
+  for (auto *N : Graph) {
+    if (*N == RootNode)
+      continue;
+    for (auto I : depth_first_ext(N, Visited))
+      if (I == N)
+        createRootedEdge(RootNode, *N);
+  }
+}
+
 template <class G> void AbstractDependenceGraphBuilder<G>::createDefUseEdges() {
   for (NodeType *N : Graph) {
     InstructionListType SrcIList;
     N->collectInstructions([](const Instruction *I) { return true; }, SrcIList);
 
     // Use a set to mark the targets that we link to N, so we don't add
     // duplicate def-use edges when more than one instruction in a target node
     // use results of instructions that are contained in N.

llvm/trunk/test/Analysis/DDG/root-node.ll

+; RUN: opt < %s -disable-output "-passes=print<ddg>" 2>&1 | FileCheck %s
+
+; CHECK-LABEL: 'DDG' for loop 'test1.for.body':
+
+; CHECK: Node Address:[[N1:0x[0-9a-f]*]]:single-instruction
+; CHECK-NEXT: Instructions:
+; CHECK-NEXT:   %i2.03 = phi i64 [ 0, %for.body.lr.ph ], [ %inc2, %test1.for.body ]
+
+; CHECK: Node Address:[[N2:0x[0-9a-f]*]]:single-instruction
+; CHECK-NEXT: Instructions:
+; CHECK-NEXT:   %i1.02 = phi i64 [ 0, %for.body.lr.ph ], [ %inc, %test1.for.body ]
+
+; CHECK: Node Address:[[ROOT:0x[0-9a-f]*]]:root
+; CHECK-NEXT: Edges:
+; CHECK-NEXT:  [rooted] to [[N1]]
+; CHECK-NEXT:  [rooted] to [[N2]]
+
+
+;; // Two separate components in the graph. Root node must link to both.
+;; void test1(unsigned long n, float * restrict a, float * restrict b) {
+;;   for (unsigned long i1 = 0, i2 = 0; i1 < n; i1++, i2++) {
+;;     a[i1] = 1;
+;;     b[i2] = -1;
+;;   }
+;; }
+
+define void @test1(i64 %n, float* noalias %a, float* noalias %b) {
+entry:
+  %cmp1 = icmp ult i64 0, %n
+  br i1 %cmp1, label %for.body.lr.ph, label %for.end
+
+for.body.lr.ph:                                   ; preds = %entry
+  br label %test1.for.body
+
+test1.for.body:                                         ; preds = %for.body.lr.ph, %test1.for.body
+  %i2.03 = phi i64 [ 0, %for.body.lr.ph ], [ %inc2, %test1.for.body ]
+  %i1.02 = phi i64 [ 0, %for.body.lr.ph ], [ %inc, %test1.for.body ]
+  %arrayidx = getelementptr inbounds float, float* %a, i64 %i1.02
+  store float 1.000000e+00, float* %arrayidx, align 4
+  %arrayidx1 = getelementptr inbounds float, float* %b, i64 %i2.03
+  store float -1.000000e+00, float* %arrayidx1, align 4
+  %inc = add i64 %i1.02, 1
+  %inc2 = add i64 %i2.03, 1
+  %cmp = icmp ult i64 %inc, %n
+  br i1 %cmp, label %test1.for.body, label %for.cond.for.end_crit_edge
+
+for.cond.for.end_crit_edge:                       ; preds = %test1.for.body
+  br label %for.end
+
+for.end:                                          ; preds = %for.cond.for.end_crit_edge, %entry
+  ret void
+}