Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Analysis/CallGraphSCCPass.cpp
Line
Count
Source (jump to first uncovered line)
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/Analysis/CallGraph.h"
22
#include "llvm/IR/Function.h"
23
#include "llvm/IR/IRPrintingPasses.h"
24
#include "llvm/IR/Intrinsics.h"
25
#include "llvm/IR/LLVMContext.h"
26
#include "llvm/IR/LegacyPassManagers.h"
27
#include "llvm/IR/Module.h"
28
#include "llvm/IR/OptBisect.h"
29
#include "llvm/IR/PassTimingInfo.h"
30
#include "llvm/Pass.h"
31
#include "llvm/Support/CommandLine.h"
32
#include "llvm/Support/Debug.h"
33
#include "llvm/Support/Timer.h"
34
#include "llvm/Support/raw_ostream.h"
35
#include <cassert>
36
#include <string>
37
#include <utility>
38
#include <vector>
39
40
using namespace llvm;
41
42
#define DEBUG_TYPE "cgscc-passmgr"
43
44
static cl::opt<unsigned>
45
MaxIterations("max-cg-scc-iterations", cl::ReallyHidden, cl::init(4));
46
47
STATISTIC(MaxSCCIterations, "Maximum CGSCCPassMgr iterations on one SCC");
48
49
//===----------------------------------------------------------------------===//
50
// CGPassManager
51
//
52
/// CGPassManager manages FPPassManagers and CallGraphSCCPasses.
53
54
namespace {
55
56
class CGPassManager : public ModulePass, public PMDataManager {
57
public:
58
  static char ID;
59
60
31.8k
  explicit CGPassManager() : ModulePass(ID), PMDataManager() {}
61
62
  /// Execute all of the passes scheduled for execution.  Keep track of
63
  /// whether any of the passes modifies the module, and if so, return true.
64
  bool runOnModule(Module &M) override;
65
66
  using ModulePass::doInitialization;
67
  using ModulePass::doFinalization;
68
69
  bool doInitialization(CallGraph &CG);
70
  bool doFinalization(CallGraph &CG);
71
72
  /// Pass Manager itself does not invalidate any analysis info.
73
31.8k
  void getAnalysisUsage(AnalysisUsage &Info) const override {
74
31.8k
    // CGPassManager walks SCC and it needs CallGraph.
75
31.8k
    Info.addRequired<CallGraphWrapperPass>();
76
31.8k
    Info.setPreservesAll();
77
31.8k
  }
78
79
2
  StringRef getPassName() const override { return "CallGraph Pass Manager"; }
80
81
31.9k
  PMDataManager *getAsPMDataManager() override { return this; }
82
2.85M
  Pass *getAsPass() override { return this; }
83
84
  // Print passes managed by this manager
85
45
  void dumpPassStructure(unsigned Offset) override {
86
45
    errs().indent(Offset*2) << "Call Graph SCC Pass Manager\n";
87
183
    for (unsigned Index = 0; Index < getNumContainedPasses(); 
++Index138
) {
88
138
      Pass *P = getContainedPass(Index);
89
138
      P->dumpPassStructure(Offset + 1);
90
138
      dumpLastUses(P, Offset+1);
91
138
    }
92
45
  }
93
94
3.97M
  Pass *getContainedPass(unsigned N) {
95
3.97M
    assert(N < PassVector.size() && "Pass number out of range!");
96
3.97M
    return static_cast<Pass *>(PassVector[N]);
97
3.97M
  }
98
99
193k
  PassManagerType getPassManagerType() const override {
100
193k
    return PMT_CallGraphPassManager;
101
193k
  }
102
103
private:
104
  bool RunAllPassesOnSCC(CallGraphSCC &CurSCC, CallGraph &CG,
105
                         bool &DevirtualizedCall);
106
107
  bool RunPassOnSCC(Pass *P, CallGraphSCC &CurSCC,
108
                    CallGraph &CG, bool &CallGraphUpToDate,
109
                    bool &DevirtualizedCall);
110
  bool RefreshCallGraph(const CallGraphSCC &CurSCC, CallGraph &CG,
111
                        bool IsCheckingMode);
112
};
113
114
} // end anonymous namespace.
115
116
char CGPassManager::ID = 0;
117
118
bool CGPassManager::RunPassOnSCC(Pass *P, CallGraphSCC &CurSCC,
119
                                 CallGraph &CG, bool &CallGraphUpToDate,
120
3.64M
                                 bool &DevirtualizedCall) {
121
3.64M
  bool Changed = false;
122
3.64M
  PMDataManager *PM = P->getAsPMDataManager();
123
3.64M
  Module &M = CG.getModule();
124
3.64M
125
3.64M
  if (!PM) {
126
2.88M
    CallGraphSCCPass *CGSP = (CallGraphSCCPass *)P;
127
2.88M
    if (!CallGraphUpToDate) {
128
17.9k
      DevirtualizedCall |= RefreshCallGraph(CurSCC, CG, false);
129
17.9k
      CallGraphUpToDate = true;
130
17.9k
    }
131
2.88M
132
2.88M
    {
133
2.88M
      unsigned InstrCount, SCCCount = 0;
134
2.88M
      StringMap<std::pair<unsigned, unsigned>> FunctionToInstrCount;
135
2.88M
      bool EmitICRemark = M.shouldEmitInstrCountChangedRemark();
136
2.88M
      TimeRegion PassTimer(getPassTimer(CGSP));
137
2.88M
      if (EmitICRemark)
138
6
        InstrCount = initSizeRemarkInfo(M, FunctionToInstrCount);
139
2.88M
      Changed = CGSP->runOnSCC(CurSCC);
140
2.88M
141
2.88M
      if (EmitICRemark) {
142
6
        // FIXME: Add getInstructionCount to CallGraphSCC.
143
6
        SCCCount = M.getInstructionCount();
144
6
        // Is there a difference in the number of instructions in the module?
145
6
        if (SCCCount != InstrCount) {
146
1
          // Yep. Emit a remark and update InstrCount.
147
1
          int64_t Delta =
148
1
              static_cast<int64_t>(SCCCount) - static_cast<int64_t>(InstrCount);
149
1
          emitInstrCountChangedRemark(P, M, Delta, InstrCount,
150
1
                                      FunctionToInstrCount);
151
1
          InstrCount = SCCCount;
152
1
        }
153
6
      }
154
2.88M
    }
155
2.88M
156
2.88M
    // After the CGSCCPass is done, when assertions are enabled, use
157
2.88M
    // RefreshCallGraph to verify that the callgraph was correctly updated.
158
#ifndef NDEBUG
159
    if (Changed)
160
      RefreshCallGraph(CurSCC, CG, true);
161
#endif
162
163
2.88M
    return Changed;
164
2.88M
  }
165
763k
166
763k
  assert(PM->getPassManagerType() == PMT_FunctionPassManager &&
167
763k
         "Invalid CGPassManager member");
168
763k
  FPPassManager *FPP = (FPPassManager*)P;
169
763k
170
763k
  // Run pass P on all functions in the current SCC.
171
763k
  for (CallGraphNode *CGN : CurSCC) {
172
763k
    if (Function *F = CGN->getFunction()) {
173
732k
      dumpPassInfo(P, EXECUTION_MSG, ON_FUNCTION_MSG, F->getName());
174
732k
      {
175
732k
        TimeRegion PassTimer(getPassTimer(FPP));
176
732k
        Changed |= FPP->runOnFunction(*F);
177
732k
      }
178
732k
      F->getContext().yield();
179
732k
    }
180
763k
  }
181
763k
182
763k
  // The function pass(es) modified the IR, they may have clobbered the
183
763k
  // callgraph.
184
763k
  if (Changed && 
CallGraphUpToDate280k
) {
185
280k
    LLVM_DEBUG(dbgs() << "CGSCCPASSMGR: Pass Dirtied SCC: " << P->getPassName()
186
280k
                      << '\n');
187
280k
    CallGraphUpToDate = false;
188
280k
  }
189
763k
  return Changed;
190
763k
}
191
192
/// Scan the functions in the specified CFG and resync the
193
/// callgraph with the call sites found in it.  This is used after
194
/// FunctionPasses have potentially munged the callgraph, and can be used after
195
/// CallGraphSCC passes to verify that they correctly updated the callgraph.
196
///
197
/// This function returns true if it devirtualized an existing function call,
198
/// meaning it turned an indirect call into a direct call.  This happens when
199
/// a function pass like GVN optimizes away stuff feeding the indirect call.
200
/// This never happens in checking mode.
201
bool CGPassManager::RefreshCallGraph(const CallGraphSCC &CurSCC, CallGraph &CG,
202
280k
                                     bool CheckingMode) {
203
280k
  DenseMap<Value *, CallGraphNode *> Calls;
204
280k
205
280k
  LLVM_DEBUG(dbgs() << "CGSCCPASSMGR: Refreshing SCC with " << CurSCC.size()
206
280k
                    << " nodes:\n";
207
280k
             for (CallGraphNode *CGN
208
280k
                  : CurSCC) CGN->dump(););
209
280k
210
280k
  bool MadeChange = false;
211
280k
  bool DevirtualizedCall = false;
212
280k
213
280k
  // Scan all functions in the SCC.
214
280k
  unsigned FunctionNo = 0;
215
280k
  for (CallGraphSCC::iterator SCCIdx = CurSCC.begin(), E = CurSCC.end();
216
560k
       SCCIdx != E; 
++SCCIdx, ++FunctionNo280k
) {
217
280k
    CallGraphNode *CGN = *SCCIdx;
218
280k
    Function *F = CGN->getFunction();
219
280k
    if (!F || F->isDeclaration()) 
continue0
;
220
280k
221
280k
    // Walk the function body looking for call sites.  Sync up the call sites in
222
280k
    // CGN with those actually in the function.
223
280k
224
280k
    // Keep track of the number of direct and indirect calls that were
225
280k
    // invalidated and removed.
226
280k
    unsigned NumDirectRemoved = 0, NumIndirectRemoved = 0;
227
280k
228
280k
    // Get the set of call sites currently in the function.
229
1.40M
    for (CallGraphNode::iterator I = CGN->begin(), E = CGN->end(); I != E; ) {
230
1.12M
      // If this call site is null, then the function pass deleted the call
231
1.12M
      // entirely and the WeakTrackingVH nulled it out.
232
1.12M
      auto *Call = dyn_cast_or_null<CallBase>(I->first);
233
1.12M
      if (!I->first ||
234
1.12M
          // If we've already seen this call site, then the FunctionPass RAUW'd
235
1.12M
          // one call with another, which resulted in two "uses" in the edge
236
1.12M
          // list of the same call.
237
1.12M
          
Calls.count(I->first)1.09M
||
238
1.12M
239
1.12M
          // If the call edge is not from a call or invoke, or it is a
240
1.12M
          // instrinsic call, then the function pass RAUW'd a call with
241
1.12M
          // another value. This can happen when constant folding happens
242
1.12M
          // of well known functions etc.
243
1.12M
          
!Call1.09M
||
244
1.12M
          
(1.09M
Call->getCalledFunction()1.09M
&&
245
1.09M
           
Call->getCalledFunction()->isIntrinsic()1.03M
&&
246
1.09M
           
Intrinsic::isLeaf(Call->getCalledFunction()->getIntrinsicID())6
)) {
247
34.3k
        assert(!CheckingMode &&
248
34.3k
               "CallGraphSCCPass did not update the CallGraph correctly!");
249
34.3k
250
34.3k
        // If this was an indirect call site, count it.
251
34.3k
        if (!I->second->getFunction())
252
455
          ++NumIndirectRemoved;
253
33.8k
        else
254
33.8k
          ++NumDirectRemoved;
255
34.3k
256
34.3k
        // Just remove the edge from the set of callees, keep track of whether
257
34.3k
        // I points to the last element of the vector.
258
34.3k
        bool WasLast = I + 1 == E;
259
34.3k
        CGN->removeCallEdge(I);
260
34.3k
261
34.3k
        // If I pointed to the last element of the vector, we have to bail out:
262
34.3k
        // iterator checking rejects comparisons of the resultant pointer with
263
34.3k
        // end.
264
34.3k
        if (WasLast)
265
4.64k
          break;
266
29.6k
        E = CGN->end();
267
29.6k
        continue;
268
29.6k
      }
269
1.09M
270
1.09M
      assert(!Calls.count(I->first) &&
271
1.09M
             "Call site occurs in node multiple times");
272
1.09M
273
1.09M
      if (Call) {
274
1.09M
        Function *Callee = Call->getCalledFunction();
275
1.09M
        // Ignore intrinsics because they're not really function calls.
276
1.09M
        if (!Callee || 
!(Callee->isIntrinsic())1.03M
)
277
1.09M
          Calls.insert(std::make_pair(I->first, I->second));
278
1.09M
      }
279
1.09M
      ++I;
280
1.09M
    }
281
280k
282
280k
    // Loop over all of the instructions in the function, getting the callsites.
283
280k
    // Keep track of the number of direct/indirect calls added.
284
280k
    unsigned NumDirectAdded = 0, NumIndirectAdded = 0;
285
280k
286
280k
    for (BasicBlock &BB : *F)
287
13.4M
      
for (Instruction &I : BB)2.30M
{
288
13.4M
        auto *Call = dyn_cast<CallBase>(&I);
289
13.4M
        if (!Call)
290
11.9M
          continue;
291
1.48M
        Function *Callee = Call->getCalledFunction();
292
1.48M
        if (Callee && 
Callee->isIntrinsic()1.42M
)
293
360k
          continue;
294
1.12M
295
1.12M
        // If this call site already existed in the callgraph, just verify it
296
1.12M
        // matches up to expectations and remove it from Calls.
297
1.12M
        DenseMap<Value *, CallGraphNode *>::iterator ExistingIt =
298
1.12M
            Calls.find(Call);
299
1.12M
        if (ExistingIt != Calls.end()) {
300
1.09M
          CallGraphNode *ExistingNode = ExistingIt->second;
301
1.09M
302
1.09M
          // Remove from Calls since we have now seen it.
303
1.09M
          Calls.erase(ExistingIt);
304
1.09M
305
1.09M
          // Verify that the callee is right.
306
1.09M
          if (ExistingNode->getFunction() == Call->getCalledFunction())
307
1.09M
            continue;
308
585
309
585
          // If we are in checking mode, we are not allowed to actually mutate
310
585
          // the callgraph.  If this is a case where we can infer that the
311
585
          // callgraph is less precise than it could be (e.g. an indirect call
312
585
          // site could be turned direct), don't reject it in checking mode, and
313
585
          // don't tweak it to be more precise.
314
585
          if (CheckingMode && 
Call->getCalledFunction()0
&&
315
585
              
ExistingNode->getFunction() == nullptr0
)
316
0
            continue;
317
585
318
585
          assert(!CheckingMode &&
319
585
                 "CallGraphSCCPass did not update the CallGraph correctly!");
320
585
321
585
          // If not, we either went from a direct call to indirect, indirect to
322
585
          // direct, or direct to different direct.
323
585
          CallGraphNode *CalleeNode;
324
585
          if (Function *Callee = Call->getCalledFunction()) {
325
585
            CalleeNode = CG.getOrInsertFunction(Callee);
326
585
            // Keep track of whether we turned an indirect call into a direct
327
585
            // one.
328
585
            if (!ExistingNode->getFunction()) {
329
534
              DevirtualizedCall = true;
330
534
              LLVM_DEBUG(dbgs() << "  CGSCCPASSMGR: Devirtualized call to '"
331
534
                                << Callee->getName() << "'\n");
332
534
            }
333
585
          } else {
334
0
            CalleeNode = CG.getCallsExternalNode();
335
0
          }
336
585
337
585
          // Update the edge target in CGN.
338
585
          CGN->replaceCallEdge(*Call, *Call, CalleeNode);
339
585
          MadeChange = true;
340
585
          continue;
341
585
        }
342
35.7k
343
35.7k
        assert(!CheckingMode &&
344
35.7k
               "CallGraphSCCPass did not update the CallGraph correctly!");
345
35.7k
346
35.7k
        // If the call site didn't exist in the CGN yet, add it.
347
35.7k
        CallGraphNode *CalleeNode;
348
35.7k
        if (Function *Callee = Call->getCalledFunction()) {
349
30.4k
          CalleeNode = CG.getOrInsertFunction(Callee);
350
30.4k
          ++NumDirectAdded;
351
30.4k
        } else {
352
5.27k
          CalleeNode = CG.getCallsExternalNode();
353
5.27k
          ++NumIndirectAdded;
354
5.27k
        }
355
35.7k
356
35.7k
        CGN->addCalledFunction(Call, CalleeNode);
357
35.7k
        MadeChange = true;
358
35.7k
      }
359
280k
360
280k
    // We scanned the old callgraph node, removing invalidated call sites and
361
280k
    // then added back newly found call sites.  One thing that can happen is
362
280k
    // that an old indirect call site was deleted and replaced with a new direct
363
280k
    // call.  In this case, we have devirtualized a call, and CGSCCPM would like
364
280k
    // to iteratively optimize the new code.  Unfortunately, we don't really
365
280k
    // have a great way to detect when this happens.  As an approximation, we
366
280k
    // just look at whether the number of indirect calls is reduced and the
367
280k
    // number of direct calls is increased.  There are tons of ways to fool this
368
280k
    // (e.g. DCE'ing an indirect call and duplicating an unrelated block with a
369
280k
    // direct call) but this is close enough.
370
280k
    if (NumIndirectRemoved > NumIndirectAdded &&
371
280k
        
NumDirectRemoved < NumDirectAdded185
)
372
6
      DevirtualizedCall = true;
373
280k
374
280k
    // After scanning this function, if we still have entries in callsites, then
375
280k
    // they are dangling pointers.  WeakTrackingVH should save us for this, so
376
280k
    // abort if
377
280k
    // this happens.
378
280k
    assert(Calls.empty() && "Dangling pointers found in call sites map");
379
280k
380
280k
    // Periodically do an explicit clear to remove tombstones when processing
381
280k
    // large scc's.
382
280k
    if ((FunctionNo & 15) == 15)
383
8
      Calls.clear();
384
280k
  }
385
280k
386
280k
  LLVM_DEBUG(if (MadeChange) {
387
280k
    dbgs() << "CGSCCPASSMGR: Refreshed SCC is now:\n";
388
280k
    for (CallGraphNode *CGN : CurSCC)
389
280k
      CGN->dump();
390
280k
    if (DevirtualizedCall)
391
280k
      dbgs() << "CGSCCPASSMGR: Refresh devirtualized a call!\n";
392
280k
  } else {
393
280k
    dbgs() << "CGSCCPASSMGR: SCC Refresh didn't change call graph.\n";
394
280k
  });
395
280k
  (void)MadeChange;
396
280k
397
280k
  return DevirtualizedCall;
398
280k
}
399
400
/// Execute the body of the entire pass manager on the specified SCC.
401
/// This keeps track of whether a function pass devirtualizes
402
/// any calls and returns it in DevirtualizedCall.
403
bool CGPassManager::RunAllPassesOnSCC(CallGraphSCC &CurSCC, CallGraph &CG,
404
940k
                                      bool &DevirtualizedCall) {
405
940k
  bool Changed = false;
406
940k
407
940k
  // Keep track of whether the callgraph is known to be up-to-date or not.
408
940k
  // The CGSSC pass manager runs two types of passes:
409
940k
  // CallGraphSCC Passes and other random function passes.  Because other
410
940k
  // random function passes are not CallGraph aware, they may clobber the
411
940k
  // call graph by introducing new calls or deleting other ones.  This flag
412
940k
  // is set to false when we run a function pass so that we know to clean up
413
940k
  // the callgraph when we need to run a CGSCCPass again.
414
940k
  bool CallGraphUpToDate = true;
415
940k
416
940k
  // Run all passes on current SCC.
417
940k
  for (unsigned PassNo = 0, e = getNumContainedPasses();
418
4.59M
       PassNo != e; 
++PassNo3.64M
) {
419
3.64M
    Pass *P = getContainedPass(PassNo);
420
3.64M
421
3.64M
    // If we're in -debug-pass=Executions mode, construct the SCC node list,
422
3.64M
    // otherwise avoid constructing this string as it is expensive.
423
3.64M
    if (isPassDebuggingExecutionsOrMore()) {
424
4
      std::string Functions;
425
  #ifndef NDEBUG
426
      raw_string_ostream OS(Functions);
427
      for (CallGraphSCC::iterator I = CurSCC.begin(), E = CurSCC.end();
428
           I != E; ++I) {
429
        if (I != CurSCC.begin()) OS << ", ";
430
        (*I)->print(OS);
431
      }
432
      OS.flush();
433
  #endif
434
      dumpPassInfo(P, EXECUTION_MSG, ON_CG_MSG, Functions);
435
4
    }
436
3.64M
    dumpRequiredSet(P);
437
3.64M
438
3.64M
    initializeAnalysisImpl(P);
439
3.64M
440
3.64M
    // Actually run this pass on the current SCC.
441
3.64M
    Changed |= RunPassOnSCC(P, CurSCC, CG,
442
3.64M
                            CallGraphUpToDate, DevirtualizedCall);
443
3.64M
444
3.64M
    if (Changed)
445
969k
      dumpPassInfo(P, MODIFICATION_MSG, ON_CG_MSG, "");
446
3.64M
    dumpPreservedSet(P);
447
3.64M
448
3.64M
    verifyPreservedAnalysis(P);
449
3.64M
    removeNotPreservedAnalysis(P);
450
3.64M
    recordAvailableAnalysis(P);
451
3.64M
    removeDeadPasses(P, "", ON_CG_MSG);
452
3.64M
  }
453
940k
454
940k
  // If the callgraph was left out of date (because the last pass run was a
455
940k
  // functionpass), refresh it before we move on to the next SCC.
456
940k
  if (!CallGraphUpToDate)
457
262k
    DevirtualizedCall |= RefreshCallGraph(CurSCC, CG, false);
458
940k
  return Changed;
459
940k
}
460
461
/// Execute all of the passes scheduled for execution.  Keep track of
462
/// whether any of the passes modifies the module, and if so, return true.
463
31.7k
bool CGPassManager::runOnModule(Module &M) {
464
31.7k
  CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
465
31.7k
  bool Changed = doInitialization(CG);
466
31.7k
467
31.7k
  // Walk the callgraph in bottom-up SCC order.
468
31.7k
  scc_iterator<CallGraph*> CGI = scc_begin(&CG);
469
31.7k
470
31.7k
  CallGraphSCC CurSCC(CG, &CGI);
471
972k
  while (!CGI.isAtEnd()) {
472
940k
    // Copy the current SCC and increment past it so that the pass can hack
473
940k
    // on the SCC if it wants to without invalidating our iterator.
474
940k
    const std::vector<CallGraphNode *> &NodeVec = *CGI;
475
940k
    CurSCC.initialize(NodeVec);
476
940k
    ++CGI;
477
940k
478
940k
    // At the top level, we run all the passes in this pass manager on the
479
940k
    // functions in this SCC.  However, we support iterative compilation in the
480
940k
    // case where a function pass devirtualizes a call to a function.  For
481
940k
    // example, it is very common for a function pass (often GVN or instcombine)
482
940k
    // to eliminate the addressing that feeds into a call.  With that improved
483
940k
    // information, we would like the call to be an inline candidate, infer
484
940k
    // mod-ref information etc.
485
940k
    //
486
940k
    // Because of this, we allow iteration up to a specified iteration count.
487
940k
    // This only happens in the case of a devirtualized call, so we only burn
488
940k
    // compile time in the case that we're making progress.  We also have a hard
489
940k
    // iteration count limit in case there is crazy code.
490
940k
    unsigned Iteration = 0;
491
940k
    bool DevirtualizedCall = false;
492
940k
    do {
493
940k
      LLVM_DEBUG(if (Iteration) dbgs()
494
940k
                 << "  SCCPASSMGR: Re-visiting SCC, iteration #" << Iteration
495
940k
                 << '\n');
496
940k
      DevirtualizedCall = false;
497
940k
      Changed |= RunAllPassesOnSCC(CurSCC, CG, DevirtualizedCall);
498
940k
    } while (Iteration++ < MaxIterations && 
DevirtualizedCall940k
);
499
940k
500
940k
    if (DevirtualizedCall)
501
940k
      LLVM_DEBUG(dbgs() << "  CGSCCPASSMGR: Stopped iteration after "
502
940k
                        << Iteration
503
940k
                        << " times, due to -max-cg-scc-iterations\n");
504
940k
505
940k
    MaxSCCIterations.updateMax(Iteration);
506
940k
  }
507
31.7k
  Changed |= doFinalization(CG);
508
31.7k
  return Changed;
509
31.7k
}
510
511
/// Initialize CG
512
31.7k
bool CGPassManager::doInitialization(CallGraph &CG) {
513
31.7k
  bool Changed = false;
514
124k
  for (unsigned i = 0, e = getNumContainedPasses(); i != e; 
++i92.7k
) {
515
92.7k
    if (PMDataManager *PM = getContainedPass(i)->getAsPMDataManager()) {
516
21.2k
      assert(PM->getPassManagerType() == PMT_FunctionPassManager &&
517
21.2k
             "Invalid CGPassManager member");
518
21.2k
      Changed |= ((FPPassManager*)PM)->doInitialization(CG.getModule());
519
71.4k
    } else {
520
71.4k
      Changed |= ((CallGraphSCCPass*)getContainedPass(i))->doInitialization(CG);
521
71.4k
    }
522
92.7k
  }
523
31.7k
  return Changed;
524
31.7k
}
525
526
/// Finalize CG
527
31.7k
bool CGPassManager::doFinalization(CallGraph &CG) {
528
31.7k
  bool Changed = false;
529
124k
  for (unsigned i = 0, e = getNumContainedPasses(); i != e; 
++i92.7k
) {
530
92.7k
    if (PMDataManager *PM = getContainedPass(i)->getAsPMDataManager()) {
531
21.2k
      assert(PM->getPassManagerType() == PMT_FunctionPassManager &&
532
21.2k
             "Invalid CGPassManager member");
533
21.2k
      Changed |= ((FPPassManager*)PM)->doFinalization(CG.getModule());
534
71.4k
    } else {
535
71.4k
      Changed |= ((CallGraphSCCPass*)getContainedPass(i))->doFinalization(CG);
536
71.4k
    }
537
92.7k
  }
538
31.7k
  return Changed;
539
31.7k
}
540
541
//===----------------------------------------------------------------------===//
542
// CallGraphSCC Implementation
543
//===----------------------------------------------------------------------===//
544
545
/// This informs the SCC and the pass manager that the specified
546
/// Old node has been deleted, and New is to be used in its place.
547
1.83k
void CallGraphSCC::ReplaceNode(CallGraphNode *Old, CallGraphNode *New) {
548
1.83k
  assert(Old != New && "Should not replace node with self");
549
1.83k
  for (unsigned i = 0; ; 
++i0
) {
550
1.83k
    assert(i != Nodes.size() && "Node not in SCC");
551
1.83k
    if (Nodes[i] != Old) 
continue0
;
552
1.83k
    Nodes[i] = New;
553
1.83k
    break;
554
1.83k
  }
555
1.83k
556
1.83k
  // Update the active scc_iterator so that it doesn't contain dangling
557
1.83k
  // pointers to the old CallGraphNode.
558
1.83k
  scc_iterator<CallGraph*> *CGI = (scc_iterator<CallGraph*>*)Context;
559
1.83k
  CGI->ReplaceNode(Old, New);
560
1.83k
}
561
562
//===----------------------------------------------------------------------===//
563
// CallGraphSCCPass Implementation
564
//===----------------------------------------------------------------------===//
565
566
/// Assign pass manager to manage this pass.
567
void CallGraphSCCPass::assignPassManager(PMStack &PMS,
568
71.4k
                                         PassManagerType PreferredType) {
569
71.4k
  // Find CGPassManager
570
76.6k
  while (!PMS.empty() &&
571
76.6k
         PMS.top()->getPassManagerType() > PMT_CallGraphPassManager)
572
5.13k
    PMS.pop();
573
71.4k
574
71.4k
  assert(!PMS.empty() && "Unable to handle Call Graph Pass");
575
71.4k
  CGPassManager *CGP;
576
71.4k
577
71.4k
  if (PMS.top()->getPassManagerType() == PMT_CallGraphPassManager)
578
39.6k
    CGP = (CGPassManager*)PMS.top();
579
31.8k
  else {
580
31.8k
    // Create new Call Graph SCC Pass Manager if it does not exist.
581
31.8k
    assert(!PMS.empty() && "Unable to create Call Graph Pass Manager");
582
31.8k
    PMDataManager *PMD = PMS.top();
583
31.8k
584
31.8k
    // [1] Create new Call Graph Pass Manager
585
31.8k
    CGP = new CGPassManager();
586
31.8k
587
31.8k
    // [2] Set up new manager's top level manager
588
31.8k
    PMTopLevelManager *TPM = PMD->getTopLevelManager();
589
31.8k
    TPM->addIndirectPassManager(CGP);
590
31.8k
591
31.8k
    // [3] Assign manager to manage this new manager. This may create
592
31.8k
    // and push new managers into PMS
593
31.8k
    Pass *P = CGP;
594
31.8k
    TPM->schedulePass(P);
595
31.8k
596
31.8k
    // [4] Push new manager into PMS
597
31.8k
    PMS.push(CGP);
598
31.8k
  }
599
71.4k
600
71.4k
  CGP->add(this);
601
71.4k
}
602
603
/// For this class, we declare that we require and preserve the call graph.
604
/// If the derived class implements this method, it should
605
/// always explicitly call the implementation here.
606
66.3k
void CallGraphSCCPass::getAnalysisUsage(AnalysisUsage &AU) const {
607
66.3k
  AU.addRequired<CallGraphWrapperPass>();
608
66.3k
  AU.addPreserved<CallGraphWrapperPass>();
609
66.3k
}
610
611
//===----------------------------------------------------------------------===//
612
// PrintCallGraphPass Implementation
613
//===----------------------------------------------------------------------===//
614
615
namespace {
616
617
  /// PrintCallGraphPass - Print a Module corresponding to a call graph.
618
  ///
619
  class PrintCallGraphPass : public CallGraphSCCPass {
620
    std::string Banner;
621
    raw_ostream &OS;       // raw_ostream to print on.
622
623
  public:
624
    static char ID;
625
626
    PrintCallGraphPass(const std::string &B, raw_ostream &OS)
627
6
      : CallGraphSCCPass(ID), Banner(B), OS(OS) {}
628
629
6
    void getAnalysisUsage(AnalysisUsage &AU) const override {
630
6
      AU.setPreservesAll();
631
6
    }
632
633
14
    bool runOnSCC(CallGraphSCC &SCC) override {
634
14
      bool BannerPrinted = false;
635
15
      auto PrintBannerOnce = [&]() {
636
15
        if (BannerPrinted)
637
1
          return;
638
14
        OS << Banner;
639
14
        BannerPrinted = true;
640
14
      };
641
14
642
14
      bool NeedModule = llvm::forcePrintModuleIR();
643
14
      if (isFunctionInPrintList("*") && NeedModule) {
644
3
        PrintBannerOnce();
645
3
        OS << "\n";
646
3
        SCC.getCallGraph().getModule().print(OS, nullptr);
647
3
        return false;
648
3
      }
649
11
      bool FoundFunction = false;
650
12
      for (CallGraphNode *CGN : SCC) {
651
12
        if (Function *F = CGN->getFunction()) {
652
7
          if (!F->isDeclaration() && isFunctionInPrintList(F->getName())) {
653
7
            FoundFunction = true;
654
7
            if (!NeedModule) {
655
7
              PrintBannerOnce();
656
7
              F->print(OS);
657
7
            }
658
7
          }
659
7
        } else 
if (5
isFunctionInPrintList("*")5
) {
660
5
          PrintBannerOnce();
661
5
          OS << "\nPrinting <null> Function\n";
662
5
        }
663
12
      }
664
11
      if (NeedModule && 
FoundFunction0
) {
665
0
        PrintBannerOnce();
666
0
        OS << "\n";
667
0
        SCC.getCallGraph().getModule().print(OS, nullptr);
668
0
      }
669
11
      return false;
670
11
    }
671
672
0
    StringRef getPassName() const override { return "Print CallGraph IR"; }
673
  };
674
675
} // end anonymous namespace.
676
677
char PrintCallGraphPass::ID = 0;
678
679
Pass *CallGraphSCCPass::createPrinterPass(raw_ostream &OS,
680
6
                                          const std::string &Banner) const {
681
6
  return new PrintCallGraphPass(Banner, OS);
682
6
}
683
684
80
static std::string getDescription(const CallGraphSCC &SCC) {
685
80
  std::string Desc = "SCC (";
686
80
  bool First = true;
687
80
  for (CallGraphNode *CGN : SCC) {
688
80
    if (First)
689
80
      First = false;
690
0
    else
691
0
      Desc += ", ";
692
80
    Function *F = CGN->getFunction();
693
80
    if (F)
694
60
      Desc += F->getName();
695
20
    else
696
20
      Desc += "<<null function>>";
697
80
  }
698
80
  Desc += ")";
699
80
  return Desc;
700
80
}
701
702
2.55M
bool CallGraphSCCPass::skipSCC(CallGraphSCC &SCC) const {
703
2.55M
  OptPassGate &Gate =
704
2.55M
      SCC.getCallGraph().getModule().getContext().getOptPassGate();
705
2.55M
  return Gate.isEnabled() && 
!Gate.shouldRunPass(this, getDescription(SCC))80
;
706
2.55M
}
707
708
char DummyCGSCCPass::ID = 0;
709
710
INITIALIZE_PASS(DummyCGSCCPass, "DummyCGSCCPass", "DummyCGSCCPass", false,
711
                false)