Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #2599

Nitty-gritty aspects of register allocation

Show key headers only | View raw

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

Back to comp.compilers | Previous | Next — Next in thread | Find similar

Thread

Nitty-gritty aspects of register allocation Elijah Stone <elronnd@elronnd.net> - 2020-09-10 16:41 -0700
  Re: Nitty-gritty aspects of register allocation "Alexei A. Frounze" <alexfrunews@gmail.com> - 2020-09-10 18:01 -0700
    Re: Nitty-gritty aspects of register allocation Bo Persson <bo@bo-persson.se> - 2020-09-11 11:44 +0200
  Re: Nitty-gritty aspects of register allocation anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2020-09-11 10:35 +0000

csiph-web