9 Dec 1995 19:16:06 -0500

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

Re: Value range tracing gough@dstc.qut.edu.au (John Gough) (1995-12-09) |

[4 later articles] |

From: | preston@tera.com (Preston Briggs) |

Newsgroups: | comp.compilers |

Date: | 9 Dec 1995 19:16:06 -0500 |

Organization: | /etc/organization |

References: | 95-12-014 |

Keywords: | analysis, optimize |

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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.