Re: Looking for the name of an optimization

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


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


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

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