llvm-project

1
//===- CallGraphSCCPass.cpp - Pass that operates BU on 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
// This file implements the CallGraphSCCPass class, which is used for passes
10
// which are implemented as bottom-up traversals on the call graph.  Because
11
// there may be cycles in the call graph, passes of this type operate on the
12
// call-graph in SCC order: that is, they process function bottom-up, except for
13
// recursive functions, which they process all at once.
14
//
15
//===----------------------------------------------------------------------===//
16

17
#include "llvm/Analysis/CallGraphSCCPass.h"
18
#include "llvm/ADT/DenseMap.h"
19
#include "llvm/ADT/SCCIterator.h"
20
#include "llvm/ADT/Statistic.h"
21
#include "llvm/ADT/StringExtras.h"
22
#include "llvm/Analysis/CallGraph.h"
23
#include "llvm/IR/AbstractCallSite.h"
24
#include "llvm/IR/Function.h"
25
#include "llvm/IR/Intrinsics.h"
26
#include "llvm/IR/LLVMContext.h"
27
#include "llvm/IR/LegacyPassManagers.h"
28
#include "llvm/IR/Module.h"
29
#include "llvm/IR/OptBisect.h"
30
#include "llvm/IR/PassTimingInfo.h"
31
#include "llvm/IR/PrintPasses.h"
32
#include "llvm/Pass.h"
33
#include "llvm/Support/CommandLine.h"
34
#include "llvm/Support/Debug.h"
35
#include "llvm/Support/Timer.h"
36
#include "llvm/Support/raw_ostream.h"
37
#include <cassert>
38
#include <string>
39
#include <utility>
40
#include <vector>
41

42
using namespace llvm;
43

44
#define DEBUG_TYPE "cgscc-passmgr"
45

46
namespace llvm {
47
cl::opt<unsigned> MaxDevirtIterations("max-devirt-iterations", cl::ReallyHidden,
48
                                      cl::init(4));
49
} // namespace llvm
50

51
STATISTIC(MaxSCCIterations, "Maximum CGSCCPassMgr iterations on one SCC");
52

53
//===----------------------------------------------------------------------===//
54
// CGPassManager
55
//
56
/// CGPassManager manages FPPassManagers and CallGraphSCCPasses.
57

58
namespace {
59

60
class CGPassManager : public ModulePass, public PMDataManager {
61
public:
62
  static char ID;
63

64
  explicit CGPassManager() : ModulePass(ID) {}
65

66
  /// Execute all of the passes scheduled for execution.  Keep track of
67
  /// whether any of the passes modifies the module, and if so, return true.
68
  bool runOnModule(Module &M) override;
69

70
  using ModulePass::doInitialization;
71
  using ModulePass::doFinalization;
72

73
  bool doInitialization(CallGraph &CG);
74
  bool doFinalization(CallGraph &CG);
75

76
  /// Pass Manager itself does not invalidate any analysis info.
77
  void getAnalysisUsage(AnalysisUsage &Info) const override {
78
    // CGPassManager walks SCC and it needs CallGraph.
79
    Info.addRequired<CallGraphWrapperPass>();
80
    Info.setPreservesAll();
81
  }
82

83
  StringRef getPassName() const override { return "CallGraph Pass Manager"; }
84

85
  PMDataManager *getAsPMDataManager() override { return this; }
86
  Pass *getAsPass() override { return this; }
87

88
  // Print passes managed by this manager
89
  void dumpPassStructure(unsigned Offset) override {
90
    errs().indent(Offset*2) << "Call Graph SCC Pass Manager\n";
91
    for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
92
      Pass *P = getContainedPass(Index);
93
      P->dumpPassStructure(Offset + 1);
94
      dumpLastUses(P, Offset+1);
95
    }
96
  }
97

98
  Pass *getContainedPass(unsigned N) {
99
    assert(N < PassVector.size() && "Pass number out of range!");
100
    return static_cast<Pass *>(PassVector[N]);
101
  }
102

103
  PassManagerType getPassManagerType() const override {
104
    return PMT_CallGraphPassManager;
105
  }
106

107
private:
108
  bool RunAllPassesOnSCC(CallGraphSCC &CurSCC, CallGraph &CG,
109
                         bool &DevirtualizedCall);
110

111
  bool RunPassOnSCC(Pass *P, CallGraphSCC &CurSCC,
112
                    CallGraph &CG, bool &CallGraphUpToDate,
113
                    bool &DevirtualizedCall);
114
  bool RefreshCallGraph(const CallGraphSCC &CurSCC, CallGraph &CG,
115
                        bool IsCheckingMode);
116
};
117

