Re: Looking for the name of an optimization

"Diego Novillo" <dnovillo@xxxxxxx> writes:

On Mon, Mar 31, 2008 at 8:36 PM, Chris Cox <ccox@xxxxxxxxxxx> wrote:

if (x == 1 && y == 2)
z = 300 / (x + y)
==>
if (x == 1 && y == 2)
z = 100

In GCC we call it VRP, value range propagation.

It falls out of the singularity that happens when you have ranges
where min == max: In this case, inside the then clause of that if(),
the range for x is [1, 1], the range for y is [2, 2]. After
propagation, GCC substitutes x with 1, y with 2 and the folders do the
rest.

The names I have heard for that optimization, from most to least
general are:

1) value range propagation

propagating the set of values that a variable (or
expression) might have, often restricted to min..max
type calculations--hence the word range.

2) value propagation (or value numbering)

propagating the exact value (2 for x, 1 for y) that a
variable (or expression) might have. note in value
propagation, one can also propagate symbolic
expressions, and optimize things like


if (x == y && y != 0)
z = 300 / (x + y)
==>
if (x == y && y != 0)
z = 100 / y; // does not overflow

by noting that x and y are the same value (without knowing)
exactly what the value of y is (other than non-zero).


3) constant propagation

propagating the exact constant value that a variable
(or expression) has.

Note in each case the key word is propagation, that is one takes a
fact established somewhere in a program (the definition point) and
propagates that fact to uses of the variables or expressions involved
in that fact. The key thing one needs is a way of representing the
facts known about variables to keep in the internal database the
compiler is using. For example, with constant propagation, one
usually keeps the value of the constant itself as the representation
(with some way of indicating that a constant value is not know). In
value numbering, one keeps records of where a value for a variable was
computed (looks like ssa doesn't it), and uses the pointer to (number
of) that record as the representation. In min-max value range
propagation, one keeps pairs (min and max) values as the
representation--note that the min and max values could either be
constants (the simple case) or value numbers (the harder case)
depending upon how much complexity one wants to bite off. You can
even do set theoretic computations if you are willing to keep
representations of sets in your database.

Hope this helps,
-Chris

******************************************************************************
Chris Clark Internet: christopher.f.clark@xxxxxxxxxxxxxxxxxxxxxx
Compiler Resources, Inc. or: compres@xxxxxxxxxxxxx
23 Bailey Rd Web Site: http://world.std.com/~compres
Berlin, MA 01503 voice: (508) 435-5016
USA fax: (978) 838-0263 (24 hours)
------------------------------------------------------------------------------
.