Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/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
//                     The LLVM Compiler Infrastructure
4
//
5
// This file is distributed under the University of Illinois Open Source
6
// License. See LICENSE.TXT for details.
7
//
8
//===----------------------------------------------------------------------===//
9
//
10
// This file implements the CallGraphSCCPass class, which is used for passes
11
// which are implemented as bottom-up traversals on the call graph.  Because
12
// there may be cycles in the call graph, passes of this type operate on the
13
// call-graph in SCC order: that is, they process function bottom-up, except for
14
// recursive functions, which they process all at once.
15
//
16
//===----------------------------------------------------------------------===//
17
18
#include "llvm/Analysis/CallGraphSCCPass.h"
19
#include "llvm/ADT/DenseMap.h"
20
#include "llvm/ADT/SCCIterator.h"
21
#include "llvm/ADT/Statistic.h"
22
#include "llvm/Analysis/CallGraph.h"
23
#include "llvm/IR/CallSite.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/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
26.4k
  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
26.4k
  void getAnalysisUsage(AnalysisUsage &Info) const override {
74
26.4k
    // CGPassManager walks SCC and it needs CallGraph.
75
26.4k
    Info.addRequired<CallGraphWrapperPass>();
76
26.4k
    Info.setPreservesAll();
77
26.4k
  }
78
79
2
  StringRef getPassName() const override { return "CallGraph Pass Manager"; }
80
81
26.5k
  PMDataManager *getAsPMDataManager() override { return this; }
82
3.23M
  Pass *getAsPass() override { return this; }
83
84
  // Print passes managed by this manager
85
12
  void dumpPassStructure(unsigned Offset) override {
86
12
    errs().indent(Offset*2) << "Call Graph SCC Pass Manager\n";
87
48
    for (unsigned Index = 0; 
Index < getNumContainedPasses()48
;
++Index36
) {
88
36
      Pass *P = getContainedPass(Index);
89
36
      P->dumpPassStructure(Offset + 1);
90
36
      dumpLastUses(P, Offset+1);
91
36
    }
92
12
  }
93
94
4.33M
  Pass *getContainedPass(unsigned N) {
95
4.33M
    assert(N < PassVector.size() && "Pass number out of range!");
96
4.33M
    return static_cast<Pass *>(PassVector[N]);
97
4.33M
  }
