Control flow graph
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
- a set of directed edges that represent possible transitions, ie program sequences.
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.
Examples
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 .
Graph contains a cycle. The underlying program thus contains an (implicit or explicit) loop .
See also
- Dominance relation (control flow graph)
- Program schedule
- Reducible and irreducible control flow graph
- Compiler construction
- McCabe metric
Individual evidence
- ↑ : Masking wrong-successor Control Flow Errors employing data redundancy . IEEE, pp. 201-205. doi : 10.1109 / ICCKE.2015.7365827
- ^ Aho, Alfred V., Aho, Alfred V .: Compilers: principles, techniques, & tools . 2nd ed. Pearson / Addison-Wesley, Boston 2007, ISBN 0-321-48681-1 .