118
} // end anonymous namespace.
119

120
char CGPassManager::ID = 0;
121

122
bool CGPassManager::RunPassOnSCC(Pass *P, CallGraphSCC &CurSCC,
123
                                 CallGraph &CG, bool &CallGraphUpToDate,
124
                                 bool &DevirtualizedCall) {
125
  bool Changed = false;
126
  PMDataManager *PM = P->getAsPMDataManager();
127
  Module &M = CG.getModule();
128

129
  if (!PM) {
130
    CallGraphSCCPass *CGSP = (CallGraphSCCPass *)P;
131
    if (!CallGraphUpToDate) {
132
      DevirtualizedCall |= RefreshCallGraph(CurSCC, CG, false);
133
      CallGraphUpToDate = true;
134
    }
135

136
    {
137
      unsigned InstrCount, SCCCount = 0;
138
      StringMap<std::pair<unsigned, unsigned>> FunctionToInstrCount;
139
      bool EmitICRemark = M.shouldEmitInstrCountChangedRemark();
140
      TimeRegion PassTimer(getPassTimer(CGSP));
141
      if (EmitICRemark)
142
        InstrCount = initSizeRemarkInfo(M, FunctionToInstrCount);
143
      Changed = CGSP->runOnSCC(CurSCC);
144

145
      if (EmitICRemark) {
146
        // FIXME: Add getInstructionCount to CallGraphSCC.
147
        SCCCount = M.getInstructionCount();
148
        // Is there a difference in the number of instructions in the module?
149
        if (SCCCount != InstrCount) {
150
          // Yep. Emit a remark and update InstrCount.
151
          int64_t Delta =
152
              static_cast<int64_t>(SCCCount) - static_cast<int64_t>(InstrCount);
153
          emitInstrCountChangedRemark(P, M, Delta, InstrCount,
154
                                      FunctionToInstrCount);
155
          InstrCount = SCCCount;
156
        }
157
      }
158
    }
159

160
    // After the CGSCCPass is done, when assertions are enabled, use
161
    // RefreshCallGraph to verify that the callgraph was correctly updated.
162
#ifndef NDEBUG
163
    if (Changed)
164
      RefreshCallGraph(CurSCC, CG, true);
165
#endif
166

167
    return Changed;
168
  }
169

170
  assert(PM->getPassManagerType() == PMT_FunctionPassManager &&
171
         "Invalid CGPassManager member");
172
  FPPassManager *FPP = (FPPassManager*)P;
173

174
  // Run pass P on all functions in the current SCC.
175
  for (CallGraphNode *CGN : CurSCC) {
176
    if (Function *F = CGN->getFunction()) {
177
      dumpPassInfo(P, EXECUTION_MSG, ON_FUNCTION_MSG, F->getName());
178
      {
179
        TimeRegion PassTimer(getPassTimer(FPP));
180
        Changed |= FPP->runOnFunction(*F);
181
      }
182
      F->getContext().yield();
183
    }
184
  }
185

186
  // The function pass(es) modified the IR, they may have clobbered the
187
  // callgraph.
188
  if (Changed && CallGraphUpToDate) {
189
    LLVM_DEBUG(dbgs() << "CGSCCPASSMGR: Pass Dirtied SCC: " << P->getPassName()
190
                      << '\n');
191
    CallGraphUpToDate = false;
192
  }
193
  return Changed;
194
}
195

