X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FIPA%2FCallGraph.cpp;h=67cf7f86e072507836b3057e3dc4a8a36a97d788;hb=12af22e8cc217827cf4f118b0f5e4ebbda9925ae;hp=9711013bea362f3ff1dbf0ee349608325485ca75;hpb=b374b90e81d0ce6b5d02041ba4f7b15a945b38d8;p=oota-llvm.git diff --git a/lib/Analysis/IPA/CallGraph.cpp b/lib/Analysis/IPA/CallGraph.cpp index 9711013bea3..67cf7f86e07 100644 --- a/lib/Analysis/IPA/CallGraph.cpp +++ b/lib/Analysis/IPA/CallGraph.cpp @@ -6,188 +6,105 @@ // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// -// -// This file implements the CallGraph class and provides the BasicCallGraph -// default implementation. -// -//===----------------------------------------------------------------------===// #include "llvm/Analysis/CallGraph.h" -#include "llvm/Module.h" -#include "llvm/Instructions.h" -#include "llvm/IntrinsicInst.h" -#include "llvm/Support/CallSite.h" -#include "llvm/Support/Compiler.h" +#include "llvm/IR/CallSite.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/IntrinsicInst.h" +#include "llvm/IR/Module.h" +#include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" using namespace llvm; -namespace { - //===----------------------------------------------------------------------===// -// BasicCallGraph class definition +// Implementations of the CallGraph class methods. // -class VISIBILITY_HIDDEN 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; - - // 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: - static char ID; // Class identification, replacement for typeinfo - BasicCallGraph() : ModulePass(&ID), Root(0), - ExternalCallingNode(0), CallsExternalNode(0) {} - - // runOnModule - Compute the call graph for the specified module. - virtual bool runOnModule(Module &M) { - CallGraph::initialize(M); - - ExternalCallingNode = getOrInsertFunction(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; - } - - virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.setPreservesAll(); - } - virtual void print(raw_ostream &OS, const Module *) const { - OS << "CallGraph Root is: "; - if (Function *F = getRoot()->getFunction()) - OS << F->getName() << "\n"; - else { - OS << "<>\n"; - } - - CallGraph::print(OS, 0); - } +CallGraph::CallGraph(Module &M) + : M(M), Root(nullptr), ExternalCallingNode(getOrInsertFunction(nullptr)), + CallsExternalNode(new CallGraphNode(nullptr)) { + // Add every function to the call graph. + for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) + addToCallGraph(I); - virtual void releaseMemory() { - destroy(); - } - - 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 - // - - // 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 = getOrInsertFunction(F); - - // If this function has external linkage, anything could call it. - if (!F->hasLocalLinkage()) { - ExternalCallingNode->addCalledFunction(CallSite(), 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! - } - } - - // Loop over all of the users of the function, looking for non-call uses. - for (Value::use_iterator I = F->use_begin(), E = F->use_end(); I != E; ++I) - if ((!isa(I) && !isa(I)) - || !CallSite(cast(I)).isCallee(I)) { - // Not a call, or being used as a parameter rather than as the callee. - ExternalCallingNode->addCalledFunction(CallSite(), Node); - break; - } + // If we didn't find a main function, use the external call graph node + if (!Root) + Root = ExternalCallingNode; +} - // If this function is not defined in this translation unit, it could call - // anything. - if (F->isDeclaration() && !F->isIntrinsic()) - Node->addCalledFunction(CallSite(), CallsExternalNode); - - // Look for calls by this function. - 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() && !isa(II)) { - const Function *Callee = CS.getCalledFunction(); - if (Callee) - Node->addCalledFunction(CS, getOrInsertFunction(Callee)); - else - Node->addCalledFunction(CS, CallsExternalNode); - } - } - } +CallGraph::~CallGraph() { + // CallsExternalNode is not in the function map, delete it explicitly. + CallsExternalNode->allReferencesDropped(); + delete CallsExternalNode; - // - // destroy - Release memory for the call graph - virtual void destroy() { - /// CallsExternalNode is not in the function map, delete it explicitly. - delete CallsExternalNode; - CallsExternalNode = 0; - CallGraph::destroy(); - } -}; +// 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; +} -} //End anonymous namespace +void CallGraph::addToCallGraph(Function *F) { + CallGraphNode *Node = getOrInsertFunction(F); -static RegisterAnalysisGroup X("Call Graph"); -static RegisterPass -Y("basiccg", "Basic CallGraph Construction", false, true); -static RegisterAnalysisGroup Z(Y); + // If this function has external linkage, anything could call it. + if (!F->hasLocalLinkage()) { + ExternalCallingNode->addCalledFunction(CallSite(), Node); -char CallGraph::ID = 0; -char BasicCallGraph::ID = 0; + // 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! + } + } -void CallGraph::initialize(Module &M) { - Mod = &M; + // If this function has its address taken, anything could call it. + if (F->hasAddressTaken()) + ExternalCallingNode->addCalledFunction(CallSite(), Node); + + // If this function is not defined in this translation unit, it could call + // anything. + if (F->isDeclaration() && !F->isIntrinsic()) + Node->addCalledFunction(CallSite(), CallsExternalNode); + + // Look for calls by this function. + 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(cast(II)); + if (CS) { + const Function *Callee = CS.getCalledFunction(); + if (!Callee) + // Indirect calls of intrinsics are not allowed so no need to check. + Node->addCalledFunction(CS, CallsExternalNode); + else if (!Callee->isIntrinsic()) + Node->addCalledFunction(CS, getOrInsertFunction(Callee)); + } + } } -void CallGraph::destroy() { - if (FunctionMap.empty()) return; - - for (FunctionMapTy::iterator I = FunctionMap.begin(), E = FunctionMap.end(); - I != E; ++I) - delete I->second; - FunctionMap.clear(); -} +void CallGraph::print(raw_ostream &OS) const { + OS << "CallGraph Root is: "; + if (Function *F = Root->getFunction()) + OS << F->getName() << "\n"; + else { + OS << "<>\n"; + } -void CallGraph::print(raw_ostream &OS, Module*) const { for (CallGraph::const_iterator I = begin(), E = end(); I != E; ++I) I->second->print(OS); } -void CallGraph::dump() const { - print(errs(), 0); -} -//===----------------------------------------------------------------------===// -// Implementations of public modification methods -// +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) +void CallGraph::dump() const { print(dbgs()); } +#endif // removeFunctionFromModule - Unlink the function from this module, returning // it. Because this removes the function from the module, the call graph node @@ -202,38 +119,62 @@ Function *CallGraph::removeFunctionFromModule(CallGraphNode *CGN) { delete CGN; // Delete the call graph node for this func FunctionMap.erase(F); // Remove the call graph node from the map - Mod->getFunctionList().remove(F); + M.getFunctionList().remove(F); return F; } +/// spliceFunction - Replace the function represented by this node by another. +/// This does not rescan the body of the function, so it is suitable when +/// splicing the body of the old function to the new while also updating all +/// callers from old to new. +/// +void CallGraph::spliceFunction(const Function *From, const Function *To) { + assert(FunctionMap.count(From) && "No CallGraphNode for function!"); + assert(!FunctionMap.count(To) && + "Pointing CallGraphNode at a function that already exists"); + FunctionMapTy::iterator I = FunctionMap.find(From); + I->second->F = const_cast(To); + FunctionMap[To] = I->second; + FunctionMap.erase(I); +} + // getOrInsertFunction - This method is identical to calling operator[], but // it will insert a new CallGraphNode for the specified function if one does // not already exist. CallGraphNode *CallGraph::getOrInsertFunction(const Function *F) { CallGraphNode *&CGN = FunctionMap[F]; - if (CGN) return CGN; - - assert((!F || F->getParent() == Mod) && "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(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() << "'"; else OS << "Call graph node <>"; - OS << "<<0x" << this << ">> #uses=" << getNumReferences() << '\n'; + OS << "<<" << this << ">> #uses=" << getNumReferences() << '\n'; - for (const_iterator I = begin(), E = end(); I != E; ++I) + for (const_iterator I = begin(), E = end(); I != E; ++I) { + OS << " CS<" << I->first << "> calls "; if (Function *FI = I->second->getFunction()) - OS << " Calls function '" << FI->getName() <<"'\n"; - else - OS << " Calls external node\n"; - OS << "\n"; + OS << "function '" << FI->getName() <<"'\n"; + else + OS << "external node\n"; + } + OS << '\n'; } -void CallGraphNode::dump() const { print(errs()); } +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) +void CallGraphNode::dump() const { print(dbgs()); } +#endif /// removeCallEdgeFor - This method removes the edge in the node for the /// specified call site. Note that this method takes linear time, so it @@ -241,7 +182,7 @@ void CallGraphNode::dump() const { print(errs()); } void CallGraphNode::removeCallEdgeFor(CallSite CS) { for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) { assert(I != CalledFunctions.end() && "Cannot find callsite to remove!"); - if (I->first == CS) { + if (I->first == CS.getInstruction()) { I->second->DropRef(); *I = CalledFunctions.back(); CalledFunctions.pop_back(); @@ -250,7 +191,6 @@ void CallGraphNode::removeCallEdgeFor(CallSite CS) { } } - // removeAnyCallEdgeTo - This method removes any call edges from this node to // the specified callee function. This takes more time to execute than // removeCallEdgeTo, so it should not be used unless necessary. @@ -270,7 +210,7 @@ void CallGraphNode::removeOneAbstractEdgeTo(CallGraphNode *Callee) { for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) { assert(I != CalledFunctions.end() && "Cannot find callee to remove!"); CallRecord &CR = *I; - if (CR.second == Callee && CR.first.getInstruction() == 0) { + if (CR.second == Callee && CR.first == nullptr) { Callee->DropRef(); *I = CalledFunctions.back(); CalledFunctions.pop_back(); @@ -279,27 +219,66 @@ void CallGraphNode::removeOneAbstractEdgeTo(CallGraphNode *Callee) { } } -/// replaceCallSite - Make the edge in the node for Old CallSite be for -/// New CallSite instead. Note that this method takes linear time, so it -/// should be used sparingly. -void CallGraphNode::replaceCallSite(CallSite Old, CallSite New, - CallGraphNode *NewCallee) { +/// replaceCallEdge - This method replaces the edge in the node for the +/// specified call site with a new one. Note that this method takes linear +/// time, so it should be used sparingly. +void CallGraphNode::replaceCallEdge(CallSite CS, + CallSite NewCS, CallGraphNode *NewNode){ for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) { - assert(I != CalledFunctions.end() && "Cannot find callsite to replace!"); - if (I->first == Old) { - I->first = New; - - // If the callee is changing, not just the callsite, then update it as - // well. - if (NewCallee) { - I->second->DropRef(); - I->second = NewCallee; - I->second->AddRef(); - } + assert(I != CalledFunctions.end() && "Cannot find callsite to remove!"); + if (I->first == CS.getInstruction()) { + I->second->DropRef(); + I->first = NewCS.getInstruction(); + I->second = NewNode; + NewNode->AddRef(); return; } } } -// Enuse that users of CallGraph.h also link with this file -DEFINING_FILE_FOR(CallGraph) +//===----------------------------------------------------------------------===// +// Out-of-line definitions of CallGraphAnalysis class members. +// + +char CallGraphAnalysis::PassID; + +//===----------------------------------------------------------------------===// +// 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(); } + +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(), nullptr); } +#endif