# Data-flow analysis problem adjust to Ullman-Aho's framework?

I am reading the classical book "Compilers. Principles, techniques and tools" by Aho et alii. On chapter 9.3 they talk about a general framework to solve data-flow analysis problems that use a framework which is monotone and of finite height.

The technique is shown to be useful for live variable and reaching definition analysis and I'm wondering if it is applicable to the following problems:

1. Checking if variables are always initialized.
2. Do range computations (the idea is to apply it on out of bounds array accesses check).
3. Eliminate common subexpressions.

My question is if this same framework can be used for this problem or I need more general frameworks such as the constant propagation framework described in chapter 9.4.

If the answer is yes what are the values of the framework defined as $(D,F,V,\land)$, where D is the direction of the analysis, F the family of transfer functions, V is the semilattice domain and $\land$ the semilattice operator? If the answer is no for some of the problems I don't really need this parameters for the more general framework but the reason why it doesn't work would suffice so that I can find a more general framework.

I ask this just in case somebody already know the answer and I can save me some time so don't worry about being too specific.

Checking initialization: Yes, you can use this framework. You need only a single boolean for each variable. The lattice is $V\to \{\bot,\top\}$, i.e., $2^V$, where $V$ is the set of variables. The height of this lattice is $n+1$ where $n=|V|$ is the number of variables. The transfer functions are monotonic. Consequently, you can use the framework.
Range computation: No. The lattice of ranges has infinite height. Consider, e.g., the sequence of ranges $[0,0]$, $[0,1]$, $[0,2]$, $[0,3]$, and so on: it never ends. Consequently, you need something more, such as widening operators.
• @Rodrigo, then the lattice of ranges has height $(2^{32})^n$ where $n$ is the number of variables. As a result the monotone framework might take an extremely long time to converge (as many as $2^{32n}$ steps). – D.W. Dec 19 '16 at 14:56