LLVM  10.0.0svn
DDG.h
Go to the documentation of this file.
1 //===- llvm/Analysis/DDG.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 the Data-Dependence Graph (DDG).
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #ifndef LLVM_ANALYSIS_DDG_H
14 #define LLVM_ANALYSIS_DDG_H
15 
16 #include "llvm/ADT/DirectedGraph.h"
20 #include "llvm/IR/Instructions.h"
21 #include <unordered_map>
22 
23 namespace llvm {
24 class DDGNode;
25 class DDGEdge;
29 class LPMUpdater;
30 
31 /// Data Dependence Graph Node
32 /// The graph can represent the following types of nodes:
33 /// 1. Single instruction node containing just one instruction.
34 /// 2. Multiple instruction node where two or more instructions from
35 /// the same basic block are merged into one node.
36 /// 3. Root node is a special node that connects to all components such that
37 /// there is always a path from it to any node in the graph.
38 class DDGNode : public DDGNodeBase {
39 public:
41 
42  enum class NodeKind {
43  Unknown,
46  Root,
47  };
48 
49  DDGNode() = delete;
50  DDGNode(const NodeKind K) : DDGNodeBase(), Kind(K) {}
51  DDGNode(const DDGNode &N) : DDGNodeBase(N), Kind(N.Kind) {}
52  DDGNode(DDGNode &&N) : DDGNodeBase(std::move(N)), Kind(N.Kind) {}
53  virtual ~DDGNode() = 0;
54 
57  Kind = N.Kind;
58  return *this;
59  }
60 
62  DGNode::operator=(std::move(N));
63  Kind = N.Kind;
64  return *this;
65  }
66 
67  /// Getter for the kind of this node.
68  NodeKind getKind() const { return Kind; }
69 
70  /// Collect a list of instructions, in \p IList, for which predicate \p Pred
71  /// evaluates to true when iterating over instructions of this node. Return
72  /// true if at least one instruction was collected, and false otherwise.
73  bool collectInstructions(llvm::function_ref<bool(Instruction *)> const &Pred,
74  InstructionListType &IList) const;
75 
76 protected:
77  /// Setter for the kind of this node.
78  void setKind(NodeKind K) { Kind = K; }
79 
80 private:
81  NodeKind Kind;
82 };
83 
84 /// Subclass of DDGNode representing the root node of the graph.
85 /// There should only be one such node in a given graph.
86 class RootDDGNode : public DDGNode {
87 public:
89  RootDDGNode(const RootDDGNode &N) = delete;
90  RootDDGNode(RootDDGNode &&N) : DDGNode(std::move(N)) {}
92 
93  /// Define classof to be able to use isa<>, cast<>, dyn_cast<>, etc.
94  static bool classof(const DDGNode *N) {
95  return N->getKind() == NodeKind::Root;
96  }
97  static bool classof(const RootDDGNode *N) { return true; }
98 };
99 
100 /// Subclass of DDGNode representing single or multi-instruction nodes.
101 class SimpleDDGNode : public DDGNode {
102 public:
103  SimpleDDGNode() = delete;
105  SimpleDDGNode(const SimpleDDGNode &N);
107  ~SimpleDDGNode();
108 
111  InstList = N.InstList;
112  return *this;
113  }
114 
116  DDGNode::operator=(std::move(N));
117  InstList = std::move(N.InstList);
118  return *this;
119  }
120 
121  /// Get the list of instructions in this node.
123  assert(!InstList.empty() && "Instruction List is empty.");
124  return InstList;
125  }
127  return const_cast<InstructionListType &>(
128  static_cast<const SimpleDDGNode *>(this)->getInstructions());
129  }
130 
131  /// Get the first/last instruction in the node.
132  Instruction *getFirstInstruction() const { return getInstructions().front(); }
133  Instruction *getLastInstruction() const { return getInstructions().back(); }
134 
135  /// Define classof to be able to use isa<>, cast<>, dyn_cast<>, etc.
136  static bool classof(const DDGNode *N) {
137  return N->getKind() == NodeKind::SingleInstruction ||
139  }
140  static bool classof(const SimpleDDGNode *N) { return true; }
141 
142 private:
143  /// Append the list of instructions in \p Input to this node.
144  void appendInstructions(const InstructionListType &Input) {
145  setKind((InstList.size() == 0 && Input.size() == 1)
148  InstList.insert(InstList.end(), Input.begin(), Input.end());
149  }
150  void appendInstructions(const SimpleDDGNode &Input) {
151  appendInstructions(Input.getInstructions());
152  }
153 
154  /// List of instructions associated with a single or multi-instruction node.
156 };
157 
158 /// Data Dependency Graph Edge.
159 /// An edge in the DDG can represent a def-use relationship or
160 /// a memory dependence based on the result of DependenceAnalysis.
161 /// A rooted edge connects the root node to one of the components
162 /// of the graph.
163 class DDGEdge : public DDGEdgeBase {
164 public:
165  /// The kind of edge in the DDG
166  enum class EdgeKind { Unknown, RegisterDefUse, MemoryDependence, Rooted };
167 
168  explicit DDGEdge(DDGNode &N) = delete;
169  DDGEdge(DDGNode &N, EdgeKind K) : DDGEdgeBase(N), Kind(K) {}
170  DDGEdge(const DDGEdge &E) : DDGEdgeBase(E), Kind(E.getKind()) {}
171  DDGEdge(DDGEdge &&E) : DDGEdgeBase(std::move(E)), Kind(E.Kind) {}
174  Kind = E.Kind;
175  return *this;
176  }
177 
179  DDGEdgeBase::operator=(std::move(E));
180  Kind = E.Kind;
181  return *this;
182  }
183 
184  /// Get the edge kind
185  EdgeKind getKind() const { return Kind; };
186 
187  /// Return true if this is a def-use edge, and false otherwise.
188  bool isDefUse() const { return Kind == EdgeKind::RegisterDefUse; }
189 
190  /// Return true if this is a memory dependence edge, and false otherwise.
191  bool isMemoryDependence() const { return Kind == EdgeKind::MemoryDependence; }
192 
193  /// Return true if this is an edge stemming from the root node, and false
194  /// otherwise.
195  bool isRooted() const { return Kind == EdgeKind::Rooted; }
196 
197 private:
198  EdgeKind Kind;
199 };
200 
201 /// Encapsulate some common data and functionality needed for different
202 /// variations of data dependence graphs.
203 template <typename NodeType> class DependenceGraphInfo {
204 public:
206 
207  DependenceGraphInfo() = delete;
208  DependenceGraphInfo(const DependenceGraphInfo &G) = delete;
209  DependenceGraphInfo(const std::string &N, const DependenceInfo &DepInfo)
210  : Name(N), DI(DepInfo), Root(nullptr) {}
212  : Name(std::move(G.Name)), DI(std::move(G.DI)), Root(G.Root) {}
213  virtual ~DependenceGraphInfo() {}
214 
215  /// Return the label that is used to name this graph.
216  const StringRef getName() const { return Name; }
217 
218  /// Return the root node of the graph.
219  NodeType &getRoot() const {
220  assert(Root && "Root node is not available yet. Graph construction may "
221  "still be in progress\n");
222  return *Root;
223  }
224 
225 protected:
226  // Name of the graph.
227  std::string Name;
228 
229  // Store a copy of DependenceInfo in the graph, so that individual memory
230  // dependencies don't need to be stored. Instead when the dependence is
231  // queried it is recomputed using @DI.
233 
234  // A special node in the graph that has an edge to every connected component of
235  // the graph, to ensure all nodes are reachable in a graph walk.
236  NodeType *Root = nullptr;
237 };
238 
240 
241 /// Data Dependency Graph
242 class DataDependenceGraph : public DDGBase, public DDGInfo {
243  friend class DDGBuilder;
244 
245 public:
246  using NodeType = DDGNode;
247  using EdgeType = DDGEdge;
248 
249  DataDependenceGraph() = delete;
250  DataDependenceGraph(const DataDependenceGraph &G) = delete;
252  : DDGBase(std::move(G)), DDGInfo(std::move(G)) {}
254  DataDependenceGraph(const Loop &L, DependenceInfo &DI);
256 
257 protected:
258  /// Add node \p N to the graph, if it's not added yet, and keep track of
259  /// the root node. Return true if node is successfully added.
260  bool addNode(NodeType &N);
261 
262 };
263 
264 /// Concrete implementation of a pure data dependence graph builder. This class
265 /// provides custom implementation for the pure-virtual functions used in the
266 /// generic dependence graph build algorithm.
267 ///
268 /// For information about time complexity of the build algorithm see the
269 /// comments near the declaration of AbstractDependenceGraphBuilder.
270 class DDGBuilder : public AbstractDependenceGraphBuilder<DataDependenceGraph> {
271 public:
273  const BasicBlockListType &BBs)
274  : AbstractDependenceGraphBuilder(G, D, BBs) {}
275  DDGNode &createRootNode() final override {
276  auto *RN = new RootDDGNode();
277  assert(RN && "Failed to allocate memory for DDG root node.");
278  Graph.addNode(*RN);
279  return *RN;
280  }
282  auto *SN = new SimpleDDGNode(I);
283  assert(SN && "Failed to allocate memory for simple DDG node.");
284  Graph.addNode(*SN);
285  return *SN;
286  }
287  DDGEdge &createDefUseEdge(DDGNode &Src, DDGNode &Tgt) final override {
288  auto *E = new DDGEdge(Tgt, DDGEdge::EdgeKind::RegisterDefUse);
289  assert(E && "Failed to allocate memory for edge");
290  Graph.connect(Src, Tgt, *E);
291  return *E;
292  }
293  DDGEdge &createMemoryEdge(DDGNode &Src, DDGNode &Tgt) final override {
295  assert(E && "Failed to allocate memory for edge");
296  Graph.connect(Src, Tgt, *E);
297  return *E;
298  }
299  DDGEdge &createRootedEdge(DDGNode &Src, DDGNode &Tgt) final override {
300  auto *E = new DDGEdge(Tgt, DDGEdge::EdgeKind::Rooted);
301  assert(E && "Failed to allocate memory for edge");
302  assert(isa<RootDDGNode>(Src) && "Expected root node");
303  Graph.connect(Src, Tgt, *E);
304  return *E;
305  }
306 
307 };
308 
314 
315 //===--------------------------------------------------------------------===//
316 // DDG Analysis Passes
317 //===--------------------------------------------------------------------===//
318 
319 /// Analysis pass that builds the DDG for a loop.
320 class DDGAnalysis : public AnalysisInfoMixin<DDGAnalysis> {
321 public:
322  using Result = std::unique_ptr<DataDependenceGraph>;
324 
325 private:
327  static AnalysisKey Key;
328 };
329 
330 /// Textual printer pass for the DDG of a loop.
331 class DDGAnalysisPrinterPass : public PassInfoMixin<DDGAnalysisPrinterPass> {
332 public:
333  explicit DDGAnalysisPrinterPass(raw_ostream &OS) : OS(OS) {}
336 
337 private:
338  raw_ostream &OS;
339 };
340 
341 //===--------------------------------------------------------------------===//
342 // GraphTraits specializations for the DDG
343 //===--------------------------------------------------------------------===//
344 
345 /// non-const versions of the grapth trait specializations for DDG
346 template <> struct GraphTraits<DDGNode *> {
347  using NodeRef = DDGNode *;
348 
350  return &P->getTargetNode();
351  }
352 
353  // Provide a mapped iterator so that the GraphTrait-based implementations can
354  // find the target nodes without having to explicitly go through the edges.
355  using ChildIteratorType =
358 
359  static NodeRef getEntryNode(NodeRef N) { return N; }
361  return ChildIteratorType(N->begin(), &DDGGetTargetNode);
362  }
364  return ChildIteratorType(N->end(), &DDGGetTargetNode);
365  }
366 
368  return N->begin();
369  }
370  static ChildEdgeIteratorType child_edge_end(NodeRef N) { return N->end(); }
371 };
372 
373 template <>
377  return &DG->getRoot();
378  }
380  return DG->begin();
381  }
382  static nodes_iterator nodes_end(DataDependenceGraph *DG) { return DG->end(); }
383 };
384 
385 /// const versions of the grapth trait specializations for DDG
386 template <> struct GraphTraits<const DDGNode *> {
387  using NodeRef = const DDGNode *;
388 
390  return &P->getTargetNode();
391  }
392 
393  // Provide a mapped iterator so that the GraphTrait-based implementations can
394  // find the target nodes without having to explicitly go through the edges.
395  using ChildIteratorType =
398 
399  static NodeRef getEntryNode(NodeRef N) { return N; }
401  return ChildIteratorType(N->begin(), &DDGGetTargetNode);
402  }
404  return ChildIteratorType(N->end(), &DDGGetTargetNode);
405  }
406 
408  return N->begin();
409  }
410  static ChildEdgeIteratorType child_edge_end(NodeRef N) { return N->end(); }
411 };
412 
413 template <>
418  return &DG->getRoot();
419  }
421  return DG->begin();
422  }
424  return DG->end();
425  }
426 };
427 
428 } // namespace llvm
429 
430 #endif // LLVM_ANALYSIS_DDG_H
DataDependenceGraph::const_iterator nodes_iterator
Definition: DDG.h:416
DGEdge< NodeType, EdgeType > & operator=(const DGEdge< NodeType, EdgeType > &E)
Definition: DirectedGraph.h:34
Data Dependency Graph.
Definition: DDG.h:242
DDGEdge(const DDGEdge &E)
Definition: DDG.h:170
static NodeRef getEntryNode(const DataDependenceGraph *DG)
Definition: DDG.h:417
DDGNode & operator=(DDGNode &&N)
Definition: DDG.h:61
NodeType & getRoot() const
Return the root node of the graph.
Definition: DDG.h:219
This class represents lattice values for constants.
Definition: AllocatorList.h:23
static bool classof(const DDGNode *N)
Define classof to be able to use isa<>, cast<>, dyn_cast<>, etc.
Definition: DDG.h:94
static nodes_iterator nodes_end(DataDependenceGraph *DG)
Definition: DDG.h:382
amdgpu Simplify well known AMD library false FunctionCallee Value const Twine & Name
static NodeRef getEntryNode(NodeRef N)
Definition: DDG.h:359
Data Dependency Graph Edge.
Definition: DDG.h:163
Data Dependence Graph Node The graph can represent the following types of nodes:
Definition: DDG.h:38
DataDependenceGraph(DataDependenceGraph &&G)
Definition: DDG.h:251
static ChildIteratorType child_begin(NodeRef N)
Definition: DDG.h:400
virtual ~DependenceGraphInfo()
Definition: DDG.h:213
DDGAnalysisPrinterPass(raw_ostream &OS)
Definition: DDG.h:333
DDGEdge & operator=(DDGEdge &&E)
Definition: DDG.h:178
DDGEdge & createMemoryEdge(DDGNode &Src, DDGNode &Tgt) final override
Definition: DDG.h:293
SimpleDDGNode & operator=(SimpleDDGNode &&N)
Definition: DDG.h:115
static nodes_iterator nodes_end(const DataDependenceGraph *DG)
Definition: DDG.h:423
const NodeType & getTargetNode() const
Retrieve the target node this edge connects to.
Definition: DirectedGraph.h:45
static ChildEdgeIteratorType child_edge_begin(NodeRef N)
Definition: DDG.h:407
const InstructionListType & getInstructions() const
Get the list of instructions in this node.
Definition: DDG.h:122
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLExtras.h:104
virtual ~DDGNode()=0
Definition: DDG.cpp:25
static nodes_iterator nodes_begin(DataDependenceGraph *DG)
Definition: DDG.h:379
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
F(f)
void setKind(NodeKind K)
Setter for the kind of this node.
Definition: DDG.h:78
DependenceInfo - This class is the main dependence-analysis driver.
bool isMemoryDependence() const
Return true if this is a memory dependence edge, and false otherwise.
Definition: DDG.h:191
NodeType
ISD::NodeType enum - This enum defines the target-independent operators for a SelectionDAG.
Definition: ISDOpcodes.h:38
std::string Name
Definition: DDG.h:227
static ChildEdgeIteratorType child_edge_begin(NodeRef N)
Definition: DDG.h:367
Concrete implementation of a pure data dependence graph builder.
Definition: DDG.h:270
const_iterator begin() const
DDGEdge(DDGEdge &&E)
Definition: DDG.h:171
Definition: BitVector.h:937
static nodes_iterator nodes_begin(const DataDependenceGraph *DG)
Definition: DDG.h:420
static ChildEdgeIteratorType child_edge_end(NodeRef N)
Definition: DDG.h:370
DDGNode & operator=(const DDGNode &N)
Definition: DDG.h:55
DDGBuilder(DataDependenceGraph &G, DependenceInfo &D, const BasicBlockListType &BBs)
Definition: DDG.h:272
DDGNode & createRootNode() final override
Create the root node of the graph.
Definition: DDG.h:275
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:41
DGNode< NodeType, EdgeType > & operator=(const DGNode< NodeType, EdgeType > &N)
Definition: DirectedGraph.h:80
Instruction * getFirstInstruction() const
Get the first/last instruction in the node.
Definition: DDG.h:132
Key
PAL metadata keys.
bool isRooted() const
Return true if this is an edge stemming from the root node, and false otherwise.
Definition: DDG.h:195
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:373
DDGEdge & operator=(const DDGEdge &E)
Definition: DDG.h:172
typename EdgeListTy::const_iterator const_iterator
Definition: DirectedGraph.h:71
This header provides classes for managing per-loop analyses.
static ChildIteratorType child_begin(NodeRef N)
Definition: DDG.h:360
static NodeRef getEntryNode(DataDependenceGraph *DG)
Definition: DDG.h:376
~RootDDGNode()
Definition: DDG.h:91
EdgeKind getKind() const
Get the edge kind.
Definition: DDG.h:185
Textual printer pass for the DDG of a loop.
Definition: DDG.h:331
DDGNode(const NodeKind K)
Definition: DDG.h:50
#define P(N)
SimpleDDGNode & operator=(const SimpleDDGNode &N)
Definition: DDG.h:109
typename DDGNode *::UnknownGraphTypeError NodeRef
Definition: GraphTraits.h:78
const_iterator end() const
Definition: DirectedGraph.h:95
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:154
Represent an edge in the directed graph.
Definition: DirectedGraph.h:27
EdgeKind
The kind of edge in the DDG.
Definition: DDG.h:166
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static ChildIteratorType child_end(NodeRef N)
Definition: DDG.h:403
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:390
static bool classof(const RootDDGNode *N)
Definition: DDG.h:97
const StringRef getName() const
Return the label that is used to name this graph.
Definition: DDG.h:216
NodeKind getKind() const
Getter for the kind of this node.
Definition: DDG.h:68
DDGNode()=delete
Determine the kind of a node from its type.
DDGEdge & createRootedEdge(DDGNode &Src, DDGNode &Tgt) final override
Definition: DDG.h:299
size_t size() const
Definition: SmallVector.h:52
static ChildEdgeIteratorType child_edge_end(NodeRef N)
Definition: DDG.h:410
const versions of the grapth trait specializations for DDG
Definition: DDG.h:386
DDGNode & createFineGrainedNode(Instruction &I) final override
Create an atomic node in the graph given a single instruction.
Definition: DDG.h:281
static DDGNode * DDGGetTargetNode(DGEdge< DDGNode, DDGEdge > *P)
Definition: DDG.h:349
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
std::unique_ptr< DataDependenceGraph > Result
Definition: DDG.h:322
Directed graph.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
InstructionListType & getInstructions()
Definition: DDG.h:126
Encapsulate some common data and functionality needed for different variations of data dependence gra...
Definition: DDG.h:203
Represent a node in the directed graph.
Definition: DirectedGraph.h:67
const DataFlowGraph & G
Definition: RDFGraph.cpp:202
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
bool isDefUse() const
Return true if this is a def-use edge, and false otherwise.
Definition: DDG.h:188
DDGNode::const_iterator ChildEdgeIteratorType
Definition: DDG.h:397
const_iterator end() const
Instruction * getLastInstruction() const
Definition: DDG.h:133
const DependenceInfo DI
Definition: DDG.h:232
Subclass of DDGNode representing the root node of the graph.
Definition: DDG.h:86
non-const versions of the grapth trait specializations for DDG
Definition: DDG.h:346
Analysis pass that builds the DDG for a loop.
Definition: DDG.h:320
RootDDGNode(RootDDGNode &&N)
Definition: DDG.h:90
DependenceGraphInfo(const std::string &N, const DependenceInfo &DepInfo)
Definition: DDG.h:209
static const DDGNode * DDGGetTargetNode(const DGEdge< DDGNode, DDGEdge > *P)
Definition: DDG.h:389
This abstract builder class defines a set of high-level steps for creating DDG-like graphs...
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:509
typename EdgeListTy::iterator iterator
Definition: DirectedGraph.h:70
typename NodeListTy::const_iterator const_iterator
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
static NodeRef getEntryNode(NodeRef N)
Definition: DDG.h:399
static bool classof(const SimpleDDGNode *N)
Definition: DDG.h:140
DDGNode::iterator ChildEdgeIteratorType
Definition: DDG.h:357
static ChildIteratorType child_end(NodeRef N)
Definition: DDG.h:363
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2047
DependenceGraphInfo(DependenceGraphInfo &&G)
Definition: DDG.h:211
Subclass of DDGNode representing single or multi-instruction nodes.
Definition: DDG.h:101
DDGNode(DDGNode &&N)
Definition: DDG.h:52
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
aarch64 promote const
typename NodeListTy::iterator iterator
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
DataDependenceGraph::iterator nodes_iterator
Definition: DDG.h:375
A container for analyses that lazily runs them and caches their results.
DDGEdge & createDefUseEdge(DDGNode &Src, DDGNode &Tgt) final override
Definition: DDG.h:287
DDGNode(const DDGNode &N)
Definition: DDG.h:51
static bool classof(const DDGNode *N)
Define classof to be able to use isa<>, cast<>, dyn_cast<>, etc.
Definition: DDG.h:136
const_iterator begin() const
Definition: DirectedGraph.h:94
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:71
bool collectInstructions(llvm::function_ref< bool(Instruction *)> const &Pred, InstructionListType &IList) const
Collect a list of instructions, in IList, for which predicate Pred evaluates to true when iterating o...
Definition: DDG.cpp:27
DDGEdge(DDGNode &N, EdgeKind K)
Definition: DDG.h:169