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