Coverage Report

Created: 2019-07-24 05:18

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