Kontrollflussgraph

Ein Kontrollflussgraph (CFG) ist eine graphische Repräsentation des Kontrollflusses eines Programms oder einer Funktion. Knoten repräsentieren in der Regel sogenannte Basic Blocks, also zusammenhängende Folgen von Anweisungen ohne Sprünge, deren einziger Eintrittspunkt der Beginn des Blocks und der einzige Austrittspunkt das Ende ist. Kanten verbinden Blöcke und kennzeichnen mögliche Sprünge der Ausführung von einem Block zum nächsten.

Ein CFG enthält typischerweise einen Einstiegsknoten (Entry) und oft einen Exit-Knoten. Die Kanten entstehen durch bedingte oder unbedingte Sprünge; bedingte Anweisungen erzeugen Verzweigungen, etwa true/false-Zweige, während unbedingte Sprünge den Fluss in den Zielblock festlegen. In der Regel ist der CFG intraprozedural (innerhalb einer Funktion); interprocedurale CFGs modellieren auch Funktionsaufrufe und Rückkehrpfade.

Verwendung: CFGs dienen der statischen Analyse und Optimierung. Sie ermöglichen Datenflussanalysen wie Erreichbarkeit, Liveness oder konstanter Propagation, sowie Optimierungen wie Dead Code Elimination oder Register Allocation. Sie unterstützen auch formale Verifikation, Visualisierung der Kontrollstruktur und Debugging.

Eigenschaften: CFGs sind abstrahierte Modelle des Programms. Sie erleichtern Analysen, können aber bei komplexen Programmen sehr groß oder irreduzibel werden, was bestimmte Algorithmen erschwert. Die Granularität (Basic Blocks) beeinflusst Präzision und Effizienz; Schleifen werden durch Zyklen im Graph dargestellt.

Varianten: In vielen Compilern handelt es sich um intraprozedurale CFGs; es gibt auch interprocedurale CFGs oder SSA-Formen, die zusätzlich durch Variableversionsbildung die Optimierung unterstützen. Grafische Darstellungen unterstützen das Verständnis der Kontrollflussstruktur und die Planung von Optimierungsschritten.