LLVM  16.0.0git
LazyCallGraph.cpp
Go to the documentation of this file.
1 //===- LazyCallGraph.cpp - Analysis of a Module's call graph --------------===//
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 
10 
11 #include "llvm/ADT/ArrayRef.h"
12 #include "llvm/ADT/STLExtras.h"
13 #include "llvm/ADT/Sequence.h"
14 #include "llvm/ADT/SmallPtrSet.h"
15 #include "llvm/ADT/SmallVector.h"
18 #include "llvm/IR/Constants.h"
19 #include "llvm/IR/Function.h"
20 #include "llvm/IR/GlobalVariable.h"
21 #include "llvm/IR/InstIterator.h"
22 #include "llvm/IR/Instruction.h"
23 #include "llvm/IR/Module.h"
24 #include "llvm/IR/PassManager.h"
25 #include "llvm/Support/Casting.h"
26 #include "llvm/Support/Compiler.h"
27 #include "llvm/Support/Debug.h"
30 #include <algorithm>
31 
32 #ifdef EXPENSIVE_CHECKS
33 #include "llvm/ADT/ScopeExit.h"
34 #endif
35 
36 using namespace llvm;
37 
38 #define DEBUG_TYPE "lcg"
39 
40 void LazyCallGraph::EdgeSequence::insertEdgeInternal(Node &TargetN,
41  Edge::Kind EK) {
42  EdgeIndexMap.try_emplace(&TargetN, Edges.size());
43  Edges.emplace_back(TargetN, EK);
44 }
45 
46 void LazyCallGraph::EdgeSequence::setEdgeKind(Node &TargetN, Edge::Kind EK) {
47  Edges[EdgeIndexMap.find(&TargetN)->second].setKind(EK);
48 }
49 
50 bool LazyCallGraph::EdgeSequence::removeEdgeInternal(Node &TargetN) {
51  auto IndexMapI = EdgeIndexMap.find(&TargetN);
52  if (IndexMapI == EdgeIndexMap.end())
53  return false;
54 
55  Edges[IndexMapI->second] = Edge();
56  EdgeIndexMap.erase(IndexMapI);
57  return true;
58 }
59 
63  if (!EdgeIndexMap.try_emplace(&N, Edges.size()).second)
64  return;
65 
66  LLVM_DEBUG(dbgs() << " Added callable function: " << N.getName() << "\n");
68 }
69 
70 LazyCallGraph::EdgeSequence &LazyCallGraph::Node::populateSlow() {
71  assert(!Edges && "Must not have already populated the edges for this node!");
72 
73  LLVM_DEBUG(dbgs() << " Adding functions called by '" << getName()
74  << "' to the graph.\n");
75 
76  Edges = EdgeSequence();
77 
81 
82  // Find all the potential call graph edges in this function. We track both
83  // actual call edges and indirect references to functions. The direct calls
84  // are trivially added, but to accumulate the latter we walk the instructions
85  // and add every operand which is a constant to the worklist to process
86  // afterward.
87  //
88  // Note that we consider *any* function with a definition to be a viable
89  // edge. Even if the function's definition is subject to replacement by
90  // some other module (say, a weak definition) there may still be
91  // optimizations which essentially speculate based on the definition and
92  // a way to check that the specific definition is in fact the one being
93  // used. For example, this could be done by moving the weak definition to
94  // a strong (internal) definition and making the weak definition be an
95  // alias. Then a test of the address of the weak function against the new
96  // strong definition's address would be an effective way to determine the
97  // safety of optimizing a direct call edge.
98  for (BasicBlock &BB : *F)
99  for (Instruction &I : BB) {
100  if (auto *CB = dyn_cast<CallBase>(&I))
101  if (Function *Callee = CB->getCalledFunction())
102  if (!Callee->isDeclaration())
103  if (Callees.insert(Callee).second) {
104  Visited.insert(Callee);
105  addEdge(Edges->Edges, Edges->EdgeIndexMap, G->get(*Callee),
107  }
108 
109  for (Value *Op : I.operand_values())
110  if (Constant *C = dyn_cast<Constant>(Op))
111  if (Visited.insert(C).second)
112  Worklist.push_back(C);
113  }
114 
115  // We've collected all the constant (and thus potentially function or
116  // function containing) operands to all the instructions in the function.
117  // Process them (recursively) collecting every function found.
118  visitReferences(Worklist, Visited, [&](Function &F) {
119  addEdge(Edges->Edges, Edges->EdgeIndexMap, G->get(F),
121  });
122 
123  // Add implicit reference edges to any defined libcall functions (if we
124  // haven't found an explicit edge).
125  for (auto *F : G->LibFunctions)
126  if (!Visited.count(F))
127  addEdge(Edges->Edges, Edges->EdgeIndexMap, G->get(*F),
129 
130  return *Edges;
131 }
132 
133 void LazyCallGraph::Node::replaceFunction(Function &NewF) {
134  assert(F != &NewF && "Must not replace a function with itself!");
135  F = &NewF;
136 }
137 
138 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
139 LLVM_DUMP_METHOD void LazyCallGraph::Node::dump() const {
140  dbgs() << *this << '\n';
141 }
142 #endif
143 
145  LibFunc LF;
146 
147  // Either this is a normal library function or a "vectorizable"
148  // function. Not using the VFDatabase here because this query
149  // is related only to libraries handled via the TLI.
150  return TLI.getLibFunc(F, LF) ||
151  TLI.isKnownVectorFunctionInLibrary(F.getName());
152 }
153 
155  Module &M, function_ref<TargetLibraryInfo &(Function &)> GetTLI) {
156  LLVM_DEBUG(dbgs() << "Building CG for module: " << M.getModuleIdentifier()
157  << "\n");
158  for (Function &F : M) {
159  if (F.isDeclaration())
160  continue;
161  // If this function is a known lib function to LLVM then we want to
162  // synthesize reference edges to it to model the fact that LLVM can turn
163  // arbitrary code into a library function call.
164  if (isKnownLibFunction(F, GetTLI(F)))
165  LibFunctions.insert(&F);
166 
167  if (F.hasLocalLinkage())
168  continue;
169 
170  // External linkage defined functions have edges to them from other
171  // modules.
172  LLVM_DEBUG(dbgs() << " Adding '" << F.getName()
173  << "' to entry set of the graph.\n");
174  addEdge(EntryEdges.Edges, EntryEdges.EdgeIndexMap, get(F), Edge::Ref);
175  }
176 
177  // Externally visible aliases of internal functions are also viable entry
178  // edges to the module.
179  for (auto &A : M.aliases()) {
180  if (A.hasLocalLinkage())
181  continue;
182  if (Function* F = dyn_cast<Function>(A.getAliasee())) {
183  LLVM_DEBUG(dbgs() << " Adding '" << F->getName()
184  << "' with alias '" << A.getName()
185  << "' to entry set of the graph.\n");
186  addEdge(EntryEdges.Edges, EntryEdges.EdgeIndexMap, get(*F), Edge::Ref);
187  }
188  }
189 
190  // Now add entry nodes for functions reachable via initializers to globals.
193  for (GlobalVariable &GV : M.globals())
194  if (GV.hasInitializer())
195  if (Visited.insert(GV.getInitializer()).second)
196  Worklist.push_back(GV.getInitializer());
197 
198  LLVM_DEBUG(
199  dbgs() << " Adding functions referenced by global initializers to the "
200  "entry set.\n");
201  visitReferences(Worklist, Visited, [&](Function &F) {
202  addEdge(EntryEdges.Edges, EntryEdges.EdgeIndexMap, get(F),
204  });
205 }
206 
208  : BPA(std::move(G.BPA)), NodeMap(std::move(G.NodeMap)),
209  EntryEdges(std::move(G.EntryEdges)), SCCBPA(std::move(G.SCCBPA)),
210  SCCMap(std::move(G.SCCMap)), LibFunctions(std::move(G.LibFunctions)) {
211  updateGraphPtrs();
212 }
213 
216  // Check whether the analysis, all analyses on functions, or the function's
217  // CFG have been preserved.
218  auto PAC = PA.getChecker<llvm::LazyCallGraphAnalysis>();
219  return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Module>>());
220 }
221 
223  BPA = std::move(G.BPA);
224  NodeMap = std::move(G.NodeMap);
225  EntryEdges = std::move(G.EntryEdges);
226  SCCBPA = std::move(G.SCCBPA);
227  SCCMap = std::move(G.SCCMap);
228  LibFunctions = std::move(G.LibFunctions);
229  updateGraphPtrs();
230  return *this;
231 }
232 
233 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
234 LLVM_DUMP_METHOD void LazyCallGraph::SCC::dump() const {
235  dbgs() << *this << '\n';
236 }
237 #endif
238 
239 #if !defined(NDEBUG) || defined(EXPENSIVE_CHECKS)
240 void LazyCallGraph::SCC::verify() {
241  assert(OuterRefSCC && "Can't have a null RefSCC!");
242  assert(!Nodes.empty() && "Can't have an empty SCC!");
243 
244  for (Node *N : Nodes) {
245  assert(N && "Can't have a null node!");
246  assert(OuterRefSCC->G->lookupSCC(*N) == this &&
247  "Node does not map to this SCC!");
248  assert(N->DFSNumber == -1 &&
249  "Must set DFS numbers to -1 when adding a node to an SCC!");
250  assert(N->LowLink == -1 &&
251  "Must set low link to -1 when adding a node to an SCC!");
252  for (Edge &E : **N)
253  assert(E.getNode().isPopulated() && "Can't have an unpopulated node!");
254 
255 #ifdef EXPENSIVE_CHECKS
256  // Verify that all nodes in this SCC can reach all other nodes.
257  SmallVector<Node *, 4> Worklist;
258  SmallPtrSet<Node *, 4> Visited;
259  Worklist.push_back(N);
260  while (!Worklist.empty()) {
261  Node *VisitingNode = Worklist.pop_back_val();
262  if (!Visited.insert(VisitingNode).second)
263  continue;
264  for (Edge &E : (*VisitingNode)->calls())
265  Worklist.push_back(&E.getNode());
266  }
267  for (Node *NodeToVisit : Nodes) {
268  assert(Visited.contains(NodeToVisit) &&
269  "Cannot reach all nodes within SCC");
270  }
271 #endif
272  }
273 }
274 #endif
275 
277  if (this == &C)
278  return false;
279 
280  for (Node &N : *this)
281  for (Edge &E : N->calls())
282  if (OuterRefSCC->G->lookupSCC(E.getNode()) == &C)
283  return true;
284 
285  // No edges found.
286  return false;
287 }
288 
289 bool LazyCallGraph::SCC::isAncestorOf(const SCC &TargetC) const {
290  if (this == &TargetC)
291  return false;
292 
293  LazyCallGraph &G = *OuterRefSCC->G;
294 
295  // Start with this SCC.
296  SmallPtrSet<const SCC *, 16> Visited = {this};
297  SmallVector<const SCC *, 16> Worklist = {this};
298 
299  // Walk down the graph until we run out of edges or find a path to TargetC.
300  do {
301  const SCC &C = *Worklist.pop_back_val();
302  for (Node &N : C)
303  for (Edge &E : N->calls()) {
304  SCC *CalleeC = G.lookupSCC(E.getNode());
305  if (!CalleeC)
306  continue;
307 
308  // If the callee's SCC is the TargetC, we're done.
309  if (CalleeC == &TargetC)
310  return true;
311 
312  // If this is the first time we've reached this SCC, put it on the
313  // worklist to recurse through.
314  if (Visited.insert(CalleeC).second)
315  Worklist.push_back(CalleeC);
316  }
317  } while (!Worklist.empty());
318 
319  // No paths found.
320  return false;
321 }
322 
323 LazyCallGraph::RefSCC::RefSCC(LazyCallGraph &G) : G(&G) {}
324 
325 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
326 LLVM_DUMP_METHOD void LazyCallGraph::RefSCC::dump() const {
327  dbgs() << *this << '\n';
328 }
329 #endif
330 
331 #if !defined(NDEBUG) || defined(EXPENSIVE_CHECKS)
332 void LazyCallGraph::RefSCC::verify() {
333  assert(G && "Can't have a null graph!");
334  assert(!SCCs.empty() && "Can't have an empty SCC!");
335 
336  // Verify basic properties of the SCCs.
337  SmallPtrSet<SCC *, 4> SCCSet;
338  for (SCC *C : SCCs) {
339  assert(C && "Can't have a null SCC!");
340  C->verify();
341  assert(&C->getOuterRefSCC() == this &&
342  "SCC doesn't think it is inside this RefSCC!");
343  bool Inserted = SCCSet.insert(C).second;
344  assert(Inserted && "Found a duplicate SCC!");
345  auto IndexIt = SCCIndices.find(C);
346  assert(IndexIt != SCCIndices.end() &&
347  "Found an SCC that doesn't have an index!");
348  }
349 
350  // Check that our indices map correctly.
351  for (auto [C, I] : SCCIndices) {
352  assert(C && "Can't have a null SCC in the indices!");
353  assert(SCCSet.count(C) && "Found an index for an SCC not in the RefSCC!");
354  assert(SCCs[I] == C && "Index doesn't point to SCC!");
355  }
356 
357  // Check that the SCCs are in fact in post-order.
358  for (int I = 0, Size = SCCs.size(); I < Size; ++I) {
359  SCC &SourceSCC = *SCCs[I];
360  for (Node &N : SourceSCC)
361  for (Edge &E : *N) {
362  if (!E.isCall())
363  continue;
364  SCC &TargetSCC = *G->lookupSCC(E.getNode());
365  if (&TargetSCC.getOuterRefSCC() == this) {
366  assert(SCCIndices.find(&TargetSCC)->second <= I &&
367  "Edge between SCCs violates post-order relationship.");
368  continue;
369  }
370  }
371  }
372 
373 #ifdef EXPENSIVE_CHECKS
374  // Verify that all nodes in this RefSCC can reach all other nodes.
375  SmallVector<Node *> Nodes;
376  for (SCC *C : SCCs) {
377  for (Node &N : *C)
378  Nodes.push_back(&N);
379  }
380  for (Node *N : Nodes) {
381  SmallVector<Node *, 4> Worklist;
382  SmallPtrSet<Node *, 4> Visited;
383  Worklist.push_back(N);
384  while (!Worklist.empty()) {
385  Node *VisitingNode = Worklist.pop_back_val();
386  if (!Visited.insert(VisitingNode).second)
387  continue;
388  for (Edge &E : **VisitingNode)
389  Worklist.push_back(&E.getNode());
390  }
391  for (Node *NodeToVisit : Nodes) {
392  assert(Visited.contains(NodeToVisit) &&
393  "Cannot reach all nodes within RefSCC");
394  }
395  }
396 #endif
397 }
398 #endif
399 
401  if (&RC == this)
402  return false;
403 
404  // Search all edges to see if this is a parent.
405  for (SCC &C : *this)
406  for (Node &N : C)
407  for (Edge &E : *N)
408  if (G->lookupRefSCC(E.getNode()) == &RC)
409  return true;
410 
411  return false;
412 }
413 
415  if (&RC == this)
416  return false;
417 
418  // For each descendant of this RefSCC, see if one of its children is the
419  // argument. If not, add that descendant to the worklist and continue
420  // searching.
423  Worklist.push_back(this);
424  Visited.insert(this);
425  do {
426  const RefSCC &DescendantRC = *Worklist.pop_back_val();
427  for (SCC &C : DescendantRC)
428  for (Node &N : C)
429  for (Edge &E : *N) {
430  auto *ChildRC = G->lookupRefSCC(E.getNode());
431  if (ChildRC == &RC)
432  return true;
433  if (!ChildRC || !Visited.insert(ChildRC).second)
434  continue;
435  Worklist.push_back(ChildRC);
436  }
437  } while (!Worklist.empty());
438 
439  return false;
440 }
441 
442 /// Generic helper that updates a postorder sequence of SCCs for a potentially
443 /// cycle-introducing edge insertion.
444 ///
445 /// A postorder sequence of SCCs of a directed graph has one fundamental
446 /// property: all deges in the DAG of SCCs point "up" the sequence. That is,
447 /// all edges in the SCC DAG point to prior SCCs in the sequence.
448 ///
449 /// This routine both updates a postorder sequence and uses that sequence to
450 /// compute the set of SCCs connected into a cycle. It should only be called to
451 /// insert a "downward" edge which will require changing the sequence to
452 /// restore it to a postorder.
453 ///
454 /// When inserting an edge from an earlier SCC to a later SCC in some postorder
455 /// sequence, all of the SCCs which may be impacted are in the closed range of
456 /// those two within the postorder sequence. The algorithm used here to restore
457 /// the state is as follows:
458 ///
459 /// 1) Starting from the source SCC, construct a set of SCCs which reach the
460 /// source SCC consisting of just the source SCC. Then scan toward the
461 /// target SCC in postorder and for each SCC, if it has an edge to an SCC
462 /// in the set, add it to the set. Otherwise, the source SCC is not
463 /// a successor, move it in the postorder sequence to immediately before
464 /// the source SCC, shifting the source SCC and all SCCs in the set one
465 /// position toward the target SCC. Stop scanning after processing the
466 /// target SCC.
467 /// 2) If the source SCC is now past the target SCC in the postorder sequence,
468 /// and thus the new edge will flow toward the start, we are done.
469 /// 3) Otherwise, starting from the target SCC, walk all edges which reach an
470 /// SCC between the source and the target, and add them to the set of
471 /// connected SCCs, then recurse through them. Once a complete set of the
472 /// SCCs the target connects to is known, hoist the remaining SCCs between
473 /// the source and the target to be above the target. Note that there is no
474 /// need to process the source SCC, it is already known to connect.
475 /// 4) At this point, all of the SCCs in the closed range between the source
476 /// SCC and the target SCC in the postorder sequence are connected,
477 /// including the target SCC and the source SCC. Inserting the edge from
478 /// the source SCC to the target SCC will form a cycle out of precisely
479 /// these SCCs. Thus we can merge all of the SCCs in this closed range into
480 /// a single SCC.
481 ///
482 /// This process has various important properties:
483 /// - Only mutates the SCCs when adding the edge actually changes the SCC
484 /// structure.
485 /// - Never mutates SCCs which are unaffected by the change.
486 /// - Updates the postorder sequence to correctly satisfy the postorder
487 /// constraint after the edge is inserted.
488 /// - Only reorders SCCs in the closed postorder sequence from the source to
489 /// the target, so easy to bound how much has changed even in the ordering.
490 /// - Big-O is the number of edges in the closed postorder range of SCCs from
491 /// source to target.
492 ///
493 /// This helper routine, in addition to updating the postorder sequence itself
494 /// will also update a map from SCCs to indices within that sequence.
495 ///
496 /// The sequence and the map must operate on pointers to the SCC type.
497 ///
498 /// Two callbacks must be provided. The first computes the subset of SCCs in
499 /// the postorder closed range from the source to the target which connect to
500 /// the source SCC via some (transitive) set of edges. The second computes the
501 /// subset of the same range which the target SCC connects to via some
502 /// (transitive) set of edges. Both callbacks should populate the set argument
503 /// provided.
504 template <typename SCCT, typename PostorderSequenceT, typename SCCIndexMapT,
505  typename ComputeSourceConnectedSetCallableT,
506  typename ComputeTargetConnectedSetCallableT>
509  SCCT &SourceSCC, SCCT &TargetSCC, PostorderSequenceT &SCCs,
510  SCCIndexMapT &SCCIndices,
511  ComputeSourceConnectedSetCallableT ComputeSourceConnectedSet,
512  ComputeTargetConnectedSetCallableT ComputeTargetConnectedSet) {
513  int SourceIdx = SCCIndices[&SourceSCC];
514  int TargetIdx = SCCIndices[&TargetSCC];
515  assert(SourceIdx < TargetIdx && "Cannot have equal indices here!");
516 
517  SmallPtrSet<SCCT *, 4> ConnectedSet;
518 
519  // Compute the SCCs which (transitively) reach the source.
520  ComputeSourceConnectedSet(ConnectedSet);
521 
522  // Partition the SCCs in this part of the port-order sequence so only SCCs
523  // connecting to the source remain between it and the target. This is
524  // a benign partition as it preserves postorder.
525  auto SourceI = std::stable_partition(
526  SCCs.begin() + SourceIdx, SCCs.begin() + TargetIdx + 1,
527  [&ConnectedSet](SCCT *C) { return !ConnectedSet.count(C); });
528  for (int I = SourceIdx, E = TargetIdx + 1; I < E; ++I)
529  SCCIndices.find(SCCs[I])->second = I;
530 
531  // If the target doesn't connect to the source, then we've corrected the
532  // post-order and there are no cycles formed.
533  if (!ConnectedSet.count(&TargetSCC)) {
534  assert(SourceI > (SCCs.begin() + SourceIdx) &&
535  "Must have moved the source to fix the post-order.");
536  assert(*std::prev(SourceI) == &TargetSCC &&
537  "Last SCC to move should have bene the target.");
538 
539  // Return an empty range at the target SCC indicating there is nothing to
540  // merge.
541  return make_range(std::prev(SourceI), std::prev(SourceI));
542  }
543 
544  assert(SCCs[TargetIdx] == &TargetSCC &&
545  "Should not have moved target if connected!");
546  SourceIdx = SourceI - SCCs.begin();
547  assert(SCCs[SourceIdx] == &SourceSCC &&
548  "Bad updated index computation for the source SCC!");
549 
550  // See whether there are any remaining intervening SCCs between the source
551  // and target. If so we need to make sure they all are reachable form the
552  // target.
553  if (SourceIdx + 1 < TargetIdx) {
554  ConnectedSet.clear();
555  ComputeTargetConnectedSet(ConnectedSet);
556 
557  // Partition SCCs so that only SCCs reached from the target remain between
558  // the source and the target. This preserves postorder.
559  auto TargetI = std::stable_partition(
560  SCCs.begin() + SourceIdx + 1, SCCs.begin() + TargetIdx + 1,
561  [&ConnectedSet](SCCT *C) { return ConnectedSet.count(C); });
562  for (int I = SourceIdx + 1, E = TargetIdx + 1; I < E; ++I)
563  SCCIndices.find(SCCs[I])->second = I;
564  TargetIdx = std::prev(TargetI) - SCCs.begin();
565  assert(SCCs[TargetIdx] == &TargetSCC &&
566  "Should always end with the target!");
567  }
568 
569  // At this point, we know that connecting source to target forms a cycle
570  // because target connects back to source, and we know that all the SCCs
571  // between the source and target in the postorder sequence participate in that
572  // cycle.
573  return make_range(SCCs.begin() + SourceIdx, SCCs.begin() + TargetIdx);
574 }
575 
577  Node &SourceN, Node &TargetN,
578  function_ref<void(ArrayRef<SCC *> MergeSCCs)> MergeCB) {
579  assert(!(*SourceN)[TargetN].isCall() && "Must start with a ref edge!");
580  SmallVector<SCC *, 1> DeletedSCCs;
581 
582 #ifdef EXPENSIVE_CHECKS
583  verify();
584  auto VerifyOnExit = make_scope_exit([&]() { verify(); });
585 #endif
586 
587  SCC &SourceSCC = *G->lookupSCC(SourceN);
588  SCC &TargetSCC = *G->lookupSCC(TargetN);
589 
590  // If the two nodes are already part of the same SCC, we're also done as
591  // we've just added more connectivity.
592  if (&SourceSCC == &TargetSCC) {
593  SourceN->setEdgeKind(TargetN, Edge::Call);
594  return false; // No new cycle.
595  }
596 
597  // At this point we leverage the postorder list of SCCs to detect when the
598  // insertion of an edge changes the SCC structure in any way.
599  //
600  // First and foremost, we can eliminate the need for any changes when the
601  // edge is toward the beginning of the postorder sequence because all edges
602  // flow in that direction already. Thus adding a new one cannot form a cycle.
603  int SourceIdx = SCCIndices[&SourceSCC];
604  int TargetIdx = SCCIndices[&TargetSCC];
605  if (TargetIdx < SourceIdx) {
606  SourceN->setEdgeKind(TargetN, Edge::Call);
607  return false; // No new cycle.
608  }
609 
610  // Compute the SCCs which (transitively) reach the source.
611  auto ComputeSourceConnectedSet = [&](SmallPtrSetImpl<SCC *> &ConnectedSet) {
612 #ifdef EXPENSIVE_CHECKS
613  // Check that the RefSCC is still valid before computing this as the
614  // results will be nonsensical of we've broken its invariants.
615  verify();
616 #endif
617  ConnectedSet.insert(&SourceSCC);
618  auto IsConnected = [&](SCC &C) {
619  for (Node &N : C)
620  for (Edge &E : N->calls())
621  if (ConnectedSet.count(G->lookupSCC(E.getNode())))
622  return true;
623 
624  return false;
625  };
626 
627  for (SCC *C :
628  make_range(SCCs.begin() + SourceIdx + 1, SCCs.begin() + TargetIdx + 1))
629  if (IsConnected(*C))
630  ConnectedSet.insert(C);
631  };
632 
633  // Use a normal worklist to find which SCCs the target connects to. We still
634  // bound the search based on the range in the postorder list we care about,
635  // but because this is forward connectivity we just "recurse" through the
636  // edges.
637  auto ComputeTargetConnectedSet = [&](SmallPtrSetImpl<SCC *> &ConnectedSet) {
638 #ifdef EXPENSIVE_CHECKS
639  // Check that the RefSCC is still valid before computing this as the
640  // results will be nonsensical of we've broken its invariants.
641  verify();
642 #endif
643  ConnectedSet.insert(&TargetSCC);
644  SmallVector<SCC *, 4> Worklist;
645  Worklist.push_back(&TargetSCC);
646  do {
647  SCC &C = *Worklist.pop_back_val();
648  for (Node &N : C)
649  for (Edge &E : *N) {
650  if (!E.isCall())
651  continue;
652  SCC &EdgeC = *G->lookupSCC(E.getNode());
653  if (&EdgeC.getOuterRefSCC() != this)
654  // Not in this RefSCC...
655  continue;
656  if (SCCIndices.find(&EdgeC)->second <= SourceIdx)
657  // Not in the postorder sequence between source and target.
658  continue;
659 
660  if (ConnectedSet.insert(&EdgeC).second)
661  Worklist.push_back(&EdgeC);
662  }
663  } while (!Worklist.empty());
664  };
665 
666  // Use a generic helper to update the postorder sequence of SCCs and return
667  // a range of any SCCs connected into a cycle by inserting this edge. This
668  // routine will also take care of updating the indices into the postorder
669  // sequence.
670  auto MergeRange = updatePostorderSequenceForEdgeInsertion(
671  SourceSCC, TargetSCC, SCCs, SCCIndices, ComputeSourceConnectedSet,
672  ComputeTargetConnectedSet);
673 
674  // Run the user's callback on the merged SCCs before we actually merge them.
675  if (MergeCB)
676  MergeCB(makeArrayRef(MergeRange.begin(), MergeRange.end()));
677 
678  // If the merge range is empty, then adding the edge didn't actually form any
679  // new cycles. We're done.
680  if (MergeRange.empty()) {
681  // Now that the SCC structure is finalized, flip the kind to call.
682  SourceN->setEdgeKind(TargetN, Edge::Call);
683  return false; // No new cycle.
684  }
685 
686 #ifdef EXPENSIVE_CHECKS
687  // Before merging, check that the RefSCC remains valid after all the
688  // postorder updates.
689  verify();
690 #endif
691 
692  // Otherwise we need to merge all the SCCs in the cycle into a single result
693  // SCC.
694  //
695  // NB: We merge into the target because all of these functions were already
696  // reachable from the target, meaning any SCC-wide properties deduced about it
697  // other than the set of functions within it will not have changed.
698  for (SCC *C : MergeRange) {
699  assert(C != &TargetSCC &&
700  "We merge *into* the target and shouldn't process it here!");
701  SCCIndices.erase(C);
702  TargetSCC.Nodes.append(C->Nodes.begin(), C->Nodes.end());
703  for (Node *N : C->Nodes)
704  G->SCCMap[N] = &TargetSCC;
705  C->clear();
706  DeletedSCCs.push_back(C);
707  }
708 
709  // Erase the merged SCCs from the list and update the indices of the
710  // remaining SCCs.
711  int IndexOffset = MergeRange.end() - MergeRange.begin();
712  auto EraseEnd = SCCs.erase(MergeRange.begin(), MergeRange.end());
713  for (SCC *C : make_range(EraseEnd, SCCs.end()))
714  SCCIndices[C] -= IndexOffset;
715 
716  // Now that the SCC structure is finalized, flip the kind to call.
717  SourceN->setEdgeKind(TargetN, Edge::Call);
718 
719  // And we're done, but we did form a new cycle.
720  return true;
721 }
722 
724  Node &TargetN) {
725  assert((*SourceN)[TargetN].isCall() && "Must start with a call edge!");
726 
727 #ifdef EXPENSIVE_CHECKS
728  verify();
729  auto VerifyOnExit = make_scope_exit([&]() { verify(); });
730 #endif
731 
732  assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");
733  assert(G->lookupRefSCC(TargetN) == this && "Target must be in this RefSCC.");
734  assert(G->lookupSCC(SourceN) != G->lookupSCC(TargetN) &&
735  "Source and Target must be in separate SCCs for this to be trivial!");
736 
737  // Set the edge kind.
738  SourceN->setEdgeKind(TargetN, Edge::Ref);
739 }
740 
743  assert((*SourceN)[TargetN].isCall() && "Must start with a call edge!");
744 
745 #ifdef EXPENSIVE_CHECKS
746  verify();
747  auto VerifyOnExit = make_scope_exit([&]() { verify(); });
748 #endif
749 
750  assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");
751  assert(G->lookupRefSCC(TargetN) == this && "Target must be in this RefSCC.");
752 
753  SCC &TargetSCC = *G->lookupSCC(TargetN);
754  assert(G->lookupSCC(SourceN) == &TargetSCC && "Source and Target must be in "
755  "the same SCC to require the "
756  "full CG update.");
757 
758  // Set the edge kind.
759  SourceN->setEdgeKind(TargetN, Edge::Ref);
760 
761  // Otherwise we are removing a call edge from a single SCC. This may break
762  // the cycle. In order to compute the new set of SCCs, we need to do a small
763  // DFS over the nodes within the SCC to form any sub-cycles that remain as
764  // distinct SCCs and compute a postorder over the resulting SCCs.
765  //
766  // However, we specially handle the target node. The target node is known to
767  // reach all other nodes in the original SCC by definition. This means that
768  // we want the old SCC to be replaced with an SCC containing that node as it
769  // will be the root of whatever SCC DAG results from the DFS. Assumptions
770  // about an SCC such as the set of functions called will continue to hold,
771  // etc.
772 
773  SCC &OldSCC = TargetSCC;
775  SmallVector<Node *, 16> PendingSCCStack;
776  SmallVector<SCC *, 4> NewSCCs;
777 
778  // Prepare the nodes for a fresh DFS.
779  SmallVector<Node *, 16> Worklist;
780  Worklist.swap(OldSCC.Nodes);
781  for (Node *N : Worklist) {
782  N->DFSNumber = N->LowLink = 0;
783  G->SCCMap.erase(N);
784  }
785 
786  // Force the target node to be in the old SCC. This also enables us to take
787  // a very significant short-cut in the standard Tarjan walk to re-form SCCs
788  // below: whenever we build an edge that reaches the target node, we know
789  // that the target node eventually connects back to all other nodes in our
790  // walk. As a consequence, we can detect and handle participants in that
791  // cycle without walking all the edges that form this connection, and instead
792  // by relying on the fundamental guarantee coming into this operation (all
793  // nodes are reachable from the target due to previously forming an SCC).
794  TargetN.DFSNumber = TargetN.LowLink = -1;
795  OldSCC.Nodes.push_back(&TargetN);
796  G->SCCMap[&TargetN] = &OldSCC;
797 
798  // Scan down the stack and DFS across the call edges.
799  for (Node *RootN : Worklist) {
800  assert(DFSStack.empty() &&
801  "Cannot begin a new root with a non-empty DFS stack!");
802  assert(PendingSCCStack.empty() &&
803  "Cannot begin a new root with pending nodes for an SCC!");
804 
805  // Skip any nodes we've already reached in the DFS.
806  if (RootN->DFSNumber != 0) {
807  assert(RootN->DFSNumber == -1 &&
808  "Shouldn't have any mid-DFS root nodes!");
809  continue;
810  }
811 
812  RootN->DFSNumber = RootN->LowLink = 1;
813  int NextDFSNumber = 2;
814 
815  DFSStack.emplace_back(RootN, (*RootN)->call_begin());
816  do {
817  auto [N, I] = DFSStack.pop_back_val();
818  auto E = (*N)->call_end();
819  while (I != E) {
820  Node &ChildN = I->getNode();
821  if (ChildN.DFSNumber == 0) {
822  // We haven't yet visited this child, so descend, pushing the current
823  // node onto the stack.
824  DFSStack.emplace_back(N, I);
825 
826  assert(!G->SCCMap.count(&ChildN) &&
827  "Found a node with 0 DFS number but already in an SCC!");
828  ChildN.DFSNumber = ChildN.LowLink = NextDFSNumber++;
829  N = &ChildN;
830  I = (*N)->call_begin();
831  E = (*N)->call_end();
832  continue;
833  }
834 
835  // Check for the child already being part of some component.
836  if (ChildN.DFSNumber == -1) {
837  if (G->lookupSCC(ChildN) == &OldSCC) {
838  // If the child is part of the old SCC, we know that it can reach
839  // every other node, so we have formed a cycle. Pull the entire DFS
840  // and pending stacks into it. See the comment above about setting
841  // up the old SCC for why we do this.
842  int OldSize = OldSCC.size();
843  OldSCC.Nodes.push_back(N);
844  OldSCC.Nodes.append(PendingSCCStack.begin(), PendingSCCStack.end());
845  PendingSCCStack.clear();
846  while (!DFSStack.empty())
847  OldSCC.Nodes.push_back(DFSStack.pop_back_val().first);
848  for (Node &N : drop_begin(OldSCC, OldSize)) {
849  N.DFSNumber = N.LowLink = -1;
850  G->SCCMap[&N] = &OldSCC;
851  }
852  N = nullptr;
853  break;
854  }
855 
856  // If the child has already been added to some child component, it
857  // couldn't impact the low-link of this parent because it isn't
858  // connected, and thus its low-link isn't relevant so skip it.
859  ++I;
860  continue;
861  }
862 
863  // Track the lowest linked child as the lowest link for this node.
864  assert(ChildN.LowLink > 0 && "Must have a positive low-link number!");
865  if (ChildN.LowLink < N->LowLink)
866  N->LowLink = ChildN.LowLink;
867 
868  // Move to the next edge.
869  ++I;
870  }
871  if (!N)
872  // Cleared the DFS early, start another round.
873  break;
874 
875  // We've finished processing N and its descendants, put it on our pending
876  // SCC stack to eventually get merged into an SCC of nodes.
877  PendingSCCStack.push_back(N);
878 
879  // If this node is linked to some lower entry, continue walking up the
880  // stack.
881  if (N->LowLink != N->DFSNumber)
882  continue;
883 
884  // Otherwise, we've completed an SCC. Append it to our post order list of
885  // SCCs.
886  int RootDFSNumber = N->DFSNumber;
887  // Find the range of the node stack by walking down until we pass the
888  // root DFS number.
889  auto SCCNodes = make_range(
890  PendingSCCStack.rbegin(),
891  find_if(reverse(PendingSCCStack), [RootDFSNumber](const Node *N) {
892  return N->DFSNumber < RootDFSNumber;
893  }));
894 
895  // Form a new SCC out of these nodes and then clear them off our pending
896  // stack.
897  NewSCCs.push_back(G->createSCC(*this, SCCNodes));
898  for (Node &N : *NewSCCs.back()) {
899  N.DFSNumber = N.LowLink = -1;
900  G->SCCMap[&N] = NewSCCs.back();
901  }
902  PendingSCCStack.erase(SCCNodes.end().base(), PendingSCCStack.end());
903  } while (!DFSStack.empty());
904  }
905 
906  // Insert the remaining SCCs before the old one. The old SCC can reach all
907  // other SCCs we form because it contains the target node of the removed edge
908  // of the old SCC. This means that we will have edges into all the new SCCs,
909  // which means the old one must come last for postorder.
910  int OldIdx = SCCIndices[&OldSCC];
911  SCCs.insert(SCCs.begin() + OldIdx, NewSCCs.begin(), NewSCCs.end());
912 
913  // Update the mapping from SCC* to index to use the new SCC*s, and remove the
914  // old SCC from the mapping.
915  for (int Idx = OldIdx, Size = SCCs.size(); Idx < Size; ++Idx)
916  SCCIndices[SCCs[Idx]] = Idx;
917 
918  return make_range(SCCs.begin() + OldIdx,
919  SCCs.begin() + OldIdx + NewSCCs.size());
920 }
921 
923  Node &TargetN) {
924  assert(!(*SourceN)[TargetN].isCall() && "Must start with a ref edge!");
925 
926  assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");
927  assert(G->lookupRefSCC(TargetN) != this &&
928  "Target must not be in this RefSCC.");
929 #ifdef EXPENSIVE_CHECKS
930  assert(G->lookupRefSCC(TargetN)->isDescendantOf(*this) &&
931  "Target must be a descendant of the Source.");
932 #endif
933 
934  // Edges between RefSCCs are the same regardless of call or ref, so we can
935  // just flip the edge here.
936  SourceN->setEdgeKind(TargetN, Edge::Call);
937 
938 #ifdef EXPENSIVE_CHECKS
939  verify();
940 #endif
941 }
942 
944  Node &TargetN) {
945  assert((*SourceN)[TargetN].isCall() && "Must start with a call edge!");
946 
947  assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");
948  assert(G->lookupRefSCC(TargetN) != this &&
949  "Target must not be in this RefSCC.");
950 #ifdef EXPENSIVE_CHECKS
951  assert(G->lookupRefSCC(TargetN)->isDescendantOf(*this) &&
952  "Target must be a descendant of the Source.");
953 #endif
954 
955  // Edges between RefSCCs are the same regardless of call or ref, so we can
956  // just flip the edge here.
957  SourceN->setEdgeKind(TargetN, Edge::Ref);
958 
959 #ifdef EXPENSIVE_CHECKS
960  verify();
961 #endif
962 }
963 
965  Node &TargetN) {
966  assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");
967  assert(G->lookupRefSCC(TargetN) == this && "Target must be in this RefSCC.");
968 
969  SourceN->insertEdgeInternal(TargetN, Edge::Ref);
970 
971 #ifdef EXPENSIVE_CHECKS
972  verify();
973 #endif
974 }
975 
977  Edge::Kind EK) {
978  // First insert it into the caller.
979  SourceN->insertEdgeInternal(TargetN, EK);
980 
981  assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");
982 
983  assert(G->lookupRefSCC(TargetN) != this &&
984  "Target must not be in this RefSCC.");
985 #ifdef EXPENSIVE_CHECKS
986  assert(G->lookupRefSCC(TargetN)->isDescendantOf(*this) &&
987  "Target must be a descendant of the Source.");
988 #endif
989 
990 #ifdef EXPENSIVE_CHECKS
991  verify();
992 #endif
993 }
994 
997  assert(G->lookupRefSCC(TargetN) == this && "Target must be in this RefSCC.");
998  RefSCC &SourceC = *G->lookupRefSCC(SourceN);
999  assert(&SourceC != this && "Source must not be in this RefSCC.");
1000 #ifdef EXPENSIVE_CHECKS
1001  assert(SourceC.isDescendantOf(*this) &&
1002  "Source must be a descendant of the Target.");
1003 #endif
1004 
1005  SmallVector<RefSCC *, 1> DeletedRefSCCs;
1006 
1007 #ifdef EXPENSIVE_CHECKS
1008  verify();
1009  auto VerifyOnExit = make_scope_exit([&]() { verify(); });
1010 #endif
1011 
1012  int SourceIdx = G->RefSCCIndices[&SourceC];
1013  int TargetIdx = G->RefSCCIndices[this];
1014  assert(SourceIdx < TargetIdx &&
1015  "Postorder list doesn't see edge as incoming!");
1016 
1017  // Compute the RefSCCs which (transitively) reach the source. We do this by
1018  // working backwards from the source using the parent set in each RefSCC,
1019  // skipping any RefSCCs that don't fall in the postorder range. This has the
1020  // advantage of walking the sparser parent edge (in high fan-out graphs) but
1021  // more importantly this removes examining all forward edges in all RefSCCs
1022  // within the postorder range which aren't in fact connected. Only connected
1023  // RefSCCs (and their edges) are visited here.
1024  auto ComputeSourceConnectedSet = [&](SmallPtrSetImpl<RefSCC *> &Set) {
1025  Set.insert(&SourceC);
1026  auto IsConnected = [&](RefSCC &RC) {
1027  for (SCC &C : RC)
1028  for (Node &N : C)
1029  for (Edge &E : *N)
1030  if (Set.count(G->lookupRefSCC(E.getNode())))
1031  return true;
1032 
1033  return false;
1034  };
1035 
1036  for (RefSCC *C : make_range(G->PostOrderRefSCCs.begin() + SourceIdx + 1,
1037  G->PostOrderRefSCCs.begin() + TargetIdx + 1))
1038  if (IsConnected(*C))
1039  Set.insert(C);
1040  };
1041 
1042  // Use a normal worklist to find which SCCs the target connects to. We still
1043  // bound the search based on the range in the postorder list we care about,
1044  // but because this is forward connectivity we just "recurse" through the
1045  // edges.
1046  auto ComputeTargetConnectedSet = [&](SmallPtrSetImpl<RefSCC *> &Set) {
1047  Set.insert(this);
1048  SmallVector<RefSCC *, 4> Worklist;
1049  Worklist.push_back(this);
1050  do {
1051  RefSCC &RC = *Worklist.pop_back_val();
1052  for (SCC &C : RC)
1053  for (Node &N : C)
1054  for (Edge &E : *N) {
1055  RefSCC &EdgeRC = *G->lookupRefSCC(E.getNode());
1056  if (G->getRefSCCIndex(EdgeRC) <= SourceIdx)
1057  // Not in the postorder sequence between source and target.
1058  continue;
1059 
1060  if (Set.insert(&EdgeRC).second)
1061  Worklist.push_back(&EdgeRC);
1062  }
1063  } while (!Worklist.empty());
1064  };
1065 
1066  // Use a generic helper to update the postorder sequence of RefSCCs and return
1067  // a range of any RefSCCs connected into a cycle by inserting this edge. This
1068  // routine will also take care of updating the indices into the postorder
1069  // sequence.
1072  SourceC, *this, G->PostOrderRefSCCs, G->RefSCCIndices,
1073  ComputeSourceConnectedSet, ComputeTargetConnectedSet);
1074 
1075  // Build a set, so we can do fast tests for whether a RefSCC will end up as
1076  // part of the merged RefSCC.
1077  SmallPtrSet<RefSCC *, 16> MergeSet(MergeRange.begin(), MergeRange.end());
1078 
1079  // This RefSCC will always be part of that set, so just insert it here.
1080  MergeSet.insert(this);
1081 
1082  // Now that we have identified all the SCCs which need to be merged into
1083  // a connected set with the inserted edge, merge all of them into this SCC.
1084  SmallVector<SCC *, 16> MergedSCCs;
1085  int SCCIndex = 0;
1086  for (RefSCC *RC : MergeRange) {
1087  assert(RC != this && "We're merging into the target RefSCC, so it "
1088  "shouldn't be in the range.");
1089 
1090  // Walk the inner SCCs to update their up-pointer and walk all the edges to
1091  // update any parent sets.
1092  // FIXME: We should try to find a way to avoid this (rather expensive) edge
1093  // walk by updating the parent sets in some other manner.
1094  for (SCC &InnerC : *RC) {
1095  InnerC.OuterRefSCC = this;
1096  SCCIndices[&InnerC] = SCCIndex++;
1097  for (Node &N : InnerC)
1098  G->SCCMap[&N] = &InnerC;
1099  }
1100 
1101  // Now merge in the SCCs. We can actually move here so try to reuse storage
1102  // the first time through.
1103  if (MergedSCCs.empty())
1104  MergedSCCs = std::move(RC->SCCs);
1105  else
1106  MergedSCCs.append(RC->SCCs.begin(), RC->SCCs.end());
1107  RC->SCCs.clear();
1108  DeletedRefSCCs.push_back(RC);
1109  }
1110 
1111  // Append our original SCCs to the merged list and move it into place.
1112  for (SCC &InnerC : *this)
1113  SCCIndices[&InnerC] = SCCIndex++;
1114  MergedSCCs.append(SCCs.begin(), SCCs.end());
1115  SCCs = std::move(MergedSCCs);
1116 
1117  // Remove the merged away RefSCCs from the post order sequence.
1118  for (RefSCC *RC : MergeRange)
1119  G->RefSCCIndices.erase(RC);
1120  int IndexOffset = MergeRange.end() - MergeRange.begin();
1121  auto EraseEnd =
1122  G->PostOrderRefSCCs.erase(MergeRange.begin(), MergeRange.end());
1123  for (RefSCC *RC : make_range(EraseEnd, G->PostOrderRefSCCs.end()))
1124  G->RefSCCIndices[RC] -= IndexOffset;
1125 
1126  // At this point we have a merged RefSCC with a post-order SCCs list, just
1127  // connect the nodes to form the new edge.
1128  SourceN->insertEdgeInternal(TargetN, Edge::Ref);
1129 
1130  // We return the list of SCCs which were merged so that callers can
1131  // invalidate any data they have associated with those SCCs. Note that these
1132  // SCCs are no longer in an interesting state (they are totally empty) but
1133  // the pointers will remain stable for the life of the graph itself.
1134  return DeletedRefSCCs;
1135 }
1136 
1138  assert(G->lookupRefSCC(SourceN) == this &&
1139  "The source must be a member of this RefSCC.");
1140  assert(G->lookupRefSCC(TargetN) != this &&
1141  "The target must not be a member of this RefSCC");
1142 
1143 #ifdef EXPENSIVE_CHECKS
1144  verify();
1145  auto VerifyOnExit = make_scope_exit([&]() { verify(); });
1146 #endif
1147 
1148  // First remove it from the node.
1149  bool Removed = SourceN->removeEdgeInternal(TargetN);
1150  (void)Removed;
1151  assert(Removed && "Target not in the edge set for this caller?");
1152 }
1153 
1156  ArrayRef<Node *> TargetNs) {
1157  // We return a list of the resulting *new* RefSCCs in post-order.
1158  SmallVector<RefSCC *, 1> Result;
1159 
1160 #ifdef EXPENSIVE_CHECKS
1161  // Verify the RefSCC is valid to start with and that either we return an empty
1162  // list of result RefSCCs and this RefSCC remains valid, or we return new
1163  // RefSCCs and this RefSCC is dead.
1164  verify();
1165  auto VerifyOnExit = make_scope_exit([&]() {
1166  // If we didn't replace our RefSCC with new ones, check that this one
1167  // remains valid.
1168  if (G)
1169  verify();
1170  });
1171 #endif
1172 
1173  // First remove the actual edges.
1174  for (Node *TargetN : TargetNs) {
1175  assert(!(*SourceN)[*TargetN].isCall() &&
1176  "Cannot remove a call edge, it must first be made a ref edge");
1177 
1178  bool Removed = SourceN->removeEdgeInternal(*TargetN);
1179  (void)Removed;
1180  assert(Removed && "Target not in the edge set for this caller?");
1181  }
1182 
1183  // Direct self references don't impact the ref graph at all.
1184  if (llvm::all_of(TargetNs,
1185  [&](Node *TargetN) { return &SourceN == TargetN; }))
1186  return Result;
1187 
1188  // If all targets are in the same SCC as the source, because no call edges
1189  // were removed there is no RefSCC structure change.
1190  SCC &SourceC = *G->lookupSCC(SourceN);
1191  if (llvm::all_of(TargetNs, [&](Node *TargetN) {
1192  return G->lookupSCC(*TargetN) == &SourceC;
1193  }))
1194  return Result;
1195 
1196  // We build somewhat synthetic new RefSCCs by providing a postorder mapping
1197  // for each inner SCC. We store these inside the low-link field of the nodes
1198  // rather than associated with SCCs because this saves a round-trip through
1199  // the node->SCC map and in the common case, SCCs are small. We will verify
1200  // that we always give the same number to every node in the SCC such that
1201  // these are equivalent.
1202  int PostOrderNumber = 0;
1203 
1204  // Reset all the other nodes to prepare for a DFS over them, and add them to
1205  // our worklist.
1206  SmallVector<Node *, 8> Worklist;
1207  for (SCC *C : SCCs) {
1208  for (Node &N : *C)
1209  N.DFSNumber = N.LowLink = 0;
1210 
1211  Worklist.append(C->Nodes.begin(), C->Nodes.end());
1212  }
1213 
1214  // Track the number of nodes in this RefSCC so that we can quickly recognize
1215  // an important special case of the edge removal not breaking the cycle of
1216  // this RefSCC.
1217  const int NumRefSCCNodes = Worklist.size();
1218 
1220  SmallVector<Node *, 4> PendingRefSCCStack;
1221  do {
1222  assert(DFSStack.empty() &&
1223  "Cannot begin a new root with a non-empty DFS stack!");
1224  assert(PendingRefSCCStack.empty() &&
1225  "Cannot begin a new root with pending nodes for an SCC!");
1226 
1227  Node *RootN = Worklist.pop_back_val();
1228  // Skip any nodes we've already reached in the DFS.
1229  if (RootN->DFSNumber != 0) {
1230  assert(RootN->DFSNumber == -1 &&
1231  "Shouldn't have any mid-DFS root nodes!");
1232  continue;
1233  }
1234 
1235  RootN->DFSNumber = RootN->LowLink = 1;
1236  int NextDFSNumber = 2;
1237 
1238  DFSStack.emplace_back(RootN, (*RootN)->begin());
1239  do {
1240  auto [N, I] = DFSStack.pop_back_val();
1241  auto E = (*N)->end();
1242 
1243  assert(N->DFSNumber != 0 && "We should always assign a DFS number "
1244  "before processing a node.");
1245 
1246  while (I != E) {
1247  Node &ChildN = I->getNode();
1248  if (ChildN.DFSNumber == 0) {
1249  // Mark that we should start at this child when next this node is the
1250  // top of the stack. We don't start at the next child to ensure this
1251  // child's lowlink is reflected.
1252  DFSStack.emplace_back(N, I);
1253 
1254  // Continue, resetting to the child node.
1255  ChildN.LowLink = ChildN.DFSNumber = NextDFSNumber++;
1256  N = &ChildN;
1257  I = ChildN->begin();
1258  E = ChildN->end();
1259  continue;
1260  }
1261  if (ChildN.DFSNumber == -1) {
1262  // If this child isn't currently in this RefSCC, no need to process
1263  // it.
1264  ++I;
1265  continue;
1266  }
1267 
1268  // Track the lowest link of the children, if any are still in the stack.
1269  // Any child not on the stack will have a LowLink of -1.
1270  assert(ChildN.LowLink != 0 &&
1271  "Low-link must not be zero with a non-zero DFS number.");
1272  if (ChildN.LowLink >= 0 && ChildN.LowLink < N->LowLink)
1273  N->LowLink = ChildN.LowLink;
1274  ++I;
1275  }
1276 
1277  // We've finished processing N and its descendants, put it on our pending
1278  // stack to eventually get merged into a RefSCC.
1279  PendingRefSCCStack.push_back(N);
1280 
1281  // If this node is linked to some lower entry, continue walking up the
1282  // stack.
1283  if (N->LowLink != N->DFSNumber) {
1284  assert(!DFSStack.empty() &&
1285  "We never found a viable root for a RefSCC to pop off!");
1286  continue;
1287  }
1288 
1289  // Otherwise, form a new RefSCC from the top of the pending node stack.
1290  int RefSCCNumber = PostOrderNumber++;
1291  int RootDFSNumber = N->DFSNumber;
1292 
1293  // Find the range of the node stack by walking down until we pass the
1294  // root DFS number. Update the DFS numbers and low link numbers in the
1295  // process to avoid re-walking this list where possible.
1296  auto StackRI = find_if(reverse(PendingRefSCCStack), [&](Node *N) {
1297  if (N->DFSNumber < RootDFSNumber)
1298  // We've found the bottom.
1299  return true;
1300 
1301  // Update this node and keep scanning.
1302  N->DFSNumber = -1;
1303  // Save the post-order number in the lowlink field so that we can use
1304  // it to map SCCs into new RefSCCs after we finish the DFS.
1305  N->LowLink = RefSCCNumber;
1306  return false;
1307  });
1308  auto RefSCCNodes = make_range(StackRI.base(), PendingRefSCCStack.end());
1309 
1310  // If we find a cycle containing all nodes originally in this RefSCC then
1311  // the removal hasn't changed the structure at all. This is an important
1312  // special case, and we can directly exit the entire routine more
1313  // efficiently as soon as we discover it.
1314  if (llvm::size(RefSCCNodes) == NumRefSCCNodes) {
1315  // Clear out the low link field as we won't need it.
1316  for (Node *N : RefSCCNodes)
1317  N->LowLink = -1;
1318  // Return the empty result immediately.
1319  return Result;
1320  }
1321 
1322  // We've already marked the nodes internally with the RefSCC number so
1323  // just clear them off the stack and continue.
1324  PendingRefSCCStack.erase(RefSCCNodes.begin(), PendingRefSCCStack.end());
1325  } while (!DFSStack.empty());
1326 
1327  assert(DFSStack.empty() && "Didn't flush the entire DFS stack!");
1328  assert(PendingRefSCCStack.empty() && "Didn't flush all pending nodes!");
1329  } while (!Worklist.empty());
1330 
1331  assert(PostOrderNumber > 1 &&
1332  "Should never finish the DFS when the existing RefSCC remains valid!");
1333 
1334  // Otherwise we create a collection of new RefSCC nodes and build
1335  // a radix-sort style map from postorder number to these new RefSCCs. We then
1336  // append SCCs to each of these RefSCCs in the order they occurred in the
1337  // original SCCs container.
1338  for (int I = 0; I < PostOrderNumber; ++I)
1339  Result.push_back(G->createRefSCC(*G));
1340 
1341  // Insert the resulting postorder sequence into the global graph postorder
1342  // sequence before the current RefSCC in that sequence, and then remove the
1343  // current one.
1344  //
1345  // FIXME: It'd be nice to change the APIs so that we returned an iterator
1346  // range over the global postorder sequence and generally use that sequence
1347  // rather than building a separate result vector here.
1348  int Idx = G->getRefSCCIndex(*this);
1349  G->PostOrderRefSCCs.erase(G->PostOrderRefSCCs.begin() + Idx);
1350  G->PostOrderRefSCCs.insert(G->PostOrderRefSCCs.begin() + Idx, Result.begin(),
1351  Result.end());
1352  for (int I : seq<int>(Idx, G->PostOrderRefSCCs.size()))
1353  G->RefSCCIndices[G->PostOrderRefSCCs[I]] = I;
1354 
1355  for (SCC *C : SCCs) {
1356  // We store the SCC number in the node's low-link field above.
1357  int SCCNumber = C->begin()->LowLink;
1358  // Clear out all the SCC's node's low-link fields now that we're done
1359  // using them as side-storage.
1360  for (Node &N : *C) {
1361  assert(N.LowLink == SCCNumber &&
1362  "Cannot have different numbers for nodes in the same SCC!");
1363  N.LowLink = -1;
1364  }
1365 
1366  RefSCC &RC = *Result[SCCNumber];
1367  int SCCIndex = RC.SCCs.size();
1368  RC.SCCs.push_back(C);
1369  RC.SCCIndices[C] = SCCIndex;
1370  C->OuterRefSCC = &RC;
1371  }
1372 
1373  // Now that we've moved things into the new RefSCCs, clear out our current
1374  // one.
1375  G = nullptr;
1376  SCCs.clear();
1377  SCCIndices.clear();
1378 
1379 #ifdef EXPENSIVE_CHECKS
1380  // Verify the new RefSCCs we've built.
1381  for (RefSCC *RC : Result)
1382  RC->verify();
1383 #endif
1384 
1385  // Return the new list of SCCs.
1386  return Result;
1387 }
1388 
1390  Node &TargetN) {
1391 #ifdef EXPENSIVE_CHECKS
1392  auto ExitVerifier = make_scope_exit([this] { verify(); });
1393 
1394  // Check that we aren't breaking some invariants of the SCC graph. Note that
1395  // this is quadratic in the number of edges in the call graph!
1396  SCC &SourceC = *G->lookupSCC(SourceN);
1397  SCC &TargetC = *G->lookupSCC(TargetN);
1398  if (&SourceC != &TargetC)
1399  assert(SourceC.isAncestorOf(TargetC) &&
1400  "Call edge is not trivial in the SCC graph!");
1401 #endif
1402 
1403  // First insert it into the source or find the existing edge.
1404  auto [Iterator, Inserted] =
1405  SourceN->EdgeIndexMap.try_emplace(&TargetN, SourceN->Edges.size());
1406  if (!Inserted) {
1407  // Already an edge, just update it.
1408  Edge &E = SourceN->Edges[Iterator->second];
1409  if (E.isCall())
1410  return; // Nothing to do!
1411  E.setKind(Edge::Call);
1412  } else {
1413  // Create the new edge.
1414  SourceN->Edges.emplace_back(TargetN, Edge::Call);
1415  }
1416 }
1417 
1419 #ifdef EXPENSIVE_CHECKS
1420  auto ExitVerifier = make_scope_exit([this] { verify(); });
1421 
1422  // Check that we aren't breaking some invariants of the RefSCC graph.
1423  RefSCC &SourceRC = *G->lookupRefSCC(SourceN);
1424  RefSCC &TargetRC = *G->lookupRefSCC(TargetN);
1425  if (&SourceRC != &TargetRC)
1426  assert(SourceRC.isAncestorOf(TargetRC) &&
1427  "Ref edge is not trivial in the RefSCC graph!");
1428 #endif
1429 
1430  // First insert it into the source or find the existing edge.
1431  auto [Iterator, Inserted] =
1432  SourceN->EdgeIndexMap.try_emplace(&TargetN, SourceN->Edges.size());
1433  (void)Iterator;
1434  if (!Inserted)
1435  // Already an edge, we're done.
1436  return;
1437 
1438  // Create the new edge.
1439  SourceN->Edges.emplace_back(TargetN, Edge::Ref);
1440 }
1441 
1443  Function &OldF = N.getFunction();
1444 
1445 #ifdef EXPENSIVE_CHECKS
1446  auto ExitVerifier = make_scope_exit([this] { verify(); });
1447 
1448  assert(G->lookupRefSCC(N) == this &&
1449  "Cannot replace the function of a node outside this RefSCC.");
1450 
1451  assert(G->NodeMap.find(&NewF) == G->NodeMap.end() &&
1452  "Must not have already walked the new function!'");
1453 
1454  // It is important that this replacement not introduce graph changes so we
1455  // insist that the caller has already removed every use of the original
1456  // function and that all uses of the new function correspond to existing
1457  // edges in the graph. The common and expected way to use this is when
1458  // replacing the function itself in the IR without changing the call graph
1459  // shape and just updating the analysis based on that.
1460  assert(&OldF != &NewF && "Cannot replace a function with itself!");
1461  assert(OldF.use_empty() &&
1462  "Must have moved all uses from the old function to the new!");
1463 #endif
1464 
1465  N.replaceFunction(NewF);
1466 
1467  // Update various call graph maps.
1468  G->NodeMap.erase(&OldF);
1469  G->NodeMap[&NewF] = &N;
1470 
1471  // Update lib functions.
1472  if (G->isLibFunction(OldF)) {
1473  G->LibFunctions.remove(&OldF);
1474  G->LibFunctions.insert(&NewF);
1475  }
1476 }
1477 
1478 void LazyCallGraph::insertEdge(Node &SourceN, Node &TargetN, Edge::Kind EK) {
1479  assert(SCCMap.empty() &&
1480  "This method cannot be called after SCCs have been formed!");
1481 
1482  return SourceN->insertEdgeInternal(TargetN, EK);
1483 }
1484 
1485 void LazyCallGraph::removeEdge(Node &SourceN, Node &TargetN) {
1486  assert(SCCMap.empty() &&
1487  "This method cannot be called after SCCs have been formed!");
1488 
1489  bool Removed = SourceN->removeEdgeInternal(TargetN);
1490  (void)Removed;
1491  assert(Removed && "Target not in the edge set for this caller?");
1492 }
1493 
1495  // FIXME: This is unnecessarily restrictive. We should be able to remove
1496  // functions which recursively call themselves.
1497  assert(F.hasZeroLiveUses() &&
1498  "This routine should only be called on trivially dead functions!");
1499 
1500  // We shouldn't remove library functions as they are never really dead while
1501  // the call graph is in use -- every function definition refers to them.
1502  assert(!isLibFunction(F) &&
1503  "Must not remove lib functions from the call graph!");
1504 
1505  auto NI = NodeMap.find(&F);
1506  if (NI == NodeMap.end())
1507  // Not in the graph at all!
1508  return;
1509 
1510  Node &N = *NI->second;
1511 
1512  // Cannot remove a function which has yet to be visited in the DFS walk, so
1513  // if we have a node at all then we must have an SCC and RefSCC.
1514  auto CI = SCCMap.find(&N);
1515  assert(CI != SCCMap.end() &&
1516  "Tried to remove a node without an SCC after DFS walk started!");
1517  SCC &C = *CI->second;
1518  RefSCC *RC = &C.getOuterRefSCC();
1519 
1520  // In extremely rare cases, we can delete a dead function which is still in a
1521  // non-trivial RefSCC. This can happen due to spurious ref edges sticking
1522  // around after an IR function reference is removed.
1523  if (RC->size() != 1) {
1524  SmallVector<Node *, 0> NodesInRC;
1525  for (SCC &OtherC : *RC) {
1526  for (Node &OtherN : OtherC)
1527  NodesInRC.push_back(&OtherN);
1528  }
1529  for (Node *OtherN : NodesInRC) {
1530  if ((*OtherN)->lookup(N)) {
1531  auto NewRefSCCs =
1532  RC->removeInternalRefEdge(*OtherN, ArrayRef<Node *>(&N));
1533  // If we've split into multiple RefSCCs, RC is now invalid and the
1534  // RefSCC containing C will be different.
1535  if (!NewRefSCCs.empty())
1536  RC = &C.getOuterRefSCC();
1537  }
1538  }
1539  }
1540 
1541  NodeMap.erase(NI);
1542  EntryEdges.removeEdgeInternal(N);
1543  SCCMap.erase(CI);
1544 
1545  // This node must be the only member of its SCC as it has no callers, and
1546  // that SCC must be the only member of a RefSCC as it has no references.
1547  // Validate these properties first.
1548  assert(C.size() == 1 && "Dead functions must be in a singular SCC");
1549  assert(RC->size() == 1 && "Dead functions must be in a singular RefSCC");
1550 
1551  // Finally clear out all the data structures from the node down through the
1552  // components. postorder_ref_scc_iterator will skip empty RefSCCs, so no need
1553  // to adjust LazyCallGraph data structures.
1554  N.clear();
1555  N.G = nullptr;
1556  N.F = nullptr;
1557  C.clear();
1558  RC->clear();
1559  RC->G = nullptr;
1560 
1561  // Nothing to delete as all the objects are allocated in stable bump pointer
1562  // allocators.
1563 }
1564 
1565 // Gets the Edge::Kind from one function to another by looking at the function's
1566 // instructions. Asserts if there is no edge.
1567 // Useful for determining what type of edge should exist between functions when
1568 // the edge hasn't been created yet.
1570  Function &NewFunction) {
1571  // In release builds, assume that if there are no direct calls to the new
1572  // function, then there is a ref edge. In debug builds, keep track of
1573  // references to assert that there is actually a ref edge if there is no call
1574  // edge.
1575 #ifndef NDEBUG
1576  SmallVector<Constant *, 16> Worklist;
1578 #endif
1579 
1580  for (Instruction &I : instructions(OriginalFunction)) {
1581  if (auto *CB = dyn_cast<CallBase>(&I)) {
1582  if (Function *Callee = CB->getCalledFunction()) {
1583  if (Callee == &NewFunction)
1585  }
1586  }
1587 #ifndef NDEBUG
1588  for (Value *Op : I.operand_values()) {
1589  if (Constant *C = dyn_cast<Constant>(Op)) {
1590  if (Visited.insert(C).second)
1591  Worklist.push_back(C);
1592  }
1593  }
1594 #endif
1595  }
1596 
1597 #ifndef NDEBUG
1598  bool FoundNewFunction = false;
1599  LazyCallGraph::visitReferences(Worklist, Visited, [&](Function &F) {
1600  if (&F == &NewFunction)
1601  FoundNewFunction = true;
1602  });
1603  assert(FoundNewFunction && "No edge from original function to new function");
1604 #endif
1605 
1606  return LazyCallGraph::Edge::Kind::Ref;
1607 }
1608 
1610  Function &NewFunction) {
1611  assert(lookup(OriginalFunction) &&
1612  "Original function's node should already exist");
1613  Node &OriginalN = get(OriginalFunction);
1614  SCC *OriginalC = lookupSCC(OriginalN);
1615  RefSCC *OriginalRC = lookupRefSCC(OriginalN);
1616 
1617 #ifdef EXPENSIVE_CHECKS
1618  OriginalRC->verify();
1619  auto VerifyOnExit = make_scope_exit([&]() { OriginalRC->verify(); });
1620 #endif
1621 
1622  assert(!lookup(NewFunction) &&
1623  "New function's node should not already exist");
1624  Node &NewN = initNode(NewFunction);
1625 
1626  Edge::Kind EK = getEdgeKind(OriginalFunction, NewFunction);
1627 
1628  SCC *NewC = nullptr;
1629  for (Edge &E : *NewN) {
1630  Node &EN = E.getNode();
1631  if (EK == Edge::Kind::Call && E.isCall() && lookupSCC(EN) == OriginalC) {
1632  // If the edge to the new function is a call edge and there is a call edge
1633  // from the new function to any function in the original function's SCC,
1634  // it is in the same SCC (and RefSCC) as the original function.
1635  NewC = OriginalC;
1636  NewC->Nodes.push_back(&NewN);
1637  break;
1638  }
1639  }
1640 
1641  if (!NewC) {
1642  for (Edge &E : *NewN) {
1643  Node &EN = E.getNode();
1644  if (lookupRefSCC(EN) == OriginalRC) {
1645  // If there is any edge from the new function to any function in the
1646  // original function's RefSCC, it is in the same RefSCC as the original
1647  // function but a new SCC.
1648  RefSCC *NewRC = OriginalRC;
1649  NewC = createSCC(*NewRC, SmallVector<Node *, 1>({&NewN}));
1650 
1651  // The new function's SCC is not the same as the original function's
1652  // SCC, since that case was handled earlier. If the edge from the
1653  // original function to the new function was a call edge, then we need
1654  // to insert the newly created function's SCC before the original
1655  // function's SCC. Otherwise, either the new SCC comes after the
1656  // original function's SCC, or it doesn't matter, and in both cases we
1657  // can add it to the very end.
1658  int InsertIndex = EK == Edge::Kind::Call ? NewRC->SCCIndices[OriginalC]
1659  : NewRC->SCCIndices.size();
1660  NewRC->SCCs.insert(NewRC->SCCs.begin() + InsertIndex, NewC);
1661  for (int I = InsertIndex, Size = NewRC->SCCs.size(); I < Size; ++I)
1662  NewRC->SCCIndices[NewRC->SCCs[I]] = I;
1663 
1664  break;
1665  }
1666  }
1667  }
1668 
1669  if (!NewC) {
1670  // We didn't find any edges back to the original function's RefSCC, so the
1671  // new function belongs in a new RefSCC. The new RefSCC goes before the
1672  // original function's RefSCC.
1673  RefSCC *NewRC = createRefSCC(*this);
1674  NewC = createSCC(*NewRC, SmallVector<Node *, 1>({&NewN}));
1675  NewRC->SCCIndices[NewC] = 0;
1676  NewRC->SCCs.push_back(NewC);
1677  auto OriginalRCIndex = RefSCCIndices.find(OriginalRC)->second;
1678  PostOrderRefSCCs.insert(PostOrderRefSCCs.begin() + OriginalRCIndex, NewRC);
1679  for (int I = OriginalRCIndex, Size = PostOrderRefSCCs.size(); I < Size; ++I)
1680  RefSCCIndices[PostOrderRefSCCs[I]] = I;
1681  }
1682 
1683  SCCMap[&NewN] = NewC;
1684 
1685  OriginalN->insertEdgeInternal(NewN, EK);
1686 }
1687 
1689  Function &OriginalFunction, ArrayRef<Function *> NewFunctions) {
1690  assert(!NewFunctions.empty() && "Can't add zero functions");
1691  assert(lookup(OriginalFunction) &&
1692  "Original function's node should already exist");
1693  Node &OriginalN = get(OriginalFunction);
1694  RefSCC *OriginalRC = lookupRefSCC(OriginalN);
1695 
1696 #ifdef EXPENSIVE_CHECKS
1697  OriginalRC->verify();
1698  auto VerifyOnExit = make_scope_exit([&]() {
1699  OriginalRC->verify();
1700  for (Function *NewFunction : NewFunctions)
1701  lookupRefSCC(get(*NewFunction))->verify();
1702  });
1703 #endif
1704 
1705  bool ExistsRefToOriginalRefSCC = false;
1706 
1707  for (Function *NewFunction : NewFunctions) {
1708  Node &NewN = initNode(*NewFunction);
1709 
1710  OriginalN->insertEdgeInternal(NewN, Edge::Kind::Ref);
1711 
1712  // Check if there is any edge from any new function back to any function in
1713  // the original function's RefSCC.
1714  for (Edge &E : *NewN) {
1715  if (lookupRefSCC(E.getNode()) == OriginalRC) {
1716  ExistsRefToOriginalRefSCC = true;
1717  break;
1718  }
1719  }
1720  }
1721 
1722  RefSCC *NewRC;
1723  if (ExistsRefToOriginalRefSCC) {
1724  // If there is any edge from any new function to any function in the
1725  // original function's RefSCC, all new functions will be in the same RefSCC
1726  // as the original function.
1727  NewRC = OriginalRC;
1728  } else {
1729  // Otherwise the new functions are in their own RefSCC.
1730  NewRC = createRefSCC(*this);
1731  // The new RefSCC goes before the original function's RefSCC in postorder
1732  // since there are only edges from the original function's RefSCC to the new
1733  // RefSCC.
1734  auto OriginalRCIndex = RefSCCIndices.find(OriginalRC)->second;
1735  PostOrderRefSCCs.insert(PostOrderRefSCCs.begin() + OriginalRCIndex, NewRC);
1736  for (int I = OriginalRCIndex, Size = PostOrderRefSCCs.size(); I < Size; ++I)
1737  RefSCCIndices[PostOrderRefSCCs[I]] = I;
1738  }
1739 
1740  for (Function *NewFunction : NewFunctions) {
1741  Node &NewN = get(*NewFunction);
1742  // Each new function is in its own new SCC. The original function can only
1743  // have a ref edge to new functions, and no other existing functions can
1744  // have references to new functions. Each new function only has a ref edge
1745  // to the other new functions.
1746  SCC *NewC = createSCC(*NewRC, SmallVector<Node *, 1>({&NewN}));
1747  // The new SCCs are either sibling SCCs or parent SCCs to all other existing
1748  // SCCs in the RefSCC. Either way, they can go at the back of the postorder
1749  // SCC list.
1750  auto Index = NewRC->SCCIndices.size();
1751  NewRC->SCCIndices[NewC] = Index;
1752  NewRC->SCCs.push_back(NewC);
1753  SCCMap[&NewN] = NewC;
1754  }
1755 
1756 #ifndef NDEBUG
1757  for (Function *F1 : NewFunctions) {
1758  assert(getEdgeKind(OriginalFunction, *F1) == Edge::Kind::Ref &&
1759  "Expected ref edges from original function to every new function");
1760  Node &N1 = get(*F1);
1761  for (Function *F2 : NewFunctions) {
1762  if (F1 == F2)
1763  continue;
1764  Node &N2 = get(*F2);
1765  assert(!N1->lookup(N2)->isCall() &&
1766  "Edges between new functions must be ref edges");
1767  }
1768  }
1769 #endif
1770 }
1771 
1772 LazyCallGraph::Node &LazyCallGraph::insertInto(Function &F, Node *&MappedN) {
1773  return *new (MappedN = BPA.Allocate()) Node(*this, F);
1774 }
1775 
1776 void LazyCallGraph::updateGraphPtrs() {
1777  // Walk the node map to update their graph pointers. While this iterates in
1778  // an unstable order, the order has no effect, so it remains correct.
1779  for (auto &FunctionNodePair : NodeMap)
1780  FunctionNodePair.second->G = this;
1781 
1782  for (auto *RC : PostOrderRefSCCs)
1783  RC->G = this;
1784 }
1785 
1786 LazyCallGraph::Node &LazyCallGraph::initNode(Function &F) {
1787  Node &N = get(F);
1788  N.DFSNumber = N.LowLink = -1;
1789  N.populate();
1790  NodeMap[&F] = &N;
1791  return N;
1792 }
1793 
1794 template <typename RootsT, typename GetBeginT, typename GetEndT,
1795  typename GetNodeT, typename FormSCCCallbackT>
1796 void LazyCallGraph::buildGenericSCCs(RootsT &&Roots, GetBeginT &&GetBegin,
1797  GetEndT &&GetEnd, GetNodeT &&GetNode,
1798  FormSCCCallbackT &&FormSCC) {
1799  using EdgeItT = decltype(GetBegin(std::declval<Node &>()));
1800 
1802  SmallVector<Node *, 16> PendingSCCStack;
1803 
1804  // Scan down the stack and DFS across the call edges.
1805  for (Node *RootN : Roots) {
1806  assert(DFSStack.empty() &&
1807  "Cannot begin a new root with a non-empty DFS stack!");
1808  assert(PendingSCCStack.empty() &&
1809  "Cannot begin a new root with pending nodes for an SCC!");
1810 
1811  // Skip any nodes we've already reached in the DFS.
1812  if (RootN->DFSNumber != 0) {
1813  assert(RootN->DFSNumber == -1 &&
1814  "Shouldn't have any mid-DFS root nodes!");
1815  continue;
1816  }
1817 
1818  RootN->DFSNumber = RootN->LowLink = 1;
1819  int NextDFSNumber = 2;
1820 
1821  DFSStack.emplace_back(RootN, GetBegin(*RootN));
1822  do {
1823  auto [N, I] = DFSStack.pop_back_val();
1824  auto E = GetEnd(*N);
1825  while (I != E) {
1826  Node &ChildN = GetNode(I);
1827  if (ChildN.DFSNumber == 0) {
1828  // We haven't yet visited this child, so descend, pushing the current
1829  // node onto the stack.
1830  DFSStack.emplace_back(N, I);
1831 
1832  ChildN.DFSNumber = ChildN.LowLink = NextDFSNumber++;
1833  N = &ChildN;
1834  I = GetBegin(*N);
1835  E = GetEnd(*N);
1836  continue;
1837  }
1838 
1839  // If the child has already been added to some child component, it
1840  // couldn't impact the low-link of this parent because it isn't
1841  // connected, and thus its low-link isn't relevant so skip it.
1842  if (ChildN.DFSNumber == -1) {
1843  ++I;
1844  continue;
1845  }
1846 
1847  // Track the lowest linked child as the lowest link for this node.
1848  assert(ChildN.LowLink > 0 && "Must have a positive low-link number!");
1849  if (ChildN.LowLink < N->LowLink)
1850  N->LowLink = ChildN.LowLink;
1851 
1852  // Move to the next edge.
1853  ++I;
1854  }
1855 
1856  // We've finished processing N and its descendants, put it on our pending
1857  // SCC stack to eventually get merged into an SCC of nodes.
1858  PendingSCCStack.push_back(N);
1859 
1860  // If this node is linked to some lower entry, continue walking up the
1861  // stack.
1862  if (N->LowLink != N->DFSNumber)
1863  continue;
1864 
1865  // Otherwise, we've completed an SCC. Append it to our post order list of
1866  // SCCs.
1867  int RootDFSNumber = N->DFSNumber;
1868  // Find the range of the node stack by walking down until we pass the
1869  // root DFS number.
1870  auto SCCNodes = make_range(
1871  PendingSCCStack.rbegin(),
1872  find_if(reverse(PendingSCCStack), [RootDFSNumber](const Node *N) {
1873  return N->DFSNumber < RootDFSNumber;
1874  }));
1875  // Form a new SCC out of these nodes and then clear them off our pending
1876  // stack.
1877  FormSCC(SCCNodes);
1878  PendingSCCStack.erase(SCCNodes.end().base(), PendingSCCStack.end());
1879  } while (!DFSStack.empty());
1880  }
1881 }
1882 
1883 /// Build the internal SCCs for a RefSCC from a sequence of nodes.
1884 ///
1885 /// Appends the SCCs to the provided vector and updates the map with their
1886 /// indices. Both the vector and map must be empty when passed into this
1887 /// routine.
1888 void LazyCallGraph::buildSCCs(RefSCC &RC, node_stack_range Nodes) {
1889  assert(RC.SCCs.empty() && "Already built SCCs!");
1890  assert(RC.SCCIndices.empty() && "Already mapped SCC indices!");
1891 
1892  for (Node *N : Nodes) {
1893  assert(N->LowLink >= (*Nodes.begin())->LowLink &&
1894  "We cannot have a low link in an SCC lower than its root on the "
1895  "stack!");
1896 
1897  // This node will go into the next RefSCC, clear out its DFS and low link
1898  // as we scan.
1899  N->DFSNumber = N->LowLink = 0;
1900  }
1901 
1902  // Each RefSCC contains a DAG of the call SCCs. To build these, we do
1903  // a direct walk of the call edges using Tarjan's algorithm. We reuse the
1904  // internal storage as we won't need it for the outer graph's DFS any longer.
1905  buildGenericSCCs(
1906  Nodes, [](Node &N) { return N->call_begin(); },
1907  [](Node &N) { return N->call_end(); },
1908  [](EdgeSequence::call_iterator I) -> Node & { return I->getNode(); },
1909  [this, &RC](node_stack_range Nodes) {
1910  RC.SCCs.push_back(createSCC(RC, Nodes));
1911  for (Node &N : *RC.SCCs.back()) {
1912  N.DFSNumber = N.LowLink = -1;
1913  SCCMap[&N] = RC.SCCs.back();
1914  }
1915  });
1916 
1917  // Wire up the SCC indices.
1918  for (int I = 0, Size = RC.SCCs.size(); I < Size; ++I)
1919  RC.SCCIndices[RC.SCCs[I]] = I;
1920 }
1921 
1923  if (EntryEdges.empty() || !PostOrderRefSCCs.empty())
1924  // RefSCCs are either non-existent or already built!
1925  return;
1926 
1927  assert(RefSCCIndices.empty() && "Already mapped RefSCC indices!");
1928 
1930  for (Edge &E : *this)
1931  Roots.push_back(&E.getNode());
1932 
1933  // The roots will be iterated in order.
1934  buildGenericSCCs(
1935  Roots,
1936  [](Node &N) {
1937  // We need to populate each node as we begin to walk its edges.
1938  N.populate();
1939  return N->begin();
1940  },
1941  [](Node &N) { return N->end(); },
1942  [](EdgeSequence::iterator I) -> Node & { return I->getNode(); },
1943  [this](node_stack_range Nodes) {
1944  RefSCC *NewRC = createRefSCC(*this);
1945  buildSCCs(*NewRC, Nodes);
1946 
1947  // Push the new node into the postorder list and remember its position
1948  // in the index map.
1949  bool Inserted =
1950  RefSCCIndices.try_emplace(NewRC, PostOrderRefSCCs.size()).second;
1951  (void)Inserted;
1952  assert(Inserted && "Cannot already have this RefSCC in the index map!");
1953  PostOrderRefSCCs.push_back(NewRC);
1954 #ifdef EXPENSIVE_CHECKS
1955  NewRC->verify();
1956 #endif
1957  });
1958 }
1959 
1961  SmallPtrSetImpl<Constant *> &Visited,
1962  function_ref<void(Function &)> Callback) {
1963  while (!Worklist.empty()) {
1964  Constant *C = Worklist.pop_back_val();
1965 
1966  if (Function *F = dyn_cast<Function>(C)) {
1967  if (!F->isDeclaration())
1968  Callback(*F);
1969  continue;
1970  }
1971 
1972  // blockaddresses are weird and don't participate in the call graph anyway,
1973  // skip them.
1974  if (isa<BlockAddress>(C))
1975  continue;
1976 
1977  for (Value *Op : C->operand_values())
1978  if (Visited.insert(cast<Constant>(Op)).second)
1979  Worklist.push_back(cast<Constant>(Op));
1980  }
1981 }
1982 
1983 AnalysisKey LazyCallGraphAnalysis::Key;
1984 
1986 
1988  OS << " Edges in function: " << N.getFunction().getName() << "\n";
1989  for (LazyCallGraph::Edge &E : N.populate())
1990  OS << " " << (E.isCall() ? "call" : "ref ") << " -> "
1991  << E.getFunction().getName() << "\n";
1992 
1993  OS << "\n";
1994 }
1995 
1997  OS << " SCC with " << C.size() << " functions:\n";
1998 
1999  for (LazyCallGraph::Node &N : C)
2000  OS << " " << N.getFunction().getName() << "\n";
2001 }
2002 
2004  OS << " RefSCC with " << C.size() << " call SCCs:\n";
2005 
2006  for (LazyCallGraph::SCC &InnerC : C)
2007  printSCC(OS, InnerC);
2008 
2009  OS << "\n";
2010 }
2011 
2013  ModuleAnalysisManager &AM) {
2015 
2016  OS << "Printing the call graph for module: " << M.getModuleIdentifier()
2017  << "\n\n";
2018 
2019  for (Function &F : M)
2020  printNode(OS, G.get(F));
2021 
2022  G.buildRefSCCs();
2023  for (LazyCallGraph::RefSCC &C : G.postorder_ref_sccs())
2024  printRefSCC(OS, C);
2025 
2026  return PreservedAnalyses::all();
2027 }
2028 
2030  : OS(OS) {}
2031 
2033  std::string Name =
2034  "\"" + DOT::EscapeString(std::string(N.getFunction().getName())) + "\"";
2035 
2036  for (LazyCallGraph::Edge &E : N.populate()) {
2037  OS << " " << Name << " -> \""
2038  << DOT::EscapeString(std::string(E.getFunction().getName())) << "\"";
2039  if (!E.isCall()) // It is a ref edge.
2040  OS << " [style=dashed,label=\"ref\"]";
2041  OS << ";\n";
2042  }
2043 
2044  OS << "\n";
2045 }
2046 
2048  ModuleAnalysisManager &AM) {
2050 
2051  OS << "digraph \"" << DOT::EscapeString(M.getModuleIdentifier()) << "\" {\n";
2052 
2053  for (Function &F : M)
2054  printNodeDOT(OS, G.get(F));
2055 
2056  OS << "}\n";
2057 
2058  return PreservedAnalyses::all();
2059 }
llvm::Check::Size
@ Size
Definition: FileCheck.h:77
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm::LazyCallGraph::SCC::isParentOf
bool isParentOf(const SCC &C) const
Test if this SCC is a parent of C.
Definition: LazyCallGraph.cpp:276
getName
static StringRef getName(Value *V)
Definition: ProvenanceAnalysisEvaluator.cpp:20
llvm::LazyCallGraphPrinterPass::LazyCallGraphPrinterPass
LazyCallGraphPrinterPass(raw_ostream &OS)
Definition: LazyCallGraph.cpp:1985
LLVM_DUMP_METHOD
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:492
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::SmallVectorImpl::erase
iterator erase(const_iterator CI)
Definition: SmallVector.h:741
llvm::LazyCallGraph::buildRefSCCs
void buildRefSCCs()
Definition: LazyCallGraph.cpp:1922
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
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::drop_begin
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
Definition: STLExtras.h:387
llvm::LazyCallGraph::LazyCallGraph
LazyCallGraph(Module &M, function_ref< TargetLibraryInfo &(Function &)> GetTLI)
Construct a graph for the given module.
Definition: LazyCallGraph.cpp:154
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:774
InstIterator.h
llvm::Function
Definition: Function.h:60
llvm::LazyCallGraph::insertEdge
void insertEdge(Node &SourceN, Node &TargetN, Edge::Kind EK)
Update the call graph after inserting a new edge.
Definition: LazyCallGraph.cpp:1478
llvm::LazyCallGraph::RefSCC::size
ssize_t size() const
Definition: LazyCallGraph.h:616
addEdge
static void addEdge(SmallVectorImpl< LazyCallGraph::Edge > &Edges, DenseMap< LazyCallGraph::Node *, int > &EdgeIndexMap, LazyCallGraph::Node &N, LazyCallGraph::Edge::Kind EK)
Definition: LazyCallGraph.cpp:60
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
llvm::DOT::EscapeString
std::string EscapeString(const std::string &Label)
Definition: GraphWriter.cpp:55
llvm::GlobalVariable
Definition: GlobalVariable.h:39
llvm::AllAnalysesOn
This templated class represents "all analyses that operate over <a particular IR unit>" (e....
Definition: PassManager.h:90
llvm::LazyCallGraph::removeDeadFunction
void removeDeadFunction(Function &F)
Remove a dead function from the call graph (typically to delete it).
Definition: LazyCallGraph.cpp:1494
llvm::LazyCallGraphDOTPrinterPass::run
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
Definition: LazyCallGraph.cpp:2047
Module.h
llvm::LazyCallGraph::lookup
Node * lookup(const Function &F) const
Lookup a function in the graph which has already been scanned and added.
Definition: LazyCallGraph.h:974
getEdgeKind
static LazyCallGraph::Edge::Kind getEdgeKind(Function &OriginalFunction, Function &NewFunction)
Definition: LazyCallGraph.cpp:1569
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
STLExtras.h
Sequence.h
llvm::LazyCallGraph::EdgeSequence::begin
iterator begin()
Definition: LazyCallGraph.h:255
llvm::ArrayRef::empty
bool empty() const
empty - Check if the array is empty.
Definition: ArrayRef.h:159
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::LazyCallGraph::invalidate
bool invalidate(Module &, const PreservedAnalyses &PA, ModuleAnalysisManager::Invalidator &)
Definition: LazyCallGraph.cpp:214
llvm::LazyCallGraph::RefSCC::isAncestorOf
bool isAncestorOf(const RefSCC &RC) const
Test if this RefSCC is an ancestor of RC.
Definition: LazyCallGraph.cpp:414
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
Instruction.h
llvm::all_of
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1709
llvm::LazyCallGraph::RefSCC::insertTrivialCallEdge
void insertTrivialCallEdge(Node &SourceN, Node &TargetN)
A convenience wrapper around the above to handle trivial cases of inserting a new call edge.
Definition: LazyCallGraph.cpp:1389
llvm::LazyCallGraph::SCC
An SCC of the call graph.
Definition: LazyCallGraph.h:420
llvm::LazyCallGraph::operator=
LazyCallGraph & operator=(LazyCallGraph &&RHS)
Definition: LazyCallGraph.cpp:222
printNode
static void printNode(raw_ostream &OS, LazyCallGraph::Node &N)
Definition: LazyCallGraph.cpp:1987
Constants.h
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
printRefSCC
static void printRefSCC(raw_ostream &OS, LazyCallGraph::RefSCC &C)
Definition: LazyCallGraph.cpp:2003
llvm::LibFunc
LibFunc
Definition: TargetLibraryInfo.h:36
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::LazyCallGraph::EdgeSequence::end
iterator end()
Definition: LazyCallGraph.h:256
llvm::LazyCallGraph::RefSCC::isParentOf
bool isParentOf(const RefSCC &RC) const
Test if this RefSCC is a parent of RC.
Definition: LazyCallGraph.cpp:400
updatePostorderSequenceForEdgeInsertion
static iterator_range< typename PostorderSequenceT::iterator > updatePostorderSequenceForEdgeInsertion(SCCT &SourceSCC, SCCT &TargetSCC, PostorderSequenceT &SCCs, SCCIndexMapT &SCCIndices, ComputeSourceConnectedSetCallableT ComputeSourceConnectedSet, ComputeTargetConnectedSetCallableT ComputeTargetConnectedSet)
Generic helper that updates a postorder sequence of SCCs for a potentially cycle-introducing edge ins...
Definition: LazyCallGraph.cpp:508
llvm::LazyCallGraph::RefSCC::insertTrivialRefEdge
void insertTrivialRefEdge(Node &SourceN, Node &TargetN)
A convenience wrapper around the above to handle trivial cases of inserting a new ref edge.
Definition: LazyCallGraph.cpp:1418
TargetLibraryInfo.h
llvm::dwarf::Index
Index
Definition: Dwarf.h:472
llvm::TargetLibraryInfo::getLibFunc
bool getLibFunc(StringRef funcName, LibFunc &F) const
Searches for a particular function name.
Definition: TargetLibraryInfo.h:298
llvm::Instruction
Definition: Instruction.h:42
llvm::LazyCallGraph::RefSCC
A RefSCC of the call graph.
Definition: LazyCallGraph.h:545
llvm::LazyCallGraph::EdgeSequence::iterator
An iterator used for the edges to both entry nodes and child nodes.
Definition: LazyCallGraph.h:193
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
llvm::LazyCallGraph::EdgeSequence
The edge sequence object.
Definition: LazyCallGraph.h:183
SmallPtrSet.h
llvm::LazyCallGraph::lookupSCC
SCC * lookupSCC(Node &N) const
Lookup a function's SCC in the graph.
Definition: LazyCallGraph.h:980
llvm::SmallVectorImpl::append
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:687
llvm::AnalysisManager::Invalidator
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:661
LazyCallGraph.h
llvm::MCID::Call
@ Call
Definition: MCInstrDesc.h:155
llvm::lltok::Kind
Kind
Definition: LLToken.h:18
llvm::Value::use_empty
bool use_empty() const
Definition: Value.h:344
llvm::LazyCallGraph::RefSCC::insertOutgoingEdge
void insertOutgoingEdge(Node &SourceN, Node &TargetN, Edge::Kind EK)
Insert an edge whose parent is in this RefSCC and child is in some child RefSCC.
Definition: LazyCallGraph.cpp:976
llvm::LazyCallGraph::get
Node & get(Function &F)
Get a graph node for a given function, scanning it to populate the graph data as necessary.
Definition: LazyCallGraph.h:995
llvm::LazyCallGraph::RefSCC::switchInternalEdgeToCall
bool switchInternalEdgeToCall(Node &SourceN, Node &TargetN, function_ref< void(ArrayRef< SCC * > MergedSCCs)> MergeCB={})
Make an existing internal ref edge into a call edge.
Definition: LazyCallGraph.cpp:576
llvm::function_ref
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLFunctionalExtras.h:36
G
const DataFlowGraph & G
Definition: RDFGraph.cpp:200
llvm::LazyCallGraph::RefSCC::switchInternalEdgeToRef
iterator_range< iterator > switchInternalEdgeToRef(Node &SourceN, Node &TargetN)
Make an existing internal call edge within a single SCC into a ref edge.
Definition: LazyCallGraph.cpp:742
llvm::instructions
inst_range instructions(Function *F)
Definition: InstIterator.h:133
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
Index
uint32_t Index
Definition: ELFObjHandler.cpp:83
llvm::LazyCallGraph::RefSCC::isDescendantOf
bool isDescendantOf(const RefSCC &RC) const
Test if this RefSCC is a descendant of RC.
Definition: LazyCallGraph.h:648
llvm::LazyCallGraph::addSplitFunction
void addSplitFunction(Function &OriginalFunction, Function &NewFunction)
Add a new function split/outlined from an existing function.
Definition: LazyCallGraph.cpp:1609
llvm::LazyCallGraph::lookupRefSCC
RefSCC * lookupRefSCC(Node &N) const
Lookup a function's RefSCC in the graph.
Definition: LazyCallGraph.h:986
llvm::LazyCallGraph::RefSCC::removeOutgoingEdge
void removeOutgoingEdge(Node &SourceN, Node &TargetN)
Remove an edge whose source is in this RefSCC and target is not.
Definition: LazyCallGraph.cpp:1137
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::DenseMap
Definition: DenseMap.h:714
llvm::AnalysisKey
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:69
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::LazyCallGraph::RefSCC::insertIncomingRefEdge
SmallVector< RefSCC *, 1 > insertIncomingRefEdge(Node &SourceN, Node &TargetN)
Insert an edge whose source is in a descendant RefSCC and target is in this RefSCC.
Definition: LazyCallGraph.cpp:996
ArrayRef.h
llvm::LazyCallGraph::Edge::Kind
Kind
The kind of edge in the graph.
Definition: LazyCallGraph.h:135
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::move
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1836
iterator_range.h
llvm::LazyCallGraph::EdgeSequence::lookup
Edge * lookup(Node &N)
Definition: LazyCallGraph.h:265
llvm::TargetLibraryInfo::isKnownVectorFunctionInLibrary
bool isKnownVectorFunctionInLibrary(StringRef F) const
Check if the function "F" is listed in a library known to LLVM.
Definition: TargetLibraryInfo.h:441
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
llvm::LazyCallGraph::SCC::isAncestorOf
bool isAncestorOf(const SCC &C) const
Test if this SCC is an ancestor of C.
Definition: LazyCallGraph.cpp:289
llvm::LazyCallGraph::Node
A node in the call graph.
Definition: LazyCallGraph.h:316
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:383
llvm::size
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
Definition: STLExtras.h:1690
llvm::AMDGPU::CPol::SCC
@ SCC
Definition: SIDefines.h:307
llvm::LazyCallGraph::Edge
A class used to represent edges in the call graph.
Definition: LazyCallGraph.h:132
llvm::SmallPtrSetImplBase::clear
void clear()
Definition: SmallPtrSet.h:95
llvm::iterator_range::end
IteratorT end() const
Definition: iterator_range.h:45
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::LazyCallGraph::RefSCC::removeInternalRefEdge
SmallVector< RefSCC *, 1 > removeInternalRefEdge(Node &SourceN, ArrayRef< Node * > TargetNs)
Remove a list of ref edges which are entirely within this RefSCC.
Definition: LazyCallGraph.cpp:1155
llvm::LazyCallGraph::SCC::size
int size() const
Definition: LazyCallGraph.h:481
Compiler.h
llvm::LazyCallGraph::RefSCC::replaceNodeFunction
void replaceNodeFunction(Node &N, Function &NewF)
Directly replace a node's function with a new function.
Definition: LazyCallGraph.cpp:1442
llvm::make_scope_exit
detail::scope_exit< std::decay_t< Callable > > make_scope_exit(Callable &&F)
Definition: ScopeExit.h:59
llvm::find_if
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1736
Callee
amdgpu Simplify well known AMD library false FunctionCallee Callee
Definition: AMDGPULibCalls.cpp:187
isKnownLibFunction
static bool isKnownLibFunction(Function &F, TargetLibraryInfo &TLI)
Definition: LazyCallGraph.cpp:144
GraphWriter.h
std
Definition: BitVector.h:851
llvm::SmallVectorImpl::swap
void swap(SmallVectorImpl &RHS)
Definition: SmallVector.h:972
llvm::LazyCallGraph::addSplitRefRecursiveFunctions
void addSplitRefRecursiveFunctions(Function &OriginalFunction, ArrayRef< Function * > NewFunctions)
Add new ref-recursive functions split/outlined from an existing function.
Definition: LazyCallGraph.cpp:1688
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:348
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
llvm::LazyCallGraph::Edge::isCall
bool isCall() const
Test whether the edge represents a direct call to a function.
Definition: LazyCallGraph.h:1224
GlobalVariable.h
llvm::LazyCallGraphAnalysis
An analysis pass which computes the call graph for a module.
Definition: LazyCallGraph.h:1258
Casting.h
llvm::LazyCallGraph::isLibFunction
bool isLibFunction(Function &F) const
Test whether a function is a known and defined library function tracked by the call graph.
Definition: LazyCallGraph.h:1017
Function.h
PassManager.h
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:226
verify
ppc ctr loops verify
Definition: PPCCTRLoopsVerify.cpp:76
llvm::LazyCallGraphDOTPrinterPass::LazyCallGraphDOTPrinterPass
LazyCallGraphDOTPrinterPass(raw_ostream &OS)
Definition: LazyCallGraph.cpp:2029
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:614
llvm::LazyCallGraph::RefSCC::switchTrivialInternalEdgeToRef
void switchTrivialInternalEdgeToRef(Node &SourceN, Node &TargetN)
Make an existing internal call edge between separate SCCs into a ref edge.
Definition: LazyCallGraph.cpp:723
llvm::LazyCallGraph::EdgeSequence::empty
bool empty()
Definition: LazyCallGraph.h:282
llvm::makeArrayRef
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
Definition: ArrayRef.h:475
llvm::LazyCallGraph::RefSCC::switchOutgoingEdgeToRef
void switchOutgoingEdgeToRef(Node &SourceN, Node &TargetN)
Make an existing outgoing call edge into a ref edge.
Definition: LazyCallGraph.cpp:943
SmallVector.h
N
#define N
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::try_emplace
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&... Args)
Definition: DenseMap.h:222
llvm::SmallVectorImpl::pop_back_val
T pop_back_val()
Definition: SmallVector.h:677
llvm::LazyCallGraph::RefSCC::switchOutgoingEdgeToCall
void switchOutgoingEdgeToCall(Node &SourceN, Node &TargetN)
Make an existing outgoing ref edge into a call edge.
Definition: LazyCallGraph.cpp:922
llvm::LazyCallGraph::SCC::getOuterRefSCC
RefSCC & getOuterRefSCC() const
Definition: LazyCallGraph.h:483
llvm::iterator_range
A range adaptor for a pair of iterators.
Definition: iterator_range.h:30
ScopeExit.h
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
llvm::reverse
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:485
llvm::SmallPtrSetImpl
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:344
llvm::LazyCallGraph::Edge::Ref
@ Ref
Definition: LazyCallGraph.h:135
llvm::PreservedAnalyses::getChecker
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
Definition: PassManager.h:310
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
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::LazyCallGraph
A lazily constructed view of the call graph of a module.
Definition: LazyCallGraph.h:111
raw_ostream.h
llvm::LazyCallGraph::visitReferences
static void visitReferences(SmallVectorImpl< Constant * > &Worklist, SmallPtrSetImpl< Constant * > &Visited, function_ref< void(Function &)> Callback)
Recursively visits the defined functions whose address is reachable from every constant in the Workli...
Definition: LazyCallGraph.cpp:1960
llvm::SmallPtrSetImpl::contains
bool contains(ConstPtrType Ptr) const
Definition: SmallPtrSet.h:389
printSCC
static void printSCC(raw_ostream &OS, LazyCallGraph::SCC &C)
Definition: LazyCallGraph.cpp:1996
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
Debug.h
llvm::iterator_range::begin
IteratorT begin() const
Definition: iterator_range.h:44
llvm::LazyCallGraph::Edge::Call
@ Call
Definition: LazyCallGraph.h:135
llvm::LazyCallGraph::RefSCC::insertInternalRefEdge
void insertInternalRefEdge(Node &SourceN, Node &TargetN)
Insert a ref edge from one node in this RefSCC to another in this RefSCC.
Definition: LazyCallGraph.cpp:964
llvm::LazyCallGraph::removeEdge
void removeEdge(Node &SourceN, Node &TargetN)
Update the call graph after deleting an edge.
Definition: LazyCallGraph.cpp:1485
llvm::SmallVectorImpl::emplace_back
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:941
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:365
printNodeDOT
static void printNodeDOT(raw_ostream &OS, LazyCallGraph::Node &N)
Definition: LazyCallGraph.cpp:2032
llvm::LazyCallGraphPrinterPass::run
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
Definition: LazyCallGraph.cpp:2012