Re: Value range tracing

John Gough <>
9 Dec 1995 19:44:30 -0500

          From comp.compilers

Related articles
[3 earlier articles]
Re: Value range tracing (1995-12-09)
Re: Value range tracing (1995-12-09)
Value range tracing (Dave Lloyd) (1995-12-09)
Re: Value range tracing (1995-12-09)
Re: Value range tracing (1995-12-09)
Value range tracing (1995-12-09)
Re: Value range tracing (John Gough) (1995-12-09)
Re: Value range tracing (Jason Patterson) (1995-12-09)
Re: Value range tracing (1995-12-09)
Re: Value range tracing (1995-12-17)
Re: Value range tracing (1995-12-17)
| List of all articles for this month |

From: John Gough <>
Newsgroups: comp.compilers
Date: 9 Dec 1995 19:44:30 -0500
Organization: Distributed Systems Technology Centr
References: 95-12-014
Keywords: optimize, bibliography (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

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.


Post a followup to this message

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