196
/// Scan the functions in the specified CFG and resync the
197
/// callgraph with the call sites found in it.  This is used after
198
/// FunctionPasses have potentially munged the callgraph, and can be used after
199
/// CallGraphSCC passes to verify that they correctly updated the callgraph.
200
///
201
/// This function returns true if it devirtualized an existing function call,
202
/// meaning it turned an indirect call into a direct call.  This happens when
203
/// a function pass like GVN optimizes away stuff feeding the indirect call.
204
/// This never happens in checking mode.
205
bool CGPassManager::RefreshCallGraph(const CallGraphSCC &CurSCC, CallGraph &CG,
206
                                     bool CheckingMode) {
207
  DenseMap<Value *, CallGraphNode *> Calls;
208

209
  LLVM_DEBUG(dbgs() << "CGSCCPASSMGR: Refreshing SCC with " << CurSCC.size()
210
                    << " nodes:\n";
211
             for (CallGraphNode *CGN
212
                  : CurSCC) CGN->dump(););
213

214
  bool MadeChange = false;
215
  bool DevirtualizedCall = false;
216

217
  // Scan all functions in the SCC.
218
  unsigned FunctionNo = 0;
219
  for (CallGraphSCC::iterator SCCIdx = CurSCC.begin(), E = CurSCC.end();
220
       SCCIdx != E; ++SCCIdx, ++FunctionNo) {
221
    CallGraphNode *CGN = *SCCIdx;
222
    Function *F = CGN->getFunction();
223
    if (!F || F->isDeclaration()) continue;
224

225
    // Walk the function body looking for call sites.  Sync up the call sites in
226
    // CGN with those actually in the function.
227

228
    // Keep track of the number of direct and indirect calls that were
229
    // invalidated and removed.
230
    unsigned NumDirectRemoved = 0, NumIndirectRemoved = 0;
231

232
    CallGraphNode::iterator CGNEnd = CGN->end();
233

234
    auto RemoveAndCheckForDone = [&](CallGraphNode::iterator I) {
235
      // Just remove the edge from the set of callees, keep track of whether
236
      // I points to the last element of the vector.
237
      bool WasLast = I + 1 == CGNEnd;
238
      CGN->removeCallEdge(I);
239

240
      // If I pointed to the last element of the vector, we have to bail out:
241
      // iterator checking rejects comparisons of the resultant pointer with
242
      // end.
243
      if (WasLast)
244
        return true;
245

246
      CGNEnd = CGN->end();
247
      return false;
248
    };
249

250
    // Get the set of call sites currently in the function.
251
    for (CallGraphNode::iterator I = CGN->begin(); I != CGNEnd;) {
252
      // Delete "reference" call records that do not have call instruction. We
253
      // reinsert them as needed later. However, keep them in checking mode.
254
      if (!I->first) {
255
        if (CheckingMode) {
256
          ++I;
257
          continue;
258
        }
259
        if (RemoveAndCheckForDone(I))
260
          break;
261
        continue;
262
      }
263

264
      // If this call site is null, then the function pass deleted the call
265
      // entirely and the WeakTrackingVH nulled it out.
266
      auto *Call = dyn_cast_or_null<CallBase>(*I->first);
267
      if (!Call ||
268
          // If we've already seen this call site, then the FunctionPass RAUW'd
269
          // one call with another, which resulted in two "uses" in the edge
270
          // list of the same call.
271
          Calls.count(Call)) {
272
        assert(!CheckingMode &&
273
               "CallGraphSCCPass did not update the CallGraph correctly!");
274

275
        // If this was an indirect call site, count it.
276
        if (!I->second->getFunction())
277
          ++NumIndirectRemoved;
278
        else
279
          ++NumDirectRemoved;
280

281
        if (RemoveAndCheckForDone(I))
282
          break;
283
        continue;
284
      }
285

286
      assert(!Calls.count(Call) && "Call site occurs in node multiple times");
287

288
      if (Call) {
289
        Function *Callee = Call->getCalledFunction();
290
        // Ignore intrinsics because they're not really function calls.
291
        if (!Callee || !(Callee->isIntrinsic()))
292
          Calls.insert(std::make_pair(Call, I->second));
293
      }
294
      ++I;
295
    }
296

297
    // Loop over all of the instructions in the function, getting the callsites.
298
    // Keep track of the number of direct/indirect calls added.
299
    unsigned NumDirectAdded = 0, NumIndirectAdded = 0;
300

301
    for (BasicBlock &BB : *F)
302
      for (Instruction &I : BB) {
303
        auto *Call = dyn_cast<CallBase>(&I);
304
        if (!Call)
305
          continue;
306
        Function *Callee = Call->getCalledFunction();
307
        if (Callee && Callee->isIntrinsic())
308
          continue;
309

310
        // If we are not in checking mode, insert potential callback calls as
311
        // references. This is not a requirement but helps to iterate over the
312
        // functions in the right order.
313
        if (!CheckingMode) {
314
          forEachCallbackFunction(*Call, [&](Function *CB) {
315
            CGN->addCalledFunction(nullptr, CG.getOrInsertFunction(CB));
316
          });
317
        }
318

319
        // If this call site already existed in the callgraph, just verify it
320
        // matches up to expectations and remove it from Calls.
321
        DenseMap<Value *, CallGraphNode *>::iterator ExistingIt =
322
            Calls.find(Call);
323
        if (ExistingIt != Calls.end()) {
324
          CallGraphNode *ExistingNode = ExistingIt->second;
325

326
          // Remove from Calls since we have now seen it.
327
          Calls.erase(ExistingIt);
328

329
          // Verify that the callee is right.
330
          if (ExistingNode->getFunction() == Call->getCalledFunction())
331
            continue;
332

333
          // If we are in checking mode, we are not allowed to actually mutate
334
          // the callgraph.  If this is a case where we can infer that the
335
          // callgraph is less precise than it could be (e.g. an indirect call
336
          // site could be turned direct), don't reject it in checking mode, and
337
          // don't tweak it to be more precise.
338
          if (CheckingMode && Call->getCalledFunction() &&
339
              ExistingNode->getFunction() == nullptr)
340
            continue;
341

342
          assert(!CheckingMode &&
343
                 "CallGraphSCCPass did not update the CallGraph correctly!");
344

345
          // If not, we either went from a direct call to indirect, indirect to
346
          // direct, or direct to different direct.
347
          CallGraphNode *CalleeNode;
348
          if (Function *Callee = Call->getCalledFunction()) {
349
            CalleeNode = CG.getOrInsertFunction(Callee);
350
            // Keep track of whether we turned an indirect call into a direct
351
            // one.
352
            if (!ExistingNode->getFunction()) {
353
              DevirtualizedCall = true;
354
              LLVM_DEBUG(dbgs() << "  CGSCCPASSMGR: Devirtualized call to '"
355
                                << Callee->getName() << "'\n");
356
            }
357
          } else {
358
            CalleeNode = CG.getCallsExternalNode();
359
          }
360

361
          // Update the edge target in CGN.
362
          CGN->replaceCallEdge(*Call, *Call, CalleeNode);
363
          MadeChange = true;
364
          continue;
365
        }
366

367
        assert(!CheckingMode &&
368
               "CallGraphSCCPass did not update the CallGraph correctly!");
369

370
        // If the call site didn't exist in the CGN yet, add it.
371
        CallGraphNode *CalleeNode;
372
        if (Function *Callee = Call->getCalledFunction()) {
373
          CalleeNode = CG.getOrInsertFunction(Callee);
374
          ++NumDirectAdded;
375
        } else {
376
          CalleeNode = CG.getCallsExternalNode();
377
          ++NumIndirectAdded;
378
        }
379

380
        CGN->addCalledFunction(Call, CalleeNode);
381
        MadeChange = true;
382
      }
383

384
    // We scanned the old callgraph node, removing invalidated call sites and
385
    // then added back newly found call sites.  One thing that can happen is
386
    // that an old indirect call site was deleted and replaced with a new direct
387
    // call.  In this case, we have devirtualized a call, and CGSCCPM would like
388
    // to iteratively optimize the new code.  Unfortunately, we don't really
389
    // have a great way to detect when this happens.  As an approximation, we
390
    // just look at whether the number of indirect calls is reduced and the
391
    // number of direct calls is increased.  There are tons of ways to fool this
392
    // (e.g. DCE'ing an indirect call and duplicating an unrelated block with a
393
    // direct call) but this is close enough.
394
    if (NumIndirectRemoved > NumIndirectAdded &&
395
        NumDirectRemoved < NumDirectAdded)
396
      DevirtualizedCall = true;
397

398
    // After scanning this function, if we still have entries in callsites, then
399
    // they are dangling pointers.  WeakTrackingVH should save us for this, so
400
    // abort if
401
    // this happens.
402
    assert(Calls.empty() && "Dangling pointers found in call sites map");
403

404
    // Periodically do an explicit clear to remove tombstones when processing
405
    // large scc's.
406
    if ((FunctionNo & 15) == 15)
407
      Calls.clear();
408
  }
409

410
  LLVM_DEBUG(if (MadeChange) {
411
    dbgs() << "CGSCCPASSMGR: Refreshed SCC is now:\n";
412
    for (CallGraphNode *CGN : CurSCC)
413
      CGN->dump();
414
    if (DevirtualizedCall)
415
      dbgs() << "CGSCCPASSMGR: Refresh devirtualized a call!\n";
416
  } else {
417
    dbgs() << "CGSCCPASSMGR: SCC Refresh didn't change call graph.\n";
418
  });
419
  (void)MadeChange;
420

421
  return DevirtualizedCall;
422
}
423

