Re: non trivial constant folding

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

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