2
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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.

Common subexpressions: I don't know of any nice way to express this in that framework (though there could always be something I'm not aware of).

Improve this answer
$\endgroup$
2
  • $\begingroup$ If we deal with machine integers what would happen to the range computation? $\endgroup$
    – user1868607
    Commented Dec 19, 2016 at 13:01
  • $\begingroup$ @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). $\endgroup$
    – D.W. ♦
    Commented Dec 19, 2016 at 14:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.