Re: Strahler number and register allocation

Alex McDonald <blog@rivadpm.com>
Thu, 15 Jul 2010 09:54:10 -0700 (PDT)

          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: Alex McDonald <blog@rivadpm.com>
Newsgroups: comp.compilers
Date: Thu, 15 Jul 2010 09:54:10 -0700 (PDT)
Organization: Compilers Central
References: 10-07-014 10-07-015
Keywords: registers, optimize
Posted-Date: 15 Jul 2010 17:21:57 EDT

On 14 July, 14:54, Tomasz Kowaltowski <t...@ic.unicamp.br> 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).
>
> Strahler numbers work as long as you have an expression tree. It is a
> very simple task to adapt the algorithm for operators with any any
> arity: unary, binary, ternary and so on.
>
> -- Tomasz Kowaltowski
> [How does it compare to Sethi-Ullman numbering? -John]


Tomasz Kowaltowski himself outlined the algorith here on c.c. in 2002;
http://compilers.iecc.com/comparch/article/02-06-053


Examples and an explanation of the algorithm can be found at these
links;


http://www.cs.oberlin.edu/~jdonalds/331/lecture29.html
http://cg.scs.carleton.ca/~morin/teaching/3002/notes/dataflow.pdf
http://pages.cpsc.ucalgary.ca/~robin/class/510/cg-expressions.pdf
http://www.prog.uni-saarland.de/teaching/cc/2009/slides/l12_codegen.pdf


Post a followup to this message

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