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