Friday, October 19, 2007

Caller-saves versus Callee-saves

Consider two functions say fun and bar and bar is calling fun, then bar is called the caller and fun is called the callee. All the registers saved by fun is called callee saved registers and the registers saved by bar is called caller saved registers. Now that we know what caller saved registers and callee saved registers are, let’s look into their role in register allocation.

A good complier will make sure that there are as many registers are available for allocator to work with. This is not always an easy job. When one function calls another function, the values in the registers used by the parent or the caller should not be altered by the child or the callee. One way to make sure this is happening is to save all the registers used by the caller just before calling the callee. Thus the callee can access all the registers without any restrictions and the allocator can also do its function efficiently. Another way for smooth functioning of the allocator is to make the callee save all the registers just before executing its main function body. Yet another way is to make sure that none of the registers used by the caller is allocated to the callee. The caller need to save only those registers which are live across the call and the callee need to save only the registers which are used inside the callee function. This is so because the registers allocator will have information about which all variables are live across a call in the caller and which all variables are used inside a callee function. Whenever a register is saved, it should be reloaded back into the registers either by the caller after the function call or by the callee just before returning to the parent depending on whether its caller saved or callee saved. So basically the only difference between the caller saves and callee saves comes down to when the registers get actually saved.

A compiler can be either use caller save strategy or callee save strategy, but this has got some problems. The entire caller saved registers may not be used in the callee function and not all the registers saved by the callee are live or used across the function call. We cannot avoid these unnecessary saves since when one function is being complied we don’t know the register usage of callee/caller. But unnecessary saves can be reduced by adopting a mix of caller save and callee save strategy. In this some set of registers will be marked as caller save registers and another set will be marked as callee saved registers. No registers will be in both the sets and all the registers available need not be in both the sets. So if any of the registers in the caller save list is live across the function call, then only they need to be saved and not all the registers live across the call. If a mixed strategy is used the variables that are live across a function call should be allocated to callee saved registers. This way, the caller doesn’t have to save these and ,with luck, they don’t have to be saved by the callee either (if the callee doesn’t use these registers in its body).