freenode/#sicl - IRC Chatlog
Search
6:23:09
beach
For some reason, I started thinking about register allocation. Probably in order to distract me from stuff that absolutely needs to be done, like finishing the papers before the deadline.
6:23:39
beach
Is it possible that existing techniques for register allocation don't take function calls and callee-saves registers into account?
6:29:35
beach
Also, most x86 instructions have an additional restriction that the result register and the first operand register are the same. I have not seen that restriction taken into account either.
6:31:58
beach
And, at a program point where there are not enough registers to hold all lexical variables, which variable is assigned to a register may depend on how soon it is likely to be used again, and whether a register needs to be saved because it has been modified.
6:33:49
beach
I have really looked into only one technique, namely graph coloring, and it takes into account none of these aspects. Nor does it allow for the register assignment to change at some program point. A variable is either permanently assigned to a register, or never assigned to a register.
6:36:07
beach
So it seems to me that external function calls should be looked at first. A variable that is live across such a call should preferably be assigned to callee-saves registers, if it is to be assigned to a register at all.
6:37:15
beach
Then, the assignment of variables to caller-saves registers can be totally different after a function call compared to the assignment before the call.
6:38:04
beach
... simply because all the caller-saves registers must be saved before the call anyway, if it has been modified. And no such register has any known contents after the call.
6:39:55
beach
I wonder whether all these restrictions might make some greedy approach feasible. Or some traditional search algorithm like alpha-beta with a very good heuristic.
6:41:30
beach
If an inner loop is likely to execute several times, the cost of arranging the registers before the loop and re-arranging them after the loop is going to be negligible.
6:45:26
alandipert
i suspect tracing JITs take calls and modifications into account when they (re) allocate registers. at least i vaguely recal reading about something like this in either the HP Dynamo or one of the Truffle papers
6:52:10
alandipert
ie training a model on allocating registers in reference programs and the learning function is the execution profile. or this in concert with various other heuristics as you mention
6:56:30
alandipert
plus you're making SICL, which exactly the kind of thing that would make it easy for interested people to try
7:15:02
beach
That's my secret hope, that once I get something working, more people will be contributing.
7:15:44
beach
And that's why I want the code to be as implementation-independent and as maintainable as possible.
7:32:38
alandipert
battery about to die. i might not be able to sleep, but i definitely won't be back for awhile. so goodnight for real o/
15:17:54
scymtym
::notify heisig (apply #'mapcar …) in SEALABLE-METAOBJECTS::COMPUTE-STATIC-CALL-SIGNATURES signals an error if the generic has no methods
15:39:33
heisig
scymtym: Thanks for pointing this out. Incidentally, I spent the whole day working on that ELS submission already.
15:39:33
Colleen
heisig: scymtym said 21 minutes, 39 seconds ago: (apply #'mapcar …) in SEALABLE-METAOBJECTS::COMPUTE-STATIC-CALL-SIGNATURES signals an error if the generic has no methods
15:47:41
heisig
That bug was a classic - transposing a list using (apply #'mapcar #'list ...) - which fails for zero arguments.