non trivial constant folding

"MickaŽl Pointier" <mpointie@eden-studios.fr>
5 Jan 2001 14:04:55 -0500

          From comp.compilers

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)
[16 later articles]
| List of all articles for this month |

From: "MickaŽl Pointier" <mpointie@eden-studios.fr>
Newsgroups: comp.compilers
Date: 5 Jan 2001 14:04:55 -0500
Organization: ImagiNET / Colt Internet
Keywords: optimize, question, comment
Posted-Date: 05 Jan 2001 14:04:54 EST

Hi.
I've been searching on the web for information about this
particular problem, as well as in my books ("Compiler
Construction" - Niklaus Wirth, and "Crafting a Compiler
with C" - Fisher/LeBlanc) but does not find anything
clear about it.


I'm parsing expression to create a tree made of nodes
that contains either "operators" or "values". This works
fine, so I've started to "optimise" the resulting tree with
a code that recursively compute all the operators that
have immediate childs that are two immediate numerical
values.


This works fine for an expression like this:


eval(1+2+3/2+4+5*8)


is translated in this tree:


+(+(+(+(1.000000,2.000000),/(3.000000,2.000000)),4.000000),*(5.000000,8.0000
00))


And optimised like this:


  Optimise + (1.000000+2.000000=3.000000)
  Optimise / (3.000000/2.000000=1.500000)
  Optimise + (3.000000+1.500000=4.500000)
  Optimise + (4.500000+4.000000=8.500000)
  Optimise * (5.000000*8.000000=40.000000)
  Optimise + (8.500000+40.000000=48.500000)


Giving this final evaluate expression:


48.500000


My problem is that I do not manage to find a clean solution
to optimise this:


eval(1+var+1)


is translated as:


+(+(1.000000,var),1.000000)


And I do not manage to optimise it.


(Of course eval(1+1+var) is optimised in "+(2.000000,var)")


I've been looking extensively on how I can reorganise my
expression tree, but do not manage to find any explanation.
I believe it's a question that's often ask (I found a question
on this subject by "Tim Pierce" in 1992 in this newsgroup,
but do not find the answer...)


Thanks in advance for any help


        Mickael Pointier


PS: Happy new year
[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]


Post a followup to this message

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