Re: Value range tracing

Jason Patterson <jason@reflections.com.au>
9 Dec 1995 19:48:01 -0500

          From comp.compilers

Related articles
[4 earlier articles]
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)
Re: Value range tracing gough@dstc.qut.edu.au (John Gough) (1995-12-09)
Re: Value range tracing jason@reflections.com.au (Jason Patterson) (1995-12-09)
Re: Value range tracing bill@amber.ssd.hcsc.com (1995-12-09)
Re: Value range tracing vadik@cs.umd.edu (1995-12-17)
Re: Value range tracing mab@wdl.loral.com (1995-12-17)
| List of all articles for this month |

From: Jason Patterson <jason@reflections.com.au>
Newsgroups: comp.compilers
Date: 9 Dec 1995 19:48:01 -0500
Organization: University of Queensland
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.
> [ example deleted ]


I presented a paper at this year's PLDI about using exactly
that kind of analysis to perform static branch prediction:


    Jason Patterson. "Accurate Static Branch Prediction by Value
    Range Propagation". Proceedings of the SIGPLAN '95 Conference
    on Programming Language Design and Implementation, June 1995,
    pages 67-78.




> Is this kind of thing useful? Is it useful enough to implement?


Well, speaking from a static branch prediction perspective, it
turns out that it gives you a pretty significant improvement
over the standard heuristic approaches (eg Ball&Larus). Not a
*huge* improvement, but enough to be worth doing IMHO. This is
especially so if you believe that in the real world software
developers never use profile feedback :-(


As far as other uses go, value range propagation subsumes both
constant and copy propagation, and therefore assists in finding
more dead code. It is also of limited use in the elimination
of array bounds and type-hierarchy tests.




> This isn't very complex, so I assume people have thought about it,
> but I've seen very little literature on it.


Its been around for ages, but it has never really caught on...
See my paper for some references. I can send you a PostScript if
you want. Its not up on the web yet, sorry (coming RSN though :-)




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


The abstract interpretation folks have been doing advanced forms
of this for ages, but its generally been considered far too slow
to be used in a real compiler. Making it fast by restricting the
range representations to common cases is the big trick. But this
also restricts its power, of course. There's no such thing as a
free lunch. See my paper for what I consider to be a reasonable
tradeoff.




> So what do people do in practice? Or does everyone just use
> constants?


Yep, pretty much all the commercial compilers just wimp out and
use constant and copy propagation.




JASON PATTERSON
--


Post a followup to this message

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