| //===- DependenceGraphBuilder.cpp ------------------------------------------==// |
| // |
| // 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 implements common steps of the build algorithm for construction |
| // of dependence graphs such as DDG and PDG. |
| //===----------------------------------------------------------------------===// |
| |
| #include "llvm/Analysis/DependenceGraphBuilder.h" |
| #include "llvm/ADT/SCCIterator.h" |
| #include "llvm/ADT/Statistic.h" |
| #include "llvm/Analysis/DDG.h" |
| |
| using namespace llvm; |
| |
| #define DEBUG_TYPE "dgb" |
| |
| STATISTIC(TotalGraphs, "Number of dependence graphs created."); |
| STATISTIC(TotalDefUseEdges, "Number of def-use edges created."); |
| STATISTIC(TotalMemoryEdges, "Number of memory dependence edges created."); |
| STATISTIC(TotalFineGrainedNodes, "Number of fine-grained nodes created."); |
| STATISTIC(TotalConfusedEdges, |
| "Number of confused memory dependencies between two nodes."); |
| STATISTIC(TotalEdgeReversals, |
| "Number of times the source and sink of dependence was reversed to " |
| "expose cycles in the graph."); |
| |
| using InstructionListType = SmallVector<Instruction *, 2>; |
| |
| //===--------------------------------------------------------------------===// |
| // AbstractDependenceGraphBuilder implementation |
| //===--------------------------------------------------------------------===// |
| |
| template <class G> |
| void AbstractDependenceGraphBuilder<G>::createFineGrainedNodes() { |
| ++TotalGraphs; |
| assert(IMap.empty() && "Expected empty instruction map at start"); |
| for (BasicBlock *BB : BBList) |
| for (Instruction &I : *BB) { |
| auto &NewNode = createFineGrainedNode(I); |
| IMap.insert(std::make_pair(&I, &NewNode)); |
| ++TotalFineGrainedNodes; |
| } |
| } |
| |
| template <class G> |
| void AbstractDependenceGraphBuilder<G>::createAndConnectRootNode() { |
| // Create a root node that connects to every connected component of the graph. |
| // This is done to allow graph iterators to visit all the disjoint components |
| // of the graph, in a single walk. |
| // |
| // This algorithm works by going through each node of the graph and for each |
| // node N, do a DFS starting from N. A rooted edge is established between the |
| // root node and N (if N is not yet visited). All the nodes reachable from N |
| // are marked as visited and are skipped in the DFS of subsequent nodes. |
| // |
| // Note: This algorithm tries to limit the number of edges out of the root |
| // node to some extent, but there may be redundant edges created depending on |
| // the iteration order. For example for a graph {A -> B}, an edge from the |
| // root node is added to both nodes if B is visited before A. While it does |
| // not result in minimal number of edges, this approach saves compile-time |
| // while keeping the number of edges in check. |
| auto &RootNode = createRootNode(); |
| df_iterator_default_set<const NodeType *, 4> Visited; |
| for (auto *N : Graph) { |
| if (*N == RootNode) |
| continue; |
| for (auto I : depth_first_ext(N, Visited)) |
| if (I == N) |
| createRootedEdge(RootNode, *N); |
| } |
| } |
| |
| template <class G> void AbstractDependenceGraphBuilder<G>::createDefUseEdges() { |
| for (NodeType *N : Graph) { |
| InstructionListType SrcIList; |
| N->collectInstructions([](const Instruction *I) { return true; }, SrcIList); |
| |
| // Use a set to mark the targets that we link to N, so we don't add |
| // duplicate def-use edges when more than one instruction in a target node |
| // use results of instructions that are contained in N. |
| SmallPtrSet<NodeType *, 4> VisitedTargets; |
| |
| for (Instruction *II : SrcIList) { |
| for (User *U : II->users()) { |
| Instruction *UI = dyn_cast<Instruction>(U); |
| if (!UI) |
| continue; |
| NodeType *DstNode = nullptr; |
| if (IMap.find(UI) != IMap.end()) |
| DstNode = IMap.find(UI)->second; |
| |
| // In the case of loops, the scope of the subgraph is all the |
| // basic blocks (and instructions within them) belonging to the loop. We |
| // simply ignore all the edges coming from (or going into) instructions |
| // or basic blocks outside of this range. |
| if (!DstNode) { |
| LLVM_DEBUG( |
| dbgs() |
| << "skipped def-use edge since the sink" << *UI |
| << " is outside the range of instructions being considered.\n"); |
| continue; |
| } |
| |
| // Self dependencies are ignored because they are redundant and |
| // uninteresting. |
| if (DstNode == N) { |
| LLVM_DEBUG(dbgs() |
| << "skipped def-use edge since the sink and the source (" |
| << N << ") are the same.\n"); |
| continue; |
| } |
| |
| if (VisitedTargets.insert(DstNode).second) { |
| createDefUseEdge(*N, *DstNode); |
| ++TotalDefUseEdges; |
| } |
| } |
| } |
| } |
| } |
| |
| template <class G> |
| void AbstractDependenceGraphBuilder<G>::createMemoryDependencyEdges() { |
| using DGIterator = typename G::iterator; |
| auto isMemoryAccess = [](const Instruction *I) { |
| return I->mayReadOrWriteMemory(); |
| }; |
| for (DGIterator SrcIt = Graph.begin(), E = Graph.end(); SrcIt != E; ++SrcIt) { |
| InstructionListType SrcIList; |
| (*SrcIt)->collectInstructions(isMemoryAccess, SrcIList); |
| if (SrcIList.empty()) |
| continue; |
| |
| for (DGIterator DstIt = SrcIt; DstIt != E; ++DstIt) { |
| if (**SrcIt == **DstIt) |
| continue; |
| InstructionListType DstIList; |
| (*DstIt)->collectInstructions(isMemoryAccess, DstIList); |
| if (DstIList.empty()) |
| continue; |
| bool ForwardEdgeCreated = false; |
| bool BackwardEdgeCreated = false; |
| for (Instruction *ISrc : SrcIList) { |
| for (Instruction *IDst : DstIList) { |
| auto D = DI.depends(ISrc, IDst, true); |
| if (!D) |
| continue; |
| |
| // If we have a dependence with its left-most non-'=' direction |
| // being '>' we need to reverse the direction of the edge, because |
| // the source of the dependence cannot occur after the sink. For |
| // confused dependencies, we will create edges in both directions to |
| // represent the possibility of a cycle. |
| |
| auto createConfusedEdges = [&](NodeType &Src, NodeType &Dst) { |
| if (!ForwardEdgeCreated) { |
| createMemoryEdge(Src, Dst); |
| ++TotalMemoryEdges; |
| } |
| if (!BackwardEdgeCreated) { |
| createMemoryEdge(Dst, Src); |
| ++TotalMemoryEdges; |
| } |
| ForwardEdgeCreated = BackwardEdgeCreated = true; |
| ++TotalConfusedEdges; |
| }; |
| |
| auto createForwardEdge = [&](NodeType &Src, NodeType &Dst) { |
| if (!ForwardEdgeCreated) { |
| createMemoryEdge(Src, Dst); |
| ++TotalMemoryEdges; |
| } |
| ForwardEdgeCreated = true; |
| }; |
| |
| auto createBackwardEdge = [&](NodeType &Src, NodeType &Dst) { |
| if (!BackwardEdgeCreated) { |
| createMemoryEdge(Dst, Src); |
| ++TotalMemoryEdges; |
| } |
| BackwardEdgeCreated = true; |
| }; |
| |
| if (D->isConfused()) |
| createConfusedEdges(**SrcIt, **DstIt); |
| else if (D->isOrdered() && !D->isLoopIndependent()) { |
| bool ReversedEdge = false; |
| for (unsigned Level = 1; Level <= D->getLevels(); ++Level) { |
| if (D->getDirection(Level) == Dependence::DVEntry::EQ) |
| continue; |
| else if (D->getDirection(Level) == Dependence::DVEntry::GT) { |
| createBackwardEdge(**SrcIt, **DstIt); |
| ReversedEdge = true; |
| ++TotalEdgeReversals; |
| break; |
| } else if (D->getDirection(Level) == Dependence::DVEntry::LT) |
| break; |
| else { |
| createConfusedEdges(**SrcIt, **DstIt); |
| break; |
| } |
| } |
| if (!ReversedEdge) |
| createForwardEdge(**SrcIt, **DstIt); |
| } else |
| createForwardEdge(**SrcIt, **DstIt); |
| |
| // Avoid creating duplicate edges. |
| if (ForwardEdgeCreated && BackwardEdgeCreated) |
| break; |
| } |
| |
| // If we've created edges in both directions, there is no more |
| // unique edge that we can create between these two nodes, so we |
| // can exit early. |
| if (ForwardEdgeCreated && BackwardEdgeCreated) |
| break; |
| } |
| } |
| } |
| } |
| |
| template class llvm::AbstractDependenceGraphBuilder<DataDependenceGraph>; |
| template class llvm::DependenceGraphInfo<DDGNode>; |