Could this problem be helped by a Genetic Algorithm similar to GEQO on PostgreSQL? For those not in the know on this, PostgreSQL has a "Genetic Query Optimizer" that kicks in when the number of joins in an SQL statement exceed a certain number. As the number of joins increases, the number of possible plans that must be explored explode exponentially. For a realistic number of joins the complexity becomes so much that the "Planner" takes longer to plan the query than it takes to execute (or at least a non-insignificant fraction thereof).
This is actually a well-known, and long-solved, problem--compilers have been dealing with this for as long as there have been compilers, as almost all hardware CPUs have been register based for decades. The algorithm we're using's one of these solutions.
What we're running into's either a limitation of the chosen algorithm (the code that makes it fall down *is* really nasty) or an issue with the implementation in a corner case. If it's an implementation issue then it's just a matter of writing the fallback code (which is potentially non-trivial, but not as bad as reimplementing things) or grabbing an alternate heavily abused algorithm and going with that. (Again, potentially non-trivial, but at least well-known, which is good)
There may be genetic algorithms for this particular sort of problems -- I'm not sure. It'd be interesting to go look, though.
-----Original Message----- From: Dan Sugalski [mailto:[EMAIL PROTECTED] Sent: Thursday, August 05, 2004 11:15 AM To: Butler, Gerald Cc: [EMAIL PROTECTED] Subject: RE: Spilling problems
[Cc'd back to the list, since it's of general interest] At 9:51 AM -0400 8/5/04, Butler, Gerald wrote:upI hate to intrude on this discussion, but, I was wondering if anyone could give a brief explanation (or point me to a resource) that explains what exactly is meant by "Register Spilling" and what the issues involved are.
My understanding is that this is a problem of trying to keep local variables of a sub/function in the Parrot registers without pushing/popping to/from a stack and/or saving/restoring to heap. Optimization includes doing code analysis to know when a particular local variable can be discarded, to freethe registers, because it is no longer needed, and also, what registers to swap out when another is needed such that you minimize swapping of values in registers.
Is my understanding at all correct?
Yep, that's pretty much it.
This isn't an issue with plain PASM, as there's no register spilling at all going on there--all register access is absolute, which is just fine. No local variables at all.
With PIR, though, there are locals that aren't bound to registers as such. These are named variables declared with .local and symbolic registers which use the format $Pxxx (or $Ixxx, $Sxxxx, or $Nxxx). These named locals and symbolic registers need to be in real registers when they're being used, which is where the register coloring and spilling comes in.
Parrot's got some code in it to scan the source, locate all the locals and symbolic registers, and map them to real registers. If there are fewer of these symbolic registers in use than real registers it's easy to do the mapping, if there are more then the PIR compiler needs to generate code to temporarily shuffle the unused ones off to a holding area, and shuffle them back when they're needed again.
The algorithm to do this shuffling is iterative. It'll do a run through, allocate things as best it can, then if there are leftover things that didn't get put in real registers it does the loop again. And again, and again, and again... unfortunately there's some code that our algorithm won't ever be able to generate a perfect mapping for, no matter how many times through the loop it goes. Eventually this exhausts memory and the compile dies.
This is more likely to happen the more temps you have, and the larger the chunk of code you're trying to compile. Unfortunately for me, some of my code's extraordinarily large (60-80k lines) and triggers the degenerate behaviour. To fix this we need to have the feedback loop just give up after some number of trips through and generate functional, if sub-optimal, code, since sub-optimal and running's better than dying with an out-of-memory error. (Which is also a potential compromise/DOS attack on parrot, so it needs fixing for security reasons too)
-----Original Message----- From: Dan Sugalski [mailto:[EMAIL PROTECTED] Sent: Thursday, August 05, 2004 9:44 AM To: Leopold Toetsch Cc: [EMAIL PROTECTED] Subject: Re: Spilling problems
At 11:47 AM +0200 8/5/04, Leopold Toetsch wrote:Dan Sugalski wrote:... In this case I'm hitting the double spill error, but this is, I expect, tied in with the infinite loop the register spiller hits on some code.
Should be fixed now. Hopefully. - There were 2 bugs in the code WRT calculating life range of spilled regs and the ordering of registers was suboptimal.
It does indeed fix that problem. Cool, thanks. (I'm giving one of the nasty chunks of code I've got a test to see how it runs, but it may take a while to check)
It's probably a Leo or Melvin thing (unless anyone's see Angel Faus recently) to thump the register spilling code to have a fairly stupid fallback scheme (after X tries, or when we hit double spill) rather than trying to be optimal, but this one's going to need to get addressed.
Spill just all in one pass?
Yeah. Give a dozen or two passes through the code doing optimized spilling, and after that just give up and spill what's left. -- Dan
--------------------------------------it's like this------------------- Dan Sugalski even samurai [EMAIL PROTECTED] have teddy bears and even teddy bears get drunk
The information contained in this e-mail message is privileged and/or confidential and is intended only for the use of the individual or entity named above. If the reader of this message is not the intended recipient, or the employee or agent responsible to deliver it to the intended recipient, you are hereby notified that any dissemination, distribution or copying of this communication is strictly prohibited. If you have received this communication in error, please immediately notify us by telephone (330-668-5000), and destroy the original message. Thank you.
-- Dan
--------------------------------------it's like this------------------- Dan Sugalski even samurai [EMAIL PROTECTED] have teddy bears and even teddy bears get drunk
The information contained in this e-mail message is privileged and/or confidential and is intended only for the use of the individual or entity named above. If the reader of this message is not the intended recipient, or the employee or agent responsible to deliver it to the intended recipient, you are hereby notified that any dissemination, distribution or copying of this communication is strictly prohibited. If you have received this communication in error, please immediately notify us by telephone (330-668-5000), and destroy the original message. Thank you.
--
Dan--------------------------------------it's like this-------------------
Dan Sugalski even samurai
[EMAIL PROTECTED] have teddy bears and even
teddy bears get drunk
