A call graph (also known as a call multigraph) is a

control-flow graph In computer science, a control-flow graph (CFG) is a representation, using graph notation, of all paths that might be traversed through a program during its execution. The control-flow graph was discovered by Frances E. Allen, who noted that ...

, which represents calling relationships between subroutines in a

computer program A computer program is a sequence or set of instructions in a programming language for a computer to execute. Computer programs are one component of software, which also includes documentation and other intangible components. A computer program ...

. 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.

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 In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is proved to be impossible to construct an algorithm that always leads to a correct yes-or-no answer. The halting problem is an ...

, 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 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, program stack, control stack, run-time stack, or m ...

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 In computer science, dynamic dispatch is the process of selecting which implementation of a polymorphic operation (method or function) to call at run time. It is commonly employed in, and considered a prime characteristic of, object-oriented ...

(i.e.

Java Java (; id, Jawa, ; jv, ꦗꦮ; su, ) is one of the Greater Sunda Islands in Indonesia. It is bordered by the Indian Ocean to the south and the Java Sea to the north. With a population of 151.6 million people, Java is the world's mos ...

C++ C++ (pronounced "C plus plus") is a high-level general-purpose programming language created by Danish computer scientist Bjarne Stroustrup as an extension of the C programming language, or "C with Classes". The language has expanded significan ...

first-class functions In computer science, a programming language is said to have first-class functions if it treats functions as first-class citizens. This means the language supports passing functions as arguments to other functions, returning them as the values from ...

(i.e.

Python Python may refer to: Snakes * Pythonidae, a family of nonvenomous snakes found in Africa, Asia, and Australia ** ''Python'' (genus), a genus of Pythonidae found in Africa and Asia * Python (mythology), a mythical serpent Computing * Python (pro ...

or Racket), or function pointers (i.e. C), computing a static call graph precisely requires

alias analysis Alias may refer to: * Pseudonym * Pen name * Nickname Arts and entertainment Film and television * ''Alias'' (2013 film), a 2013 Canadian documentary film * ''Alias'' (TV series), an American action thriller series 2001–2006 * ''Alias the J ...

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 Free software or libre software is computer software distributed under terms that allow users to run the software for any purpose as well as to study, change, and distribute it and any adapted versions. Free software is a matter of liberty, no ...
call graph generators

Run-time call graph (most of tools listed are profilers with call graph functionality)

gprof Gprof is a performance analysis tool for Unix applications. It used a hybrid of instrumentation and samplingSusan L. Graham, Peter B. Kessler, and Marshall K. Mckusick''gprof: a Call Graph Execution Profiler''// Proceedings of the SIGPLAN '82 Sy ...

: included in BSD or part of the

GNU Binary Utilities The GNU Binary Utilities, or , are a set of programming tools for creating and managing binary programs, object files, libraries, profile data, and assembly source code. Tools They were originally written by programmers at Cygnus Solutions. ...

* callgrind : part of

Valgrind Valgrind () is a programming tool for memory debugging, memory leak detection, and profiling. Valgrind was originally designed to be a free memory debugging tool for Linux on x86, but has since evolved to become a generic framework for crea ...

KCachegrind
: 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 macOS (; previously OS X and originally Mac OS X) is a Unix operating system developed and marketed by Apple Inc. since 2001. It is the primary operating system for Apple's Mac computers. Within the market of desktop and la ...

Leopard * OpenPAT : includes the control_flow tool which automatically creates a

Graphviz Graphviz (short for ''Graph Visualization Software'') is a package of open-source tools initiated by AT&T Labs Research for drawing graphs specified in DOT language scripts having the file name extension "gv". It also provides libraries for ...

call-graph picture from runtime measurements.
pprof
open source tool for visualization and analysis of profile data, to be used in conjunction wit

*

CodeAnalyst AMD CodeAnalyst is a GUI-based code profiler for x86 and x86-64-based machines. CodeAnalyst has similar look and feel on both Linux and Microsoft Windows platforms. CodeAnalyst uses specific hardware profiling techniques which are designed to wo ...

from

AMD Advanced Micro Devices, Inc. (AMD) is an American multinational semiconductor company based in Santa Clara, California, that develops computer processors and related technologies for business and consumer markets. While it initially manufactur ...

(released under GPL)
makeppgraph
is a dependency graph generator (at module level) for builds performed with makepp.
Intel(R) Single Event API
(free, open-source)

Static for getting call graphs without running application

; C/C++ *

Sourcetrail Sourcetrail was a FOSS source code explorer that provided interactive dependency graphs and support for multiple programming languages including C, C++, Java and Python. History The project was started by Eberhard Gräther after an internship a ...

creates a static call graph, that can be dynamically explored by the user. Also supports Python and Java *

doxygen Doxygen ( ) is a documentation generator and static analysis tool for software source trees. When used as a documentation generator, Doxygen extracts information from specially-formatted comments within the code. When used for analysis, Doxyge ...

: Uses

to generate static call/inheritance diagrams *

cflow GNU cflow is a flow graph generator that is part of the GNU Project. It reads a collection of C source files and generates a C flow graph of external references. It uses only sources and doesn't need to run the program. History It was initial ...

: GNU cflow is able to generate the direct and inverted call graph of a C program
egypt
: a small

Perl Perl is a family of two high-level, general-purpose, interpreted, dynamic programming languages. "Perl" refers to Perl 5, but from 2000 to 2019 it also referred to its redesigned "sister language", Perl 6, before the latter's name was offic ...

script that uses gcc and

to generate the static call graph of a C program.
Analizo
calculates source code metrics, generates dependency graphs.
CCTree
: Native Vim plugin that can display static call graphs by reading a

cscope cscope is a programming tool which works in console mode, text-based interface, that allows computer programmers or software developers to search source code of the programming language C, with some support for C++ and Java. It is often used ...

database. Works for C programs.
codeviz
: a static call graph generator (the program is ''not'' run). Implemented as a patch to gcc; works for C and C++ programs.
calltree.sh
: 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.
tceetree
: like calltree.sh, it connects

Cscope cscope is a programming tool which works in console mode, text-based interface, that allows computer programmers or software developers to search source code of the programming language C, with some support for C++ and Java. It is often used ...

and

, but it is an executable rather than a bash script. ;Go
go-callvis
: an interactive call graph generator for Go programs whose output can be drawn with

;Multi-language
callGraph
: open-source call graph generator for awk, bash, basic, dart, fortran, go, lua, javascript, julia, kotlin, matlab, perl, pascal, php, python, R, raku, ruby, rust, scala, swift, tcl, and typescript. ;.NET *

NDepend NDepend is a static analysis tool for .NET managed code. The tool proposes a large number features, from dependency visualization to Quality Gates and Smart Technical Debt Estimation. For that reasons the community refers to it as the "Swiss Army ...

: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. ;PHP, Perl and Python
Devel::NYTProf
: a Perl performance analyser and call chart generator
phpCallGraph
: a call graph generator for PHP programs that uses

. It is written in PHP and requires at least PHP 5.2.
pycallgraph
: a call graph generator for Python programs that uses

.
pyan
: a static call graph generator for Python programs that uses

.
gprof2dot
: A call graph generator written in Python that converts profiling data for many languages/runtimes to a

callgraph.
code2flow
A call graph generator for Python and Javascript programs that uses

rcviz
: Python module for rendering runtime-generated call graphs with

. Each node represents an invocation of a function with the parameters passed to it and the return value. ;XQuery
XQuery Call Graphs from the XQuery Wikibook
A call graph generator for an XQuery function module that uses

Proprietary call graph generators

;

LDRA Testbed LDRA Testbed provides the core static and dynamic analysis engines for both host and embedded software. LDRA Testbed is made by Liverpool Data Research Associates (LDRA). LDRA Testbed provides the means to enforce compliance with coding standard ...

: Static and dynamic analysis engines for both host and embedded software, with a myriad of reports including call graphs. ; Project Analyzer : Static code analyzer and call graph generator for Visual Basic code ; Visual Expert : Static code analyzer and call graph generator for Oracle

PL/SQL PL/SQL (Procedural Language for SQL) is Oracle Corporation's procedural extension for SQL and the Oracle relational database. PL/SQL is available in Oracle Database (since version 6 - stored PL/SQL procedures/functions/packages/triggers since ...

, SQLServer

Transact-SQL Transact-SQL (T-SQL) is Microsoft's and Sybase's proprietary extension to the SQL (Structured Query Language) used to interact with relational databases. T-SQL expands on the SQL standard to include procedural programming, local variables, vari ...

, C# and

PowerBuilder PowerBuilder is an integrated development environment owned by SAP since the acquisition of Sybase in 2010. On July 5, 2016, SAP and Appeon entered into an agreement whereby Appeon, an independent company, would be responsible for developing, se ...

code ; Intel VTune Performance Analyzer : Instrumenting profiler to show call graph and execution statistics ;

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 langu ...

: Customizable program analysis tool with static whole-program global call graph extraction for C, Java and COBOL

Other, related tools

;

: Turns a text representation of any graph (including a call graph) into a picture. ;

tsort The tsort program is a command line utility on Unix and Unix-like platforms, that performs a topological sort on its input. , it is part of the POSIX.1 standard. History According to its info page, this command was initially written for providi ...

: Command-line utility that performs a topological sort.

Sample graph

A sample call graph generated from

analyzing itself:

index    called     name                              , index    called     name
      72384/72384       sym_id_parse  4            ,        1508/1508        cg_dfn  5   72384             match                      ,  3  1508             pre_visit  3----------------------                                , ----------------------
          4/9052        cg_tally  2                ,        1508/1508        cg_assemble  8       3016/9052        hist_print  9              ,  4  1508             propagate_time  4       6032/9052        propagate_flags  2         , ----------------------
    9052             sym_lookup                 ,           2             cg_dfn  5----------------------                                ,        1507/1507        cg_assemble  8       5766/5766        core_create_function_syms  1 5  1507+2           cg_dfn  5    5766             core_sym_class             ,        1509/1509        is_numbered  ----------------------                                ,        1508/1508        is_busy  1         24/1537        parse_spec  9              ,        1508/1508        pre_visit  3       1513/1537        core_create_function_syms  1       1508/1508        post_visit  2    1537             sym_init                   ,           2             cg_dfn  5----------------------                                , ----------------------
       1511/1511        core_create_function_syms  1       1505/1505        hist_print  9    1511             get_src_info               ,  6  1505             print_line  6----------------------                                ,           2/9           print_name_only  5          2/1510        arc_add  1                 , ----------------------
       1508/1510        cg_assemble  8             ,        1430/1430        core_create_function_syms  1    1510             arc_lookup                 ,  7  1430             source_file_lookup_path  7----------------------                                , ----------------------
       1509/1509        cg_dfn  5                  ,          24/24          sym_id_parse  4    1509             is_numbered                ,  8    24             parse_id  8----------------------                                ,          24/24          parse_spec  9       1508/1508        propagate_flags  2         , ----------------------
 0  1508             inherit_flags  0           ,          24/24          parse_id  8----------------------                                ,  9    24             parse_spec  9       1508/1508        cg_dfn  5                  ,          24/1537        sym_init   1  1508             is_busy  1                 , ----------------------
----------------------                                ,          24/24          main 210 




Year 210 ( CCX) was a common year starting on Monday (link will display the full calendar) of the Julian calendar. At the time, it was known as the Year of the Consulship of Faustinus and Rufinus (or, less frequently, year 963 '' Ab urbe condit ...
       1508/1508        cg_dfn  5                  ,  0    24             sym_id_add  0 2  1508             post_visit  2              ,

References

{{Reflist Compiler construction Documentation generators Static program analysis Graph data structures