Compilers - Looking for the name of an optimization

Author

Looking for the name of an optimization

Chris Cox

2008-03-31, 10:25 pm

I've seen this optimization mentioned a few places, but nobody seems to
agree on the name.

So, I thought I'd ask and see if someone else seen a definitive name for it.

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

==>

if (x == 1 && y == 2)
z = 100

Can anyone help me name that optimization?

Thanks,
Chris

Diego Novillo

2008-03-31, 10:25 pm

On Mon, Mar 31, 2008 at 8:36 PM, Chris Cox <ccox@comcast.net> 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.

Diego.

Chris F Clark

2008-04-02, 11:03 pm

"Diego Novillo" <dnovillo@acm.org> writes:

> On Mon, Mar 31, 2008 at 8:36 PM, Chris Cox <ccox@comcast.net> wrote:
>
>
> 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@compiler-resources.com
Compiler Resources, Inc. or: compres@world.std.com
23 Bailey Rd Web Site: http://world.std.com/~compres
Berlin, MA 01503 voice: (508) 435-5016
USA fax: (978) 838-0263 (24 hours)
------------------------------------------------------------------------------

Sponsored Links