6 Jan 2001 22:11:24 -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) |

[13 later articles] |

From: | Patryk Zadarnowski <pat@jantar.org> |

Newsgroups: | comp.compilers |

Date: | 6 Jan 2001 22:11:24 -0500 |

Organization: | Compilers Central |

References: | 01-01-015 |

Keywords: | optimize |

Posted-Date: | 06 Jan 2001 22:11:24 EST |

On 5 Jan 2001, Mickaël Pointier wrote:

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

*> to optimise this:*

*>*

*> eval(1+var+1)*

*>*

*> [I've seen compilers that do that. With associative operators like +*

*> they combine all of the operands of a set of cascaded operators into*

*> a list or array, then sort that array to get the constants together.*

*> -John]*

A neater way to do this is to iteratively apply a series of tree

transformations to the AST, converting the tree into some

``canonical'' form in which all constants will naturally group

together. For example, you can alway require that, in a sum of

variable and a constant, the constant is the first operand (using

associativity), and, in any sum, the second operand is a leaf (using

commutativity of modulo addition). That is, if a, b and c are

expressions (possibly variables) and cN are constants, convert:

c1 + c2 -> c3

a + c1 -> c1 + a

a + (b + c) -> (a + b) + c

If you apply these three tranformations iteratively, constants will

propagate through the tree to the right place and will get folded

there if possible.

Note that this works for any associative and commutative operator, ie.

multiplication and the usual bitwise operators as well. Once, I've

even used it on the regular expression concatenation and "|" operators

in order to partition a large input alphabet into equivalence classes

directly from the AST.

This is a nicer way of tackling the problem than with lists, as you

can generalize the technique easily enough to optimize across pairs of

field operators (eg + and *, or AND and OR) using

distribution. Although you'll have to add about a dozen

transformations to your algorithm to do that, and more if you want to

tacle subtraction as well. Of course, it's easy enough to reuse the

same code for any pair of field operations.

Note however, that you are relying on the operators being associative,

commutative and distributive, and therefore, as somebody else already

mentioned in another posting, you will have to be careful with

floating point arithmetic, as floating point addition and

multiplication are neither commutative nor distributive.

Muchnick covers the technique in Advanced Compiler Design and

Implementation (section 12.3), although his treatment of it is

somewhat incomplete.

Pat.

Patryk Zadarnowski University of New South Wales

<pat@jantar.org> School of Computer Science and Engineering

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.