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