summaryrefslogtreecommitdiff
path: root/lib/Analysis/DependenceGraphBuilder.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'lib/Analysis/DependenceGraphBuilder.cpp')
-rw-r--r--lib/Analysis/DependenceGraphBuilder.cpp228
1 files changed, 228 insertions, 0 deletions
diff --git a/lib/Analysis/DependenceGraphBuilder.cpp b/lib/Analysis/DependenceGraphBuilder.cpp
new file mode 100644
index 000000000000..ed1d8351b2f0
--- /dev/null
+++ b/lib/Analysis/DependenceGraphBuilder.cpp
@@ -0,0 +1,228 @@
+//===- 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>;
generated by cgit v1.2.3 (git 2.25.1) at 2024-09-26 05:00:57 +0000