CS 461
Subroutines and Control Abstraction Stack and Calling Sequences
Yanling Wang
Computer Science and Engineering Penn State University
Carnegie Mellon
1
Terminology
Function (Fortran, Ada): returns a value
Procedure (Ada), Subroutine (Fortran): returns no value C-like language: both are called function
Method (C++, Java): a function declared inside a class
Carnegie Mellon
2
3
Carnegie Mellon
Caller & Callee
When function A calls function B
• A is the Caller
• B is the Callee
What needs to be done? Who is responsible?
3
Stack-Based Allocation
Carnegie Mellon
4
5
Carnegie Mellon
Stack Frame (Activation Record)
A stack frame contains:
• Local variables
• Temporaries
• Arguments, return values
• Bookkeeping info
When is it created? By whom? When is it destroyed? By whom?
arguments
temporaries
locals
misc bookkeeping
return addr
5
Registers
Carnegie Mellon
6
Registers
How can registers be used?
When should they be used? Who saves registers?
Carnegie Mellon
7
Saving & Restoring Registers
Registers are shared, caller & callee need to save and restore registers
Ideally: save exactly registers used in caller & callee In practice, registers fall into two categories:
¢ Caller-saves
§ For transient values not likely needed across calls.
¢ Callee-saves
§ For local variables and other long-lived values.
Carnegie Mellon
8
Caller Save vs. Callee Save
Caller saves all caller-saves registers before call Callee saves all callee-saves registers before run Callee restores all callee-saves registers before exit Caller restores all caller-saves registers before resume
Separation of responsibility:
1. Caller assumes callee will not destroy callee-saves
2. Callee assumes nothing is valuable in caller-saves
Carnegie Mellon
9
x86-64 Integer Registers
Carnegie Mellon
%rax
%eax
%rbx
%ebx
%rcx
%ecx
%rdx
%edx
%rsi
%esi
%rdi
%edi
%rsp
%esp
%rbp
%ebp
%r8
%r8d
%r9
%r9d
%r10
%r10d
%r11
%r11d
%r12
%r12d
%r13
%r13d
%r14
%r14d
%r15
%r15d
§ Can reference low-order 4 bytes (also low-order 1 & 2 bytes)
10
x86-64 Linux Register Usage #1
¢ %rax
§ Return value
§ Also caller-saved
§ Can be modified by procedure
¢ %rdi, …, %r9 § Arguments
§ Also caller-saved
§ Can be modified by procedure
¢ %r10,%r11
§ Caller-saved
§ Can be modified by procedure temporaries
Return value
CCaarrnegiie Mellloonn
%rax
%rdi
%rsi
%rdx
%rcx
%r8
%r9
%r10
%r11
Arguments
Caller-saved
11
x86-64 Linux Register Usage #2
CCaarrnegiie Mellloonn
%rbx
%r12
%r13
%r14
%r15
%rbp
%rsp
¢ %rbx,%r12,%r13, %r14,%r15
§ Callee-saved
§ Callee must save & restore
¢ %rbp
§ Callee-saved
§ Callee must save & restore
§ May be used as frame pointer § Can mix & match
¢ %rsp
§ Special form of callee save
§ Restored to original value upon exit from procedure
Callee-saved Temporaries
Special
12
A Typical Calling Sequence
1. The Caller A: prep before calling B
2. The Callee B: prologue before running B
3. The Callee B: epilogue after completing B before returning to A
4. The Caller A: clean up after calls to B
Compiled with clang to x86
Carnegie Mellon
Sample code:
int g(int x) {
return 2 * x; }
int f(int x) {
return 3 + g(x + 4);
}
13
A Typical Calling Sequence 1 ¢ The Caller:
§ Save any caller-saved registers that may be needed after the call
§ Compute the values of arguments and moves them into the stack or registers
§ Computes the static link (if the language has nested subroutines), and passes it as an extra, hidden argument
§ Use a special subroutine call instruction to jump to the subroutine, simultaneously passing the return address on the stack or in a register.
Carnegie Mellon
int f(int x) {
return 3 + g(x+4);
}
f: pushq %rbp
movq %rsp, %rbp
subq $16, %rsp
movl %edi, -4(%rbp)
movl -4(%rbp), %edi
addl $4, %edi
callq g
addl $3, %eax
addq $16, %rsp
popq %rbp
retq
14
A Typical Calling Sequence 2 ¢ Prologue in Callee
§ allocates a frame by subtracting an appropriate constant from the sp
§ saves the old frame pointer into the stack, and updates it to point to the newly allocated frame
§ saves any callee-saved register that may be overwritten by the current routine
Carnegie Mellon
int g(int x) {
return 2 * x;
}
g: pushq %rbp
movq %rsp, %rbp
movl %edi, -4(%rbp)
movl -4(%rbp), %edi
shll $1, %edi
movl %edi, %eax
popq %rbp
retq
15
A Typical Calling Sequence 3 ¢ Epilogue in Callee
§ moves the return value into a register or a reserved location in the stack
§ restores callee-saves registers if needed
§ restores the fp and the sp
§ jumps back to the return address
Carnegie Mellon
int g(int x) {
return 2 * x;
}
g: pushq %rbp
movq %rsp, %rbp
movl %edi, -4(%rbp)
movl -4(%rbp), %edi
shll $1, %edi
movl %edi, %eax
popq %rbp
retq
16
A Typical Calling Sequence 4 ¢ The Caller:
§ moves the return value to wherever it is needed
§ restores caller-saves registers if needed.
Carnegie Mellon
int f(int x) {
return 3 + g(x+4);
}
f: pushq %rbp
movq %rsp, %rbp
subq $16, %rsp
movl %edi, -4(%rbp)
movl -4(%rbp), %edi
addl $4, %edi
callq g
addl $3, %eax
addq $16, %rsp
popq %rbp
retq
17
Function Calls are costly ¢ Time
§ Need special calling sequences/instructions ¢ Space
§ Each active function needs space on the stack (stack frame/activation record)
¢ Design of calling conventions
§ To reduce the function call cost for simple functions.
§ Use registers for saving values, only use stack when necessary
¢ In-lining the code
§ Expand the callee to be part of caller’s code. Avoid call over heads § Disadvantage– increasing the code size
Carnegie Mellon
18
Next lecture – Parameter Passing
¢ Parameters vs. Arguments
§ Most subroutines are parameterized
§ Parameter names in function declaration – Formal Parameters
§ Variables and expressions that are passed to a subroutine in a call – Actual Parameters/ Arguments
¢ Parameter-Passing modes § Call by values
§ Call by references § Call by sharing
Carnegie Mellon
19