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