Rakudo *Needs* Register Allocation

Peter Lobsinger plobsing at gmail.com
Mon Jun 28 07:40:05 UTC 2010


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. 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.


More information about the parrot-dev mailing list