424
/// Execute the body of the entire pass manager on the specified SCC.
425
/// This keeps track of whether a function pass devirtualizes
426
/// any calls and returns it in DevirtualizedCall.
427
bool CGPassManager::RunAllPassesOnSCC(CallGraphSCC &CurSCC, CallGraph &CG,
428
                                      bool &DevirtualizedCall) {
429
  bool Changed = false;
430

431
  // Keep track of whether the callgraph is known to be up-to-date or not.
432
  // The CGSSC pass manager runs two types of passes:
433
  // CallGraphSCC Passes and other random function passes.  Because other
434
  // random function passes are not CallGraph aware, they may clobber the
435
  // call graph by introducing new calls or deleting other ones.  This flag
436
  // is set to false when we run a function pass so that we know to clean up
437
  // the callgraph when we need to run a CGSCCPass again.
438
  bool CallGraphUpToDate = true;
439

440
  // Run all passes on current SCC.
441
  for (unsigned PassNo = 0, e = getNumContainedPasses();
442
       PassNo != e; ++PassNo) {
443
    Pass *P = getContainedPass(PassNo);
444

445
    // If we're in -debug-pass=Executions mode, construct the SCC node list,
446
    // otherwise avoid constructing this string as it is expensive.
447
    if (isPassDebuggingExecutionsOrMore()) {
448
      std::string Functions;
449
  #ifndef NDEBUG
450
      raw_string_ostream OS(Functions);
451
      ListSeparator LS;
452
      for (const CallGraphNode *CGN : CurSCC) {
453
        OS << LS;
454
        CGN->print(OS);
455
      }
456
      OS.flush();
457
  #endif
458
      dumpPassInfo(P, EXECUTION_MSG, ON_CG_MSG, Functions);
459
    }
460
    dumpRequiredSet(P);
461

462
    initializeAnalysisImpl(P);
463

464
#ifdef EXPENSIVE_CHECKS
465
    uint64_t RefHash = P->structuralHash(CG.getModule());
466
#endif
467

468
    // Actually run this pass on the current SCC.
469
    bool LocalChanged =
470
        RunPassOnSCC(P, CurSCC, CG, CallGraphUpToDate, DevirtualizedCall);
471

472
    Changed |= LocalChanged;
473

474
#ifdef EXPENSIVE_CHECKS
475
    if (!LocalChanged && (RefHash != P->structuralHash(CG.getModule()))) {
476
      llvm::errs() << "Pass modifies its input and doesn't report it: "
477
                   << P->getPassName() << "\n";
478
      llvm_unreachable("Pass modifies its input and doesn't report it");
479
    }
480
#endif
481
    if (LocalChanged)
482
      dumpPassInfo(P, MODIFICATION_MSG, ON_CG_MSG, "");
483
    dumpPreservedSet(P);
484

485
    verifyPreservedAnalysis(P);
486
    if (LocalChanged)
487
      removeNotPreservedAnalysis(P);
488
    recordAvailableAnalysis(P);
489
    removeDeadPasses(P, "", ON_CG_MSG);
490
  }
491

492
  // If the callgraph was left out of date (because the last pass run was a
493
  // functionpass), refresh it before we move on to the next SCC.
494
  if (!CallGraphUpToDate)
495
    DevirtualizedCall |= RefreshCallGraph(CurSCC, CG, false);
496
  return Changed;
497
}
498

