0

I'm currently working on the lab of CS61C from UC Berkeley. According to the slide, the caller-saved registers, including ra(return address), should be saved right before invoking another function and restored right after this. enter image description here

But in the sample code of this course, I found ra is stored together with s0, s1 (callee-saved register).

So what's the difference between these two kinds of registers? Should we actually treat them differently according to the calling convention?

enter image description here

KningTG
  • 77
  • 6
  • 1
    What research have you done before posting this question? Come on, there are at least dozens of questions asking about caller and callee saved registers on this site. – fuz Oct 05 '20 at 15:06

1 Answers1

3

ra and sp don't fit nicely into the classification of caller/callee (aka scratch/preserved).  These are both parameters passed to the function, with special purpose, and, note that these values/concepts are not directly visible in C programming.

The ra is a parameter — the place to return to — passed from the caller to the callee.  The sp is a parameter — the place below which stack memory can be allocated — passed from the caller to the callee.

ra is restored in epilog, not for the caller's sake, but because it is immediately needed by the jr ra instruction.  The code would work perfectly fine1 if the saved ra value was restored to t0 instead (still from 0(sp)), the only adjustment needed would be that jr then would do jr t0).

The sp also must be restored, but this one is for the caller, so that the caller's stack frame memory can be found where it was when it made the call — where the sp points upon return should be the same as where it was upon initial call.

Should we actually treat them differently according to the calling convention?

Treat them as they need to be treated by the definition of what they do, not strictly as either caller or callee saves.

Some texts will put ra into a caller saves classification, and others into a callee saves classification, but these are both over simplification as the real answer is that while ra exhibits qualities of both classifications, neither/special is more accurate.

In prologue/epilog, ra visually appears as callee saves, since it is saved and restored with other callee saves registers, but this is a red herring as the value being preserved is a parameter the callee will need to return to the caller, whereas the other callee saved register's initial values are meaningless to the callee and only saved so they can be restored to original.  Once the return address value is saved though, ra becomes a scratch register, meaning it can be used as a caller saves register, if an extra register is needed (it cannot be used as a callee saves register since it is, by definition, repurposed to make a call).

ra is passed in order that the function can return to whoever called it.  If the function invokes another function, the ra register will necessarily be repurposed so saving its original value in prolog and restoring in epilog make sense as that is as efficient as we can get.  The caller does not rely on ra upon return.

(Saving ra in prologue and restoring upon use effectively treats the return address as a memory variable that is initialized from the incoming ra value.  We have three ways to preserve variables that are live across a call (defined before and used after): callee saves, caller saves, and memory variables.  We could treat ra like a caller saves register saving and restoring around a call, but that would have only equal efficiency when in a function that has only one call not in a loop — otherwise the caller saves approach would be less efficient for non-leaf functions.  This analysis is similar with usages of other caller saves registers.)

sp is passed to communicate the boundary between free stack and in-use stack, and, if changed, this needs to be restored upon return.  (In some sense, sp is similar to an in & out parameter — though with specific purpose related restrictions: it is passed in for the callee to use for stack allocation, and passed back to the caller, restored to original.)

Parameters registers that are not used to pass parameters to the callee are caller saves (scratch) registers.  However, those that are passed are inherently different than simple caller saves registers, since they are initialized already.

ra is different than other passed arguments, in that this parameter is only used for only one purpose, namely by a final jr ra, well past the body of the function.  Because of this we can know without seeing the body of function the best way to preserve that value.  Whereas the other passed arguments are used fully within the body of the function, in function-specific ways, so their best save/restore is custom.

1 modulo hardware return address prediction

Erik Eidt
  • 23,049
  • 2
  • 29
  • 53
  • Is it necessary to restore sp on purpose since sp should restore itself after returning from called(all memory used by callee should be popped out) – KningTG Oct 05 '20 at 18:27
  • 2
    Only the `addi sp, sp, 12` restores the `sp`, nothing else is automatically doing that. – Erik Eidt Oct 05 '20 at 18:45
  • *We could treat ra like a caller saves register saving and restoring around a call* - That's not how you should ever use "caller-saves" registers in general (for reasons you explain), which is why that terminology is pretty terrible. I find ["call clobbered" vs. "call preserved" to be much clearer](https://stackoverflow.com/a/56178078/224132). (ping @KningTG). BTW, it's easy to see that `sp` is call-preserved: it must have the same value on exit as on entry, regardless of how you make that happen. – Peter Cordes Oct 06 '20 at 00:26
  • Also note that designing a calling convention that enforces the callee restoring the caller's `ra` doesn't actually help: the call itself made with `jal ra, malloc` means the caller is overwriting its own `ra` before the callee can do anything, so the callee only ever sees its return address (which makes sense of course, but isn't the value the caller *actually* wants to keep). You could save copy `ra` to a call-preserved reg (and back for performance), perhaps that's what you meant by "call preserved" instead of spill/reload. – Peter Cordes Oct 06 '20 at 00:37
  • IMO, as far as the calling convention is concerned, `ra` is a call-clobbered register used for passing a special "function arg" (good idea to describe it that way), which functions need to use at the end, after the function body. So in some ways it's just like any other function arg that needs to survive a function call. But the spill/reload instead of copying to a call-preserved reg is a special-case way of handling it which works better because return-address prediction hides latency, so saving instructions wins. – Peter Cordes Oct 06 '20 at 00:40
  • 1
    @Peter Cordes I kind of understand what you meant. So the only standard should be whether this register will be destroyed after the call, the use of "caller-saved" misleadingly implies that it's the caller's responsibility to store the register, which is not the case for some temporaries. `ra` is a special register which would be destroyed once we call another function, but it is still needed for later "jr ra". Therefore, the natural option is to store it before destroying it. – KningTG Oct 06 '20 at 04:30
  • @KningTG: Yes exactly, as I said in my linked answer it's normal to let function calls destroy registers. `ra` is only slightly special compared to other call-clobbered registers, especially ones use for passing function args. Basically just one way of solving a problem that can exist for other registers (when you need a function arg for something after some function call(s)). – Peter Cordes Oct 06 '20 at 04:35
  • And just like @Erik Eidt said, it's also acceptable to make `ra` callee-saved, which maintains `ra` after every single call, though this is not an efficient choice when we have multiple calls within the caller. Thank you both for deepening my understanding in this topic! – KningTG Oct 06 '20 at 04:57
  • I concur with @PeterCordes in that I also don't much care for the terms caller saved and callee saved. I like scratch vs. preferred, though call clobbered is probably even better than scratch. The preserved model is practical and often used. The caller saves registers are typically used for variables that simply are not live across a call and naming them caller saves suggests an extreme and bad model for how to save variables that are live across a call. – Erik Eidt Oct 06 '20 at 14:30
  • 1
    If have more variables live across a call than preserved registers, then a spill/reload that is custom to that variable is almost certainly better than the extreme caller saves model and better than another extreme model, memory variables, whose model says they are saved on change and reloaded on use. – Erik Eidt Oct 06 '20 at 14:32