Re: register allocation questions

Bill~

I have to say that I am really impressed by all of the work that you
are doing, and if you can make the internals of imcc a little more
approachable, you would be doing a great service.

Thanks,
Matt


On Thu, 28 Oct 2004 15:08:23 -0700, Bill Coffman <bill.coffman@xxxxxxxxx> wrote:
> Hi all,
> 
> Thanks for your continued comments.  Btw, I usually read all the
> parrot list, so don't think I'm not paying attention.
> 
> Currently, here's how the register allocator is doing.
> 
> Failed Test        Stat Wstat Total Fail  Failed  List of Failed
> -------------------------------------------------------------------------------
> t/library/dumper.t    5  1280    13    5  38.46%  1-2 5 8 13
> 4 tests and 51 subtests skipped.
> Failed 1/123 test scripts, 99.19% okay. 5/1956 subtests failed, 99.74% okay.
> 
> I recall Leo, or someone, saying that the data dumper routines are not
> following the calling convention properly.  So I've decided not to
> worry about it too much.  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).
> 
> 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've learned a lot about how the compiler works at this point, and I'd
> like to contribute more :)
> 
> Would you like a patch?  Should I fix the data dumper routines first?
> What is all this talk about deferred registers?  What should I do
> next?
> 
> 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:
> > >
> > >>>So, if you want that really super efficient, you would allocate
> > >>>registers around function calls directly to that wanted register number,
> > >>>which should be in the SymReg's want_regno.
> 
> Yes, I think we are kind of doing this.  It's best to pass the
> registers straight through though.  Like when a variable will be used
> as a parameter, give it the appropriate reg num.  Sort of outside the
> immediate scope of register coloring, but as I've learned, one must go
> a little beyond, to see the input and output for each sub.
> 
> > >>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.
> 
> > >Yep, that's the easy part ;) OTOH when the register allocator is
> > >doing register renaming anyway, the most inner loop with a function
> > >call should get registers assigned already matching the calling
> > >convemtions. With more then one call at that loop level, you have to
> > >move around registers anyway.
> 
> Yes, yes, renaming!  I want to do register renaming!
> 
> > Oh, sure, but keeping your scratch PMCs out of the way makes life a
> > lot easier for the register coloring algorithms. Might not be
> > optimal, but if it makes life simpler to start, optimal can come
> > later.
> 
> p31 holds all the spill stuff.  It's a pain.  Maybe I'll move that
> around, but if p31 is used, it means that there is no more room for
> symbols, in at least one of the reg sets.
> 
> > >[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.
> 
> - Bill Coffman
> 
> 
> 


-- 
"Computer Science is merely the post-Turing Decline of Formal Systems Theory."
-???