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_DEPENDENCEGRAPHBUILDER_H 15 #define LLVM_ANALYSIS_DEPENDENCEGRAPHBUILDER_H 16 17 #include "llvm/ADT/DenseMap.h" 18 #include "llvm/ADT/EquivalenceClasses.h" 19 #include "llvm/ADT/SmallVector.h" 20 21 namespace llvm { 22 23 class BasicBlock; 24 class DependenceInfo; 25 class Instruction; 26 27 /// This abstract builder class defines a set of high-level steps for creating 28 /// DDG-like graphs. The client code is expected to inherit from this class and 29 /// define concrete implementation for each of the pure virtual functions used 30 /// in the high-level algorithm. 31 template <class GraphType> class AbstractDependenceGraphBuilder { 32 protected: 33 using BasicBlockListType = SmallVectorImpl<BasicBlock *>; 34 35 private: 36 using NodeType = typename GraphType::NodeType; 37 using EdgeType = typename GraphType::EdgeType; 38 39 public: 40 using ClassesType = EquivalenceClasses<BasicBlock *>; 41 using NodeListType = SmallVector<NodeType *, 4>; 42 43 AbstractDependenceGraphBuilder(GraphType &G, DependenceInfo &D, 44 const BasicBlockListType &BBs) 45 : Graph(G), DI(D), BBList(BBs) {} 46 virtual ~AbstractDependenceGraphBuilder() = default; 47 48 /// The main entry to the graph construction algorithm. It starts by 49 /// creating nodes in increasing order of granularity and then 50 /// adds def-use and memory edges. As one of the final stages, it 51 /// also creates pi-block nodes to facilitate codegen in transformations 52 /// that use dependence graphs. 53 /// 54 /// The algorithmic complexity of this implementation is O(V^2 * I^2), where V 55 /// is the number of vertecies (nodes) and I is the number of instructions in 56 /// each node. The total number of instructions, N, is equal to V * I, 57 /// therefore the worst-case time complexity is O(N^2). The average time 58 /// complexity is O((N^2)/2). 59 void populate() { 60 computeInstructionOrdinals(); 61 createFineGrainedNodes(); 62 createDefUseEdges(); 63 createMemoryDependencyEdges(); 64 simplify(); 65 createAndConnectRootNode(); 66 createPiBlocks(); 67 sortNodesTopologically(); 68 } 69 70 /// Compute ordinal numbers for each instruction and store them in a map for 71 /// future look up. These ordinals are used to compute node ordinals which are 72 /// in turn used to order nodes that are part of a cycle. 73 /// Instruction ordinals are assigned based on lexical program order. 74 void computeInstructionOrdinals(); 75 76 /// Create fine grained nodes. These are typically atomic nodes that 77 /// consist of a single instruction. 78 void createFineGrainedNodes(); 79 80 /// Analyze the def-use chains and create edges from the nodes containing 81 /// definitions to the nodes containing the uses. 82 void createDefUseEdges(); 83 84 /// Analyze data dependencies that exist between memory loads or stores, 85 /// in the graph nodes and create edges between them. 86 void createMemoryDependencyEdges(); 87 88 /// Create a root node and add edges such that each node in the graph is 89 /// reachable from the root. 90 void createAndConnectRootNode(); 91 92 /// Apply graph abstraction to groups of nodes that belong to a strongly 93 /// connected component of the graph to create larger compound nodes 94 /// called pi-blocks. The purpose of this abstraction is to isolate sets of 95 /// program elements that need to stay together during codegen and turn 96 /// the dependence graph into an acyclic graph. 97 void createPiBlocks(); 98 99 /// Go through all the nodes in the graph and collapse any two nodes 100 /// 'a' and 'b' if all of the following are true: 101 /// - the only edge from 'a' is a def-use edge to 'b' and 102 /// - the only edge to 'b' is a def-use edge from 'a' and 103 /// - there is no cyclic edge from 'b' to 'a' and 104 /// - all instructions in 'a' and 'b' belong to the same basic block and 105 /// - both 'a' and 'b' are simple (single or multi instruction) nodes. 106 void simplify(); 107 108 /// Topologically sort the graph nodes. 109 void sortNodesTopologically(); 110 111 protected: 112 /// Create the root node of the graph. 113 virtual NodeType &createRootNode() = 0; 114 115 /// Create an atomic node in the graph given a single instruction. 116 virtual NodeType &createFineGrainedNode(Instruction &I) = 0; 117 118 /// Create a pi-block node in the graph representing a group of nodes in an 119 /// SCC of the graph. 120 virtual NodeType &createPiBlock(const NodeListType &L) = 0; 121 122 /// Create a def-use edge going from \p Src to \p Tgt. 123 virtual EdgeType &createDefUseEdge(NodeType &Src, NodeType &Tgt) = 0; 124 125 /// Create a memory dependence edge going from \p Src to \p Tgt. 126 virtual EdgeType &createMemoryEdge(NodeType &Src, NodeType &Tgt) = 0; 127 128 /// Create a rooted edge going from \p Src to \p Tgt . 129 virtual EdgeType &createRootedEdge(NodeType &Src, NodeType &Tgt) = 0; 130 131 /// Given a pi-block node, return a vector of all the nodes contained within 132 /// it. 133 virtual const NodeListType &getNodesInPiBlock(const NodeType &N) = 0; 134 135 /// Deallocate memory of edge \p E. 136 virtual void destroyEdge(EdgeType &E) { delete &E; } 137 138 /// Deallocate memory of node \p N. 139 virtual void destroyNode(NodeType &N) { delete &N; } 140 141 /// Return true if creation of pi-blocks are supported and desired, 142 /// and false otherwise. 143 virtual bool shouldCreatePiBlocks() const { return true; } 144 145 /// Return true if graph simplification step is requested, and false 146 /// otherwise. 147 virtual bool shouldSimplify() const { return true; } 148 149 /// Return true if it's safe to merge the two nodes. 150 virtual bool areNodesMergeable(const NodeType &A, 151 const NodeType &B) const = 0; 152 153 /// Append the content of node \p B into node \p A and remove \p B and 154 /// the edge between \p A and \p B from the graph. 155 virtual void mergeNodes(NodeType &A, NodeType &B) = 0; 156 157 /// Given an instruction \p I return its associated ordinal number. 158 size_t getOrdinal(Instruction &I) { 159 assert(InstOrdinalMap.contains(&I) && 160 "No ordinal computed for this instruction."); 161 return InstOrdinalMap[&I]; 162 } 163 164 /// Given a node \p N return its associated ordinal number. 165 size_t getOrdinal(NodeType &N) { 166 assert(NodeOrdinalMap.contains(&N) && "No ordinal computed for this node."); 167 return NodeOrdinalMap[&N]; 168 } 169 170 /// Map types to map instructions to nodes used when populating the graph. 171 using InstToNodeMap = DenseMap<Instruction *, NodeType *>; 172 173 /// Map Types to map instruction/nodes to an ordinal number. 174 using InstToOrdinalMap = DenseMap<Instruction *, size_t>; 175 using NodeToOrdinalMap = DenseMap<NodeType *, size_t>; 176 177 /// Reference to the graph that gets built by a concrete implementation of 178 /// this builder. 179 GraphType &Graph; 180 181 /// Dependence information used to create memory dependence edges in the 182 /// graph. 183 DependenceInfo &DI; 184 185 /// The list of basic blocks to consider when building the graph. 186 const BasicBlockListType &BBList; 187 188 /// A mapping from instructions to the corresponding nodes in the graph. 189 InstToNodeMap IMap; 190 191 /// A mapping from each instruction to an ordinal number. This map is used to 192 /// populate the \p NodeOrdinalMap. 193 InstToOrdinalMap InstOrdinalMap; 194 195 /// A mapping from nodes to an ordinal number. This map is used to sort nodes 196 /// in a pi-block based on program order. 197 NodeToOrdinalMap NodeOrdinalMap; 198 }; 199 200 } // namespace llvm 201 202 #endif // LLVM_ANALYSIS_DEPENDENCEGRAPHBUILDER_H 203