Re: Value range tracing

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

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