Re: math expressions optimalization

"Tomasz Kowaltowski" <tomasz@ic.unicamp.br>
17 Jun 2002 00:12:10 -0400

          From comp.compilers

Related articles
math expressions optimalization trix@polbox.com (Trix) (2002-06-13)
Re: math expressions optimalization Sid-Ahmed-Ali.TOUATI@inria.fr (Sid Ahmed Ali TOUATI) (2002-06-14)
Re: math expressions optimalization misar@rbg.informatik.tu-darmstadt.de (Walter Misar) (2002-06-14)
Re: math expressions optimalization dimock@deas.harvard.edu (Allyn Dimock) (2002-06-14)
Re: math expressions optimalization tomasz@ic.unicamp.br (Tomasz Kowaltowski) (2002-06-17)
History: Strahler or Ershov? tk@ic.unicamp.br (Tomasz Kowaltowski) (2008-05-05)
| List of all articles for this month |

From: "Tomasz Kowaltowski" <tomasz@ic.unicamp.br>
Newsgroups: comp.compilers
Date: 17 Jun 2002 00:12:10 -0400
Organization: Compilers Central
References: 02-06-032
Keywords: code, optimize
Posted-Date: 17 Jun 2002 00:12:10 EDT

"Trix" <trix@polbox.com> wrote:


> I`m going to implement simple alghoritm to optimalize math
> expressions in terms of use of memory cells.


As far as I know, this problem has been solved independently by many
people and has several variants like minimizing the stack positions
used to evaluate an expression or minimizing the number of temporary
variables as in this case.


Just build a tree representing the expression. For the example given in
your message you get:


                                          +
                                      / \
                                    * *
                                  / \ / \
                                a b c +
                                                  / \
                                                + d
                                              / \
                                            a c




Now label nodes of the tree using the following recursive rules:


(1) A leaf receives the label 0.


(2) If the the two children of an inner node have equal labels, say
        'n', then the node receives the label 'n+1'; otherwise it receives
        the maximum of the two labels.


In your case:




                                          +2
                                      / \
                                    *1 *1
                                  / \ / \
                                a b c +1
                                0 0 0 / \
                                                +1 d
                                              / \ 0
                                            a c
                                            0 0


Now generate your code by choosing first the subtree whose root has a
higher
label and reusing temporaries when they are free:


      x1 = a*b
      x2 = a+c
      x2 = x2+d
      x2 = c+x2
      x1 = x1+x2


Again you get two temporaries (I assumed '+' is left assiociative, but
it does not change the result in this case). It is easy to prove that
this algorithm produces an optimal result.


This kind of numbering of the tree nodes is related to what is known
as Strahler numbers -- they are used also in geography to describe
complexity of confluent streams!


The problem bocomes much harder (NP-complete?) when you try to reuse
common subexpressions. I recall there is an old paper by Sethi & Bruno
about this subject.


-- Tomasz Kowaltowski


Post a followup to this message

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