499
/// Execute all of the passes scheduled for execution.  Keep track of
500
/// whether any of the passes modifies the module, and if so, return true.
501
bool CGPassManager::runOnModule(Module &M) {
502
  CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
503
  bool Changed = doInitialization(CG);
504

505
  // Walk the callgraph in bottom-up SCC order.
506
  scc_iterator<CallGraph*> CGI = scc_begin(&CG);
507

508
  CallGraphSCC CurSCC(CG, &CGI);
509
  while (!CGI.isAtEnd()) {
510
    // Copy the current SCC and increment past it so that the pass can hack
511
    // on the SCC if it wants to without invalidating our iterator.
512
    const std::vector<CallGraphNode *> &NodeVec = *CGI;
513
    CurSCC.initialize(NodeVec);
514
    ++CGI;
515

516
    // At the top level, we run all the passes in this pass manager on the
517
    // functions in this SCC.  However, we support iterative compilation in the
518
    // case where a function pass devirtualizes a call to a function.  For
519
    // example, it is very common for a function pass (often GVN or instcombine)
520
    // to eliminate the addressing that feeds into a call.  With that improved
521
    // information, we would like the call to be an inline candidate, infer
522
    // mod-ref information etc.
523
    //
524
    // Because of this, we allow iteration up to a specified iteration count.
525
    // This only happens in the case of a devirtualized call, so we only burn
526
    // compile time in the case that we're making progress.  We also have a hard
527
    // iteration count limit in case there is crazy code.
528
    unsigned Iteration = 0;
529
    bool DevirtualizedCall = false;
530
    do {
531
      LLVM_DEBUG(if (Iteration) dbgs()
532
                 << "  SCCPASSMGR: Re-visiting SCC, iteration #" << Iteration
533
                 << '\n');
534
      DevirtualizedCall = false;
535
      Changed |= RunAllPassesOnSCC(CurSCC, CG, DevirtualizedCall);
536
    } while (Iteration++ < MaxDevirtIterations && DevirtualizedCall);
537

538
    if (DevirtualizedCall)
539
      LLVM_DEBUG(dbgs() << "  CGSCCPASSMGR: Stopped iteration after "
540
                        << Iteration
541
                        << " times, due to -max-devirt-iterations\n");
542

543
    MaxSCCIterations.updateMax(Iteration);
544
  }
545
  Changed |= doFinalization(CG);
546
  return Changed;
547
}
548

