5
$\begingroup$

In original implementations of the B language, the caller was responsible for saving and restoring any registers it cares about before calling a function.
But in the C language, the called function is responsible for saving and restoring any registers it is going to use.

Consider this code:

for (index=0; index<1000; ++index) {
    tally += f(index);
}

In B, the active registers can be saved before the loop and restored after it.
That's 1 save and 1 restore.

In C, the function will preserve and restore the same register values every time it is called.
That's 1000 saves and 1000 restores.

The first convention seems far more efficient, especially in cases where the function uses many registers.
There doesn't appear to be any advantage to the second convention.

Yet, C was designed and implemented after B, and most other compiled languages developed since then follow that same convention.

Here is a description from 1981 by Johnson and Ritchie:

The Basic Call/Return Process

3. Control passes to the called procedure.
4. The bookkeeping registers and register variables of the calling procedure are saved so that their values can be restored on return

8. The returned value, if any, is put in a safe place while the stack space is freed, the calling procedure’s register variables and bookkeeping registers are restored, and the return address is obtained and transferred to.
The C Language Calling Sequence

A current definition from The Linux Foundation:

Registers r6 through r13, r15, and f8 through f15 are nonvolatile; that is, they "belong" to the calling function.
A called function shall save these registers' values before it changes them, restoring their values before it returns.
Function calling sequence

If a function uses any of r6 through r13, it must save and restore them each time it is called.

It is more efficient for the caller to preserve whichever registers it needs, so why was this seemingly far less efficient convention chosen?

NOTE:

This question is about actual implementations, not about the design of the language itself, which says nothing about how calling stacks etc. should be implemented.

Also note that I'm asking about why this decision to change the protocols already in use with B was made for the very first C compilers in the 1970s. I am not asking whether it is a good or bad idea for more recent hardware architectures, but why such as major change was made at that time.

$\endgroup$
4
  • 1
    $\begingroup$ Register windows mitigate a lot of the cost of saving/restoring registers, as long as the call stack isn't too deep. $\endgroup$ Commented May 19, 2023 at 1:54
  • $\begingroup$ @chrisaycock, that concept didn't exist in the 1970s. $\endgroup$ Commented May 19, 2023 at 2:05
  • 1
    $\begingroup$ Your question is not clear: are you talking about the first implementation of C on the PDP-11? Modern implementations typically have some registers be caller-saved and some be callee-saved, with rules (part of the ABI specification) that depend on the CPU type (and on some platforms, also on the OS). I have no idea where you're going with “most other compiled languages developed since then follow that same convention”: languages don't define register conventions, implementations do, and implementations typically follow the platform's ABI to be able to link with system libraries. $\endgroup$ Commented May 19, 2023 at 7:37
  • $\begingroup$ @Gilles'SO-stopbeingevil', I'm talking about every implementation of C that I've seen. And as you say, libraries could have been written in any language, and those languages too must follow this convention of having the registers preserved by the called function. (I've added a couple of real examples.) $\endgroup$ Commented May 19, 2023 at 12:23

2 Answers 2

9
$\begingroup$

How registers behave across function calls is part of the calling conventions defined by a particular language implementation. To facilitate cross-implementation and cross-language calls, most platforms specify a calling convention that holds for all programs on a particular CPU architecture, or at least on a particular operating system on a particular architecture. The standard term for a register that a function must save if it modifies it is callee-saved register, also called preserved register or nonvolatile register. The standard term for a register that the caller must save before calling a function is caller-saved register, also called clobbered register or volatile register.

Note that this is not particularly related to the programming language. C, in particular, does not mandate any particular rule. I am not aware that C is markedly different to other programming language in terms of favoring caller-saved or callee-saved registers.

Your assertion that making all registers caller-saved is more efficient is simply wrong. Sometimes caller-saved registers are more efficient, sometimes callee-saved registers are more efficient. Having both gives a chance to pick the more efficient kind where it matters.

Let's look at your example:

for (index=0; index<1000; ++index) {
    tally += f(index);
}

Let's suppose that tally and index are each stored in a register. What's the most efficient way to manage these registers? It depends on what f does!

If the compiler puts the variables in a caller-saved register, they have to be saved and restored around each loop iteration. If the compiler puts the variable in a callee-saved register, then whether they are saved or not depends on f. If f is a small function that doesn't do much (e.g. it's just an array lookup), then maybe it doesn't touch these registers, and so the registers don't need to be saved at all. On the other hand, if f is a complex function that needs all the registers it can have, it will need to save those registers at each call. So that's either a significant saving with callee-saved registers (if f uses very few registers, then typically it doesn't do much, and saving registers would be costly relative to the code of f), or indifferent.

