Re: non trivial constant folding

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

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