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. As one of the final stages, it
48   /// also creates pi-block nodes to facilitate codegen in transformations
49   /// that use dependence graphs.
50   ///
51   /// The algorithmic complexity of this implementation is O(V^2 * I^2), where V
52   /// is the number of vertecies (nodes) and I is the number of instructions in
53   /// each node. The total number of instructions, N, is equal to V * I,
54   /// therefore the worst-case time complexity is O(N^2). The average time
55   /// complexity is O((N^2)/2).
56   void populate() {
57     computeInstructionOrdinals();
58     createFineGrainedNodes();
59     createDefUseEdges();
60     createMemoryDependencyEdges();
61     createAndConnectRootNode();
62     createPiBlocks();
63     sortNodesTopologically();
64   }
65 
66   /// Compute ordinal numbers for each instruction and store them in a map for
67   /// future look up. These ordinals are used to compute node ordinals which are
68   /// in turn used to order nodes that are part of a cycle.
69   /// Instruction ordinals are assigned based on lexical program order.
70   void computeInstructionOrdinals();
71 
72   /// Create fine grained nodes. These are typically atomic nodes that
73   /// consist of a single instruction.
74   void createFineGrainedNodes();
75 
76   /// Analyze the def-use chains and create edges from the nodes containing
77   /// definitions to the nodes containing the uses.
78   void createDefUseEdges();
79 
80   /// Analyze data dependencies that exist between memory loads or stores,
81   /// in the graph nodes and create edges between them.
82   void createMemoryDependencyEdges();
83 
84   /// Create a root node and add edges such that each node in the graph is
85   /// reachable from the root.
86   void createAndConnectRootNode();
87 
88   /// Apply graph abstraction to groups of nodes that belong to a strongly
89   /// connected component of the graph to create larger compound nodes
90   /// called pi-blocks. The purpose of this abstraction is to isolate sets of
91   /// program elements that need to stay together during codegen and turn
92   /// the dependence graph into an acyclic graph.
93   void createPiBlocks();
94 
95   /// Topologically sort the graph nodes.
96   void sortNodesTopologically();
97 
98 protected:
99   /// Create the root node of the graph.
100   virtual NodeType &createRootNode() = 0;
101 
102   /// Create an atomic node in the graph given a single instruction.
103   virtual NodeType &createFineGrainedNode(Instruction &I) = 0;
104 
105   /// Create a pi-block node in the graph representing a group of nodes in an
106   /// SCC of the graph.
107   virtual NodeType &createPiBlock(const NodeListType &L) = 0;
108 
109   /// Create a def-use edge going from \p Src to \p Tgt.
110   virtual EdgeType &createDefUseEdge(NodeType &Src, NodeType &Tgt) = 0;
111 
112   /// Create a memory dependence edge going from \p Src to \p Tgt.
113   virtual EdgeType &createMemoryEdge(NodeType &Src, NodeType &Tgt) = 0;
114 
115   /// Create a rooted edge going from \p Src to \p Tgt .
116   virtual EdgeType &createRootedEdge(NodeType &Src, NodeType &Tgt) = 0;
117 
118   /// Given a pi-block node, return a vector of all the nodes contained within
119   /// it.
120   virtual const NodeListType &getNodesInPiBlock(const NodeType &N) = 0;
121 
122   /// Deallocate memory of edge \p E.
123   virtual void destroyEdge(EdgeType &E) { delete &E; }
124 
125   /// Deallocate memory of node \p N.
126   virtual void destroyNode(NodeType &N) { delete &N; }
127 
128   /// Return true if creation of pi-blocks are supported and desired,
129   /// and false otherwise.
130   virtual bool shouldCreatePiBlocks() const { return true; }
131 
132   /// Given an instruction \p I return its associated ordinal number.
133   size_t getOrdinal(Instruction &I) {
134     assert(InstOrdinalMap.find(&I) != InstOrdinalMap.end() &&
135            "No ordinal computed for this instruction.");
136     return InstOrdinalMap[&I];
137   }
138 
139   /// Given a node \p N return its associated ordinal number.
140   size_t getOrdinal(NodeType &N) {
141     assert(NodeOrdinalMap.find(&N) != NodeOrdinalMap.end() &&
142            "No ordinal computed for this node.");
143     return NodeOrdinalMap[&N];
144   }
145 
146   /// Map types to map instructions to nodes used when populating the graph.
147   using InstToNodeMap = DenseMap<Instruction *, NodeType *>;
148 
149   /// Map Types to map instruction/nodes to an ordinal number.
150   using InstToOrdinalMap = DenseMap<Instruction *, size_t>;
151   using NodeToOrdinalMap = DenseMap<NodeType *, size_t>;
152 
153   /// Reference to the graph that gets built by a concrete implementation of
154   /// this builder.
155   GraphType &Graph;
156 
157   /// Dependence information used to create memory dependence edges in the
158   /// graph.
159   DependenceInfo &DI;
160 
161   /// The list of basic blocks to consider when building the graph.
162   const BasicBlockListType &BBList;
163 
164   /// A mapping from instructions to the corresponding nodes in the graph.
165   InstToNodeMap IMap;
166 
167   /// A mapping from each instruction to an ordinal number. This map is used to
168   /// populate the \p NodeOrdinalMap.
169   InstToOrdinalMap InstOrdinalMap;
170 
171   /// A mapping from nodes to an ordinal number. This map is used to sort nodes
172   /// in a pi-block based on program order.
173   NodeToOrdinalMap NodeOrdinalMap;
174 };
175 
176 } // namespace llvm
177 
178 #endif // LLVM_ANALYSIS_DEPENDENCE_GRAPH_BUILDER_H
179