Re: math expressions optimalization

"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

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