Call graph
Encyclopedia
A call graph is a directed graph
that represents calling relationships between subroutine
s in a computer program
. Specifically, each node represents a procedure and each edge (f, g) indicates that procedure f calls procedure g. Thus, a cycle in the graph indicates recursive procedure calls.
Call graphs are a basic program analysis result that can be used for human understanding of programs, or as a basis for further analyses, such as an analysis that tracks the flow of values between procedures. One simple application of call graphs is finding procedures that are never called.
Call graphs can be dynamic or static. A dynamic call graph is a record of an execution of the program, e.g., as output by a profiler. Thus, a dynamic call graph can be exact, but only describes one run of the program. A static call graph is a call graph intended to represent every possible run of the program. The exact static call graph is undecidable
, so static call graph algorithms are generally overapproximations. That is, every call relationship that occurs is represented in the graph, and possibly also some call relationships that would never occur in actual runs of the program.
Call graphs can be defined to represent varying degrees of precision. A more precise call graph more precisely approximates the behavior of the real program, at the cost of taking longer to compute and more memory to store. The most precise call graph is fully context-sensitive, which means that for each procedure, the graph contains a separate node for each call stack
that procedure can be activated with. A fully context-sensitive call graph can be computed dynamically easily, although it may take up a large amount of memory. Fully context-sensitive call graphs are usually not computed statically, because it would take too long for a large program. The least precise call graph is context-insensitive, which means that there is only one node for each procedure.
With languages that feature dynamic dispatch
, such as Java
and C++
, computing a static call graph precisely requires alias analysis
results. Conversely, computing precise aliasing requires a call graph. Many static analysis systems solve the apparent infinite regress by computing both simultaneously.
This term is frequently used in the compiler
and binary translation
community. By tracking a call graph, it may be possible to detect anomalies of program execution or code injection attacks.
Free software
Run-time call-graph (most of tools listed are profilers with callgraph functionality):
Static (for C language), for getting call graphs without running of application:
PHP, perl, python
Intel VTune Performance Analyzer
: Instrumenting profiler to show call graph and execution statistics
DMS Software Reengineering Toolkit
: Customizable program analysis tool with static whole-program global call graph extraction for C, Java and COBOL
CodeProphet Profiler : Callgraph Profiler for native C/C++ code under Windows x86, x64 and Windows Mobile.
: Turns a text representation of any graph (including a call graph) into a picture. Must be used together with
doesn't handle graphics by itself.
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
that represents calling relationships between subroutine
Subroutine
In computer science, a subroutine is a portion of code within a larger program that performs a specific task and is relatively independent of the remaining code....
s in a computer program
Computer program
A computer program is a sequence of instructions written to perform a specified task with a computer. A computer requires programs to function, typically executing the program's instructions in a central processor. The program has an executable form that the computer can use directly to execute...
. Specifically, each node represents a procedure and each edge (f, g) indicates that procedure f calls procedure g. Thus, a cycle in the graph indicates recursive procedure calls.
Call graphs are a basic program analysis result that can be used for human understanding of programs, or as a basis for further analyses, such as an analysis that tracks the flow of values between procedures. One simple application of call graphs is finding procedures that are never called.
Call graphs can be dynamic or static. A dynamic call graph is a record of an execution of the program, e.g., as output by a profiler. Thus, a dynamic call graph can be exact, but only describes one run of the program. A static call graph is a call graph intended to represent every possible run of the program. The exact static call graph is undecidable
Undecidable
Undecidable may refer to:In mathematics and logic* Undecidable problem - a decision problem which no algorithm can decide* "Undecidable" is sometimes used as a synonym of "independent", where a formula in mathematical logic is independent of a logical theory if neither that formula nor its negation...
, so static call graph algorithms are generally overapproximations. That is, every call relationship that occurs is represented in the graph, and possibly also some call relationships that would never occur in actual runs of the program.
Call graphs can be defined to represent varying degrees of precision. A more precise call graph more precisely approximates the behavior of the real program, at the cost of taking longer to compute and more memory to store. The most precise call graph is fully context-sensitive, which means that for each procedure, the graph contains a separate node for each call stack
Call stack
In computer science, a call stack is a stack data structure that stores information about the active subroutines of a computer program. This kind of stack is also known as an execution stack, control stack, run-time stack, or machine stack, and is often shortened to just "the stack"...
that procedure can be activated with. A fully context-sensitive call graph can be computed dynamically easily, although it may take up a large amount of memory. Fully context-sensitive call graphs are usually not computed statically, because it would take too long for a large program. The least precise call graph is context-insensitive, which means that there is only one node for each procedure.
With languages that feature dynamic dispatch
Dynamic dispatch
In computer science, dynamic dispatch is the process of mapping a message to a specific sequence of code at runtime. This is done to support the cases where the appropriate method can't be determined at compile-time...
, such as Java
Java (programming language)
Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...
and C++
C++
C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...
, computing a static call graph precisely requires alias analysis
Alias analysis
Alias analysis is a technique in compiler theory, used to determine if a storage location may be accessed in more than one way. Two pointers are said to be aliased if they point to the same location....
results. Conversely, computing precise aliasing requires a call graph. Many static analysis systems solve the apparent infinite regress by computing both simultaneously.
This term is frequently used in the compiler
Compiler
A compiler is a computer program that transforms source code written in a programming language into another computer language...
and binary translation
Binary translation
In computing, binary translation is the emulation of one instruction set by another through translation of code. Sequences of instructions are translated from the source to the target instruction set...
community. By tracking a call graph, it may be possible to detect anomalies of program execution or code injection attacks.
Free softwareFree softwareFree software, software libre or libre software is software that can be used, studied, and modified without restriction, and which can be copied and redistributed in modified or unmodified form either without restriction, or with restrictions that only ensure that further recipients can also do...
call-graph generators
Run-time call-graph (most of tools listed are profilers with callgraph functionality):- gprof : part of the GNU Binary UtilitiesGNU Binary UtilitiesThe GNU Binary Utilities, or binutils, comprise a collection of programming tools for the manipulation of object code in various object file formats. The current versions were originally written by programmers at Cygnus Solutions using the Binary File Descriptor library...
- KCachegrind : powerful tool to generate and analyze call graphs based on data generated by ValgrindValgrindValgrind is a GPL licensed programming tool for memory debugging, memory leak detection, and profiling. The name valgrind comes from the main entrance to Valhalla in Norse mythology....
's callgrind tool. - Mac OS X Activity Monitor : Apple GUI process monitor Activity Monitor has a built-in call graph generator that can sample processes and return a call graph. This function is only available in Mac OS XMac OS XMac OS X is a series of Unix-based operating systems and graphical user interfaces developed, marketed, and sold by Apple Inc. Since 2002, has been included with all new Macintosh computer systems...
Leopard - pprof tool, part of open-source google-perftools.
Static (for C language), for getting call graphs without running of application:
- doxygenDoxygenDoxygen is a documentation generator for multiple programming languages.Doxygen is a tool for writing software reference documentation. The documentation is written within code, and is thus relatively easy to keep up to date...
: Uses graphvizGraphvizGraphviz is a package of open-source tools initiated by AT&T Labs Research for drawing graphs specified in DOT language scripts. It also provides libraries for software applications to use the tools...
to generate static call/inheritance diagrams - cflowGNU cflowGNU cflow is a flow graph generator that is part of the GNU Project. It reads a collection of C source files and generate a C flow graph of external references...
: GNU cflow is able to generate the direct and inverted call graph of a C program - egypt : a small PerlPerlPerl is a high-level, general-purpose, interpreted, dynamic programming language. Perl was originally developed by Larry Wall in 1987 as a general-purpose Unix scripting language to make report processing easier. Since then, it has undergone many changes and revisions and become widely popular...
script that uses gcc and GraphvizGraphvizGraphviz is a package of open-source tools initiated by AT&T Labs Research for drawing graphs specified in DOT language scripts. It also provides libraries for software applications to use the tools...
to generate the static call graph of a C program. - CCTree : Native Vim plugin that can display static call graphs by reading a cscopeCscopecscope is a console mode or text-based graphical interface that allows computer programmers or software developers to search C source code . It is often used on very large projects to find source code, functions, declarations, definitions and regular expressions given a text string. cscope is free...
database. Works for C programs. - codeviz : a static call graph generator (the program is not run). Implemented as a patch to gccGNU Compiler CollectionThe GNU Compiler Collection is a compiler system produced by the GNU Project supporting various programming languages. GCC is a key component of the GNU toolchain...
; works for C and C++ programs.
PHP, perl, python
- Devel::NYTProf : a perl performance analyser and call chart generator
- phpCallGraph : a call graph generator for PHP programs that uses GraphvizGraphvizGraphviz is a package of open-source tools initiated by AT&T Labs Research for drawing graphs specified in DOT language scripts. It also provides libraries for software applications to use the tools...
. It is written in PHP and requires at least PHP 5.2. - pycallgraph : a call graph generator for Python programs that uses GraphvizGraphvizGraphviz is a package of open-source tools initiated by AT&T Labs Research for drawing graphs specified in DOT language scripts. It also provides libraries for software applications to use the tools...
.
Proprietary call-graph generators
Project Analyzer : Static code analyzer and call graph generator for Visual Basic codeIntel VTune Performance Analyzer
VTune
Intel VTune Amplifier XE is a commercial application for software performance analysis for 32 and 64-bit x86 based machines, and has both GUI and command line interfaces. It is available for both Linux and Microsoft Windows operating systems...
: Instrumenting profiler to show call graph and execution statistics
DMS Software Reengineering Toolkit
DMS Software Reengineering Toolkit
The DMS Software Reengineering Toolkit is a proprietary set of program transformation tools available for automating custom source program analysis, modification, translation or generation of software systems for arbitrary mixtures of source languages for large scale software systems.DMS has been...
: Customizable program analysis tool with static whole-program global call graph extraction for C, Java and COBOL
CodeProphet Profiler : Callgraph Profiler for native C/C++ code under Windows x86, x64 and Windows Mobile.
Other, related tools
GraphvizGraphviz
Graphviz is a package of open-source tools initiated by AT&T Labs Research for drawing graphs specified in DOT language scripts. It also provides libraries for software applications to use the tools...
: Turns a text representation of any graph (including a call graph) into a picture. Must be used together with
gprof (and a glue script, such as gprof2dot), which in accordance to the Unix philosophyUnix philosophy
The Unix philosophy is a set of cultural norms and philosophical approaches to developing software based on the experience of leading developers of the Unix operating system.-McIlroy: A Quarter Century of Unix:...
doesn't handle graphics by itself.
Sample Graph
A sample Call Graph generated from gprof analyzing itself:
index called name |index called name
72384/72384 sym_id_parse [54] | 1508/1508 cg_dfn [15]
[3] 72384 match [3] |[13] 1508 pre_visit [13]
---------------------- |----------------------
4/9052 cg_tally [32] | 1508/1508 cg_assemble [38]
3016/9052 hist_print [49] |[14] 1508 propagate_time [14]
6032/9052 propagate_flags [52] |----------------------
[4] 9052 sym_lookup [4] | 2 cg_dfn [15]
---------------------- | 1507/1507 cg_assemble [38]
5766/5766 core_create_function_syms [41]|[15] 1507+2 cg_dfn [15]
[5] 5766 core_sym_class [5] | 1509/1509 is_numbered [9]
---------------------- | 1508/1508 is_busy [11]
24/1537 parse_spec [19] | 1508/1508 pre_visit [13]
1513/1537 core_create_function_syms [41]| 1508/1508 post_visit [12]
[6] 1537 sym_init [6] | 2 cg_dfn [15]
---------------------- |----------------------
1511/1511 core_create_function_syms [41]| 1505/1505 hist_print [49]
[7] 1511 get_src_info [7] |[16] 1505 print_line [16]
---------------------- | 2/9 print_name_only [25]
2/1510 arc_add [31] |----------------------
1508/1510 cg_assemble [38] | 1430/1430 core_create_function_syms [41]
[8] 1510 arc_lookup [8] |[17] 1430 source_file_lookup_path [17]
---------------------- |----------------------
1509/1509 cg_dfn [15] | 24/24 sym_id_parse [54]
[9] 1509 is_numbered [9] |[18] 24 parse_id [18]
---------------------- | 24/24 parse_spec [19]
1508/1508 propagate_flags [52] |----------------------
[10] 1508 inherit_flags [10] | 24/24 parse_id [18]
---------------------- |[19] 24 parse_spec [19]
1508/1508 cg_dfn [15] | 24/1537 sym_init [6]
[11] 1508 is_busy [11] |----------------------
---------------------- | 24/24 main [1210]
1508/1508 cg_dfn [15] |[20] 24 sym_id_add [20]
[12] 1508 post_visit [12] |