|Value range tracing firstname.lastname@example.org (1995-12-01)|
|Re: value range tracing email@example.com (David Whalley) (1995-12-09)|
|Re: Value range tracing firstname.lastname@example.org (1995-12-09)|
|Re: Value range tracing email@example.com (1995-12-09)|
|Re: Value range tracing firstname.lastname@example.org (1995-12-09)|
|Value range tracing email@example.com (Dave Lloyd) (1995-12-09)|
|Re: Value range tracing firstname.lastname@example.org (1995-12-09)|
|Re: Value range tracing email@example.com (1995-12-09)|
|Value range tracing firstname.lastname@example.org (1995-12-09)|
|[5 later articles]|
|From:||email@example.com (Henry Baker)|
|Date:||9 Dec 1995 19:10:26 -0500|
firstname.lastname@example.org (Jeremy Fitzhardinge) wrote:
> 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 good example deleted]
> Is this kind of thing useful? Is it useful enough to implement?
> This isn't very complex, so I assume people have thought about it,
> but I've seen very little literature on it.
> I suppose it is, in effect, a more general handling of constant
> propagation. Rather than saying "this particular value is here", you
> can say "this range is possible". On the other hand, ranges are
> somewhat limited as well, since you might want to say "this variable is
> a power of 2" or something similar. However, I suspect attaching
> general functions expressing constraints to variables in the compiler
> would be hard to deal with to get useful information (unless, I
> suppose, you wrote the compiler in prolog).
1. 'value range tracing' has been researched. Among other references, see
ftp://ftp.netcom.com/pub/hb/hbaker/TInference.html (also .ps.Z).
2. To do a really good job on this can cause exponential blowup during the
3. You typically still only solve the 'first-order' problem, where the
endpoints of all the ranges are _compile-time constants_. Unfortunately,
most of the really important problems have ranges in which one of the
endpoints is not known at compile time -- e.g., an array passed to a subroutine
as an argument. Solving this class of problems bumps the complexity up
by a lot.
4. Interestingly, a closely allied problem -- that of keeping track of
whether an integer is divisible by some compile-time constant, or whether
a variable has a certain compile-time alignment, is readily solveable by
these techniques. So you could keep track of variables which were 'even'
or 'odd', or variables which were word-aligned. This last case is important
for pipelined machines, where a subroutine might want to special case
aligned arguments (or might _have_ to special case them to keep track
of multiple banks of memory -- e.g., Multiflow).
I think that using ML-style type inference can easily handle the alignment
inference problem, although I don't have any references.
Return to the
Search the comp.compilers archives again.