17 Jun 2002 00:12:10 -0400

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

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.