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/Analysis/Writer.h"
  15 #include "llvm/Module.h"
  16 #include "llvm/Method.h"
  17 #include "llvm/iOther.h"
  18 #include "llvm/iTerminators.h"
  19 #include "Support/STLExtras.h"
  20 #include <algorithm>
  21
  22 // getNodeFor - Return the node for the specified method or create one if it
  23 // does not already exist.
  24 //
  25 cfg::CallGraphNode *cfg::CallGraph::getNodeFor(Method *M) {
  26   iterator I = MethodMap.find(M);
  27   if (I != MethodMap.end()) return I->second;
  28
  29   assert(M->getParent() == Mod && "Method not in current module!");
  30   CallGraphNode *New = new CallGraphNode(M);
  31
  32   MethodMap.insert(pair<const Method*, CallGraphNode*>(M, New));
  33   return New;
  34 }
  35
  36 // addToCallGraph - Add a method to the call graph, and link the node to all of
  37 // the methods that it calls.
  38 //
  39 void cfg::CallGraph::addToCallGraph(Method *M) {
  40   CallGraphNode *Node = getNodeFor(M);
  41
  42   // If this method has external linkage,
  43   if (!M->hasInternalLinkage())
  44     Root->addCalledMethod(Node);
  45
  46   for (Method::inst_iterator I = M->inst_begin(), E = M->inst_end();
  47        I != E; ++I) {
  48     // Dynamic calls will cause Null nodes to be created
  49     if (CallInst *CI = dyn_cast<CallInst>(*I))
  50       Node->addCalledMethod(getNodeFor(CI->getCalledMethod()));
  51     else if (InvokeInst *II = dyn_cast<InvokeInst>(*I))
  52       Node->addCalledMethod(getNodeFor(II->getCalledMethod()));
  53   }
  54 }
  55
  56 cfg::CallGraph::CallGraph(Module *TheModule) {
  57   Mod = TheModule;
  58
  59   // Create the root node of the module...
  60   Root = new CallGraphNode(0);
  61
  62   // Add every method to the call graph...
  63   for_each(Mod->begin(), Mod->end(), bind_obj(this,&CallGraph::addToCallGraph));
  64 }
  65
  66 cfg::CallGraph::~CallGraph() {
  67   for (MethodMapTy::iterator I = MethodMap.begin(), E = MethodMap.end();
  68        I != E; ++I) {
  69     delete I->second;
  70   }
  71 }
  72
  73
  74 void cfg::WriteToOutput(const CallGraphNode *CGN, ostream &o) {
  75   if (CGN->getMethod())
  76     o << "Call graph node for method: '" << CGN->getMethod()->getName() <<"'\n";
  77   else
  78     o << "Call graph node null method:\n";
  79
  80   for (unsigned i = 0; i < CGN->size(); ++i)
  81     o << "  Calls method '" << (*CGN)[i]->getMethod()->getName() << "'\n";
  82   o << endl;
  83 }
  84
  85 void cfg::WriteToOutput(const CallGraph &CG, ostream &o) {
  86   WriteToOutput(CG.getRoot(), o);
  87   for (CallGraph::const_iterator I = CG.begin(), E = CG.end(); I != E; ++I)
  88     o << I->second;
  89 }
  90
  91
  92 //===----------------------------------------------------------------------===//
  93 // Implementations of public modification methods
  94 //
  95
  96 // Methods to keep a call graph up to date with a method that has been
  97 // modified
  98 //
  99 void cfg::CallGraph::addMethodToModule(Method *Meth) {
 100   assert(0 && "not implemented");
 101   abort();
 102 }
 103
 104 // removeMethodFromModule - Unlink the method from this module, returning it.
 105 // Because this removes the method from the module, the call graph node is
 106 // destroyed.  This is only valid if the method does not call any other
 107 // methods (ie, there are no edges in it's CGN).  The easiest way to do this
 108 // is to dropAllReferences before calling this.
 109 //
 110 Method *cfg::CallGraph::removeMethodFromModule(CallGraphNode *CGN) {
 111   assert(CGN->CalledMethods.empty() && "Cannot remove method from call graph"
 112          " if it references other methods!");
 113   Method *M = CGN->getMethod();  // Get the method for the call graph node
 114   delete CGN;                    // Delete the call graph node for this method
 115   MethodMap.erase(M);            // Remove the call graph node from the map
 116
 117   Mod->getMethodList().remove(M);
 118   return M;
 119 }
 120
 121
 122 //
 123 // Checks if a method contains any call instructions.
 124 // Note that this uses the call graph only if one is provided.
 125 // It does not build the call graph.
 126 //
 127 bool IsLeafMethod(const Method* M, const cfg::CallGraph* CG) {
 128   if (CG) {
 129     const cfg::CallGraphNode *cgn = (*CG)[M];
 130     return (cgn->begin() == cgn->end());
 131   }
 132
 133   for (Method::const_inst_iterator I = M->inst_begin(), E = M->inst_end();
 134        I != E; ++I)
 135     if ((*I)->getOpcode() == Instruction::Call)
 136       return false;
 137   return true;
 138 }
 139
 140