Re: Value range tracing

jeremy@suede.sw.oz.au (Jeremy Fitzhardinge) writes:


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


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


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.


At the cheapest level, we do constant propagation , which isn't really
range propagation but serves as a nice starting point. Constant
propagation notices statements like i = 10 or i = j + k, where j and k
can be proven to be constant. Most compilers, in my experience, don't
even bother to do this very well.


There's also value numbering, which notices when values are equal.


A slightly more expensive form of constant propagation would notice
conditional branches, things like


if (i == 10) {
...
}


and propagate the fact that i is 10 throughout all the blocks
dominated by the true branch of the test. Wegman and Zadeck suggest
this in the POPL version of their paper on constant propagation. I
wrote a paper, with Keith Cooper and Linda Torczon, describing exactly
how to go about it, but we were never able to collect good numbers
showing whether or not it was useful, and never got it published. I
haven't come across a compiler that does it systematically.


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.


Generally, this all involves testing for the feasibility of a set of
linear inequalities. Most of the better compilers do this to support
their dependence analysis. In that case, we want to test the
_integer_ feasibility of a set of linear inequalities -- a more
expensive proposition. A typical approach is to use Fourier-Motzkin
variable elimination. An extended version of this technique is used
in the Omega test, by Bill Pugh.


I don't know of anyoe who tries to use this technique for entire
routines. It's quite expensive and the extra benefit obtained (over
ordinary value numbering, say) may be quite small. I don't know of
any experiments though.


And we could try to handle still more general relationships, things
like ax + by >= c where a, b, x, and y are allowed to be arbitrary
variables, or sin(y) = 0.5, or x^2 + xy + y^2 = 0. It just gets out
of hand.


I probably haven't been very clear, sorry. An extended example might
help. The problem is that the very simple example you showed is
wonderful, but the very simple cases don't arise that often. Is it
worth writing some special-purpose optimizer machinery to handle a
case that never arises? It's easy to generalize to cases that occur
more frequently, but those are very expensive to solve at compile
time, and nobody's sure that there's enough benefit to warrant the
effort. Be a nice set of experiments for some enterprising soul, but
it'd be difficult to publish the results.


Preston Briggs
--

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