In Chapter 9 of the Dragon Book, the authors describe the dataflow framework for global analysis (described also in these slides). In this framework, an analysis is defined by a set of transfer functions, along with a meet semilattice.
At each step of the iteration, the algorithm works by maintaining two values for each basic block: an IN set representing information known to be true on input to the basic block, and an OUT set representing information known to be true on output from the basic block. The algorithm works as follows:
- Compute the meet of the OUT sets for all predecessors of the current basic block, and set that value as the IN set to the current basic block.
- Compute $f(IN)$ for the current basic block, where $f$ is a transfer function representing the effects of the basic block. Then set OUT for this block equal to this value.
I am confused about why this algorithm works by taking the meet of all the input blocks before applying the transfer function. In some cases (non-distributive analyses), this causes a loss of precision. Wouldn't it make more sense to apply the transfer function to each of the OUT values of the predecessors of the given block, then to meet all of those values together? Or is this not sound?
Thanks!