LLVM  6.0.0svn
Classes | Namespaces
CallGraph.h File Reference

This file provides interfaces used to build and manipulate a call graph, which is a very useful tool for interprocedural optimization. More...

#include "llvm/ADT/GraphTraits.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/IR/CallSite.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/Intrinsics.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/Pass.h"
#include <cassert>
#include <map>
#include <memory>
#include <utility>
#include <vector>
Include dependency graph for CallGraph.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes

class  llvm::CallGraph
 The basic data container for the call graph of a Module of IR. More...
 
class  llvm::CallGraphNode
 A node in the call graph for a module. More...
 
class  llvm::CallGraphAnalysis
 An analysis pass to compute the CallGraph for a Module. More...
 
class  llvm::CallGraphPrinterPass
 Printer pass for the CallGraphAnalysis results. More...
 
class  llvm::CallGraphWrapperPass
 The ModulePass which wraps up a CallGraph and the logic to build it. More...
 
struct  llvm::GraphTraits< CallGraphNode * >
 
struct  llvm::GraphTraits< const CallGraphNode * >
 
struct  llvm::GraphTraits< CallGraph * >
 
struct  llvm::GraphTraits< const CallGraph * >
 

Namespaces

 llvm
 Compute iterated dominance frontiers using a linear time algorithm.
 

Detailed Description

This file provides interfaces used to build and manipulate a call graph, which is a very useful tool for interprocedural optimization.

Every function in a module is represented as a node in the call graph. The callgraph node keeps track of which functions are called by the function corresponding to the node.

A call graph may contain nodes where the function that they correspond to is null. These 'external' nodes are used to represent control flow that is not represented (or analyzable) in the module. In particular, this analysis builds one external node such that:

  1. All functions in the module without internal linkage will have edges from this external node, indicating that they could be called by functions outside of the module.
  2. All functions whose address is used for something more than a direct call, for example being stored into a memory location will also have an edge from this external node. Since they may be called by an unknown caller later, they must be tracked as such.

There is a second external node added for calls that leave this module. Functions have a call edge to the external node iff:

  1. The function is external, reflecting the fact that they could call anything without internal linkage or that has its address taken.
  2. The function contains an indirect function call.

As an extension in the future, there may be multiple nodes with a null function. These will be used when we can prove (through pointer analysis) that an indirect call site can call only a specific set of functions.

Because of these properties, the CallGraph captures a conservative superset of all of the caller-callee relationships, which is useful for transformations.

Definition in file CallGraph.h.