Rakudo *Needs* Register Allocation

kjstol parrotcode at gmail.com
Mon Jun 28 19:13:05 UTC 2010


On Mon, Jun 28, 2010 at 8:40 AM, Peter Lobsinger <plobsing at gmail.com> wrote:
> On Sun, Jun 27, 2010 at 11:50 PM, chromatic <chromatic at wgz.org> 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
>


More information about the parrot-dev mailing list