A call graph (also known as a call multigraph) is a directed graph that represents calling relationship among subroutines in a computer program. It shows a certain indication about a program's control flow (but is not the same as a control flow graph) and it can be partially determined statically. However, it is usually a nondeterministic structure, since branch execution is decided at run time. Depending on the algorithm and the nature of the programming language used, the call graph may or may not support recursion. The call graph of a program that does not use recursion is a directed acyclic graph. A multigraph is a graph with multiple edges, i. ... In computer science, a subroutine (function, method, procedure, or subprogram) is a portion of code within a larger program, which performs a specific task and is relatively independent of the remaining code. ... A computer program is a collection of instructions that describe a task, or set of tasks, to be carried out by a computer. ... In computer science control flow (or alternatively, flow of control) refers to the order in which the individual statements or instructions of an imperative program are performed or executed. ... A control flow graph (CFG) is a representation, using graph notation, of all paths that might be traversed through a program during its execution. ... In the theory of computation, a nondeterministic algorithm is a hypothetical algorithm where computation can branch, choosing among different execution paths in a way that does not depend only on the input and current execution state. ... A programming language is an artificial language that can be used to control the behavior of a machine, particularly a computer. ... A visual form of recursion known as the Droste effect. ... A visual form of recursion known as the Droste effect. ... A simple directed acyclic graph In computer science and mathematics, a directed acyclic graph, also called a dag or DAG, is a directed graph with no directed cycles; that is, for any vertex v, there is no nonempty directed path starting and ending on v. ...

Call graphs are distinguished between context-insensitive and context-sensitive kinds. For context-insensitive graphs, each procedure is represented as a node, and the arrows are all the possible calls between the nodes. In the case of context-sensitive graphs, the generating algorithm takes in consideration the parameters of the function call, which may result in a simpler and more relevant graph.

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. This article is about the computing term. ... In computing, binary translation is the emulation of one instruction set by another through translation of code. ...

Known call graph-related programs include: Dotty, gprof (part of GNU_Binary_Utilities) and aiCall[1] dotty is the name of the tool that reads DOT Language scripts and renders the graphs. ... The GNU Binutils is a collection of programming tools for the manipulation of object code in various object file formats. ...

References

• Ryder, B.G., "Constructing the Call Graph of a Program," Software Engineering, IEEE Transactions on , vol.SE-5, no.3pp. 216- 226, May 1979 [2]
• Grove, D., DeFouw, G., Dean, J., and Chambers, C. 1997. Call graph construction in object-oriented languages. SIGPLAN Not. 32, 10 (Oct. 1997), 108-124. [3]
• Callahan, D.; Carle, A.; Hall, M.W.; Kennedy, K., "Constructing the procedure call multigraph," Software Engineering, IEEE Transactions on , vol.16, no.4pp.483-487, Apr 1990 [4]