Re: Strahler number and register allocation

George Neuner <gneuner2@comcast.net>
Wed, 14 Jul 2010 13:28:59 -0400

          From comp.compilers

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)
| List of all articles for this month |

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.