From 632cd52162e0fa95bb3527af71476babe6052353 Mon Sep 17 00:00:00 2001 From: Andrew Lenharth Date: Mon, 29 May 2006 22:58:38 +0000 Subject: [PATCH] Since there was interest on the mailing list, this is a utility pass that uses DSA to make find targets of calls. It provides a very convinient interface to DSA results to do things with indirect calls, such as write a devirtualizer (which I have and may commit one of these days). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@28545 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/CallTargets.h | 54 ++++++++++ include/llvm/Analysis/LinkAllAnalyses.h | 2 + lib/Analysis/IPA/CallTargets.cpp | 125 ++++++++++++++++++++++++ 3 files changed, 181 insertions(+) create mode 100644 include/llvm/Analysis/CallTargets.h create mode 100644 lib/Analysis/IPA/CallTargets.cpp diff --git a/include/llvm/Analysis/CallTargets.h b/include/llvm/Analysis/CallTargets.h new file mode 100644 index 00000000000..d4f56e8c801 --- /dev/null +++ b/include/llvm/Analysis/CallTargets.h @@ -0,0 +1,54 @@ +//=- llvm/Analysis/CallTargets.h - Resolve Indirect Call Targets --*- C++ -*-=// +// +// The LLVM Compiler Infrastructure +// +// This file was developed by the LLVM research group and is distributed under +// the University of Illinois Open Source License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass uses DSA to map targets of all calls, and reports on if it +// thinks it knows all targets of a given call. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_CALLTARGETS_H +#define LLVM_ANALYSIS_CALLTARGETS_H + +#include "llvm/Pass.h" +#include "llvm/Support/CallSite.h" + +#include +#include + +namespace llvm { + + class CallTargetFinder : public ModulePass { + std::map > IndMap; + std::set CompleteSites; + std::list AllSites; + + void findIndTargets(Module &M); + public: + virtual bool runOnModule(Module &M); + + virtual void getAnalysisUsage(AnalysisUsage &AU) const; + + virtual void print(std::ostream &O, const Module *M) const; + + // Given a CallSite, get an iterator of callees + std::vector::iterator begin(CallSite cs); + std::vector::iterator end(CallSite cs); + + // Iterate over CallSites in program + std::list::iterator cs_begin(); + std::list::iterator cs_end(); + + // Do we think we have complete knowledge of this site? + // That is, do we think there are no missing callees + bool isComplete(CallSite cs) const; + }; + +} + +#endif diff --git a/include/llvm/Analysis/LinkAllAnalyses.h b/include/llvm/Analysis/LinkAllAnalyses.h index cac2abdc4c5..0be53648fbd 100644 --- a/include/llvm/Analysis/LinkAllAnalyses.h +++ b/include/llvm/Analysis/LinkAllAnalyses.h @@ -22,6 +22,7 @@ #include "llvm/Analysis/Passes.h" #include "llvm/Analysis/ScalarEvolution.h" #include "llvm/Analysis/DataStructure/DataStructure.h" +#include "llvm/Analysis/CallTargets.h" #include "llvm/Function.h" #include @@ -50,6 +51,7 @@ namespace { (void)new llvm::PostDominatorSet(); (void)new llvm::FindUsedTypes(); (void)new llvm::ScalarEvolution(); + (void)new llvm::CallTargetFinder(); ((llvm::Function*)0)->viewCFGOnly(); llvm::AliasSetTracker X(*(llvm::AliasAnalysis*)0); X.add((llvm::Value*)0, 0); // for -print-alias-sets diff --git a/lib/Analysis/IPA/CallTargets.cpp b/lib/Analysis/IPA/CallTargets.cpp new file mode 100644 index 00000000000..10fe26e7063 --- /dev/null +++ b/lib/Analysis/IPA/CallTargets.cpp @@ -0,0 +1,125 @@ +//=- lib/Analysis/IPA/CallTargets.cpp - Resolve Call Targets --*- C++ -*-=====// +// +// The LLVM Compiler Infrastructure +// +// This file was developed by the LLVM research group and is distributed under +// the University of Illinois Open Source License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass uses DSA to map targets of all calls, and reports on if it +// thinks it knows all targets of a given call. +// +// Loop over all callsites, and lookup the DSNode for that site. Pull the +// Functions from the node as callees. +// This is essentially a utility pass to simplify later passes that only depend +// on call sites and callees to operate (such as a devirtualizer). +// +//===----------------------------------------------------------------------===// + +#include "llvm/Module.h" +#include "llvm/Instructions.h" +#include "llvm/Analysis/DataStructure/DataStructure.h" +#include "llvm/Analysis/DataStructure/DSGraph.h" +#include "llvm/Analysis/CallTargets.h" +#include "llvm/ADT/Statistic.h" +#include +#include "llvm/Constants.h" + +using namespace llvm; + +namespace { + Statistic<> DirCall("calltarget", "Number of direct calls"); + Statistic<> IndCall("calltarget", "Number of indirect calls"); + Statistic<> CompleteInd("calltarget", "Number of complete indirect calls"); + Statistic<> CompleteEmpty("calltarget", "Number of complete empty calls"); + + RegisterAnalysis X("calltarget", "Find Call Targets (uses DSA)"); +} + +void CallTargetFinder::findIndTargets(Module &M) +{ + TDDataStructures* T = &getAnalysis(); + for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) + if (!I->isExternal()) + for (Function::iterator F = I->begin(), FE = I->end(); F != FE; ++F) + for (BasicBlock::iterator B = F->begin(), BE = F->end(); B != BE; ++B) + if (isa(B) || isa(B)) { + CallSite cs = CallSite::get(B); + AllSites.push_back(cs); + if (!cs.getCalledFunction()) { + IndCall++; + DSNode* N = T->getDSGraph(*cs.getCaller()) + .getNodeForValue(cs.getCalledValue()).getNode(); + N->addFullFunctionList(IndMap[cs]); + if (N->isComplete() && IndMap[cs].size()) { + CompleteSites.insert(cs); + ++CompleteInd; + } + if (N->isComplete() && !IndMap[cs].size()) { + ++CompleteEmpty; + std::cerr << "Call site empty: '" << cs.getInstruction()->getName() + << "' In '" << cs.getInstruction()->getParent()->getParent()->getName() + << "'\n"; + } + } else { + ++DirCall; + IndMap[cs].push_back(cs.getCalledFunction()); + CompleteSites.insert(cs); + } + } +} + +void CallTargetFinder::print(std::ostream &O, const Module *M) const +{ + return; + O << "[* = incomplete] CS: func list\n"; + for (std::map >::const_iterator ii = IndMap.begin(), + ee = IndMap.end(); ii != ee; ++ii) { + if (!ii->first.getCalledFunction()) { //only print indirect + if (!isComplete(ii->first)) { + O << "* "; + CallSite cs = ii->first; + cs.getInstruction()->dump(); + O << cs.getInstruction()->getParent()->getParent()->getName() << " " + << cs.getInstruction()->getName() << " "; + } + O << ii->first.getInstruction() << ":"; + for (std::vector::const_iterator i = ii->second.begin(), + e = ii->second.end(); i != e; ++i) { + O << " " << (*i)->getName(); + } + O << "\n"; + } + } +} + +bool CallTargetFinder::runOnModule(Module &M) { + findIndTargets(M); + return false; +} + +void CallTargetFinder::getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesAll(); + AU.addRequired(); +} + +std::vector::iterator CallTargetFinder::begin(CallSite cs) { + return IndMap[cs].begin(); +} + +std::vector::iterator CallTargetFinder::end(CallSite cs) { + return IndMap[cs].end(); +} + +bool CallTargetFinder::isComplete(CallSite cs) const { + return CompleteSites.find(cs) != CompleteSites.end(); +} + +std::list::iterator CallTargetFinder::cs_begin() { + return AllSites.begin(); +} + +std::list::iterator CallTargetFinder::cs_end() { + return AllSites.end(); +} -- 2.34.1