1 //===- DependenceGraphBuilder.cpp ------------------------------------------==// 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 // This file implements common steps of the build algorithm for construction 9 // of dependence graphs such as DDG and PDG. 10 //===----------------------------------------------------------------------===// 11 12 #include "llvm/Analysis/DependenceGraphBuilder.h" 13 #include "llvm/ADT/SCCIterator.h" 14 #include "llvm/ADT/Statistic.h" 15 #include "llvm/Analysis/DDG.h" 16 17 using namespace llvm; 18 19 #define DEBUG_TYPE "dgb" 20 21 STATISTIC(TotalGraphs, "Number of dependence graphs created."); 22 STATISTIC(TotalDefUseEdges, "Number of def-use edges created."); 23 STATISTIC(TotalMemoryEdges, "Number of memory dependence edges created."); 24 STATISTIC(TotalFineGrainedNodes, "Number of fine-grained nodes created."); 25 STATISTIC(TotalConfusedEdges, 26 "Number of confused memory dependencies between two nodes."); 27 STATISTIC(TotalEdgeReversals, 28 "Number of times the source and sink of dependence was reversed to " 29 "expose cycles in the graph."); 30 31 using InstructionListType = SmallVector<Instruction *, 2>; 32 33 //===--------------------------------------------------------------------===// 34 // AbstractDependenceGraphBuilder implementation 35 //===--------------------------------------------------------------------===// 36 37 template <class G> 38 void AbstractDependenceGraphBuilder<G>::createFineGrainedNodes() { 39 ++TotalGraphs; 40 assert(IMap.empty() && "Expected empty instruction map at start"); 41 for (BasicBlock *BB : BBList) 42 for (Instruction &I : *BB) { 43 auto &NewNode = createFineGrainedNode(I); 44 IMap.insert(std::make_pair(&I, &NewNode)); 45 ++TotalFineGrainedNodes; 46 } 47 } 48 49 template <class G> 50 void AbstractDependenceGraphBuilder<G>::createAndConnectRootNode() { 51 // Create a root node that connects to every connected component of the graph. 52 // This is done to allow graph iterators to visit all the disjoint components 53 // of the graph, in a single walk. 54 // 55 // This algorithm works by going through each node of the graph and for each 56 // node N, do a DFS starting from N. A rooted edge is established between the 57 // root node and N (if N is not yet visited). All the nodes reachable from N 58 // are marked as visited and are skipped in the DFS of subsequent nodes. 59 // 60 // Note: This algorithm tries to limit the number of edges out of the root 61 // node to some extent, but there may be redundant edges created depending on 62 // the iteration order. For example for a graph {A -> B}, an edge from the 63 // root node is added to both nodes if B is visited before A. While it does 64 // not result in minimal number of edges, this approach saves compile-time 65 // while keeping the number of edges in check. 66 auto &RootNode = createRootNode(); 67 df_iterator_default_set<const NodeType *, 4> Visited; 68 for (auto *N : Graph) { 69 if (*N == RootNode) 70 continue; 71 for (auto I : depth_first_ext(N, Visited)) 72 if (I == N) 73 createRootedEdge(RootNode, *N); 74 } 75 } 76 77 template <class G> void AbstractDependenceGraphBuilder<G>::createDefUseEdges() { 78 for (NodeType *N : Graph) { 79 InstructionListType SrcIList; 80 N->collectInstructions([](const Instruction *I) { return true; }, SrcIList); 81 82 // Use a set to mark the targets that we link to N, so we don't add 83 // duplicate def-use edges when more than one instruction in a target node 84 // use results of instructions that are contained in N. 85 SmallPtrSet<NodeType *, 4> VisitedTargets; 86 87 for (Instruction *II : SrcIList) { 88 for (User *U : II->users()) { 89 Instruction *UI = dyn_cast<Instruction>(U); 90 if (!UI) 91 continue; 92 NodeType *DstNode = nullptr; 93 if (IMap.find(UI) != IMap.end()) 94 DstNode = IMap.find(UI)->second; 95 96 // In the case of loops, the scope of the subgraph is all the 97 // basic blocks (and instructions within them) belonging to the loop. We 98 // simply ignore all the edges coming from (or going into) instructions 99 // or basic blocks outside of this range. 100 if (!DstNode) { 101 LLVM_DEBUG( 102 dbgs() 103 << "skipped def-use edge since the sink" << *UI 104 << " is outside the range of instructions being considered.\n"); 105 continue; 106 } 107 108 // Self dependencies are ignored because they are redundant and 109 // uninteresting. 110 if (DstNode == N) { 111 LLVM_DEBUG(dbgs() 112 << "skipped def-use edge since the sink and the source (" 113 << N << ") are the same.\n"); 114 continue; 115 } 116 117 if (VisitedTargets.insert(DstNode).second) { 118 createDefUseEdge(*N, *DstNode); 119 ++TotalDefUseEdges; 120 } 121 } 122 } 123 } 124 } 125 126 template <class G> 127 void AbstractDependenceGraphBuilder<G>::createMemoryDependencyEdges() { 128 using DGIterator = typename G::iterator; 129 auto isMemoryAccess = [](const Instruction *I) { 130 return I->mayReadOrWriteMemory(); 131 }; 132 for (DGIterator SrcIt = Graph.begin(), E = Graph.end(); SrcIt != E; ++SrcIt) { 133 InstructionListType SrcIList; 134 (*SrcIt)->collectInstructions(isMemoryAccess, SrcIList); 135 if (SrcIList.empty()) 136 continue; 137 138 for (DGIterator DstIt = SrcIt; DstIt != E; ++DstIt) { 139 if (**SrcIt == **DstIt) 140 continue; 141 InstructionListType DstIList; 142 (*DstIt)->collectInstructions(isMemoryAccess, DstIList); 143 if (DstIList.empty()) 144 continue; 145 bool ForwardEdgeCreated = false; 146 bool BackwardEdgeCreated = false; 147 for (Instruction *ISrc : SrcIList) { 148 for (Instruction *IDst : DstIList) { 149 auto D = DI.depends(ISrc, IDst, true); 150 if (!D) 151 continue; 152 153 // If we have a dependence with its left-most non-'=' direction 154 // being '>' we need to reverse the direction of the edge, because 155 // the source of the dependence cannot occur after the sink. For 156 // confused dependencies, we will create edges in both directions to 157 // represent the possibility of a cycle. 158 159 auto createConfusedEdges = [&](NodeType &Src, NodeType &Dst) { 160 if (!ForwardEdgeCreated) { 161 createMemoryEdge(Src, Dst); 162 ++TotalMemoryEdges; 163 } 164 if (!BackwardEdgeCreated) { 165 createMemoryEdge(Dst, Src); 166 ++TotalMemoryEdges; 167 } 168 ForwardEdgeCreated = BackwardEdgeCreated = true; 169 ++TotalConfusedEdges; 170 }; 171 172 auto createForwardEdge = [&](NodeType &Src, NodeType &Dst) { 173 if (!ForwardEdgeCreated) { 174 createMemoryEdge(Src, Dst); 175 ++TotalMemoryEdges; 176 } 177 ForwardEdgeCreated = true; 178 }; 179 180 auto createBackwardEdge = [&](NodeType &Src, NodeType &Dst) { 181 if (!BackwardEdgeCreated) { 182 createMemoryEdge(Dst, Src); 183 ++TotalMemoryEdges; 184 } 185 BackwardEdgeCreated = true; 186 }; 187 188 if (D->isConfused()) 189 createConfusedEdges(**SrcIt, **DstIt); 190 else if (D->isOrdered() && !D->isLoopIndependent()) { 191 bool ReversedEdge = false; 192 for (unsigned Level = 1; Level <= D->getLevels(); ++Level) { 193 if (D->getDirection(Level) == Dependence::DVEntry::EQ) 194 continue; 195 else if (D->getDirection(Level) == Dependence::DVEntry::GT) { 196 createBackwardEdge(**SrcIt, **DstIt); 197 ReversedEdge = true; 198 ++TotalEdgeReversals; 199 break; 200 } else if (D->getDirection(Level) == Dependence::DVEntry::LT) 201 break; 202 else { 203 createConfusedEdges(**SrcIt, **DstIt); 204 break; 205 } 206 } 207 if (!ReversedEdge) 208 createForwardEdge(**SrcIt, **DstIt); 209 } else 210 createForwardEdge(**SrcIt, **DstIt); 211 212 // Avoid creating duplicate edges. 213 if (ForwardEdgeCreated && BackwardEdgeCreated) 214 break; 215 } 216 217 // If we've created edges in both directions, there is no more 218 // unique edge that we can create between these two nodes, so we 219 // can exit early. 220 if (ForwardEdgeCreated && BackwardEdgeCreated) 221 break; 222 } 223 } 224 } 225 } 226 227 template class llvm::AbstractDependenceGraphBuilder<DataDependenceGraph>; 228 template class llvm::DependenceGraphInfo<DDGNode>; 229