LLVM  10.0.0svn
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_DEPENDENCE_GRAPH_BUILDER_H
15 #define LLVM_ANALYSIS_DEPENDENCE_GRAPH_BUILDER_H
16 
19 #include "llvm/IR/BasicBlock.h"
20 #include "llvm/IR/Instructions.h"
21 
22 namespace 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.
28 template <class GraphType> class AbstractDependenceGraphBuilder {
29 protected:
31 
32 private:
33  using NodeType = typename GraphType::NodeType;
34  using EdgeType = typename GraphType::EdgeType;
35 
36 public:
39 
41  const BasicBlockListType &BBs)
42  : Graph(G), DI(D), BBList(BBs) {}
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.
48  ///
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).
54  void populate() {
59  }
60 
61  /// Create fine grained nodes. These are typically atomic nodes that
62  /// consist of a single instruction.
64 
65  /// Analyze the def-use chains and create edges from the nodes containing
66  /// definitions to the nodes containing the uses.
67  void createDefUseEdges();
68 
69  /// Analyze data dependencies that exist between memory loads or stores,
70  /// in the graph nodes and create edges between them.
72 
73  /// Create a root node and add edges such that each node in the graph is
74  /// reachable from the root.
76 
77 protected:
78  /// Create the root node of the graph.
79  virtual NodeType &createRootNode() = 0;
80 
81  /// Create an atomic node in the graph given a single instruction.
82  virtual NodeType &createFineGrainedNode(Instruction &I) = 0;
83 
84  /// Create a def-use edge going from \p Src to \p Tgt.
85  virtual EdgeType &createDefUseEdge(NodeType &Src, NodeType &Tgt) = 0;
86 
87  /// Create a memory dependence edge going from \p Src to \p Tgt.
88  virtual EdgeType &createMemoryEdge(NodeType &Src, NodeType &Tgt) = 0;
89 
90  /// Create a rooted edge going from \p Src to \p Tgt .
91  virtual EdgeType &createRootedEdge(NodeType &Src, NodeType &Tgt) = 0;
92 
93  /// Deallocate memory of edge \p E.
94  virtual void destroyEdge(EdgeType &E) { delete &E; }
95 
96  /// Deallocate memory of node \p N.
97  virtual void destroyNode(NodeType &N) { delete &N; }
98 
99  /// Map types to map instructions to nodes used when populating the graph.
101 
102  /// Reference to the graph that gets built by a concrete implementation of
103  /// this builder.
104  GraphType &Graph;
105 
106  /// Dependence information used to create memory dependence edges in the
107  /// graph.
109 
110  /// The list of basic blocks to consider when building the graph.
112 
113  /// A mapping from instructions to the corresponding nodes in the graph.
115 };
116 
117 } // namespace llvm
118 
119 #endif // LLVM_ANALYSIS_DEPENDENCE_GRAPH_BUILDER_H
This class represents lattice values for constants.
Definition: AllocatorList.h:23
virtual EdgeType & createDefUseEdge(NodeType &Src, NodeType &Tgt)=0
Create a def-use edge going from Src to Tgt.
DependenceInfo - This class is the main dependence-analysis driver.
const BasicBlockListType & BBList
The list of basic blocks to consider when building the graph.
NodeType
ISD::NodeType enum - This enum defines the target-independent operators for a SelectionDAG.
Definition: ISDOpcodes.h:38
AbstractDependenceGraphBuilder(GraphType &G, DependenceInfo &D, const BasicBlockListType &BBs)
void createFineGrainedNodes()
Create fine grained nodes.
virtual EdgeType & createMemoryEdge(NodeType &Src, NodeType &Tgt)=0
Create a memory dependence edge going from Src to Tgt.
virtual EdgeType & createRootedEdge(NodeType &Src, NodeType &Tgt)=0
Create a rooted edge going from Src to Tgt .
virtual void destroyNode(NodeType &N)
Deallocate memory of node N.
virtual void destroyEdge(EdgeType &E)
Deallocate memory of edge E.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
EquivalenceClasses - This represents a collection of equivalence classes and supports three efficient...
void createDefUseEdges()
Analyze the def-use chains and create edges from the nodes containing definitions to the nodes contai...
void populate()
The main entry to the graph construction algorithm.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
const DataFlowGraph & G
Definition: RDFGraph.cpp:202
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
void createMemoryDependencyEdges()
Analyze data dependencies that exist between memory loads or stores, in the graph nodes and create ed...
This abstract builder class defines a set of high-level steps for creating DDG-like graphs...
InstToNodeMap IMap
A mapping from instructions to the corresponding nodes in the graph.
DependenceInfo & DI
Dependence information used to create memory dependence edges in the graph.
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
virtual NodeType & createFineGrainedNode(Instruction &I)=0
Create an atomic node in the graph given a single instruction.
virtual NodeType & createRootNode()=0
Create the root node of the graph.
GraphType & Graph
Reference to the graph that gets built by a concrete implementation of this builder.
void createAndConnectRootNode()
Create a root node and add edges such that each node in the graph is reachable from the root...