Wed, 02 Apr 2008 11:39:14 -0400

Related articles |
---|

Looking for the name of an optimization ccox@comcast.net (Chris Cox) (2008-03-31) |

Re: Looking for the name of an optimization dnovillo@acm.org (Diego Novillo) (2008-03-31) |

Re: Looking for the name of an optimization cfc@shell01.TheWorld.com (Chris F Clark) (2008-04-02) |

Re: Looking for the name of an optimization andreybokhanko@gmail.com (2008-04-13) |

From: | Chris F Clark <cfc@shell01.TheWorld.com> |

Newsgroups: | comp.compilers |

Date: | Wed, 02 Apr 2008 11:39:14 -0400 |

Organization: | The World Public Access UNIX, Brookline, MA |

References: | 08-03-123 08-03-124 |

Keywords: | optimize |

Posted-Date: | 02 Apr 2008 22:55:27 EDT |

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

------------------------------------------------------------------------------

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.