LLVM API Documentation

CallGraph.h

Go to the documentation of this file.
00001 //===- CallGraph.h - Build a Module's call graph ----------------*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This interface is used to build and manipulate a call graph, which is a very
00011 // useful tool for interprocedural optimization.
00012 //
00013 // Every function in a module is represented as a node in the call graph.  The
00014 // callgraph node keeps track of which functions the are called by the function
00015 // corresponding to the node.
00016 //
00017 // A call graph may contain nodes where the function that they correspond to is
00018 // null.  These 'external' nodes are used to represent control flow that is not
00019 // represented (or analyzable) in the module.  In particular, this analysis
00020 // builds one external node such that:
00021 //   1. All functions in the module without internal linkage will have edges
00022 //      from this external node, indicating that they could be called by
00023 //      functions outside of the module.
00024 //   2. All functions whose address is used for something more than a direct
00025 //      call, for example being stored into a memory location will also have an
00026 //      edge from this external node.  Since they may be called by an unknown
00027 //      caller later, they must be tracked as such.
00028 //
00029 // There is a second external node added for calls that leave this module.
00030 // Functions have a call edge to the external node iff:
00031 //   1. The function is external, reflecting the fact that they could call
00032 //      anything without internal linkage or that has its address taken.
00033 //   2. The function contains an indirect function call.
00034 //
00035 // As an extension in the future, there may be multiple nodes with a null
00036 // function.  These will be used when we can prove (through pointer analysis)
00037 // that an indirect call site can call only a specific set of functions.
00038 //
00039 // Because of these properties, the CallGraph captures a conservative superset
00040 // of all of the caller-callee relationships, which is useful for
00041 // transformations.
00042 //
00043 // The CallGraph class also attempts to figure out what the root of the
00044 // CallGraph is, which it currently does by looking for a function named 'main'.
00045 // If no function named 'main' is found, the external node is used as the entry
00046 // node, reflecting the fact that any function without internal linkage could
00047 // be called into (which is common for libraries).
00048 //
00049 //===----------------------------------------------------------------------===//
00050 
00051 #ifndef LLVM_ANALYSIS_CALLGRAPH_H
00052 #define LLVM_ANALYSIS_CALLGRAPH_H
00053 
00054 #include "llvm/ADT/GraphTraits.h"
00055 #include "llvm/ADT/STLExtras.h"
00056 #include "llvm/Pass.h"
00057 #include "llvm/Support/CallSite.h"
00058 
00059 namespace llvm {
00060 
00061 class Function;
00062 class Module;
00063 class CallGraphNode;
00064 
00065 //===----------------------------------------------------------------------===//
00066 // CallGraph class definition
00067 //
00068 class CallGraph {
00069 protected:
00070   Module *Mod;              // The module this call graph represents
00071 
00072   typedef std::map<const Function *, CallGraphNode *> FunctionMapTy;
00073   FunctionMapTy FunctionMap;    // Map from a function to its node
00074 
00075 public:
00076   //===---------------------------------------------------------------------
00077   // Accessors...
00078   //
00079   typedef FunctionMapTy::iterator iterator;
00080   typedef FunctionMapTy::const_iterator const_iterator;
00081 
00082   /// getModule - Return the module the call graph corresponds to.
00083   ///
00084   Module &getModule() const { return *Mod; }
00085 
00086   inline       iterator begin()       { return FunctionMap.begin(); }
00087   inline       iterator end()         { return FunctionMap.end();   }
00088   inline const_iterator begin() const { return FunctionMap.begin(); }
00089   inline const_iterator end()   const { return FunctionMap.end();   }
00090 
00091   // Subscripting operators, return the call graph node for the provided
00092   // function
00093   inline const CallGraphNode *operator[](const Function *F) const {
00094     const_iterator I = FunctionMap.find(F);
00095     assert(I != FunctionMap.end() && "Function not in callgraph!");
00096     return I->second;
00097   }
00098   inline CallGraphNode *operator[](const Function *F) {
00099     const_iterator I = FunctionMap.find(F);
00100     assert(I != FunctionMap.end() && "Function not in callgraph!");
00101     return I->second;
00102   }
00103 
00104   //Returns the CallGraphNode which is used to represent undetermined calls 
00105   // into the callgraph.  Override this if you want behavioural inheritance.
00106   virtual CallGraphNode* getExternalCallingNode() const { return 0; }
00107   
00108   //Return the root/main method in the module, or some other root node, such
00109   // as the externalcallingnode.  Overload these if you behavioural 
00110   // inheritance.
00111   virtual CallGraphNode* getRoot() { return 0; }
00112   virtual const CallGraphNode* getRoot() const { return 0; }
00113   
00114   //===---------------------------------------------------------------------
00115   // Functions to keep a call graph up to date with a function that has been
00116   // modified.
00117   //
00118 
00119   /// removeFunctionFromModule - Unlink the function from this module, returning
00120   /// it.  Because this removes the function from the module, the call graph
00121   /// node is destroyed.  This is only valid if the function does not call any
00122   /// other functions (ie, there are no edges in it's CGN).  The easiest way to
00123   /// do this is to dropAllReferences before calling this.
00124   ///
00125   Function *removeFunctionFromModule(CallGraphNode *CGN);
00126   Function *removeFunctionFromModule(Function *F) {
00127     return removeFunctionFromModule((*this)[F]);
00128   }
00129 
00130   /// changeFunction - This method changes the function associated with this
00131   /// CallGraphNode, for use by transformations that need to change the
00132   /// prototype of a Function (thus they must create a new Function and move the
00133   /// old code over).
00134   void changeFunction(Function *OldF, Function *NewF);
00135 
00136   /// getOrInsertFunction - This method is identical to calling operator[], but
00137   /// it will insert a new CallGraphNode for the specified function if one does
00138   /// not already exist.
00139   CallGraphNode *getOrInsertFunction(const Function *F);
00140   
00141   //===---------------------------------------------------------------------
00142   // Pass infrastructure interface glue code...
00143   //
00144 protected:
00145   CallGraph() {}
00146   
00147 public:
00148   virtual ~CallGraph() { destroy(); }
00149 
00150   /// initialize - Call this method before calling other methods, 
00151   /// re/initializes the state of the CallGraph.
00152   ///
00153   void initialize(Module &M);
00154 
00155   virtual void print(std::ostream &o, const Module *M) const;
00156   void dump() const;
00157   
00158   // stub - dummy function, just ignore it
00159   static int stub;
00160 protected:
00161 
00162   // destroy - Release memory for the call graph
00163   virtual void destroy();
00164 };
00165 
00166 //===----------------------------------------------------------------------===//
00167 // CallGraphNode class definition
00168 //
00169 class CallGraphNode {
00170   Function *F;
00171   typedef std::pair<CallSite,CallGraphNode*> CallRecord;
00172   std::vector<CallRecord> CalledFunctions;
00173 
00174   CallGraphNode(const CallGraphNode &);           // Do not implement
00175 public:
00176   //===---------------------------------------------------------------------
00177   // Accessor methods...
00178   //
00179 
00180   typedef std::vector<CallRecord>::iterator iterator;
00181   typedef std::vector<CallRecord>::const_iterator const_iterator;
00182 
00183   // getFunction - Return the function that this call graph node represents...
00184   Function *getFunction() const { return F; }
00185 
00186   inline iterator begin() { return CalledFunctions.begin(); }
00187   inline iterator end()   { return CalledFunctions.end();   }
00188   inline const_iterator begin() const { return CalledFunctions.begin(); }
00189   inline const_iterator end()   const { return CalledFunctions.end();   }
00190   inline unsigned size() const { return CalledFunctions.size(); }
00191 
00192   // Subscripting operator - Return the i'th called function...
00193   //
00194   CallGraphNode *operator[](unsigned i) const {
00195     return CalledFunctions[i].second;
00196   }
00197 
00198   /// dump - Print out this call graph node.
00199   ///
00200   void dump() const;
00201   void print(std::ostream &OS) const;
00202 
00203   //===---------------------------------------------------------------------
00204   // Methods to keep a call graph up to date with a function that has been
00205   // modified
00206   //
00207 
00208   /// removeAllCalledFunctions - As the name implies, this removes all edges
00209   /// from this CallGraphNode to any functions it calls.
00210   void removeAllCalledFunctions() {
00211     CalledFunctions.clear();
00212   }
00213 
00214   /// addCalledFunction add a function to the list of functions called by this
00215   /// one.
00216   void addCalledFunction(CallSite CS, CallGraphNode *M) {
00217     CalledFunctions.push_back(std::make_pair(CS, M));
00218   }
00219 
00220   /// removeCallEdgeTo - This method removes a *single* edge to the specified
00221   /// callee function.  Note that this method takes linear time, so it should be
00222   /// used sparingly.
00223   void removeCallEdgeTo(CallGraphNode *Callee);
00224 
00225   /// removeAnyCallEdgeTo - This method removes any call edges from this node to
00226   /// the specified callee function.  This takes more time to execute than
00227   /// removeCallEdgeTo, so it should not be used unless necessary.
00228   void removeAnyCallEdgeTo(CallGraphNode *Callee);
00229 
00230   friend class CallGraph;
00231 
00232   // CallGraphNode ctor - Create a node for the specified function.
00233   inline CallGraphNode(Function *f) : F(f) {}
00234 };
00235 
00236 //===----------------------------------------------------------------------===//
00237 // GraphTraits specializations for call graphs so that they can be treated as
00238 // graphs by the generic graph algorithms.
00239 //
00240 
00241 // Provide graph traits for tranversing call graphs using standard graph
00242 // traversals.
00243 template <> struct GraphTraits<CallGraphNode*> {
00244   typedef CallGraphNode NodeType;
00245 
00246   typedef std::pair<CallSite, CallGraphNode*> CGNPairTy;
00247   typedef std::pointer_to_unary_function<CGNPairTy, CallGraphNode*> CGNDerefFun;
00248   
00249   static NodeType *getEntryNode(CallGraphNode *CGN) { return CGN; }
00250   
00251   typedef mapped_iterator<NodeType::iterator, CGNDerefFun> ChildIteratorType;
00252   
00253   static inline ChildIteratorType child_begin(NodeType *N) {
00254     return map_iterator(N->begin(), CGNDerefFun(CGNDeref));
00255   }
00256   static inline ChildIteratorType child_end  (NodeType *N) {
00257     return map_iterator(N->end(), CGNDerefFun(CGNDeref));
00258   }
00259   
00260   static CallGraphNode *CGNDeref(CGNPairTy P) {
00261     return P.second;
00262   }
00263   
00264 };
00265 
00266 template <> struct GraphTraits<const CallGraphNode*> {
00267   typedef const CallGraphNode NodeType;
00268   typedef NodeType::const_iterator ChildIteratorType;
00269 
00270   static NodeType *getEntryNode(const CallGraphNode *CGN) { return CGN; }
00271   static inline ChildIteratorType child_begin(NodeType *N) { return N->begin();}
00272   static inline ChildIteratorType child_end  (NodeType *N) { return N->end(); }
00273 };
00274 
00275 template<> struct GraphTraits<CallGraph*> : public GraphTraits<CallGraphNode*> {
00276   static NodeType *getEntryNode(CallGraph *CGN) {
00277     return CGN->getExternalCallingNode();  // Start at the external node!
00278   }
00279   typedef std::pair<const Function*, CallGraphNode*> PairTy;
00280   typedef std::pointer_to_unary_function<PairTy, CallGraphNode&> DerefFun;
00281 
00282   // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
00283   typedef mapped_iterator<CallGraph::iterator, DerefFun> nodes_iterator;
00284   static nodes_iterator nodes_begin(CallGraph *CG) {
00285     return map_iterator(CG->begin(), DerefFun(CGdereference));
00286   }
00287   static nodes_iterator nodes_end  (CallGraph *CG) {
00288     return map_iterator(CG->end(), DerefFun(CGdereference));
00289   }
00290 
00291   static CallGraphNode &CGdereference(PairTy P) {
00292     return *P.second;
00293   }
00294 };
00295 
00296 template<> struct GraphTraits<const CallGraph*> :
00297   public GraphTraits<const CallGraphNode*> {
00298   static NodeType *getEntryNode(const CallGraph *CGN) {
00299     return CGN->getExternalCallingNode();
00300   }
00301   // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
00302   typedef CallGraph::const_iterator nodes_iterator;
00303   static nodes_iterator nodes_begin(const CallGraph *CG) { return CG->begin(); }
00304   static nodes_iterator nodes_end  (const CallGraph *CG) { return CG->end(); }
00305 };
00306 
00307 } // End llvm namespace
00308 
00309 // Make sure that any clients of this file link in CallGraph.cpp
00310 FORCE_DEFINING_FILE_TO_BE_LINKED(CallGraph)
00311 
00312 #endif