Coverage Report

Created: 2019-02-15 18:59

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