LLVM  13.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 
15 #include "llvm/ADT/SCCIterator.h"
16 #include "llvm/ADT/Statistic.h"
17 #include "llvm/Analysis/DDG.h"
18 
19 using namespace llvm;
20 
21 #define DEBUG_TYPE "dgb"
22 
23 STATISTIC(TotalGraphs, "Number of dependence graphs created.");
24 STATISTIC(TotalDefUseEdges, "Number of def-use edges created.");
25 STATISTIC(TotalMemoryEdges, "Number of memory dependence edges created.");
26 STATISTIC(TotalFineGrainedNodes, "Number of fine-grained nodes created.");
27 STATISTIC(TotalPiBlockNodes, "Number of pi-block nodes created.");
28 STATISTIC(TotalConfusedEdges,
29  "Number of confused memory dependencies between two nodes.");
30 STATISTIC(TotalEdgeReversals,
31  "Number of times the source and sink of dependence was reversed to "
32  "expose cycles in the graph.");
33 
35 
36 //===--------------------------------------------------------------------===//
37 // AbstractDependenceGraphBuilder implementation
38 //===--------------------------------------------------------------------===//
39 
40 template <class G>
42  // The BBList is expected to be in program order.
43  size_t NextOrdinal = 1;
44  for (auto *BB : BBList)
45  for (auto &I : *BB)
46  InstOrdinalMap.insert(std::make_pair(&I, NextOrdinal++));
47 }
48 
49 template <class G>
51  ++TotalGraphs;
52  assert(IMap.empty() && "Expected empty instruction map at start");
53  for (BasicBlock *BB : BBList)
54  for (Instruction &I : *BB) {
55  auto &NewNode = createFineGrainedNode(I);
56  IMap.insert(std::make_pair(&I, &NewNode));
57  NodeOrdinalMap.insert(std::make_pair(&NewNode, getOrdinal(I)));
58  ++TotalFineGrainedNodes;
59  }
60 }
61 
62 template <class G>
64  // Create a root node that connects to every connected component of the graph.
65  // This is done to allow graph iterators to visit all the disjoint components
66  // of the graph, in a single walk.
67  //
68  // This algorithm works by going through each node of the graph and for each
69  // node N, do a DFS starting from N. A rooted edge is established between the
70  // root node and N (if N is not yet visited). All the nodes reachable from N
71  // are marked as visited and are skipped in the DFS of subsequent nodes.
72  //
73  // Note: This algorithm tries to limit the number of edges out of the root
74  // node to some extent, but there may be redundant edges created depending on
75  // the iteration order. For example for a graph {A -> B}, an edge from the
76  // root node is added to both nodes if B is visited before A. While it does
77  // not result in minimal number of edges, this approach saves compile-time
78  // while keeping the number of edges in check.
79  auto &RootNode = createRootNode();
81  for (auto *N : Graph) {
82  if (*N == RootNode)
83  continue;
84  for (auto I : depth_first_ext(N, Visited))
85  if (I == N)
86  createRootedEdge(RootNode, *N);
87  }
88 }
89 
91  if (!shouldCreatePiBlocks())
92  return;
93 
94  LLVM_DEBUG(dbgs() << "==== Start of Creation of Pi-Blocks ===\n");
95 
96  // The overall algorithm is as follows:
97  // 1. Identify SCCs and for each SCC create a pi-block node containing all
98  // the nodes in that SCC.
99  // 2. Identify incoming edges incident to the nodes inside of the SCC and
100  // reconnect them to the pi-block node.
101  // 3. Identify outgoing edges from the nodes inside of the SCC to nodes
102  // outside of it and reconnect them so that the edges are coming out of the
103  // SCC node instead.
104 
105  // Adding nodes as we iterate through the SCCs cause the SCC
106  // iterators to get invalidated. To prevent this invalidation, we first
107  // collect a list of nodes that are part of an SCC, and then iterate over
108  // those lists to create the pi-block nodes. Each element of the list is a
109  // list of nodes in an SCC. Note: trivial SCCs containing a single node are
110  // ignored.
111  SmallVector<NodeListType, 4> ListOfSCCs;
112  for (auto &SCC : make_range(scc_begin(&Graph), scc_end(&Graph))) {
113  if (SCC.size() > 1)
114  ListOfSCCs.emplace_back(SCC.begin(), SCC.end());
115  }
116 
117  for (NodeListType &NL : ListOfSCCs) {
118  LLVM_DEBUG(dbgs() << "Creating pi-block node with " << NL.size()
119  << " nodes in it.\n");
120 
121  // SCC iterator may put the nodes in an order that's different from the
122  // program order. To preserve original program order, we sort the list of
123  // nodes based on ordinal numbers computed earlier.
124  llvm::sort(NL, [&](NodeType *LHS, NodeType *RHS) {
125  return getOrdinal(*LHS) < getOrdinal(*RHS);
126  });
127 
128  NodeType &PiNode = createPiBlock(NL);
129  ++TotalPiBlockNodes;
130 
131  // Build a set to speed up the lookup for edges whose targets
132  // are inside the SCC.
133  SmallPtrSet<NodeType *, 4> NodesInSCC(NL.begin(), NL.end());
134 
135  // We have the set of nodes in the SCC. We go through the set of nodes
136  // that are outside of the SCC and look for edges that cross the two sets.
137  for (NodeType *N : Graph) {
138 
139  // Skip the SCC node and all the nodes inside of it.
140  if (*N == PiNode || NodesInSCC.count(N))
141  continue;
142 
143  enum Direction {
144  Incoming, // Incoming edges to the SCC
145  Outgoing, // Edges going ot of the SCC
146  DirectionCount // To make the enum usable as an array index.
147  };
148 
149  // Use these flags to help us avoid creating redundant edges. If there
150  // are more than one edges from an outside node to inside nodes, we only
151  // keep one edge from that node to the pi-block node. Similarly, if
152  // there are more than one edges from inside nodes to an outside node,
153  // we only keep one edge from the pi-block node to the outside node.
154  // There is a flag defined for each direction (incoming vs outgoing) and
155  // for each type of edge supported, using a two-dimensional boolean
156  // array.
157  using EdgeKind = typename EdgeType::EdgeKind;
158  EnumeratedArray<bool, EdgeKind> EdgeAlreadyCreated[DirectionCount]{false,
159  false};
160 
161  auto createEdgeOfKind = [this](NodeType &Src, NodeType &Dst,
162  const EdgeKind K) {
163  switch (K) {
164  case EdgeKind::RegisterDefUse:
165  createDefUseEdge(Src, Dst);
166  break;
167  case EdgeKind::MemoryDependence:
168  createMemoryEdge(Src, Dst);
169  break;
170  case EdgeKind::Rooted:
171  createRootedEdge(Src, Dst);
172  break;
173  default:
174  llvm_unreachable("Unsupported type of edge.");
175  }
176  };
177 
178  auto reconnectEdges = [&](NodeType *Src, NodeType *Dst, NodeType *New,
179  const Direction Dir) {
180  if (!Src->hasEdgeTo(*Dst))
181  return;
182  LLVM_DEBUG(
183  dbgs() << "reconnecting("
184  << (Dir == Direction::Incoming ? "incoming)" : "outgoing)")
185  << ":\nSrc:" << *Src << "\nDst:" << *Dst << "\nNew:" << *New
186  << "\n");
187  assert((Dir == Direction::Incoming || Dir == Direction::Outgoing) &&
188  "Invalid direction.");
189 
191  Src->findEdgesTo(*Dst, EL);
192  for (EdgeType *OldEdge : EL) {
193  EdgeKind Kind = OldEdge->getKind();
194  if (!EdgeAlreadyCreated[Dir][Kind]) {
195  if (Dir == Direction::Incoming) {
196  createEdgeOfKind(*Src, *New, Kind);
197  LLVM_DEBUG(dbgs() << "created edge from Src to New.\n");
198  } else if (Dir == Direction::Outgoing) {
199  createEdgeOfKind(*New, *Dst, Kind);
200  LLVM_DEBUG(dbgs() << "created edge from New to Dst.\n");
201  }
202  EdgeAlreadyCreated[Dir][Kind] = true;
203  }
204  Src->removeEdge(*OldEdge);
205  destroyEdge(*OldEdge);
206  LLVM_DEBUG(dbgs() << "removed old edge between Src and Dst.\n\n");
207  }
208  };
209 
210  for (NodeType *SCCNode : NL) {
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.erase(&Src))
438  continue;
439 
440  assert(Src.getEdges().size() == 1 &&
441  "Expected a single edge from the candidate src node.");
442  NodeType &Tgt = Src.back().getTargetNode();
443  assert(TargetInDegreeMap.find(&Tgt) != TargetInDegreeMap.end() &&
444  "Expected target to be in the in-degree map.");
445 
446  if (TargetInDegreeMap[&Tgt] != 1)
447  continue;
448 
449  if (!areNodesMergeable(Src, Tgt))
450  continue;
451 
452  // Do not merge if there is also an edge from target to src (immediate
453  // cycle).
454  if (Tgt.hasEdgeTo(Src))
455  continue;
456 
457  LLVM_DEBUG(dbgs() << "Merging:" << Src << "\nWith:" << Tgt << "\n");
458 
459  mergeNodes(Src, Tgt);
460 
461  // If the target node is in the candidate set itself, we need to put the
462  // src node back into the worklist again so it gives the target a chance
463  // to get merged into it. For example if we have:
464  // {(a)->(b), (b)->(c), (c)->(d), ...} and the worklist is initially {b, a},
465  // then after merging (a) and (b) together, we need to put (a,b) back in
466  // the worklist so that (c) can get merged in as well resulting in
467  // {(a,b,c) -> d}
468  // We also need to remove the old target (b), from the worklist. We first
469  // remove it from the candidate set here, and skip any item from the
470  // worklist that is not in the set.
471  if (CandidateSourceNodes.erase(&Tgt)) {
472  Worklist.push_back(&Src);
473  CandidateSourceNodes.insert(&Src);
474  LLVM_DEBUG(dbgs() << "Putting " << &Src << " back in the worklist.\n");
475  }
476  }
477  LLVM_DEBUG(dbgs() << "=== End of Graph Simplification ===\n");
478 }
479 
480 template <class G>
482 
483  // If we don't create pi-blocks, then we may not have a DAG.
484  if (!shouldCreatePiBlocks())
485  return;
486 
487  SmallVector<NodeType *, 64> NodesInPO;
488  using NodeKind = typename NodeType::NodeKind;
489  for (NodeType *N : post_order(&Graph)) {
490  if (N->getKind() == NodeKind::PiBlock) {
491  // Put members of the pi-block right after the pi-block itself, for
492  // convenience.
493  const NodeListType &PiBlockMembers = getNodesInPiBlock(*N);
494  llvm::append_range(NodesInPO, PiBlockMembers);
495  }
496  NodesInPO.push_back(N);
497  }
498 
499  size_t OldSize = Graph.Nodes.size();
500  Graph.Nodes.clear();
501  append_range(Graph.Nodes, reverse(NodesInPO));
502  if (Graph.Nodes.size() != OldSize)
503  assert(false &&
504  "Expected the number of nodes to stay the same after the sort");
505 }
506 
llvm::DependenceGraphInfo
Encapsulate some common data and functionality needed for different variations of data dependence gra...
Definition: DDG.h:265
llvm
Definition: AllocatorList.h:23
llvm::make_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:53
llvm::SmallPtrSetImpl::erase
bool erase(PtrType Ptr)
erase - If the set contains the specified pointer, remove it and return true, otherwise return false.
Definition: SmallPtrSet.h:378
llvm::AbstractDependenceGraphBuilder::createDefUseEdges
void createDefUseEdges()
Analyze the def-use chains and create edges from the nodes containing definitions to the nodes contai...
Definition: DependenceGraphBuilder.cpp:227
SCCIterator.h
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1167
Statistic.h
llvm::Dependence::DVEntry::EQ
@ EQ
Definition: DependenceAnalysis.h:91
NL
#define NL
Definition: DetailedRecordsBackend.cpp:32
llvm::reverse
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:329
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
llvm::AbstractDependenceGraphBuilder::createPiBlocks
void createPiBlocks()
Apply graph abstraction to groups of nodes that belong to a strongly connected component of the graph...
Definition: DependenceGraphBuilder.cpp:90
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:122
DepthFirstIterator.h
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
DependenceGraphBuilder.h
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::User
Definition: User.h:44
llvm::EnumeratedArray
Definition: EnumeratedArray.h:23
llvm::depth_first_ext
iterator_range< df_ext_iterator< T, SetTy > > depth_first_ext(const T &G, SetTy &S)
Definition: DepthFirstIterator.h:251
llvm::Instruction
Definition: Instruction.h:45
llvm::AbstractDependenceGraphBuilder::createAndConnectRootNode
void createAndConnectRootNode()
Create a root node and add edges such that each node in the graph is reachable from the root.
Definition: DependenceGraphBuilder.cpp:63
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >
llvm::lltok::Kind
Kind
Definition: LLToken.h:18
llvm::Loop::LoopBounds::Direction
Direction
An enum for the direction of the loop.
Definition: LoopInfo.h:698
llvm::scc_begin
scc_iterator< T > scc_begin(const T &G)
Construct the begin iterator for a deduced graph type T.
Definition: SCCIterator.h:228
llvm::AbstractDependenceGraphBuilder::createMemoryDependencyEdges
void createMemoryDependencyEdges()
Analyze data dependencies that exist between memory loads or stores, in the graph nodes and create ed...
Definition: DependenceGraphBuilder.cpp:277
llvm::AbstractDependenceGraphBuilder::computeInstructionOrdinals
void computeInstructionOrdinals()
Compute ordinal numbers for each instruction and store them in a map for future look up.
Definition: DependenceGraphBuilder.cpp:41
D
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
llvm::SmallPtrSetImpl::end
iterator end() const
Definition: SmallPtrSet.h:407
llvm::Dependence::DVEntry::GT
@ GT
Definition: DependenceAnalysis.h:93
llvm::DenseMap
Definition: DenseMap.h:714
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::SmallPtrSetImpl::begin
iterator begin() const
Definition: SmallPtrSet.h:402
llvm::Dependence::DVEntry::LT
@ LT
Definition: DependenceAnalysis.h:90
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::SmallPtrSetImpl::count
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
llvm::df_iterator_default_set
Definition: DepthFirstIterator.h:69
llvm::AMDGPU::CPol::SCC
@ SCC
Definition: SIDefines.h:285
DDG.h
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:136
EnumeratedArray.h
llvm::append_range
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:1672
llvm::PICLevel::Level
Level
Definition: CodeGen.h:33
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::insert
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:207
llvm::AbstractDependenceGraphBuilder::simplify
void simplify()
Go through all the nodes in the graph and collapse any two nodes 'a' and 'b' if all of the following ...
Definition: DependenceGraphBuilder.cpp:377
llvm::SmallPtrSetImplBase::size
size_type size() const
Definition: SmallPtrSet.h:92
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::end
iterator end()
Definition: DenseMap.h:83
llvm::post_order
iterator_range< po_iterator< T > > post_order(const T &G)
Definition: PostOrderIterator.h:188
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::size
unsigned size() const
Definition: DenseMap.h:100
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1423
llvm::AbstractDependenceGraphBuilder::sortNodesTopologically
void sortNodesTopologically()
Topologically sort the graph nodes.
Definition: DependenceGraphBuilder.cpp:481
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:584
llvm::ms_demangle::NodeKind
NodeKind
Definition: MicrosoftDemangleNodes.h:225
llvm::AbstractDependenceGraphBuilder::createFineGrainedNodes
void createFineGrainedNodes()
Create fine grained nodes.
Definition: DependenceGraphBuilder.cpp:50
N
#define N
llvm::scc_end
scc_iterator< T > scc_end(const T &G)
Construct the end iterator for a deduced graph type T.
Definition: SCCIterator.h:233
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::Value::users
iterator_range< user_iterator > users()
Definition: Value.h:422
llvm::SmallVectorImpl::emplace_back
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:907
llvm::SmallPtrSetImpl::insert
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