Data flow analysis

from Wikipedia, the free encyclopedia

A data flow analysis is a static code analysis of a computer program that examines between which parts of a program data is passed and which dependencies result from it. The aim of such analyzes is to optimize the code in terms of execution time (by deleting superfluous code, restructuring or parallelization) and memory usage.

Data flow analyzes are divided into the following types:

  • Forward analyzes in which the program code is examined with the help of the control flow graph and
  • Backward analyzes in which the program code is examined using the reverse control flow graph.

Basic principle

all information before and after a block has been run through

Data flow analyzes mostly work on the control flow graph, the nodes of which form so-called blocks, some also on the dominator tree . These blocks contain one or more statements. Data flow analyzes examine how data changes through a block. For example, if a block contains the code x: = 5, the data of the program change so that the variable x contains the value 5 after running through this block, regardless of which or whether it previously contained a value.

It also examines how the data changes between the blocks. In the simplest case, they are simply passed on. However, if several control flows (or edges of the control flow graph) flow together (e.g. in the case of loops), the information from the preceding blocks is either combined or cut. According to this, a distinction is made between must (for intersections) and may analyzes (for union).

See also

literature