6 Jan 2001 22:13:51 -0500

Related articles |
---|

non trivial constant folding mpointie@eden-studios.fr (Mickaël Pointier) (2001-01-05) |

Re: non trivial constant folding broeker@physik.rwth-aachen.de (Hans-Bernhard Broeker) (2001-01-05) |

Re: non trivial constant folding mihai@cs.wisc.edu (Mihai Christodorescu) (2001-01-06) |

Re: non trivial constant folding pat@jantar.org (Patryk Zadarnowski) (2001-01-06) |

Re: non trivial constant folding bonzini@gnu.org (2001-01-06) |

Re: non trivial constant folding idbaxter@semdesigns.com (Ira D. Baxter) (2001-01-06) |

Re: non trivial constant folding cfc@world.std.com (Chris F Clark) (2001-01-06) |

Re: non trivial constant folding anton@mips.complang.tuwien.ac.at (2001-01-09) |

Re: non trivial constant folding anton@mips.complang.tuwien.ac.at (2001-01-09) |

Re: non trivial constant folding metzger@rsn.hp.com (Robert Metzger) (2001-01-09) |

Re: non trivial constant folding sjmeyer@www.tdl.com (2001-01-09) |

Re: non trivial constant folding henry@spsystems.net (2001-01-09) |

Re: non trivial constant folding dew@cray.com (2001-01-09) |

[10 later articles] |

From: | Chris F Clark <cfc@world.std.com> |

Newsgroups: | comp.compilers |

Date: | 6 Jan 2001 22:13:51 -0500 |

Organization: | Compilers Central |

References: | 01-01-015 |

Keywords: | arithmetic, optimize |

Posted-Date: | 06 Jan 2001 22:13:51 EST |

*> My problem is that I do not manage to find a clean solution*

*> to optimise this:*

*>*

*> eval(1+var+1)*

What you are looking for is sometimes called "canonicalizing" (or

sorting). You order the leaves of each expression (of commutative

operators) so that the constants are first (or last) and then move

them down to the lowest level (of associative operators)--this part is

often called reassociation. You can also apply the distributive law

(or DeMorgan's theorem or any other algebraic identity that holds(*))

to further collect the constants. For example, Fred Chow, organized

his expressions to "tower" to the left (or perhaps it was right) to

minimize register usage.

You can find information in Advanced Compiler Design and

Implementation, by Steven S Munchnick (ISBN 1-55860-320-4) pp.333-355

where it discusses Algebraic Simplifications and Reassociation. It is

also covered in Building an Optimizing Compiler by Robert Morgan (ISBN

1-55558-179-X).

*) One common issue is that computer arithmetic (especially floating

point) does not obey the normal arithmetic identities. Computing

operations in a different order can often cause over- or underflows

that change the numeric value. In addition, some machines have guard

bits on the registers that allow them to hold "more accurate" values

in registers than they do in memory, introducing round-off errors.

Imagine how upset your user will be when after testing (in a program)

the discriminant of a quadratic equation for a negative value (and

getting false), and then computing the root and getting an incorrect

imaginary number. (This actually happened in a FORTRAN compiler

after we did some local optimizations without paying close enough

attention to the ramifications.)

Although, the problem is commonly recognized in floating point, the

same problem can occur with integer arithmetic, especially when the

arithmetic overflows. Depending on the hardware, you can cause

exceptions to be raised (or not to be raised), if you cavalierly

reorder integer arithmetic that can overflow (and use the

instructions that trap overflows).

Hope this helps,

-Chris

*****************************************************************************

Chris Clark Internet : compres@world.std.com

Compiler Resources, Inc. Web Site : http://world.std.com/~compres

3 Proctor Street voice : (508) 435-5016

Hopkinton, MA 01748 USA fax : (508) 435-4847 (24 hours)

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.