Changes in directory llvm/lib/Analysis/IPA:
CallGraph.cpp updated: 1.48 -> 1.49 --- Log message: Separate the call graph implementation from its interface. This implements the rough idea sketched out in http://nondot.org/sabre/LLVMNotes/CallGraphClass.txt, allowing new spiffy implementations of the callgraph interface to be built. Many thanks to Saem Ghani for contributing this! --- Diffs of the changes: (+179 -106) CallGraph.cpp | 285 ++++++++++++++++++++++++++++++++++++---------------------- 1 files changed, 179 insertions(+), 106 deletions(-) Index: llvm/lib/Analysis/IPA/CallGraph.cpp diff -u llvm/lib/Analysis/IPA/CallGraph.cpp:1.48 llvm/lib/Analysis/IPA/CallGraph.cpp:1.49 --- llvm/lib/Analysis/IPA/CallGraph.cpp:1.48 Thu Apr 21 16:08:44 2005 +++ llvm/lib/Analysis/IPA/CallGraph.cpp Thu Dec 22 00:07:52 2005 @@ -7,7 +7,8 @@ // //===----------------------------------------------------------------------===// // -// This file implements the CallGraph class. +// This file implements the CallGraph class and provides the BasicCallGraph +// default implementation. // //===----------------------------------------------------------------------===// @@ -15,22 +16,10 @@ #include "llvm/Module.h" #include "llvm/Instructions.h" #include "llvm/Support/CallSite.h" -#include "llvm/ADT/STLExtras.h" #include <iostream> using namespace llvm; -static RegisterAnalysis<CallGraph> X("callgraph", "Call Graph Construction"); - -// getNodeFor - Return the node for the specified function or create one if it -// does not already exist. -// -CallGraphNode *CallGraph::getNodeFor(Function *F) { - CallGraphNode *&CGN = FunctionMap[F]; - if (CGN) return CGN; - - assert((!F || F->getParent() == Mod) && "Function not in current module!"); - return CGN = new CallGraphNode(F); -} +void llvm::BasicCallGraphStub() {} static bool isOnlyADirectCall(Function *F, CallSite CS) { if (!CS.getInstruction()) return false; @@ -39,125 +28,194 @@ return true; } -// addToCallGraph - Add a function to the call graph, and link the node to all -// of the functions that it calls. +namespace { + +//===----------------------------------------------------------------------===// +// BasicCallGraph class definition // -void CallGraph::addToCallGraph(Function *F) { - CallGraphNode *Node = getNodeFor(F); +class BasicCallGraph : public CallGraph, public ModulePass { + // Root is root of the call graph, or the external node if a 'main' function + // couldn't be found. + // + CallGraphNode *Root; - // If this function has external linkage, anything could call it... - if (!F->hasInternalLinkage()) { - ExternalCallingNode->addCalledFunction(Node); - - // Found the entry point? - if (F->getName() == "main") { - if (Root) // Found multiple external mains? Don't pick one. - Root = ExternalCallingNode; - else - Root = Node; // Found a main, keep track of it! - } + // ExternalCallingNode - This node has edges to all external functions and + // those internal functions that have their address taken. + CallGraphNode *ExternalCallingNode; + + // CallsExternalNode - This node has edges to it from all functions making + // indirect calls or calling an external function. + CallGraphNode *CallsExternalNode; + +public: + BasicCallGraph() : Root(0), ExternalCallingNode(0), CallsExternalNode(0) {} + ~BasicCallGraph() { destroy(); } + + // runOnModule - Compute the call graph for the specified module. + virtual bool runOnModule(Module &M) { + destroy(); + CallGraph::initialize(M); + + ExternalCallingNode = getNodeFor(0); + 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; } - // If this function is not defined in this translation unit, it could call - // anything. - if (F->isExternal() && !F->getIntrinsicID()) - Node->addCalledFunction(CallsExternalNode); - - // Loop over all of the users of the function... looking for callers... - // - bool isUsedExternally = false; - for (Value::use_iterator I = F->use_begin(), E = F->use_end(); I != E; ++I) { - if (Instruction *Inst = dyn_cast<Instruction>(*I)) { - if (isOnlyADirectCall(F, CallSite::get(Inst))) - getNodeFor(Inst->getParent()->getParent())->addCalledFunction(Node); - else - isUsedExternally = true; - } else if (GlobalValue *GV = dyn_cast<GlobalValue>(*I)) { - for (Value::use_iterator I = GV->use_begin(), E = GV->use_end(); - I != E; ++I) - if (Instruction *Inst = dyn_cast<Instruction>(*I)) { + virtual void getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesAll(); + } + + virtual void print(std::ostream &o, const Module *M) const { + o << "CallGraph Root is: "; + if (Function *F = getRoot()->getFunction()) + o << F->getName() << "\n"; + else + o << "<<null function: 0x" << getRoot() << ">>\n"; + + CallGraph::print(o, M); + } + + virtual void releaseMemory() { + destroy(); + } + + /// dump - Print out this call graph. + /// + inline void dump() const { + print(std::cerr, Mod); + } + + CallGraphNode* getExternalCallingNode() const { return ExternalCallingNode; } + CallGraphNode* getCallsExternalNode() const { return CallsExternalNode; } + + // getRoot - Return the root of the call graph, which is either main, or if + // main cannot be found, the external node. + // + CallGraphNode *getRoot() { return Root; } + const CallGraphNode *getRoot() const { return Root; } + +private: + //===--------------------------------------------------------------------- + // Implementation of CallGraph construction + // + // getNodeFor - Return the node for the specified function or create one if it + // does not already exist. + // + + CallGraphNode *getNodeFor(Function *F) { + CallGraphNode *&CGN = FunctionMap[F]; + if (CGN) return CGN; + + assert((!F || F->getParent() == Mod) && "Function not in current module!"); + return CGN = new CallGraphNode(F); + } + + // + // addToCallGraph - Add a function to the call graph, and link the node to all + // of the functions that it calls. + // + void addToCallGraph(Function *F) { + CallGraphNode *Node = getNodeFor(F); + + // If this function has external linkage, anything could call it... + if (!F->hasInternalLinkage()) { + ExternalCallingNode->addCalledFunction(Node); + + // Found the entry point? + if (F->getName() == "main") { + if (Root) // Found multiple external mains? Don't pick one. + Root = ExternalCallingNode; + else + Root = Node; // Found a main, keep track of it! + } + } + + // If this function is not defined in this translation unit, it could call + // anything. + if (F->isExternal() && !F->getIntrinsicID()) + Node->addCalledFunction(CallsExternalNode); + + // Loop over all of the users of the function... looking for callers... + // + bool isUsedExternally = false; + for (Value::use_iterator I = F->use_begin(), E = F->use_end(); I != E; ++I){ + if (Instruction *Inst = dyn_cast<Instruction>(*I)) { + if (isOnlyADirectCall(F, CallSite::get(Inst))) + getNodeFor(Inst->getParent()->getParent())->addCalledFunction(Node); + else + isUsedExternally = true; + } else if (GlobalValue *GV = dyn_cast<GlobalValue>(*I)) { + for (Value::use_iterator I = GV->use_begin(), E = GV->use_end(); + I != E; ++I) + if (Instruction *Inst = dyn_cast<Instruction>(*I)) { if (isOnlyADirectCall(F, CallSite::get(Inst))) getNodeFor(Inst->getParent()->getParent())->addCalledFunction(Node); else isUsedExternally = true; - } else { - isUsedExternally = true; - } - } else { // Can't classify the user! - isUsedExternally = true; + } else { + isUsedExternally = true; + } + } else { // Can't classify the user! + isUsedExternally = true; + } } - } - if (isUsedExternally) - ExternalCallingNode->addCalledFunction(Node); + if (isUsedExternally) + ExternalCallingNode->addCalledFunction(Node); // Look for an indirect function call... - for (Function::iterator BB = F->begin(), BBE = F->end(); BB != BBE; ++BB) - for (BasicBlock::iterator II = BB->begin(), IE = BB->end(); II != IE; ++II){ + for (Function::iterator BB = F->begin(), BBE = F->end(); BB != BBE; ++BB) + for (BasicBlock::iterator II = BB->begin(), IE = BB->end(); + II != IE; ++II) { CallSite CS = CallSite::get(II); if (CS.getInstruction() && !CS.getCalledFunction()) Node->addCalledFunction(CallsExternalNode); - } -} + } + } -bool CallGraph::runOnModule(Module &M) { - destroy(); + // + // destroy - Release memory for the call graph + virtual void destroy() { + if (!CallsExternalNode) { + delete CallsExternalNode; + CallsExternalNode = 0; + } + } +}; - Mod = &M; - ExternalCallingNode = getNodeFor(0); - 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); +RegisterAnalysisGroup<CallGraph> X("Call Graph"); +RegisterOpt<BasicCallGraph> Y("basiccg", "Basic CallGraph Construction"); +RegisterAnalysisGroup<CallGraph, BasicCallGraph, true> Z; - // If we didn't find a main function, use the external call graph node - if (Root == 0) Root = ExternalCallingNode; +} //End anonymous namespace - return false; +void CallGraph::initialize(Module &M) { + destroy(); + Mod = &M; } void CallGraph::destroy() { - for (FunctionMapTy::iterator I = FunctionMap.begin(), E = FunctionMap.end(); - I != E; ++I) - delete I->second; - FunctionMap.clear(); - delete CallsExternalNode; - CallsExternalNode = 0; -} - -void CallGraphNode::print(std::ostream &OS) const { - if (Function *F = getFunction()) - OS << "Call graph node for function: '" << F->getName() <<"'\n"; - else - OS << "Call graph node <<null function: 0x" << this << ">>:\n"; - - for (const_iterator I = begin(), E = end(); I != E; ++I) - if ((*I)->getFunction()) - OS << " Calls function '" << (*I)->getFunction()->getName() << "'\n"; - else - OS << " Calls external node\n"; - OS << "\n"; + if(!FunctionMap.size()) { + for (FunctionMapTy::iterator I = FunctionMap.begin(), E = FunctionMap.end(); + I != E; ++I) + delete I->second; + FunctionMap.clear(); + } } -void CallGraphNode::dump() const { print(std::cerr); } - void CallGraph::print(std::ostream &OS, const Module *M) const { - OS << "CallGraph Root is: "; - if (Function *F = getRoot()->getFunction()) - OS << F->getName() << "\n"; - else - OS << "<<null function: 0x" << getRoot() << ">>\n"; - for (CallGraph::const_iterator I = begin(), E = end(); I != E; ++I) I->second->print(OS); } -void CallGraph::dump() const { - print(std::cerr, 0); -} - - //===----------------------------------------------------------------------===// // Implementations of public modification methods // @@ -193,9 +251,24 @@ FunctionMap.erase(I); } - void CallGraph::stub() {} +void CallGraphNode::print(std::ostream &OS) const { + if (Function *F = getFunction()) + OS << "Call graph node for function: '" << F->getName() <<"'\n"; + else + OS << "Call graph node <<null function: 0x" << this << ">>:\n"; + + for (const_iterator I = begin(), E = end(); I != E; ++I) + if ((*I)->getFunction()) + OS << " Calls function '" << (*I)->getFunction()->getName() << "'\n"; + else + OS << " Calls external node\n"; + OS << "\n"; +} + +void CallGraphNode::dump() const { print(std::cerr); } + void CallGraphNode::removeCallEdgeTo(CallGraphNode *Callee) { for (unsigned i = CalledFunctions.size(); ; --i) { assert(i && "Cannot find callee to remove!"); _______________________________________________ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
