Re: Value range tracing

hbaker@netcom.com (Henry Baker)
9 Dec 1995 19:10:26 -0500

          From comp.compilers

Related articles
Value range tracing jeremy@suede.sw.oz.au (1995-12-01)
Re: value range tracing whalley@sed.cs.fsu.edu (David Whalley) (1995-12-09)
Re: Value range tracing hbaker@netcom.com (1995-12-09)
Re: Value range tracing preston@tera.com (1995-12-09)
Re: Value range tracing schinz@guano.alphanet.ch (1995-12-09)
Value range tracing dave@occl-cam.demon.co.uk (Dave Lloyd) (1995-12-09)
Re: Value range tracing bernecky@eecg.toronto.edu (1995-12-09)
Re: Value range tracing creusil@cri.ensmp.fr (1995-12-09)
Value range tracing deaeni@auto-trol.com (1995-12-09)
[5 later articles]
| List of all articles for this month |

From: hbaker@netcom.com (Henry Baker)
Newsgroups: comp.compilers
Date: 9 Dec 1995 19:10:26 -0500
Organization: nil organization
References: 95-12-014
Keywords: analysis, optimize

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
--


Post a followup to this message

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