LCOV - code coverage report
Current view: top level - lib/Analysis - CallGraphSCCPass.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 170 173 98.3 %
Date: 2018-10-17 09:37:48 Functions: 21 22 95.5 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13