#define LLVM_ANALYSIS_CALLGRAPH_H
#include "llvm/ADT/GraphTraits.h"
+#include "llvm/ADT/OwningPtr.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/IR/Function.h"
#include "llvm/Pass.h"
class Module;
class CallGraphNode;
-/// \brief The basic data container for the call graph and the \c ModulePass
-/// which produces it.
+/// \brief The basic data container for the call graph of a \c Module of IR.
///
-/// This class exposes both the interface to the call graph container and the
-/// module pass which runs over a module of IR and produces the call graph.
+/// This class exposes both the interface to the call graph for a module of IR.
///
/// The core call graph itself can also be updated to reflect changes to the IR.
-class CallGraph : public ModulePass {
- Module *M;
+class CallGraph {
+ Module &M;
typedef std::map<const Function *, CallGraphNode *> FunctionMapTy;
void addToCallGraph(Function *F);
public:
- static char ID; // Class identification, replacement for typeinfo
+ CallGraph(Module &M);
+ ~CallGraph();
+
+ void print(raw_ostream &OS) const;
+ void dump() const;
typedef FunctionMapTy::iterator iterator;
typedef FunctionMapTy::const_iterator const_iterator;
/// \brief Returns the module the call graph corresponds to.
- Module &getModule() const { return *M; }
+ Module &getModule() const { return M; }
inline iterator begin() { return FunctionMap.begin(); }
inline iterator end() { return FunctionMap.end(); }
/// \brief Similar to operator[], but this will insert a new CallGraphNode for
/// \c F if one does not already exist.
CallGraphNode *getOrInsertFunction(const Function *F);
-
- CallGraph();
- virtual ~CallGraph() { releaseMemory(); }
-
- //===---------------------------------------------------------------------
- // Implementation of the ModulePass interface needed here.
- //
-
- virtual void getAnalysisUsage(AnalysisUsage &AU) const;
- virtual bool runOnModule(Module &M);
- virtual void releaseMemory();
-
- void print(raw_ostream &o, const Module *) const;
- void dump() const;
};
/// \brief A node in the call graph for a module.
void allReferencesDropped() { NumReferences = 0; }
};
+/// \brief The \c ModulePass which wraps up a \c CallGraph and the logic to
+/// build it.
+///
+/// This class exposes both the interface to the call graph container and the
+/// module pass which runs over a module of IR and produces the call graph. The
+/// call graph interface is entirelly a wrapper around a \c CallGraph object
+/// which is stored internally for each module.
+class CallGraphWrapperPass : public ModulePass {
+ OwningPtr<CallGraph> G;
+
+public:
+ static char ID; // Class identification, replacement for typeinfo
+
+ CallGraphWrapperPass();
+ virtual ~CallGraphWrapperPass();
+
+ /// \brief The internal \c CallGraph around which the rest of this interface
+ /// is wrapped.
+ const CallGraph &getCallGraph() const { return *G; }
+ CallGraph &getCallGraph() { return *G; }
+
+ typedef CallGraph::iterator iterator;
+ typedef CallGraph::const_iterator const_iterator;
+
+ /// \brief Returns the module the call graph corresponds to.
+ Module &getModule() const { return G->getModule(); }
+
+ inline iterator begin() { return G->begin(); }
+ inline iterator end() { return G->end(); }
+ inline const_iterator begin() const { return G->begin(); }
+ inline const_iterator end() const { return G->end(); }
+
+ /// \brief Returns the call graph node for the provided function.
+ inline const CallGraphNode *operator[](const Function *F) const {
+ return (*G)[F];
+ }
+
+ /// \brief Returns the call graph node for the provided function.
+ inline CallGraphNode *operator[](const Function *F) { return (*G)[F]; }
+
+ /// \brief Returns the \c CallGraphNode which is used to represent
+ /// undetermined calls into the callgraph.
+ CallGraphNode *getExternalCallingNode() const {
+ return G->getExternalCallingNode();
+ }
+
+ CallGraphNode *getCallsExternalNode() const {
+ return G->getCallsExternalNode();
+ }
+
+ /// \brief Returns the root/main method in the module, or some other root
+ /// node, such as the externalcallingnode.
+ CallGraphNode *getRoot() { return G->getRoot(); }
+ const CallGraphNode *getRoot() const { return G->getRoot(); }
+
+ //===---------------------------------------------------------------------
+ // Functions to keep a call graph up to date with a function that has been
+ // modified.
+ //
+
+ /// \brief Unlink the function from this module, returning it.
+ ///
+ /// Because this removes the function from the module, the call graph node is
+ /// destroyed. This is only valid if the function does not call any other
+ /// functions (ie, there are no edges in it's CGN). The easiest way to do
+ /// this is to dropAllReferences before calling this.
+ Function *removeFunctionFromModule(CallGraphNode *CGN) {
+ return G->removeFunctionFromModule(CGN);
+ }
+
+ /// \brief Similar to operator[], but this will insert a new CallGraphNode for
+ /// \c F if one does not already exist.
+ CallGraphNode *getOrInsertFunction(const Function *F) {
+ return G->getOrInsertFunction(F);
+ }
+
+ //===---------------------------------------------------------------------
+ // Implementation of the ModulePass interface needed here.
+ //
+
+ virtual void getAnalysisUsage(AnalysisUsage &AU) const;
+ virtual bool runOnModule(Module &M);
+ virtual void releaseMemory();
+
+ void print(raw_ostream &o, const Module *) const;
+ void dump() const;
+};
+
//===----------------------------------------------------------------------===//
// GraphTraits specializations for call graphs so that they can be treated as
// graphs by the generic graph algorithms.
void initializeSampleProfileLoaderPass(PassRegistry&);
void initializeBarrierNoopPass(PassRegistry&);
void initializeBasicAliasAnalysisPass(PassRegistry&);
-void initializeCallGraphPass(PassRegistry&);
+void initializeCallGraphWrapperPassPass(PassRegistry &);
void initializeBasicTTIPass(PassRegistry&);
void initializeBlockExtractorPassPass(PassRegistry&);
void initializeBlockFrequencyInfoPass(PassRegistry&);
#include "llvm/Support/raw_ostream.h"
using namespace llvm;
-CallGraph::CallGraph()
- : ModulePass(ID), Root(0), ExternalCallingNode(0), CallsExternalNode(0) {
- initializeCallGraphPass(*PassRegistry::getPassRegistry());
+//===----------------------------------------------------------------------===//
+// Implementations of the CallGraph class methods.
+//
+
+CallGraph::CallGraph(Module &M)
+ : M(M), Root(0), ExternalCallingNode(getOrInsertFunction(0)),
+ CallsExternalNode(new CallGraphNode(0)) {
+ // Add every function to the call graph.
+ for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
+ addToCallGraph(I);
+
+ // If we didn't find a main function, use the external call graph node
+ if (Root == 0)
+ Root = ExternalCallingNode;
+}
+
+CallGraph::~CallGraph() {
+ // CallsExternalNode is not in the function map, delete it explicitly.
+ CallsExternalNode->allReferencesDropped();
+ delete CallsExternalNode;
+
+// Reset all node's use counts to zero before deleting them to prevent an
+// assertion from firing.
+#ifndef NDEBUG
+ for (FunctionMapTy::iterator I = FunctionMap.begin(), E = FunctionMap.end();
+ I != E; ++I)
+ I->second->allReferencesDropped();
+#endif
+ for (FunctionMapTy::iterator I = FunctionMap.begin(), E = FunctionMap.end();
+ I != E; ++I)
+ delete I->second;
}
void CallGraph::addToCallGraph(Function *F) {
}
}
-void CallGraph::getAnalysisUsage(AnalysisUsage &AU) const {
- AU.setPreservesAll();
-}
-
-bool CallGraph::runOnModule(Module &M) {
- this->M = &M;
-
- ExternalCallingNode = getOrInsertFunction(0);
- assert(!CallsExternalNode);
- CallsExternalNode = new CallGraphNode(0);
- Root = 0;
-
- // Add every function to the call graph.
- for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
- addToCallGraph(I);
-
- // If we didn't find a main function, use the external call graph node
- if (Root == 0)
- Root = ExternalCallingNode;
-
- return false;
-}
-
-INITIALIZE_PASS(CallGraph, "basiccg", "CallGraph Construction", false, true)
-
-char CallGraph::ID = 0;
-
-void CallGraph::releaseMemory() {
- /// CallsExternalNode is not in the function map, delete it explicitly.
- if (CallsExternalNode) {
- CallsExternalNode->allReferencesDropped();
- delete CallsExternalNode;
- CallsExternalNode = 0;
- }
-
- if (FunctionMap.empty())
- return;
-
-// Reset all node's use counts to zero before deleting them to prevent an
-// assertion from firing.
-#ifndef NDEBUG
- for (FunctionMapTy::iterator I = FunctionMap.begin(), E = FunctionMap.end();
- I != E; ++I)
- I->second->allReferencesDropped();
-#endif
-
- for (FunctionMapTy::iterator I = FunctionMap.begin(), E = FunctionMap.end();
- I != E; ++I)
- delete I->second;
- FunctionMap.clear();
-}
-
-void CallGraph::print(raw_ostream &OS, const Module*) const {
+void CallGraph::print(raw_ostream &OS) const {
OS << "CallGraph Root is: ";
if (Function *F = Root->getFunction())
OS << F->getName() << "\n";
for (CallGraph::const_iterator I = begin(), E = end(); I != E; ++I)
I->second->print(OS);
}
+
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
-void CallGraph::dump() const {
- print(dbgs(), 0);
-}
+void CallGraph::dump() const { print(dbgs()); }
#endif
-//===----------------------------------------------------------------------===//
-// Implementations of public modification methods
-//
-
// removeFunctionFromModule - Unlink the function from this module, returning
// it. Because this removes the function from the module, the call graph node
// is destroyed. This is only valid if the function does not call any other
delete CGN; // Delete the call graph node for this func
FunctionMap.erase(F); // Remove the call graph node from the map
- M->getFunctionList().remove(F);
+ M.getFunctionList().remove(F);
return F;
}
// not already exist.
CallGraphNode *CallGraph::getOrInsertFunction(const Function *F) {
CallGraphNode *&CGN = FunctionMap[F];
- if (CGN) return CGN;
-
- assert((!F || F->getParent() == M) && "Function not in current module!");
+ if (CGN)
+ return CGN;
+
+ assert((!F || F->getParent() == &M) && "Function not in current module!");
return CGN = new CallGraphNode(const_cast<Function*>(F));
}
+//===----------------------------------------------------------------------===//
+// Implementations of the CallGraphNode class methods.
+//
+
void CallGraphNode::print(raw_ostream &OS) const {
if (Function *F = getFunction())
OS << "Call graph node for function: '" << F->getName() << "'";
}
}
+//===----------------------------------------------------------------------===//
+// Implementations of the CallGraphWrapperPass class methods.
+//
+
+CallGraphWrapperPass::CallGraphWrapperPass() : ModulePass(ID) {
+ initializeCallGraphWrapperPassPass(*PassRegistry::getPassRegistry());
+}
+
+CallGraphWrapperPass::~CallGraphWrapperPass() {}
+
+void CallGraphWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
+ AU.setPreservesAll();
+}
+
+bool CallGraphWrapperPass::runOnModule(Module &M) {
+ // All the real work is done in the constructor for the CallGraph.
+ G.reset(new CallGraph(M));
+ return false;
+}
+
+INITIALIZE_PASS(CallGraphWrapperPass, "basiccg", "CallGraph Construction",
+ false, true)
+
+char CallGraphWrapperPass::ID = 0;
+
+void CallGraphWrapperPass::releaseMemory() { G.reset(0); }
+
+void CallGraphWrapperPass::print(raw_ostream &OS, const Module *) const {
+ if (!G) {
+ OS << "No call graph has been built!\n";
+ return;
+ }
+
+ // Just delegate.
+ G->print(OS);
+}
+
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+void CallGraphWrapperPass::dump() const { print(dbgs(), 0); }
+#endif
+
// Enuse that users of CallGraph.h also link with this file
DEFINING_FILE_FOR(CallGraph)
/// 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.addRequired<CallGraphWrapperPass>();
Info.setPreservesAll();
}
/// 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 CGPassManager::runOnModule(Module &M) {
- CallGraph &CG = getAnalysis<CallGraph>();
+ CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
bool Changed = doInitialization(CG);
// Walk the callgraph in bottom-up SCC order.
/// the call graph. If the derived class implements this method, it should
/// always explicitly call the implementation here.
void CallGraphSCCPass::getAnalysisUsage(AnalysisUsage &AU) const {
- AU.addRequired<CallGraph>();
- AU.addPreserved<CallGraph>();
+ AU.addRequired<CallGraphWrapperPass>();
+ AU.addPreserved<CallGraphWrapperPass>();
}
}
};
+struct AnalysisCallGraphWrapperPassTraits {
+ static CallGraph *getGraph(CallGraphWrapperPass *P) {
+ return &P->getCallGraph();
+ }
+};
+
} // end llvm namespace
namespace {
-struct CallGraphViewer : public DOTGraphTraitsModuleViewer<CallGraph, true> {
+struct CallGraphViewer
+ : public DOTGraphTraitsModuleViewer<CallGraphWrapperPass, true, CallGraph *,
+ AnalysisCallGraphWrapperPassTraits> {
static char ID;
CallGraphViewer()
- : DOTGraphTraitsModuleViewer<CallGraph, true>("callgraph", ID) {
+ : DOTGraphTraitsModuleViewer<CallGraphWrapperPass, true, CallGraph *,
+ AnalysisCallGraphWrapperPassTraits>(
+ "callgraph", ID) {
initializeCallGraphViewerPass(*PassRegistry::getPassRegistry());
}
};
-struct CallGraphPrinter : public DOTGraphTraitsModulePrinter<CallGraph, true> {
+struct CallGraphPrinter : public DOTGraphTraitsModulePrinter<
+ CallGraphWrapperPass, true, CallGraph *,
+ AnalysisCallGraphWrapperPassTraits> {
static char ID;
CallGraphPrinter()
- : DOTGraphTraitsModulePrinter<CallGraph, true>("callgraph", ID) {
+ : DOTGraphTraitsModulePrinter<CallGraphWrapperPass, true, CallGraph *,
+ AnalysisCallGraphWrapperPassTraits>(
+ "callgraph", ID) {
initializeCallGraphPrinterPass(*PassRegistry::getPassRegistry());
}
};
}
bool runOnModule(Module &M) {
- InitializeAliasAnalysis(this); // set up super class
- AnalyzeGlobals(M); // find non-addr taken globals
- AnalyzeCallGraph(getAnalysis<CallGraph>(), M); // Propagate on CG
+ InitializeAliasAnalysis(this);
+
+ // Find non-addr taken globals.
+ AnalyzeGlobals(M);
+
+ // Propagate on CG.
+ AnalyzeCallGraph(getAnalysis<CallGraphWrapperPass>().getCallGraph(), M);
return false;
}
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AliasAnalysis::getAnalysisUsage(AU);
- AU.addRequired<CallGraph>();
+ AU.addRequired<CallGraphWrapperPass>();
AU.setPreservesAll(); // Does not transform code
}
INITIALIZE_AG_PASS_BEGIN(GlobalsModRef, AliasAnalysis,
"globalsmodref-aa", "Simple mod/ref analysis for globals",
false, true, false)
-INITIALIZE_PASS_DEPENDENCY(CallGraph)
+INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
INITIALIZE_AG_PASS_END(GlobalsModRef, AliasAnalysis,
"globalsmodref-aa", "Simple mod/ref analysis for globals",
false, true, false)
/// initializeIPA - Initialize all passes linked into the IPA library.
void llvm::initializeIPA(PassRegistry &Registry) {
- initializeCallGraphPass(Registry);
+ initializeCallGraphWrapperPassPass(Registry);
initializeCallGraphPrinterPass(Registry);
initializeCallGraphViewerPass(Registry);
initializeFindUsedTypesPass(Registry);
INITIALIZE_PASS_BEGIN(ArgPromotion, "argpromotion",
"Promote 'by reference' arguments to scalars", false, false)
INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
-INITIALIZE_PASS_DEPENDENCY(CallGraph)
+INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
INITIALIZE_PASS_END(ArgPromotion, "argpromotion",
"Promote 'by reference' arguments to scalars", false, false)
// Get the callgraph information that we need to update to reflect our
// changes.
- CallGraph &CG = getAnalysis<CallGraph>();
-
+ CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
+
// Get a new callgraph node for NF.
CallGraphNode *NF_CGN = CG.getOrInsertFunction(NF);
INITIALIZE_PASS_BEGIN(FunctionAttrs, "functionattrs",
"Deduce function attributes", false, false)
INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
-INITIALIZE_PASS_DEPENDENCY(CallGraph)
+INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo)
INITIALIZE_PASS_END(FunctionAttrs, "functionattrs",
"Deduce function attributes", false, false)
char AlwaysInliner::ID = 0;
INITIALIZE_PASS_BEGIN(AlwaysInliner, "always-inline",
"Inliner for always_inline functions", false, false)
-INITIALIZE_PASS_DEPENDENCY(CallGraph)
+INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
INITIALIZE_PASS_DEPENDENCY(InlineCostAnalysis)
INITIALIZE_PASS_END(AlwaysInliner, "always-inline",
"Inliner for always_inline functions", false, false)
char SimpleInliner::ID = 0;
INITIALIZE_PASS_BEGIN(SimpleInliner, "inline",
"Function Integration/Inlining", false, false)
-INITIALIZE_PASS_DEPENDENCY(CallGraph)
+INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
INITIALIZE_PASS_DEPENDENCY(InlineCostAnalysis)
INITIALIZE_PASS_END(SimpleInliner, "inline",
"Function Integration/Inlining", false, false)
}
bool Inliner::runOnSCC(CallGraphSCC &SCC) {
- CallGraph &CG = getAnalysis<CallGraph>();
+ CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
const DataLayout *TD = getAnalysisIfAvailable<DataLayout>();
const TargetLibraryInfo *TLI = getAnalysisIfAvailable<TargetLibraryInfo>();
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesCFG();
- AU.addPreserved<CallGraph>();
+ AU.addPreserved<CallGraphWrapperPass>();
}
};
} // end anonymous namespace
}
bool InternalizePass::runOnModule(Module &M) {
- CallGraph *CG = getAnalysisIfAvailable<CallGraph>();
+ CallGraphWrapperPass *CGPass = getAnalysisIfAvailable<CallGraphWrapperPass>();
+ CallGraph *CG = CGPass ? &CGPass->getCallGraph() : 0;
CallGraphNode *ExternalNode = CG ? CG->getExternalCallingNode() : 0;
bool Changed = false;
char PruneEH::ID = 0;
INITIALIZE_PASS_BEGIN(PruneEH, "prune-eh",
"Remove unused exception handling info", false, false)
-INITIALIZE_PASS_DEPENDENCY(CallGraph)
+INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
INITIALIZE_PASS_END(PruneEH, "prune-eh",
"Remove unused exception handling info", false, false)
bool PruneEH::runOnSCC(CallGraphSCC &SCC) {
SmallPtrSet<CallGraphNode *, 8> SCCNodes;
- CallGraph &CG = getAnalysis<CallGraph>();
+ CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
bool MadeChange = false;
// Fill SCCNodes with the elements of the SCC. Used for quickly
/// exist in the BB.
void PruneEH::DeleteBasicBlock(BasicBlock *BB) {
assert(pred_begin(BB) == pred_end(BB) && "BB is not dead!");
- CallGraph &CG = getAnalysis<CallGraph>();
+ CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
CallGraphNode *CGN = CG[BB->getParent()];
for (BasicBlock::iterator I = BB->end(), E = BB->begin(); I != E; ) {
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesAll();
- AU.addRequiredTransitive<CallGraph>();
+ AU.addRequiredTransitive<CallGraphWrapperPass>();
}
virtual bool runOnModule(Module &M) {
- getAnalysis<CallGraph>().print(errs(), &M);
+ getAnalysis<CallGraphWrapperPass>().print(errs(), &M);
return false;
}
};
// getAnalysisUsage - This pass requires the CallGraph.
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesAll();
- AU.addRequired<CallGraph>();
+ AU.addRequired<CallGraphWrapperPass>();
}
};
}
// run - Print out SCCs in the call graph for the specified module.
bool CallGraphSCC::runOnModule(Module &M) {
- CallGraphNode* rootNode = getAnalysis<CallGraph>().getRoot();
+ CallGraphNode *rootNode = getAnalysis<CallGraphWrapperPass>().getRoot();
unsigned sccNum = 0;
errs() << "SCCs for the program in PostOrder:";
for (scc_iterator<CallGraphNode*> SCCI = scc_begin(rootNode),
INITIALIZE_PASS(ModuleNDM, "mndm", "mndm", false, false)
INITIALIZE_PASS_BEGIN(CGPass, "cgp","cgp", false, false)
-INITIALIZE_PASS_DEPENDENCY(CallGraph)
+INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
INITIALIZE_PASS_END(CGPass, "cgp","cgp", false, false)
INITIALIZE_PASS(FPass, "fp","fp", false, false)
INITIALIZE_PASS_BEGIN(LPass, "lp","lp", false, false)
projects / oota-llvm.git / commitdiff