549
/// Initialize CG
550
bool CGPassManager::doInitialization(CallGraph &CG) {
551
  bool Changed = false;
552
  for (unsigned i = 0, e = getNumContainedPasses(); i != e; ++i) {
553
    if (PMDataManager *PM = getContainedPass(i)->getAsPMDataManager()) {
554
      assert(PM->getPassManagerType() == PMT_FunctionPassManager &&
555
             "Invalid CGPassManager member");
556
      Changed |= ((FPPassManager*)PM)->doInitialization(CG.getModule());
557
    } else {
558
      Changed |= ((CallGraphSCCPass*)getContainedPass(i))->doInitialization(CG);
559
    }
560
  }
561
  return Changed;
562
}
563

564
/// Finalize CG
565
bool CGPassManager::doFinalization(CallGraph &CG) {
566
  bool Changed = false;
567
  for (unsigned i = 0, e = getNumContainedPasses(); i != e; ++i) {
568
    if (PMDataManager *PM = getContainedPass(i)->getAsPMDataManager()) {
569
      assert(PM->getPassManagerType() == PMT_FunctionPassManager &&
570
             "Invalid CGPassManager member");
571
      Changed |= ((FPPassManager*)PM)->doFinalization(CG.getModule());
572
    } else {
573
      Changed |= ((CallGraphSCCPass*)getContainedPass(i))->doFinalization(CG);
574
    }
575
  }
576
  return Changed;
577
}
578