On the other hand, for variables that don't change across the loop, having caller-saved registers is more efficient, as you note.

Another advantage of callee-saved registers is that a function has only one implementation, but is typically called from many sites. If the code to save registers (and also code to adjust the stack pointer) is inside the function, this leads to more compact code. More compact code is faster code since it spends less time getting loaded and it uses caches more efficiently.

Certain kinds of registers practically have to be of a particular type. Registers that influence how the processor works (for example, configuring memory mappings or floating point rounding modes) are pretty much always callee-saved, because most functions don't modify them: the rare functions that need a nonstandard value have to save and restore such registers. Conversely, some registers that are very frequently modified, such as condition flag registers, are typically caller-saved, because almost all functions will modify them, but callers often don't need to preserve them across function calls. Registers that contain function parameters are effectively caller-saved since the calling code itself modifies them, and registers that contain function return values are effectively caller-saved since it's the callee's job not to preserve them.

As a special case, when function calls take place across a privilege level, it's always the job of the most privileged side to save and restore registers: when privileged code starts, it can't trust anything about the values in registers that were written by the non-privileged code, so it needs to restore anything that it cares about; and when privileged code ends, it must wipe any confidential data from registers, since it can't trust that the non-privileged code won't read them.

See also:

$\endgroup$
6
  • $\begingroup$ Thanks (+1). One problem I have trouble with is that most of the modern registers didn't exist back when C was first implemented, and it was the programmer, not the compiler, that suggested which variables should be in registers. Anyone writing that loop wouldn't bother to suggest that index or tally should be registers, since their use is trivial compared with whatever it is the function does. The other problem is that before C, I was intimate with the workings of B, which had caller-saved registers, and I still don't understand why the switch was made from one method to the other. $\endgroup$ Commented May 21, 2023 at 1:20
  • $\begingroup$ @RayButterworth In response to my comment under your question, you clarified that you were asking about C implementations in general, and not about the specific case of the original C implementation on the PDP-11 (which is extremely register-starved by modern standards). If you want to know what choices went into that specific implementation, that would be a different (also on-topic) question. $\endgroup$ Commented May 21, 2023 at 10:08
  • $\begingroup$ I did ask in context of "C was designed and implemented after B". I've just added a note about this at the end to make it more explicit. $\endgroup$ Commented May 21, 2023 at 13:10
  • $\begingroup$ Your latest edit completely contradicts your previous one where you stated you were asking about “every implementation”! Please don't edit answered questions in ways that invalidate answers. There's really room for separate questions here, go ahead and ask a second one! $\endgroup$ Commented May 21, 2023 at 19:14
  • $\begingroup$ "you stated you were asking about “every implementation”" — No. That wasn't an edit, it was in a comment. And it meant that this situation was true in "every implementation". Once a decision has been made, future versions will have to use the same conventions so that the libraries stay compatible. The language B was written by Ken Thompson and Dennis Ritchie in 1969, so I guess the fundamental question is why Ritchie changed the convention when he wrote and implemented C. $\endgroup$ Commented May 21, 2023 at 20:33
5
$\begingroup$

The C language does not require that it be implemented on a register transfer machine, let alone define which registers are callee-save and which registers are caller-save.

This is the job of the ABI on a given platform. For example, there is an ABI for x64 on Windows, and the SysV ABI is used for x64 pretty much everywhere else.

The ABI document says which registers are used for various purposes, such as:

  • parameter passing,
  • return values,
  • return location on CPUs without call and return instructions,
  • thread-local storage,
  • position-independent code on CPUs that need to reserve a register for this, and
  • which general-purpose registers are callee-save and which are caller-save across a call.
$\endgroup$
4
  • 1
    $\begingroup$ The question isn't about the design of the language, it's about the implementation. (I've just clarified the Title accordingly.) $\endgroup$ Commented May 19, 2023 at 3:25
  • 1
    $\begingroup$ I don't believe the C language standard mentions this at all. Do you know something that I don't? $\endgroup$
    – Pseudonym
    Commented May 19, 2023 at 3:45
  • 1
    $\begingroup$ @Pseudonym: The C language doesn't fully specify any particular dialect. Most dialects of C can interoperate with programs written in other languages; calling conventions used for such interop are part of the semantics of the dialects in question, rather than just implementation details. $\endgroup$
    – supercat
    Commented Jul 17, 2023 at 16:43
  • $\begingroup$ In the 1980s, the Microsoft C Compiler had a P-code (i.e. stack machine) backend for those times when memory usage was more precious than execution time. $\endgroup$
    – Pseudonym
    Commented Jul 17, 2023 at 23:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .