What is a proper way to handle caller/callee saved register?

Question

Hi I'm writing a tiger compiler from the book "Modern Compiler Implementation in C" and have some questions with caller and callee saved registers.

As described by the book, when calling a function, the caller need to save registers that satisfy:

1. Is a caller-save register(In x86-64: rax, rcx, rdx, rsi, rdi, r8, r9, r10, r11)
2. Is alive for the call instruction
3. Defined by the callee

Similarly for callee, it need to save the following registers:

1. Is a callee-saved register(In x86-64: rbx, r12-15)
2. Defined in the callee

Thus I the following is what I think should be true:

1. Caller/callee-saved are physical registers, this makes the procedure to analyze liveness and identify callee definition of registers lines after register coloring.
2. It is inefficient to simply push the relative registers into the stack, since there may be chances that other registers are not in use and can take the value temprarily.

Therefore, I would like to ask that "Do I have to do a second time liveness analysis and register coloring??"

What if after coloring, the callee uses more registers and require a new loop of this??

Furthermore, when calling external function(runtime C functions compiled by gcc), I should save and restore all registers that are alive in the call instruction right?

Answer 1

The details depend on how you encode register constraints, i.e., the need to use specific physical regs.

One common thing is "pre-coloring". Let's say you have a function func with an argument x which returns one value. Then your code generator (instruction selection) could emit the following sequence (this is AT&T syntax, so ins src,dst):

mov x,%rdi
call func
mov %rax,res

So we emit code connecting our virtual registers with physical registers. The register allocator then has to connect the dots. Liveness analysis should see, that %rdi is born in the move and dies in the call.

In general, when calling random external functions, you won't know which registers that function will clobber. So you'll have to spill all caller-saves registers. If your register allocator is smart enough, it can move them to callee-saves registers, but I'd keep it simple in the beginning. Register allocation is super hard and debugging it is hell.