On Mon, Jun 28, 2010 at 8:40 AM, Peter Lobsinger <[email protected]> wrote: > On Sun, Jun 27, 2010 at 11:50 PM, chromatic <[email protected]> wrote: >> On Sunday 27 June 2010 at 23:05, Peter Lobsinger wrote: >> >>> The problem with doing register allocation before IMCC is that IMCC >>> creates temporary registers and does so in a very simple, inefficient >>> way (every temporary in a function consumes an independant register). >> >> This wouldn't be a problem if the generated PIR reused temporaries. >> POST->PIR >> doesn't. > > Those aren't the temporaries I'm referring to. Many PIR operations > which appear to be single ops compile down to multi-op sequences which > use temporary registers. For example "sqrt $N0, $I0" is internally > "set $N<temp>, $I0 ; sqrt $N0, $N<temp>". As another example, every > function call that IMCC cannot resolve statically uses a > find_sub_not_null and a temporary. It can be almost guaranteed that > any HLL compilation will hit several cases of these IMCC internal > temporaries. > >>> I'm not saying that we should keep register allocation in IMCC, but >>> rather that it should occur in a phase *after* IMCC has finished >>> allocating its temproraries. >> >> I'm not sure we have enough information available at that point; IMCC has >> already thrown away what it needs to know by then. We *could* modify IMCC to >> keep that around, but that means modifying IMCC. > > Does IMCC really have more information than that available in PBC? > What information is present in PIR, isn't present in PBC, and is > relevant to register allocation or optimization in general? > >> For historical reference, the point at which I decided that IMCC wasn't worth >> my own time to revise heavily was fixing its register allocator. We'd have >> to >> tease out the various uses of its SymReg struct into multiple separate >> types-- >> that's the source of the O(n^4) and O(n^8) algorithms now. > > By all means, replace IMCC then.
That's what I thought 3 years ago :-) It's called PIRC. Got very far, but stuck now and not long enough time slots and/or energy available to look into it. Would be happy to answer any questions though, if somebody decides to take it up. PIRC has a register allocator based on linear scan algorithm. Works nicely! cheers, kjs But whatever replaces it will also > need to create these temporaries if it is to provide the same kind of > op selection and desugaring to protect the users from lower-level > aspects of Parrot. Full register allocation can only occur after the > selection/desugaring step. > _______________________________________________ > http://lists.parrot.org/mailman/listinfo/parrot-dev > _______________________________________________ http://lists.parrot.org/mailman/listinfo/parrot-dev
