//===----------------------------------------------------------------------===//
// CallGraph class definition
//
-class CallGraph {
-protected:
+class CallGraph : public ModulePass {
Module *Mod; // The module this call graph represents
typedef std::map<const Function *, CallGraphNode *> FunctionMapTy;
FunctionMapTy FunctionMap; // Map from a function to its node
+ // Root is root of the call graph, or the external node if a 'main' function
+ // couldn't be found.
+ //
+ CallGraphNode *Root;
+
+ // ExternalCallingNode - This node has edges to all external functions and
+ // those internal functions that have their address taken.
+ CallGraphNode *ExternalCallingNode;
+
+ // CallsExternalNode - This node has edges to it from all functions making
+ // indirect calls or calling an external function.
+ CallGraphNode *CallsExternalNode;
+
+ /// Replace the function represented by this node by another.
+ /// This does not rescan the body of the function, so it is suitable when
+ /// splicing the body of one function to another while also updating all
+ /// callers from the old function to the new.
+ ///
+ void spliceFunction(const Function *From, const Function *To);
+
+ // Add a function to the call graph, and link the node to all of the functions
+ // that it calls.
+ void addToCallGraph(Function *F);
+
public:
static char ID; // Class identification, replacement for typeinfo
//===---------------------------------------------------------------------
}
/// Returns the CallGraphNode which is used to represent undetermined calls
- /// into the callgraph. Override this if you want behavioral inheritance.
- virtual CallGraphNode* getExternalCallingNode() const { return 0; }
- virtual CallGraphNode* getCallsExternalNode() const { return 0; }
+ /// into the callgraph.
+ CallGraphNode *getExternalCallingNode() const { return ExternalCallingNode; }
+ CallGraphNode *getCallsExternalNode() const { return CallsExternalNode; }
/// Return the root/main method in the module, or some other root node, such
- /// as the externalcallingnode. Overload these if you behavioral
- /// inheritance.
- virtual CallGraphNode* getRoot() { return 0; }
- virtual const CallGraphNode* getRoot() const { return 0; }
+ /// as the externalcallingnode.
+ CallGraphNode *getRoot() { return Root; }
+ const CallGraphNode *getRoot() const { return Root; }
//===---------------------------------------------------------------------
// Functions to keep a call graph up to date with a function that has been
/// do this is to dropAllReferences before calling this.
///
Function *removeFunctionFromModule(CallGraphNode *CGN);
- Function *removeFunctionFromModule(Function *F) {
- return removeFunctionFromModule((*this)[F]);
- }
/// getOrInsertFunction - This method is identical to calling operator[], but
/// it will insert a new CallGraphNode for the specified function if one does
/// not already exist.
CallGraphNode *getOrInsertFunction(const Function *F);
- /// spliceFunction - Replace the function represented by this node by another.
- /// This does not rescan the body of the function, so it is suitable when
- /// splicing the body of one function to another while also updating all
- /// callers from the old function to the new.
- ///
- void spliceFunction(const Function *From, const Function *To);
-
- //===---------------------------------------------------------------------
- // Pass infrastructure interface glue code.
- //
-protected:
- CallGraph() {}
-
-public:
- virtual ~CallGraph() { }
-
- /// initialize - Call this method before calling other methods,
- /// re/initializes the state of the CallGraph.
- ///
- void initialize(Module &M);
+ CallGraph();
+ virtual ~CallGraph() { releaseMemory(); }
+ virtual void getAnalysisUsage(AnalysisUsage &AU) const;
+ virtual bool runOnModule(Module &M);
+ virtual void releaseMemory();
- void print(raw_ostream &o, Module *) const;
+ void print(raw_ostream &o, const Module *) const;
void dump() const;
-protected:
- // destroy - Release memory for the call graph
- virtual void destroy();
};
//===----------------------------------------------------------------------===//
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
-//
-// This file implements the CallGraph class and provides the BasicCallGraph
-// default implementation.
-//
-//===----------------------------------------------------------------------===//
#include "llvm/Analysis/CallGraph.h"
#include "llvm/IR/Instructions.h"
#include "llvm/Support/raw_ostream.h"
using namespace llvm;
-namespace {
-
-//===----------------------------------------------------------------------===//
-// BasicCallGraph class definition
-//
-class BasicCallGraph : public ModulePass, public CallGraph {
- // Root is root of the call graph, or the external node if a 'main' function
- // couldn't be found.
- //
- CallGraphNode *Root;
-
- // ExternalCallingNode - This node has edges to all external functions and
- // those internal functions that have their address taken.
- CallGraphNode *ExternalCallingNode;
-
- // CallsExternalNode - This node has edges to it from all functions making
- // indirect calls or calling an external function.
- CallGraphNode *CallsExternalNode;
-
-public:
- static char ID; // Class identification, replacement for typeinfo
- BasicCallGraph() : ModulePass(ID), Root(0),
- ExternalCallingNode(0), CallsExternalNode(0) {
- initializeBasicCallGraphPass(*PassRegistry::getPassRegistry());
- }
- ~BasicCallGraph() {
- destroy();
- }
+CallGraph::CallGraph()
+ : ModulePass(ID), Root(0), ExternalCallingNode(0), CallsExternalNode(0) {
+ initializeCallGraphPass(*PassRegistry::getPassRegistry());
+}
- // runOnModule - Compute the call graph for the specified module.
- virtual bool runOnModule(Module &M) {
- CallGraph::initialize(M);
-
- ExternalCallingNode = getOrInsertFunction(0);
- assert(!CallsExternalNode);
- CallsExternalNode = new CallGraphNode(0);
- Root = 0;
-
- // Add every function to the call graph.
- for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
- addToCallGraph(I);
-
- // If we didn't find a main function, use the external call graph node
- if (Root == 0) Root = ExternalCallingNode;
-
- return false;
- }
+void CallGraph::addToCallGraph(Function *F) {
+ CallGraphNode *Node = getOrInsertFunction(F);
- virtual void getAnalysisUsage(AnalysisUsage &AU) const {
- AU.setPreservesAll();
- }
+ // If this function has external linkage, anything could call it.
+ if (!F->hasLocalLinkage()) {
+ ExternalCallingNode->addCalledFunction(CallSite(), Node);
- virtual void print(raw_ostream &OS, const Module *) const {
- OS << "CallGraph Root is: ";
- if (Function *F = getRoot()->getFunction())
- OS << F->getName() << "\n";
- else {
- OS << "<<null function: 0x" << getRoot() << ">>\n";
+ // Found the entry point?
+ if (F->getName() == "main") {
+ if (Root) // Found multiple external mains? Don't pick one.
+ Root = ExternalCallingNode;
+ else
+ Root = Node; // Found a main, keep track of it!
}
-
- CallGraph::print(OS, 0);
}
- virtual void releaseMemory() {
- destroy();
- }
-
- /// getAdjustedAnalysisPointer - This method is used when a pass implements
- /// an analysis interface through multiple inheritance. If needed, it should
- /// override this to adjust the this pointer as needed for the specified pass
- /// info.
- virtual void *getAdjustedAnalysisPointer(AnalysisID PI) {
- if (PI == &CallGraph::ID)
- return (CallGraph*)this;
- return this;
- }
-
- CallGraphNode* getExternalCallingNode() const { return ExternalCallingNode; }
- CallGraphNode* getCallsExternalNode() const { return CallsExternalNode; }
-
- // getRoot - Return the root of the call graph, which is either main, or if
- // main cannot be found, the external node.
- //
- CallGraphNode *getRoot() { return Root; }
- const CallGraphNode *getRoot() const { return Root; }
-
-private:
- //===---------------------------------------------------------------------
- // Implementation of CallGraph construction
- //
-
- // addToCallGraph - Add a function to the call graph, and link the node to all
- // of the functions that it calls.
- //
- void addToCallGraph(Function *F) {
- CallGraphNode *Node = getOrInsertFunction(F);
-
- // If this function has external linkage, anything could call it.
- if (!F->hasLocalLinkage()) {
- ExternalCallingNode->addCalledFunction(CallSite(), Node);
-
- // Found the entry point?
- if (F->getName() == "main") {
- if (Root) // Found multiple external mains? Don't pick one.
- Root = ExternalCallingNode;
- else
- Root = Node; // Found a main, keep track of it!
+ // If this function has its address taken, anything could call it.
+ if (F->hasAddressTaken())
+ ExternalCallingNode->addCalledFunction(CallSite(), Node);
+
+ // If this function is not defined in this translation unit, it could call
+ // anything.
+ if (F->isDeclaration() && !F->isIntrinsic())
+ Node->addCalledFunction(CallSite(), CallsExternalNode);
+
+ // Look for calls by this function.
+ for (Function::iterator BB = F->begin(), BBE = F->end(); BB != BBE; ++BB)
+ for (BasicBlock::iterator II = BB->begin(), IE = BB->end(); II != IE;
+ ++II) {
+ CallSite CS(cast<Value>(II));
+ if (CS) {
+ const Function *Callee = CS.getCalledFunction();
+ if (!Callee)
+ // Indirect calls of intrinsics are not allowed so no need to check.
+ Node->addCalledFunction(CS, CallsExternalNode);
+ else if (!Callee->isIntrinsic())
+ Node->addCalledFunction(CS, getOrInsertFunction(Callee));
}
}
+}
- // If this function has its address taken, anything could call it.
- if (F->hasAddressTaken())
- ExternalCallingNode->addCalledFunction(CallSite(), Node);
-
- // If this function is not defined in this translation unit, it could call
- // anything.
- if (F->isDeclaration() && !F->isIntrinsic())
- Node->addCalledFunction(CallSite(), CallsExternalNode);
-
- // Look for calls by this function.
- for (Function::iterator BB = F->begin(), BBE = F->end(); BB != BBE; ++BB)
- for (BasicBlock::iterator II = BB->begin(), IE = BB->end();
- II != IE; ++II) {
- CallSite CS(cast<Value>(II));
- if (CS) {
- const Function *Callee = CS.getCalledFunction();
- if (!Callee)
- // Indirect calls of intrinsics are not allowed so no need to check.
- Node->addCalledFunction(CS, CallsExternalNode);
- else if (!Callee->isIntrinsic())
- Node->addCalledFunction(CS, getOrInsertFunction(Callee));
- }
- }
- }
+void CallGraph::getAnalysisUsage(AnalysisUsage &AU) const {
+ AU.setPreservesAll();
+}
- //
- // destroy - Release memory for the call graph
- virtual void destroy() {
- /// CallsExternalNode is not in the function map, delete it explicitly.
- if (CallsExternalNode) {
- CallsExternalNode->allReferencesDropped();
- delete CallsExternalNode;
- CallsExternalNode = 0;
- }
- CallGraph::destroy();
- }
-};
+bool CallGraph::runOnModule(Module &M) {
+ Mod = &M;
-} //End anonymous namespace
+ ExternalCallingNode = getOrInsertFunction(0);
+ assert(!CallsExternalNode);
+ CallsExternalNode = new CallGraphNode(0);
+ Root = 0;
-INITIALIZE_ANALYSIS_GROUP(CallGraph, "Call Graph", BasicCallGraph)
-INITIALIZE_AG_PASS(BasicCallGraph, CallGraph, "basiccg",
- "Basic CallGraph Construction", false, true, true)
+ // Add every function to the call graph.
+ for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
+ addToCallGraph(I);
-char CallGraph::ID = 0;
-char BasicCallGraph::ID = 0;
+ // If we didn't find a main function, use the external call graph node
+ if (Root == 0)
+ Root = ExternalCallingNode;
-void CallGraph::initialize(Module &M) {
- Mod = &M;
+ return false;
}
-void CallGraph::destroy() {
- if (FunctionMap.empty()) return;
-
- // Reset all node's use counts to zero before deleting them to prevent an
- // assertion from firing.
+INITIALIZE_PASS(CallGraph, "basiccg", "CallGraph Construction", false, true)
+
+char CallGraph::ID = 0;
+
+void CallGraph::releaseMemory() {
+ /// CallsExternalNode is not in the function map, delete it explicitly.
+ if (CallsExternalNode) {
+ CallsExternalNode->allReferencesDropped();
+ delete CallsExternalNode;
+ CallsExternalNode = 0;
+ }
+
+ if (FunctionMap.empty())
+ return;
+
+// Reset all node's use counts to zero before deleting them to prevent an
+// assertion from firing.
#ifndef NDEBUG
for (FunctionMapTy::iterator I = FunctionMap.begin(), E = FunctionMap.end();
I != E; ++I)
FunctionMap.clear();
}
-void CallGraph::print(raw_ostream &OS, Module*) const {
+void CallGraph::print(raw_ostream &OS, const Module*) const {
+ OS << "CallGraph Root is: ";
+ if (Function *F = Root->getFunction())
+ OS << F->getName() << "\n";
+ else {
+ OS << "<<null function: 0x" << Root << ">>\n";
+ }
+
for (CallGraph::const_iterator I = begin(), E = end(); I != E; ++I)
I->second->print(OS);
}
projects / oota-llvm.git / commitdiff