Reduzierbarer und irreduzierbarer Kontrollflussgraph

Die Menge der Kontrollflussgraphen kann in reduzierbare und irreduzierbare Kontrollflussgraphen partitioniert (geteilt) werden. Diese Einteilung geht auf Frances E. Allen zurück.[1] Hecht und Ullman geben äquivalente Charakterisierungen zu Allens ursprünglicher Definition und benutzen diese, um zu zeigen, dass strukturierte Kontrollstrukturen stets reduzierbare Kontrollflussgraphen erzeugen.[2] Eine Auflistung alternativer Charakterisierungen findet sich in einer späteren Veröffentlichung.[3]

Ein für die Definition eines reduzierbaren Kontrollflussgraphen wichtiger Begriff ist der einer Rückwärtskante (engl. backedge). Wenn man im Zuge einer Tiefensuche eines Kontrollflussgraphen ${\displaystyle G\langle V,E,r\rangle }$, die beim Knoten ${\displaystyle r}$ startet, ausgehend von einem Knoten ${\displaystyle u}$ entlang der Kante ${\displaystyle u\to v}$ zu einem Knoten ${\displaystyle v}$ gelangt, der schon entdeckt worden ist, so nennt man die Kante ${\displaystyle u\to v}$ Rückwärtskante.

Ein Kontrollflussgraph ${\displaystyle G\langle V,E,r\rangle }$ ist genau dann reduzibel, wenn er eine der folgenden drei (untereinander äquivalenten) Bedingungen erfüllt.

1. Jede Tiefensuche findet dieselbe Menge an Rückwärtskanten.
2. Sei ${\displaystyle u\to v}$ eine Rückwärtskante. Dann dominiert ${\displaystyle v}$ den Knoten ${\displaystyle u}$.
3. ${\displaystyle G}$ enthält keinen Untergraphen der Form , wobei die eingezeichneten gestrichelten Kanten Pfade repräsentieren.

Nicht reduzierbare Kontrollflussgraphen n​ennt man irreduzierbar.

Die Unterscheidung i​n reduzierbare u​nd irreduzierbare Kontrollflussgraphen i​st in d​er Informatik insofern v​on Interesse, a​ls für reduzierbare Kontrollflussgraphen i​m Allgemeinen effizientere Algorithmen existieren.

Bibliographie

1. Frances E. Allen: Control flow analysis. In: SIGPLAN Notices. Band 5, Nr. 7, Juli 1970, S. 1–19.
2. Matthew S. Hecht, Jeffrey D. Ullman: Flow Graph Reducibility. In: STOC. 1972, S. 238–250.
3. Matthew S. Hecht, Jeffrey D. Ullman: Characterizations of Reducible Flow Graphs. In: Journal of the ACM. Band 21, Nr. 3, Juli 1974, S. 367–375.