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

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

+
/ \
* *
/ \ / \
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
the maximum of the two labels.

+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