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: | 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
Return to the
comp.compilers page.
Search the
comp.compilers archives again.