Nitty-gritty aspects of register allocation

There is a lot of research and a lot of resources on the high-level
aspects of register allocation--colouring interference graphs, lifetimes,
CFGs, etc.


But there are a lot of low-level architecture-specific things that these
models don't account for on their own. Most notably, not all registers
can be used for the same things. Just on amd64:


- Multiplication and division use the rdx:rax register pair.


- Bit shifts always use cl.


- When calling functions, their arguments have to go in specific registers.


In all of these cases, you can spill whatever happens to already be in
those registers, but it would be nicer if you could arrange for the
appropriate values to already be in the right places. But how? A naive
solution to the first two problems just makes rax/rcx/rdx the
lowest-priority registers except when doing a multiply/divide/shift; and
spills only if necessary (rare). But that's not a general solution
(imagine if every register has a few pieces of unique functionality), and
function calls reserve too many registers for that strategy to be
practical in that case.


Bonus microconsiderations (these seem much easier to model, but still not
trivial):


- Some registers need a special prefix to be used (REX prefix). These
    registers are generally different from the special-purpose registers
    (for e.g. multiplication). Is it better to put a non-multiplied value
    in a REX-prefixed register, or keep it in an unprefixed register and
    spill it later when you need to multiply?


- The second-lowest 8 bits of some registers can be addressed
    separately. When does it make sense to use them?


(All of these are x86-specific, and most architectures admittedly have
fewer esotericisms.)


--
time flies like an arrow;
fruit flies like a banana

Return to the comp.compilers page.
Search the comp.compilers archives again.