llvm/llvm/lib/Analysis/CallGraphSCCPass.cpp

//===- CallGraphSCCPass.cpp - Pass that operates BU on call graph ---------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file implements the CallGraphSCCPass class, which is used for passes
// which are implemented as bottom-up traversals on the call graph.  Because
// there may be cycles in the call graph, passes of this type operate on the
// call-graph in SCC order: that is, they process function bottom-up, except for
// recursive functions, which they process all at once.
//
//===----------------------------------------------------------------------===//

#include "llvm/Analysis/CallGraphSCCPass.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SCCIterator.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/Analysis/CallGraph.h"
#include "llvm/IR/AbstractCallSite.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/Intrinsics.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/LegacyPassManagers.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/OptBisect.h"
#include "llvm/IR/PassTimingInfo.h"
#include "llvm/IR/PrintPasses.h"
#include "llvm/Pass.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/Timer.h"
#include "llvm/Support/raw_ostream.h"
#include <cassert>
#include <string>
#include <utility>
#include <vector>

usingnamespacellvm;

#define DEBUG_TYPE …

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

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

//===----------------------------------------------------------------------===//
// CGPassManager
//
/// CGPassManager manages FPPassManagers and CallGraphSCCPasses.

namespace {

class CGPassManager : public ModulePass, public PMDataManager { … };

} // end anonymous namespace.

char CGPassManager::ID = …;

bool CGPassManager::RunPassOnSCC(Pass *P, CallGraphSCC &CurSCC,
                                 CallGraph &CG, bool &CallGraphUpToDate,
                                 bool &DevirtualizedCall) { … }

/// Scan the functions in the specified CFG and resync the
/// callgraph with the call sites found in it.  This is used after
/// FunctionPasses have potentially munged the callgraph, and can be used after
/// CallGraphSCC passes to verify that they correctly updated the callgraph.
///
/// This function returns true if it devirtualized an existing function call,
/// meaning it turned an indirect call into a direct call.  This happens when
/// a function pass like GVN optimizes away stuff feeding the indirect call.
/// This never happens in checking mode.
bool CGPassManager::RefreshCallGraph(const CallGraphSCC &CurSCC, CallGraph &CG,
                                     bool CheckingMode) { … }

/// Execute the body of the entire pass manager on the specified SCC.
/// This keeps track of whether a function pass devirtualizes
/// any calls and returns it in DevirtualizedCall.
bool CGPassManager::RunAllPassesOnSCC(CallGraphSCC &CurSCC, CallGraph &CG,
                                      bool &DevirtualizedCall) { … }

/// Execute all of the passes scheduled for execution.  Keep track of
/// whether any of the passes modifies the module, and if so, return true.
bool CGPassManager::runOnModule(Module &M) { … }

/// Initialize CG
bool CGPassManager::doInitialization(CallGraph &CG) { … }

/// Finalize CG
bool CGPassManager::doFinalization(CallGraph &CG) { … }

//===----------------------------------------------------------------------===//
// CallGraphSCC Implementation
//===----------------------------------------------------------------------===//

/// This informs the SCC and the pass manager that the specified
/// Old node has been deleted, and New is to be used in its place.
void CallGraphSCC::ReplaceNode(CallGraphNode *Old, CallGraphNode *New) { … }

void CallGraphSCC::DeleteNode(CallGraphNode *Old) { … }

//===----------------------------------------------------------------------===//
// CallGraphSCCPass Implementation
//===----------------------------------------------------------------------===//

/// Assign pass manager to manage this pass.
void CallGraphSCCPass::assignPassManager(PMStack &PMS,
                                         PassManagerType PreferredType) { … }

/// For this class, we declare that we require and preserve the call graph.
/// If the derived class implements this method, it should
/// always explicitly call the implementation here.
void CallGraphSCCPass::getAnalysisUsage(AnalysisUsage &AU) const { … }

//===----------------------------------------------------------------------===//
// PrintCallGraphPass Implementation
//===----------------------------------------------------------------------===//

namespace {

  /// PrintCallGraphPass - Print a Module corresponding to a call graph.
  ///
  class PrintCallGraphPass : public CallGraphSCCPass { … };

} // end anonymous namespace.

char PrintCallGraphPass::ID = …;

Pass *CallGraphSCCPass::createPrinterPass(raw_ostream &OS,
                                          const std::string &Banner) const { … }

static std::string getDescription(const CallGraphSCC &SCC) { … }

bool CallGraphSCCPass::skipSCC(CallGraphSCC &SCC) const { … }

char DummyCGSCCPass::ID = …;

INITIALIZE_PASS(…)