LLVM  14.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"
19 #include "llvm/ADT/SmallVector.h"
20 
21 namespace llvm {
22 
23 class BasicBlock;
24 class DependenceInfo;
25 class 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.
31 template <class GraphType> class AbstractDependenceGraphBuilder {
32 protected:
34 
35 private:
36  using NodeType = typename GraphType::NodeType;
37  using EdgeType = typename GraphType::EdgeType;
38 
39 public:
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.
109  void sortNodesTopologically();
110 
111 protected:
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) {
167  "No ordinal computed for this node.");
168  return NodeOrdinalMap[&N];
169  }
170 
171  /// Map types to map instructions to nodes used when populating the graph.
173 
174  /// Map Types to map instruction/nodes to an ordinal number.
177 
178  /// Reference to the graph that gets built by a concrete implementation of
179  /// this builder.
180  GraphType &Graph;
181 
182  /// Dependence information used to create memory dependence edges in the
183  /// graph.
185 
186  /// The list of basic blocks to consider when building the graph.
188 
189  /// A mapping from instructions to the corresponding nodes in the graph.
191 
192  /// A mapping from each instruction to an ordinal number. This map is used to
193  /// populate the \p NodeOrdinalMap.
195 
196  /// A mapping from nodes to an ordinal number. This map is used to sort nodes
197  /// in a pi-block based on program order.
199 };
200 
201 } // namespace llvm
202 
203 #endif // LLVM_ANALYSIS_DEPENDENCEGRAPHBUILDER_H
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::AbstractDependenceGraphBuilder::createDefUseEdges
void createDefUseEdges()
Analyze the def-use chains and create edges from the nodes containing definitions to the nodes contai...
Definition: DependenceGraphBuilder.cpp:227
llvm::AbstractDependenceGraphBuilder::populate
void populate()
The main entry to the graph construction algorithm.
Definition: DependenceGraphBuilder.h:59
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
llvm::EquivalenceClasses
EquivalenceClasses - This represents a collection of equivalence classes and supports three efficient...
Definition: EquivalenceClasses.h:58
DenseMap.h
llvm::AbstractDependenceGraphBuilder::getOrdinal
size_t getOrdinal(Instruction &I)
Given an instruction I return its associated ordinal number.
Definition: DependenceGraphBuilder.h:158
llvm::AbstractDependenceGraphBuilder::createPiBlocks
void createPiBlocks()
Apply graph abstraction to groups of nodes that belong to a strongly connected component of the graph...
Definition: DependenceGraphBuilder.cpp:90
llvm::AbstractDependenceGraphBuilder::destroyNode
virtual void destroyNode(NodeType &N)
Deallocate memory of node N.
Definition: DependenceGraphBuilder.h:139
llvm::AbstractDependenceGraphBuilder::AbstractDependenceGraphBuilder
AbstractDependenceGraphBuilder(GraphType &G, DependenceInfo &D, const BasicBlockListType &BBs)
Definition: DependenceGraphBuilder.h:43
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::AbstractDependenceGraphBuilder::NodeOrdinalMap
NodeToOrdinalMap NodeOrdinalMap
A mapping from nodes to an ordinal number.
Definition: DependenceGraphBuilder.h:198
llvm::AbstractDependenceGraphBuilder::BBList
const BasicBlockListType & BBList
The list of basic blocks to consider when building the graph.
Definition: DependenceGraphBuilder.h:187
llvm::AbstractDependenceGraphBuilder::getNodesInPiBlock
virtual const NodeListType & getNodesInPiBlock(const NodeType &N)=0
Given a pi-block node, return a vector of all the nodes contained within it.
llvm::AbstractDependenceGraphBuilder::DI
DependenceInfo & DI
Dependence information used to create memory dependence edges in the graph.
Definition: DependenceGraphBuilder.h:184
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::ISD::NodeType
NodeType
ISD::NodeType enum - This enum defines the target-independent operators for a SelectionDAG.
Definition: ISDOpcodes.h:40
llvm::Instruction
Definition: Instruction.h:45
llvm::AbstractDependenceGraphBuilder::createAndConnectRootNode
void createAndConnectRootNode()
Create a root node and add edges such that each node in the graph is reachable from the root.
Definition: DependenceGraphBuilder.cpp:63
llvm::AbstractDependenceGraphBuilder
This abstract builder class defines a set of high-level steps for creating DDG-like graphs.
Definition: DependenceGraphBuilder.h:31
llvm::AbstractDependenceGraphBuilder::createRootedEdge
virtual EdgeType & createRootedEdge(NodeType &Src, NodeType &Tgt)=0
Create a rooted edge going from Src to Tgt .
llvm::AbstractDependenceGraphBuilder::getOrdinal
size_t getOrdinal(NodeType &N)
Given a node N return its associated ordinal number.
Definition: DependenceGraphBuilder.h:165
llvm::AbstractDependenceGraphBuilder::createMemoryDependencyEdges
void createMemoryDependencyEdges()
Analyze data dependencies that exist between memory loads or stores, in the graph nodes and create ed...
Definition: DependenceGraphBuilder.cpp:277
G
const DataFlowGraph & G
Definition: RDFGraph.cpp:202
llvm::AbstractDependenceGraphBuilder::createFineGrainedNode
virtual NodeType & createFineGrainedNode(Instruction &I)=0
Create an atomic node in the graph given a single instruction.
llvm::DependenceInfo
DependenceInfo - This class is the main dependence-analysis driver.
Definition: DependenceAnalysis.h:272
llvm::AbstractDependenceGraphBuilder::createPiBlock
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.
llvm::AbstractDependenceGraphBuilder::computeInstructionOrdinals
void computeInstructionOrdinals()
Compute ordinal numbers for each instruction and store them in a map for future look up.
Definition: DependenceGraphBuilder.cpp:41
D
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
llvm::AbstractDependenceGraphBuilder::shouldCreatePiBlocks
virtual bool shouldCreatePiBlocks() const
Return true if creation of pi-blocks are supported and desired, and false otherwise.
Definition: DependenceGraphBuilder.h:143
llvm::DenseMap< Instruction *, NodeType * >
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::DenseMapBase::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
llvm::AbstractDependenceGraphBuilder::~AbstractDependenceGraphBuilder
virtual ~AbstractDependenceGraphBuilder()
Definition: DependenceGraphBuilder.h:46
llvm::AbstractDependenceGraphBuilder::NodeListType
SmallVector< NodeType *, 4 > NodeListType
Definition: DependenceGraphBuilder.h:41
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::AbstractDependenceGraphBuilder::createMemoryEdge
virtual EdgeType & createMemoryEdge(NodeType &Src, NodeType &Tgt)=0
Create a memory dependence edge going from Src to Tgt.
llvm::ISD::BasicBlock
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
llvm::AbstractDependenceGraphBuilder::createDefUseEdge
virtual EdgeType & createDefUseEdge(NodeType &Src, NodeType &Tgt)=0
Create a def-use edge going from Src to Tgt.
llvm::AbstractDependenceGraphBuilder::areNodesMergeable
virtual bool areNodesMergeable(const NodeType &A, const NodeType &B) const =0
Return true if it's safe to merge the two nodes.
llvm::AbstractDependenceGraphBuilder::simplify
void simplify()
Go through all the nodes in the graph and collapse any two nodes 'a' and 'b' if all of the following ...
Definition: DependenceGraphBuilder.cpp:377
llvm::AbstractDependenceGraphBuilder::InstOrdinalMap
InstToOrdinalMap InstOrdinalMap
A mapping from each instruction to an ordinal number.
Definition: DependenceGraphBuilder.h:194
llvm::AbstractDependenceGraphBuilder::createRootNode
virtual NodeType & createRootNode()=0
Create the root node of the graph.
llvm::DenseMapBase::end
iterator end()
Definition: DenseMap.h:83
llvm::AbstractDependenceGraphBuilder::destroyEdge
virtual void destroyEdge(EdgeType &E)
Deallocate memory of edge E.
Definition: DependenceGraphBuilder.h:136
EquivalenceClasses.h
llvm::AbstractDependenceGraphBuilder::sortNodesTopologically
void sortNodesTopologically()
Topologically sort the graph nodes.
Definition: DependenceGraphBuilder.cpp:481
SmallVector.h
llvm::AbstractDependenceGraphBuilder::createFineGrainedNodes
void createFineGrainedNodes()
Create fine grained nodes.
Definition: DependenceGraphBuilder.cpp:50
N
#define N
llvm::SmallVectorImpl< BasicBlock * >
llvm::AbstractDependenceGraphBuilder::IMap
InstToNodeMap IMap
A mapping from instructions to the corresponding nodes in the graph.
Definition: DependenceGraphBuilder.h:190
llvm::AbstractDependenceGraphBuilder::shouldSimplify
virtual bool shouldSimplify() const
Return true if graph simplification step is requested, and false otherwise.
Definition: DependenceGraphBuilder.h:147
llvm::AbstractDependenceGraphBuilder::mergeNodes
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.
llvm::AbstractDependenceGraphBuilder::Graph
GraphType & Graph
Reference to the graph that gets built by a concrete implementation of this builder.
Definition: DependenceGraphBuilder.h:180