Ein gerichteter Graph, der die mögliche Ausführungsreihenfolge und den Kontrolltransfer zwischen Grundblöcken oder Anweisungen in einem Programm darstellt; Knoten stehen typischerweise für Grundblöcke und Kanten für Sprünge, Verzweigungen und Fall-through-Übergänge.

Prinzip

Programmausführung als Übergänge zwischen Kontrollregionen modellieren, sodass Erreichbarkeit, Dominanz, Liveness und andere kontrolleozentrische Analysen als Graphprobleme über Knoten und Kanten formuliert werden können, die den Fluss des Programmzählers repräsentieren.

Demonstration

Eine Funktion mit if/else und einer Schleife bildet einen CFG ab, in dem ein konditioneller Knoten zwei ausgehende Kanten zu den 'then'- und 'else'-Blöcken hat; die Schleife erzeugt eine Rückkante vom Schleifenende zum Schleifenanfang, wodurch der CFG zyklisch wird.

Fehlanwendung

Einen CFG zur Beurteilung von Datenabhängigkeiten zu verwenden (z. B. anzunehmen, dass Wertdefinitionen entlang CFG-Kanten fließen) oder anzunehmen, dass das Vorhandensein einer Kante einen Laufzeitübergang mit konstanter Häufigkeit impliziert — beides führt zu falschen Optimierungen oder Analysen.

Konsequenz

Korrekte Nutzung unterstützt Optimierungen wie Dead-Code-Elimination, Schleifentransformationen, Inlining-Entscheidungen (in Kombination mit interprozeduralen Informationen) und Verifikationsaufgaben wie das Beweisen von Erreichbarkeit oder dem Fehlen bestimmter Kontrollpfade.

Umkehrung

Das Programm rein als Datenfluss (Berechnungsgraph) zu betrachten, wobei Kontrollkonstrukte als Daten-Transformationen kodiert werden; diese Umkehr ersetzt explizite Kontrollkanten durch datenbasierte Prüfungen und kann kontrolleozentrische Eigenschaften verschleiern.

Abgrenzung

Gilt standardmäßig für intraprozedurale Repräsentationen; interprozeduraler Kontrollfluss erfordert Erweiterungen (Aufruf-/Rückgabekanten, interprozeduraler CFG). Er kodiert keine Seiteneffekte, Thread-Interleavings oder präzise Zeitdetails ohne Erweiterung.

Semantische Spannung

Spannung zwischen CFG und Berechnungs-/Datenflussgraphen: CFG betont mögliche Programmzähler-Überträge (Kontrolle), während Datenflussgraphen die Verbreitung von Werten hervorheben; ihre Verwechslung führt zu ungeeigneten Analysen.

Synthese

Ein Kontrollflussgraph ist die Programmabstraktion, die mögliche Übergänge zwischen Programmregionen als gerichtete Kanten explizit macht; er ist die grundlegende Struktur für Analysen und Transformationen, die von der Gestalt der Kontrolle und nicht vom reinen Datenfluss abhängen.