CallGraphSCCPass.cpp [plain text]
#include "llvm/Analysis/CallGraphSCCPass.h"
#include "llvm/ADT/SCCIterator.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/CallGraph.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/LegacyPassManagers.h"
#include "llvm/IR/LLVMContext.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;
#define DEBUG_TYPE "cgscc-passmgr"
static cl::opt<unsigned>
MaxIterations("max-cg-scc-iterations", cl::ReallyHidden, cl::init(4));
STATISTIC(MaxSCCIterations, "Maximum CGSCCPassMgr iterations on one SCC");
namespace {
class CGPassManager : public ModulePass, public PMDataManager {
public:
static char ID;
explicit CGPassManager()
: ModulePass(ID), PMDataManager() { }
bool runOnModule(Module &M) override;
using ModulePass::doInitialization;
using ModulePass::doFinalization;
bool doInitialization(CallGraph &CG);
bool doFinalization(CallGraph &CG);
void getAnalysisUsage(AnalysisUsage &Info) const override {
Info.addRequired<CallGraphWrapperPass>();
Info.setPreservesAll();
}
const char *getPassName() const override {
return "CallGraph Pass Manager";
}
PMDataManager *getAsPMDataManager() override { return this; }
Pass *getAsPass() override { return this; }
void dumpPassStructure(unsigned Offset) override {
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]);
}
PassManagerType getPassManagerType() const override {
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);
};
}
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) {
CallGraphSCCPass *CGSP = (CallGraphSCCPass*)P;
if (!CallGraphUpToDate) {
DevirtualizedCall |= RefreshCallGraph(CurSCC, CG, false);
CallGraphUpToDate = true;
}
{
TimeRegion PassTimer(getPassTimer(CGSP));
Changed = CGSP->runOnSCC(CurSCC);
}
#ifndef NDEBUG
if (Changed)
RefreshCallGraph(CurSCC, CG, true);
#endif
return Changed;
}
assert(PM->getPassManagerType() == PMT_FunctionPassManager &&
"Invalid CGPassManager member");
FPPassManager *FPP = (FPPassManager*)P;
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);
}
F->getContext().yield();
}
}
if (Changed && CallGraphUpToDate) {
DEBUG(dbgs() << "CGSCCPASSMGR: Pass Dirtied SCC: "
<< P->getPassName() << '\n');
CallGraphUpToDate = false;
}
return Changed;
}
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;
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 || F->isDeclaration()) continue;
unsigned NumDirectRemoved = 0, NumIndirectRemoved = 0;
for (CallGraphNode::iterator I = CGN->begin(), E = CGN->end(); I != E; ) {
if (!I->first ||
CallSites.count(I->first) ||
!CallSite(I->first)) {
assert(!CheckingMode &&
"CallGraphSCCPass did not update the CallGraph correctly!");
if (!I->second->getFunction())
++NumIndirectRemoved;
else
++NumDirectRemoved;
bool WasLast = I + 1 == E;
CGN->removeCallEdge(I);
if (WasLast)
break;
E = CGN->end();
continue;
}
assert(!CallSites.count(I->first) &&
"Call site occurs in node multiple times");
CallSite CS(I->first);
if (CS) {
Function *Callee = CS.getCalledFunction();
if (!Callee || !(Callee->isIntrinsic()))
CallSites.insert(std::make_pair(I->first, I->second));
}
++I;
}
unsigned NumDirectAdded = 0, NumIndirectAdded = 0;
for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
CallSite CS(cast<Value>(I));
if (!CS) continue;
Function *Callee = CS.getCalledFunction();
if (Callee && Callee->isIntrinsic()) continue;
DenseMap<Value*, CallGraphNode*>::iterator ExistingIt =
CallSites.find(CS.getInstruction());
if (ExistingIt != CallSites.end()) {
CallGraphNode *ExistingNode = ExistingIt->second;
CallSites.erase(ExistingIt);
if (ExistingNode->getFunction() == CS.getCalledFunction())
continue;
if (CheckingMode && CS.getCalledFunction() &&
ExistingNode->getFunction() == nullptr)
continue;
assert(!CheckingMode &&
"CallGraphSCCPass did not update the CallGraph correctly!");
CallGraphNode *CalleeNode;
if (Function *Callee = CS.getCalledFunction()) {
CalleeNode = CG.getOrInsertFunction(Callee);
if (!ExistingNode->getFunction()) {
DevirtualizedCall = true;
DEBUG(dbgs() << " CGSCCPASSMGR: Devirtualized call to '"
<< Callee->getName() << "'\n");
}
} else {
CalleeNode = CG.getCallsExternalNode();
}
CGN->replaceCallEdge(CS, CS, CalleeNode);
MadeChange = true;
continue;
}
assert(!CheckingMode &&
"CallGraphSCCPass did not update the CallGraph correctly!");
CallGraphNode *CalleeNode;
if (Function *Callee = CS.getCalledFunction()) {
CalleeNode = CG.getOrInsertFunction(Callee);
++NumDirectAdded;
} else {
CalleeNode = CG.getCallsExternalNode();
++NumIndirectAdded;
}
CGN->addCalledFunction(CS, CalleeNode);
MadeChange = true;
}
if (NumIndirectRemoved > NumIndirectAdded &&
NumDirectRemoved < NumDirectAdded)
DevirtualizedCall = true;
assert(CallSites.empty() && "Dangling pointers found in call sites map");
if ((FunctionNo & 15) == 15)
CallSites.clear();
}
DEBUG(if (MadeChange) {
dbgs() << "CGSCCPASSMGR: Refreshed SCC is now:\n";
for (CallGraphSCC::iterator I = CurSCC.begin(), E = CurSCC.end();
I != E; ++I)
(*I)->dump();
if (DevirtualizedCall)
dbgs() << "CGSCCPASSMGR: Refresh devirtualized a call!\n";
} else {
dbgs() << "CGSCCPASSMGR: SCC Refresh didn't change call graph.\n";
}
);
(void)MadeChange;
return DevirtualizedCall;
}
bool CGPassManager::RunAllPassesOnSCC(CallGraphSCC &CurSCC, CallGraph &CG,
bool &DevirtualizedCall) {
bool Changed = false;
bool CallGraphUpToDate = true;
for (unsigned PassNo = 0, e = getNumContainedPasses();
PassNo != e; ++PassNo) {
Pass *P = getContainedPass(PassNo);
if (isPassDebuggingExecutionsOrMore()) {
std::string Functions;
#ifndef NDEBUG
raw_string_ostream OS(Functions);
for (CallGraphSCC::iterator I = CurSCC.begin(), E = CurSCC.end();
I != E; ++I) {
if (I != CurSCC.begin()) OS << ", ";
(*I)->print(OS);
}
OS.flush();
#endif
dumpPassInfo(P, EXECUTION_MSG, ON_CG_MSG, Functions);
}
dumpRequiredSet(P);
initializeAnalysisImpl(P);
Changed |= RunPassOnSCC(P, CurSCC, CG,
CallGraphUpToDate, DevirtualizedCall);
if (Changed)
dumpPassInfo(P, MODIFICATION_MSG, ON_CG_MSG, "");
dumpPreservedSet(P);
verifyPreservedAnalysis(P);
removeNotPreservedAnalysis(P);
recordAvailableAnalysis(P);
removeDeadPasses(P, "", ON_CG_MSG);
}
if (!CallGraphUpToDate)
DevirtualizedCall |= RefreshCallGraph(CurSCC, CG, false);
return Changed;
}
bool CGPassManager::runOnModule(Module &M) {
CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
bool Changed = doInitialization(CG);
scc_iterator<CallGraph*> CGI = scc_begin(&CG);
CallGraphSCC CurSCC(&CGI);
while (!CGI.isAtEnd()) {
const std::vector<CallGraphNode *> &NodeVec = *CGI;
CurSCC.initialize(NodeVec.data(), NodeVec.data() + NodeVec.size());
++CGI;
unsigned Iteration = 0;
bool DevirtualizedCall = false;
do {
DEBUG(if (Iteration)
dbgs() << " SCCPASSMGR: Re-visiting SCC, iteration #"
<< Iteration << '\n');
DevirtualizedCall = false;
Changed |= RunAllPassesOnSCC(CurSCC, CG, DevirtualizedCall);
} while (Iteration++ < MaxIterations && DevirtualizedCall);
if (DevirtualizedCall)
DEBUG(dbgs() << " CGSCCPASSMGR: Stopped iteration after " << Iteration
<< " times, due to -max-cg-scc-iterations\n");
if (Iteration > MaxSCCIterations)
MaxSCCIterations = Iteration;
}
Changed |= doFinalization(CG);
return Changed;
}
bool CGPassManager::doInitialization(CallGraph &CG) {
bool Changed = false;
for (unsigned i = 0, e = getNumContainedPasses(); i != e; ++i) {
if (PMDataManager *PM = getContainedPass(i)->getAsPMDataManager()) {
assert(PM->getPassManagerType() == PMT_FunctionPassManager &&
"Invalid CGPassManager member");
Changed |= ((FPPassManager*)PM)->doInitialization(CG.getModule());
} else {
Changed |= ((CallGraphSCCPass*)getContainedPass(i))->doInitialization(CG);
}
}
return Changed;
}
bool CGPassManager::doFinalization(CallGraph &CG) {
bool Changed = false;
for (unsigned i = 0, e = getNumContainedPasses(); i != e; ++i) {
if (PMDataManager *PM = getContainedPass(i)->getAsPMDataManager()) {
assert(PM->getPassManagerType() == PMT_FunctionPassManager &&
"Invalid CGPassManager member");
Changed |= ((FPPassManager*)PM)->doFinalization(CG.getModule());
} else {
Changed |= ((CallGraphSCCPass*)getContainedPass(i))->doFinalization(CG);
}
}
return Changed;
}
void CallGraphSCC::ReplaceNode(CallGraphNode *Old, CallGraphNode *New) {
assert(Old != New && "Should not replace node with self");
for (unsigned i = 0; ; ++i) {
assert(i != Nodes.size() && "Node not in SCC");
if (Nodes[i] != Old) continue;
Nodes[i] = New;
break;
}
scc_iterator<CallGraph*> *CGI = (scc_iterator<CallGraph*>*)Context;
CGI->ReplaceNode(Old, New);
}
void CallGraphSCCPass::assignPassManager(PMStack &PMS,
PassManagerType PreferredType) {
while (!PMS.empty() &&
PMS.top()->getPassManagerType() > PMT_CallGraphPassManager)
PMS.pop();
assert(!PMS.empty() && "Unable to handle Call Graph Pass");
CGPassManager *CGP;
if (PMS.top()->getPassManagerType() == PMT_CallGraphPassManager)
CGP = (CGPassManager*)PMS.top();
else {
assert(!PMS.empty() && "Unable to create Call Graph Pass Manager");
PMDataManager *PMD = PMS.top();
CGP = new CGPassManager();
PMTopLevelManager *TPM = PMD->getTopLevelManager();
TPM->addIndirectPassManager(CGP);
Pass *P = CGP;
TPM->schedulePass(P);
PMS.push(CGP);
}
CGP->add(this);
}
void CallGraphSCCPass::getAnalysisUsage(AnalysisUsage &AU) const {
AU.addRequired<CallGraphWrapperPass>();
AU.addPreserved<CallGraphWrapperPass>();
}
namespace {
class PrintCallGraphPass : public CallGraphSCCPass {
std::string Banner;
raw_ostream &Out;
public:
static char ID;
PrintCallGraphPass(const std::string &B, raw_ostream &o)
: CallGraphSCCPass(ID), Banner(B), Out(o) {}
void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.setPreservesAll();
}
bool runOnSCC(CallGraphSCC &SCC) override {
Out << Banner;
for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
if ((*I)->getFunction())
(*I)->getFunction()->print(Out);
else
Out << "\nPrinting <null> Function\n";
}
return false;
}
};
}
char PrintCallGraphPass::ID = 0;
Pass *CallGraphSCCPass::createPrinterPass(raw_ostream &O,
const std::string &Banner) const {
return new PrintCallGraphPass(Banner, O);
}