Control flow graph

The following important information is missing from this article or section:

Applications are missing or not detailed (e.g. elimination of dead codes), examples are insufficient (appearance of common control flow elements such as if / while / goto is completely missing)

Help Wikipedia by researching and pasting it .

A control flow graph is a term from computer science and describes a directed graph that is used to describe the control flow of a computer program . Among other things, they are used for program optimization .

construction

Each control flow graph consists of

• a set of nodes representing the basic blocks of the program described, as well as ${\displaystyle V}$
• a set of directed edges that represent possible transitions, ie program sequences. ${\displaystyle E}$

Usually a special input and output node is added to the node set, for which there are no instructions in the program. These correspond to entering or exiting the corresponding program section.

If several edges lead away from a node (the node is therefore the source of several directed edges), this corresponds to a branch . Loops can be found as cycles in control flow graphs. For example, the cycle in the graph below shows that there is a loop in the underlying computer program. ${\displaystyle B\to C\to E\to D\to B}$ ${\displaystyle G_{2}\langle V,E,A\rangle }$

Examples

Control flow graph with unreachable code ${\displaystyle G_{1}}$

Control flow graph with loop ${\displaystyle G_{2}}$

In the graph shown with input node and output node, there is no path from input node to node . The basic block thus represents dead code . ${\displaystyle G_{1}}$ ${\displaystyle A}$ ${\displaystyle F}$ ${\displaystyle A}$ ${\displaystyle G}$ ${\displaystyle G}$

Graph contains a cycle. The underlying program thus contains an (implicit or explicit) loop . ${\displaystyle G_{2}}$

See also

• Dominance relation (control flow graph)
• Program schedule
• Reducible and irreducible control flow graph
• Compiler construction
• McCabe metric

Individual evidence

1. ↑ : Masking wrong-successor Control Flow Errors employing data redundancy . IEEE, pp. 201-205. doi : 10.1109 / ICCKE.2015.7365827
2. ^ Aho, Alfred V., Aho, Alfred V .: Compilers: principles, techniques, & tools . 2nd ed. Pearson / Addison-Wesley, Boston 2007, ISBN 0-321-48681-1 .