lib/Analysis/IPA/CallGraph.cpp

   1 //===- CallGraph.cpp - Build a Module's call graph ------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the CallGraph class and provides the BasicCallGraph
  11 // default implementation.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "llvm/Analysis/CallGraph.h"
  16 #include "llvm/Module.h"
  17 #include "llvm/Instructions.h"
  18 #include "llvm/Support/CallSite.h"
  19 #include <iostream>
  20 using namespace llvm;
  21
  22 void llvm::BasicCallGraphStub() {}
  23
  24 static bool isOnlyADirectCall(Function *F, CallSite CS) {
  25   if (!CS.getInstruction()) return false;
  26   for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end(); I != E; ++I)
  27     if (*I == F) return false;
  28   return true;
  29 }
  30
  31 namespace {
  32
  33 //===----------------------------------------------------------------------===//
  34 // BasicCallGraph class definition
  35 //
  36 class BasicCallGraph : public CallGraph, public ModulePass {
  37   // Root is root of the call graph, or the external node if a 'main' function
  38   // couldn't be found.
  39   //
  40   CallGraphNode *Root;
  41
  42   // ExternalCallingNode - This node has edges to all external functions and
  43   // those internal functions that have their address taken.
  44   CallGraphNode *ExternalCallingNode;
  45
  46   // CallsExternalNode - This node has edges to it from all functions making
  47   // indirect calls or calling an external function.
  48   CallGraphNode *CallsExternalNode;
  49
  50 public:
  51   BasicCallGraph() : Root(0), ExternalCallingNode(0), CallsExternalNode(0) {}
  52   ~BasicCallGraph() { destroy(); }
  53
  54   // runOnModule - Compute the call graph for the specified module.
  55   virtual bool runOnModule(Module &M) {
  56     destroy();
  57     CallGraph::initialize(M);
  58
  59     ExternalCallingNode = getNodeFor(0);
  60     CallsExternalNode = new CallGraphNode(0);
  61     Root = 0;
  62
  63     // Add every function to the call graph...
  64     for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
  65       addToCallGraph(I);
  66
  67     // If we didn't find a main function, use the external call graph node
  68     if (Root == 0) Root = ExternalCallingNode;
  69
  70     return false;
  71   }
  72
  73   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  74     AU.setPreservesAll();
  75   }
  76
  77   virtual void print(std::ostream &o, const Module *M) const {
  78     o << "CallGraph Root is: ";
  79     if (Function *F = getRoot()->getFunction())
  80       o << F->getName() << "\n";
  81     else
  82       o << "<<null function: 0x" << getRoot() << ">>\n";
  83
  84     CallGraph::print(o, M);
  85   }
  86
  87   virtual void releaseMemory() {
  88     destroy();
  89   }
  90
  91   /// dump - Print out this call graph.
  92   ///
  93   inline void dump() const {
  94     print(std::cerr, Mod);
  95   }
  96
  97   CallGraphNode* getExternalCallingNode() const { return ExternalCallingNode; }
  98   CallGraphNode* getCallsExternalNode()   const { return CallsExternalNode; }
  99
 100   // getRoot - Return the root of the call graph, which is either main, or if
 101   // main cannot be found, the external node.
 102   //
 103   CallGraphNode *getRoot()             { return Root; }
 104   const CallGraphNode *getRoot() const { return Root; }
 105
 106 private:
 107   //===---------------------------------------------------------------------
 108   // Implementation of CallGraph construction
 109   //
 110   // getNodeFor - Return the node for the specified function or create one if it
 111   // does not already exist.
 112   //
 113
 114   CallGraphNode *getNodeFor(Function *F) {
 115     CallGraphNode *&CGN = FunctionMap[F];
 116     if (CGN) return CGN;
 117
 118     assert((!F || F->getParent() == Mod) && "Function not in current module!");
 119     return CGN = new CallGraphNode(F);
 120   }
 121
 122   //
 123   // addToCallGraph - Add a function to the call graph, and link the node to all
 124   // of the functions that it calls.
 125   //
 126   void addToCallGraph(Function *F) {
 127     CallGraphNode *Node = getNodeFor(F);
 128
 129     // If this function has external linkage, anything could call it...
 130     if (!F->hasInternalLinkage()) {
 131       ExternalCallingNode->addCalledFunction(Node);
 132
 133       // Found the entry point?
 134       if (F->getName() == "main") {
 135         if (Root)    // Found multiple external mains?  Don't pick one.
 136           Root = ExternalCallingNode;
 137         else
 138           Root = Node;          // Found a main, keep track of it!
 139       }
 140     }
 141
 142     // If this function is not defined in this translation unit, it could call
 143     // anything.
 144     if (F->isExternal() && !F->getIntrinsicID())
 145       Node->addCalledFunction(CallsExternalNode);
 146
 147     // Loop over all of the users of the function... looking for callers...
 148     //
 149     bool isUsedExternally = false;
 150     for (Value::use_iterator I = F->use_begin(), E = F->use_end(); I != E; ++I){
 151       if (Instruction *Inst = dyn_cast<Instruction>(*I)) {
 152         if (isOnlyADirectCall(F, CallSite::get(Inst)))
 153           getNodeFor(Inst->getParent()->getParent())->addCalledFunction(Node);
 154         else
 155           isUsedExternally = true;
 156       } else if (GlobalValue *GV = dyn_cast<GlobalValue>(*I)) {
 157         for (Value::use_iterator I = GV->use_begin(), E = GV->use_end();
 158              I != E; ++I)
 159           if (Instruction *Inst = dyn_cast<Instruction>(*I)) {
 160           if (isOnlyADirectCall(F, CallSite::get(Inst)))
 161             getNodeFor(Inst->getParent()->getParent())->addCalledFunction(Node);
 162           else
 163             isUsedExternally = true;
 164           } else {
 165             isUsedExternally = true;
 166           }
 167       } else {                        // Can't classify the user!
 168         isUsedExternally = true;
 169       }
 170     }
 171     if (isUsedExternally)
 172       ExternalCallingNode->addCalledFunction(Node);
 173
 174   // Look for an indirect function call...
 175     for (Function::iterator BB = F->begin(), BBE = F->end(); BB != BBE; ++BB)
 176       for (BasicBlock::iterator II = BB->begin(), IE = BB->end();
 177            II != IE; ++II) {
 178       CallSite CS = CallSite::get(II);
 179       if (CS.getInstruction() && !CS.getCalledFunction())
 180         Node->addCalledFunction(CallsExternalNode);
 181       }
 182   }
 183
 184   //
 185   // destroy - Release memory for the call graph
 186   virtual void destroy() {
 187     if (!CallsExternalNode) {
 188       delete CallsExternalNode;
 189       CallsExternalNode = 0;
 190     }
 191   }
 192 };
 193
 194 RegisterAnalysisGroup<CallGraph> X("Call Graph");
 195 RegisterOpt<BasicCallGraph> Y("basiccg", "Basic CallGraph Construction");
 196 RegisterAnalysisGroup<CallGraph, BasicCallGraph, true> Z;
 197
 198 } //End anonymous namespace
 199
 200 void CallGraph::initialize(Module &M) {
 201   destroy();
 202   Mod = &M;
 203 }
 204
 205 void CallGraph::destroy() {
 206   if(!FunctionMap.size()) {
 207     for (FunctionMapTy::iterator I = FunctionMap.begin(), E = FunctionMap.end();
 208         I != E; ++I)
 209       delete I->second;
 210     FunctionMap.clear();
 211   }
 212 }
 213
 214 void CallGraph::print(std::ostream &OS, const Module *M) const {
 215   for (CallGraph::const_iterator I = begin(), E = end(); I != E; ++I)
 216     I->second->print(OS);
 217 }
 218
 219 void CallGraph::dump() const {
 220   print(std::cerr, 0);
 221 }
 222
 223 //===----------------------------------------------------------------------===//
 224 // Implementations of public modification methods
 225 //
 226
 227 // removeFunctionFromModule - Unlink the function from this module, returning
 228 // it.  Because this removes the function from the module, the call graph node
 229 // is destroyed.  This is only valid if the function does not call any other
 230 // functions (ie, there are no edges in it's CGN).  The easiest way to do this
 231 // is to dropAllReferences before calling this.
 232 //
 233 Function *CallGraph::removeFunctionFromModule(CallGraphNode *CGN) {
 234   assert(CGN->CalledFunctions.empty() && "Cannot remove function from call "
 235          "graph if it references other functions!");
 236   Function *F = CGN->getFunction(); // Get the function for the call graph node
 237   delete CGN;                       // Delete the call graph node for this func
 238   FunctionMap.erase(F);             // Remove the call graph node from the map
 239
 240   Mod->getFunctionList().remove(F);
 241   return F;
 242 }
 243
 244 // changeFunction - This method changes the function associated with this
 245 // CallGraphNode, for use by transformations that need to change the prototype
 246 // of a Function (thus they must create a new Function and move the old code
 247 // over).
 248 void CallGraph::changeFunction(Function *OldF, Function *NewF) {
 249   iterator I = FunctionMap.find(OldF);
 250   CallGraphNode *&New = FunctionMap[NewF];
 251   assert(I != FunctionMap.end() && I->second && !New &&
 252          "OldF didn't exist in CG or NewF already does!");
 253   New = I->second;
 254   New->F = NewF;
 255   FunctionMap.erase(I);
 256 }
 257
 258 void CallGraph::stub() {}
 259
 260 void CallGraphNode::print(std::ostream &OS) const {
 261   if (Function *F = getFunction())
 262     OS << "Call graph node for function: '" << F->getName() <<"'\n";
 263   else
 264     OS << "Call graph node <<null function: 0x" << this << ">>:\n";
 265
 266   for (const_iterator I = begin(), E = end(); I != E; ++I)
 267     if ((*I)->getFunction())
 268       OS << "  Calls function '" << (*I)->getFunction()->getName() << "'\n";
 269   else
 270     OS << "  Calls external node\n";
 271   OS << "\n";
 272 }
 273
 274 void CallGraphNode::dump() const { print(std::cerr); }
 275
 276 void CallGraphNode::removeCallEdgeTo(CallGraphNode *Callee) {
 277   for (unsigned i = CalledFunctions.size(); ; --i) {
 278     assert(i && "Cannot find callee to remove!");
 279     if (CalledFunctions[i-1] == Callee) {
 280       CalledFunctions.erase(CalledFunctions.begin()+i-1);
 281       return;
 282     }
 283   }
 284 }
 285
 286 // removeAnyCallEdgeTo - This method removes any call edges from this node to
 287 // the specified callee function.  This takes more time to execute than
 288 // removeCallEdgeTo, so it should not be used unless necessary.
 289 void CallGraphNode::removeAnyCallEdgeTo(CallGraphNode *Callee) {
 290   for (unsigned i = 0, e = CalledFunctions.size(); i != e; ++i)
 291     if (CalledFunctions[i] == Callee) {
 292       CalledFunctions[i] = CalledFunctions.back();
 293       CalledFunctions.pop_back();
 294       --i; --e;
 295     }
 296 }