include/llvm/Analysis/DependenceGraphBuilder.h

   1 //===- llvm/Analysis/DependenceGraphBuilder.h -------------------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file defines a builder interface that can be used to populate dependence
  10 // graphs such as DDG and PDG.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_ANALYSIS_DEPENDENCE_GRAPH_BUILDER_H
  15 #define LLVM_ANALYSIS_DEPENDENCE_GRAPH_BUILDER_H
  16
  17 #include "llvm/ADT/EquivalenceClasses.h"
  18 #include "llvm/Analysis/DependenceAnalysis.h"
  19 #include "llvm/IR/BasicBlock.h"
  20 #include "llvm/IR/Instructions.h"
  21
  22 namespace llvm {
  23
  24 /// This abstract builder class defines a set of high-level steps for creating
  25 /// DDG-like graphs. The client code is expected to inherit from this class and
  26 /// define concrete implementation for each of the pure virtual functions used
  27 /// in the high-level algorithm.
  28 template <class GraphType> class AbstractDependenceGraphBuilder {
  29 protected:
  30   using BasicBlockListType = SmallVectorImpl<BasicBlock *>;
  31
  32 private:
  33   using NodeType = typename GraphType::NodeType;
  34   using EdgeType = typename GraphType::EdgeType;
  35
  36 public:
  37   using ClassesType = EquivalenceClasses<BasicBlock *>;
  38   using NodeListType = SmallVector<NodeType *, 4>;
  39
  40   AbstractDependenceGraphBuilder(GraphType &G, DependenceInfo &D,
  41                                  const BasicBlockListType &BBs)
  42       : Graph(G), DI(D), BBList(BBs) {}
  43   virtual ~AbstractDependenceGraphBuilder() {}
  44
  45   /// The main entry to the graph construction algorithm. It starts by
  46   /// creating nodes in increasing order of granularity and then
  47   /// adds def-use and memory edges.
  48   ///
  49   /// The algorithmic complexity of this implementation is O(V^2 * I^2), where V
  50   /// is the number of vertecies (nodes) and I is the number of instructions in
  51   /// each node. The total number of instructions, N, is equal to V * I,
  52   /// therefore the worst-case time complexity is O(N^2). The average time
  53   /// complexity is O((N^2)/2).
  54   void populate() {
  55     createFineGrainedNodes();
  56     createDefUseEdges();
  57     createMemoryDependencyEdges();
  58     createAndConnectRootNode();
  59   }
  60
  61   /// Create fine grained nodes. These are typically atomic nodes that
  62   /// consist of a single instruction.
  63   void createFineGrainedNodes();
  64
  65   /// Analyze the def-use chains and create edges from the nodes containing
  66   /// definitions to the nodes containing the uses.
  67   void createDefUseEdges();
  68
  69   /// Analyze data dependencies that exist between memory loads or stores,
  70   /// in the graph nodes and create edges between them.
  71   void createMemoryDependencyEdges();
  72
  73   /// Create a root node and add edges such that each node in the graph is
  74   /// reachable from the root.
  75   void createAndConnectRootNode();
  76
  77 protected:
  78   /// Create the root node of the graph.
  79   virtual NodeType &createRootNode() = 0;
  80
  81   /// Create an atomic node in the graph given a single instruction.
  82   virtual NodeType &createFineGrainedNode(Instruction &I) = 0;
  83
  84   /// Create a def-use edge going from \p Src to \p Tgt.
  85   virtual EdgeType &createDefUseEdge(NodeType &Src, NodeType &Tgt) = 0;
  86
  87   /// Create a memory dependence edge going from \p Src to \p Tgt.
  88   virtual EdgeType &createMemoryEdge(NodeType &Src, NodeType &Tgt) = 0;
  89
  90   /// Create a rooted edge going from \p Src to \p Tgt .
  91   virtual EdgeType &createRootedEdge(NodeType &Src, NodeType &Tgt) = 0;
  92
  93   /// Deallocate memory of edge \p E.
  94   virtual void destroyEdge(EdgeType &E) { delete &E; }
  95
  96   /// Deallocate memory of node \p N.
  97   virtual void destroyNode(NodeType &N) { delete &N; }
  98
  99   /// Map types to map instructions to nodes used when populating the graph.
 100   using InstToNodeMap = DenseMap<Instruction *, NodeType *>;
 101
 102   /// Reference to the graph that gets built by a concrete implementation of
 103   /// this builder.
 104   GraphType &Graph;
 105
 106   /// Dependence information used to create memory dependence edges in the
 107   /// graph.
 108   DependenceInfo &DI;
 109
 110   /// The list of basic blocks to consider when building the graph.
 111   const BasicBlockListType &BBList;
 112
 113   /// A mapping from instructions to the corresponding nodes in the graph.
 114   InstToNodeMap IMap;
 115 };
 116
 117 } // namespace llvm
 118
 119 #endif // LLVM_ANALYSIS_DEPENDENCE_GRAPH_BUILDER_H