98
99
211k
  PassManagerType getPassManagerType() const override {
100
211k
    return PMT_CallGraphPassManager; 
101
211k
  }
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.97M
                                 bool &DevirtualizedCall) {
121
3.97M
  bool Changed = false;
122
3.97M
  PMDataManager *PM = P->getAsPMDataManager();
123
3.97M
124
3.97M
  if (
!PM3.97M
) {
125
3.17M
    CallGraphSCCPass *CGSP = (CallGraphSCCPass*)P;
126
3.17M
    if (
!CallGraphUpToDate3.17M
) {
127
14.8k
      DevirtualizedCall |= RefreshCallGraph(CurSCC, CG, false);
128
14.8k
      CallGraphUpToDate = true;
129
14.8k
    }
130
3.17M
131
3.17M
    {
132
3.17M
      TimeRegion PassTimer(getPassTimer(CGSP));
133
3.17M
      Changed = CGSP->runOnSCC(CurSCC);
134
3.17M
    }
135
3.17M
    
136
3.17M
    // After the CGSCCPass is done, when assertions are enabled, use
137
3.17M
    // RefreshCallGraph to verify that the callgraph was correctly updated.
138
#ifndef NDEBUG
139
    if (Changed)
140
      RefreshCallGraph(CurSCC, CG, true);
141
#endif
142
    
143
3.17M
    return Changed;
144
3.17M
  }
145
798k
  
146
3.97M
  assert(PM->getPassManagerType() == PMT_FunctionPassManager &&
147
798k
         "Invalid CGPassManager member");
148
798k
  FPPassManager *FPP = (FPPassManager*)P;
149
798k
  
150
798k
  // Run pass P on all functions in the current SCC.
151
799k
  for (CallGraphNode *CGN : CurSCC) {
152
799k
    if (Function *
F799k
= CGN->getFunction()) {
153
764k
      dumpPassInfo(P, EXECUTION_MSG, ON_FUNCTION_MSG, F->getName());
154
764k
      {
155
764k
        TimeRegion PassTimer(getPassTimer(FPP));
156
764k
        Changed |= FPP->runOnFunction(*F);
157
764k
      }
158
764k
      F->getContext().yield();
159
764k
    }
160
799k
  }
161
798k
  
162
798k
  // The function pass(es) modified the IR, they may have clobbered the
163
798k
  // callgraph.
164
798k
  if (
Changed && 798k
CallGraphUpToDate232k
) {
165
232k
    DEBUG(dbgs() << "CGSCCPASSMGR: Pass Dirtied SCC: "
166
232k
                 << P->getPassName() << '\n');
167
232k
    CallGraphUpToDate = false;
168
232k
  }
169
3.97M
  return Changed;
170
3.97M
}
171
172
/// Scan the functions in the specified CFG and resync the
173
/// callgraph with the call sites found in it.  This is used after
174
/// FunctionPasses have potentially munged the callgraph, and can be used after
175
/// CallGraphSCC passes to verify that they correctly updated the callgraph.
176
///
177
/// This function returns true if it devirtualized an existing function call,
178
/// meaning it turned an indirect call into a direct call.  This happens when
179
/// a function pass like GVN optimizes away stuff feeding the indirect call.
180
/// This never happens in checking mode.
181
bool CGPassManager::RefreshCallGraph(const CallGraphSCC &CurSCC, CallGraph &CG,
182
232k
                                     bool CheckingMode) {
183
232k
  DenseMap<Value*, CallGraphNode*> CallSites;
184
232k
  
185
232k
  DEBUG(dbgs() << "CGSCCPASSMGR: Refreshing SCC with " << CurSCC.size()
186
232k
               << " nodes:\n";
187
232k
        for (CallGraphNode *CGN : CurSCC)
188
232k
          CGN->dump();
189
232k
        );
190
232k
191
232k
  bool MadeChange = false;
192
232k
  bool DevirtualizedCall = false;
193
232k
  
194
232k
  // Scan all functions in the SCC.
195
232k
  unsigned FunctionNo = 0;
196
232k
  for (CallGraphSCC::iterator SCCIdx = CurSCC.begin(), E = CurSCC.end();
197
465k
       
SCCIdx != E465k
;
++SCCIdx, ++FunctionNo233k
) {
198
233k
    CallGraphNode *CGN = *SCCIdx;
199
233k
    Function *F = CGN->getFunction();
200
233k
    if (
!F || 233k
F->isDeclaration()233k
)
continue0
;
201
233k
    
202
233k
    // Walk the function body looking for call sites.  Sync up the call sites in
203
233k
    // CGN with those actually in the function.
204
233k
205
233k
    // Keep track of the number of direct and indirect calls that were
206
233k
    // invalidated and removed.
207
233k
    unsigned NumDirectRemoved = 0, NumIndirectRemoved = 0;
208
233k
    
209
233k
    // Get the set of call sites currently in the function.
210
1.65M
    for (CallGraphNode::iterator I = CGN->begin(), E = CGN->end(); 
I != E1.65M
; ) {
211
1.42M
      // If this call site is null, then the function pass deleted the call
212
1.42M
      // entirely and the WeakTrackingVH nulled it out.
213
1.42M
      if (!I->first ||
214
1.42M
          // If we've already seen this call site, then the FunctionPass RAUW'd
215
1.42M
          // one call with another, which resulted in two "uses" in the edge
216
1.42M
          // list of the same call.
217
1.37M
          CallSites.count(I->first) ||
218
1.42M
219
1.42M
          // If the call edge is not from a call or invoke, or it is a
220
1.42M
          // instrinsic call, then the function pass RAUW'd a call with 
221
1.42M
          // another value. This can happen when constant folding happens
222
1.42M
          // of well known functions etc.
223
1.37M
          !CallSite(I->first) ||
224
1.37M
          (CallSite(I->first).getCalledFunction() &&
225
1.32M
           CallSite(I->first).getCalledFunction()->isIntrinsic() &&
226
6
           Intrinsic::isLeaf(
227
1.42M
               CallSite(I->first).getCalledFunction()->getIntrinsicID()))) {
228
46.2k
        assert(!CheckingMode &&
229
46.2k
               "CallGraphSCCPass did not update the CallGraph correctly!");
230
46.2k
        
231
46.2k
        // If this was an indirect call site, count it.
232
46.2k
        if (!I->second->getFunction())
233
441
          ++NumIndirectRemoved;
234
46.2k
        else 
235
45.8k
          ++NumDirectRemoved;
236
46.2k
        
237
46.2k
        // Just remove the edge from the set of callees, keep track of whether
238
46.2k
        // I points to the last element of the vector.
239
46.2k
        bool WasLast = I + 1 == E;
240
46.2k
        CGN->removeCallEdge(I);
241
46.2k
        
242
46.2k
        // If I pointed to the last element of the vector, we have to bail out:
243
46.2k
        // iterator checking rejects comparisons of the resultant pointer with
244
46.2k
        // end.
245
46.2k
        if (WasLast)
246
2.26k
          break;
247
43.9k
        E = CGN->end();
248
43.9k
        continue;
249
43.9k
      }
250
1.37M
      
251
1.42M
      assert(!CallSites.count(I->first) &&
252
1.37M
             "Call site occurs in node multiple times");
253
1.37M
      
254
1.37M
      CallSite CS(I->first);
255
1.37M
      if (
CS1.37M
) {
256
1.37M
        Function *Callee = CS.getCalledFunction();
257
1.37M
        // Ignore intrinsics because they're not really function calls.
258
1.37M
        if (
!Callee || 1.37M
!(Callee->isIntrinsic())1.32M
)
259
1.37M
          CallSites.insert(std::make_pair(I->first, I->second));
260
1.37M
      }
261
1.42M
      ++I;
262
1.42M
    }
263
233k
    
264
233k
    // Loop over all of the instructions in the function, getting the callsites.
265
233k
    // Keep track of the number of direct/indirect calls added.
266
233k
    unsigned NumDirectAdded = 0, NumIndirectAdded = 0;
267
233k
268
233k
    for (BasicBlock &BB : *F)
269
3.07M
      
for (Instruction &I : BB) 3.07M
{
270
16.8M
        CallSite CS(&I);
271
16.8M
        if (
!CS16.8M
)
continue15.0M
;
272
1.72M
        Function *Callee = CS.getCalledFunction();
273
1.72M
        if (
Callee && 1.72M
Callee->isIntrinsic()1.67M
)
continue293k
;
274
1.43M
        
275
1.43M
        // If this call site already existed in the callgraph, just verify it
276
1.43M
        // matches up to expectations and remove it from CallSites.
277
1.43M
        DenseMap<Value*, CallGraphNode*>::iterator ExistingIt =
278
1.43M
          CallSites.find(CS.getInstruction());
279
1.43M
        if (
ExistingIt != CallSites.end()1.43M
) {
280
1.37M
          CallGraphNode *ExistingNode = ExistingIt->second;
281
1.37M
282
1.37M
          // Remove from CallSites since we have now seen it.
283
1.37M
          CallSites.erase(ExistingIt);
284
1.37M
          
285
1.37M
          // Verify that the callee is right.
286
1.37M
          if (ExistingNode->getFunction() == CS.getCalledFunction())
287
1.37M
            continue;
288
232
          
289
232
          // If we are in checking mode, we are not allowed to actually mutate
290
232
          // the callgraph.  If this is a case where we can infer that the
291
232
          // callgraph is less precise than it could be (e.g. an indirect call
292
232
          // site could be turned direct), don't reject it in checking mode, and
293
232
          // don't tweak it to be more precise.
294
232
          
if (232
CheckingMode && 232
CS.getCalledFunction()0
&&
295
0
              ExistingNode->getFunction() == nullptr)
296
0
            continue;
297
232
          
298
0
          assert(!CheckingMode &&
299
232
                 "CallGraphSCCPass did not update the CallGraph correctly!");
300
232
          
301
232
          // If not, we either went from a direct call to indirect, indirect to
302
232
          // direct, or direct to different direct.
303
232
          CallGraphNode *CalleeNode;
304
232
          if (Function *
Callee232
= CS.getCalledFunction()) {
305
232
            CalleeNode = CG.getOrInsertFunction(Callee);
306
232
            // Keep track of whether we turned an indirect call into a direct
307
232
            // one.
308
232
            if (
!ExistingNode->getFunction()232
) {
309
230
              DevirtualizedCall = true;
310
230
              DEBUG(dbgs() << "  CGSCCPASSMGR: Devirtualized call to '"
311
230
                           << Callee->getName() << "'\n");
312
230
            }
313
0
          } else {
314
0
            CalleeNode = CG.getCallsExternalNode();
315
0
          }
316
1.37M
317
1.37M
          // Update the edge target in CGN.
318
1.37M
          CGN->replaceCallEdge(CS, CS, CalleeNode);
319
1.37M
          MadeChange = true;
320
1.37M
          continue;
321
1.37M
        }
322
60.2k
        
323
1.43M
        assert(!CheckingMode &&
324
60.2k
               "CallGraphSCCPass did not update the CallGraph correctly!");
325
60.2k
326
60.2k
        // If the call site didn't exist in the CGN yet, add it.
327
60.2k
        CallGraphNode *CalleeNode;
328
60.2k
        if (Function *
Callee60.2k
= CS.getCalledFunction()) {
329
57.5k
          CalleeNode = CG.getOrInsertFunction(Callee);
330
57.5k
          ++NumDirectAdded;
331
60.2k
        } else {
332
2.62k
          CalleeNode = CG.getCallsExternalNode();
333
2.62k
          ++NumIndirectAdded;
334
2.62k
        }
335
3.07M
        
336
3.07M
        CGN->addCalledFunction(CS, CalleeNode);
337
3.07M
        MadeChange = true;
338
3.07M
      }
339
233k
    
340
233k
    // We scanned the old callgraph node, removing invalidated call sites and
341
233k
    // then added back newly found call sites.  One thing that can happen is
342
233k
    // that an old indirect call site was deleted and replaced with a new direct
343
233k
    // call.  In this case, we have devirtualized a call, and CGSCCPM would like
344
233k
    // to iteratively optimize the new code.  Unfortunately, we don't really
345
233k
    // have a great way to detect when this happens.  As an approximation, we
346
233k
    // just look at whether the number of indirect calls is reduced and the
347
233k
    // number of direct calls is increased.  There are tons of ways to fool this
348
233k
    // (e.g. DCE'ing an indirect call and duplicating an unrelated block with a
349
233k
    // direct call) but this is close enough.
350
233k
    if (NumIndirectRemoved > NumIndirectAdded &&
351
116
        NumDirectRemoved < NumDirectAdded)
352
12
      DevirtualizedCall = true;
353
233k
    
354
233k
    // After scanning this function, if we still have entries in callsites, then
355
233k
    // they are dangling pointers.  WeakTrackingVH should save us for this, so
356
233k
    // abort if
357
233k
    // this happens.
358
233k
    assert(CallSites.empty() && "Dangling pointers found in call sites map");
359
233k
    
360
233k
    // Periodically do an explicit clear to remove tombstones when processing
361
233k
    // large scc's.
362
233k
    if ((FunctionNo & 15) == 15)
363
16
      CallSites.clear();
364
233k
  }
365
232k
366
232k
  DEBUG(if (MadeChange) {
367
232k
          dbgs() << "CGSCCPASSMGR: Refreshed SCC is now:\n";
368
232k
          for (CallGraphNode *CGN : CurSCC)
369
232k
            CGN->dump();
370
232k
          if (DevirtualizedCall)
371
232k
            dbgs() << "CGSCCPASSMGR: Refresh devirtualized a call!\n";
372
232k
373
232k
         } else {
374
232k
           dbgs() << "CGSCCPASSMGR: SCC Refresh didn't change call graph.\n";
375
232k
         }
376
232k
        );
377
232k
  (void)MadeChange;
378
232k
379
232k
  return DevirtualizedCall;
380
232k
}
381
382
/// Execute the body of the entire pass manager on the specified SCC.
383
/// This keeps track of whether a function pass devirtualizes
384
/// any calls and returns it in DevirtualizedCall.
385
bool CGPassManager::RunAllPassesOnSCC(CallGraphSCC &CurSCC, CallGraph &CG,
386
901k
                                      bool &DevirtualizedCall) {
387
901k
  bool Changed = false;
388
901k
  
389
901k
  // Keep track of whether the callgraph is known to be up-to-date or not.
390
901k
  // The CGSSC pass manager runs two types of passes:
391
901k
  // CallGraphSCC Passes and other random function passes.  Because other
392
901k
  // random function passes are not CallGraph aware, they may clobber the
393
901k
  // call graph by introducing new calls or deleting other ones.  This flag
394
901k
  // is set to false when we run a function pass so that we know to clean up
395
901k
  // the callgraph when we need to run a CGSCCPass again.
396
901k
  bool CallGraphUpToDate = true;
397
901k
398
901k
  // Run all passes on current SCC.
399
901k
  for (unsigned PassNo = 0, e = getNumContainedPasses();
400
4.87M
       
PassNo != e4.87M
;
++PassNo3.97M
) {
401
3.97M
    Pass *P = getContainedPass(PassNo);
402
3.97M
    
403
3.97M
    // If we're in -debug-pass=Executions mode, construct the SCC node list,
404
3.97M
    // otherwise avoid constructing this string as it is expensive.
405
3.97M
    if (
isPassDebuggingExecutionsOrMore()3.97M
) {
406
4
      std::string Functions;
407
  #ifndef NDEBUG
408
      raw_string_ostream OS(Functions);
409
      for (CallGraphSCC::iterator I = CurSCC.begin(), E = CurSCC.end();
410
           I != E; ++I) {
411
        if (I != CurSCC.begin()) OS << ", ";
412
        (*I)->print(OS);
413
      }
414
      OS.flush();
415
  #endif
416
      dumpPassInfo(P, EXECUTION_MSG, ON_CG_MSG, Functions);
417
4
    }
418
3.97M
    dumpRequiredSet(P);
419
3.97M
    
420
3.97M
    initializeAnalysisImpl(P);
421
3.97M
    
422
3.97M
    // Actually run this pass on the current SCC.
423
3.97M
    Changed |= RunPassOnSCC(P, CurSCC, CG,
424
3.97M
                            CallGraphUpToDate, DevirtualizedCall);
425
3.97M
    
426
3.97M
    if (Changed)
427
625k
      dumpPassInfo(P, MODIFICATION_MSG, ON_CG_MSG, "");
428
3.97M
    dumpPreservedSet(P);
429
3.97M
    
430
3.97M
    verifyPreservedAnalysis(P);      
431
3.97M
    removeNotPreservedAnalysis(P);
432
3.97M
    recordAvailableAnalysis(P);
433
3.97M
    removeDeadPasses(P, "", ON_CG_MSG);
434
3.97M
  }
435
901k
  
436
901k
  // If the callgraph was left out of date (because the last pass run was a
437
901k
  // functionpass), refresh it before we move on to the next SCC.
438
901k
  if (!CallGraphUpToDate)
439
217k
    DevirtualizedCall |= RefreshCallGraph(CurSCC, CG, false);
440
901k
  return Changed;
441
901k
}
442
443
/// Execute all of the passes scheduled for execution.  Keep track of
444
/// whether any of the passes modifies the module, and if so, return true.
445
26.4k
bool CGPassManager::runOnModule(Module &M) {
446
26.4k
  CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
447
26.4k
  bool Changed = doInitialization(CG);
448
26.4k
  
449
26.4k
  // Walk the callgraph in bottom-up SCC order.
450
26.4k
  scc_iterator<CallGraph*> CGI = scc_begin(&CG);
451
26.4k
452
26.4k
  CallGraphSCC CurSCC(CG, &CGI);
453
927k
  while (
!CGI.isAtEnd()927k
) {
454
901k
    // Copy the current SCC and increment past it so that the pass can hack
455
901k
    // on the SCC if it wants to without invalidating our iterator.
456
901k
    const std::vector<CallGraphNode *> &NodeVec = *CGI;
457
901k
    CurSCC.initialize(NodeVec);
458
901k
    ++CGI;
459
901k
460
901k
    // At the top level, we run all the passes in this pass manager on the
461
901k
    // functions in this SCC.  However, we support iterative compilation in the
462
901k
    // case where a function pass devirtualizes a call to a function.  For
463
901k
    // example, it is very common for a function pass (often GVN or instcombine)
464
901k
    // to eliminate the addressing that feeds into a call.  With that improved
465
901k
    // information, we would like the call to be an inline candidate, infer
466
901k
    // mod-ref information etc.
467
901k
    //
468
901k
    // Because of this, we allow iteration up to a specified iteration count.
469
901k
    // This only happens in the case of a devirtualized call, so we only burn
470
901k
    // compile time in the case that we're making progress.  We also have a hard
471
901k
    // iteration count limit in case there is crazy code.
472
901k
    unsigned Iteration = 0;
473
901k
    bool DevirtualizedCall = false;
474
901k
    do {
475
901k
      DEBUG(if (Iteration)
476
901k
              dbgs() << "  SCCPASSMGR: Re-visiting SCC, iteration #"
477
901k
                     << Iteration << '\n');
478
901k
      DevirtualizedCall = false;
479
901k
      Changed |= RunAllPassesOnSCC(CurSCC, CG, DevirtualizedCall);
480
901k
    } while (
Iteration++ < MaxIterations && 901k
DevirtualizedCall901k
);
481
901k
    
482
901k
    if (DevirtualizedCall)
483
901k
      DEBUG(dbgs() << "  CGSCCPASSMGR: Stopped iteration after " << Iteration
484
901k
                   << " times, due to -max-cg-scc-iterations\n");
485
901k
486
901k
    MaxSCCIterations.updateMax(Iteration);
487
901k
  }
488
26.4k
  Changed |= doFinalization(CG);
489
26.4k
  return Changed;
490
26.4k
}
491
492
/// Initialize CG
493
26.4k
bool CGPassManager::doInitialization(CallGraph &CG) {
494
26.4k
  bool Changed = false;
495
125k
  for (unsigned i = 0, e = getNumContainedPasses(); 
i != e125k
;
++i98.8k
) {
496
98.8k
    if (PMDataManager *
PM98.8k
= getContainedPass(i)->getAsPMDataManager()) {
497
20.6k
      assert(PM->getPassManagerType() == PMT_FunctionPassManager &&
498
20.6k
             "Invalid CGPassManager member");
499
20.6k
      Changed |= ((FPPassManager*)PM)->doInitialization(CG.getModule());
500
98.8k
    } else {
501
78.1k
      Changed |= ((CallGraphSCCPass*)getContainedPass(i))->doInitialization(CG);
502
78.1k
    }
503
98.8k
  }
504
26.4k
  return Changed;
505
26.4k
}
506
507
/// Finalize CG
508
26.4k
bool CGPassManager::doFinalization(CallGraph &CG) {
509
26.4k
  bool Changed = false;
510
125k
  for (unsigned i = 0, e = getNumContainedPasses(); 
i != e125k
;
++i98.7k
) {
511
98.7k
    if (PMDataManager *
PM98.7k
= getContainedPass(i)->getAsPMDataManager()) {
512
20.6k
      assert(PM->getPassManagerType() == PMT_FunctionPassManager &&
513
20.6k
             "Invalid CGPassManager member");
514
20.6k
      Changed |= ((FPPassManager*)PM)->doFinalization(CG.getModule());
515
98.7k
    } else {
516
78.1k
      Changed |= ((CallGraphSCCPass*)getContainedPass(i))->doFinalization(CG);
517
78.1k
    }
518
98.7k
  }
519
26.4k
  return Changed;
520
26.4k
}
521
522
//===----------------------------------------------------------------------===//
523
// CallGraphSCC Implementation
524
//===----------------------------------------------------------------------===//
525
526
/// This informs the SCC and the pass manager that the specified
527
/// Old node has been deleted, and New is to be used in its place.
528
2.70k
void CallGraphSCC::ReplaceNode(CallGraphNode *Old, CallGraphNode *New) {
529
2.70k
  assert(Old != New && "Should not replace node with self");
530
2.70k
  for (unsigned i = 0; ; 
++i0
) {
531
2.70k
    assert(i != Nodes.size() && "Node not in SCC");
532
2.70k
    if (
Nodes[i] != Old2.70k
)
continue0
;
533
2.70k
    Nodes[i] = New;
534
2.70k
    break;
535
2.70k
  }
536
2.70k
  
537
2.70k
  // Update the active scc_iterator so that it doesn't contain dangling
538
2.70k
  // pointers to the old CallGraphNode.
539
2.70k
  scc_iterator<CallGraph*> *CGI = (scc_iterator<CallGraph*>*)Context;
540
2.70k
  CGI->ReplaceNode(Old, New);
541
2.70k
}
542
543
//===----------------------------------------------------------------------===//
544
// CallGraphSCCPass Implementation
545
//===----------------------------------------------------------------------===//
546
547
/// Assign pass manager to manage this pass.
548
void CallGraphSCCPass::assignPassManager(PMStack &PMS,
549
78.1k
                                         PassManagerType PreferredType) {
550
78.1k
  // Find CGPassManager 
551
79.6k
  while (!PMS.empty() &&
552
79.6k
         PMS.top()->getPassManagerType() > PMT_CallGraphPassManager)
553
1.48k
    PMS.pop();
554
78.1k
555
78.1k
  assert(!PMS.empty() && "Unable to handle Call Graph Pass");
556
78.1k
  CGPassManager *CGP;
557
78.1k
  
558
78.1k
  if (PMS.top()->getPassManagerType() == PMT_CallGraphPassManager)
559
51.6k
    CGP = (CGPassManager*)PMS.top();
560
26.4k
  else {
561
26.4k
    // Create new Call Graph SCC Pass Manager if it does not exist. 
562
26.4k
    assert(!PMS.empty() && "Unable to create Call Graph Pass Manager");
563
26.4k
    PMDataManager *PMD = PMS.top();
564
26.4k
565
26.4k
    // [1] Create new Call Graph Pass Manager
566
26.4k
    CGP = new CGPassManager();
567
26.4k
568
26.4k
    // [2] Set up new manager's top level manager
569
26.4k
    PMTopLevelManager *TPM = PMD->getTopLevelManager();
570
26.4k
    TPM->addIndirectPassManager(CGP);
571
26.4k
572
26.4k
    // [3] Assign manager to manage this new manager. This may create
573
26.4k
    // and push new managers into PMS
574
26.4k
    Pass *P = CGP;
575
26.4k
    TPM->schedulePass(P);
576
26.4k
577
26.4k
    // [4] Push new manager into PMS
578
26.4k
    PMS.push(CGP);
579
26.4k
  }
580
78.1k
581
78.1k
  CGP->add(this);
582
78.1k
}
583
584
/// For this class, we declare that we require and preserve the call graph.
585
/// If the derived class implements this method, it should
586
/// always explicitly call the implementation here.
587
76.6k
void CallGraphSCCPass::getAnalysisUsage(AnalysisUsage &AU) const {
588
76.6k
  AU.addRequired<CallGraphWrapperPass>();
589
76.6k
  AU.addPreserved<CallGraphWrapperPass>();
590
76.6k
}
591
592
//===----------------------------------------------------------------------===//
593
// PrintCallGraphPass Implementation
594
//===----------------------------------------------------------------------===//
595
596
namespace {
597
598
  /// PrintCallGraphPass - Print a Module corresponding to a call graph.
599
  ///
600
  class PrintCallGraphPass : public CallGraphSCCPass {
601
    std::string Banner;
602
    raw_ostream &OS;       // raw_ostream to print on.
603
    
604
  public:
605
    static char ID;
606
607
    PrintCallGraphPass(const std::string &B, raw_ostream &OS)
608
4
      : CallGraphSCCPass(ID), Banner(B), OS(OS) {}
609
610
4
    void getAnalysisUsage(AnalysisUsage &AU) const override {
611
4
      AU.setPreservesAll();
612
4
    }
613
614
8
    bool runOnSCC(CallGraphSCC &SCC) override {
615
8
      bool BannerPrinted = false;
616
8
      auto PrintBannerOnce = [&] () {
617
8
        if (BannerPrinted)
618
0
          return;
619
8
        OS << Banner;
620
8
        BannerPrinted = true;
621
8
        };
622
8
      for (CallGraphNode *CGN : SCC) {
623
8
        if (Function *
F8
= CGN->getFunction()) {
624
4
          if (
!F->isDeclaration() && 4
isFunctionInPrintList(F->getName())4
) {
625
4
            PrintBannerOnce();
626
4
            F->print(OS);
627
4
          }
628
8
        } else 
if (4
isFunctionInPrintList("*")4
) {
629
4
          PrintBannerOnce();
630
4
          OS << "\nPrinting <null> Function\n";
631
4
        }
632
8
      }
633
8
      return false;
634
8
    }
635
    
636
0
    StringRef getPassName() const override { return "Print CallGraph IR"; }
637
  };
638
  
639
} // end anonymous namespace.
640
641
char PrintCallGraphPass::ID = 0;
642
643
Pass *CallGraphSCCPass::createPrinterPass(raw_ostream &OS,
644
4
                                          const std::string &Banner) const {
645
4
  return new PrintCallGraphPass(Banner, OS);
646
4
}
647
648
3.01M
bool CallGraphSCCPass::skipSCC(CallGraphSCC &SCC) const {
649
3.01M
  return !SCC.getCallGraph().getModule()
650
3.01M
              .getContext()
651
3.01M
              .getOptBisect()
652
3.01M
              .shouldRunPass(this, SCC);
653
3.01M
}
654
655
char DummyCGSCCPass::ID = 0;
656
657
INITIALIZE_PASS(DummyCGSCCPass, "DummyCGSCCPass", "DummyCGSCCPass", false,
658
                false)