On 7/28/07, via RT chromatic <[EMAIL PROTECTED]> wrote: > # New Ticket Created by chromatic > # Please include the string: [perl #44229] > # in the subject line of all future correspondence about this issue. > # <URL: http://rt.perl.org/rt3/Ticket/Display.html?id=44229 > > > > Profiling some of the PGE tests reveals that our register allocation is fairly > expensive. Most of the time is in computing our dominators, and most of that > time goes through repeated calls to set_contains. > > I don't know enough about graphs and sets to see if we're using the naive > O(n^2) algorithm, or the Cooper, Harvey, Kennedy algorithm; someone who likes > CS more than I do and loves algorithms should peruse the paper and the code: > > http://www.hipersoft.rice.edu/grads/publications/dom14.pdf > > compilers/imcc/reg_alloc.c.
Did you use the -O flag when you were profiling? Parrot has two different register allocators. It normally uses the "vanilla register allocator", but the -O flag tells parrot to use the older register allocator. I don't know the specifics of the older algorithm, but the vanilla allocator definitely looks like it's O(n^2). There were some problems with the older allocator on large subroutines, so it was disabled. -- Matt Diephouse http://matt.diephouse.com
