lib/Analysis/DependenceGraphBuilder.cpp

   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>;