Why is it better to do the data flow analysis in the basic blocks

Question

I have been reading about compilers and it is said that doing the data flow analysis in the basic blocks is more optimal.

Sadly, quoting the exact source, would be slightly hard as it is not in English, but a quote from wikipedia can also be used:

Data-flow analysis is the process of collecting information about the way the variables are used, defined in the program. It 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.

Even though, in Wikipedia it is slightly explained, why the basic blocks are the preferred way, I still do not understand the benefits and if it is not obtained from the basic blocks, then from where?

Answer 1

It isn't "better" in the sense that the analysis is more precise. It's just more compact and cheaper to compute.

There's no reason why you can't compute an old-school iterative bit-vector-based dataflow analysis at every point between two intermediate-representation instructions. It will give you the same answer as doing it on basic blocks.

The main issue is that doing it this way, you need to store and manipulate the data at every point between two IR instructions. And remember, the only variable lifetimes that change across an instruction are the variables that participate in that instruction, so the sets on each side of an instruction are mostly the same. This is wasteful, especially on older machines.

Having said all that, we generally don't do dataflow analysis this way any more. Almost all modern compilers use some variant of static single assignment form. SSA form is cheap enough on modern machines, and gives you a more precise analysis: not only does SSA form give you the definitions that reach a program point, for example, it also gives you the paths along which those definitions reach.