Reducible and irreducible control flow graph

The set of control flow graphs can be partitioned (divided) into reducible and irreducible control flow graphs . This classification goes back to Frances E. Allen . Hecht and Ullman give equivalent characterizations to Allen's original definition and use them to show that structured control structures always generate reducible control flow graphs. A list of alternative characterizations can be found in a later publication.

An important for the definition of a reducible control flow graph concept is that a backward edge (Engl. Back edge ). If one in the course of a depth-first search of a control flow graph , which at the node , starting off from a node along the edge to a node passes, which has already been detected, it is called the edge rearward edge . ${\displaystyle G\langle V,E,r\rangle }$ ${\displaystyle r}$ ${\displaystyle u}$ ${\displaystyle u\to v}$ ${\displaystyle v}$ ${\displaystyle u\to v}$

A control flow graph is reducible if and only if it fulfills one of the following three (mutually equivalent) conditions. ${\displaystyle G\langle V,E,r\rangle }$

1. Each depth-first search finds the same amount of backward edges.
2. Be a back edge. Then the knot dominates . ${\displaystyle u\to v}$ ${\displaystyle v}$ ${\displaystyle u}$
3. ${\displaystyle G}$does not contain a subgraph of the form , whereby the drawn dashed edges represent paths.

Irreducible control flow graphs are called irreducible .

The distinction between reducible and irreducible control flow graphs is of interest in computer science insofar as more efficient algorithms generally exist for reducible control flow graphs .

bibliography

1. ↑ Frances E. Allen : Control flow analysis . In: SIGPLAN Notices . tape 5 , no. 7 , July 1970, p. 1-19 .
2. ^ Matthew S. Hecht, Jeffrey D. Ullman : Flow Graph Reducibility . In: STOC . 1972, p. 238-250 .
3. ^ Matthew S. Hecht, Jeffrey D. Ullman: Characterizations of Reducible Flow Graphs . In: Journal of the ACM . tape 21 , no. 3 , July 1974, p. 367-375 .