-//===- llvm/Analysis/CallGraph.h - Build a Module's call graph ---*- C++ -*--=//
+//===- CallGraph.cpp - Build a Module's call graph ------------------------===//
//
// This interface is used to build and manipulate a call graph, which is a very
// useful tool for interprocedural optimization.
//
-// This call graph represents a dynamic method invocation as a null method node.
-// A call graph may only have up to one null method node that represents all of
-// the dynamic method invocations.
+// Every method in a module is represented as a node in the call graph. The
+// callgraph node keeps track of which methods the are called by the method
+// corresponding to the node.
//
-// Additionally, the 'root' node of a call graph represents the "entry point"
-// node of the graph, which has an edge to every external method in the graph.
-// This node has a null method pointer.
+// A call graph will contain nodes where the method that they correspond to is
+// null. This 'external' node is used to represent control flow that is not
+// represented (or analyzable) in the module. As such, the external node will
+// have edges to methods with the following properties:
+// 1. All methods in the module without internal linkage, since they could
+// be called by methods outside of the our analysis capability.
+// 2. All methods whose address is used for something more than a direct call,
+// for example being stored into a memory location. Since they may be
+// called by an unknown caller later, they must be tracked as such.
+//
+// Similarly, methods have a call edge to the external node iff:
+// 1. The method is external, reflecting the fact that they could call
+// anything without internal linkage or that has its address taken.
+// 2. The method contains an indirect method call.
+//
+// As an extension in the future, there may be multiple nodes with a null
+// method. These will be used when we can prove (through pointer analysis) that
+// an indirect call site can call only a specific set of methods.
+//
+// Because of these properties, the CallGraph captures a conservative superset
+// of all of the caller-callee relationships, which is useful for
+// transformations.
+//
+// The CallGraph class also attempts to figure out what the root of the
+// CallGraph is, which is currently does by looking for a method named 'main'.
+// If no method named 'main' is found, the external node is used as the entry
+// node, reflecting the fact that any method without internal linkage could
+// be called into (which is common for libraries).
//
//===----------------------------------------------------------------------===//
#include "llvm/Pass.h"
class Method;
class Module;
-class CallGraph;
-
-//===----------------------------------------------------------------------===//
-// CallGraphNode class definition
-//
-class CallGraphNode {
- Method *Meth;
- std::vector<CallGraphNode*> CalledMethods;
-
- CallGraphNode(const CallGraphNode &); // Do not implement
-public:
- typedef std::vector<CallGraphNode*>::iterator iterator;
- typedef std::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];}
-
- void removeAllCalledMethods() {
- CalledMethods.clear();
- }
-
-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 CallGraphNode;
//===----------------------------------------------------------------------===//
// CallGraph class definition
typedef std::map<const Method *, CallGraphNode *> MethodMapTy;
MethodMapTy MethodMap; // Map from a method to its node
- CallGraphNode *Root;
+ // Root is root of the call graph, or the external node if a 'main' function
+ // couldn't be found. ExternalNode is equivalent to (*this)[0].
+ //
+ CallGraphNode *Root, *ExternalNode;
public:
- static AnalysisID ID; // We are an analysis, we must have an ID
-
- CallGraph(AnalysisID AID) : Root(0) { assert(AID == ID); }
- ~CallGraph() { destroy(); }
+ //===---------------------------------------------------------------------
+ // Accessors...
+ //
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(); }
+
+ // Subscripting operators, return the call graph node for the provided method
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;
}
+ //===---------------------------------------------------------------------
// Methods to keep a call graph up to date with a method that has been
// modified
//
- void addMethodToModule(Method *Meth); // TODO IMPLEMENT
+ void addMethodToModule(Method *Meth);
// removeMethodFromModule - Unlink the method from this module, returning it.
return removeMethodFromModule((*this)[Meth]);
}
+
+ //===---------------------------------------------------------------------
+ // Pass infrastructure interface glue code...
+ //
+ static AnalysisID ID; // We are an analysis, we must have an ID
+
+ CallGraph(AnalysisID AID) : Root(0) { assert(AID == ID); }
+ ~CallGraph() { destroy(); }
+
// run - Compute the call graph for the specified module.
virtual bool run(Module *TheModule);
destroy();
}
-private: // Implementation of CallGraph construction
- void destroy();
+private:
+ //===---------------------------------------------------------------------
+ // Implementation of CallGraph construction
+ //
// getNodeFor - Return the node for the specified method or create one if it
// does not already exist.
// of the methods that it calls.
//
void addToCallGraph(Method *M);
+
+ // destroy - Release memory for the call graph
+ void destroy();
};
+//===----------------------------------------------------------------------===//
+// CallGraphNode class definition
+//
+class CallGraphNode {
+ Method *Meth;
+ std::vector<CallGraphNode*> CalledMethods;
+
+ CallGraphNode(const CallGraphNode &); // Do not implement
+public:
+ //===---------------------------------------------------------------------
+ // Accessor methods...
+ //
+
+ typedef std::vector<CallGraphNode*>::iterator iterator;
+ typedef std::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(); }
+
+ // Subscripting operator - Return the i'th called method...
+ //
+ inline CallGraphNode *operator[](unsigned i) const { return CalledMethods[i];}
+
+
+ //===---------------------------------------------------------------------
+ // Methods to keep a call graph up to date with a method that has been
+ // modified
+ //
+
+ void removeAllCalledMethods() {
+ CalledMethods.clear();
+ }
+
+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);
+ }
+};
+
+
+
//===----------------------------------------------------------------------===//
// GraphTraits specializations for call graphs so that they can be treated as
// graphs by the generic graph algorithms...
//===- 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.
+// This interface is used to build and manipulate a call graph, which is a very
+// useful tool for interprocedural optimization.
//
-// This call graph represents a dynamic method invocation as a null method node.
-// A call graph may only have up to one null method node that represents all of
-// the dynamic method invocations.
+// Every method in a module is represented as a node in the call graph. The
+// callgraph node keeps track of which methods the are called by the method
+// corresponding to the node.
+//
+// A call graph will contain nodes where the method that they correspond to is
+// null. This 'external' node is used to represent control flow that is not
+// represented (or analyzable) in the module. As such, the external node will
+// have edges to methods with the following properties:
+// 1. All methods in the module without internal linkage, since they could
+// be called by methods outside of the our analysis capability.
+// 2. All methods whose address is used for something more than a direct call,
+// for example being stored into a memory location. Since they may be
+// called by an unknown caller later, they must be tracked as such.
+//
+// Similarly, methods have a call edge to the external node iff:
+// 1. The method is external, reflecting the fact that they could call
+// anything without internal linkage or that has its address taken.
+// 2. The method contains an indirect method call.
+//
+// As an extension in the future, there may be multiple nodes with a null
+// method. These will be used when we can prove (through pointer analysis) that
+// an indirect call site can call only a specific set of methods.
+//
+// Because of these properties, the CallGraph captures a conservative superset
+// of all of the caller-callee relationships, which is useful for
+// transformations.
+//
+// The CallGraph class also attempts to figure out what the root of the
+// CallGraph is, which is currently does by looking for a method named 'main'.
+// If no method named 'main' is found, the external node is used as the entry
+// node, reflecting the fact that any method without internal linkage could
+// be called into (which is common for libraries).
//
//===----------------------------------------------------------------------===//
#include "llvm/Method.h"
#include "llvm/iOther.h"
#include "llvm/iTerminators.h"
-#include "llvm/Support/InstIterator.h"// FIXME: CallGraph should use method uses
#include "Support/STLExtras.h"
#include <algorithm>
#include <iostream>
// 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);
+ CallGraphNode *&CGN = MethodMap[M];
+ if (CGN) return CGN;
- MethodMap.insert(std::make_pair(M, New));
- return New;
+ assert((!M || M->getParent() == Mod) && "Method not in current module!");
+ return CGN = new CallGraphNode(M);
}
// addToCallGraph - Add a method to the call graph, and link the node to all of
CallGraphNode *Node = getNodeFor(M);
// If this method has external linkage,
- if (!M->hasInternalLinkage())
- Root->addCalledMethod(Node);
-
- for (inst_iterator I = inst_begin(M), E = inst_end(M); I != E; ++I) {
- // Dynamic calls will cause Null nodes to be created
- if (CallInst *CI = dyn_cast<CallInst>(*I))
- Node->addCalledMethod(getNodeFor(CI->getCalledMethod()));
- else if (InvokeInst *II = dyn_cast<InvokeInst>(*I))
- Node->addCalledMethod(getNodeFor(II->getCalledMethod()));
+ if (!M->hasInternalLinkage()) {
+ ExternalNode->addCalledMethod(Node);
+
+ // Found the entry point?
+ if (M->getName() == "main") {
+ if (Root)
+ Root = ExternalNode; // Found multiple external mains? Don't pick one.
+ else
+ Root = Node; // Found a main, keep track of it!
+ }
+ } else if (M->isExternal()) { // Not defined in this xlation unit?
+ Node->addCalledMethod(ExternalNode); // It could call anything...
+ }
+
+ // Loop over all of the users of the method... looking for callers...
+ //
+ for (Value::use_iterator I = M->use_begin(), E = M->use_end(); I != E; ++I) {
+ User *U = *I;
+ if (CallInst *CI = dyn_cast<CallInst>(U))
+ getNodeFor(CI->getParent()->getParent())->addCalledMethod(Node);
+ else if (InvokeInst *II = dyn_cast<InvokeInst>(U))
+ getNodeFor(II->getParent()->getParent())->addCalledMethod(Node);
+ else // Can't classify the user!
+ ExternalNode->addCalledMethod(Node);
+ }
+
+ // Look for an indirect method call...
+ for (Method::iterator BBI = M->begin(), BBE = M->end(); BBI != BBE; ++BBI) {
+ BasicBlock *BB = *BBI;
+ for (BasicBlock::iterator II = BB->begin(), IE = BB->end(); II != IE; ++II){
+ Instruction *I = *II;
+
+ if (CallInst *CI = dyn_cast<CallInst>(I)) {
+ if (CI->getCalledMethod() == 0)
+ Node->addCalledMethod(ExternalNode);
+ } else if (InvokeInst *II = dyn_cast<InvokeInst>(I)) {
+ if (II->getCalledMethod() == 0)
+ Node->addCalledMethod(ExternalNode);
+ }
+ }
}
}
destroy();
Mod = TheModule;
-
- // Create the root node of the module...
- Root = new CallGraphNode(0);
+ ExternalNode = getNodeFor(0);
+ Root = 0;
// Add every method to the call graph...
for_each(Mod->begin(), Mod->end(), bind_obj(this,&CallGraph::addToCallGraph));
+
+ // If we didn't find a main method, use the external call graph node
+ if (Root == 0) Root = ExternalNode;
return false;
}
void CallGraph::destroy() {
for (MethodMapTy::iterator I = MethodMap.begin(), E = MethodMap.end();
- I != E; ++I) {
+ I != E; ++I)
delete I->second;
- }
MethodMap.clear();
}
o << "Call graph node null method:\n";
for (unsigned i = 0; i < CGN->size(); ++i)
- o << " Calls method '" << (*CGN)[i]->getMethod()->getName() << "'\n";
+ if ((*CGN)[i]->getMethod())
+ o << " Calls method '" << (*CGN)[i]->getMethod()->getName() << "'\n";
+ else
+ o << " Calls external node\n";
o << "\n";
}
void WriteToOutput(const CallGraph &CG, std::ostream &o) {
- WriteToOutput(CG.getRoot(), o);
for (CallGraph::const_iterator I = CG.begin(), E = CG.end(); I != E; ++I)
o << I->second;
}
projects / oota-llvm.git / commitdiff