579
//===----------------------------------------------------------------------===//
580
// CallGraphSCC Implementation
581
//===----------------------------------------------------------------------===//
582

583
/// This informs the SCC and the pass manager that the specified
584
/// Old node has been deleted, and New is to be used in its place.
585
void CallGraphSCC::ReplaceNode(CallGraphNode *Old, CallGraphNode *New) {
586
  assert(Old != New && "Should not replace node with self");
587
  for (unsigned i = 0; ; ++i) {
588
    assert(i != Nodes.size() && "Node not in SCC");
589
    if (Nodes[i] != Old) continue;
590
    if (New)
591
      Nodes[i] = New;
592
    else
593
      Nodes.erase(Nodes.begin() + i);
594
    break;
595
  }
596

597
  // Update the active scc_iterator so that it doesn't contain dangling
598
  // pointers to the old CallGraphNode.
599
  scc_iterator<CallGraph*> *CGI = (scc_iterator<CallGraph*>*)Context;
600
  CGI->ReplaceNode(Old, New);
601
}
602

603
void CallGraphSCC::DeleteNode(CallGraphNode *Old) {
604
  ReplaceNode(Old, /*New=*/nullptr);
605
}
606

607
//===----------------------------------------------------------------------===//
608
// CallGraphSCCPass Implementation
609
//===----------------------------------------------------------------------===//
610

611
/// Assign pass manager to manage this pass.
612
void CallGraphSCCPass::assignPassManager(PMStack &PMS,
613
                                         PassManagerType PreferredType) {
614
  // Find CGPassManager
615
  while (!PMS.empty() &&
616
         PMS.top()->getPassManagerType() > PMT_CallGraphPassManager)
617
    PMS.pop();
618

619
  assert(!PMS.empty() && "Unable to handle Call Graph Pass");
620
  CGPassManager *CGP;
621

622
  if (PMS.top()->getPassManagerType() == PMT_CallGraphPassManager)
623
    CGP = (CGPassManager*)PMS.top();
624
  else {
625
    // Create new Call Graph SCC Pass Manager if it does not exist.
626
    assert(!PMS.empty() && "Unable to create Call Graph Pass Manager");
627
    PMDataManager *PMD = PMS.top();
628

629
    // [1] Create new Call Graph Pass Manager
630
    CGP = new CGPassManager();
631

632
    // [2] Set up new manager's top level manager
633
    PMTopLevelManager *TPM = PMD->getTopLevelManager();
634
    TPM->addIndirectPassManager(CGP);
635

636
    // [3] Assign manager to manage this new manager. This may create
637
    // and push new managers into PMS
638
    Pass *P = CGP;
639
    TPM->schedulePass(P);
640

641
    // [4] Push new manager into PMS
642
    PMS.push(CGP);
643
  }
644

645
  CGP->add(this);
646
}
647

