Kontrollflussgraph

gerichteter Graph als Modell

Ein Kontrollflussgraph ist ein Begriff aus der Informatik und bezeichnet einen gerichteten Graphen, der dazu dient, den Programmablauf eines Computerprogramms zu beschreiben. Kontrollflussgraphen werden unter anderem zur Programmoptimierung eingesetzt.[1]

Jeder Kontrollflussgraph besteht aus

  • einer Menge von Knoten  , die die Grundblöcke des beschriebenen Programms darstellen, sowie
  • einer Menge von gerichteten Kanten  , die mögliche Übergänge, d. h. Programmabläufe darstellen.

Üblicherweise fügt man zur Knotenmenge zusätzlich einen speziellen Eingangs- und Ausgangsknoten hinzu, für die im Programm keine Anweisungen existieren. Diese entsprechen dem Betreten bzw. Verlassen des entsprechenden Programmabschnitts.[2]

Wenn von einem Knoten mehrere Kanten wegführen (der Knoten also Quelle mehrerer gerichteter Kanten ist), so entspricht das einer Verzweigung. Schleifen finden sich als Zyklen in Kontrollflussgraphen wieder. Beispielsweise zeigt der Zyklus   im unten abgebildeten Graph   an, dass im zugrundeliegenden Computer-Programm eine Schleife enthalten ist.

Beispiele

Bearbeiten
 
Kontrollflussgraph   mit unerreichbarem Code
 
Kontrollflussgraph   mit Schleife

Im abgebildeten Graphen   mit Eingangsknoten   und Ausgangsknoten   existiert kein Pfad vom Eingangsknoten   zum Knoten  . Der Grundblock   stellt damit toten Code dar.

Graph   enthält einen Zyklus. Das zugrundeliegende Programm enthält damit eine (implizite oder explizite) Schleife.

Siehe auch

Bearbeiten

Einzelnachweise

Bearbeiten
  1. Javad Yousefi: Masking wrong-successor Control Flow Errors employing data redundancy. Hrsg.: IEEE. 2015, S. 201–205, doi:10.1109/ICCKE.2015.7365827 (englisch, archive.org).
  2. Aho, Alfred V., Aho, Alfred V.: Compilers : principles, techniques, & tools. 2nd ed Auflage. Pearson/Addison-Wesley, Boston 2007, ISBN 0-321-48681-1.