1 | //===- LazyCallGraph.h - Analysis of a Module's call graph ------*- C++ -*-===// |
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 | /// \file |
9 | /// |
10 | /// Implements a lazy call graph analysis and related passes for the new pass |
11 | /// manager. |
12 | /// |
13 | /// NB: This is *not* a traditional call graph! It is a graph which models both |
14 | /// the current calls and potential calls. As a consequence there are many |
15 | /// edges in this call graph that do not correspond to a 'call' or 'invoke' |
16 | /// instruction. |
17 | /// |
18 | /// The primary use cases of this graph analysis is to facilitate iterating |
19 | /// across the functions of a module in ways that ensure all callees are |
20 | /// visited prior to a caller (given any SCC constraints), or vice versa. As |
21 | /// such is it particularly well suited to organizing CGSCC optimizations such |
22 | /// as inlining, outlining, argument promotion, etc. That is its primary use |
23 | /// case and motivates the design. It may not be appropriate for other |
24 | /// purposes. The use graph of functions or some other conservative analysis of |
25 | /// call instructions may be interesting for optimizations and subsequent |
26 | /// analyses which don't work in the context of an overly specified |
27 | /// potential-call-edge graph. |
28 | /// |
29 | /// To understand the specific rules and nature of this call graph analysis, |
30 | /// see the documentation of the \c LazyCallGraph below. |
31 | /// |
32 | //===----------------------------------------------------------------------===// |
33 | |
34 | #ifndef LLVM_ANALYSIS_LAZYCALLGRAPH_H |
35 | #define LLVM_ANALYSIS_LAZYCALLGRAPH_H |
36 | |
37 | #include "llvm/ADT/ArrayRef.h" |
38 | #include "llvm/ADT/DenseMap.h" |
39 | #include "llvm/ADT/PointerIntPair.h" |
40 | #include "llvm/ADT/SetVector.h" |
41 | #include "llvm/ADT/SmallVector.h" |
42 | #include "llvm/ADT/StringRef.h" |
43 | #include "llvm/ADT/iterator.h" |
44 | #include "llvm/ADT/iterator_range.h" |
45 | #include "llvm/Analysis/TargetLibraryInfo.h" |
46 | #include "llvm/IR/PassManager.h" |
47 | #include "llvm/Support/Allocator.h" |
48 | #include "llvm/Support/raw_ostream.h" |
49 | #include <cassert> |
50 | #include <iterator> |
51 | #include <optional> |
52 | #include <string> |
53 | #include <utility> |
54 | |
55 | namespace llvm { |
56 | |
57 | class Constant; |
58 | class Function; |
59 | template <class GraphType> struct GraphTraits; |
60 | class Module; |
61 | class TargetLibraryInfo; |
62 | class Value; |
63 | |
64 | /// A lazily constructed view of the call graph of a module. |
65 | /// |
66 | /// With the edges of this graph, the motivating constraint that we are |
67 | /// attempting to maintain is that function-local optimization, CGSCC-local |
68 | /// optimizations, and optimizations transforming a pair of functions connected |
69 | /// by an edge in the graph, do not invalidate a bottom-up traversal of the SCC |
70 | /// DAG. That is, no optimizations will delete, remove, or add an edge such |
71 | /// that functions already visited in a bottom-up order of the SCC DAG are no |
72 | /// longer valid to have visited, or such that functions not yet visited in |
73 | /// a bottom-up order of the SCC DAG are not required to have already been |
74 | /// visited. |
75 | /// |
76 | /// Within this constraint, the desire is to minimize the merge points of the |
77 | /// SCC DAG. The greater the fanout of the SCC DAG and the fewer merge points |
78 | /// in the SCC DAG, the more independence there is in optimizing within it. |
79 | /// There is a strong desire to enable parallelization of optimizations over |
80 | /// the call graph, and both limited fanout and merge points will (artificially |
81 | /// in some cases) limit the scaling of such an effort. |
82 | /// |
83 | /// To this end, graph represents both direct and any potential resolution to |
84 | /// an indirect call edge. Another way to think about it is that it represents |
85 | /// both the direct call edges and any direct call edges that might be formed |
86 | /// through static optimizations. Specifically, it considers taking the address |
87 | /// of a function to be an edge in the call graph because this might be |
88 | /// forwarded to become a direct call by some subsequent function-local |
89 | /// optimization. The result is that the graph closely follows the use-def |
90 | /// edges for functions. Walking "up" the graph can be done by looking at all |
91 | /// of the uses of a function. |
92 | /// |
93 | /// The roots of the call graph are the external functions and functions |
94 | /// escaped into global variables. Those functions can be called from outside |
95 | /// of the module or via unknowable means in the IR -- we may not be able to |
96 | /// form even a potential call edge from a function body which may dynamically |
97 | /// load the function and call it. |
98 | /// |
99 | /// This analysis still requires updates to remain valid after optimizations |
100 | /// which could potentially change the set of potential callees. The |
101 | /// constraints it operates under only make the traversal order remain valid. |
102 | /// |
103 | /// The entire analysis must be re-computed if full interprocedural |
104 | /// optimizations run at any point. For example, globalopt completely |
105 | /// invalidates the information in this analysis. |
106 | /// |
107 | /// FIXME: This class is named LazyCallGraph in a lame attempt to distinguish |
108 | /// it from the existing CallGraph. At some point, it is expected that this |
109 | /// will be the only call graph and it will be renamed accordingly. |
110 | class LazyCallGraph { |
111 | public: |
112 | class Node; |
113 | class EdgeSequence; |
114 | class SCC; |
115 | class RefSCC; |
116 | |
117 | /// A class used to represent edges in the call graph. |
118 | /// |
119 | /// The lazy call graph models both *call* edges and *reference* edges. Call |
120 | /// edges are much what you would expect, and exist when there is a 'call' or |
121 | /// 'invoke' instruction of some function. Reference edges are also tracked |
122 | /// along side these, and exist whenever any instruction (transitively |
123 | /// through its operands) references a function. All call edges are |
124 | /// inherently reference edges, and so the reference graph forms a superset |
125 | /// of the formal call graph. |
126 | /// |
127 | /// All of these forms of edges are fundamentally represented as outgoing |
128 | /// edges. The edges are stored in the source node and point at the target |
129 | /// node. This allows the edge structure itself to be a very compact data |
130 | /// structure: essentially a tagged pointer. |
131 | class Edge { |
132 | public: |
133 | /// The kind of edge in the graph. |
134 | enum Kind : bool { Ref = false, Call = true }; |
135 | |
136 | Edge(); |
137 | explicit Edge(Node &N, Kind K); |
138 | |
139 | /// Test whether the edge is null. |
140 | /// |
141 | /// This happens when an edge has been deleted. We leave the edge objects |
142 | /// around but clear them. |
143 | explicit operator bool() const; |
144 | |
145 | /// Returns the \c Kind of the edge. |
146 | Kind getKind() const; |
147 | |
148 | /// Test whether the edge represents a direct call to a function. |
149 | /// |
150 | /// This requires that the edge is not null. |
151 | bool isCall() const; |
152 | |
153 | /// Get the call graph node referenced by this edge. |
154 | /// |
155 | /// This requires that the edge is not null. |
156 | Node &getNode() const; |
157 | |
158 | /// Get the function referenced by this edge. |
159 | /// |
160 | /// This requires that the edge is not null. |
161 | Function &getFunction() const; |
162 | |
163 | private: |
164 | friend class LazyCallGraph::EdgeSequence; |
165 | friend class LazyCallGraph::RefSCC; |
166 | |
167 | PointerIntPair<Node *, 1, Kind> Value; |
168 | |
169 | void setKind(Kind K) { Value.setInt(K); } |
170 | }; |
171 | |
172 | /// The edge sequence object. |
173 | /// |
174 | /// This typically exists entirely within the node but is exposed as |
175 | /// a separate type because a node doesn't initially have edges. An explicit |
176 | /// population step is required to produce this sequence at first and it is |
177 | /// then cached in the node. It is also used to represent edges entering the |
178 | /// graph from outside the module to model the graph's roots. |
179 | /// |
180 | /// The sequence itself both iterable and indexable. The indexes remain |
181 | /// stable even as the sequence mutates (including removal). |
182 | class EdgeSequence { |
183 | friend class LazyCallGraph; |
184 | friend class LazyCallGraph::Node; |
185 | friend class LazyCallGraph::RefSCC; |
186 | |
187 | using VectorT = SmallVector<Edge, 4>; |
188 | using VectorImplT = SmallVectorImpl<Edge>; |
189 | |
190 | public: |
191 | /// An iterator used for the edges to both entry nodes and child nodes. |
192 | class iterator |
193 | : public iterator_adaptor_base<iterator, VectorImplT::iterator, |
194 | std::forward_iterator_tag> { |
195 | friend class LazyCallGraph; |
196 | friend class LazyCallGraph::Node; |
197 | |
198 | VectorImplT::iterator E; |
199 | |
200 | // Build the iterator for a specific position in the edge list. |
201 | iterator(VectorImplT::iterator BaseI, VectorImplT::iterator E) |
202 | : iterator_adaptor_base(BaseI), E(E) { |
203 | while (I != E && !*I) |
204 | ++I; |
205 | } |
206 | |
207 | public: |
208 | iterator() = default; |
209 | |
210 | using iterator_adaptor_base::operator++; |
211 | iterator &operator++() { |
212 | do { |
213 | ++I; |
214 | } while (I != E && !*I); |
215 | return *this; |
216 | } |
217 | }; |
218 | |
219 | /// An iterator over specifically call edges. |
220 | /// |
221 | /// This has the same iteration properties as the \c iterator, but |
222 | /// restricts itself to edges which represent actual calls. |
223 | class call_iterator |
224 | : public iterator_adaptor_base<call_iterator, VectorImplT::iterator, |
225 | std::forward_iterator_tag> { |
226 | friend class LazyCallGraph; |
227 | friend class LazyCallGraph::Node; |
228 | |
229 | VectorImplT::iterator E; |
230 | |
231 | /// Advance the iterator to the next valid, call edge. |
232 | void advanceToNextEdge() { |
233 | while (I != E && (!*I || !I->isCall())) |
234 | ++I; |
235 | } |
236 | |
237 | // Build the iterator for a specific position in the edge list. |
238 | call_iterator(VectorImplT::iterator BaseI, VectorImplT::iterator E) |
239 | : iterator_adaptor_base(BaseI), E(E) { |
240 | advanceToNextEdge(); |
241 | } |
242 | |
243 | public: |
244 | call_iterator() = default; |
245 | |
246 | using iterator_adaptor_base::operator++; |
247 | call_iterator &operator++() { |
248 | ++I; |
249 | advanceToNextEdge(); |
250 | return *this; |
251 | } |
252 | }; |
253 | |
254 | iterator begin() { return iterator(Edges.begin(), Edges.end()); } |
255 | iterator end() { return iterator(Edges.end(), Edges.end()); } |
256 | |
257 | Edge &operator[](Node &N) { |
258 | assert(EdgeIndexMap.contains(&N) && "No such edge!" ); |
259 | auto &E = Edges[EdgeIndexMap.find(Val: &N)->second]; |
260 | assert(E && "Dead or null edge!" ); |
261 | return E; |
262 | } |
263 | |
264 | Edge *lookup(Node &N) { |
265 | auto EI = EdgeIndexMap.find(Val: &N); |
266 | if (EI == EdgeIndexMap.end()) |
267 | return nullptr; |
268 | auto &E = Edges[EI->second]; |
269 | return E ? &E : nullptr; |
270 | } |
271 | |
272 | call_iterator call_begin() { |
273 | return call_iterator(Edges.begin(), Edges.end()); |
274 | } |
275 | call_iterator call_end() { return call_iterator(Edges.end(), Edges.end()); } |
276 | |
277 | iterator_range<call_iterator> calls() { |
278 | return make_range(x: call_begin(), y: call_end()); |
279 | } |
280 | |
281 | bool empty() { |
282 | for (auto &E : Edges) |
283 | if (E) |
284 | return false; |
285 | |
286 | return true; |
287 | } |
288 | |
289 | private: |
290 | VectorT Edges; |
291 | DenseMap<Node *, int> EdgeIndexMap; |
292 | |
293 | EdgeSequence() = default; |
294 | |
295 | /// Internal helper to insert an edge to a node. |
296 | void insertEdgeInternal(Node &ChildN, Edge::Kind EK); |
297 | |
298 | /// Internal helper to change an edge kind. |
299 | void setEdgeKind(Node &ChildN, Edge::Kind EK); |
300 | |
301 | /// Internal helper to remove the edge to the given function. |
302 | bool removeEdgeInternal(Node &ChildN); |
303 | }; |
304 | |
305 | /// A node in the call graph. |
306 | /// |
307 | /// This represents a single node. Its primary roles are to cache the list of |
308 | /// callees, de-duplicate and provide fast testing of whether a function is a |
309 | /// callee, and facilitate iteration of child nodes in the graph. |
310 | /// |
311 | /// The node works much like an optional in order to lazily populate the |
312 | /// edges of each node. Until populated, there are no edges. Once populated, |
313 | /// you can access the edges by dereferencing the node or using the `->` |
314 | /// operator as if the node was an `std::optional<EdgeSequence>`. |
315 | class Node { |
316 | friend class LazyCallGraph; |
317 | friend class LazyCallGraph::RefSCC; |
318 | |
319 | public: |
320 | LazyCallGraph &getGraph() const { return *G; } |
321 | |
322 | Function &getFunction() const { return *F; } |
323 | |
324 | StringRef getName() const { return F->getName(); } |
325 | |
326 | /// Equality is defined as address equality. |
327 | bool operator==(const Node &N) const { return this == &N; } |
328 | bool operator!=(const Node &N) const { return !operator==(N); } |
329 | |
330 | /// Tests whether the node has been populated with edges. |
331 | bool isPopulated() const { return Edges.has_value(); } |
332 | |
333 | /// Tests whether this is actually a dead node and no longer valid. |
334 | /// |
335 | /// Users rarely interact with nodes in this state and other methods are |
336 | /// invalid. This is used to model a node in an edge list where the |
337 | /// function has been completely removed. |
338 | bool isDead() const { |
339 | assert(!G == !F && |
340 | "Both graph and function pointers should be null or non-null." ); |
341 | return !G; |
342 | } |
343 | |
344 | // We allow accessing the edges by dereferencing or using the arrow |
345 | // operator, essentially wrapping the internal optional. |
346 | EdgeSequence &operator*() const { |
347 | // Rip const off because the node itself isn't changing here. |
348 | return const_cast<EdgeSequence &>(*Edges); |
349 | } |
350 | EdgeSequence *operator->() const { return &**this; } |
351 | |
352 | /// Populate the edges of this node if necessary. |
353 | /// |
354 | /// The first time this is called it will populate the edges for this node |
355 | /// in the graph. It does this by scanning the underlying function, so once |
356 | /// this is done, any changes to that function must be explicitly reflected |
357 | /// in updates to the graph. |
358 | /// |
359 | /// \returns the populated \c EdgeSequence to simplify walking it. |
360 | /// |
361 | /// This will not update or re-scan anything if called repeatedly. Instead, |
362 | /// the edge sequence is cached and returned immediately on subsequent |
363 | /// calls. |
364 | EdgeSequence &populate() { |
365 | if (Edges) |
366 | return *Edges; |
367 | |
368 | return populateSlow(); |
369 | } |
370 | |
371 | private: |
372 | LazyCallGraph *G; |
373 | Function *F; |
374 | |
375 | // We provide for the DFS numbering and Tarjan walk lowlink numbers to be |
376 | // stored directly within the node. These are both '-1' when nodes are part |
377 | // of an SCC (or RefSCC), or '0' when not yet reached in a DFS walk. |
378 | int DFSNumber = 0; |
379 | int LowLink = 0; |
380 | |
381 | std::optional<EdgeSequence> Edges; |
382 | |
383 | /// Basic constructor implements the scanning of F into Edges and |
384 | /// EdgeIndexMap. |
385 | Node(LazyCallGraph &G, Function &F) : G(&G), F(&F) {} |
386 | |
387 | /// Implementation of the scan when populating. |
388 | EdgeSequence &populateSlow(); |
389 | |
390 | /// Internal helper to directly replace the function with a new one. |
391 | /// |
392 | /// This is used to facilitate transformations which need to replace the |
393 | /// formal Function object but directly move the body and users from one to |
394 | /// the other. |
395 | void replaceFunction(Function &NewF); |
396 | |
397 | void clear() { Edges.reset(); } |
398 | |
399 | /// Print the name of this node's function. |
400 | friend raw_ostream &operator<<(raw_ostream &OS, const Node &N) { |
401 | return OS << N.F->getName(); |
402 | } |
403 | |
404 | /// Dump the name of this node's function to stderr. |
405 | void dump() const; |
406 | }; |
407 | |
408 | /// An SCC of the call graph. |
409 | /// |
410 | /// This represents a Strongly Connected Component of the direct call graph |
411 | /// -- ignoring indirect calls and function references. It stores this as |
412 | /// a collection of call graph nodes. While the order of nodes in the SCC is |
413 | /// stable, it is not any particular order. |
414 | /// |
415 | /// The SCCs are nested within a \c RefSCC, see below for details about that |
416 | /// outer structure. SCCs do not support mutation of the call graph, that |
417 | /// must be done through the containing \c RefSCC in order to fully reason |
418 | /// about the ordering and connections of the graph. |
419 | class LLVM_EXTERNAL_VISIBILITY SCC { |
420 | friend class LazyCallGraph; |
421 | friend class LazyCallGraph::Node; |
422 | |
423 | RefSCC *OuterRefSCC; |
424 | SmallVector<Node *, 1> Nodes; |
425 | |
426 | template <typename NodeRangeT> |
427 | SCC(RefSCC &OuterRefSCC, NodeRangeT &&Nodes) |
428 | : OuterRefSCC(&OuterRefSCC), Nodes(std::forward<NodeRangeT>(Nodes)) {} |
429 | |
430 | void clear() { |
431 | OuterRefSCC = nullptr; |
432 | Nodes.clear(); |
433 | } |
434 | |
435 | /// Print a short description useful for debugging or logging. |
436 | /// |
437 | /// We print the function names in the SCC wrapped in '()'s and skipping |
438 | /// the middle functions if there are a large number. |
439 | // |
440 | // Note: this is defined inline to dodge issues with GCC's interpretation |
441 | // of enclosing namespaces for friend function declarations. |
442 | friend raw_ostream &operator<<(raw_ostream &OS, const SCC &C) { |
443 | OS << '('; |
444 | int I = 0; |
445 | for (LazyCallGraph::Node &N : C) { |
446 | if (I > 0) |
447 | OS << ", " ; |
448 | // Elide the inner elements if there are too many. |
449 | if (I > 8) { |
450 | OS << "..., " << *C.Nodes.back(); |
451 | break; |
452 | } |
453 | OS << N; |
454 | ++I; |
455 | } |
456 | OS << ')'; |
457 | return OS; |
458 | } |
459 | |
460 | /// Dump a short description of this SCC to stderr. |
461 | void dump() const; |
462 | |
463 | #if !defined(NDEBUG) || defined(EXPENSIVE_CHECKS) |
464 | /// Verify invariants about the SCC. |
465 | /// |
466 | /// This will attempt to validate all of the basic invariants within an |
467 | /// SCC, but not that it is a strongly connected component per se. |
468 | /// Primarily useful while building and updating the graph to check that |
469 | /// basic properties are in place rather than having inexplicable crashes |
470 | /// later. |
471 | void verify(); |
472 | #endif |
473 | |
474 | public: |
475 | using iterator = pointee_iterator<SmallVectorImpl<Node *>::const_iterator>; |
476 | |
477 | iterator begin() const { return Nodes.begin(); } |
478 | iterator end() const { return Nodes.end(); } |
479 | |
480 | int size() const { return Nodes.size(); } |
481 | |
482 | RefSCC &getOuterRefSCC() const { return *OuterRefSCC; } |
483 | |
484 | /// Test if this SCC is a parent of \a C. |
485 | /// |
486 | /// Note that this is linear in the number of edges departing the current |
487 | /// SCC. |
488 | bool isParentOf(const SCC &C) const; |
489 | |
490 | /// Test if this SCC is an ancestor of \a C. |
491 | /// |
492 | /// Note that in the worst case this is linear in the number of edges |
493 | /// departing the current SCC and every SCC in the entire graph reachable |
494 | /// from this SCC. Thus this very well may walk every edge in the entire |
495 | /// call graph! Do not call this in a tight loop! |
496 | bool isAncestorOf(const SCC &C) const; |
497 | |
498 | /// Test if this SCC is a child of \a C. |
499 | /// |
500 | /// See the comments for \c isParentOf for detailed notes about the |
501 | /// complexity of this routine. |
502 | bool isChildOf(const SCC &C) const { return C.isParentOf(C: *this); } |
503 | |
504 | /// Test if this SCC is a descendant of \a C. |
505 | /// |
506 | /// See the comments for \c isParentOf for detailed notes about the |
507 | /// complexity of this routine. |
508 | bool isDescendantOf(const SCC &C) const { return C.isAncestorOf(C: *this); } |
509 | |
510 | /// Provide a short name by printing this SCC to a std::string. |
511 | /// |
512 | /// This copes with the fact that we don't have a name per se for an SCC |
513 | /// while still making the use of this in debugging and logging useful. |
514 | std::string getName() const { |
515 | std::string Name; |
516 | raw_string_ostream OS(Name); |
517 | OS << *this; |
518 | OS.flush(); |
519 | return Name; |
520 | } |
521 | }; |
522 | |
523 | /// A RefSCC of the call graph. |
524 | /// |
525 | /// This models a Strongly Connected Component of function reference edges in |
526 | /// the call graph. As opposed to actual SCCs, these can be used to scope |
527 | /// subgraphs of the module which are independent from other subgraphs of the |
528 | /// module because they do not reference it in any way. This is also the unit |
529 | /// where we do mutation of the graph in order to restrict mutations to those |
530 | /// which don't violate this independence. |
531 | /// |
532 | /// A RefSCC contains a DAG of actual SCCs. All the nodes within the RefSCC |
533 | /// are necessarily within some actual SCC that nests within it. Since |
534 | /// a direct call *is* a reference, there will always be at least one RefSCC |
535 | /// around any SCC. |
536 | /// |
537 | /// Spurious ref edges, meaning ref edges that still exist in the call graph |
538 | /// even though the corresponding IR reference no longer exists, are allowed. |
539 | /// This is mostly to support argument promotion, which can modify a caller to |
540 | /// no longer pass a function. The only place that needs to specially handle |
541 | /// this is deleting a dead function/node, otherwise the dead ref edges are |
542 | /// automatically removed when visiting the function/node no longer containing |
543 | /// the ref edge. |
544 | class RefSCC { |
545 | friend class LazyCallGraph; |
546 | friend class LazyCallGraph::Node; |
547 | |
548 | LazyCallGraph *G; |
549 | |
550 | /// A postorder list of the inner SCCs. |
551 | SmallVector<SCC *, 4> SCCs; |
552 | |
553 | /// A map from SCC to index in the postorder list. |
554 | SmallDenseMap<SCC *, int, 4> SCCIndices; |
555 | |
556 | /// Fast-path constructor. RefSCCs should instead be constructed by calling |
557 | /// formRefSCCFast on the graph itself. |
558 | RefSCC(LazyCallGraph &G); |
559 | |
560 | void clear() { |
561 | SCCs.clear(); |
562 | SCCIndices.clear(); |
563 | } |
564 | |
565 | /// Print a short description useful for debugging or logging. |
566 | /// |
567 | /// We print the SCCs wrapped in '[]'s and skipping the middle SCCs if |
568 | /// there are a large number. |
569 | // |
570 | // Note: this is defined inline to dodge issues with GCC's interpretation |
571 | // of enclosing namespaces for friend function declarations. |
572 | friend raw_ostream &operator<<(raw_ostream &OS, const RefSCC &RC) { |
573 | OS << '['; |
574 | int I = 0; |
575 | for (LazyCallGraph::SCC &C : RC) { |
576 | if (I > 0) |
577 | OS << ", " ; |
578 | // Elide the inner elements if there are too many. |
579 | if (I > 4) { |
580 | OS << "..., " << *RC.SCCs.back(); |
581 | break; |
582 | } |
583 | OS << C; |
584 | ++I; |
585 | } |
586 | OS << ']'; |
587 | return OS; |
588 | } |
589 | |
590 | /// Dump a short description of this RefSCC to stderr. |
591 | void dump() const; |
592 | |
593 | #if !defined(NDEBUG) || defined(EXPENSIVE_CHECKS) |
594 | /// Verify invariants about the RefSCC and all its SCCs. |
595 | /// |
596 | /// This will attempt to validate all of the invariants *within* the |
597 | /// RefSCC, but not that it is a strongly connected component of the larger |
598 | /// graph. This makes it useful even when partially through an update. |
599 | /// |
600 | /// Invariants checked: |
601 | /// - SCCs and their indices match. |
602 | /// - The SCCs list is in fact in post-order. |
603 | void verify(); |
604 | #endif |
605 | |
606 | public: |
607 | using iterator = pointee_iterator<SmallVectorImpl<SCC *>::const_iterator>; |
608 | using range = iterator_range<iterator>; |
609 | using parent_iterator = |
610 | pointee_iterator<SmallPtrSetImpl<RefSCC *>::const_iterator>; |
611 | |
612 | iterator begin() const { return SCCs.begin(); } |
613 | iterator end() const { return SCCs.end(); } |
614 | |
615 | ssize_t size() const { return SCCs.size(); } |
616 | |
617 | SCC &operator[](int Idx) { return *SCCs[Idx]; } |
618 | |
619 | iterator find(SCC &C) const { |
620 | return SCCs.begin() + SCCIndices.find(Val: &C)->second; |
621 | } |
622 | |
623 | /// Test if this RefSCC is a parent of \a RC. |
624 | /// |
625 | /// CAUTION: This method walks every edge in the \c RefSCC, it can be very |
626 | /// expensive. |
627 | bool isParentOf(const RefSCC &RC) const; |
628 | |
629 | /// Test if this RefSCC is an ancestor of \a RC. |
630 | /// |
631 | /// CAUTION: This method walks the directed graph of edges as far as |
632 | /// necessary to find a possible path to the argument. In the worst case |
633 | /// this may walk the entire graph and can be extremely expensive. |
634 | bool isAncestorOf(const RefSCC &RC) const; |
635 | |
636 | /// Test if this RefSCC is a child of \a RC. |
637 | /// |
638 | /// CAUTION: This method walks every edge in the argument \c RefSCC, it can |
639 | /// be very expensive. |
640 | bool isChildOf(const RefSCC &RC) const { return RC.isParentOf(RC: *this); } |
641 | |
642 | /// Test if this RefSCC is a descendant of \a RC. |
643 | /// |
644 | /// CAUTION: This method walks the directed graph of edges as far as |
645 | /// necessary to find a possible path from the argument. In the worst case |
646 | /// this may walk the entire graph and can be extremely expensive. |
647 | bool isDescendantOf(const RefSCC &RC) const { |
648 | return RC.isAncestorOf(RC: *this); |
649 | } |
650 | |
651 | /// Provide a short name by printing this RefSCC to a std::string. |
652 | /// |
653 | /// This copes with the fact that we don't have a name per se for an RefSCC |
654 | /// while still making the use of this in debugging and logging useful. |
655 | std::string getName() const { |
656 | std::string Name; |
657 | raw_string_ostream OS(Name); |
658 | OS << *this; |
659 | OS.flush(); |
660 | return Name; |
661 | } |
662 | |
663 | ///@{ |
664 | /// \name Mutation API |
665 | /// |
666 | /// These methods provide the core API for updating the call graph in the |
667 | /// presence of (potentially still in-flight) DFS-found RefSCCs and SCCs. |
668 | /// |
669 | /// Note that these methods sometimes have complex runtimes, so be careful |
670 | /// how you call them. |
671 | |
672 | /// Make an existing internal ref edge into a call edge. |
673 | /// |
674 | /// This may form a larger cycle and thus collapse SCCs into TargetN's SCC. |
675 | /// If that happens, the optional callback \p MergedCB will be invoked (if |
676 | /// provided) on the SCCs being merged away prior to actually performing |
677 | /// the merge. Note that this will never include the target SCC as that |
678 | /// will be the SCC functions are merged into to resolve the cycle. Once |
679 | /// this function returns, these merged SCCs are not in a valid state but |
680 | /// the pointers will remain valid until destruction of the parent graph |
681 | /// instance for the purpose of clearing cached information. This function |
682 | /// also returns 'true' if a cycle was formed and some SCCs merged away as |
683 | /// a convenience. |
684 | /// |
685 | /// After this operation, both SourceN's SCC and TargetN's SCC may move |
686 | /// position within this RefSCC's postorder list. Any SCCs merged are |
687 | /// merged into the TargetN's SCC in order to preserve reachability analyses |
688 | /// which took place on that SCC. |
689 | bool switchInternalEdgeToCall( |
690 | Node &SourceN, Node &TargetN, |
691 | function_ref<void(ArrayRef<SCC *> MergedSCCs)> MergeCB = {}); |
692 | |
693 | /// Make an existing internal call edge between separate SCCs into a ref |
694 | /// edge. |
695 | /// |
696 | /// If SourceN and TargetN in separate SCCs within this RefSCC, changing |
697 | /// the call edge between them to a ref edge is a trivial operation that |
698 | /// does not require any structural changes to the call graph. |
699 | void switchTrivialInternalEdgeToRef(Node &SourceN, Node &TargetN); |
700 | |
701 | /// Make an existing internal call edge within a single SCC into a ref |
702 | /// edge. |
703 | /// |
704 | /// Since SourceN and TargetN are part of a single SCC, this SCC may be |
705 | /// split up due to breaking a cycle in the call edges that formed it. If |
706 | /// that happens, then this routine will insert new SCCs into the postorder |
707 | /// list *before* the SCC of TargetN (previously the SCC of both). This |
708 | /// preserves postorder as the TargetN can reach all of the other nodes by |
709 | /// definition of previously being in a single SCC formed by the cycle from |
710 | /// SourceN to TargetN. |
711 | /// |
712 | /// The newly added SCCs are added *immediately* and contiguously |
713 | /// prior to the TargetN SCC and return the range covering the new SCCs in |
714 | /// the RefSCC's postorder sequence. You can directly iterate the returned |
715 | /// range to observe all of the new SCCs in postorder. |
716 | /// |
717 | /// Note that if SourceN and TargetN are in separate SCCs, the simpler |
718 | /// routine `switchTrivialInternalEdgeToRef` should be used instead. |
719 | iterator_range<iterator> switchInternalEdgeToRef(Node &SourceN, |
720 | Node &TargetN); |
721 | |
722 | /// Make an existing outgoing ref edge into a call edge. |
723 | /// |
724 | /// Note that this is trivial as there are no cyclic impacts and there |
725 | /// remains a reference edge. |
726 | void switchOutgoingEdgeToCall(Node &SourceN, Node &TargetN); |
727 | |
728 | /// Make an existing outgoing call edge into a ref edge. |
729 | /// |
730 | /// This is trivial as there are no cyclic impacts and there remains |
731 | /// a reference edge. |
732 | void switchOutgoingEdgeToRef(Node &SourceN, Node &TargetN); |
733 | |
734 | /// Insert a ref edge from one node in this RefSCC to another in this |
735 | /// RefSCC. |
736 | /// |
737 | /// This is always a trivial operation as it doesn't change any part of the |
738 | /// graph structure besides connecting the two nodes. |
739 | /// |
740 | /// Note that we don't support directly inserting internal *call* edges |
741 | /// because that could change the graph structure and requires returning |
742 | /// information about what became invalid. As a consequence, the pattern |
743 | /// should be to first insert the necessary ref edge, and then to switch it |
744 | /// to a call edge if needed and handle any invalidation that results. See |
745 | /// the \c switchInternalEdgeToCall routine for details. |
746 | void insertInternalRefEdge(Node &SourceN, Node &TargetN); |
747 | |
748 | /// Insert an edge whose parent is in this RefSCC and child is in some |
749 | /// child RefSCC. |
750 | /// |
751 | /// There must be an existing path from the \p SourceN to the \p TargetN. |
752 | /// This operation is inexpensive and does not change the set of SCCs and |
753 | /// RefSCCs in the graph. |
754 | void insertOutgoingEdge(Node &SourceN, Node &TargetN, Edge::Kind EK); |
755 | |
756 | /// Insert an edge whose source is in a descendant RefSCC and target is in |
757 | /// this RefSCC. |
758 | /// |
759 | /// There must be an existing path from the target to the source in this |
760 | /// case. |
761 | /// |
762 | /// NB! This is has the potential to be a very expensive function. It |
763 | /// inherently forms a cycle in the prior RefSCC DAG and we have to merge |
764 | /// RefSCCs to resolve that cycle. But finding all of the RefSCCs which |
765 | /// participate in the cycle can in the worst case require traversing every |
766 | /// RefSCC in the graph. Every attempt is made to avoid that, but passes |
767 | /// must still exercise caution calling this routine repeatedly. |
768 | /// |
769 | /// Also note that this can only insert ref edges. In order to insert |
770 | /// a call edge, first insert a ref edge and then switch it to a call edge. |
771 | /// These are intentionally kept as separate interfaces because each step |
772 | /// of the operation invalidates a different set of data structures. |
773 | /// |
774 | /// This returns all the RefSCCs which were merged into the this RefSCC |
775 | /// (the target's). This allows callers to invalidate any cached |
776 | /// information. |
777 | /// |
778 | /// FIXME: We could possibly optimize this quite a bit for cases where the |
779 | /// caller and callee are very nearby in the graph. See comments in the |
780 | /// implementation for details, but that use case might impact users. |
781 | SmallVector<RefSCC *, 1> insertIncomingRefEdge(Node &SourceN, |
782 | Node &TargetN); |
783 | |
784 | /// Remove an edge whose source is in this RefSCC and target is *not*. |
785 | /// |
786 | /// This removes an inter-RefSCC edge. All inter-RefSCC edges originating |
787 | /// from this SCC have been fully explored by any in-flight DFS graph |
788 | /// formation, so this is always safe to call once you have the source |
789 | /// RefSCC. |
790 | /// |
791 | /// This operation does not change the cyclic structure of the graph and so |
792 | /// is very inexpensive. It may change the connectivity graph of the SCCs |
793 | /// though, so be careful calling this while iterating over them. |
794 | void removeOutgoingEdge(Node &SourceN, Node &TargetN); |
795 | |
796 | /// Remove a list of ref edges which are entirely within this RefSCC. |
797 | /// |
798 | /// Both the \a SourceN and all of the \a TargetNs must be within this |
799 | /// RefSCC. Removing these edges may break cycles that form this RefSCC and |
800 | /// thus this operation may change the RefSCC graph significantly. In |
801 | /// particular, this operation will re-form new RefSCCs based on the |
802 | /// remaining connectivity of the graph. The following invariants are |
803 | /// guaranteed to hold after calling this method: |
804 | /// |
805 | /// 1) If a ref-cycle remains after removal, it leaves this RefSCC intact |
806 | /// and in the graph. No new RefSCCs are built. |
807 | /// 2) Otherwise, this RefSCC will be dead after this call and no longer in |
808 | /// the graph or the postorder traversal of the call graph. Any iterator |
809 | /// pointing at this RefSCC will become invalid. |
810 | /// 3) All newly formed RefSCCs will be returned and the order of the |
811 | /// RefSCCs returned will be a valid postorder traversal of the new |
812 | /// RefSCCs. |
813 | /// 4) No RefSCC other than this RefSCC has its member set changed (this is |
814 | /// inherent in the definition of removing such an edge). |
815 | /// |
816 | /// These invariants are very important to ensure that we can build |
817 | /// optimization pipelines on top of the CGSCC pass manager which |
818 | /// intelligently update the RefSCC graph without invalidating other parts |
819 | /// of the RefSCC graph. |
820 | /// |
821 | /// Note that we provide no routine to remove a *call* edge. Instead, you |
822 | /// must first switch it to a ref edge using \c switchInternalEdgeToRef. |
823 | /// This split API is intentional as each of these two steps can invalidate |
824 | /// a different aspect of the graph structure and needs to have the |
825 | /// invalidation handled independently. |
826 | /// |
827 | /// The runtime complexity of this method is, in the worst case, O(V+E) |
828 | /// where V is the number of nodes in this RefSCC and E is the number of |
829 | /// edges leaving the nodes in this RefSCC. Note that E includes both edges |
830 | /// within this RefSCC and edges from this RefSCC to child RefSCCs. Some |
831 | /// effort has been made to minimize the overhead of common cases such as |
832 | /// self-edges and edge removals which result in a spanning tree with no |
833 | /// more cycles. |
834 | [[nodiscard]] SmallVector<RefSCC *, 1> |
835 | removeInternalRefEdge(Node &SourceN, ArrayRef<Node *> TargetNs); |
836 | |
837 | /// A convenience wrapper around the above to handle trivial cases of |
838 | /// inserting a new call edge. |
839 | /// |
840 | /// This is trivial whenever the target is in the same SCC as the source or |
841 | /// the edge is an outgoing edge to some descendant SCC. In these cases |
842 | /// there is no change to the cyclic structure of SCCs or RefSCCs. |
843 | /// |
844 | /// To further make calling this convenient, it also handles inserting |
845 | /// already existing edges. |
846 | void insertTrivialCallEdge(Node &SourceN, Node &TargetN); |
847 | |
848 | /// A convenience wrapper around the above to handle trivial cases of |
849 | /// inserting a new ref edge. |
850 | /// |
851 | /// This is trivial whenever the target is in the same RefSCC as the source |
852 | /// or the edge is an outgoing edge to some descendant RefSCC. In these |
853 | /// cases there is no change to the cyclic structure of the RefSCCs. |
854 | /// |
855 | /// To further make calling this convenient, it also handles inserting |
856 | /// already existing edges. |
857 | void insertTrivialRefEdge(Node &SourceN, Node &TargetN); |
858 | |
859 | /// Directly replace a node's function with a new function. |
860 | /// |
861 | /// This should be used when moving the body and users of a function to |
862 | /// a new formal function object but not otherwise changing the call graph |
863 | /// structure in any way. |
864 | /// |
865 | /// It requires that the old function in the provided node have zero uses |
866 | /// and the new function must have calls and references to it establishing |
867 | /// an equivalent graph. |
868 | void replaceNodeFunction(Node &N, Function &NewF); |
869 | |
870 | ///@} |
871 | }; |
872 | |
873 | /// A post-order depth-first RefSCC iterator over the call graph. |
874 | /// |
875 | /// This iterator walks the cached post-order sequence of RefSCCs. However, |
876 | /// it trades stability for flexibility. It is restricted to a forward |
877 | /// iterator but will survive mutations which insert new RefSCCs and continue |
878 | /// to point to the same RefSCC even if it moves in the post-order sequence. |
879 | class postorder_ref_scc_iterator |
880 | : public iterator_facade_base<postorder_ref_scc_iterator, |
881 | std::forward_iterator_tag, RefSCC> { |
882 | friend class LazyCallGraph; |
883 | friend class LazyCallGraph::Node; |
884 | |
885 | /// Nonce type to select the constructor for the end iterator. |
886 | struct IsAtEndT {}; |
887 | |
888 | LazyCallGraph *G; |
889 | RefSCC *RC = nullptr; |
890 | |
891 | /// Build the begin iterator for a node. |
892 | postorder_ref_scc_iterator(LazyCallGraph &G) : G(&G), RC(getRC(G, Index: 0)) { |
893 | incrementUntilNonEmptyRefSCC(); |
894 | } |
895 | |
896 | /// Build the end iterator for a node. This is selected purely by overload. |
897 | postorder_ref_scc_iterator(LazyCallGraph &G, IsAtEndT /*Nonce*/) : G(&G) {} |
898 | |
899 | /// Get the post-order RefSCC at the given index of the postorder walk, |
900 | /// populating it if necessary. |
901 | static RefSCC *getRC(LazyCallGraph &G, int Index) { |
902 | if (Index == (int)G.PostOrderRefSCCs.size()) |
903 | // We're at the end. |
904 | return nullptr; |
905 | |
906 | return G.PostOrderRefSCCs[Index]; |
907 | } |
908 | |
909 | // Keep incrementing until RC is non-empty (or null). |
910 | void incrementUntilNonEmptyRefSCC() { |
911 | while (RC && RC->size() == 0) |
912 | increment(); |
913 | } |
914 | |
915 | void increment() { |
916 | assert(RC && "Cannot increment the end iterator!" ); |
917 | RC = getRC(G&: *G, Index: G->RefSCCIndices.find(Val: RC)->second + 1); |
918 | } |
919 | |
920 | public: |
921 | bool operator==(const postorder_ref_scc_iterator &Arg) const { |
922 | return G == Arg.G && RC == Arg.RC; |
923 | } |
924 | |
925 | reference operator*() const { return *RC; } |
926 | |
927 | using iterator_facade_base::operator++; |
928 | postorder_ref_scc_iterator &operator++() { |
929 | increment(); |
930 | incrementUntilNonEmptyRefSCC(); |
931 | return *this; |
932 | } |
933 | }; |
934 | |
935 | /// Construct a graph for the given module. |
936 | /// |
937 | /// This sets up the graph and computes all of the entry points of the graph. |
938 | /// No function definitions are scanned until their nodes in the graph are |
939 | /// requested during traversal. |
940 | LazyCallGraph(Module &M, |
941 | function_ref<TargetLibraryInfo &(Function &)> GetTLI); |
942 | |
943 | LazyCallGraph(LazyCallGraph &&G); |
944 | LazyCallGraph &operator=(LazyCallGraph &&RHS); |
945 | |
946 | bool invalidate(Module &, const PreservedAnalyses &PA, |
947 | ModuleAnalysisManager::Invalidator &); |
948 | |
949 | EdgeSequence::iterator begin() { return EntryEdges.begin(); } |
950 | EdgeSequence::iterator end() { return EntryEdges.end(); } |
951 | |
952 | void buildRefSCCs(); |
953 | |
954 | postorder_ref_scc_iterator postorder_ref_scc_begin() { |
955 | if (!EntryEdges.empty()) |
956 | assert(!PostOrderRefSCCs.empty() && |
957 | "Must form RefSCCs before iterating them!" ); |
958 | return postorder_ref_scc_iterator(*this); |
959 | } |
960 | postorder_ref_scc_iterator postorder_ref_scc_end() { |
961 | if (!EntryEdges.empty()) |
962 | assert(!PostOrderRefSCCs.empty() && |
963 | "Must form RefSCCs before iterating them!" ); |
964 | return postorder_ref_scc_iterator(*this, |
965 | postorder_ref_scc_iterator::IsAtEndT()); |
966 | } |
967 | |
968 | iterator_range<postorder_ref_scc_iterator> postorder_ref_sccs() { |
969 | return make_range(x: postorder_ref_scc_begin(), y: postorder_ref_scc_end()); |
970 | } |
971 | |
972 | /// Lookup a function in the graph which has already been scanned and added. |
973 | Node *lookup(const Function &F) const { return NodeMap.lookup(Val: &F); } |
974 | |
975 | /// Lookup a function's SCC in the graph. |
976 | /// |
977 | /// \returns null if the function hasn't been assigned an SCC via the RefSCC |
978 | /// iterator walk. |
979 | SCC *lookupSCC(Node &N) const { return SCCMap.lookup(Val: &N); } |
980 | |
981 | /// Lookup a function's RefSCC in the graph. |
982 | /// |
983 | /// \returns null if the function hasn't been assigned a RefSCC via the |
984 | /// RefSCC iterator walk. |
985 | RefSCC *lookupRefSCC(Node &N) const { |
986 | if (SCC *C = lookupSCC(N)) |
987 | return &C->getOuterRefSCC(); |
988 | |
989 | return nullptr; |
990 | } |
991 | |
992 | /// Get a graph node for a given function, scanning it to populate the graph |
993 | /// data as necessary. |
994 | Node &get(Function &F) { |
995 | Node *&N = NodeMap[&F]; |
996 | if (N) |
997 | return *N; |
998 | |
999 | return insertInto(F, MappedN&: N); |
1000 | } |
1001 | |
1002 | /// Get the sequence of known and defined library functions. |
1003 | /// |
1004 | /// These functions, because they are known to LLVM, can have calls |
1005 | /// introduced out of thin air from arbitrary IR. |
1006 | ArrayRef<Function *> getLibFunctions() const { |
1007 | return LibFunctions.getArrayRef(); |
1008 | } |
1009 | |
1010 | /// Test whether a function is a known and defined library function tracked by |
1011 | /// the call graph. |
1012 | /// |
1013 | /// Because these functions are known to LLVM they are specially modeled in |
1014 | /// the call graph and even when all IR-level references have been removed |
1015 | /// remain active and reachable. |
1016 | bool isLibFunction(Function &F) const { return LibFunctions.count(key: &F); } |
1017 | |
1018 | ///@{ |
1019 | /// \name Pre-SCC Mutation API |
1020 | /// |
1021 | /// These methods are only valid to call prior to forming any SCCs for this |
1022 | /// call graph. They can be used to update the core node-graph during |
1023 | /// a node-based inorder traversal that precedes any SCC-based traversal. |
1024 | /// |
1025 | /// Once you begin manipulating a call graph's SCCs, most mutation of the |
1026 | /// graph must be performed via a RefSCC method. There are some exceptions |
1027 | /// below. |
1028 | |
1029 | /// Update the call graph after inserting a new edge. |
1030 | void insertEdge(Node &SourceN, Node &TargetN, Edge::Kind EK); |
1031 | |
1032 | /// Update the call graph after inserting a new edge. |
1033 | void insertEdge(Function &Source, Function &Target, Edge::Kind EK) { |
1034 | return insertEdge(SourceN&: get(F&: Source), TargetN&: get(F&: Target), EK); |
1035 | } |
1036 | |
1037 | /// Update the call graph after deleting an edge. |
1038 | void removeEdge(Node &SourceN, Node &TargetN); |
1039 | |
1040 | /// Update the call graph after deleting an edge. |
1041 | void removeEdge(Function &Source, Function &Target) { |
1042 | return removeEdge(SourceN&: get(F&: Source), TargetN&: get(F&: Target)); |
1043 | } |
1044 | |
1045 | ///@} |
1046 | |
1047 | ///@{ |
1048 | /// \name General Mutation API |
1049 | /// |
1050 | /// There are a very limited set of mutations allowed on the graph as a whole |
1051 | /// once SCCs have started to be formed. These routines have strict contracts |
1052 | /// but may be called at any point. |
1053 | |
1054 | /// Remove a dead function from the call graph (typically to delete it). |
1055 | /// |
1056 | /// Note that the function must have an empty use list, and the call graph |
1057 | /// must be up-to-date prior to calling this. That means it is by itself in |
1058 | /// a maximal SCC which is by itself in a maximal RefSCC, etc. No structural |
1059 | /// changes result from calling this routine other than potentially removing |
1060 | /// entry points into the call graph. |
1061 | /// |
1062 | /// If SCC formation has begun, this function must not be part of the current |
1063 | /// DFS in order to call this safely. Typically, the function will have been |
1064 | /// fully visited by the DFS prior to calling this routine. |
1065 | void removeDeadFunction(Function &F); |
1066 | |
1067 | /// Add a new function split/outlined from an existing function. |
1068 | /// |
1069 | /// The new function may only reference other functions that the original |
1070 | /// function did. |
1071 | /// |
1072 | /// The original function must reference (either directly or indirectly) the |
1073 | /// new function. |
1074 | /// |
1075 | /// The new function may also reference the original function. |
1076 | /// It may end up in a parent SCC in the case that the original function's |
1077 | /// edge to the new function is a ref edge, and the edge back is a call edge. |
1078 | void addSplitFunction(Function &OriginalFunction, Function &NewFunction); |
1079 | |
1080 | /// Add new ref-recursive functions split/outlined from an existing function. |
1081 | /// |
1082 | /// The new functions may only reference other functions that the original |
1083 | /// function did. The new functions may reference (not call) the original |
1084 | /// function. |
1085 | /// |
1086 | /// The original function must reference (not call) all new functions. |
1087 | /// All new functions must reference (not call) each other. |
1088 | void addSplitRefRecursiveFunctions(Function &OriginalFunction, |
1089 | ArrayRef<Function *> NewFunctions); |
1090 | |
1091 | ///@} |
1092 | |
1093 | ///@{ |
1094 | /// \name Static helpers for code doing updates to the call graph. |
1095 | /// |
1096 | /// These helpers are used to implement parts of the call graph but are also |
1097 | /// useful to code doing updates or otherwise wanting to walk the IR in the |
1098 | /// same patterns as when we build the call graph. |
1099 | |
1100 | /// Recursively visits the defined functions whose address is reachable from |
1101 | /// every constant in the \p Worklist. |
1102 | /// |
1103 | /// Doesn't recurse through any constants already in the \p Visited set, and |
1104 | /// updates that set with every constant visited. |
1105 | /// |
1106 | /// For each defined function, calls \p Callback with that function. |
1107 | static void visitReferences(SmallVectorImpl<Constant *> &Worklist, |
1108 | SmallPtrSetImpl<Constant *> &Visited, |
1109 | function_ref<void(Function &)> Callback); |
1110 | |
1111 | ///@} |
1112 | |
1113 | private: |
1114 | using node_stack_iterator = SmallVectorImpl<Node *>::reverse_iterator; |
1115 | using node_stack_range = iterator_range<node_stack_iterator>; |
1116 | |
1117 | /// Allocator that holds all the call graph nodes. |
1118 | SpecificBumpPtrAllocator<Node> BPA; |
1119 | |
1120 | /// Maps function->node for fast lookup. |
1121 | DenseMap<const Function *, Node *> NodeMap; |
1122 | |
1123 | /// The entry edges into the graph. |
1124 | /// |
1125 | /// These edges are from "external" sources. Put another way, they |
1126 | /// escape at the module scope. |
1127 | EdgeSequence EntryEdges; |
1128 | |
1129 | /// Allocator that holds all the call graph SCCs. |
1130 | SpecificBumpPtrAllocator<SCC> SCCBPA; |
1131 | |
1132 | /// Maps Function -> SCC for fast lookup. |
1133 | DenseMap<Node *, SCC *> SCCMap; |
1134 | |
1135 | /// Allocator that holds all the call graph RefSCCs. |
1136 | SpecificBumpPtrAllocator<RefSCC> RefSCCBPA; |
1137 | |
1138 | /// The post-order sequence of RefSCCs. |
1139 | /// |
1140 | /// This list is lazily formed the first time we walk the graph. |
1141 | SmallVector<RefSCC *, 16> PostOrderRefSCCs; |
1142 | |
1143 | /// A map from RefSCC to the index for it in the postorder sequence of |
1144 | /// RefSCCs. |
1145 | DenseMap<RefSCC *, int> RefSCCIndices; |
1146 | |
1147 | /// Defined functions that are also known library functions which the |
1148 | /// optimizer can reason about and therefore might introduce calls to out of |
1149 | /// thin air. |
1150 | SmallSetVector<Function *, 4> LibFunctions; |
1151 | |
1152 | /// Helper to insert a new function, with an already looked-up entry in |
1153 | /// the NodeMap. |
1154 | Node &insertInto(Function &F, Node *&MappedN); |
1155 | |
1156 | /// Helper to initialize a new node created outside of creating SCCs and add |
1157 | /// it to the NodeMap if necessary. For example, useful when a function is |
1158 | /// split. |
1159 | Node &initNode(Function &F); |
1160 | |
1161 | /// Helper to update pointers back to the graph object during moves. |
1162 | void updateGraphPtrs(); |
1163 | |
1164 | /// Allocates an SCC and constructs it using the graph allocator. |
1165 | /// |
1166 | /// The arguments are forwarded to the constructor. |
1167 | template <typename... Ts> SCC *createSCC(Ts &&...Args) { |
1168 | return new (SCCBPA.Allocate()) SCC(std::forward<Ts>(Args)...); |
1169 | } |
1170 | |
1171 | /// Allocates a RefSCC and constructs it using the graph allocator. |
1172 | /// |
1173 | /// The arguments are forwarded to the constructor. |
1174 | template <typename... Ts> RefSCC *createRefSCC(Ts &&...Args) { |
1175 | return new (RefSCCBPA.Allocate()) RefSCC(std::forward<Ts>(Args)...); |
1176 | } |
1177 | |
1178 | /// Common logic for building SCCs from a sequence of roots. |
1179 | /// |
1180 | /// This is a very generic implementation of the depth-first walk and SCC |
1181 | /// formation algorithm. It uses a generic sequence of roots and generic |
1182 | /// callbacks for each step. This is designed to be used to implement both |
1183 | /// the RefSCC formation and SCC formation with shared logic. |
1184 | /// |
1185 | /// Currently this is a relatively naive implementation of Tarjan's DFS |
1186 | /// algorithm to form the SCCs. |
1187 | /// |
1188 | /// FIXME: We should consider newer variants such as Nuutila. |
1189 | template <typename RootsT, typename GetBeginT, typename GetEndT, |
1190 | typename GetNodeT, typename FormSCCCallbackT> |
1191 | static void buildGenericSCCs(RootsT &&Roots, GetBeginT &&GetBegin, |
1192 | GetEndT &&GetEnd, GetNodeT &&GetNode, |
1193 | FormSCCCallbackT &&FormSCC); |
1194 | |
1195 | /// Build the SCCs for a RefSCC out of a list of nodes. |
1196 | void buildSCCs(RefSCC &RC, node_stack_range Nodes); |
1197 | |
1198 | /// Get the index of a RefSCC within the postorder traversal. |
1199 | /// |
1200 | /// Requires that this RefSCC is a valid one in the (perhaps partial) |
1201 | /// postorder traversed part of the graph. |
1202 | int getRefSCCIndex(RefSCC &RC) { |
1203 | auto IndexIt = RefSCCIndices.find(Val: &RC); |
1204 | assert(IndexIt != RefSCCIndices.end() && "RefSCC doesn't have an index!" ); |
1205 | assert(PostOrderRefSCCs[IndexIt->second] == &RC && |
1206 | "Index does not point back at RC!" ); |
1207 | return IndexIt->second; |
1208 | } |
1209 | }; |
1210 | |
1211 | inline LazyCallGraph::Edge::Edge() = default; |
1212 | inline LazyCallGraph::Edge::Edge(Node &N, Kind K) : Value(&N, K) {} |
1213 | |
1214 | inline LazyCallGraph::Edge::operator bool() const { |
1215 | return Value.getPointer() && !Value.getPointer()->isDead(); |
1216 | } |
1217 | |
1218 | inline LazyCallGraph::Edge::Kind LazyCallGraph::Edge::getKind() const { |
1219 | assert(*this && "Queried a null edge!" ); |
1220 | return Value.getInt(); |
1221 | } |
1222 | |
1223 | inline bool LazyCallGraph::Edge::isCall() const { |
1224 | assert(*this && "Queried a null edge!" ); |
1225 | return getKind() == Call; |
1226 | } |
1227 | |
1228 | inline LazyCallGraph::Node &LazyCallGraph::Edge::getNode() const { |
1229 | assert(*this && "Queried a null edge!" ); |
1230 | return *Value.getPointer(); |
1231 | } |
1232 | |
1233 | inline Function &LazyCallGraph::Edge::getFunction() const { |
1234 | assert(*this && "Queried a null edge!" ); |
1235 | return getNode().getFunction(); |
1236 | } |
1237 | |
1238 | // Provide GraphTraits specializations for call graphs. |
1239 | template <> struct GraphTraits<LazyCallGraph::Node *> { |
1240 | using NodeRef = LazyCallGraph::Node *; |
1241 | using ChildIteratorType = LazyCallGraph::EdgeSequence::iterator; |
1242 | |
1243 | static NodeRef getEntryNode(NodeRef N) { return N; } |
1244 | static ChildIteratorType child_begin(NodeRef N) { return (*N)->begin(); } |
1245 | static ChildIteratorType child_end(NodeRef N) { return (*N)->end(); } |
1246 | }; |
1247 | template <> struct GraphTraits<LazyCallGraph *> { |
1248 | using NodeRef = LazyCallGraph::Node *; |
1249 | using ChildIteratorType = LazyCallGraph::EdgeSequence::iterator; |
1250 | |
1251 | static NodeRef getEntryNode(NodeRef N) { return N; } |
1252 | static ChildIteratorType child_begin(NodeRef N) { return (*N)->begin(); } |
1253 | static ChildIteratorType child_end(NodeRef N) { return (*N)->end(); } |
1254 | }; |
1255 | |
1256 | /// An analysis pass which computes the call graph for a module. |
1257 | class LazyCallGraphAnalysis : public AnalysisInfoMixin<LazyCallGraphAnalysis> { |
1258 | friend AnalysisInfoMixin<LazyCallGraphAnalysis>; |
1259 | |
1260 | static AnalysisKey Key; |
1261 | |
1262 | public: |
1263 | /// Inform generic clients of the result type. |
1264 | using Result = LazyCallGraph; |
1265 | |
1266 | /// Compute the \c LazyCallGraph for the module \c M. |
1267 | /// |
1268 | /// This just builds the set of entry points to the call graph. The rest is |
1269 | /// built lazily as it is walked. |
1270 | LazyCallGraph run(Module &M, ModuleAnalysisManager &AM) { |
1271 | FunctionAnalysisManager &FAM = |
1272 | AM.getResult<FunctionAnalysisManagerModuleProxy>(IR&: M).getManager(); |
1273 | auto GetTLI = [&FAM](Function &F) -> TargetLibraryInfo & { |
1274 | return FAM.getResult<TargetLibraryAnalysis>(IR&: F); |
1275 | }; |
1276 | return LazyCallGraph(M, GetTLI); |
1277 | } |
1278 | }; |
1279 | |
1280 | /// A pass which prints the call graph to a \c raw_ostream. |
1281 | /// |
1282 | /// This is primarily useful for testing the analysis. |
1283 | class LazyCallGraphPrinterPass |
1284 | : public PassInfoMixin<LazyCallGraphPrinterPass> { |
1285 | raw_ostream &OS; |
1286 | |
1287 | public: |
1288 | explicit LazyCallGraphPrinterPass(raw_ostream &OS); |
1289 | |
1290 | PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); |
1291 | |
1292 | static bool isRequired() { return true; } |
1293 | }; |
1294 | |
1295 | /// A pass which prints the call graph as a DOT file to a \c raw_ostream. |
1296 | /// |
1297 | /// This is primarily useful for visualization purposes. |
1298 | class LazyCallGraphDOTPrinterPass |
1299 | : public PassInfoMixin<LazyCallGraphDOTPrinterPass> { |
1300 | raw_ostream &OS; |
1301 | |
1302 | public: |
1303 | explicit LazyCallGraphDOTPrinterPass(raw_ostream &OS); |
1304 | |
1305 | PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); |
1306 | |
1307 | static bool isRequired() { return true; } |
1308 | }; |
1309 | |
1310 | } // end namespace llvm |
1311 | |
1312 | #endif // LLVM_ANALYSIS_LAZYCALLGRAPH_H |
1313 | |