648
/// For this class, we declare that we require and preserve the call graph.
649
/// If the derived class implements this method, it should
650
/// always explicitly call the implementation here.
651
void CallGraphSCCPass::getAnalysisUsage(AnalysisUsage &AU) const {
652
  AU.addRequired<CallGraphWrapperPass>();
653
  AU.addPreserved<CallGraphWrapperPass>();
654
}
655

656
//===----------------------------------------------------------------------===//
657
// PrintCallGraphPass Implementation
658
//===----------------------------------------------------------------------===//
659

660
namespace {
661

662
  /// PrintCallGraphPass - Print a Module corresponding to a call graph.
663
  ///
664
  class PrintCallGraphPass : public CallGraphSCCPass {
665
    std::string Banner;
666
    raw_ostream &OS;       // raw_ostream to print on.
667

668
  public:
669
    static char ID;
670

671
    PrintCallGraphPass(const std::string &B, raw_ostream &OS)
672
      : CallGraphSCCPass(ID), Banner(B), OS(OS) {}
673

674
    void getAnalysisUsage(AnalysisUsage &AU) const override {
675
      AU.setPreservesAll();
676
    }
677

678
    bool runOnSCC(CallGraphSCC &SCC) override {
679
      bool BannerPrinted = false;
680
      auto PrintBannerOnce = [&]() {
681
        if (BannerPrinted)
682
          return;
683
        OS << Banner;
684
        BannerPrinted = true;
685
      };
686

687
      bool NeedModule = llvm::forcePrintModuleIR();
688
      if (isFunctionInPrintList("*") && NeedModule) {
689
        PrintBannerOnce();
690
        OS << "\n";
691
        SCC.getCallGraph().getModule().print(OS, nullptr);
692
        return false;
693
      }
694
      bool FoundFunction = false;
695
      for (CallGraphNode *CGN : SCC) {
696
        if (Function *F = CGN->getFunction()) {
697
          if (!F->isDeclaration() && isFunctionInPrintList(F->getName())) {
698
            FoundFunction = true;
699
            if (!NeedModule) {
700
              PrintBannerOnce();
701
              F->print(OS);
702
            }
703
          }
704
        } else if (isFunctionInPrintList("*")) {
705
          PrintBannerOnce();
706
          OS << "\nPrinting <null> Function\n";
707
        }
708
      }
709
      if (NeedModule && FoundFunction) {
710
        PrintBannerOnce();
711
        OS << "\n";
712
        SCC.getCallGraph().getModule().print(OS, nullptr);
713
      }
714
      return false;
715
    }
716

717
    StringRef getPassName() const override { return "Print CallGraph IR"; }
718
  };
719

720
} // end anonymous namespace.
721

722
char PrintCallGraphPass::ID = 0;
723

724
Pass *CallGraphSCCPass::createPrinterPass(raw_ostream &OS,
725
                                          const std::string &Banner) const {
726
  return new PrintCallGraphPass(Banner, OS);
727
}
728

729
static std::string getDescription(const CallGraphSCC &SCC) {
730
  std::string Desc = "SCC (";
731
  ListSeparator LS;
732
  for (CallGraphNode *CGN : SCC) {
733
    Desc += LS;
734
    Function *F = CGN->getFunction();
735
    if (F)
736
      Desc += F->getName();
737
    else
738
      Desc += "<<null function>>";
739
  }
740
  Desc += ")";
741
  return Desc;
742
}
743

744
bool CallGraphSCCPass::skipSCC(CallGraphSCC &SCC) const {
745
  OptPassGate &Gate =
746
      SCC.getCallGraph().getModule().getContext().getOptPassGate();
747
  return Gate.isEnabled() &&
748
         !Gate.shouldRunPass(this->getPassName(), getDescription(SCC));
749
}
750

751
char DummyCGSCCPass::ID = 0;
752

753
INITIALIZE_PASS(DummyCGSCCPass, "DummyCGSCCPass", "DummyCGSCCPass", false,
754
                false)
755