1193323Sed//===- CallGraph.cpp - Build a Module's call graph ------------------------===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed 10193323Sed#include "llvm/Analysis/CallGraph.h" 11249423Sdim#include "llvm/IR/Instructions.h" 12249423Sdim#include "llvm/IR/IntrinsicInst.h" 13249423Sdim#include "llvm/IR/Module.h" 14193323Sed#include "llvm/Support/CallSite.h" 15201360Srdivacky#include "llvm/Support/Debug.h" 16198090Srdivacky#include "llvm/Support/raw_ostream.h" 17193323Sedusing namespace llvm; 18193323Sed 19263508SdimCallGraph::CallGraph() 20263508Sdim : ModulePass(ID), Root(0), ExternalCallingNode(0), CallsExternalNode(0) { 21263508Sdim initializeCallGraphPass(*PassRegistry::getPassRegistry()); 22263508Sdim} 23193323Sed 24263508Sdimvoid CallGraph::addToCallGraph(Function *F) { 25263508Sdim CallGraphNode *Node = getOrInsertFunction(F); 26193323Sed 27263508Sdim // If this function has external linkage, anything could call it. 28263508Sdim if (!F->hasLocalLinkage()) { 29263508Sdim ExternalCallingNode->addCalledFunction(CallSite(), Node); 30193323Sed 31263508Sdim // Found the entry point? 32263508Sdim if (F->getName() == "main") { 33263508Sdim if (Root) // Found multiple external mains? Don't pick one. 34263508Sdim Root = ExternalCallingNode; 35263508Sdim else 36263508Sdim Root = Node; // Found a main, keep track of it! 37218893Sdim } 38193323Sed } 39193323Sed 40263508Sdim // If this function has its address taken, anything could call it. 41263508Sdim if (F->hasAddressTaken()) 42263508Sdim ExternalCallingNode->addCalledFunction(CallSite(), Node); 43193323Sed 44263508Sdim // If this function is not defined in this translation unit, it could call 45263508Sdim // anything. 46263508Sdim if (F->isDeclaration() && !F->isIntrinsic()) 47263508Sdim Node->addCalledFunction(CallSite(), CallsExternalNode); 48263508Sdim 49263508Sdim // Look for calls by this function. 50263508Sdim for (Function::iterator BB = F->begin(), BBE = F->end(); BB != BBE; ++BB) 51263508Sdim for (BasicBlock::iterator II = BB->begin(), IE = BB->end(); II != IE; 52263508Sdim ++II) { 53263508Sdim CallSite CS(cast<Value>(II)); 54263508Sdim if (CS) { 55263508Sdim const Function *Callee = CS.getCalledFunction(); 56263508Sdim if (!Callee) 57263508Sdim // Indirect calls of intrinsics are not allowed so no need to check. 58263508Sdim Node->addCalledFunction(CS, CallsExternalNode); 59263508Sdim else if (!Callee->isIntrinsic()) 60263508Sdim Node->addCalledFunction(CS, getOrInsertFunction(Callee)); 61263508Sdim } 62198090Srdivacky } 63263508Sdim} 64193323Sed 65263508Sdimvoid CallGraph::getAnalysisUsage(AnalysisUsage &AU) const { 66263508Sdim AU.setPreservesAll(); 67263508Sdim} 68193323Sed 69263508Sdimbool CallGraph::runOnModule(Module &M) { 70263508Sdim Mod = &M; 71193323Sed 72263508Sdim ExternalCallingNode = getOrInsertFunction(0); 73263508Sdim assert(!CallsExternalNode); 74263508Sdim CallsExternalNode = new CallGraphNode(0); 75263508Sdim Root = 0; 76193323Sed 77263508Sdim // Add every function to the call graph. 78263508Sdim for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) 79263508Sdim addToCallGraph(I); 80193323Sed 81263508Sdim // If we didn't find a main function, use the external call graph node 82263508Sdim if (Root == 0) 83263508Sdim Root = ExternalCallingNode; 84193323Sed 85263508Sdim return false; 86263508Sdim} 87193323Sed 88263508SdimINITIALIZE_PASS(CallGraph, "basiccg", "CallGraph Construction", false, true) 89193323Sed 90263508Sdimchar CallGraph::ID = 0; 91193323Sed 92263508Sdimvoid CallGraph::releaseMemory() { 93263508Sdim /// CallsExternalNode is not in the function map, delete it explicitly. 94263508Sdim if (CallsExternalNode) { 95263508Sdim CallsExternalNode->allReferencesDropped(); 96263508Sdim delete CallsExternalNode; 97263508Sdim CallsExternalNode = 0; 98193323Sed } 99193323Sed 100263508Sdim if (FunctionMap.empty()) 101263508Sdim return; 102193323Sed 103263508Sdim// Reset all node's use counts to zero before deleting them to prevent an 104263508Sdim// assertion from firing. 105207618Srdivacky#ifndef NDEBUG 106198090Srdivacky for (FunctionMapTy::iterator I = FunctionMap.begin(), E = FunctionMap.end(); 107207618Srdivacky I != E; ++I) 108207618Srdivacky I->second->allReferencesDropped(); 109207618Srdivacky#endif 110207618Srdivacky 111207618Srdivacky for (FunctionMapTy::iterator I = FunctionMap.begin(), E = FunctionMap.end(); 112198090Srdivacky I != E; ++I) 113198090Srdivacky delete I->second; 114198090Srdivacky FunctionMap.clear(); 115193323Sed} 116193323Sed 117263508Sdimvoid CallGraph::print(raw_ostream &OS, const Module*) const { 118263508Sdim OS << "CallGraph Root is: "; 119263508Sdim if (Function *F = Root->getFunction()) 120263508Sdim OS << F->getName() << "\n"; 121263508Sdim else { 122263508Sdim OS << "<<null function: 0x" << Root << ">>\n"; 123263508Sdim } 124263508Sdim 125193323Sed for (CallGraph::const_iterator I = begin(), E = end(); I != E; ++I) 126193323Sed I->second->print(OS); 127193323Sed} 128243830Sdim#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 129193323Sedvoid CallGraph::dump() const { 130201360Srdivacky print(dbgs(), 0); 131193323Sed} 132243830Sdim#endif 133193323Sed 134193323Sed//===----------------------------------------------------------------------===// 135193323Sed// Implementations of public modification methods 136193323Sed// 137193323Sed 138193323Sed// removeFunctionFromModule - Unlink the function from this module, returning 139193323Sed// it. Because this removes the function from the module, the call graph node 140193323Sed// is destroyed. This is only valid if the function does not call any other 141193323Sed// functions (ie, there are no edges in it's CGN). The easiest way to do this 142193323Sed// is to dropAllReferences before calling this. 143193323Sed// 144193323SedFunction *CallGraph::removeFunctionFromModule(CallGraphNode *CGN) { 145198090Srdivacky assert(CGN->empty() && "Cannot remove function from call " 146193323Sed "graph if it references other functions!"); 147193323Sed Function *F = CGN->getFunction(); // Get the function for the call graph node 148193323Sed delete CGN; // Delete the call graph node for this func 149193323Sed FunctionMap.erase(F); // Remove the call graph node from the map 150193323Sed 151193323Sed Mod->getFunctionList().remove(F); 152193323Sed return F; 153193323Sed} 154193323Sed 155218893Sdim/// spliceFunction - Replace the function represented by this node by another. 156218893Sdim/// This does not rescan the body of the function, so it is suitable when 157218893Sdim/// splicing the body of the old function to the new while also updating all 158218893Sdim/// callers from old to new. 159218893Sdim/// 160218893Sdimvoid CallGraph::spliceFunction(const Function *From, const Function *To) { 161218893Sdim assert(FunctionMap.count(From) && "No CallGraphNode for function!"); 162218893Sdim assert(!FunctionMap.count(To) && 163218893Sdim "Pointing CallGraphNode at a function that already exists"); 164218893Sdim FunctionMapTy::iterator I = FunctionMap.find(From); 165218893Sdim I->second->F = const_cast<Function*>(To); 166218893Sdim FunctionMap[To] = I->second; 167218893Sdim FunctionMap.erase(I); 168218893Sdim} 169218893Sdim 170193323Sed// getOrInsertFunction - This method is identical to calling operator[], but 171193323Sed// it will insert a new CallGraphNode for the specified function if one does 172193323Sed// not already exist. 173193323SedCallGraphNode *CallGraph::getOrInsertFunction(const Function *F) { 174193323Sed CallGraphNode *&CGN = FunctionMap[F]; 175193323Sed if (CGN) return CGN; 176193323Sed 177193323Sed assert((!F || F->getParent() == Mod) && "Function not in current module!"); 178193323Sed return CGN = new CallGraphNode(const_cast<Function*>(F)); 179193323Sed} 180193323Sed 181198090Srdivackyvoid CallGraphNode::print(raw_ostream &OS) const { 182193323Sed if (Function *F = getFunction()) 183198090Srdivacky OS << "Call graph node for function: '" << F->getName() << "'"; 184193323Sed else 185198090Srdivacky OS << "Call graph node <<null function>>"; 186198090Srdivacky 187207618Srdivacky OS << "<<" << this << ">> #uses=" << getNumReferences() << '\n'; 188193323Sed 189207618Srdivacky for (const_iterator I = begin(), E = end(); I != E; ++I) { 190207618Srdivacky OS << " CS<" << I->first << "> calls "; 191193323Sed if (Function *FI = I->second->getFunction()) 192207618Srdivacky OS << "function '" << FI->getName() <<"'\n"; 193207618Srdivacky else 194207618Srdivacky OS << "external node\n"; 195207618Srdivacky } 196207618Srdivacky OS << '\n'; 197193323Sed} 198193323Sed 199243830Sdim#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 200201360Srdivackyvoid CallGraphNode::dump() const { print(dbgs()); } 201243830Sdim#endif 202193323Sed 203193323Sed/// removeCallEdgeFor - This method removes the edge in the node for the 204193323Sed/// specified call site. Note that this method takes linear time, so it 205193323Sed/// should be used sparingly. 206193323Sedvoid CallGraphNode::removeCallEdgeFor(CallSite CS) { 207193323Sed for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) { 208193323Sed assert(I != CalledFunctions.end() && "Cannot find callsite to remove!"); 209198090Srdivacky if (I->first == CS.getInstruction()) { 210198090Srdivacky I->second->DropRef(); 211198090Srdivacky *I = CalledFunctions.back(); 212198090Srdivacky CalledFunctions.pop_back(); 213193323Sed return; 214193323Sed } 215193323Sed } 216193323Sed} 217193323Sed 218193323Sed// removeAnyCallEdgeTo - This method removes any call edges from this node to 219193323Sed// the specified callee function. This takes more time to execute than 220193323Sed// removeCallEdgeTo, so it should not be used unless necessary. 221193323Sedvoid CallGraphNode::removeAnyCallEdgeTo(CallGraphNode *Callee) { 222193323Sed for (unsigned i = 0, e = CalledFunctions.size(); i != e; ++i) 223193323Sed if (CalledFunctions[i].second == Callee) { 224198090Srdivacky Callee->DropRef(); 225193323Sed CalledFunctions[i] = CalledFunctions.back(); 226193323Sed CalledFunctions.pop_back(); 227193323Sed --i; --e; 228193323Sed } 229193323Sed} 230193323Sed 231193323Sed/// removeOneAbstractEdgeTo - Remove one edge associated with a null callsite 232193323Sed/// from this node to the specified callee function. 233193323Sedvoid CallGraphNode::removeOneAbstractEdgeTo(CallGraphNode *Callee) { 234193323Sed for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) { 235193323Sed assert(I != CalledFunctions.end() && "Cannot find callee to remove!"); 236193323Sed CallRecord &CR = *I; 237198090Srdivacky if (CR.second == Callee && CR.first == 0) { 238198090Srdivacky Callee->DropRef(); 239198090Srdivacky *I = CalledFunctions.back(); 240198090Srdivacky CalledFunctions.pop_back(); 241193323Sed return; 242193323Sed } 243193323Sed } 244193323Sed} 245193323Sed 246198090Srdivacky/// replaceCallEdge - This method replaces the edge in the node for the 247198090Srdivacky/// specified call site with a new one. Note that this method takes linear 248198090Srdivacky/// time, so it should be used sparingly. 249198090Srdivackyvoid CallGraphNode::replaceCallEdge(CallSite CS, 250198090Srdivacky CallSite NewCS, CallGraphNode *NewNode){ 251193323Sed for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) { 252198090Srdivacky assert(I != CalledFunctions.end() && "Cannot find callsite to remove!"); 253198090Srdivacky if (I->first == CS.getInstruction()) { 254198090Srdivacky I->second->DropRef(); 255198090Srdivacky I->first = NewCS.getInstruction(); 256198090Srdivacky I->second = NewNode; 257198090Srdivacky NewNode->AddRef(); 258193323Sed return; 259193323Sed } 260193323Sed } 261193323Sed} 262193323Sed 263193323Sed// Enuse that users of CallGraph.h also link with this file 264193323SedDEFINING_FILE_FOR(CallGraph) 265