LLVM  11.0.0git
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 
14 #include "llvm/ADT/SCCIterator.h"
15 #include "llvm/ADT/Statistic.h"
16 #include "llvm/Analysis/DDG.h"
17 
18 using namespace llvm;
19 
20 #define DEBUG_TYPE "dgb"
21 
22 STATISTIC(TotalGraphs, "Number of dependence graphs created.");
23 STATISTIC(TotalDefUseEdges, "Number of def-use edges created.");
24 STATISTIC(TotalMemoryEdges, "Number of memory dependence edges created.");
25 STATISTIC(TotalFineGrainedNodes, "Number of fine-grained nodes created.");
26 STATISTIC(TotalPiBlockNodes, "Number of pi-block nodes created.");
27 STATISTIC(TotalConfusedEdges,
28  "Number of confused memory dependencies between two nodes.");
29 STATISTIC(TotalEdgeReversals,
30  "Number of times the source and sink of dependence was reversed to "
31  "expose cycles in the graph.");
32 
34 
35 //===--------------------------------------------------------------------===//
36 // AbstractDependenceGraphBuilder implementation
37 //===--------------------------------------------------------------------===//
38 
39 template <class G>
41  // The BBList is expected to be in program order.
42  size_t NextOrdinal = 1;
43  for (auto *BB : BBList)
44  for (auto &I : *BB)
45  InstOrdinalMap.insert(std::make_pair(&I, NextOrdinal++));
46 }
47 
48 template <class G>
50  ++TotalGraphs;
51  assert(IMap.empty() && "Expected empty instruction map at start");
52  for (BasicBlock *BB : BBList)
53  for (Instruction &I : *BB) {
54  auto &NewNode = createFineGrainedNode(I);
55  IMap.insert(std::make_pair(&I, &NewNode));
56  NodeOrdinalMap.insert(std::make_pair(&NewNode, getOrdinal(I)));
57  ++TotalFineGrainedNodes;
58  }
59 }
60 
61 template <class G>
63  // Create a root node that connects to every connected component of the graph.
64  // This is done to allow graph iterators to visit all the disjoint components
65  // of the graph, in a single walk.
66  //
67  // This algorithm works by going through each node of the graph and for each
68  // node N, do a DFS starting from N. A rooted edge is established between the
69  // root node and N (if N is not yet visited). All the nodes reachable from N
70  // are marked as visited and are skipped in the DFS of subsequent nodes.
71  //
72  // Note: This algorithm tries to limit the number of edges out of the root
73  // node to some extent, but there may be redundant edges created depending on
74  // the iteration order. For example for a graph {A -> B}, an edge from the
75  // root node is added to both nodes if B is visited before A. While it does
76  // not result in minimal number of edges, this approach saves compile-time
77  // while keeping the number of edges in check.
78  auto &RootNode = createRootNode();
80  for (auto *N : Graph) {
81  if (*N == RootNode)
82  continue;
83  for (auto I : depth_first_ext(N, Visited))
84  if (I == N)
85  createRootedEdge(RootNode, *N);
86  }
87 }
88 
90  if (!shouldCreatePiBlocks())
91  return;
92 
93  LLVM_DEBUG(dbgs() << "==== Start of Creation of Pi-Blocks ===\n");
94 
95  // The overall algorithm is as follows:
96  // 1. Identify SCCs and for each SCC create a pi-block node containing all
97  // the nodes in that SCC.
98  // 2. Identify incoming edges incident to the nodes inside of the SCC and
99  // reconnect them to the pi-block node.
100  // 3. Identify outgoing edges from the nodes inside of the SCC to nodes
101  // outside of it and reconnect them so that the edges are coming out of the
102  // SCC node instead.
103 
104  // Adding nodes as we iterate through the SCCs cause the SCC
105  // iterators to get invalidated. To prevent this invalidation, we first
106  // collect a list of nodes that are part of an SCC, and then iterate over
107  // those lists to create the pi-block nodes. Each element of the list is a
108  // list of nodes in an SCC. Note: trivial SCCs containing a single node are
109  // ignored.
110  SmallVector<NodeListType, 4> ListOfSCCs;
111  for (auto &SCC : make_range(scc_begin(&Graph), scc_end(&Graph))) {
112  if (SCC.size() > 1)
113  ListOfSCCs.emplace_back(SCC.begin(), SCC.end());
114  }
115 
116  for (NodeListType &NL : ListOfSCCs) {
117  LLVM_DEBUG(dbgs() << "Creating pi-block node with " << NL.size()
118  << " nodes in it.\n");
119 
120  // SCC iterator may put the nodes in an order that's different from the
121  // program order. To preserve original program order, we sort the list of
122  // nodes based on ordinal numbers computed earlier.
123  llvm::sort(NL, [&](NodeType *LHS, NodeType *RHS) {
124  return getOrdinal(*LHS) < getOrdinal(*RHS);
125  });
126 
127  NodeType &PiNode = createPiBlock(NL);
128  ++TotalPiBlockNodes;
129 
130  // Build a set to speed up the lookup for edges whose targets
131  // are inside the SCC.
132  SmallPtrSet<NodeType *, 4> NodesInSCC(NL.begin(), NL.end());
133 
134  // We have the set of nodes in the SCC. We go through the set of nodes
135  // that are outside of the SCC and look for edges that cross the two sets.
136  for (NodeType *N : Graph) {
137 
138  // Skip the SCC node and all the nodes inside of it.
139  if (*N == PiNode || NodesInSCC.count(N))
140  continue;
141 
142  for (NodeType *SCCNode : NL) {
143 
144  enum Direction {
145  Incoming, // Incoming edges to the SCC
146  Outgoing, // Edges going ot of the SCC
147  DirectionCount // To make the enum usable as an array index.
148  };
149 
150  // Use these flags to help us avoid creating redundant edges. If there
151  // are more than one edges from an outside node to inside nodes, we only
152  // keep one edge from that node to the pi-block node. Similarly, if
153  // there are more than one edges from inside nodes to an outside node,
154  // we only keep one edge from the pi-block node to the outside node.
155  // There is a flag defined for each direction (incoming vs outgoing) and
156  // for each type of edge supported, using a two-dimensional boolean
157  // array.
158  using EdgeKind = typename EdgeType::EdgeKind;
159  EnumeratedArray<bool, EdgeKind> EdgeAlreadyCreated[DirectionCount]{
160  false, false};
161 
162  auto createEdgeOfKind = [this](NodeType &Src, NodeType &Dst,
163  const EdgeKind K) {
164  switch (K) {
165  case EdgeKind::RegisterDefUse:
166  createDefUseEdge(Src, Dst);
167  break;
168  case EdgeKind::MemoryDependence:
169  createMemoryEdge(Src, Dst);
170  break;
171  case EdgeKind::Rooted:
172  createRootedEdge(Src, Dst);
173  break;
174  default:
175  llvm_unreachable("Unsupported type of edge.");
176  }
177  };
178 
179  auto reconnectEdges = [&](NodeType *Src, NodeType *Dst, NodeType *New,
180  const Direction Dir) {
181  if (!Src->hasEdgeTo(*Dst))
182  return;
183  LLVM_DEBUG(dbgs()
184  << "reconnecting("
185  << (Dir == Direction::Incoming ? "incoming)" : "outgoing)")
186  << ":\nSrc:" << *Src << "\nDst:" << *Dst
187  << "\nNew:" << *New << "\n");
188  assert((Dir == Direction::Incoming || Dir == Direction::Outgoing) &&
189  "Invalid direction.");
190 
192  Src->findEdgesTo(*Dst, EL);
193  for (EdgeType *OldEdge : EL) {
194  EdgeKind Kind = OldEdge->getKind();
195  if (!EdgeAlreadyCreated[Dir][Kind]) {
196  if (Dir == Direction::Incoming) {
197  createEdgeOfKind(*Src, *New, Kind);
198  LLVM_DEBUG(dbgs() << "created edge from Src to New.\n");
199  } else if (Dir == Direction::Outgoing) {
200  createEdgeOfKind(*New, *Dst, Kind);
201  LLVM_DEBUG(dbgs() << "created edge from New to Dst.\n");
202  }
203  EdgeAlreadyCreated[Dir][Kind] = true;
204  }
205  Src->removeEdge(*OldEdge);
206  destroyEdge(*OldEdge);
207  LLVM_DEBUG(dbgs() << "removed old edge between Src and Dst.\n\n");
208  }
209  };
210 
211  // Process incoming edges incident to the pi-block node.
212  reconnectEdges(N, SCCNode, &PiNode, Direction::Incoming);
213 
214  // Process edges that are coming out of the pi-block node.
215  reconnectEdges(SCCNode, N, &PiNode, Direction::Outgoing);
216  }
217  }
218  }
219 
220  // Ordinal maps are no longer needed.
221  InstOrdinalMap.clear();
222  NodeOrdinalMap.clear();
223 
224  LLVM_DEBUG(dbgs() << "==== End of Creation of Pi-Blocks ===\n");
225 }
226 
228  for (NodeType *N : Graph) {
229  InstructionListType SrcIList;
230  N->collectInstructions([](const Instruction *I) { return true; }, SrcIList);
231 
232  // Use a set to mark the targets that we link to N, so we don't add
233  // duplicate def-use edges when more than one instruction in a target node
234  // use results of instructions that are contained in N.
235  SmallPtrSet<NodeType *, 4> VisitedTargets;
236 
237  for (Instruction *II : SrcIList) {
238  for (User *U : II->users()) {
239  Instruction *UI = dyn_cast<Instruction>(U);
240  if (!UI)
241  continue;
242  NodeType *DstNode = nullptr;
243  if (IMap.find(UI) != IMap.end())
244  DstNode = IMap.find(UI)->second;
245 
246  // In the case of loops, the scope of the subgraph is all the
247  // basic blocks (and instructions within them) belonging to the loop. We
248  // simply ignore all the edges coming from (or going into) instructions
249  // or basic blocks outside of this range.
250  if (!DstNode) {
251  LLVM_DEBUG(
252  dbgs()
253  << "skipped def-use edge since the sink" << *UI
254  << " is outside the range of instructions being considered.\n");
255  continue;
256  }
257 
258  // Self dependencies are ignored because they are redundant and
259  // uninteresting.
260  if (DstNode == N) {
261  LLVM_DEBUG(dbgs()
262  << "skipped def-use edge since the sink and the source ("
263  << N << ") are the same.\n");
264  continue;
265  }
266 
267  if (VisitedTargets.insert(DstNode).second) {
268  createDefUseEdge(*N, *DstNode);
269  ++TotalDefUseEdges;
270  }
271  }
272  }
273  }
274 }
275 
276 template <class G>
278  using DGIterator = typename G::iterator;
279  auto isMemoryAccess = [](const Instruction *I) {
280  return I->mayReadOrWriteMemory();
281  };
282  for (DGIterator SrcIt = Graph.begin(), E = Graph.end(); SrcIt != E; ++SrcIt) {
283  InstructionListType SrcIList;
284  (*SrcIt)->collectInstructions(isMemoryAccess, SrcIList);
285  if (SrcIList.empty())
286  continue;
287 
288  for (DGIterator DstIt = SrcIt; DstIt != E; ++DstIt) {
289  if (**SrcIt == **DstIt)
290  continue;
291  InstructionListType DstIList;
292  (*DstIt)->collectInstructions(isMemoryAccess, DstIList);
293  if (DstIList.empty())
294  continue;
295  bool ForwardEdgeCreated = false;
296  bool BackwardEdgeCreated = false;
297  for (Instruction *ISrc : SrcIList) {
298  for (Instruction *IDst : DstIList) {
299  auto D = DI.depends(ISrc, IDst, true);
300  if (!D)
301  continue;
302 
303  // If we have a dependence with its left-most non-'=' direction
304  // being '>' we need to reverse the direction of the edge, because
305  // the source of the dependence cannot occur after the sink. For
306  // confused dependencies, we will create edges in both directions to
307  // represent the possibility of a cycle.
308 
309  auto createConfusedEdges = [&](NodeType &Src, NodeType &Dst) {
310  if (!ForwardEdgeCreated) {
311  createMemoryEdge(Src, Dst);
312  ++TotalMemoryEdges;
313  }
314  if (!BackwardEdgeCreated) {
315  createMemoryEdge(Dst, Src);
316  ++TotalMemoryEdges;
317  }
318  ForwardEdgeCreated = BackwardEdgeCreated = true;
319  ++TotalConfusedEdges;
320  };
321 
322  auto createForwardEdge = [&](NodeType &Src, NodeType &Dst) {
323  if (!ForwardEdgeCreated) {
324  createMemoryEdge(Src, Dst);
325  ++TotalMemoryEdges;
326  }
327  ForwardEdgeCreated = true;
328  };
329 
330  auto createBackwardEdge = [&](NodeType &Src, NodeType &Dst) {
331  if (!BackwardEdgeCreated) {
332  createMemoryEdge(Dst, Src);
333  ++TotalMemoryEdges;
334  }
335  BackwardEdgeCreated = true;
336  };
337 
338  if (D->isConfused())
339  createConfusedEdges(**SrcIt, **DstIt);
340  else if (D->isOrdered() && !D->isLoopIndependent()) {
341  bool ReversedEdge = false;
342  for (unsigned Level = 1; Level <= D->getLevels(); ++Level) {
343  if (D->getDirection(Level) == Dependence::DVEntry::EQ)
344  continue;
345  else if (D->getDirection(Level) == Dependence::DVEntry::GT) {
346  createBackwardEdge(**SrcIt, **DstIt);
347  ReversedEdge = true;
348  ++TotalEdgeReversals;
349  break;
350  } else if (D->getDirection(Level) == Dependence::DVEntry::LT)
351  break;
352  else {
353  createConfusedEdges(**SrcIt, **DstIt);
354  break;
355  }
356  }
357  if (!ReversedEdge)
358  createForwardEdge(**SrcIt, **DstIt);
359  } else
360  createForwardEdge(**SrcIt, **DstIt);
361 
362  // Avoid creating duplicate edges.
363  if (ForwardEdgeCreated && BackwardEdgeCreated)
364  break;
365  }
366 
367  // If we've created edges in both directions, there is no more
368  // unique edge that we can create between these two nodes, so we
369  // can exit early.
370  if (ForwardEdgeCreated && BackwardEdgeCreated)
371  break;
372  }
373  }
374  }
375 }
376 
378  if (!shouldSimplify())
379  return;
380  LLVM_DEBUG(dbgs() << "==== Start of Graph Simplification ===\n");
381 
382  // This algorithm works by first collecting a set of candidate nodes that have
383  // an out-degree of one (in terms of def-use edges), and then ignoring those
384  // whose targets have an in-degree more than one. Each node in the resulting
385  // set can then be merged with its corresponding target and put back into the
386  // worklist until no further merge candidates are available.
387  SmallPtrSet<NodeType *, 32> CandidateSourceNodes;
388 
389  // A mapping between nodes and their in-degree. To save space, this map
390  // only contains nodes that are targets of nodes in the CandidateSourceNodes.
391  DenseMap<NodeType *, unsigned> TargetInDegreeMap;
392 
393  for (NodeType *N : Graph) {
394  if (N->getEdges().size() != 1)
395  continue;
396  EdgeType &Edge = N->back();
397  if (!Edge.isDefUse())
398  continue;
399  CandidateSourceNodes.insert(N);
400 
401  // Insert an element into the in-degree map and initialize to zero. The
402  // count will get updated in the next step.
403  TargetInDegreeMap.insert({&Edge.getTargetNode(), 0});
404  }
405 
406  LLVM_DEBUG({
407  dbgs() << "Size of candidate src node list:" << CandidateSourceNodes.size()
408  << "\nNode with single outgoing def-use edge:\n";
409  for (NodeType *N : CandidateSourceNodes) {
410  dbgs() << N << "\n";
411  }
412  });
413 
414  for (NodeType *N : Graph) {
415  for (EdgeType *E : *N) {
416  NodeType *Tgt = &E->getTargetNode();
417  auto TgtIT = TargetInDegreeMap.find(Tgt);
418  if (TgtIT != TargetInDegreeMap.end())
419  ++(TgtIT->second);
420  }
421  }
422 
423  LLVM_DEBUG({
424  dbgs() << "Size of target in-degree map:" << TargetInDegreeMap.size()
425  << "\nContent of in-degree map:\n";
426  for (auto &I : TargetInDegreeMap) {
427  dbgs() << I.first << " --> " << I.second << "\n";
428  }
429  });
430 
431  SmallVector<NodeType *, 32> Worklist(CandidateSourceNodes.begin(),
432  CandidateSourceNodes.end());
433  while (!Worklist.empty()) {
434  NodeType &Src = *Worklist.pop_back_val();
435  // As nodes get merged, we need to skip any node that has been removed from
436  // the candidate set (see below).
437  if (CandidateSourceNodes.find(&Src) == CandidateSourceNodes.end())
438  continue;
439  CandidateSourceNodes.erase(&Src);
440 
441  assert(Src.getEdges().size() == 1 &&
442  "Expected a single edge from the candidate src node.");
443  NodeType &Tgt = Src.back().getTargetNode();
444  assert(TargetInDegreeMap.find(&Tgt) != TargetInDegreeMap.end() &&
445  "Expected target to be in the in-degree map.");
446 
447  if (TargetInDegreeMap[&Tgt] != 1)
448  continue;
449 
450  if (!areNodesMergeable(Src, Tgt))
451  continue;
452 
453  // Do not merge if there is also an edge from target to src (immediate
454  // cycle).
455  if (Tgt.hasEdgeTo(Src))
456  continue;
457 
458  LLVM_DEBUG(dbgs() << "Merging:" << Src << "\nWith:" << Tgt << "\n");
459 
460  mergeNodes(Src, Tgt);
461 
462  // If the target node is in the candidate set itself, we need to put the
463  // src node back into the worklist again so it gives the target a chance
464  // to get merged into it. For example if we have:
465  // {(a)->(b), (b)->(c), (c)->(d), ...} and the worklist is initially {b, a},
466  // then after merging (a) and (b) together, we need to put (a,b) back in
467  // the worklist so that (c) can get merged in as well resulting in
468  // {(a,b,c) -> d}
469  // We also need to remove the old target (b), from the worklist. We first
470  // remove it from the candidate set here, and skip any item from the
471  // worklist that is not in the set.
472  if (CandidateSourceNodes.find(&Tgt) != CandidateSourceNodes.end()) {
473  Worklist.push_back(&Src);
474  CandidateSourceNodes.insert(&Src);
475  CandidateSourceNodes.erase(&Tgt);
476  LLVM_DEBUG(dbgs() << "Putting " << &Src << " back in the worklist.\n");
477  }
478  }
479  LLVM_DEBUG(dbgs() << "=== End of Graph Simplification ===\n");
480 }
481 
482 template <class G>
484 
485  // If we don't create pi-blocks, then we may not have a DAG.
486  if (!shouldCreatePiBlocks())
487  return;
488 
489  SmallVector<NodeType *, 64> NodesInPO;
490  using NodeKind = typename NodeType::NodeKind;
491  for (NodeType *N : post_order(&Graph)) {
492  if (N->getKind() == NodeKind::PiBlock) {
493  // Put members of the pi-block right after the pi-block itself, for
494  // convenience.
495  const NodeListType &PiBlockMembers = getNodesInPiBlock(*N);
496  NodesInPO.insert(NodesInPO.end(), PiBlockMembers.begin(),
497  PiBlockMembers.end());
498  }
499  NodesInPO.push_back(N);
500  }
501 
502  size_t OldSize = Graph.Nodes.size();
503  Graph.Nodes.clear();
504  for (NodeType *N : reverse(NodesInPO))
505  Graph.Nodes.push_back(N);
506  if (Graph.Nodes.size() != OldSize)
507  assert(false &&
508  "Expected the number of nodes to stay the same after the sort");
509 }
510 
This builds on the llvm/ADT/GraphTraits.h file to find the strongly connected components (SCCs) of a ...
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:687
LLVM_NODISCARD std::enable_if_t< !is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type > dyn_cast(const Y &Val)
Definition: Casting.h:328
This class represents lattice values for constants.
Definition: AllocatorList.h:23
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:69
STATISTIC(NumFunctions, "Total number of functions")
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:207
iterator find(ConstPtrType Ptr) const
Definition: SmallPtrSet.h:378
Direction
An enum for the direction of the loop.
Definition: LoopInfo.h:684
void createFineGrainedNodes()
Create fine grained nodes.
scc_iterator< T > scc_begin(const T &G)
Construct the begin iterator for a deduced graph type T.
Definition: SCCIterator.h:228
void sortNodesTopologically()
Topologically sort the graph nodes.
void simplify()
Go through all the nodes in the graph and collapse any two nodes &#39;a&#39; and &#39;b&#39; if all of the following ...
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
scc_iterator< T > scc_end(const T &G)
Construct the end iterator for a deduced graph type T.
Definition: SCCIterator.h:233
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:364
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...
iterator_range< po_iterator< T > > post_order(const T &G)
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1425
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
void computeInstructionOrdinals()
Compute ordinal numbers for each instruction and store them in a map for future look up...
size_type size() const
Definition: SmallPtrSet.h:92
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
void createPiBlocks()
Apply graph abstraction to groups of nodes that belong to a strongly connected component of the graph...
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:439
bool erase(PtrType Ptr)
erase - If the set contains the specified pointer, remove it and return true, otherwise return false...
Definition: SmallPtrSet.h:371
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:883
Encapsulate some common data and functionality needed for different variations of data dependence gra...
Definition: DDG.h:265
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:420
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:418
iterator insert(iterator I, T &&Elt)
Definition: SmallVector.h:513
void createMemoryDependencyEdges()
Analyze data dependencies that exist between memory loads or stores, in the graph nodes and create ed...
iterator begin() const
Definition: SmallPtrSet.h:392
#define I(x, y, z)
Definition: MD5.cpp:59
#define N
iterator end() const
Definition: SmallPtrSet.h:397
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:341
#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...
Level
Definition: Debugify.cpp:33