LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

CallGraph.cpp

Go to the documentation of this file.
00001 //===- CallGraph.cpp - Build a Module's call graph ------------------------===//
00002 // 
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 // 
00008 //===----------------------------------------------------------------------===//
00009 //
00010 //  This file implements the CallGraph class.
00011 //
00012 //===----------------------------------------------------------------------===//
00013 
00014 #include "llvm/Analysis/CallGraph.h"
00015 #include "llvm/Module.h"
00016 #include "llvm/Instructions.h"
00017 #include "llvm/Support/CallSite.h"
00018 #include "llvm/ADT/STLExtras.h"
00019 #include <iostream>
00020 using namespace llvm;
00021 
00022 static RegisterAnalysis<CallGraph> X("callgraph", "Call Graph Construction");
00023 
00024 // getNodeFor - Return the node for the specified function or create one if it
00025 // does not already exist.
00026 //
00027 CallGraphNode *CallGraph::getNodeFor(Function *F) {
00028   CallGraphNode *&CGN = FunctionMap[F];
00029   if (CGN) return CGN;
00030 
00031   assert((!F || F->getParent() == Mod) && "Function not in current module!");
00032   return CGN = new CallGraphNode(F);
00033 }
00034 
00035 static bool isOnlyADirectCall(Function *F, CallSite CS) {
00036   if (!CS.getInstruction()) return false;
00037   for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end(); I != E; ++I)
00038     if (*I == F) return false;
00039   return true;
00040 }
00041 
00042 // addToCallGraph - Add a function to the call graph, and link the node to all
00043 // of the functions that it calls.
00044 //
00045 void CallGraph::addToCallGraph(Function *F) {
00046   CallGraphNode *Node = getNodeFor(F);
00047 
00048   // If this function has external linkage, anything could call it...
00049   if (!F->hasInternalLinkage()) {
00050     ExternalCallingNode->addCalledFunction(Node);
00051 
00052     // Found the entry point?
00053     if (F->getName() == "main") {
00054       if (Root)    // Found multiple external mains?  Don't pick one.
00055         Root = ExternalCallingNode;
00056       else
00057         Root = Node;          // Found a main, keep track of it!
00058     }
00059   }
00060   
00061   // If this function is not defined in this translation unit, it could call
00062   // anything.
00063   if (F->isExternal() && !F->getIntrinsicID())
00064     Node->addCalledFunction(CallsExternalNode);
00065 
00066   // Loop over all of the users of the function... looking for callers...
00067   //
00068   bool isUsedExternally = false;
00069   for (Value::use_iterator I = F->use_begin(), E = F->use_end(); I != E; ++I) {
00070     if (Instruction *Inst = dyn_cast<Instruction>(*I)) {
00071       if (isOnlyADirectCall(F, CallSite::get(Inst)))
00072         getNodeFor(Inst->getParent()->getParent())->addCalledFunction(Node);
00073       else
00074         isUsedExternally = true;
00075     } else if (GlobalValue *GV = dyn_cast<GlobalValue>(*I)) {
00076       for (Value::use_iterator I = GV->use_begin(), E = GV->use_end();
00077            I != E; ++I)
00078         if (Instruction *Inst = dyn_cast<Instruction>(*I)) {
00079           if (isOnlyADirectCall(F, CallSite::get(Inst)))
00080             getNodeFor(Inst->getParent()->getParent())->addCalledFunction(Node);
00081           else
00082             isUsedExternally = true;
00083         } else {
00084           isUsedExternally = true;
00085         }
00086     } else {                        // Can't classify the user!
00087       isUsedExternally = true;
00088     }
00089   }
00090   if (isUsedExternally)
00091     ExternalCallingNode->addCalledFunction(Node);
00092 
00093   // Look for an indirect function call...
00094   for (Function::iterator BB = F->begin(), BBE = F->end(); BB != BBE; ++BB)
00095     for (BasicBlock::iterator II = BB->begin(), IE = BB->end(); II != IE; ++II){
00096       CallSite CS = CallSite::get(II);
00097       if (CS.getInstruction() && !CS.getCalledFunction())
00098         Node->addCalledFunction(CallsExternalNode);
00099     }
00100 }
00101 
00102 bool CallGraph::runOnModule(Module &M) {
00103   destroy();
00104 
00105   Mod = &M;
00106   ExternalCallingNode = getNodeFor(0);
00107   CallsExternalNode = new CallGraphNode(0);
00108   Root = 0;
00109 
00110   // Add every function to the call graph...
00111   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
00112     addToCallGraph(I);
00113 
00114   // If we didn't find a main function, use the external call graph node
00115   if (Root == 0) Root = ExternalCallingNode;
00116   
00117   return false;
00118 }
00119 
00120 void CallGraph::destroy() {
00121   for (FunctionMapTy::iterator I = FunctionMap.begin(), E = FunctionMap.end();
00122        I != E; ++I)
00123     delete I->second;
00124   FunctionMap.clear();
00125   delete CallsExternalNode;
00126   CallsExternalNode = 0;
00127 }
00128 
00129 void CallGraphNode::print(std::ostream &OS) const {
00130   if (Function *F = getFunction())
00131     OS << "Call graph node for function: '" << F->getName() <<"'\n";
00132   else
00133     OS << "Call graph node <<null function: 0x" << this << ">>:\n";
00134 
00135   for (const_iterator I = begin(), E = end(); I != E; ++I)
00136     if ((*I)->getFunction())
00137       OS << "  Calls function '" << (*I)->getFunction()->getName() << "'\n";
00138     else
00139       OS << "  Calls external node\n";
00140   OS << "\n";
00141 }
00142 
00143 void CallGraphNode::dump() const { print(std::cerr); }
00144 
00145 void CallGraph::print(std::ostream &OS, const Module *M) const {
00146   OS << "CallGraph Root is: ";
00147   if (Function *F = getRoot()->getFunction())
00148     OS << F->getName() << "\n";
00149   else
00150     OS << "<<null function: 0x" << getRoot() << ">>\n";
00151   
00152   for (CallGraph::const_iterator I = begin(), E = end(); I != E; ++I)
00153     I->second->print(OS);
00154 }
00155 
00156 void CallGraph::dump() const {
00157   print(std::cerr, 0);
00158 }
00159 
00160 
00161 //===----------------------------------------------------------------------===//
00162 // Implementations of public modification methods
00163 //
00164 
00165 // removeFunctionFromModule - Unlink the function from this module, returning
00166 // it.  Because this removes the function from the module, the call graph node
00167 // is destroyed.  This is only valid if the function does not call any other
00168 // functions (ie, there are no edges in it's CGN).  The easiest way to do this
00169 // is to dropAllReferences before calling this.
00170 //
00171 Function *CallGraph::removeFunctionFromModule(CallGraphNode *CGN) {
00172   assert(CGN->CalledFunctions.empty() && "Cannot remove function from call "
00173          "graph if it references other functions!");
00174   Function *F = CGN->getFunction(); // Get the function for the call graph node
00175   delete CGN;                       // Delete the call graph node for this func
00176   FunctionMap.erase(F);             // Remove the call graph node from the map
00177 
00178   Mod->getFunctionList().remove(F);
00179   return F;
00180 }
00181 
00182 // changeFunction - This method changes the function associated with this
00183 // CallGraphNode, for use by transformations that need to change the prototype
00184 // of a Function (thus they must create a new Function and move the old code
00185 // over).
00186 void CallGraph::changeFunction(Function *OldF, Function *NewF) {
00187   iterator I = FunctionMap.find(OldF);
00188   CallGraphNode *&New = FunctionMap[NewF];
00189   assert(I != FunctionMap.end() && I->second && !New &&
00190          "OldF didn't exist in CG or NewF already does!");
00191   New = I->second;
00192   New->F = NewF;
00193   FunctionMap.erase(I);
00194 }
00195 
00196 
00197 void CallGraph::stub() {}
00198 
00199 void CallGraphNode::removeCallEdgeTo(CallGraphNode *Callee) {
00200   for (unsigned i = CalledFunctions.size(); ; --i) {
00201     assert(i && "Cannot find callee to remove!");
00202     if (CalledFunctions[i-1] == Callee) {
00203       CalledFunctions.erase(CalledFunctions.begin()+i-1);
00204       return;
00205     }
00206   }
00207 }
00208 
00209 // removeAnyCallEdgeTo - This method removes any call edges from this node to
00210 // the specified callee function.  This takes more time to execute than
00211 // removeCallEdgeTo, so it should not be used unless necessary.
00212 void CallGraphNode::removeAnyCallEdgeTo(CallGraphNode *Callee) {
00213   for (unsigned i = 0, e = CalledFunctions.size(); i != e; ++i)
00214     if (CalledFunctions[i] == Callee) {
00215       CalledFunctions[i] = CalledFunctions.back();
00216       CalledFunctions.pop_back();
00217       --i; --e;
00218     }
00219 }