X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=lib%2FAnalysis%2FIPA%2FCallGraph.cpp;h=083b22d0170aa127e8690162d15c0f1306f156c5;hp=5757bfd897f6db3ea4123aa21b216e9ec13995ce;hb=5df1207c2cf57a98763c28c8534230726ca8fc3a;hpb=be577659d3c1222cc58c33628c0baddb94d241ab diff --git a/lib/Analysis/IPA/CallGraph.cpp b/lib/Analysis/IPA/CallGraph.cpp index 5757bfd897f..083b22d0170 100644 --- a/lib/Analysis/IPA/CallGraph.cpp +++ b/lib/Analysis/IPA/CallGraph.cpp @@ -6,188 +6,130 @@ // 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(); - } +CallGraph::CallGraph(Module &M) + : M(M), Root(nullptr), ExternalCallingNode(getOrInsertFunction(nullptr)), + CallsExternalNode(llvm::make_unique(nullptr)) { + // Add every function to the call graph. + for (Function &F : M) + addToCallGraph(&F); + + // If we didn't find a main function, use the external call graph node + if (!Root) + Root = ExternalCallingNode; +} - 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::CallGraph(CallGraph &&Arg) + : M(Arg.M), FunctionMap(std::move(Arg.FunctionMap)), Root(Arg.Root), + ExternalCallingNode(Arg.ExternalCallingNode), + CallsExternalNode(std::move(Arg.CallsExternalNode)) { + Arg.FunctionMap.clear(); + Arg.Root = nullptr; + Arg.ExternalCallingNode = nullptr; +} + +CallGraph::~CallGraph() { + // CallsExternalNode is not in the function map, delete it explicitly. + if (CallsExternalNode) + CallsExternalNode->allReferencesDropped(); + +// Reset all node's use counts to zero before deleting them to prevent an +// assertion from firing. +#ifndef NDEBUG + for (auto &I : FunctionMap) + I.second->allReferencesDropped(); +#endif +} + +void CallGraph::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! } - - CallGraph::print(OS, 0); } - 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! + // 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.get()); + + // 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 || !Intrinsic::isLeaf(Callee->getIntrinsicID())) + // Indirect calls of intrinsics are not allowed so no need to check. + // We can be more precise here by using TargetArg returned by + // Intrinsic::isLeaf. + Node->addCalledFunction(CS, CallsExternalNode.get()); + else if (!Callee->isIntrinsic()) + Node->addCalledFunction(CS, getOrInsertFunction(Callee)); } } +} - // 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 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); - } - } +void CallGraph::print(raw_ostream &OS) const { + OS << "CallGraph Root is: "; + if (Function *F = Root->getFunction()) + OS << F->getName() << "\n"; + else { + OS << "<>\n"; } - // - // 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(); - } -}; + // Print in a deterministic order by sorting CallGraphNodes by name. We do + // this here to avoid slowing down the non-printing fast path. -} //End anonymous namespace + SmallVector Nodes; + Nodes.reserve(FunctionMap.size()); -static RegisterAnalysisGroup X("Call Graph"); -static RegisterPass -Y("basiccg", "Basic CallGraph Construction", false, true); -static RegisterAnalysisGroup Z(Y); + for (auto I = begin(), E = end(); I != E; ++I) + Nodes.push_back(I->second.get()); -char CallGraph::ID = 0; -char BasicCallGraph::ID = 0; + std::sort(Nodes.begin(), Nodes.end(), + [](CallGraphNode *LHS, CallGraphNode *RHS) { + if (Function *LF = LHS->getFunction()) + if (Function *RF = RHS->getFunction()) + return LF->getName() < RF->getName(); -void CallGraph::initialize(Module &M) { - Mod = &M; -} + return RHS->getFunction() != nullptr; + }); -void CallGraph::destroy() { - if (FunctionMap.empty()) return; - - for (FunctionMapTy::iterator I = FunctionMap.begin(), E = FunctionMap.end(); - I != E; ++I) - delete I->second; - FunctionMap.clear(); + for (CallGraphNode *CN : Nodes) + CN->print(OS); } -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 @@ -199,41 +141,65 @@ Function *CallGraph::removeFunctionFromModule(CallGraphNode *CGN) { 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 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] = std::move(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!"); - return CGN = new CallGraphNode(const_cast(F)); + auto &CGN = FunctionMap[F]; + if (CGN) + return CGN.get(); + + assert((!F || F->getParent() == &M) && "Function not in current module!"); + CGN = llvm::make_unique(const_cast(F)); + return CGN.get(); } +//===----------------------------------------------------------------------===// +// 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 +207,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,22 +216,6 @@ void CallGraphNode::removeCallEdgeFor(CallSite CS) { } } -// FIXME: REMOVE THIS WHEN HACK IS REMOVED FROM CGSCCPASSMGR. -void CallGraphNode::removeCallEdgeFor(Instruction *CS) { - for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) { - assert(I != CalledFunctions.end() && "Cannot find callsite to remove!"); - if (I->first.getInstruction() == CS) { - I->second->DropRef(); - *I = CalledFunctions.back(); - CalledFunctions.pop_back(); - return; - } - } - -} - - - // 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. @@ -285,7 +235,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(); @@ -294,27 +244,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) continue; - - I->first = New; - - // If the callee is changing, not just the callsite, then update it as - // well. - if (NewCallee) { + assert(I != CalledFunctions.end() && "Cannot find callsite to remove!"); + if (I->first == CS.getInstruction()) { I->second->DropRef(); - I->second = NewCallee; - I->second->AddRef(); + I->first = NewCS.getInstruction(); + I->second = NewNode; + NewNode->AddRef(); + return; } + } +} + +//===----------------------------------------------------------------------===// +// 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); } -// Enuse that users of CallGraph.h also link with this file -DEFINING_FILE_FOR(CallGraph) +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) +void CallGraphWrapperPass::dump() const { print(dbgs(), nullptr); } +#endif