[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

register allocation

From: Stefan Israelsson Tampe
Subject: register allocation
Date: Sat, 17 Nov 2012 18:33:27 +0100

Hi all,

If I've not miss - understood wingo's and Marks intention for native code, there need to be a intermediate format
to output from tree-il that is different from the rtl bytecode. One of the reason's for this is that one need a better format in
order to do register allocations well. What I can do to quickly output examples for this language is for the compile-glil
port to compile-rtl add another emit command e.-g. emit-tree where for example

(<lexical-ref>  ... )

get's an emitting of

(ref I #f )

where I is an identity for the memory slot

furthermore there will be a set  meaning setting a variable e.g.

(set I #f), and (set I reg) for sources that

we can have sinks as well e.g. for function call registers e.g. typically they add a constraint on the used register

(sink I reg) (sink I #f)

with set! and sink we can model the constraints that are imposed by the function argument and return values
or even user demanded constraints.

numbers 10 15 25 is also included in the list and will represent the actual cost for doing any work

*  will represent an action that will clobber any register, we could add (* reg1 reg2 reg3) to refine this but this will be for later.

branches e.g. <condition> will be represented by

((w1 code-x) (w2 code-y))

w1 is the weight for branch 1 and w2 will be the weight for branch 2, w1 + w2 = 1. with this we can make sure that
register allocation can take advantage of a (unlikly pred) hint for an if as well as if we profile code we can analyze which numbers
to put for w1 and w2 due to statistics about the branches, I suppose we need a phi statements or the goto that letrec and named let's
will end up generating. Not sure what to do with them, but I will in the first version assume they are not imposing any constraints.
If the arguments of the head of the code representing the phi is allocated in the first pass to a register that information can be used at
a second pass or something like that.

The fun part is that this representation is almost for free using the tree-il representation due to not having the goto you have in c++ and c.
If we would like to generate this representation for such languages that include them I suspect that everything will be more costly. I think thik
wingo said something along this line previusly on the net no?

What I have now is an register allocator for non constrained cases. I have a plan to incorporate the constraints as well and I will probably finish
that work within a week or so. So, we will then have a register allocator in scheme that can make use of constraints coming from register arguments both as
caller and calle as well as return register(s). But not only this it will be able to intelligently make use of branch hints as well. Also one version will be a linear scan
like algorithm, But we will be able totest out more intelligently or more stupidly (if i'm  algorithms as well

Again this is a lot of experimenting maybe we will use it or we don't but this module can be used separately.

Have fun

reply via email to

[Prev in Thread] Current Thread [Next in Thread]