Re: Value range tracing

jeremy@suede.sw.oz.au (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
inference phase.


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.


--
www/ftp directory:
ftp://ftp.netcom.com/pub/hb/hbaker/home.html
--

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