Re: Value range tracing

jeremy@suede.sw.oz.au (Jeremy Fitzhardinge) wrote:
>Hi all,
>
>I'm wondering if people bother with value range tracing. That is,
>keeping track of the possible range of variables at each point in the
>program. For example: [snip]


I am glad you asked. You should look at the preprint of the paper
"Eliminating Range Checks Using Static Single Assignment Form" by
Gough and Klaeren, which you can get from my home page


http://www.dstc.qut.edu.au/~gough


In general, many different kinds of assertions may be passed around in
a CFG. Jason Patterson, at PLDI-95 described using a similar scheme
for passing around value-density attributes to allow very accurate
branch predictions. Corney and Gough also used a similar scheme for
passing around bounds on the type in a language with bounded
polymorphism, to eliminate runtime type tests.


Anyhow, in all these cases the use of SSA is critical, with the
general idea being that of Wegman and Zadeck's constant propagation.
In the case of the Gough and Klaeren paper the main difference is that
the computation on the lattice uses "all values" as TOP, and "empty
range" as BOTTOM, with convex cover as the merge operation. There is
also an application of not-quite-standard interval arithmetic
involved. The correctness of these computations _relies_ on arithmetic
overflows being trapped.


These techniques can get rid of many range checks and overflow checks
from value-safe languages. As with constant propagation, the
technique also leads to dead-code removal. However, a practical
difficulty is that in languages with dynamically sized arrays the
value ranges need to be symbolic, ratherthan constants, which is a
more difficult problem.


John
--

Return to the comp.compilers page.
Search the comp.compilers archives again.