LLVM  8.0.0svn
LazyCallGraph.cpp
Go to the documentation of this file.
1 //===- LazyCallGraph.cpp - Analysis of a Module's call graph --------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
11 #include "llvm/ADT/ArrayRef.h"
12 #include "llvm/ADT/STLExtras.h"
13 #include "llvm/ADT/ScopeExit.h"
14 #include "llvm/ADT/Sequence.h"
15 #include "llvm/ADT/SmallPtrSet.h"
16 #include "llvm/ADT/SmallVector.h"
19 #include "llvm/Config/llvm-config.h"
20 #include "llvm/IR/CallSite.h"
21 #include "llvm/IR/Function.h"
22 #include "llvm/IR/GlobalVariable.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");
70  Edges.emplace_back(LazyCallGraph::Edge(N, EK));
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 CS = CallSite(&I))
104  if (Function *Callee = CS.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" function.
151  return TLI.getLibFunc(F, LF) || TLI.isFunctionVectorizable(F.getName());
152 }
153 
155  LLVM_DEBUG(dbgs() << "Building CG for module: " << M.getModuleIdentifier()
156  << "\n");
157  for (Function &F : M) {
158  if (F.isDeclaration())
159  continue;
160  // If this function is a known lib function to LLVM then we want to
161  // synthesize reference edges to it to model the fact that LLVM can turn
162  // arbitrary code into a library function call.
163  if (isKnownLibFunction(F, TLI))
164  LibFunctions.insert(&F);
165 
166  if (F.hasLocalLinkage())
167  continue;
168 
169  // External linkage defined functions have edges to them from other
170  // modules.
171  LLVM_DEBUG(dbgs() << " Adding '" << F.getName()
172  << "' to entry set of the graph.\n");
173  addEdge(EntryEdges.Edges, EntryEdges.EdgeIndexMap, get(F), Edge::Ref);
174  }
175 
176  // Now add entry nodes for functions reachable via initializers to globals.
179  for (GlobalVariable &GV : M.globals())
180  if (GV.hasInitializer())
181  if (Visited.insert(GV.getInitializer()).second)
182  Worklist.push_back(GV.getInitializer());
183 
184  LLVM_DEBUG(
185  dbgs() << " Adding functions referenced by global initializers to the "
186  "entry set.\n");
187  visitReferences(Worklist, Visited, [&](Function &F) {
188  addEdge(EntryEdges.Edges, EntryEdges.EdgeIndexMap, get(F),
190  });
191 }
192 
194  : BPA(std::move(G.BPA)), NodeMap(std::move(G.NodeMap)),
195  EntryEdges(std::move(G.EntryEdges)), SCCBPA(std::move(G.SCCBPA)),
196  SCCMap(std::move(G.SCCMap)),
197  LibFunctions(std::move(G.LibFunctions)) {
198  updateGraphPtrs();
199 }
200 
202  BPA = std::move(G.BPA);
203  NodeMap = std::move(G.NodeMap);
204  EntryEdges = std::move(G.EntryEdges);
205  SCCBPA = std::move(G.SCCBPA);
206  SCCMap = std::move(G.SCCMap);
207  LibFunctions = std::move(G.LibFunctions);
208  updateGraphPtrs();
209  return *this;
210 }
211 
212 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
213 LLVM_DUMP_METHOD void LazyCallGraph::SCC::dump() const {
214  dbgs() << *this << '\n';
215 }
216 #endif
217 
218 #ifndef NDEBUG
219 void LazyCallGraph::SCC::verify() {
220  assert(OuterRefSCC && "Can't have a null RefSCC!");
221  assert(!Nodes.empty() && "Can't have an empty SCC!");
222 
223  for (Node *N : Nodes) {
224  assert(N && "Can't have a null node!");
225  assert(OuterRefSCC->G->lookupSCC(*N) == this &&
226  "Node does not map to this SCC!");
227  assert(N->DFSNumber == -1 &&
228  "Must set DFS numbers to -1 when adding a node to an SCC!");
229  assert(N->LowLink == -1 &&
230  "Must set low link to -1 when adding a node to an SCC!");
231  for (Edge &E : **N)
232  assert(E.getNode().isPopulated() && "Can't have an unpopulated node!");
233  }
234 }
235 #endif
236 
238  if (this == &C)
239  return false;
240 
241  for (Node &N : *this)
242  for (Edge &E : N->calls())
243  if (OuterRefSCC->G->lookupSCC(E.getNode()) == &C)
244  return true;
245 
246  // No edges found.
247  return false;
248 }
249 
250 bool LazyCallGraph::SCC::isAncestorOf(const SCC &TargetC) const {
251  if (this == &TargetC)
252  return false;
253 
254  LazyCallGraph &G = *OuterRefSCC->G;
255 
256  // Start with this SCC.
257  SmallPtrSet<const SCC *, 16> Visited = {this};
258  SmallVector<const SCC *, 16> Worklist = {this};
259 
260  // Walk down the graph until we run out of edges or find a path to TargetC.
261  do {
262  const SCC &C = *Worklist.pop_back_val();
263  for (Node &N : C)
264  for (Edge &E : N->calls()) {
265  SCC *CalleeC = G.lookupSCC(E.getNode());
266  if (!CalleeC)
267  continue;
268 
269  // If the callee's SCC is the TargetC, we're done.
270  if (CalleeC == &TargetC)
271  return true;
272 
273  // If this is the first time we've reached this SCC, put it on the
274  // worklist to recurse through.
275  if (Visited.insert(CalleeC).second)
276  Worklist.push_back(CalleeC);
277  }
278  } while (!Worklist.empty());
279 
280  // No paths found.
281  return false;
282 }
283 
284 LazyCallGraph::RefSCC::RefSCC(LazyCallGraph &G) : G(&G) {}
285 
286 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
287 LLVM_DUMP_METHOD void LazyCallGraph::RefSCC::dump() const {
288  dbgs() << *this << '\n';
289 }
290 #endif
291 
292 #ifndef NDEBUG
293 void LazyCallGraph::RefSCC::verify() {
294  assert(G && "Can't have a null graph!");
295  assert(!SCCs.empty() && "Can't have an empty SCC!");
296 
297  // Verify basic properties of the SCCs.
298  SmallPtrSet<SCC *, 4> SCCSet;
299  for (SCC *C : SCCs) {
300  assert(C && "Can't have a null SCC!");
301  C->verify();
302  assert(&C->getOuterRefSCC() == this &&
303  "SCC doesn't think it is inside this RefSCC!");
304  bool Inserted = SCCSet.insert(C).second;
305  assert(Inserted && "Found a duplicate SCC!");
306  auto IndexIt = SCCIndices.find(C);
307  assert(IndexIt != SCCIndices.end() &&
308  "Found an SCC that doesn't have an index!");
309  }
310 
311  // Check that our indices map correctly.
312  for (auto &SCCIndexPair : SCCIndices) {
313  SCC *C = SCCIndexPair.first;
314  int i = SCCIndexPair.second;
315  assert(C && "Can't have a null SCC in the indices!");
316  assert(SCCSet.count(C) && "Found an index for an SCC not in the RefSCC!");
317  assert(SCCs[i] == C && "Index doesn't point to SCC!");
318  }
319 
320  // Check that the SCCs are in fact in post-order.
321  for (int i = 0, Size = SCCs.size(); i < Size; ++i) {
322  SCC &SourceSCC = *SCCs[i];
323  for (Node &N : SourceSCC)
324  for (Edge &E : *N) {
325  if (!E.isCall())
326  continue;
327  SCC &TargetSCC = *G->lookupSCC(E.getNode());
328  if (&TargetSCC.getOuterRefSCC() == this) {
329  assert(SCCIndices.find(&TargetSCC)->second <= i &&
330  "Edge between SCCs violates post-order relationship.");
331  continue;
332  }
333  }
334  }
335 }
336 #endif
337 
339  if (&RC == this)
340  return false;
341 
342  // Search all edges to see if this is a parent.
343  for (SCC &C : *this)
344  for (Node &N : C)
345  for (Edge &E : *N)
346  if (G->lookupRefSCC(E.getNode()) == &RC)
347  return true;
348 
349  return false;
350 }
351 
353  if (&RC == this)
354  return false;
355 
356  // For each descendant of this RefSCC, see if one of its children is the
357  // argument. If not, add that descendant to the worklist and continue
358  // searching.
361  Worklist.push_back(this);
362  Visited.insert(this);
363  do {
364  const RefSCC &DescendantRC = *Worklist.pop_back_val();
365  for (SCC &C : DescendantRC)
366  for (Node &N : C)
367  for (Edge &E : *N) {
368  auto *ChildRC = G->lookupRefSCC(E.getNode());
369  if (ChildRC == &RC)
370  return true;
371  if (!ChildRC || !Visited.insert(ChildRC).second)
372  continue;
373  Worklist.push_back(ChildRC);
374  }
375  } while (!Worklist.empty());
376 
377  return false;
378 }
379 
380 /// Generic helper that updates a postorder sequence of SCCs for a potentially
381 /// cycle-introducing edge insertion.
382 ///
383 /// A postorder sequence of SCCs of a directed graph has one fundamental
384 /// property: all deges in the DAG of SCCs point "up" the sequence. That is,
385 /// all edges in the SCC DAG point to prior SCCs in the sequence.
386 ///
387 /// This routine both updates a postorder sequence and uses that sequence to
388 /// compute the set of SCCs connected into a cycle. It should only be called to
389 /// insert a "downward" edge which will require changing the sequence to
390 /// restore it to a postorder.
391 ///
392 /// When inserting an edge from an earlier SCC to a later SCC in some postorder
393 /// sequence, all of the SCCs which may be impacted are in the closed range of
394 /// those two within the postorder sequence. The algorithm used here to restore
395 /// the state is as follows:
396 ///
397 /// 1) Starting from the source SCC, construct a set of SCCs which reach the
398 /// source SCC consisting of just the source SCC. Then scan toward the
399 /// target SCC in postorder and for each SCC, if it has an edge to an SCC
400 /// in the set, add it to the set. Otherwise, the source SCC is not
401 /// a successor, move it in the postorder sequence to immediately before
402 /// the source SCC, shifting the source SCC and all SCCs in the set one
403 /// position toward the target SCC. Stop scanning after processing the
404 /// target SCC.
405 /// 2) If the source SCC is now past the target SCC in the postorder sequence,
406 /// and thus the new edge will flow toward the start, we are done.
407 /// 3) Otherwise, starting from the target SCC, walk all edges which reach an
408 /// SCC between the source and the target, and add them to the set of
409 /// connected SCCs, then recurse through them. Once a complete set of the
410 /// SCCs the target connects to is known, hoist the remaining SCCs between
411 /// the source and the target to be above the target. Note that there is no
412 /// need to process the source SCC, it is already known to connect.
413 /// 4) At this point, all of the SCCs in the closed range between the source
414 /// SCC and the target SCC in the postorder sequence are connected,
415 /// including the target SCC and the source SCC. Inserting the edge from
416 /// the source SCC to the target SCC will form a cycle out of precisely
417 /// these SCCs. Thus we can merge all of the SCCs in this closed range into
418 /// a single SCC.
419 ///
420 /// This process has various important properties:
421 /// - Only mutates the SCCs when adding the edge actually changes the SCC
422 /// structure.
423 /// - Never mutates SCCs which are unaffected by the change.
424 /// - Updates the postorder sequence to correctly satisfy the postorder
425 /// constraint after the edge is inserted.
426 /// - Only reorders SCCs in the closed postorder sequence from the source to
427 /// the target, so easy to bound how much has changed even in the ordering.
428 /// - Big-O is the number of edges in the closed postorder range of SCCs from
429 /// source to target.
430 ///
431 /// This helper routine, in addition to updating the postorder sequence itself
432 /// will also update a map from SCCs to indices within that sequence.
433 ///
434 /// The sequence and the map must operate on pointers to the SCC type.
435 ///
436 /// Two callbacks must be provided. The first computes the subset of SCCs in
437 /// the postorder closed range from the source to the target which connect to
438 /// the source SCC via some (transitive) set of edges. The second computes the
439 /// subset of the same range which the target SCC connects to via some
440 /// (transitive) set of edges. Both callbacks should populate the set argument
441 /// provided.
442 template <typename SCCT, typename PostorderSequenceT, typename SCCIndexMapT,
443  typename ComputeSourceConnectedSetCallableT,
444  typename ComputeTargetConnectedSetCallableT>
447  SCCT &SourceSCC, SCCT &TargetSCC, PostorderSequenceT &SCCs,
448  SCCIndexMapT &SCCIndices,
449  ComputeSourceConnectedSetCallableT ComputeSourceConnectedSet,
450  ComputeTargetConnectedSetCallableT ComputeTargetConnectedSet) {
451  int SourceIdx = SCCIndices[&SourceSCC];
452  int TargetIdx = SCCIndices[&TargetSCC];
453  assert(SourceIdx < TargetIdx && "Cannot have equal indices here!");
454 
455  SmallPtrSet<SCCT *, 4> ConnectedSet;
456 
457  // Compute the SCCs which (transitively) reach the source.
458  ComputeSourceConnectedSet(ConnectedSet);
459 
460  // Partition the SCCs in this part of the port-order sequence so only SCCs
461  // connecting to the source remain between it and the target. This is
462  // a benign partition as it preserves postorder.
463  auto SourceI = std::stable_partition(
464  SCCs.begin() + SourceIdx, SCCs.begin() + TargetIdx + 1,
465  [&ConnectedSet](SCCT *C) { return !ConnectedSet.count(C); });
466  for (int i = SourceIdx, e = TargetIdx + 1; i < e; ++i)
467  SCCIndices.find(SCCs[i])->second = i;
468 
469  // If the target doesn't connect to the source, then we've corrected the
470  // post-order and there are no cycles formed.
471  if (!ConnectedSet.count(&TargetSCC)) {
472  assert(SourceI > (SCCs.begin() + SourceIdx) &&
473  "Must have moved the source to fix the post-order.");
474  assert(*std::prev(SourceI) == &TargetSCC &&
475  "Last SCC to move should have bene the target.");
476 
477  // Return an empty range at the target SCC indicating there is nothing to
478  // merge.
479  return make_range(std::prev(SourceI), std::prev(SourceI));
480  }
481 
482  assert(SCCs[TargetIdx] == &TargetSCC &&
483  "Should not have moved target if connected!");
484  SourceIdx = SourceI - SCCs.begin();
485  assert(SCCs[SourceIdx] == &SourceSCC &&
486  "Bad updated index computation for the source SCC!");
487 
488 
489  // See whether there are any remaining intervening SCCs between the source
490  // and target. If so we need to make sure they all are reachable form the
491  // target.
492  if (SourceIdx + 1 < TargetIdx) {
493  ConnectedSet.clear();
494  ComputeTargetConnectedSet(ConnectedSet);
495 
496  // Partition SCCs so that only SCCs reached from the target remain between
497  // the source and the target. This preserves postorder.
498  auto TargetI = std::stable_partition(
499  SCCs.begin() + SourceIdx + 1, SCCs.begin() + TargetIdx + 1,
500  [&ConnectedSet](SCCT *C) { return ConnectedSet.count(C); });
501  for (int i = SourceIdx + 1, e = TargetIdx + 1; i < e; ++i)
502  SCCIndices.find(SCCs[i])->second = i;
503  TargetIdx = std::prev(TargetI) - SCCs.begin();
504  assert(SCCs[TargetIdx] == &TargetSCC &&
505  "Should always end with the target!");
506  }
507 
508  // At this point, we know that connecting source to target forms a cycle
509  // because target connects back to source, and we know that all of the SCCs
510  // between the source and target in the postorder sequence participate in that
511  // cycle.
512  return make_range(SCCs.begin() + SourceIdx, SCCs.begin() + TargetIdx);
513 }
514 
515 bool
517  Node &SourceN, Node &TargetN,
518  function_ref<void(ArrayRef<SCC *> MergeSCCs)> MergeCB) {
519  assert(!(*SourceN)[TargetN].isCall() && "Must start with a ref edge!");
520  SmallVector<SCC *, 1> DeletedSCCs;
521 
522 #ifndef NDEBUG
523  // In a debug build, verify the RefSCC is valid to start with and when this
524  // routine finishes.
525  verify();
526  auto VerifyOnExit = make_scope_exit([&]() { verify(); });
527 #endif
528 
529  SCC &SourceSCC = *G->lookupSCC(SourceN);
530  SCC &TargetSCC = *G->lookupSCC(TargetN);
531 
532  // If the two nodes are already part of the same SCC, we're also done as
533  // we've just added more connectivity.
534  if (&SourceSCC == &TargetSCC) {
535  SourceN->setEdgeKind(TargetN, Edge::Call);
536  return false; // No new cycle.
537  }
538 
539  // At this point we leverage the postorder list of SCCs to detect when the
540  // insertion of an edge changes the SCC structure in any way.
541  //
542  // First and foremost, we can eliminate the need for any changes when the
543  // edge is toward the beginning of the postorder sequence because all edges
544  // flow in that direction already. Thus adding a new one cannot form a cycle.
545  int SourceIdx = SCCIndices[&SourceSCC];
546  int TargetIdx = SCCIndices[&TargetSCC];
547  if (TargetIdx < SourceIdx) {
548  SourceN->setEdgeKind(TargetN, Edge::Call);
549  return false; // No new cycle.
550  }
551 
552  // Compute the SCCs which (transitively) reach the source.
553  auto ComputeSourceConnectedSet = [&](SmallPtrSetImpl<SCC *> &ConnectedSet) {
554 #ifndef NDEBUG
555  // Check that the RefSCC is still valid before computing this as the
556  // results will be nonsensical of we've broken its invariants.
557  verify();
558 #endif
559  ConnectedSet.insert(&SourceSCC);
560  auto IsConnected = [&](SCC &C) {
561  for (Node &N : C)
562  for (Edge &E : N->calls())
563  if (ConnectedSet.count(G->lookupSCC(E.getNode())))
564  return true;
565 
566  return false;
567  };
568 
569  for (SCC *C :
570  make_range(SCCs.begin() + SourceIdx + 1, SCCs.begin() + TargetIdx + 1))
571  if (IsConnected(*C))
572  ConnectedSet.insert(C);
573  };
574 
575  // Use a normal worklist to find which SCCs the target connects to. We still
576  // bound the search based on the range in the postorder list we care about,
577  // but because this is forward connectivity we just "recurse" through the
578  // edges.
579  auto ComputeTargetConnectedSet = [&](SmallPtrSetImpl<SCC *> &ConnectedSet) {
580 #ifndef NDEBUG
581  // Check that the RefSCC is still valid before computing this as the
582  // results will be nonsensical of we've broken its invariants.
583  verify();
584 #endif
585  ConnectedSet.insert(&TargetSCC);
586  SmallVector<SCC *, 4> Worklist;
587  Worklist.push_back(&TargetSCC);
588  do {
589  SCC &C = *Worklist.pop_back_val();
590  for (Node &N : C)
591  for (Edge &E : *N) {
592  if (!E.isCall())
593  continue;
594  SCC &EdgeC = *G->lookupSCC(E.getNode());
595  if (&EdgeC.getOuterRefSCC() != this)
596  // Not in this RefSCC...
597  continue;
598  if (SCCIndices.find(&EdgeC)->second <= SourceIdx)
599  // Not in the postorder sequence between source and target.
600  continue;
601 
602  if (ConnectedSet.insert(&EdgeC).second)
603  Worklist.push_back(&EdgeC);
604  }
605  } while (!Worklist.empty());
606  };
607 
608  // Use a generic helper to update the postorder sequence of SCCs and return
609  // a range of any SCCs connected into a cycle by inserting this edge. This
610  // routine will also take care of updating the indices into the postorder
611  // sequence.
612  auto MergeRange = updatePostorderSequenceForEdgeInsertion(
613  SourceSCC, TargetSCC, SCCs, SCCIndices, ComputeSourceConnectedSet,
614  ComputeTargetConnectedSet);
615 
616  // Run the user's callback on the merged SCCs before we actually merge them.
617  if (MergeCB)
618  MergeCB(makeArrayRef(MergeRange.begin(), MergeRange.end()));
619 
620  // If the merge range is empty, then adding the edge didn't actually form any
621  // new cycles. We're done.
622  if (empty(MergeRange)) {
623  // Now that the SCC structure is finalized, flip the kind to call.
624  SourceN->setEdgeKind(TargetN, Edge::Call);
625  return false; // No new cycle.
626  }
627 
628 #ifndef NDEBUG
629  // Before merging, check that the RefSCC remains valid after all the
630  // postorder updates.
631  verify();
632 #endif
633 
634  // Otherwise we need to merge all of the SCCs in the cycle into a single
635  // result SCC.
636  //
637  // NB: We merge into the target because all of these functions were already
638  // reachable from the target, meaning any SCC-wide properties deduced about it
639  // other than the set of functions within it will not have changed.
640  for (SCC *C : MergeRange) {
641  assert(C != &TargetSCC &&
642  "We merge *into* the target and shouldn't process it here!");
643  SCCIndices.erase(C);
644  TargetSCC.Nodes.append(C->Nodes.begin(), C->Nodes.end());
645  for (Node *N : C->Nodes)
646  G->SCCMap[N] = &TargetSCC;
647  C->clear();
648  DeletedSCCs.push_back(C);
649  }
650 
651  // Erase the merged SCCs from the list and update the indices of the
652  // remaining SCCs.
653  int IndexOffset = MergeRange.end() - MergeRange.begin();
654  auto EraseEnd = SCCs.erase(MergeRange.begin(), MergeRange.end());
655  for (SCC *C : make_range(EraseEnd, SCCs.end()))
656  SCCIndices[C] -= IndexOffset;
657 
658  // Now that the SCC structure is finalized, flip the kind to call.
659  SourceN->setEdgeKind(TargetN, Edge::Call);
660 
661  // And we're done, but we did form a new cycle.
662  return true;
663 }
664 
666  Node &TargetN) {
667  assert((*SourceN)[TargetN].isCall() && "Must start with a call edge!");
668 
669 #ifndef NDEBUG
670  // In a debug build, verify the RefSCC is valid to start with and when this
671  // routine finishes.
672  verify();
673  auto VerifyOnExit = make_scope_exit([&]() { verify(); });
674 #endif
675 
676  assert(G->lookupRefSCC(SourceN) == this &&
677  "Source must be in this RefSCC.");
678  assert(G->lookupRefSCC(TargetN) == this &&
679  "Target must be in this RefSCC.");
680  assert(G->lookupSCC(SourceN) != G->lookupSCC(TargetN) &&
681  "Source and Target must be in separate SCCs for this to be trivial!");
682 
683  // Set the edge kind.
684  SourceN->setEdgeKind(TargetN, Edge::Ref);
685 }
686 
689  assert((*SourceN)[TargetN].isCall() && "Must start with a call edge!");
690 
691 #ifndef NDEBUG
692  // In a debug build, verify the RefSCC is valid to start with and when this
693  // routine finishes.
694  verify();
695  auto VerifyOnExit = make_scope_exit([&]() { verify(); });
696 #endif
697 
698  assert(G->lookupRefSCC(SourceN) == this &&
699  "Source must be in this RefSCC.");
700  assert(G->lookupRefSCC(TargetN) == this &&
701  "Target must be in this RefSCC.");
702 
703  SCC &TargetSCC = *G->lookupSCC(TargetN);
704  assert(G->lookupSCC(SourceN) == &TargetSCC && "Source and Target must be in "
705  "the same SCC to require the "
706  "full CG update.");
707 
708  // Set the edge kind.
709  SourceN->setEdgeKind(TargetN, Edge::Ref);
710 
711  // Otherwise we are removing a call edge from a single SCC. This may break
712  // the cycle. In order to compute the new set of SCCs, we need to do a small
713  // DFS over the nodes within the SCC to form any sub-cycles that remain as
714  // distinct SCCs and compute a postorder over the resulting SCCs.
715  //
716  // However, we specially handle the target node. The target node is known to
717  // reach all other nodes in the original SCC by definition. This means that
718  // we want the old SCC to be replaced with an SCC containing that node as it
719  // will be the root of whatever SCC DAG results from the DFS. Assumptions
720  // about an SCC such as the set of functions called will continue to hold,
721  // etc.
722 
723  SCC &OldSCC = TargetSCC;
725  SmallVector<Node *, 16> PendingSCCStack;
726  SmallVector<SCC *, 4> NewSCCs;
727 
728  // Prepare the nodes for a fresh DFS.
729  SmallVector<Node *, 16> Worklist;
730  Worklist.swap(OldSCC.Nodes);
731  for (Node *N : Worklist) {
732  N->DFSNumber = N->LowLink = 0;
733  G->SCCMap.erase(N);
734  }
735 
736  // Force the target node to be in the old SCC. This also enables us to take
737  // a very significant short-cut in the standard Tarjan walk to re-form SCCs
738  // below: whenever we build an edge that reaches the target node, we know
739  // that the target node eventually connects back to all other nodes in our
740  // walk. As a consequence, we can detect and handle participants in that
741  // cycle without walking all the edges that form this connection, and instead
742  // by relying on the fundamental guarantee coming into this operation (all
743  // nodes are reachable from the target due to previously forming an SCC).
744  TargetN.DFSNumber = TargetN.LowLink = -1;
745  OldSCC.Nodes.push_back(&TargetN);
746  G->SCCMap[&TargetN] = &OldSCC;
747 
748  // Scan down the stack and DFS across the call edges.
749  for (Node *RootN : Worklist) {
750  assert(DFSStack.empty() &&
751  "Cannot begin a new root with a non-empty DFS stack!");
752  assert(PendingSCCStack.empty() &&
753  "Cannot begin a new root with pending nodes for an SCC!");
754 
755  // Skip any nodes we've already reached in the DFS.
756  if (RootN->DFSNumber != 0) {
757  assert(RootN->DFSNumber == -1 &&
758  "Shouldn't have any mid-DFS root nodes!");
759  continue;
760  }
761 
762  RootN->DFSNumber = RootN->LowLink = 1;
763  int NextDFSNumber = 2;
764 
765  DFSStack.push_back({RootN, (*RootN)->call_begin()});
766  do {
767  Node *N;
769  std::tie(N, I) = DFSStack.pop_back_val();
770  auto E = (*N)->call_end();
771  while (I != E) {
772  Node &ChildN = I->getNode();
773  if (ChildN.DFSNumber == 0) {
774  // We haven't yet visited this child, so descend, pushing the current
775  // node onto the stack.
776  DFSStack.push_back({N, I});
777 
778  assert(!G->SCCMap.count(&ChildN) &&
779  "Found a node with 0 DFS number but already in an SCC!");
780  ChildN.DFSNumber = ChildN.LowLink = NextDFSNumber++;
781  N = &ChildN;
782  I = (*N)->call_begin();
783  E = (*N)->call_end();
784  continue;
785  }
786 
787  // Check for the child already being part of some component.
788  if (ChildN.DFSNumber == -1) {
789  if (G->lookupSCC(ChildN) == &OldSCC) {
790  // If the child is part of the old SCC, we know that it can reach
791  // every other node, so we have formed a cycle. Pull the entire DFS
792  // and pending stacks into it. See the comment above about setting
793  // up the old SCC for why we do this.
794  int OldSize = OldSCC.size();
795  OldSCC.Nodes.push_back(N);
796  OldSCC.Nodes.append(PendingSCCStack.begin(), PendingSCCStack.end());
797  PendingSCCStack.clear();
798  while (!DFSStack.empty())
799  OldSCC.Nodes.push_back(DFSStack.pop_back_val().first);
800  for (Node &N : make_range(OldSCC.begin() + OldSize, OldSCC.end())) {
801  N.DFSNumber = N.LowLink = -1;
802  G->SCCMap[&N] = &OldSCC;
803  }
804  N = nullptr;
805  break;
806  }
807 
808  // If the child has already been added to some child component, it
809  // couldn't impact the low-link of this parent because it isn't
810  // connected, and thus its low-link isn't relevant so skip it.
811  ++I;
812  continue;
813  }
814 
815  // Track the lowest linked child as the lowest link for this node.
816  assert(ChildN.LowLink > 0 && "Must have a positive low-link number!");
817  if (ChildN.LowLink < N->LowLink)
818  N->LowLink = ChildN.LowLink;
819 
820  // Move to the next edge.
821  ++I;
822  }
823  if (!N)
824  // Cleared the DFS early, start another round.
825  break;
826 
827  // We've finished processing N and its descendants, put it on our pending
828  // SCC stack to eventually get merged into an SCC of nodes.
829  PendingSCCStack.push_back(N);
830 
831  // If this node is linked to some lower entry, continue walking up the
832  // stack.
833  if (N->LowLink != N->DFSNumber)
834  continue;
835 
836  // Otherwise, we've completed an SCC. Append it to our post order list of
837  // SCCs.
838  int RootDFSNumber = N->DFSNumber;
839  // Find the range of the node stack by walking down until we pass the
840  // root DFS number.
841  auto SCCNodes = make_range(
842  PendingSCCStack.rbegin(),
843  find_if(reverse(PendingSCCStack), [RootDFSNumber](const Node *N) {
844  return N->DFSNumber < RootDFSNumber;
845  }));
846 
847  // Form a new SCC out of these nodes and then clear them off our pending
848  // stack.
849  NewSCCs.push_back(G->createSCC(*this, SCCNodes));
850  for (Node &N : *NewSCCs.back()) {
851  N.DFSNumber = N.LowLink = -1;
852  G->SCCMap[&N] = NewSCCs.back();
853  }
854  PendingSCCStack.erase(SCCNodes.end().base(), PendingSCCStack.end());
855  } while (!DFSStack.empty());
856  }
857 
858  // Insert the remaining SCCs before the old one. The old SCC can reach all
859  // other SCCs we form because it contains the target node of the removed edge
860  // of the old SCC. This means that we will have edges into all of the new
861  // SCCs, which means the old one must come last for postorder.
862  int OldIdx = SCCIndices[&OldSCC];
863  SCCs.insert(SCCs.begin() + OldIdx, NewSCCs.begin(), NewSCCs.end());
864 
865  // Update the mapping from SCC* to index to use the new SCC*s, and remove the
866  // old SCC from the mapping.
867  for (int Idx = OldIdx, Size = SCCs.size(); Idx < Size; ++Idx)
868  SCCIndices[SCCs[Idx]] = Idx;
869 
870  return make_range(SCCs.begin() + OldIdx,
871  SCCs.begin() + OldIdx + NewSCCs.size());
872 }
873 
875  Node &TargetN) {
876  assert(!(*SourceN)[TargetN].isCall() && "Must start with a ref edge!");
877 
878  assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");
879  assert(G->lookupRefSCC(TargetN) != this &&
880  "Target must not be in this RefSCC.");
881 #ifdef EXPENSIVE_CHECKS
882  assert(G->lookupRefSCC(TargetN)->isDescendantOf(*this) &&
883  "Target must be a descendant of the Source.");
884 #endif
885 
886  // Edges between RefSCCs are the same regardless of call or ref, so we can
887  // just flip the edge here.
888  SourceN->setEdgeKind(TargetN, Edge::Call);
889 
890 #ifndef NDEBUG
891  // Check that the RefSCC is still valid.
892  verify();
893 #endif
894 }
895 
897  Node &TargetN) {
898  assert((*SourceN)[TargetN].isCall() && "Must start with a call edge!");
899 
900  assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");
901  assert(G->lookupRefSCC(TargetN) != this &&
902  "Target must not be in this RefSCC.");
903 #ifdef EXPENSIVE_CHECKS
904  assert(G->lookupRefSCC(TargetN)->isDescendantOf(*this) &&
905  "Target must be a descendant of the Source.");
906 #endif
907 
908  // Edges between RefSCCs are the same regardless of call or ref, so we can
909  // just flip the edge here.
910  SourceN->setEdgeKind(TargetN, Edge::Ref);
911 
912 #ifndef NDEBUG
913  // Check that the RefSCC is still valid.
914  verify();
915 #endif
916 }
917 
919  Node &TargetN) {
920  assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");
921  assert(G->lookupRefSCC(TargetN) == this && "Target must be in this RefSCC.");
922 
923  SourceN->insertEdgeInternal(TargetN, Edge::Ref);
924 
925 #ifndef NDEBUG
926  // Check that the RefSCC is still valid.
927  verify();
928 #endif
929 }
930 
932  Edge::Kind EK) {
933  // First insert it into the caller.
934  SourceN->insertEdgeInternal(TargetN, EK);
935 
936  assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");
937 
938  assert(G->lookupRefSCC(TargetN) != this &&
939  "Target must not be in this RefSCC.");
940 #ifdef EXPENSIVE_CHECKS
941  assert(G->lookupRefSCC(TargetN)->isDescendantOf(*this) &&
942  "Target must be a descendant of the Source.");
943 #endif
944 
945 #ifndef NDEBUG
946  // Check that the RefSCC is still valid.
947  verify();
948 #endif
949 }
950 
953  assert(G->lookupRefSCC(TargetN) == this && "Target must be in this RefSCC.");
954  RefSCC &SourceC = *G->lookupRefSCC(SourceN);
955  assert(&SourceC != this && "Source must not be in this RefSCC.");
956 #ifdef EXPENSIVE_CHECKS
957  assert(SourceC.isDescendantOf(*this) &&
958  "Source must be a descendant of the Target.");
959 #endif
960 
961  SmallVector<RefSCC *, 1> DeletedRefSCCs;
962 
963 #ifndef NDEBUG
964  // In a debug build, verify the RefSCC is valid to start with and when this
965  // routine finishes.
966  verify();
967  auto VerifyOnExit = make_scope_exit([&]() { verify(); });
968 #endif
969 
970  int SourceIdx = G->RefSCCIndices[&SourceC];
971  int TargetIdx = G->RefSCCIndices[this];
972  assert(SourceIdx < TargetIdx &&
973  "Postorder list doesn't see edge as incoming!");
974 
975  // Compute the RefSCCs which (transitively) reach the source. We do this by
976  // working backwards from the source using the parent set in each RefSCC,
977  // skipping any RefSCCs that don't fall in the postorder range. This has the
978  // advantage of walking the sparser parent edge (in high fan-out graphs) but
979  // more importantly this removes examining all forward edges in all RefSCCs
980  // within the postorder range which aren't in fact connected. Only connected
981  // RefSCCs (and their edges) are visited here.
982  auto ComputeSourceConnectedSet = [&](SmallPtrSetImpl<RefSCC *> &Set) {
983  Set.insert(&SourceC);
984  auto IsConnected = [&](RefSCC &RC) {
985  for (SCC &C : RC)
986  for (Node &N : C)
987  for (Edge &E : *N)
988  if (Set.count(G->lookupRefSCC(E.getNode())))
989  return true;
990 
991  return false;
992  };
993 
994  for (RefSCC *C : make_range(G->PostOrderRefSCCs.begin() + SourceIdx + 1,
995  G->PostOrderRefSCCs.begin() + TargetIdx + 1))
996  if (IsConnected(*C))
997  Set.insert(C);
998  };
999 
1000  // Use a normal worklist to find which SCCs the target connects to. We still
1001  // bound the search based on the range in the postorder list we care about,
1002  // but because this is forward connectivity we just "recurse" through the
1003  // edges.
1004  auto ComputeTargetConnectedSet = [&](SmallPtrSetImpl<RefSCC *> &Set) {
1005  Set.insert(this);
1006  SmallVector<RefSCC *, 4> Worklist;
1007  Worklist.push_back(this);
1008  do {
1009  RefSCC &RC = *Worklist.pop_back_val();
1010  for (SCC &C : RC)
1011  for (Node &N : C)
1012  for (Edge &E : *N) {
1013  RefSCC &EdgeRC = *G->lookupRefSCC(E.getNode());
1014  if (G->getRefSCCIndex(EdgeRC) <= SourceIdx)
1015  // Not in the postorder sequence between source and target.
1016  continue;
1017 
1018  if (Set.insert(&EdgeRC).second)
1019  Worklist.push_back(&EdgeRC);
1020  }
1021  } while (!Worklist.empty());
1022  };
1023 
1024  // Use a generic helper to update the postorder sequence of RefSCCs and return
1025  // a range of any RefSCCs connected into a cycle by inserting this edge. This
1026  // routine will also take care of updating the indices into the postorder
1027  // sequence.
1030  SourceC, *this, G->PostOrderRefSCCs, G->RefSCCIndices,
1031  ComputeSourceConnectedSet, ComputeTargetConnectedSet);
1032 
1033  // Build a set so we can do fast tests for whether a RefSCC will end up as
1034  // part of the merged RefSCC.
1035  SmallPtrSet<RefSCC *, 16> MergeSet(MergeRange.begin(), MergeRange.end());
1036 
1037  // This RefSCC will always be part of that set, so just insert it here.
1038  MergeSet.insert(this);
1039 
1040  // Now that we have identified all of the SCCs which need to be merged into
1041  // a connected set with the inserted edge, merge all of them into this SCC.
1042  SmallVector<SCC *, 16> MergedSCCs;
1043  int SCCIndex = 0;
1044  for (RefSCC *RC : MergeRange) {
1045  assert(RC != this && "We're merging into the target RefSCC, so it "
1046  "shouldn't be in the range.");
1047 
1048  // Walk the inner SCCs to update their up-pointer and walk all the edges to
1049  // update any parent sets.
1050  // FIXME: We should try to find a way to avoid this (rather expensive) edge
1051  // walk by updating the parent sets in some other manner.
1052  for (SCC &InnerC : *RC) {
1053  InnerC.OuterRefSCC = this;
1054  SCCIndices[&InnerC] = SCCIndex++;
1055  for (Node &N : InnerC)
1056  G->SCCMap[&N] = &InnerC;
1057  }
1058 
1059  // Now merge in the SCCs. We can actually move here so try to reuse storage
1060  // the first time through.
1061  if (MergedSCCs.empty())
1062  MergedSCCs = std::move(RC->SCCs);
1063  else
1064  MergedSCCs.append(RC->SCCs.begin(), RC->SCCs.end());
1065  RC->SCCs.clear();
1066  DeletedRefSCCs.push_back(RC);
1067  }
1068 
1069  // Append our original SCCs to the merged list and move it into place.
1070  for (SCC &InnerC : *this)
1071  SCCIndices[&InnerC] = SCCIndex++;
1072  MergedSCCs.append(SCCs.begin(), SCCs.end());
1073  SCCs = std::move(MergedSCCs);
1074 
1075  // Remove the merged away RefSCCs from the post order sequence.
1076  for (RefSCC *RC : MergeRange)
1077  G->RefSCCIndices.erase(RC);
1078  int IndexOffset = MergeRange.end() - MergeRange.begin();
1079  auto EraseEnd =
1080  G->PostOrderRefSCCs.erase(MergeRange.begin(), MergeRange.end());
1081  for (RefSCC *RC : make_range(EraseEnd, G->PostOrderRefSCCs.end()))
1082  G->RefSCCIndices[RC] -= IndexOffset;
1083 
1084  // At this point we have a merged RefSCC with a post-order SCCs list, just
1085  // connect the nodes to form the new edge.
1086  SourceN->insertEdgeInternal(TargetN, Edge::Ref);
1087 
1088  // We return the list of SCCs which were merged so that callers can
1089  // invalidate any data they have associated with those SCCs. Note that these
1090  // SCCs are no longer in an interesting state (they are totally empty) but
1091  // the pointers will remain stable for the life of the graph itself.
1092  return DeletedRefSCCs;
1093 }
1094 
1096  assert(G->lookupRefSCC(SourceN) == this &&
1097  "The source must be a member of this RefSCC.");
1098  assert(G->lookupRefSCC(TargetN) != this &&
1099  "The target must not be a member of this RefSCC");
1100 
1101 #ifndef NDEBUG
1102  // In a debug build, verify the RefSCC is valid to start with and when this
1103  // routine finishes.
1104  verify();
1105  auto VerifyOnExit = make_scope_exit([&]() { verify(); });
1106 #endif
1107 
1108  // First remove it from the node.
1109  bool Removed = SourceN->removeEdgeInternal(TargetN);
1110  (void)Removed;
1111  assert(Removed && "Target not in the edge set for this caller?");
1112 }
1113 
1116  ArrayRef<Node *> TargetNs) {
1117  // We return a list of the resulting *new* RefSCCs in post-order.
1118  SmallVector<RefSCC *, 1> Result;
1119 
1120 #ifndef NDEBUG
1121  // In a debug build, verify the RefSCC is valid to start with and that either
1122  // we return an empty list of result RefSCCs and this RefSCC remains valid,
1123  // or we return new RefSCCs and this RefSCC is dead.
1124  verify();
1125  auto VerifyOnExit = make_scope_exit([&]() {
1126  // If we didn't replace our RefSCC with new ones, check that this one
1127  // remains valid.
1128  if (G)
1129  verify();
1130  });
1131 #endif
1132 
1133  // First remove the actual edges.
1134  for (Node *TargetN : TargetNs) {
1135  assert(!(*SourceN)[*TargetN].isCall() &&
1136  "Cannot remove a call edge, it must first be made a ref edge");
1137 
1138  bool Removed = SourceN->removeEdgeInternal(*TargetN);
1139  (void)Removed;
1140  assert(Removed && "Target not in the edge set for this caller?");
1141  }
1142 
1143  // Direct self references don't impact the ref graph at all.
1144  if (llvm::all_of(TargetNs,
1145  [&](Node *TargetN) { return &SourceN == TargetN; }))
1146  return Result;
1147 
1148  // If all targets are in the same SCC as the source, because no call edges
1149  // were removed there is no RefSCC structure change.
1150  SCC &SourceC = *G->lookupSCC(SourceN);
1151  if (llvm::all_of(TargetNs, [&](Node *TargetN) {
1152  return G->lookupSCC(*TargetN) == &SourceC;
1153  }))
1154  return Result;
1155 
1156  // We build somewhat synthetic new RefSCCs by providing a postorder mapping
1157  // for each inner SCC. We store these inside the low-link field of the nodes
1158  // rather than associated with SCCs because this saves a round-trip through
1159  // the node->SCC map and in the common case, SCCs are small. We will verify
1160  // that we always give the same number to every node in the SCC such that
1161  // these are equivalent.
1162  int PostOrderNumber = 0;
1163 
1164  // Reset all the other nodes to prepare for a DFS over them, and add them to
1165  // our worklist.
1166  SmallVector<Node *, 8> Worklist;
1167  for (SCC *C : SCCs) {
1168  for (Node &N : *C)
1169  N.DFSNumber = N.LowLink = 0;
1170 
1171  Worklist.append(C->Nodes.begin(), C->Nodes.end());
1172  }
1173 
1174  // Track the number of nodes in this RefSCC so that we can quickly recognize
1175  // an important special case of the edge removal not breaking the cycle of
1176  // this RefSCC.
1177  const int NumRefSCCNodes = Worklist.size();
1178 
1180  SmallVector<Node *, 4> PendingRefSCCStack;
1181  do {
1182  assert(DFSStack.empty() &&
1183  "Cannot begin a new root with a non-empty DFS stack!");
1184  assert(PendingRefSCCStack.empty() &&
1185  "Cannot begin a new root with pending nodes for an SCC!");
1186 
1187  Node *RootN = Worklist.pop_back_val();
1188  // Skip any nodes we've already reached in the DFS.
1189  if (RootN->DFSNumber != 0) {
1190  assert(RootN->DFSNumber == -1 &&
1191  "Shouldn't have any mid-DFS root nodes!");
1192  continue;
1193  }
1194 
1195  RootN->DFSNumber = RootN->LowLink = 1;
1196  int NextDFSNumber = 2;
1197 
1198  DFSStack.push_back({RootN, (*RootN)->begin()});
1199  do {
1200  Node *N;
1202  std::tie(N, I) = DFSStack.pop_back_val();
1203  auto E = (*N)->end();
1204 
1205  assert(N->DFSNumber != 0 && "We should always assign a DFS number "
1206  "before processing a node.");
1207 
1208  while (I != E) {
1209  Node &ChildN = I->getNode();
1210  if (ChildN.DFSNumber == 0) {
1211  // Mark that we should start at this child when next this node is the
1212  // top of the stack. We don't start at the next child to ensure this
1213  // child's lowlink is reflected.
1214  DFSStack.push_back({N, I});
1215 
1216  // Continue, resetting to the child node.
1217  ChildN.LowLink = ChildN.DFSNumber = NextDFSNumber++;
1218  N = &ChildN;
1219  I = ChildN->begin();
1220  E = ChildN->end();
1221  continue;
1222  }
1223  if (ChildN.DFSNumber == -1) {
1224  // If this child isn't currently in this RefSCC, no need to process
1225  // it.
1226  ++I;
1227  continue;
1228  }
1229 
1230  // Track the lowest link of the children, if any are still in the stack.
1231  // Any child not on the stack will have a LowLink of -1.
1232  assert(ChildN.LowLink != 0 &&
1233  "Low-link must not be zero with a non-zero DFS number.");
1234  if (ChildN.LowLink >= 0 && ChildN.LowLink < N->LowLink)
1235  N->LowLink = ChildN.LowLink;
1236  ++I;
1237  }
1238 
1239  // We've finished processing N and its descendants, put it on our pending
1240  // stack to eventually get merged into a RefSCC.
1241  PendingRefSCCStack.push_back(N);
1242 
1243  // If this node is linked to some lower entry, continue walking up the
1244  // stack.
1245  if (N->LowLink != N->DFSNumber) {
1246  assert(!DFSStack.empty() &&
1247  "We never found a viable root for a RefSCC to pop off!");
1248  continue;
1249  }
1250 
1251  // Otherwise, form a new RefSCC from the top of the pending node stack.
1252  int RefSCCNumber = PostOrderNumber++;
1253  int RootDFSNumber = N->DFSNumber;
1254 
1255  // Find the range of the node stack by walking down until we pass the
1256  // root DFS number. Update the DFS numbers and low link numbers in the
1257  // process to avoid re-walking this list where possible.
1258  auto StackRI = find_if(reverse(PendingRefSCCStack), [&](Node *N) {
1259  if (N->DFSNumber < RootDFSNumber)
1260  // We've found the bottom.
1261  return true;
1262 
1263  // Update this node and keep scanning.
1264  N->DFSNumber = -1;
1265  // Save the post-order number in the lowlink field so that we can use
1266  // it to map SCCs into new RefSCCs after we finish the DFS.
1267  N->LowLink = RefSCCNumber;
1268  return false;
1269  });
1270  auto RefSCCNodes = make_range(StackRI.base(), PendingRefSCCStack.end());
1271 
1272  // If we find a cycle containing all nodes originally in this RefSCC then
1273  // the removal hasn't changed the structure at all. This is an important
1274  // special case and we can directly exit the entire routine more
1275  // efficiently as soon as we discover it.
1276  if (llvm::size(RefSCCNodes) == NumRefSCCNodes) {
1277  // Clear out the low link field as we won't need it.
1278  for (Node *N : RefSCCNodes)
1279  N->LowLink = -1;
1280  // Return the empty result immediately.
1281  return Result;
1282  }
1283 
1284  // We've already marked the nodes internally with the RefSCC number so
1285  // just clear them off the stack and continue.
1286  PendingRefSCCStack.erase(RefSCCNodes.begin(), PendingRefSCCStack.end());
1287  } while (!DFSStack.empty());
1288 
1289  assert(DFSStack.empty() && "Didn't flush the entire DFS stack!");
1290  assert(PendingRefSCCStack.empty() && "Didn't flush all pending nodes!");
1291  } while (!Worklist.empty());
1292 
1293  assert(PostOrderNumber > 1 &&
1294  "Should never finish the DFS when the existing RefSCC remains valid!");
1295 
1296  // Otherwise we create a collection of new RefSCC nodes and build
1297  // a radix-sort style map from postorder number to these new RefSCCs. We then
1298  // append SCCs to each of these RefSCCs in the order they occurred in the
1299  // original SCCs container.
1300  for (int i = 0; i < PostOrderNumber; ++i)
1301  Result.push_back(G->createRefSCC(*G));
1302 
1303  // Insert the resulting postorder sequence into the global graph postorder
1304  // sequence before the current RefSCC in that sequence, and then remove the
1305  // current one.
1306  //
1307  // FIXME: It'd be nice to change the APIs so that we returned an iterator
1308  // range over the global postorder sequence and generally use that sequence
1309  // rather than building a separate result vector here.
1310  int Idx = G->getRefSCCIndex(*this);
1311  G->PostOrderRefSCCs.erase(G->PostOrderRefSCCs.begin() + Idx);
1312  G->PostOrderRefSCCs.insert(G->PostOrderRefSCCs.begin() + Idx, Result.begin(),
1313  Result.end());
1314  for (int i : seq<int>(Idx, G->PostOrderRefSCCs.size()))
1315  G->RefSCCIndices[G->PostOrderRefSCCs[i]] = i;
1316 
1317  for (SCC *C : SCCs) {
1318  // We store the SCC number in the node's low-link field above.
1319  int SCCNumber = C->begin()->LowLink;
1320  // Clear out all of the SCC's node's low-link fields now that we're done
1321  // using them as side-storage.
1322  for (Node &N : *C) {
1323  assert(N.LowLink == SCCNumber &&
1324  "Cannot have different numbers for nodes in the same SCC!");
1325  N.LowLink = -1;
1326  }
1327 
1328  RefSCC &RC = *Result[SCCNumber];
1329  int SCCIndex = RC.SCCs.size();
1330  RC.SCCs.push_back(C);
1331  RC.SCCIndices[C] = SCCIndex;
1332  C->OuterRefSCC = &RC;
1333  }
1334 
1335  // Now that we've moved things into the new RefSCCs, clear out our current
1336  // one.
1337  G = nullptr;
1338  SCCs.clear();
1339  SCCIndices.clear();
1340 
1341 #ifndef NDEBUG
1342  // Verify the new RefSCCs we've built.
1343  for (RefSCC *RC : Result)
1344  RC->verify();
1345 #endif
1346 
1347  // Return the new list of SCCs.
1348  return Result;
1349 }
1350 
1351 void LazyCallGraph::RefSCC::handleTrivialEdgeInsertion(Node &SourceN,
1352  Node &TargetN) {
1353  // The only trivial case that requires any graph updates is when we add new
1354  // ref edge and may connect different RefSCCs along that path. This is only
1355  // because of the parents set. Every other part of the graph remains constant
1356  // after this edge insertion.
1357  assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");
1358  RefSCC &TargetRC = *G->lookupRefSCC(TargetN);
1359  if (&TargetRC == this)
1360  return;
1361 
1362 #ifdef EXPENSIVE_CHECKS
1363  assert(TargetRC.isDescendantOf(*this) &&
1364  "Target must be a descendant of the Source.");
1365 #endif
1366 }
1367 
1369  Node &TargetN) {
1370 #ifndef NDEBUG
1371  // Check that the RefSCC is still valid when we finish.
1372  auto ExitVerifier = make_scope_exit([this] { verify(); });
1373 
1374 #ifdef EXPENSIVE_CHECKS
1375  // Check that we aren't breaking some invariants of the SCC graph. Note that
1376  // this is quadratic in the number of edges in the call graph!
1377  SCC &SourceC = *G->lookupSCC(SourceN);
1378  SCC &TargetC = *G->lookupSCC(TargetN);
1379  if (&SourceC != &TargetC)
1380  assert(SourceC.isAncestorOf(TargetC) &&
1381  "Call edge is not trivial in the SCC graph!");
1382 #endif // EXPENSIVE_CHECKS
1383 #endif // NDEBUG
1384 
1385  // First insert it into the source or find the existing edge.
1386  auto InsertResult =
1387  SourceN->EdgeIndexMap.insert({&TargetN, SourceN->Edges.size()});
1388  if (!InsertResult.second) {
1389  // Already an edge, just update it.
1390  Edge &E = SourceN->Edges[InsertResult.first->second];
1391  if (E.isCall())
1392  return; // Nothing to do!
1393  E.setKind(Edge::Call);
1394  } else {
1395  // Create the new edge.
1396  SourceN->Edges.emplace_back(TargetN, Edge::Call);
1397  }
1398 
1399  // Now that we have the edge, handle the graph fallout.
1400  handleTrivialEdgeInsertion(SourceN, TargetN);
1401 }
1402 
1404 #ifndef NDEBUG
1405  // Check that the RefSCC is still valid when we finish.
1406  auto ExitVerifier = make_scope_exit([this] { verify(); });
1407 
1408 #ifdef EXPENSIVE_CHECKS
1409  // Check that we aren't breaking some invariants of the RefSCC graph.
1410  RefSCC &SourceRC = *G->lookupRefSCC(SourceN);
1411  RefSCC &TargetRC = *G->lookupRefSCC(TargetN);
1412  if (&SourceRC != &TargetRC)
1413  assert(SourceRC.isAncestorOf(TargetRC) &&
1414  "Ref edge is not trivial in the RefSCC graph!");
1415 #endif // EXPENSIVE_CHECKS
1416 #endif // NDEBUG
1417 
1418  // First insert it into the source or find the existing edge.
1419  auto InsertResult =
1420  SourceN->EdgeIndexMap.insert({&TargetN, SourceN->Edges.size()});
1421  if (!InsertResult.second)
1422  // Already an edge, we're done.
1423  return;
1424 
1425  // Create the new edge.
1426  SourceN->Edges.emplace_back(TargetN, Edge::Ref);
1427 
1428  // Now that we have the edge, handle the graph fallout.
1429  handleTrivialEdgeInsertion(SourceN, TargetN);
1430 }
1431 
1433  Function &OldF = N.getFunction();
1434 
1435 #ifndef NDEBUG
1436  // Check that the RefSCC is still valid when we finish.
1437  auto ExitVerifier = make_scope_exit([this] { verify(); });
1438 
1439  assert(G->lookupRefSCC(N) == this &&
1440  "Cannot replace the function of a node outside this RefSCC.");
1441 
1442  assert(G->NodeMap.find(&NewF) == G->NodeMap.end() &&
1443  "Must not have already walked the new function!'");
1444 
1445  // It is important that this replacement not introduce graph changes so we
1446  // insist that the caller has already removed every use of the original
1447  // function and that all uses of the new function correspond to existing
1448  // edges in the graph. The common and expected way to use this is when
1449  // replacing the function itself in the IR without changing the call graph
1450  // shape and just updating the analysis based on that.
1451  assert(&OldF != &NewF && "Cannot replace a function with itself!");
1452  assert(OldF.use_empty() &&
1453  "Must have moved all uses from the old function to the new!");
1454 #endif
1455 
1456  N.replaceFunction(NewF);
1457 
1458  // Update various call graph maps.
1459  G->NodeMap.erase(&OldF);
1460  G->NodeMap[&NewF] = &N;
1461 }
1462 
1463 void LazyCallGraph::insertEdge(Node &SourceN, Node &TargetN, Edge::Kind EK) {
1464  assert(SCCMap.empty() &&
1465  "This method cannot be called after SCCs have been formed!");
1466 
1467  return SourceN->insertEdgeInternal(TargetN, EK);
1468 }
1469 
1470 void LazyCallGraph::removeEdge(Node &SourceN, Node &TargetN) {
1471  assert(SCCMap.empty() &&
1472  "This method cannot be called after SCCs have been formed!");
1473 
1474  bool Removed = SourceN->removeEdgeInternal(TargetN);
1475  (void)Removed;
1476  assert(Removed && "Target not in the edge set for this caller?");
1477 }
1478 
1480  // FIXME: This is unnecessarily restrictive. We should be able to remove
1481  // functions which recursively call themselves.
1482  assert(F.use_empty() &&
1483  "This routine should only be called on trivially dead functions!");
1484 
1485  // We shouldn't remove library functions as they are never really dead while
1486  // the call graph is in use -- every function definition refers to them.
1487  assert(!isLibFunction(F) &&
1488  "Must not remove lib functions from the call graph!");
1489 
1490  auto NI = NodeMap.find(&F);
1491  if (NI == NodeMap.end())
1492  // Not in the graph at all!
1493  return;
1494 
1495  Node &N = *NI->second;
1496  NodeMap.erase(NI);
1497 
1498  // Remove this from the entry edges if present.
1499  EntryEdges.removeEdgeInternal(N);
1500 
1501  if (SCCMap.empty()) {
1502  // No SCCs have been formed, so removing this is fine and there is nothing
1503  // else necessary at this point but clearing out the node.
1504  N.clear();
1505  return;
1506  }
1507 
1508  // Cannot remove a function which has yet to be visited in the DFS walk, so
1509  // if we have a node at all then we must have an SCC and RefSCC.
1510  auto CI = SCCMap.find(&N);
1511  assert(CI != SCCMap.end() &&
1512  "Tried to remove a node without an SCC after DFS walk started!");
1513  SCC &C = *CI->second;
1514  SCCMap.erase(CI);
1515  RefSCC &RC = C.getOuterRefSCC();
1516 
1517  // This node must be the only member of its SCC as it has no callers, and
1518  // that SCC must be the only member of a RefSCC as it has no references.
1519  // Validate these properties first.
1520  assert(C.size() == 1 && "Dead functions must be in a singular SCC");
1521  assert(RC.size() == 1 && "Dead functions must be in a singular RefSCC");
1522 
1523  auto RCIndexI = RefSCCIndices.find(&RC);
1524  int RCIndex = RCIndexI->second;
1525  PostOrderRefSCCs.erase(PostOrderRefSCCs.begin() + RCIndex);
1526  RefSCCIndices.erase(RCIndexI);
1527  for (int i = RCIndex, Size = PostOrderRefSCCs.size(); i < Size; ++i)
1528  RefSCCIndices[PostOrderRefSCCs[i]] = i;
1529 
1530  // Finally clear out all the data structures from the node down through the
1531  // components.
1532  N.clear();
1533  N.G = nullptr;
1534  N.F = nullptr;
1535  C.clear();
1536  RC.clear();
1537  RC.G = nullptr;
1538 
1539  // Nothing to delete as all the objects are allocated in stable bump pointer
1540  // allocators.
1541 }
1542 
1543 LazyCallGraph::Node &LazyCallGraph::insertInto(Function &F, Node *&MappedN) {
1544  return *new (MappedN = BPA.Allocate()) Node(*this, F);
1545 }
1546 
1547 void LazyCallGraph::updateGraphPtrs() {
1548  // Walk the node map to update their graph pointers. While this iterates in
1549  // an unstable order, the order has no effect so it remains correct.
1550  for (auto &FunctionNodePair : NodeMap)
1551  FunctionNodePair.second->G = this;
1552 
1553  for (auto *RC : PostOrderRefSCCs)
1554  RC->G = this;
1555 }
1556 
1557 template <typename RootsT, typename GetBeginT, typename GetEndT,
1558  typename GetNodeT, typename FormSCCCallbackT>
1559 void LazyCallGraph::buildGenericSCCs(RootsT &&Roots, GetBeginT &&GetBegin,
1560  GetEndT &&GetEnd, GetNodeT &&GetNode,
1561  FormSCCCallbackT &&FormSCC) {
1562  using EdgeItT = decltype(GetBegin(std::declval<Node &>()));
1563 
1565  SmallVector<Node *, 16> PendingSCCStack;
1566 
1567  // Scan down the stack and DFS across the call edges.
1568  for (Node *RootN : Roots) {
1569  assert(DFSStack.empty() &&
1570  "Cannot begin a new root with a non-empty DFS stack!");
1571  assert(PendingSCCStack.empty() &&
1572  "Cannot begin a new root with pending nodes for an SCC!");
1573 
1574  // Skip any nodes we've already reached in the DFS.
1575  if (RootN->DFSNumber != 0) {
1576  assert(RootN->DFSNumber == -1 &&
1577  "Shouldn't have any mid-DFS root nodes!");
1578  continue;
1579  }
1580 
1581  RootN->DFSNumber = RootN->LowLink = 1;
1582  int NextDFSNumber = 2;
1583 
1584  DFSStack.push_back({RootN, GetBegin(*RootN)});
1585  do {
1586  Node *N;
1587  EdgeItT I;
1588  std::tie(N, I) = DFSStack.pop_back_val();
1589  auto E = GetEnd(*N);
1590  while (I != E) {
1591  Node &ChildN = GetNode(I);
1592  if (ChildN.DFSNumber == 0) {
1593  // We haven't yet visited this child, so descend, pushing the current
1594  // node onto the stack.
1595  DFSStack.push_back({N, I});
1596 
1597  ChildN.DFSNumber = ChildN.LowLink = NextDFSNumber++;
1598  N = &ChildN;
1599  I = GetBegin(*N);
1600  E = GetEnd(*N);
1601  continue;
1602  }
1603 
1604  // If the child has already been added to some child component, it
1605  // couldn't impact the low-link of this parent because it isn't
1606  // connected, and thus its low-link isn't relevant so skip it.
1607  if (ChildN.DFSNumber == -1) {
1608  ++I;
1609  continue;
1610  }
1611 
1612  // Track the lowest linked child as the lowest link for this node.
1613  assert(ChildN.LowLink > 0 && "Must have a positive low-link number!");
1614  if (ChildN.LowLink < N->LowLink)
1615  N->LowLink = ChildN.LowLink;
1616 
1617  // Move to the next edge.
1618  ++I;
1619  }
1620 
1621  // We've finished processing N and its descendants, put it on our pending
1622  // SCC stack to eventually get merged into an SCC of nodes.
1623  PendingSCCStack.push_back(N);
1624 
1625  // If this node is linked to some lower entry, continue walking up the
1626  // stack.
1627  if (N->LowLink != N->DFSNumber)
1628  continue;
1629 
1630  // Otherwise, we've completed an SCC. Append it to our post order list of
1631  // SCCs.
1632  int RootDFSNumber = N->DFSNumber;
1633  // Find the range of the node stack by walking down until we pass the
1634  // root DFS number.
1635  auto SCCNodes = make_range(
1636  PendingSCCStack.rbegin(),
1637  find_if(reverse(PendingSCCStack), [RootDFSNumber](const Node *N) {
1638  return N->DFSNumber < RootDFSNumber;
1639  }));
1640  // Form a new SCC out of these nodes and then clear them off our pending
1641  // stack.
1642  FormSCC(SCCNodes);
1643  PendingSCCStack.erase(SCCNodes.end().base(), PendingSCCStack.end());
1644  } while (!DFSStack.empty());
1645  }
1646 }
1647 
1648 /// Build the internal SCCs for a RefSCC from a sequence of nodes.
1649 ///
1650 /// Appends the SCCs to the provided vector and updates the map with their
1651 /// indices. Both the vector and map must be empty when passed into this
1652 /// routine.
1653 void LazyCallGraph::buildSCCs(RefSCC &RC, node_stack_range Nodes) {
1654  assert(RC.SCCs.empty() && "Already built SCCs!");
1655  assert(RC.SCCIndices.empty() && "Already mapped SCC indices!");
1656 
1657  for (Node *N : Nodes) {
1658  assert(N->LowLink >= (*Nodes.begin())->LowLink &&
1659  "We cannot have a low link in an SCC lower than its root on the "
1660  "stack!");
1661 
1662  // This node will go into the next RefSCC, clear out its DFS and low link
1663  // as we scan.
1664  N->DFSNumber = N->LowLink = 0;
1665  }
1666 
1667  // Each RefSCC contains a DAG of the call SCCs. To build these, we do
1668  // a direct walk of the call edges using Tarjan's algorithm. We reuse the
1669  // internal storage as we won't need it for the outer graph's DFS any longer.
1670  buildGenericSCCs(
1671  Nodes, [](Node &N) { return N->call_begin(); },
1672  [](Node &N) { return N->call_end(); },
1673  [](EdgeSequence::call_iterator I) -> Node & { return I->getNode(); },
1674  [this, &RC](node_stack_range Nodes) {
1675  RC.SCCs.push_back(createSCC(RC, Nodes));
1676  for (Node &N : *RC.SCCs.back()) {
1677  N.DFSNumber = N.LowLink = -1;
1678  SCCMap[&N] = RC.SCCs.back();
1679  }
1680  });
1681 
1682  // Wire up the SCC indices.
1683  for (int i = 0, Size = RC.SCCs.size(); i < Size; ++i)
1684  RC.SCCIndices[RC.SCCs[i]] = i;
1685 }
1686 
1688  if (EntryEdges.empty() || !PostOrderRefSCCs.empty())
1689  // RefSCCs are either non-existent or already built!
1690  return;
1691 
1692  assert(RefSCCIndices.empty() && "Already mapped RefSCC indices!");
1693 
1695  for (Edge &E : *this)
1696  Roots.push_back(&E.getNode());
1697 
1698  // The roots will be popped of a stack, so use reverse to get a less
1699  // surprising order. This doesn't change any of the semantics anywhere.
1700  std::reverse(Roots.begin(), Roots.end());
1701 
1702  buildGenericSCCs(
1703  Roots,
1704  [](Node &N) {
1705  // We need to populate each node as we begin to walk its edges.
1706  N.populate();
1707  return N->begin();
1708  },
1709  [](Node &N) { return N->end(); },
1710  [](EdgeSequence::iterator I) -> Node & { return I->getNode(); },
1711  [this](node_stack_range Nodes) {
1712  RefSCC *NewRC = createRefSCC(*this);
1713  buildSCCs(*NewRC, Nodes);
1714 
1715  // Push the new node into the postorder list and remember its position
1716  // in the index map.
1717  bool Inserted =
1718  RefSCCIndices.insert({NewRC, PostOrderRefSCCs.size()}).second;
1719  (void)Inserted;
1720  assert(Inserted && "Cannot already have this RefSCC in the index map!");
1721  PostOrderRefSCCs.push_back(NewRC);
1722 #ifndef NDEBUG
1723  NewRC->verify();
1724 #endif
1725  });
1726 }
1727 
1728 AnalysisKey LazyCallGraphAnalysis::Key;
1729 
1731 
1733  OS << " Edges in function: " << N.getFunction().getName() << "\n";
1734  for (LazyCallGraph::Edge &E : N.populate())
1735  OS << " " << (E.isCall() ? "call" : "ref ") << " -> "
1736  << E.getFunction().getName() << "\n";
1737 
1738  OS << "\n";
1739 }
1740 
1742  ptrdiff_t Size = size(C);
1743  OS << " SCC with " << Size << " functions:\n";
1744 
1745  for (LazyCallGraph::Node &N : C)
1746  OS << " " << N.getFunction().getName() << "\n";
1747 }
1748 
1750  ptrdiff_t Size = size(C);
1751  OS << " RefSCC with " << Size << " call SCCs:\n";
1752 
1753  for (LazyCallGraph::SCC &InnerC : C)
1754  printSCC(OS, InnerC);
1755 
1756  OS << "\n";
1757 }
1758 
1760  ModuleAnalysisManager &AM) {
1762 
1763  OS << "Printing the call graph for module: " << M.getModuleIdentifier()
1764  << "\n\n";
1765 
1766  for (Function &F : M)
1767  printNode(OS, G.get(F));
1768 
1769  G.buildRefSCCs();
1771  printRefSCC(OS, C);
1772 
1773  return PreservedAnalyses::all();
1774 }
1775 
1777  : OS(OS) {}
1778 
1780  std::string Name = "\"" + DOT::EscapeString(N.getFunction().getName()) + "\"";
1781 
1782  for (LazyCallGraph::Edge &E : N.populate()) {
1783  OS << " " << Name << " -> \""
1784  << DOT::EscapeString(E.getFunction().getName()) << "\"";
1785  if (!E.isCall()) // It is a ref edge.
1786  OS << " [style=dashed,label=\"ref\"]";
1787  OS << ";\n";
1788  }
1789 
1790  OS << "\n";
1791 }
1792 
1794  ModuleAnalysisManager &AM) {
1796 
1797  OS << "digraph \"" << DOT::EscapeString(M.getModuleIdentifier()) << "\" {\n";
1798 
1799  for (Function &F : M)
1800  printNodeDOT(OS, G.get(F));
1801 
1802  OS << "}\n";
1803 
1804  return PreservedAnalyses::all();
1805 }
uint64_t CallInst * C
This routine provides some synthesis utilities to produce sequences of values.
void insertEdge(Node &SourceN, Node &TargetN, Edge::Kind EK)
Update the call graph after inserting a new edge.
iterator_range< call_iterator > calls()
void removeOutgoingEdge(Node &SourceN, Node &TargetN)
Remove an edge whose source is in this RefSCC and target is not.
void removeEdge(Node &SourceN, Node &TargetN)
Update the call graph after deleting an edge.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:770
This class represents lattice values for constants.
Definition: AllocatorList.h:24
EdgeSequence & populate()
Populate the edges of this node if necessary.
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:64
Kind
The kind of edge in the graph.
The edge sequence object.
This provides a very simple, boring adaptor for a begin and end iterator into a range type...
SCC * lookupSCC(Node &N) const
Lookup a function&#39;s SCC in the graph.
Implements a lazy call graph analysis and related passes for the new pass manager.
Function & getFunction() const
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLExtras.h:111
LLVM_NODISCARD detail::scope_exit< typename std::decay< Callable >::type > make_scope_exit(Callable &&F)
Definition: ScopeExit.h:59
unsigned second
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:1180
F(f)
Node & get(Function &F)
Get a graph node for a given function, scanning it to populate the graph data as necessary.
static void printNode(raw_ostream &OS, LazyCallGraph::Node &N)
RefSCC * lookupRefSCC(Node &N) const
Lookup a function&#39;s RefSCC in the graph.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:344
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:221
RefSCC & getOuterRefSCC() const
bool isAncestorOf(const SCC &C) const
Test if this SCC is an ancestor of C.
StringRef getName() const
amdgpu Simplify well known AMD library false Value Value const Twine & Name
Definition: BitVector.h:938
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
Definition: ArrayRef.h:451
LazyCallGraph(Module &M, TargetLibraryInfo &TLI)
Construct a graph for the given module.
bool switchInternalEdgeToCall(Node &SourceN, Node &TargetN, function_ref< void(ArrayRef< SCC *> MergedSCCs)> MergeCB={})
Make an existing internal ref edge into a call edge.
iterator begin() const
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
bool isLibFunction(Function &F) const
Test whether a function is a known and defined library function tracked by the call graph...
static StringRef getName(Value *V)
#define LLVM_DUMP_METHOD
Definition: Compiler.h:74
auto reverse(ContainerTy &&C, typename std::enable_if< has_rbegin< ContainerTy >::value >::type *=nullptr) -> decltype(make_range(C.rbegin(), C.rend()))
Definition: STLExtras.h:261
A RefSCC of the call graph.
void insertTrivialCallEdge(Node &SourceN, Node &TargetN)
A convenience wrapper around the above to handle trivial cases of inserting a new call edge...
A lazily constructed view of the call graph of a module.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
LazyCallGraph & operator=(LazyCallGraph &&RHS)
void replaceNodeFunction(Node &N, Function &NewF)
Directly replace a node&#39;s function with a new function.
amdgpu Simplify well known AMD library false Value * Callee
static void addEdge(SmallVectorImpl< LazyCallGraph::Edge > &Edges, DenseMap< LazyCallGraph::Node *, int > &EdgeIndexMap, LazyCallGraph::Node &N, LazyCallGraph::Edge::Kind EK)
void switchOutgoingEdgeToCall(Node &SourceN, Node &TargetN)
Make an existing outgoing ref edge into a call edge.
static bool isKnownLibFunction(Function &F, TargetLibraryInfo &TLI)
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:154
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
An iterator used for the edges to both entry nodes and child nodes.
LazyCallGraphDOTPrinterPass(raw_ostream &OS)
std::string EscapeString(const std::string &Label)
Definition: GraphWriter.cpp:36
void swap(SmallVectorImpl &RHS)
Definition: SmallVector.h:678
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This is an important base class in LLVM.
Definition: Constant.h:42
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:129
Node & getNode() const
Get the call graph node referenced by this edge.
void switchOutgoingEdgeToRef(Node &SourceN, Node &TargetN)
Make an existing outgoing call edge into a ref edge.
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:371
void insertInternalRefEdge(Node &SourceN, Node &TargetN)
Insert a ref edge from one node in this RefSCC to another in this RefSCC.
static void printNodeDOT(raw_ostream &OS, LazyCallGraph::Node &N)
SmallVector< RefSCC *, 1 > insertIncomingRefEdge(Node &SourceN, Node &TargetN)
Insert an edge whose source is in a descendant RefSCC and target is in this RefSCC.
iterator end() const
A node in the call graph.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
A class used to represent edges in the call graph.
auto find_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range))
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1208
iterator erase(const_iterator CI)
Definition: SmallVector.h:445
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:160
size_t size() const
Definition: SmallVector.h:53
bool isParentOf(const RefSCC &RC) const
Test if this RefSCC is a parent of RC.
const std::string & getModuleIdentifier() const
Get the module identifier which is, essentially, the name of the module.
Definition: Module.h:209
bool verify(const TargetRegisterInfo &TRI) const
Check that information hold by this instance make sense for the given TRI.
constexpr bool empty(const T &RangeOrContainer)
Test whether RangeOrContainer is empty. Similar to C++17 std::empty.
Definition: STLExtras.h:204
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:418
void removeDeadFunction(Function &F)
Remove a dead function from the call graph (typically to delete it).
auto size(R &&Range, typename std::enable_if< std::is_same< typename std::iterator_traits< decltype(Range.begin())>::iterator_category, std::random_access_iterator_tag >::value, void >::type *=nullptr) -> decltype(std::distance(Range.begin(), Range.end()))
Get the size of a range.
Definition: STLExtras.h:1161
bool isParentOf(const SCC &C) const
Test if this SCC is a parent of C.
bool isFunctionVectorizable(StringRef F, unsigned VF) const
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:847
Module.h This file contains the declarations for the Module class.
Provides information about what library functions are available for the current target.
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
const DataFlowGraph & G
Definition: RDFGraph.cpp:211
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:381
SmallVector< RefSCC *, 1 > removeInternalRefEdge(Node &SourceN, ArrayRef< Node *> TargetNs)
Remove a list of ref edges which are entirely within this RefSCC.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
A range adaptor for a pair of iterators.
An iterator over specifically call edges.
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.
bool getLibFunc(StringRef funcName, LibFunc &F) const
Searches for a particular function name.
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:394
void switchTrivialInternalEdgeToRef(Node &SourceN, Node &TargetN)
Make an existing internal call edge between separate SCCs into a ref edge.
iterator_range< iterator > switchInternalEdgeToRef(Node &SourceN, Node &TargetN)
Make an existing internal call edge within a single SCC into a ref edge.
LazyCallGraphPrinterPass(raw_ostream &OS)
bool isAncestorOf(const RefSCC &RC) const
Test if this RefSCC is an ancestor of RC.
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:133
void emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:652
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:56
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:215
static void printRefSCC(raw_ostream &OS, LazyCallGraph::RefSCC &C)
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
uint32_t Size
Definition: Profile.cpp:47
static void printSCC(raw_ostream &OS, LazyCallGraph::SCC &C)
An analysis pass which computes the call graph for a module.
void insertTrivialRefEdge(Node &SourceN, Node &TargetN)
A convenience wrapper around the above to handle trivial cases of inserting a new ref edge...
const unsigned Kind
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
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...
LLVM Value Representation.
Definition: Value.h:73
An SCC of the call graph.
IteratorT begin() const
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:46
A container for analyses that lazily runs them and caches their results.
This header defines various interfaces for pass management in LLVM.
#define LLVM_DEBUG(X)
Definition: Debug.h:123
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...
IteratorT end() const
bool isDescendantOf(const RefSCC &RC) const
Test if this RefSCC is a descendant of RC.
iterator_range< postorder_ref_scc_iterator > postorder_ref_sccs()
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:71
bool use_empty() const
Definition: Value.h:323
bool isCall() const
Test whether the edge represents a direct call to a function.