Thu, 15 Jul 2010 09:54:10 -0700 (PDT)

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.