Ein Graph, dessen Knoten Prozeduren, Funktionen oder Methoden sind und dessen gerichtete Kanten anzeigen, dass eine Routinen eine andere aufrufen kann; Kanten werden typischerweise vom Caller zum Callee gezeichnet und können mit Aufrufstellen oder Kontexten annotiert sein.

Prinzip

Die Aufrufbeziehungen eines Programms als Graph abstrahieren, sodass interprozedurale Analysen (Erreichbarkeit über Aufrufe, Rekursionserkennung, Aufrufkettenaufzählung) und Transformationen (Inlining, Dead-Code-Elimination, Whole-Program-Optimierung) durchgeführt werden können.

Demonstration

In einem Programm mit Funktionen A, B und C, wobei A B aufruft und B bedingt C aufruft, enthält der Aufrufgraph die Kanten A→B und B→C; bei Rekursion erscheint ein Zyklus (z. B. C→A), was Rekursions- und Stack-Analysen beeinflusst.

Fehlanwendung

Einen statischen Aufrufgraphen als präzisen Laufzeitaufrufverlauf zu behandeln — dynamische Dispatches, reflektive Aufrufe oder nicht aufgelöste indirekte Aufrufe zu ignorieren — kann zu falschen Annahmen über ausführbare Funktionen und zu unsicheren Optimierungen führen.

Konsequenz

Richtig konstruiert ermöglichen Aufrufgraphen interprozedurale Analysen wie Verfeinerung der Points-to-Information, Propagation von Seiteneffekt-Zusammenfassungen und Identifikation heißer Aufrufketten für Optimierung und Profiling.

Umkehrung

Perspektive umkehren zu einem Callee-zu-Caller-Graphen oder einem dynamischen Aufrufbaum, der tatsächliche Aufrufsequenzen zur Laufzeit aufzeichnet; die invertierte Ansicht betont Nutzungspunkte und realen Call-Stacks statt potentieller Aufrufbeziehungen.

Abgrenzung

Unterscheide statische (konservative, möglicherweise über-approximierende) und dynamische (beobachtete, möglicherweise unter-approximierende) Aufrufgraphen. Der Standard-Aufrufgraph erfasst nicht von sich aus Argumentwerte, Timing oder Nebenläufigkeits-Interleavings ohne Erweiterung.

Semantische Spannung

Spannung zwischen Aufrufgraph und anderen Abhängigkeitsgraphen (z. B. Datenabhängigkeitsgraph): Aufrufgraphen erfassen Aufruftopologie, nicht Datenfluss oder Kontrollfluss innerhalb von Funktionen; ihre Vermischung verschleiert Analyseziele.

Synthese

Ein Aufrufgraph ist die Programmebene-Abstraktion dessen, wer wen aufrufen kann: Knoten sind Routinen und Kanten repräsentieren potentielle oder beobachtete Aufrufe und bilden das Rückgrat interprozeduraler Analysen, wobei statische vs. dynamische Aussagen zu beachten sind.