Re: Value range tracing (Henry Baker)
9 Dec 1995 19:10:26 -0500

          From comp.compilers

Related articles
Value range tracing (1995-12-01)
Re: value range tracing (David Whalley) (1995-12-09)
Re: Value range tracing (1995-12-09)
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)
[5 later articles]
| List of all articles for this month |

From: (Henry Baker)
Newsgroups: comp.compilers
Date: 9 Dec 1995 19:10:26 -0500
Organization: nil organization
References: 95-12-014
Keywords: analysis, optimize (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 (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:

Post a followup to this message

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