DependenceGraphBuilder.h revision 360784 
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
22namespace 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.
28template <class GraphType> class AbstractDependenceGraphBuilder {
29protected:
30  using BasicBlockListType = SmallVectorImpl<BasicBlock *>;
31
32private:
33  using NodeType = typename GraphType::NodeType;
34  using EdgeType = typename GraphType::EdgeType;
35
36public:
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
98protected:
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