Re: register allocation questions

At 3:08 PM -0700 10/28/04, Bill Coffman wrote:
>  It passes the other tests, plus the
> randomized tests that I created, up to 150 symbols.  At that range, it
> still takes about 20x longer than g++ -O2, for equivalent programs to
> compile (see gen4.pl).

Still, that's not bad.

> Also, it is currently running about O(n^2) for n symbols, where the
> old one was running about O(n^3) from my analysis.  The spill code is
> still very expensive, and has a large constant associate.  I also have
> data, which is attached.  The difference doesn't show up until a lot
> of spilling is going on, around 80 symbols or so.

I'm curious to see how it behaves once the spilling gets up into the 
1000+ symbol range. Dropping from cubic to quadratic time ought to 
make a not-insignificant change in the running time, even if that 
constant's pretty big. :)

> I've learned a lot about how the compiler works at this point, and I'd
> like to contribute more :)
>
> Would you like a patch?

Yes! Oh, yeah, definitely.

> Well, I'm making some comments on the below stuff.
>
> On Thu, 28 Oct 2004 09:07:05 -0400, Dan Sugalski <dan@xxxxxxxxx> wrote:
> >  At 9:36 PM +0200 10/27/04, Leopold Toetsch wrote:
> >  >Dan Sugalski wrote:
>  > >>At 11:09 AM +0200 10/26/04, Leopold Toetsch wrote:
>  > >>While true, in the general case leaving 0-15 as non-preferred
> >  >>registers will probably make things easier. Those registers,
> >  >>especially the PMC ones, are going to see a lot of thrash as
> >  >>function calls are made, and it'll probably be easier to have them
> >  >>as scratch registers.
>
> I guess I don't agree.  I'd like to pack down the number of registers
> used to a minimum.  Then when a function is called, only those needed
> registers are copied in/out.  Don't think the functionality exists.
> But the idea is to have each sub declare how many registers to
> save/restore.  This would then save 0-k such registers.  Where k is
> the number of registers used by the sub.  Pack 'em down, minimize the
> number needed.
>
> We can also minimize this number to match the physical architecture
> that parrot is running on (for an arch specific optimization).  The
> imc_reg_alloc function does not have 32 hard coded in there (well a
> little bit, but can be easily changed).  It's pretty dynamic.

By all means, go for it. I certainly don't want to curb your 
enthusiasm. It's the right thing to do, ultimately. I didn't want to 
presume on your time. Happy to have it, of course. :)

>  > >[1] all except Dan's 6000 lines subroutines :) Did you start
> >  >creating real subs for your code already?
> >
> >  I wish. :( Unfortunately not, outside some simple stuff, and I doubt
> >  I will. The language just doesn't lend itself to that sort of thing.
> >  We're going to add actual real subroutines to the language after we
> >  roll out into production, but that doesn't help now, alas.
>
> Interesting.  I'd like to test on something like that.  Maybe SPEC99 as well.

If you've got a patch, I'd be more than happy to give it a whirl, and 
I can likely get you a copy of the code in question to give a run on.
--
                                Dan

--------------------------------------it's like this-------------------
Dan Sugalski                          even samurai
dan@xxxxxxxxx                         have teddy bears and even
                                      teddy bears get drunk