X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FIPA%2FCallGraph.cpp;h=f042964c21d918eebc66c2d41dfd2ca2b0dd9593;hb=c143c7573bfd0d55cf283cc2676dbd852f939c87;hp=bb96bb2d654ef2d36b626335dfe3ccbd271d2ff0;hpb=d7d83db5f22d05e5b14b6b1d838668222113c83a;p=oota-llvm.git diff --git a/lib/Analysis/IPA/CallGraph.cpp b/lib/Analysis/IPA/CallGraph.cpp index bb96bb2d654..f042964c21d 100644 --- a/lib/Analysis/IPA/CallGraph.cpp +++ b/lib/Analysis/IPA/CallGraph.cpp @@ -2,219 +2,134 @@ // // 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 file implements the CallGraph class and provides the BasicCallGraph -// default implementation. +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// #include "llvm/Analysis/CallGraph.h" -#include "llvm/Module.h" -#include "llvm/Instructions.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/IntrinsicInst.h" +#include "llvm/IR/Module.h" #include "llvm/Support/CallSite.h" -#include "llvm/Support/Compiler.h" -#include "llvm/Support/Streams.h" -#include +#include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" using namespace llvm; -/// isOnlyADirectCall - Return true if this callsite is *just* a direct call to -/// the specified function. Specifically return false if the callsite also -/// takes the address of the function. -static bool isOnlyADirectCall(Function *F, CallSite CS) { - if (!CS.getInstruction()) return false; - for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end(); I != E; ++I) - if (*I == F) return false; - return true; +CallGraph::CallGraph() + : ModulePass(ID), Root(0), ExternalCallingNode(0), CallsExternalNode(0) { + initializeCallGraphPass(*PassRegistry::getPassRegistry()); } -namespace { +void CallGraph::addToCallGraph(Function *F) { + CallGraphNode *Node = getOrInsertFunction(F); -//===----------------------------------------------------------------------===// -// BasicCallGraph class definition -// -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: - BasicCallGraph() : 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; - } + // If this function has external linkage, anything could call it. + if (!F->hasLocalLinkage()) { + ExternalCallingNode->addCalledFunction(CallSite(), Node); - virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.setPreservesAll(); + // 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 print(std::ostream *o, const Module *M) const { - if (o) print(*o, 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)); + } + } +} - 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 << "<>\n"; - - CallGraph::print(o, M); - } +void CallGraph::getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesAll(); +} - virtual void releaseMemory() { - destroy(); - } - - /// dump - Print out this call graph. - /// - inline void dump() const { - print(cerr, Mod); - } +bool CallGraph::runOnModule(Module &M) { + Mod = &M; - 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->hasInternalLinkage()) { - 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! - } - } + ExternalCallingNode = getOrInsertFunction(0); + assert(!CallsExternalNode); + CallsExternalNode = new CallGraphNode(0); + Root = 0; - // If this function is not defined in this translation unit, it could call - // anything. - if (F->isDeclaration() && !F->getIntrinsicID()) - Node->addCalledFunction(CallSite(), 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(*I)) { - CallSite CS = CallSite::get(Inst); - if (isOnlyADirectCall(F, CS)) - getOrInsertFunction(Inst->getParent()->getParent()) - ->addCalledFunction(CS, Node); - else - isUsedExternally = true; - } else if (GlobalValue *GV = dyn_cast(*I)) { - for (Value::use_iterator I = GV->use_begin(), E = GV->use_end(); - I != E; ++I) - if (Instruction *Inst = dyn_cast(*I)) { - CallSite CS = CallSite::get(Inst); - if (isOnlyADirectCall(F, CS)) - getOrInsertFunction(Inst->getParent()->getParent()) - ->addCalledFunction(CS, Node); - else - isUsedExternally = true; - } else { - isUsedExternally = true; - } - } else { // Can't classify the user! - isUsedExternally = true; - } - } - if (isUsedExternally) - ExternalCallingNode->addCalledFunction(CallSite(), 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) { - CallSite CS = CallSite::get(II); - if (CS.getInstruction() && !CS.getCalledFunction()) - Node->addCalledFunction(CS, CallsExternalNode); - } - } + // 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; - // - // destroy - Release memory for the call graph - virtual void destroy() { - /// CallsExternalNode is not in the function map, delete it explicitly. + 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; - CallGraph::destroy(); } -}; -RegisterAnalysisGroup X("Call Graph"); -RegisterPass Y("basiccg", "Basic CallGraph Construction"); -RegisterAnalysisGroup Z(Y); + if (FunctionMap.empty()) + return; -} //End anonymous namespace - -void CallGraph::initialize(Module &M) { - Mod = &M; +// 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::destroy() { - if (!FunctionMap.empty()) { - 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 { + OS << "CallGraph Root is: "; + if (Function *F = Root->getFunction()) + OS << F->getName() << "\n"; + else { + OS << "<>\n"; } -} -void CallGraph::print(std::ostream &OS, const Module *M) const { 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(cerr, 0); + print(dbgs(), 0); } +#endif //===----------------------------------------------------------------------===// // Implementations of public modification methods @@ -227,7 +142,7 @@ void CallGraph::dump() const { // is to dropAllReferences before calling this. // Function *CallGraph::removeFunctionFromModule(CallGraphNode *CGN) { - assert(CGN->CalledFunctions.empty() && "Cannot remove function from call " + assert(CGN->empty() && "Cannot remove function from call " "graph if it references other functions!"); Function *F = CGN->getFunction(); // Get the function for the call graph node delete CGN; // Delete the call graph node for this func @@ -237,17 +152,18 @@ Function *CallGraph::removeFunctionFromModule(CallGraphNode *CGN) { return F; } -// changeFunction - This method changes the function associated with this -// CallGraphNode, for use by transformations that need to change the prototype -// of a Function (thus they must create a new Function and move the old code -// over). -void CallGraph::changeFunction(Function *OldF, Function *NewF) { - iterator I = FunctionMap.find(OldF); - CallGraphNode *&New = FunctionMap[NewF]; - assert(I != FunctionMap.end() && I->second && !New && - "OldF didn't exist in CG or NewF already does!"); - New = I->second; - New->F = NewF; +/// 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); } @@ -262,27 +178,38 @@ CallGraphNode *CallGraph::getOrInsertFunction(const Function *F) { return CGN = new CallGraphNode(const_cast(F)); } -void CallGraphNode::print(std::ostream &OS) const { +void CallGraphNode::print(raw_ostream &OS) const { if (Function *F = getFunction()) - OS << "Call graph node for function: '" << F->getName() <<"'\n"; + OS << "Call graph node for function: '" << F->getName() << "'"; else - OS << "Call graph node <>:\n"; + OS << "Call graph node <>"; + + OS << "<<" << this << ">> #uses=" << getNumReferences() << '\n'; - for (const_iterator I = begin(), E = end(); I != E; ++I) - if (I->second->getFunction()) - OS << " Calls function '" << I->second->getFunction()->getName() <<"'\n"; - else - OS << " Calls external node\n"; - OS << "\n"; + for (const_iterator I = begin(), E = end(); I != E; ++I) { + OS << " CS<" << I->first << "> calls "; + if (Function *FI = I->second->getFunction()) + OS << "function '" << FI->getName() <<"'\n"; + else + OS << "external node\n"; + } + OS << '\n'; } -void CallGraphNode::dump() const { print(cerr); } - -void CallGraphNode::removeCallEdgeTo(CallGraphNode *Callee) { - for (unsigned i = CalledFunctions.size(); ; --i) { - assert(i && "Cannot find callee to remove!"); - if (CalledFunctions[i-1].second == Callee) { - CalledFunctions.erase(CalledFunctions.begin()+i-1); +#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 +/// should be used sparingly. +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.getInstruction()) { + I->second->DropRef(); + *I = CalledFunctions.back(); + CalledFunctions.pop_back(); return; } } @@ -294,11 +221,44 @@ void CallGraphNode::removeCallEdgeTo(CallGraphNode *Callee) { void CallGraphNode::removeAnyCallEdgeTo(CallGraphNode *Callee) { for (unsigned i = 0, e = CalledFunctions.size(); i != e; ++i) if (CalledFunctions[i].second == Callee) { + Callee->DropRef(); CalledFunctions[i] = CalledFunctions.back(); CalledFunctions.pop_back(); --i; --e; } } +/// removeOneAbstractEdgeTo - Remove one edge associated with a null callsite +/// from this node to the specified callee function. +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 == 0) { + Callee->DropRef(); + *I = CalledFunctions.back(); + CalledFunctions.pop_back(); + return; + } + } +} + +/// 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 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)