Re: Value range tracing

jeremy@suede.sw.oz.au (Jeremy Fitzhardinge) writes:
>I'm wondering if people bother with value range tracing....
>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.


preston@tera.com (Preston Briggs) writes:
>Sure you have, but it was couched in language that wasn't very
>helpful. There's a lot of ways to do this sort of thing, ranging from
>the not very useful but cheap to compute up to pretty useful for
>real-programs but too expensive for even Andy Glew. What gets built
>is usually the result of some sort of cost-benefit tradeoff in the
>compiler writer's head.


A overlooked area is found in hte literature for Ada compilers. Most
Ada Compilers do some amount of value range tracing becasue it allows
the compiler of optimize away many of the language required constraint
checks specified by the typing system (e.g. array index bounds checks,
assigning wide subtype to naroe subtype, etc.)


>Notice that the case I've shown above involves equality. If we want
>to handle things like i < 19, it's harder and more expensive.
>Vaugh Pratt showed a cute way to handle relationships like
> x <= y + c
>where x and y are variables, and c is a constant. By "handle", I mean
>the compiler walk over a routine's dominator tree, accumulating sets
>of these relationships (as well as the ordinary equality relationships
>implied by assignments). Given the set of relationships holding at
>any point, the compiler could answer certain questions, like does x =
>y, or is x < 10, or is x < y + 5, etc.
>Fancier (and more expensive) forms of analysis will handle
>relationships of the form ax + by + ... >= c, where a, b, and c are
>all constants and the sums are of arbitrary length.


Another possible area to look at is query optimization in SQL, where the
logical simplification of query conditons makes a large peed difference.


--
Mark Biggar
mab@wdl.loral.com
--

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