Wed, 14 Jul 2010 13:28:59 -0400

Related articles |
---|

Strahler number and register allocation krzikalla@gmx.de (Olaf Krzikalla) (2010-07-13) |

Re: Strahler number and register allocation tk@ic.unicamp.br (Tomasz Kowaltowski) (2010-07-14) |

Re: Strahler number and register allocation gneuner2@comcast.net (George Neuner) (2010-07-14) |

Re: Strahler number and register allocation gneuner2@comcast.net (George Neuner) (2010-07-14) |

Re: Strahler number and register allocation blog@rivadpm.com (Alex McDonald) (2010-07-15) |

From: | George Neuner <gneuner2@comcast.net> |

Newsgroups: | comp.compilers |

Date: | Wed, 14 Jul 2010 13:28:59 -0400 |

Organization: | A noiseless patient Spider |

References: | 10-07-014 |

Keywords: | registers, optimize |

Posted-Date: | 14 Jul 2010 13:51:24 EDT |

On Tue, 13 Jul 2010 17:31:38 +0200, Olaf Krzikalla <krzikalla@gmx.de>

wrote:

*>is it always correct, that the Strahler number of an expression tree*

*>denotes the minimal number of registers needed? The link in wikipedia*

*>referring to the original source is apparently broken. However IMHO the*

*>Strahler number can only be applied if the tree contains binary*

*>expressions only (which may not be the case anymore with e.g. fused*

*>multiply-add operations).*

*>Have anyone more insight in this topic or can give a link to an*

*>appropriate reference?*

AFAIK, Strahler is defined only over binary trees ... but an N-ary

tree can always be rewritten (with addition of internal nodes) into a

binary tree, so Strahler is a strict upper bound.

WRT fused operations, I believe the theory allows to treat them as a

single node ... the sub-tree representing the fused operation would

potentially add only 1 to the Strahler number because its internal

nodes are not visible.

ACM has a paper on extending the register function to N-ary trees

(http://portal.acm.org/citation.cfm?id=1159892.1159894) which has

>ites to earlier work - including Strahler's. I can send you a copy

if you don't have access.

Keep in mind that Strahler's work was in river management so I'm not

sure how readily his papers can be related to expression computation

(I've never read them). It may be easier to follow Ershov's work on

arithmetic expressions and look at some of the other applications of

Strahler's work.

George

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.