callgraph

Call graph is a representation of calling relationships in a program. It is a directed graph in which each node denotes a function, method, or subroutine, and each edge from A to B indicates that A may call B. Call graphs can be intraprocedural, capturing calls inside a single procedure, or interprocedural, spanning the entire program.

Call graphs can be built statically, by analyzing source code or an intermediate representation to determine possible call targets; or dynamically, by profiling a running program to record observed calls. Static graphs may over-approximate in the presence of dynamic features such as function pointers, polymorphism, or reflection, while dynamic graphs are precise for observed executions but may miss unseen paths. Hybrid approaches combine both techniques.

Nodes and edges are typically stored as adjacency lists or matrices. Recursion creates cycles, so strongly connected components are often collapsed for certain analyses. Call graphs tend to be large and complex as programs scale.

Applications include understanding program structure, guiding optimizations (for example inlining decisions or dead code elimination), profiling and performance tuning, and aiding software maintenance or debugging. They also support dependency analysis and impact assessment when altering code.

Tools and contexts: compilers, analysis frameworks, and visualization utilities can generate and display call graphs, occasionally integrating with documentation generation. Key challenges remain handling dynamic dispatch, callbacks, and dynamic loading, which affect accuracy and completeness of static and dynamic call graphs.