Call Graph Construction

CallGraph provides call graph construction algorithms for C/C++ programs, resolving both virtual calls and indirect function pointers.

Headers: include/Analysis/CallGraph/

Implementation: lib/Analysis/CallGraph/

Overview

This subsystem constructs an interprocedural control flow graph (the Call Graph) by resolving direct, virtual, and indirect function calls.

Main components

  • CallGraph and CallGraphBuilder: The foundational classes representing and building the call graph.

  • Resolver: The abstract interface for resolving indirect and virtual calls.

  • VirtualCallUtils: Utilities for identifying and classifying virtual calls.

Algorithms

The module provides multiple algorithms for resolving indirect and virtual calls, each balancing precision and cost differently:

Virtual Call Resolution (C++)

These algorithms rely on the Type Hierarchy (see Type Hierarchy) to resolve virtual dispatches:

  • CHA (Class Hierarchy Analysis): Statically resolves virtual calls by traversing the class inheritance tree without analyzing program control flow.

  • RTA (Rapid Type Analysis): Refines CHA by tracking which classes are instantiated (identifying new allocations).

  • VTA (Variable Type Analysis): A flow-insensitive algorithm that computes type constraints for variables to refine the set of possible targets for a virtual call.

  • OTF (On-The-Fly Call Graph Construction): Constructs the call graph on-the-fly simultaneously with points-to analysis.

Function Pointer Analysis (FPA) (C/C++)

The FPA subsystem (lib/Analysis/CallGraph/FPA) implements function pointer analyses tailored for indirect call resolution:

  • FLTA: Flow-insensitive, type-based analysis.

  • MLTA: Multi-layer type analysis (often used for OS kernels).

  • MLTADF: Multi-layer type analysis with data flow.

  • KELP: Context-sensitive kernel-level pointer analysis.

Typical use cases

  • Build a precise Call Graph to enable interprocedural analysis.

  • Resolve indirect calls in C programs or virtual calls in C++ programs.