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_DEPENDENCEGRAPHBUILDER_H
15#define LLVM_ANALYSIS_DEPENDENCEGRAPHBUILDER_H
16
17#include "llvm/ADT/DenseMap.h"
18#include "llvm/ADT/EquivalenceClasses.h"
19#include "llvm/ADT/SmallVector.h"
20
21namespace llvm {
22
23class BasicBlock;
24class DependenceInfo;
25class Instruction;
26
27/// This abstract builder class defines a set of high-level steps for creating
28/// DDG-like graphs. The client code is expected to inherit from this class and
29/// define concrete implementation for each of the pure virtual functions used
30/// in the high-level algorithm.
31template <class GraphType> class AbstractDependenceGraphBuilder {
32protected:
33 using BasicBlockListType = SmallVectorImpl<BasicBlock *>;
34
35private:
36 using NodeType = typename GraphType::NodeType;
37 using EdgeType = typename GraphType::EdgeType;
38
39public:
40 using ClassesType = EquivalenceClasses<BasicBlock *>;
41 using NodeListType = SmallVector<NodeType *, 4>;
42
43 AbstractDependenceGraphBuilder(GraphType &G, DependenceInfo &D,
44 const BasicBlockListType &BBs)
45 : Graph(G), DI(D), BBList(BBs) {}
46 virtual ~AbstractDependenceGraphBuilder() = default;
47
48 /// The main entry to the graph construction algorithm. It starts by
49 /// creating nodes in increasing order of granularity and then
50 /// adds def-use and memory edges. As one of the final stages, it
51 /// also creates pi-block nodes to facilitate codegen in transformations
52 /// that use dependence graphs.
53 ///
54 /// The algorithmic complexity of this implementation is O(V^2 * I^2), where V
55 /// is the number of vertecies (nodes) and I is the number of instructions in
56 /// each node. The total number of instructions, N, is equal to V * I,
57 /// therefore the worst-case time complexity is O(N^2). The average time
58 /// complexity is O((N^2)/2).
59 void populate() {
60 computeInstructionOrdinals();
61 createFineGrainedNodes();
62 createDefUseEdges();
63 createMemoryDependencyEdges();
64 simplify();
65 createAndConnectRootNode();
66 createPiBlocks();
67 sortNodesTopologically();
68 }
69
70 /// Compute ordinal numbers for each instruction and store them in a map for
71 /// future look up. These ordinals are used to compute node ordinals which are
72 /// in turn used to order nodes that are part of a cycle.
73 /// Instruction ordinals are assigned based on lexical program order.
74 void computeInstructionOrdinals();
75
76 /// Create fine grained nodes. These are typically atomic nodes that
77 /// consist of a single instruction.
78 void createFineGrainedNodes();
79
80 /// Analyze the def-use chains and create edges from the nodes containing
81 /// definitions to the nodes containing the uses.
82 void createDefUseEdges();
83
84 /// Analyze data dependencies that exist between memory loads or stores,
85 /// in the graph nodes and create edges between them.
86 void createMemoryDependencyEdges();
87
88 /// Create a root node and add edges such that each node in the graph is
89 /// reachable from the root.
90 void createAndConnectRootNode();
91
92 /// Apply graph abstraction to groups of nodes that belong to a strongly
93 /// connected component of the graph to create larger compound nodes
94 /// called pi-blocks. The purpose of this abstraction is to isolate sets of
95 /// program elements that need to stay together during codegen and turn
96 /// the dependence graph into an acyclic graph.
97 void createPiBlocks();
98
99 /// Go through all the nodes in the graph and collapse any two nodes
100 /// 'a' and 'b' if all of the following are true:
101 /// - the only edge from 'a' is a def-use edge to 'b' and
102 /// - the only edge to 'b' is a def-use edge from 'a' and
103 /// - there is no cyclic edge from 'b' to 'a' and
104 /// - all instructions in 'a' and 'b' belong to the same basic block and
105 /// - both 'a' and 'b' are simple (single or multi instruction) nodes.
106 void simplify();
107
108 /// Topologically sort the graph nodes.
109 void sortNodesTopologically();
110
111protected:
112 /// Create the root node of the graph.
113 virtual NodeType &createRootNode() = 0;
114
115 /// Create an atomic node in the graph given a single instruction.
116 virtual NodeType &createFineGrainedNode(Instruction &I) = 0;
117
118 /// Create a pi-block node in the graph representing a group of nodes in an
119 /// SCC of the graph.
120 virtual NodeType &createPiBlock(const NodeListType &L) = 0;
121
122 /// Create a def-use edge going from \p Src to \p Tgt.
123 virtual EdgeType &createDefUseEdge(NodeType &Src, NodeType &Tgt) = 0;
124
125 /// Create a memory dependence edge going from \p Src to \p Tgt.
126 virtual EdgeType &createMemoryEdge(NodeType &Src, NodeType &Tgt) = 0;
127
128 /// Create a rooted edge going from \p Src to \p Tgt .
129 virtual EdgeType &createRootedEdge(NodeType &Src, NodeType &Tgt) = 0;
130
131 /// Given a pi-block node, return a vector of all the nodes contained within
132 /// it.
133 virtual const NodeListType &getNodesInPiBlock(const NodeType &N) = 0;
134
135 /// Deallocate memory of edge \p E.
136 virtual void destroyEdge(EdgeType &E) { delete &E; }
137
138 /// Deallocate memory of node \p N.
139 virtual void destroyNode(NodeType &N) { delete &N; }
140
141 /// Return true if creation of pi-blocks are supported and desired,
142 /// and false otherwise.
143 virtual bool shouldCreatePiBlocks() const { return true; }
144
145 /// Return true if graph simplification step is requested, and false
146 /// otherwise.
147 virtual bool shouldSimplify() const { return true; }
148
149 /// Return true if it's safe to merge the two nodes.
150 virtual bool areNodesMergeable(const NodeType &A,
151 const NodeType &B) const = 0;
152
153 /// Append the content of node \p B into node \p A and remove \p B and
154 /// the edge between \p A and \p B from the graph.
155 virtual void mergeNodes(NodeType &A, NodeType &B) = 0;
156
157 /// Given an instruction \p I return its associated ordinal number.
158 size_t getOrdinal(Instruction &I) {
159 assert(InstOrdinalMap.contains(&I) &&
160 "No ordinal computed for this instruction.");
161 return InstOrdinalMap[&I];
162 }
163
164 /// Given a node \p N return its associated ordinal number.
165 size_t getOrdinal(NodeType &N) {
166 assert(NodeOrdinalMap.contains(&N) && "No ordinal computed for this node.");
167 return NodeOrdinalMap[&N];
168 }
169
170 /// Map types to map instructions to nodes used when populating the graph.
171 using InstToNodeMap = DenseMap<Instruction *, NodeType *>;
172
173 /// Map Types to map instruction/nodes to an ordinal number.
174 using InstToOrdinalMap = DenseMap<Instruction *, size_t>;
175 using NodeToOrdinalMap = DenseMap<NodeType *, size_t>;
176
177 /// Reference to the graph that gets built by a concrete implementation of
178 /// this builder.
179 GraphType &Graph;
180
181 /// Dependence information used to create memory dependence edges in the
182 /// graph.
183 DependenceInfo &DI;
184
185 /// The list of basic blocks to consider when building the graph.
186 const BasicBlockListType &BBList;
187
188 /// A mapping from instructions to the corresponding nodes in the graph.
189 InstToNodeMap IMap;
190
191 /// A mapping from each instruction to an ordinal number. This map is used to
192 /// populate the \p NodeOrdinalMap.
193 InstToOrdinalMap InstOrdinalMap;
194
195 /// A mapping from nodes to an ordinal number. This map is used to sort nodes
196 /// in a pi-block based on program order.
197 NodeToOrdinalMap NodeOrdinalMap;
198};
199
200} // namespace llvm
201
202#endif // LLVM_ANALYSIS_DEPENDENCEGRAPHBUILDER_H
203

source code of llvm/include/llvm/Analysis/DependenceGraphBuilder.h