lib/Analysis/IPA/CallGraph.cpp

   1 //===- CallGraph.cpp - Build a Module's call graph ------------------------===//
   2 //
   3 // This file implements call graph construction (from a module), and will
   4 // eventually implement call graph serialization and deserialization for
   5 // annotation support.
   6 //
   7 // This call graph represents a dynamic method invocation as a null method node.
   8 // A call graph may only have up to one null method node that represents all of
   9 // the dynamic method invocations.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "llvm/Analysis/CallGraph.h"
  14 #include "llvm/Module.h"
  15 #include "llvm/Method.h"
  16 #include "llvm/iOther.h"
  17 #include "llvm/iTerminators.h"
  18 #include "llvm/Support/InstIterator.h"// FIXME: CallGraph should use method uses
  19 #include "Support/STLExtras.h"
  20 #include <algorithm>
  21 #include <iostream>
  22
  23 AnalysisID CallGraph::ID(AnalysisID::create<CallGraph>());
  24
  25 // getNodeFor - Return the node for the specified method or create one if it
  26 // does not already exist.
  27 //
  28 CallGraphNode *CallGraph::getNodeFor(Method *M) {
  29   iterator I = MethodMap.find(M);
  30   if (I != MethodMap.end()) return I->second;
  31
  32   assert(M->getParent() == Mod && "Method not in current module!");
  33   CallGraphNode *New = new CallGraphNode(M);
  34
  35   MethodMap.insert(std::make_pair(M, New));
  36   return New;
  37 }
  38
  39 // addToCallGraph - Add a method to the call graph, and link the node to all of
  40 // the methods that it calls.
  41 //
  42 void CallGraph::addToCallGraph(Method *M) {
  43   CallGraphNode *Node = getNodeFor(M);
  44
  45   // If this method has external linkage,
  46   if (!M->hasInternalLinkage())
  47     Root->addCalledMethod(Node);
  48
  49   for (inst_iterator I = inst_begin(M), E = inst_end(M); I != E; ++I) {
  50     // Dynamic calls will cause Null nodes to be created
  51     if (CallInst *CI = dyn_cast<CallInst>(*I))
  52       Node->addCalledMethod(getNodeFor(CI->getCalledMethod()));
  53     else if (InvokeInst *II = dyn_cast<InvokeInst>(*I))
  54       Node->addCalledMethod(getNodeFor(II->getCalledMethod()));
  55   }
  56 }
  57
  58 bool CallGraph::run(Module *TheModule) {
  59   destroy();
  60
  61   Mod = TheModule;
  62
  63   // Create the root node of the module...
  64   Root = new CallGraphNode(0);
  65
  66   // Add every method to the call graph...
  67   for_each(Mod->begin(), Mod->end(), bind_obj(this,&CallGraph::addToCallGraph));
  68
  69   return false;
  70 }
  71
  72 void CallGraph::destroy() {
  73   for (MethodMapTy::iterator I = MethodMap.begin(), E = MethodMap.end();
  74        I != E; ++I) {
  75     delete I->second;
  76   }
  77   MethodMap.clear();
  78 }
  79
  80
  81 void WriteToOutput(const CallGraphNode *CGN, std::ostream &o) {
  82   if (CGN->getMethod())
  83     o << "Call graph node for method: '" << CGN->getMethod()->getName() <<"'\n";
  84   else
  85     o << "Call graph node null method:\n";
  86
  87   for (unsigned i = 0; i < CGN->size(); ++i)
  88     o << "  Calls method '" << (*CGN)[i]->getMethod()->getName() << "'\n";
  89   o << "\n";
  90 }
  91
  92 void WriteToOutput(const CallGraph &CG, std::ostream &o) {
  93   WriteToOutput(CG.getRoot(), o);
  94   for (CallGraph::const_iterator I = CG.begin(), E = CG.end(); I != E; ++I)
  95     o << I->second;
  96 }
  97
  98
  99 //===----------------------------------------------------------------------===//
 100 // Implementations of public modification methods
 101 //
 102
 103 // Methods to keep a call graph up to date with a method that has been
 104 // modified
 105 //
 106 void CallGraph::addMethodToModule(Method *Meth) {
 107   assert(0 && "not implemented");
 108   abort();
 109 }
 110
 111 // removeMethodFromModule - Unlink the method from this module, returning it.
 112 // Because this removes the method from the module, the call graph node is
 113 // destroyed.  This is only valid if the method does not call any other
 114 // methods (ie, there are no edges in it's CGN).  The easiest way to do this
 115 // is to dropAllReferences before calling this.
 116 //
 117 Method *CallGraph::removeMethodFromModule(CallGraphNode *CGN) {
 118   assert(CGN->CalledMethods.empty() && "Cannot remove method from call graph"
 119          " if it references other methods!");
 120   Method *M = CGN->getMethod();  // Get the method for the call graph node
 121   delete CGN;                    // Delete the call graph node for this method
 122   MethodMap.erase(M);            // Remove the call graph node from the map
 123
 124   Mod->getMethodList().remove(M);
 125   return M;
 126 }
 127