Initial support for construction of a call graph

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@660 91177308-0d34-0410-b5e6-96231b3b80d8

2 files changed, 154 insertions, 0 deletions

diff --git a/include/llvm/Analysis/CallGraph.h b/include/llvm/Analysis/CallGraph.h
new file mode 100644
index 0000000000..0683623454
--- /dev/null
+++ b/include/llvm/Analysis/CallGraph.h
@@ -0,0 +1,88 @@
+//===- llvm/Analysis/CallGraph.h - Build a Module's call graph ---*- C++ -*--=//
+//
+// This interface is used to build and manipulate a call graph, which is a very 
+// useful tool for interprocedural optimization.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_CALLGRAPH_H
+#define LLVM_ANALYSIS_CALLGRAPH_H
+
+#include <map>
+#include <vector>
+class Method;
+class Module;
+
+namespace cfg {
+
+class CallGraph;
+class CallGraphNode {
+  Method *Meth;
+  vector<CallGraphNode*> CalledMethods;
+
+  CallGraphNode(const CallGraphNode &);           // Do not implement
+public:
+  typedef vector<CallGraphNode*>::iterator iterator;
+  typedef vector<CallGraphNode*>::const_iterator const_iterator;
+
+  // getMethod - Return the method that this call graph node represents...
+  Method *getMethod() const { return Meth; }
+
+  inline iterator begin() { return CalledMethods.begin(); }
+  inline iterator end()   { return CalledMethods.end();   }
+  inline const_iterator begin() const { return CalledMethods.begin(); }
+  inline const_iterator end()   const { return CalledMethods.end();   }
+  inline unsigned size() const { return CalledMethods.size(); }
+
+  inline CallGraphNode *operator[](unsigned i) const { return CalledMethods[i];}
+
+
+private:                    // Stuff to construct the node, used by CallGraph
+  friend class CallGraph;
+
+  // CallGraphNode ctor - Create a node for the specified method...
+  inline CallGraphNode(Method *M) : Meth(M) {}
+  
+  // addCalledMethod add a method to the list of methods called by this one
+  void addCalledMethod(CallGraphNode *M) {
+    CalledMethods.push_back(M);
+  }
+};
+
+
+class CallGraph {
+  Module *Mod;
+  typedef map<const Method *, CallGraphNode *> MethodMapTy;
+  MethodMapTy MethodMap;
+public:
+  CallGraph(Module *TheModule);
+
+  typedef MethodMapTy::iterator iterator;
+  typedef MethodMapTy::const_iterator const_iterator;
+
+  inline const_iterator begin() const { return MethodMap.begin(); }
+  inline const_iterator end()   const { return MethodMap.end();   }
+
+  inline const CallGraphNode *operator[](const Method *M) const {
+    const_iterator I = MethodMap.find(M);
+    assert(I != MethodMap.end() && "Method not in callgraph!");
+    return I->second;
+  }
+
+private:   // Implementation of CallGraph construction
+
+  // getNodeFor - Return the node for the specified method or create one if it
+  // does not already exist.
+  //
+  CallGraphNode *getNodeFor(Method *M);
+
+  // addToCallGraph - Add a method to the call graph, and link the node to all
+  // of the methods that it calls.
+  //
+  void addToCallGraph(Method *M);
+};
+
+
+}  // end namespace cfg
+
+#endif
diff --git a/lib/Analysis/IPA/CallGraph.cpp b/lib/Analysis/IPA/CallGraph.cpp
new file mode 100644
index 0000000000..b1a272f032
--- /dev/null
+++ b/lib/Analysis/IPA/CallGraph.cpp
@@ -0,0 +1,66 @@
+//===- CallGraph.cpp - Build a Module's call graph --------------------------=//
+//
+// This file implements call graph construction (from a module), and will
+// eventually implement call graph serialization and deserialization for
+// annotation support.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/CallGraph.h"
+#include "llvm/Analysis/Writer.h"
+#include "llvm/Support/STLExtras.h"
+#include "llvm/Module.h"
+#include "llvm/Method.h"
+#include "llvm/iOther.h"
+#include <algorithm>
+
+using namespace cfg;
+
+// getNodeFor - Return the node for the specified method or create one if it
+// does not already exist.
+//
+CallGraphNode *CallGraph::getNodeFor(Method *M) {
+  iterator I = MethodMap.find(M);
+  if (I != MethodMap.end()) return I->second;
+
+  assert(M->getParent() == Mod && "Method not in current module!");
+  CallGraphNode *New = new CallGraphNode(M);
+
+  MethodMap.insert(pair<const Method*, CallGraphNode*>(M, New));
+  return New;
+}
+
+// addToCallGraph - Add a method to the call graph, and link the node to all of
+// the methods that it calls.
+//
+void CallGraph::addToCallGraph(Method *M) {
+  CallGraphNode *Node = getNodeFor(M);
+
+  for (Method::inst_iterator II = M->inst_begin(), IE = M->inst_end();
+       II != IE; ++II) {
+    if (II->getOpcode() == Instruction::Call) {
+      CallInst *CI = (CallInst*)*II;
+      Node->addCalledMethod(getNodeFor(CI->getCalledMethod()));
+    }
+  }
+}
+
+CallGraph::CallGraph(Module *TheModule) {
+  Mod = TheModule;
+
+  // Add every method to the call graph...
+  for_each(Mod->begin(), Mod->end(), bind_obj(this,&CallGraph::addToCallGraph));
+}
+
+
+void cfg::WriteToOutput(const CallGraphNode *CGN, ostream &o) {
+  o << "Call graph node for method: '" << CGN->getMethod()->getName() << "'\n";
+  for (unsigned i = 0; i < CGN->size(); ++i)
+    o << "  Calls method '" << (*CGN)[i]->getMethod()->getName() << "'\n";
+  o << endl;
+}
+
+void cfg::WriteToOutput(const CallGraph &CG, ostream &o) {
+  for (CallGraph::const_iterator I = CG.begin(), E = CG.end(); I != E; ++I)
+    o << I->second;
+}