Basic Principles
It is the process of collecting information about the way the variables are used, defined in the program. Data-flow analysis attempts to obtain particular information at each point in a procedure. Usually, it is enough to obtain this information at the boundaries of basic blocks, since from that it is easy to compute the information at points in the basic block. In forward flow analysis, the exit state of a block is a function of the block's entry state. This function is the composition of the effects of the statements in the block. The entry state of a block is a function of the exit states of its predecessors. This yields a set of data-flow equations:
For each block b:
In this, is the transfer function of the block . It works on the entry state, yielding the exit state . The join operation combines the exit states of the predecessors of, yielding the entry state of .
After solving this set of equations, the entry and / or exit states of the blocks can be used to derive properties of the program at the block boundaries. The transfer function of each statement separately can be applied to get information at a point inside a basic block.
Each particular type of data-flow analysis has its own specific transfer function and join operation. Some data-flow problems require backward flow analysis. This follows the same plan, except that the transfer function is applied to the exit state yielding the entry state, and the join operation works on the entry states of the successors to yield the exit state.
The entry point (in forward flow) plays an important role: Since it has no predecessors, its entry state is well defined at the start of the analysis. For instance, the set of local variables with known values is empty. If the control flow graph does not contain cycles (there were no explicit or implicit loops in the procedure) solving the equations is straightforward. The control flow graph can then be topologically sorted; running in the order of this sort, the entry states can be computed at the start of each block, since all predecessors of that block have already been processed, so their exit states are available. If the control flow graph does contain cycles, a more advanced algorithm is required.
Read more about this topic: Data-flow Analysis
Famous quotes containing the words basic and/or principles:
“There’s one basic rule you should remember about development charts that will save you countless hours of worry.... The fact that a child passes through a particular developmental stage is always more important than the age of that child when he or she does it. In the long run, it really doesn’t matter whether you learn to walk at ten months or fifteen months—as long as you learn how to walk.”
—Lawrence Kutner (20th century)
“The proposition that Muslims are welcome in Britain if, and only if, they stop behaving like Muslims is a doctrine which is incompatible with the principles that guide a free society.”
—Roy Hattersley (b. 1932)