LLVM  10.0.0svn
DependenceGraphBuilder.cpp
Go to the documentation of this file.
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 
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 
32 
33 //===--------------------------------------------------------------------===//
34 // AbstractDependenceGraphBuilder implementation
35 //===--------------------------------------------------------------------===//
36 
37 template <class G>
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>
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();
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 
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()) {
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>
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 
This builds on the llvm/ADT/GraphTraits.h file to find the strongly connected components (SCCs) of a ...
This class represents lattice values for constants.
Definition: AllocatorList.h:23
STATISTIC(NumFunctions, "Total number of functions")
void createFineGrainedNodes()
Create fine grained nodes.
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:370
iterator_range< df_ext_iterator< T, SetTy > > depth_first_ext(const T &G, SetTy &S)
void createDefUseEdges()
Analyze the def-use chains and create edges from the nodes containing definitions to the nodes contai...
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
Encapsulate some common data and functionality needed for different variations of data dependence gra...
Definition: DDG.h:203
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
iterator_range< user_iterator > users()
Definition: Value.h:420
void createMemoryDependencyEdges()
Analyze data dependencies that exist between memory loads or stores, in the graph nodes and create ed...
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:332
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
#define LLVM_DEBUG(X)
Definition: Debug.h:122
void createAndConnectRootNode()
Create a root node and add edges such that each node in the graph is reachable from the root...