Call graph
A call graph is a control flow graph, which represents calling relationships between subroutines in a computer program. Each node represents a procedure and each edge indicates that procedure f calls procedure g. Thus, a cycle in the graph indicates recursive procedure calls.
Basic concepts
Call graphs can be dynamic or static. A dynamic call graph is a record of an execution of the program, for example 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 an undecidable problem, 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 is called a calling context tree. This can be computed dynamically easily, although it may take up a large amount of memory. Calling context trees 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.
Usages
Call graphs can be used in different ways. One simple application of call graphs is finding procedures that are never called. Call graphs can act as documentation for humans to understand programs. They can also serve as basis for further analyses, such as an analysis that tracks the flow of values between procedures, or change impact prediction. Call graphs can also be used to detect anomalies of program execution or code injection attacks.Software
[Free software] call-graph generators
;Run-time call-graph :- gprof : included in BSD or part of the GNU Binary Utilities
- callgrind : part of Valgrind
- : powerful tool to generate and analyze call graphs based on data generated by callgrind
- 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 X Leopard
- OpenPAT : includes the
control_flowtool which automatically creates a Graphviz call-graph picture from runtime measurements. - , open source tool for visualization and analysis of profile data, to be used in conjunction with .
- CodeAnalyst from AMD
- is a dependency graph generator for builds performed with makepp.
- doxygen : Uses graphviz to generate static call/inheritance diagrams
- cflow : GNU cflow is able to generate the direct and inverted call graph of a C program
- : a small Perl script that uses gcc and Graphviz to generate the static call graph of a C program.
- : calculates source code metrics, generates dependency graphs.
- : Native Vim plugin that can display static call graphs by reading a cscope database. Works for C programs.
- : a static call graph generator. Implemented as a patch to gcc; works for C and C++ programs.
- : Bash shell functions that glue together cscope, graphviz, and a sampling of dot-rendering tools to display "caller" and "callee" relationships above, below, and/or between the C functions you specify.
- : like calltree.sh, it connects Cscope and Graphviz, but it is an executable rather than a bash script.
- : an interactive call graph generator for Go programs whose output can be drawn with Graphviz
- NDepend :is a static analysis tool for.Net code. This tool supports a large number of code metrics, allows for visualization of dependencies using directed graphs and dependency matrix.
- : a perl performance analyser and call chart generator
- : a call graph generator for PHP programs that uses Graphviz. It is written in PHP and requires at least PHP 5.2.
- : a call graph generator for Python programs that uses Graphviz.
- : a static call graph generator for Python programs that uses Graphviz.
- : A call graph generator written in Python that converts profiling data for many languages/runtimes to a Graphviz callgraph.
- : A call graph generator for Python and Javascript programs that uses Graphviz
- : Python module for rendering runtime-generated call graphs with Graphviz. Each node represents an invocation of a function with the parameters passed to it and the return value.
- : A call graph generator for an XQuery function module that uses Graphviz
Proprietary call-graph generators
; Visual Expert : Static code analyzer and call graph generator for Oracle PL/SQL, SQLServer Transact-SQL, C# and PowerBuilder code
; 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
Other, related tools
; Graphviz : Turns a text representation of any graph into a picture.Sample graph
A sample call graph generated from gprof analyzing itself:
index called name |index called name
72384/72384 sym_id_parse | 1508/1508 cg_dfn
72384 match | 1508 pre_visit
---------------------- |----------------------
4/9052 cg_tally | 1508/1508 cg_assemble
3016/9052 hist_print | 1508 propagate_time
6032/9052 propagate_flags |----------------------
9052 sym_lookup | 2 cg_dfn
---------------------- | 1507/1507 cg_assemble
5766/5766 core_create_function_syms | 1507+2 cg_dfn
5766 core_sym_class | 1509/1509 is_numbered
---------------------- | 1508/1508 is_busy
24/1537 parse_spec | 1508/1508 pre_visit
1513/1537 core_create_function_syms | 1508/1508 post_visit
1537 sym_init | 2 cg_dfn
---------------------- |----------------------
1511/1511 core_create_function_syms | 1505/1505 hist_print
1511 get_src_info | 1505 print_line
---------------------- | 2/9 print_name_only
2/1510 arc_add |----------------------
1508/1510 cg_assemble | 1430/1430 core_create_function_syms
1510 arc_lookup | 1430 source_file_lookup_path
---------------------- |----------------------
1509/1509 cg_dfn | 24/24 sym_id_parse
1509 is_numbered | 24 parse_id
---------------------- | 24/24 parse_spec
1508/1508 propagate_flags |----------------------
1508 inherit_flags | 24/24 parse_id
---------------------- | 24 parse_spec
1508/1508 cg_dfn | 24/1537 sym_init
1508 is_busy |----------------------
---------------------- | 24/24 main
1508/1508 cg_dfn | 24 sym_id_add
1508 post_visit |