LLVM 19.0.0git
DependenceGraphBuilder.h
Go to the documentation of this file.
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"
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:
34
35private:
36 using NodeType = typename GraphType::NodeType;
37 using EdgeType = typename GraphType::EdgeType;
38
39public:
42
44 const BasicBlockListType &BBs)
45 : Graph(G), DI(D), BBList(BBs) {}
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() {
64 simplify();
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.
75
76 /// Create fine grained nodes. These are typically atomic nodes that
77 /// consist of a single instruction.
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.
87
88 /// Create a root node and add edges such that each node in the graph is
89 /// reachable from the root.
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.
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.
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.
172
173 /// Map Types to map instruction/nodes to an ordinal number.
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.
184
185 /// The list of basic blocks to consider when building the graph.
187
188 /// A mapping from instructions to the corresponding nodes in the graph.
190
191 /// A mapping from each instruction to an ordinal number. This map is used to
192 /// populate the \p NodeOrdinalMap.
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.
198};
199
200} // namespace llvm
201
202#endif // LLVM_ANALYSIS_DEPENDENCEGRAPHBUILDER_H
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file defines the DenseMap class.
Generic implementation of equivalence classes through the use Tarjan's efficient union-find algorithm...
#define I(x, y, z)
Definition: MD5.cpp:58
#define G(x, y, z)
Definition: MD5.cpp:56
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallVector class.
This abstract builder class defines a set of high-level steps for creating DDG-like graphs.
void createAndConnectRootNode()
Create a root node and add edges such that each node in the graph is reachable from the root.
void computeInstructionOrdinals()
Compute ordinal numbers for each instruction and store them in a map for future look up.
virtual const NodeListType & getNodesInPiBlock(const NodeType &N)=0
Given a pi-block node, return a vector of all the nodes contained within it.
virtual void destroyEdge(EdgeType &E)
Deallocate memory of edge E.
virtual EdgeType & createMemoryEdge(NodeType &Src, NodeType &Tgt)=0
Create a memory dependence edge going from Src to Tgt.
virtual bool shouldCreatePiBlocks() const
Return true if creation of pi-blocks are supported and desired, and false otherwise.
virtual bool shouldSimplify() const
Return true if graph simplification step is requested, and false otherwise.
void sortNodesTopologically()
Topologically sort the graph nodes.
virtual NodeType & createFineGrainedNode(Instruction &I)=0
Create an atomic node in the graph given a single instruction.
virtual EdgeType & createRootedEdge(NodeType &Src, NodeType &Tgt)=0
Create a rooted edge going from Src to Tgt .
void createFineGrainedNodes()
Create fine grained nodes.
virtual NodeType & createPiBlock(const NodeListType &L)=0
Create a pi-block node in the graph representing a group of nodes in an SCC of the graph.
virtual NodeType & createRootNode()=0
Create the root node of the graph.
InstToOrdinalMap InstOrdinalMap
A mapping from each instruction to an ordinal number.
AbstractDependenceGraphBuilder(GraphType &G, DependenceInfo &D, const BasicBlockListType &BBs)
virtual EdgeType & createDefUseEdge(NodeType &Src, NodeType &Tgt)=0
Create a def-use edge going from Src to Tgt.
virtual ~AbstractDependenceGraphBuilder()=default
void createMemoryDependencyEdges()
Analyze data dependencies that exist between memory loads or stores, in the graph nodes and create ed...
virtual void mergeNodes(NodeType &A, NodeType &B)=0
Append the content of node B into node A and remove B and the edge between A and B from the graph.
DependenceInfo & DI
Dependence information used to create memory dependence edges in the graph.
void simplify()
Go through all the nodes in the graph and collapse any two nodes 'a' and 'b' if all of the following ...
void populate()
The main entry to the graph construction algorithm.
const BasicBlockListType & BBList
The list of basic blocks to consider when building the graph.
InstToNodeMap IMap
A mapping from instructions to the corresponding nodes in the graph.
virtual void destroyNode(NodeType &N)
Deallocate memory of node N.
size_t getOrdinal(Instruction &I)
Given an instruction I return its associated ordinal number.
void createDefUseEdges()
Analyze the def-use chains and create edges from the nodes containing definitions to the nodes contai...
size_t getOrdinal(NodeType &N)
Given a node N return its associated ordinal number.
NodeToOrdinalMap NodeOrdinalMap
A mapping from nodes to an ordinal number.
GraphType & Graph
Reference to the graph that gets built by a concrete implementation of this builder.
virtual bool areNodesMergeable(const NodeType &A, const NodeType &B) const =0
Return true if it's safe to merge the two nodes.
void createPiBlocks()
Apply graph abstraction to groups of nodes that belong to a strongly connected component of the graph...
bool contains(const_arg_type_t< KeyT > Val) const
Return true if the specified key is in the map, false otherwise.
Definition: DenseMap.h:145
DependenceInfo - This class is the main dependence-analysis driver.
EquivalenceClasses - This represents a collection of equivalence classes and supports three efficient...
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
#define N