path: root/lib/Analysis/IPA/CallGraphSCCPass.cpp

//===- CallGraphSCCPass.cpp - Pass that operates BU on call graph ---------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// 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.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "cgscc-passmgr"
#include "llvm/CallGraphSCCPass.h"
#include "llvm/IntrinsicInst.h"
#include "llvm/Function.h"
#include "llvm/PassManagers.h"
#include "llvm/Analysis/CallGraph.h"
#include "llvm/ADT/SCCIterator.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/Timer.h"
#include "llvm/Support/raw_ostream.h"
using namespace llvm;

static cl::opt<unsigned> 
MaxIterations("max-cg-scc-iterations", cl::ReallyHidden, cl::init(4));

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

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

namespace {

class CGPassManager : public ModulePass, public PMDataManager {
public:
  static char ID;
  explicit CGPassManager() 
    : ModulePass(ID), PMDataManager() { }

  /// run - 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 runOnModule(Module &M);

  bool doInitialization(CallGraph &CG);
  bool doFinalization(CallGraph &CG);

  /// Pass Manager itself does not invalidate any analysis info.
  void getAnalysisUsage(AnalysisUsage &Info) const {
    // CGPassManager walks SCC and it needs CallGraph.
    Info.addRequired<CallGraph>();
    Info.setPreservesAll();
  }

  virtual const char *getPassName() const {
    return "CallGraph Pass Manager";
  }

  virtual PMDataManager *getAsPMDataManager() { return this; }
  virtual Pass *getAsPass() { return this; }

  // Print passes managed by this manager
  void dumpPassStructure(unsigned Offset) {
    errs().indent(Offset*2) << "Call Graph SCC Pass Manager\n";
    for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
      Pass *P = getContainedPass(Index);
      P->dumpPassStructure(Offset + 1);
      dumpLastUses(P, Offset+1);
    }
  }

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

  virtual PassManagerType getPassManagerType() const { 
    return PMT_CallGraphPassManager; 
  }
  
private:
  bool RunAllPassesOnSCC(CallGraphSCC &CurSCC, CallGraph &CG,
                         bool &DevirtualizedCall);
  
  bool RunPassOnSCC(Pass *P, CallGraphSCC &CurSCC,
                    CallGraph &CG, bool &CallGraphUpToDate,
                    bool &DevirtualizedCall);
  bool RefreshCallGraph(CallGraphSCC &CurSCC, CallGraph &CG,
                        bool IsCheckingMode);
};

} // end anonymous namespace.

char CGPassManager::ID = 0;


bool CGPassManager::RunPassOnSCC(Pass *P, CallGraphSCC &CurSCC,
                                 CallGraph &CG, bool &CallGraphUpToDate,
                                 bool &DevirtualizedCall) {
  bool Changed = false;
  PMDataManager *PM = P->getAsPMDataManager();

  if (PM == 0) {
    CallGraphSCCPass *CGSP = (CallGraphSCCPass*)P;
    if (!CallGraphUpToDate) {
      DevirtualizedCall |= RefreshCallGraph(CurSCC, CG, false);
      CallGraphUpToDate = true;
    }

    {
      TimeRegion PassTimer(getPassTimer(CGSP));
      Changed = CGSP->runOnSCC(CurSCC);
    }
    
    // After the CGSCCPass is done, when assertions are enabled, use
    // RefreshCallGraph to verify that the callgraph was correctly updated.
#ifndef NDEBUG
    if (Changed)
      RefreshCallGraph(CurSCC, CG, true);
#endif
    
    return Changed;
  }
  
  
  assert(PM->getPassManagerType() == PMT_FunctionPassManager &&
         "Invalid CGPassManager member");
  FPPassManager *FPP = (FPPassManager*)P;
  
  // Run pass P on all functions in the current SCC.
  for (CallGraphSCC::iterator I = CurSCC.begin(), E = CurSCC.end();
       I != E; ++I) {
    if (Function *F = (*I)->getFunction()) {
      dumpPassInfo(P, EXECUTION_MSG, ON_FUNCTION_MSG, F->getName());
      TimeRegion PassTimer(getPassTimer(FPP));
      Changed |= FPP->runOnFunction(*F);
    }
  }
  
  // The function pass(es) modified the IR, they may have clobbered the
  // callgraph.
  if (Changed && CallGraphUpToDate) {
    DEBUG(dbgs() << "CGSCCPASSMGR: Pass Dirtied SCC: "
                 << P->getPassName() << '\n');
    CallGraphUpToDate = false;
  }
  return Changed;
}


/// RefreshCallGraph - 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(CallGraphSCC &CurSCC,
                                     CallGraph &CG, bool CheckingMode) {
  DenseMap<Value*, CallGraphNode*> CallSites;
  
  DEBUG(dbgs() << "CGSCCPASSMGR: Refreshing SCC with " << CurSCC.size()
               << " nodes:\n";
        for (CallGraphSCC::iterator I = CurSCC.begin(), E = CurSCC.end();
             I != E; ++I)
          (*I)->dump();
        );

  bool MadeChange = false;
  bool DevirtualizedCall = false;
  
  // Scan all functions in the SCC.
  unsigned FunctionNo = 0;
  for (CallGraphSCC::iterator SCCIdx = CurSCC.begin(), E = CurSCC.end();
       SCCIdx != E; ++SCCIdx, ++FunctionNo) {
    CallGraphNode *CGN = *SCCIdx;
    Function *F = CGN->getFunction();
    if (F == 0 || F->isDeclaration()) continue;
    
    // Walk the function body looking for call sites.  Sync up the call sites in
    // CGN with those actually in the function.

    // Keep track of the number of direct and indirect calls that were
    // invalidated and removed.
    unsigned NumDirectRemoved = 0, NumIndirectRemoved = 0;
    
    // Get the set of call sites currently in the function.
    for (CallGraphNode::iterator I = CGN->begin(), E = CGN->end(); I != E; ) {
      // If this call site is null, then the function pass deleted the call
      // entirely and the WeakVH nulled it out.  
      if (I->first<