Un graphe dont les nœuds sont des sous-programmes, fonctions ou méthodes et dont les arêtes orientées indiquent qu'une routine peut en invoquer une autre ; les arêtes sont typiquement tracées du caller vers le callee et peuvent être annotées par sites d'appel ou contextes d'invocation.

Principe

Abstraire les relations d'appel d'un programme sous forme de graphe afin que des analyses interprocédurales (atteignabilité via appels, détection de récursion, énumération de chaînes d'appels) et des transformations (inlining, élimination de code mort, optimisation globale) puissent être réalisées.

Démonstration

Dans un programme avec les fonctions A, B et C où A appelle B et B appelle conditionnellement C, le graphe d'appels contient les arêtes A→B et B→C ; s'il y a récursion, un cycle apparaît (par ex. C→A), ce qui informe des analyses de récursion et d'utilisation de pile.

Mauvaise application

Traiter un graphe d'appels statique comme une trace d'appels précise à l'exécution — en ignorant le dispatch dynamique, les appels par réflexion ou les appels indirects non résolus — peut conduire à des hypothèses erronées sur les fonctions exécutées et à des optimisations non sûres.

Conséquence

Un graphe d'appels construit correctement permet des analyses interprocédurales comme l'affinage de la résolution points-to, la propagation de résumés d'effets de bord et l'identification de chaînes d'appels 'chaudes' pour optimisation et profilage.

Inversion

Inverser la perspective en un graphe callee-vers-caller ou un arbre d'appels dynamique qui enregistre les séquences d'invocation réelles à l'exécution ; la vue inversée met l'accent sur les sites d'utilisation et les piles d'appels réelles plutôt que sur les relations d'appel potentielles.

Limite

Distinguer les graphes d'appels statiques (conservateurs, pouvant sur-approximer) et dynamiques (observés, pouvant sous-approximer). Le graphe d'appels standard n'encode pas en soi les valeurs d'arguments, le timing, ni les intercalations de concurrence sauf extension.

Tension sémantique

Tension entre le graphe d'appels et d'autres graphes de dépendance (par ex. graphe de dépendances de données) : le graphe d'appels capture la topologie des invocations, pas le flux de données ou le flux de contrôle à l'intérieur des fonctions ; les confondre embrouille les objectifs analytiques.

Synthèse

Un graphe d'appels est l'abstraction au niveau du programme de qui peut invoquer qui : les nœuds sont des routines et les arêtes représentent des invocations potentielles ou observées, formant l'épine dorsale du raisonnement interprocédural tout en nécessitant de distinguer staticité et dynamisme.