1 //===- llvm/Analysis/DependenceGraphBuilder.h -------------------*- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
9 // This file defines a builder interface that can be used to populate dependence
10 // graphs such as DDG and PDG.
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_ANALYSIS_DEPENDENCE_GRAPH_BUILDER_H
15 #define LLVM_ANALYSIS_DEPENDENCE_GRAPH_BUILDER_H
17 #include "llvm/ADT/EquivalenceClasses.h"
18 #include "llvm/Analysis/DependenceAnalysis.h"
19 #include "llvm/IR/BasicBlock.h"
20 #include "llvm/IR/Instructions.h"
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
{
30 using BasicBlockListType
= SmallVectorImpl
<BasicBlock
*>;
33 using NodeType
= typename
GraphType::NodeType
;
34 using EdgeType
= typename
GraphType::EdgeType
;
37 using ClassesType
= EquivalenceClasses
<BasicBlock
*>;
38 using NodeListType
= SmallVector
<NodeType
*, 4>;
40 AbstractDependenceGraphBuilder(GraphType
&G
, DependenceInfo
&D
,
41 const BasicBlockListType
&BBs
)
42 : Graph(G
), DI(D
), BBList(BBs
) {}
43 virtual ~AbstractDependenceGraphBuilder() {}
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.
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).
55 createFineGrainedNodes();
57 createMemoryDependencyEdges();
60 /// Create fine grained nodes. These are typically atomic nodes that
61 /// consist of a single instruction.
62 void createFineGrainedNodes();
64 /// Analyze the def-use chains and create edges from the nodes containing
65 /// definitions to the nodes containing the uses.
66 void createDefUseEdges();
68 /// Analyze data dependencies that exist between memory loads or stores,
69 /// in the graph nodes and create edges between them.
70 void createMemoryDependencyEdges();
73 /// Create an atomic node in the graph given a single instruction.
74 virtual NodeType
&createFineGrainedNode(Instruction
&I
) = 0;
76 /// Create a def-use edge going from \p Src to \p Tgt.
77 virtual EdgeType
&createDefUseEdge(NodeType
&Src
, NodeType
&Tgt
) = 0;
79 /// Create a memory dependence edge going from \p Src to \p Tgt.
80 virtual EdgeType
&createMemoryEdge(NodeType
&Src
, NodeType
&Tgt
) = 0;
82 /// Deallocate memory of edge \p E.
83 virtual void destroyEdge(EdgeType
&E
) { delete &E
; }
85 /// Deallocate memory of node \p N.
86 virtual void destroyNode(NodeType
&N
) { delete &N
; }
88 /// Map types to map instructions to nodes used when populating the graph.
89 using InstToNodeMap
= DenseMap
<Instruction
*, NodeType
*>;
91 /// Reference to the graph that gets built by a concrete implementation of
95 /// Dependence information used to create memory dependence edges in the
99 /// The list of basic blocks to consider when building the graph.
100 const BasicBlockListType
&BBList
;
102 /// A mapping from instructions to the corresponding nodes in the graph.
108 #endif // LLVM_ANALYSIS_DEPENDENCE_GRAPH_BUILDER_H