aboutsummaryrefslogtreecommitdiffstats
path: root/contrib/libs/llvm14/include/llvm/Analysis/DependenceGraphBuilder.h
blob: 5024c704b2c19253e1ab6c50647c52de0b41794b (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
#pragma once

#ifdef __GNUC__
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wunused-parameter"
#endif

//===- llvm/Analysis/DependenceGraphBuilder.h -------------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file defines a builder interface that can be used to populate dependence
// graphs such as DDG and PDG.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_ANALYSIS_DEPENDENCEGRAPHBUILDER_H
#define LLVM_ANALYSIS_DEPENDENCEGRAPHBUILDER_H

#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/EquivalenceClasses.h"
#include "llvm/ADT/SmallVector.h"

namespace llvm {

class BasicBlock;
class DependenceInfo;
class Instruction;

/// This abstract builder class defines a set of high-level steps for creating
/// DDG-like graphs. The client code is expected to inherit from this class and
/// define concrete implementation for each of the pure virtual functions used
/// in the high-level algorithm.
template <class GraphType> class AbstractDependenceGraphBuilder {
protected:
  using BasicBlockListType = SmallVectorImpl<BasicBlock *>;

private:
  using NodeType = typename GraphType::NodeType;
  using EdgeType = typename GraphType::EdgeType;

public:
  using ClassesType = EquivalenceClasses<BasicBlock *>;
  using NodeListType = SmallVector<NodeType *, 4>;

  AbstractDependenceGraphBuilder(GraphType &G, DependenceInfo &D,
                                 const BasicBlockListType &BBs)
      : Graph(G), DI(D), BBList(BBs) {}
  virtual ~AbstractDependenceGraphBuilder() = default;

  /// The main entry to the graph construction algorithm. It starts by
  /// creating nodes in increasing order of granularity and then
  /// adds def-use and memory edges. As one of the final stages, it
  /// also creates pi-block nodes to facilitate codegen in transformations
  /// that use dependence graphs.
  ///
  /// The algorithmic complexity of this implementation is O(V^2 * I^2), where V
  /// is the number of vertecies (nodes) and I is the number of instructions in
  /// each node. The total number of instructions, N, is equal to V * I,
  /// therefore the worst-case time complexity is O(N^2). The average time
  /// complexity is O((N^2)/2).
  void populate() {
    computeInstructionOrdinals();
    createFineGrainedNodes();
    createDefUseEdges();
    createMemoryDependencyEdges();
    simplify();
    createAndConnectRootNode();
    createPiBlocks();
    sortNodesTopologically();
  }

  /// Compute ordinal numbers for each instruction and store them in a map for
  /// future look up. These ordinals are used to compute node ordinals which are
  /// in turn used to order nodes that are part of a cycle.
  /// Instruction ordinals are assigned based on lexical program order.
  void computeInstructionOrdinals();

  /// Create fine grained nodes. These are typically atomic nodes that
  /// consist of a single instruction.
  void createFineGrainedNodes();

  /// Analyze the def-use chains and create edges from the nodes containing
  /// definitions to the nodes containing the uses.
  void createDefUseEdges();

  /// Analyze data dependencies that exist between memory loads or stores,
  /// in the graph nodes and create edges between them.
  void createMemoryDependencyEdges();

  /// Create a root node and add edges such that each node in the graph is
  /// reachable from the root.
  void createAndConnectRootNode();

  /// Apply graph abstraction to groups of nodes that belong to a strongly
  /// connected component of the graph to create larger compound nodes
  /// called pi-blocks. The purpose of this abstraction is to isolate sets of
  /// program elements that need to stay together during codegen and turn
  /// the dependence graph into an acyclic graph.
  void createPiBlocks();

  /// Go through all the nodes in the graph and collapse any two nodes
  /// 'a' and 'b' if all of the following are true:
  ///   - the only edge from 'a' is a def-use edge to 'b' and
  ///   - the only edge to 'b' is a def-use edge from 'a' and
  ///   - there is no cyclic edge from 'b' to 'a' and
  ///   - all instructions in 'a' and 'b' belong to the same basic block and
  ///   - both 'a' and 'b' are simple (single or multi instruction) nodes.
  void simplify();

  /// Topologically sort the graph nodes.
  void sortNodesTopologically();

protected:
  /// Create the root node of the graph.
  virtual NodeType &createRootNode() = 0;

  /// Create an atomic node in the graph given a single instruction.
  virtual NodeType &createFineGrainedNode(Instruction &I) = 0;

  /// Create a pi-block node in the graph representing a group of nodes in an
  /// SCC of the graph.
  virtual NodeType &createPiBlock(const NodeListType &L) = 0;

  /// Create a def-use edge going from \p Src to \p Tgt.
  virtual EdgeType &createDefUseEdge(NodeType &Src, NodeType &Tgt) = 0;

  /// Create a memory dependence edge going from \p Src to \p Tgt.
  virtual EdgeType &createMemoryEdge(NodeType &Src, NodeType &Tgt) = 0;

  /// Create a rooted edge going from \p Src to \p Tgt .
  virtual EdgeType &createRootedEdge(NodeType &Src, NodeType &Tgt) = 0;

  /// Given a pi-block node, return a vector of all the nodes contained within
  /// it.
  virtual const NodeListType &getNodesInPiBlock(const NodeType &N) = 0;

  /// Deallocate memory of edge \p E.
  virtual void destroyEdge(EdgeType &E) { delete &E; }

  /// Deallocate memory of node \p N.
  virtual void destroyNode(NodeType &N) { delete &N; }

  /// Return true if creation of pi-blocks are supported and desired,
  /// and false otherwise.
  virtual bool shouldCreatePiBlocks() const { return true; }

  /// Return true if graph simplification step is requested, and false
  /// otherwise.
  virtual bool shouldSimplify() const { return true; }

  /// Return true if it's safe to merge the two nodes.
  virtual bool areNodesMergeable(const NodeType &A,
                                 const NodeType &B) const = 0;

  /// Append the content of node \p B into node \p A and remove \p B and
  /// the edge between \p A and \p B from the graph.
  virtual void mergeNodes(NodeType &A, NodeType &B) = 0;

  /// Given an instruction \p I return its associated ordinal number.
  size_t getOrdinal(Instruction &I) {
    assert(InstOrdinalMap.find(&I) != InstOrdinalMap.end() &&
           "No ordinal computed for this instruction.");
    return InstOrdinalMap[&I];
  }

  /// Given a node \p N return its associated ordinal number.
  size_t getOrdinal(NodeType &N) {
    assert(NodeOrdinalMap.find(&N) != NodeOrdinalMap.end() &&
           "No ordinal computed for this node.");
    return NodeOrdinalMap[&N];
  }

  /// Map types to map instructions to nodes used when populating the graph.
  using InstToNodeMap = DenseMap<Instruction *, NodeType *>;

  /// Map Types to map instruction/nodes to an ordinal number.
  using InstToOrdinalMap = DenseMap<Instruction *, size_t>;
  using NodeToOrdinalMap = DenseMap<NodeType *, size_t>;

  /// Reference to the graph that gets built by a concrete implementation of
  /// this builder.
  GraphType &Graph;

  /// Dependence information used to create memory dependence edges in the
  /// graph.
  DependenceInfo &DI;

  /// The list of basic blocks to consider when building the graph.
  const BasicBlockListType &BBList;

  /// A mapping from instructions to the corresponding nodes in the graph.
  InstToNodeMap IMap;

  /// A mapping from each instruction to an ordinal number. This map is used to
  /// populate the \p NodeOrdinalMap.
  InstToOrdinalMap InstOrdinalMap;

  /// A mapping from nodes to an ordinal number. This map is used to sort nodes
  /// in a pi-block based on program order.
  NodeToOrdinalMap NodeOrdinalMap;
};

} // namespace llvm

#endif // LLVM_ANALYSIS_DEPENDENCEGRAPHBUILDER_H

#ifdef __GNUC__
#pragma GCC diagnostic pop
#endif