Callee save with the caller passing the used registers?

Question

In compiler design, why instead of having a caller or callee register saving arrangement, couldn't the caller pass its list of used registers (that it would push in case of a caller saving arrangement) to the callee so that the callee can compare its list of used registers to the registers used by the caller. Then only the registers that really need to be pushed, would be pushed. Am I missing something?

Answer 1

that's very inefficient... you will need to parse the list (for every function!) which is totally unnecessary.

Answer 2

It's an interesting idea. I think there are two things that make it less than attractive:

• The callee has to reserve stack space for the worst case, regardless.
• To make it efficient, you would need special instructions for storing and loading sets of registers at one go. Such instructions were on the Motorola 68000 (and maybe also PowerPC), but they have not been popular.

Here is a little elaboration of how it would have to work: You would want the caller to pack the list into a machine word as a bit vector. You would then need the callee to bitwise-and with its own list, the have an instruction that saves all the registers named by the resulting bit vector.

Because you are going to have to reserve space on the stack for the worst case, you don't save much---on a modern, superscalar, out-of-order processor, writes into the same cache line are nearly free.

It's also true that if what you really want is to minimize the number of loads and stores at run time, you just go with all caller-saves registers. This strategy also makes it really cheap to raise an exception and to pre-emptively switch threads, and plenty of compilers (like OCaml) use it for that reason. Callee-saves registers are a kind of a hack to try to cut down on the code size for the spill and reload instructions. They work in many situations, and they save space because call sites far outnumber procedure definitions (on average, a procedure contains multiple calls).

For more info about tradeoffs between caller-saves and callee-saves registers, there's a nice paper by Jack Davidson and David Whalley.