Clean up call graph, add comments, and fix test/Regression/Other/2002-01-31-CallGraph.ll
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@1828 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Analysis/IPA/CallGraph.cpp b/lib/Analysis/IPA/CallGraph.cpp
index 5618a74..6a5cad4 100644
--- a/lib/Analysis/IPA/CallGraph.cpp
+++ b/lib/Analysis/IPA/CallGraph.cpp
@@ -1,12 +1,40 @@
//===- 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).
//
//===----------------------------------------------------------------------===//
@@ -15,7 +43,6 @@
#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>
@@ -26,14 +53,11 @@
// does not already exist.
//
CallGraphNode *CallGraph::getNodeFor(Method *M) {
- iterator I = MethodMap.find(M);
- if (I != MethodMap.end()) return I->second;
+ CallGraphNode *&CGN = MethodMap[M];
+ if (CGN) return CGN;
- assert(M->getParent() == Mod && "Method not in current module!");
- CallGraphNode *New = new CallGraphNode(M);
-
- 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
@@ -43,15 +67,46 @@
CallGraphNode *Node = getNodeFor(M);
// If this method has external linkage,
- if (!M->hasInternalLinkage())
- Root->addCalledMethod(Node);
+ if (!M->hasInternalLinkage()) {
+ ExternalNode->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()));
+ // 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);
+ }
+ }
}
}
@@ -59,21 +114,22 @@
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();
}
@@ -85,12 +141,14 @@
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;
}