Carnegie Mellon
Machine-Level Programming III: Procedures
15-213/18-213/14-513/15-513: Introduction to Computer Systems 7th Lecture, June 3rd 2020
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Carnegie Mellon
Objectives
Basic functionality of the pairs: push / pop and call / ret
Students should be able to identify the different components of a stack (return address, arguments, saved registers, local variables)
Explain the difference between callee and caller save registers
Explain how a stack permits functions to be called recursively /
re-entrant
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
2
Carnegie Mellon
Today
Procedures ▪ Mechanisms
▪ Stack Structure
▪ Calling Conventions
▪ Passing control
▪ Passing data
▪ Managing local data
▪ Illustration of Recursion
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
3
Carnegie Mellon
Mechanisms in Procedures
Passing control
▪ To beginning of procedure code ▪ Back to return point
Passing data
▪ Procedure arguments ▪ Return value
Memory management
▪ Allocate during procedure execution ▪ Deallocate upon return
Mechanisms all implemented with machine instructions
x86-64 implementation of a procedure uses only those mechanisms required
P(…) { •
•
y = Q(x);
print(y)
•
}
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
4
int Q(int i) {
int t = 3*i;
int v[10];
•
•
return v[t];
}
Carnegie Mellon
Mechanisms in Procedures
Passing control
▪ To beginning of procedure code ▪ Back to return point
Passing data
▪ Procedure arguments ▪ Return value
Memory management
▪ Allocate during procedure execution ▪ Deallocate upon return
Mechanisms all implemented with machine instructions
x86-64 implementation of a procedure uses only those mechanisms required
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
5
P(…) { •
•
y = Q(x);
print(y)
•
}
int Q(int i) {
int t = 3*i;
int v[10];
•
•
return v[t];
}
Carnegie Mellon
Mechanisms in Procedures
Passing control
▪ To beginning of procedure code ▪ Back to return point
Passing data
▪ Procedure arguments ▪ Return value
Memory management
▪ Allocate during procedure execution ▪ Deallocate upon return
Mechanisms all implemented with machine instructions
x86-64 implementation of a procedure uses only those mechanisms required
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
6
P(…) { •
•
y = Q(x);
print(y)
•
}
int Q(int i) {
int t = 3*i;
int v[10];
•
•
return v[t];
}
Carnegie Mellon
Mechanisms in Procedures
Passing control
▪ To beginning of procedure code ▪ Back to return point
Passing data
▪ Procedure arguments ▪ Return value
Memory management
▪ Allocate during procedure execution ▪ Deallocate upon return
Mechanisms all implemented with machine instructions
x86-64 implementation of a procedure uses only those mechanisms required
P(…) { •
•
y = Q(x);
print(y)
•
}
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
7
int Q(int i) {
int t = 3*i;
int v[10];
•
•
return v[t];
}
Carnegie Mellon
Mechanisms in Procedures
▪ Deallocate upon return
Mechanisms all implemented with
machine instructions
x86-64 implementation of a procedure uses only those mechanisms required
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
8
P(…) {
Passing control
Machine instructions implement the
▪ To beginning of procedure code ▪ Back to return point
• •
mechanisms, but the choices are
Passing data
determined by designers. These choices
▪ Procedure arguments
▪mReatukren vaulupe the Application Binary Interface
Memory management (ABI). ▪ Allocate during procedure execution
int Q(int i) {
int t = 3*i;
•
}
y = Q(x);
print(y)
int v[10];
•
•
return v[t];
}
Carnegie Mellon
Today
Procedures ▪ Mechanisms
▪ Stack Structure
▪ Calling Conventions
▪ Passing control
▪ Passing data
▪ Managing local data
▪ Illustration of Recursion
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
9
Carnegie Mellon
x86-64 Stack
Region of memory managed with stack discipline
▪ Memory viewed as array of bytes. ▪ Different regions have different
purposes.
▪ (Like ABI, a policy decision)
m e m o r y
Carnegie Mellon
stack
code
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
10
Carnegie Mellon
x86-64 Stack
Region of memory managed with stack discipline
Stack “Bottom”
Stack “Top”
Carnegie Mellon
stack
code
Stack Pointer: %rsp
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
11
Carnegie Mellon
x86-64 Stack
Region of memory managed with stack discipline
Grows toward lower addresses
Register %rsp contains lowest stack address
▪ address of “top” element
Stack Pointer: %rsp
Stack “Bottom”
Stack “Top”
Increasing Addresses
Stack Grows Down
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
12
Carnegie Mellon
x86-64 Stack: Push
pushq Src
▪ Fetch operand at Src
val
Stack “Bottom”
Stack “Top”
▪ Decrement %rsp by 8
▪ Write operand at address given by %rsp
Increasing Addresses
Stack Pointer: %rsp
Stack Grows Down
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
13
Carnegie Mellon
x86-64 Stack: Push
pushq Src
▪ Fetch operand at Src
Stack “Bottom”
▪ Decrement %rsp by 8
▪ Write operand at address given by %rsp
val
Increasing Addresses
Stack Pointer: %rsp
-8
Stack “Top”
Stack Grows Down
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
14
CaCranrnegeigeieMMeelllolonn
x86-64 Stack: Pop
popq Dest
▪ Read value at address given by %rsp
▪ Increment %rsp by 8
▪ Store value at Dest (usually a register)
Stack “Bottom”
Stack “Top”
Increasing Addresses
val
Stack Pointer: %rsp
Stack Grows Down
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
15
Carnegie Mellon
x86-64 Stack: Pop
popq Dest
▪ Read value at address given by %rsp
▪ Increment %rsp by 8
▪ Store value at Dest (usually a register)
val
Stack “Bottom”
+8
Stack “Top”
Increasing Addresses
Stack Pointer: %rsp
Stack Grows Down
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
16
Carnegie Mellon
x86-64 Stack: Pop
popq Dest
▪ Read value at address given by %rsp
▪ Increment %rsp by 8
▪ Store value at Dest (usually a register)
Stack “Bottom”
Stack “Top”
Increasing Addresses
val
Stack Pointer: %rsp
Stack Grows Down
(The memory doesn’t change, only the value of %rsp)
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
17
Carnegie Mellon
Today
Procedures ▪ Mechanisms
▪ Stack Structure
▪ Calling Conventions
▪ Passing control
▪ Passing data
▪ Managing local data
▪ Illustration of Recursion
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
18
Carnegie Mellon
Code Examples
void multstore(long x, long y, long *dest) {
long t = mult2(x, y);
*dest = t; }
long mult2(long a, long b)
{
long s = a * b;
return s; }
0000000000400540
400540: push 400541: mov 400544: callq 400549: mov 40054c: pop 40054d: retq
%rbx
%rdx,%rbx
400550
%rax,(%rbx)
%rbx
# Save %rbx
# Save dest
# mult2(x,y) # Save at dest # Restore %rbx # Return
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
19
0000000000400550
400550: mov 400553: imul 400557: retq
%rdi,%rax %rsi,%rax
# a
# a * b # Return
Carnegie Mellon
Procedure Control Flow
Use stack to support procedure call and return
Procedure call: call label ▪ Push return address on stack
▪ Jump to label
Return address:
▪ Address of the next instruction right after call ▪ Example from disassembly
Procedure return: ret ▪ Pop address from stack ▪ Jump to address
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
20
Carnegie Mellon
Control Flow Example #1
0x130 0x128 0x120
%rsp 0x120 %rip 0x400544
• • •
0000000000400540
•
400544: callq 400550
•
•
0000000000400550
400550: mov %rdi,%rax
•
•
400557: retq
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
21
Carnegie Mellon
• • •
0x400549
Control Flow Example #2
0x130 0x128 0x120 0x118
%rsp 0x118 %rip 0x400550
0000000000400540
•
400544: callq 400550
•
•
0000000000400550
400550: mov %rdi,%rax
•
•
400557: retq
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
22
Carnegie Mellon
• • •
0x400549
Control Flow Example #3
0x130 0x128 0x120 0x118
%rsp 0x118 %rip 0x400557
0000000000400540
•
400544: callq 400550
•
•
0000000000400550
400550: mov %rdi,%rax
•
•
400557: retq
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
23
Carnegie Mellon
Control Flow Example #4
0x130 0x128 0x120
%rsp 0x120 %rip 0x400549
• • •
0000000000400540
•
400544: callq 400550
•
•
0000000000400550
400550: mov %rdi,%rax
•
•
400557: retq
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
24
Carnegie Mellon
Today
Procedures ▪ Mechanisms
▪ tack Structure
▪ Calling Conventions
▪ Passing control
▪ Passing data
▪ Managing local data
▪ Illustrations of Recursion & Pointers
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
25
Carnegie Mellon
Procedure Data Flow Registers
First 6 arguments
Stack
•• •
Arg n
•• •
Arg 8
Arg 7
%rdi
%rsi
%rdx
%rcx
%r8
%r9
Return value %rax
Only allocate stack space when needed
Increasing Addresses
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
26
Carnegie Mellon
void multstore
(long x, long y, long *dest)
{
long t = mult2(x, y);
*dest = t;
}
Data Flow Examples
0000000000400540
# x in %rdi, y in %rsi, dest in %rdx
• ••
400541: mov %rdx,%rbx # Save dest 400544: callq 400550
400549: mov %rax,(%rbx) # Save at dest • ••
long mult2
(long a, long b)
{
long s = a * b;
return s;
}
0000000000400550
# a in %rdi, b in %rsi
400550: mov
400553: imul
# s in %rax
400557: retq
%rdi,%rax
%rsi,%rax
# a
# a * b
# Return
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
27
Carnegie Mellon
Today
Procedures ▪ Mechanisms
▪ Stack Structure
▪ Calling Conventions
▪ Passing control
▪ Passing data
▪ Managing local data
▪ Illustration of Recursion
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
28
Carnegie Mellon
Stack-Based Languages
Languages that support recursion ▪ e.g., C, Pascal, Java
▪ Code must be “Reentrant”
▪ Multiple simultaneous instantiations of single procedure ▪ Need some place to store state of each instantiation
▪ Arguments
▪ Local variables ▪ Return pointer
Stack discipline
▪ State for given procedure needed for limited time
▪ From when called to when return ▪ Callee returns before caller does
Stack allocated in Frames
▪ state for single procedure instantiation Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
29
Carnegie Mellon
Call Chain Example
Procedure amI() is recursive Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Example Call Chain
yoo(…) {
•
• who(); •
•
}
yoo
who
amI amI amI
amI
who(…) {
••• amI(); ••• amI(); •••
}
amI(…) {
•
• amI(); •
•
}
30
Carnegie Mellon
Previous Frame
Frame for
proc
Stack Frames
Contents
▪ Return information
▪ Local storage (if needed)
▪ Temporary space (if needed)
Frame Pointer: %rbp (Optional) x
Stack Pointer: %rsp
Management
▪ Space allocated when enter procedure
▪ “Set-up” code
▪ Includes push by call instruction ▪ Deallocated when return
▪ “Finish” code
▪ Includes pop by ret instruction
Stack “Top”
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
31
Carnegie Mellon
Example
Stack
yoo
yoo
who
amI amI amI
amI
%rbp %rsp
yoo(…) {
•
• who(); •
•
}
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
32
Carnegie Mellon
Example
Stack
yoo
who
yoo(…) {
yoo
who
amI amI amI
amI
%rbp %rsp
}
who(…) {
••• amI(); ••• amI(); •••
}
•
•
• •
who();
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
33
Carnegie Mellon
Example
Stack
yoo
who
amI
yoo(…) {
yoo
who
amI amI amI
amI
%rbp %rsp
}
who(…)
{ •
amI(…)
•••
• who();
•
•••
{
amI();
•
•••
}
}
•
•
amI();
amI(); •
•
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
34
Carnegie Mellon
Example
Stack
yoo
who
amI
amI
yoo(…) {
yoo
who
amI amI amI
amI
%rbp %rsp
}
who(…)
{ •
amI(…) •••
• who();
{ amI();
•
••• •{
•
•••
}
• amI(); ••
• amI(…)
amI();
• amI();
}• }
•
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
35
Carnegie Mellon
Example
Stack
yoo
who
amI
amI
amI
yoo(…) {
yoo
who
amI amI amI
amI
}
who(…)
{ •
• •
••• •{
amI(…) •••
• who();
{ amI();
• amI(…)
amI();
amI(…)
amI();
••• }••
•
•{
• }
amI(); ••
• amI();
}
}
•
•
%rbp %rsp
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
36
Carnegie Mellon
Example
Stack
yoo
who
amI
amI
yoo(…) {
yoo
who
amI amI amI
amI
%rbp %rsp
}
who(…)
{ •
•
••• •{
amI(…) •••
• who();
{ amI();
•
•••
}
• amI(); ••
• amI(…)
amI();
• amI();
}• }
•
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
37
Carnegie Mellon
Example
Stack
yoo
who
amI
yoo(…) {
yoo
who
amI amI amI
amI
%rbp %rsp
}
who(…)
{ •
•
• •••
amI(…) •••
• who();
{ amI();
• amI();
•
•••
}
}
amI(); •
•
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
38
Carnegie Mellon
Example
Stack
yoo
who
yoo(…) {
yoo
who
amI amI amI
amI
%rbp %rsp
}
who(…) {
•
• who();
• •
••• amI(); ••• amI(); •••
}
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
39
Carnegie Mellon
Example
Stack
yoo
who
amI
yoo(…) {
yoo
who
amI amI amI
amI
%rbp %rsp
}
who(…)
{ •
•
• •••
amI(…) •••
• who();
{ amI();
• amI();
•
•••
}
}
amI(); •
•
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
40
Carnegie Mellon
Example
Stack
yoo
who
yoo(…) {
yoo
who
amI amI amI
amI
%rbp %rsp
}
who(…) {
•
• who();
• •
••• amI(); ••• amI(); •••
}
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
41
Carnegie Mellon
Example
Stack
yoo
yoo
who
amI amI amI
amI
%rbp %rsp
yoo(…) {
•
• who(); •
•
}
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
42
Carnegie Mellon
x86-64/Linux Stack Frame
Current Stack Frame (“Top” to Bottom)
▪ “Argument build:”
Parameters for function about to call
▪ Local variables
If can’t keep in registers
▪ Saved register context
▪ Old frame pointer (optional)
Caller Stack Frame ▪ Return address
▪ Pushed by call instruction ▪ Arguments for this call
Arguments 7+
Return Addr
Old %rbp
Saved Registers + Local Variables
Argument Build (Optional)
Caller Frame
Frame pointer
%rbp
(Optional)
Stack pointer
%rsp
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
43
Carnegie Mellon
Register Saving Conventions
When procedure yoo calls who: ▪ yoo is the caller
▪ who is the callee
Can register be used for temporary storage?
▪ Contents of register %rdx overwritten by who
▪ This could be trouble ➙ something should be done!
▪ Need some coordination
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
44
yoo:
• ••
movq $15213, %rdx
call who
addq %rdx, %rax
• •• ret
who:
• ••
subq $18213, %rdx • ••
ret
Carnegie Mellon
Register Saving Conventions
When procedure yoo calls who: ▪ yoo is the caller
▪ who is the callee
Can register be used for temporary storage?
Conventions
▪ “Caller Saved”
▪ Caller saves temporary values in its frame before the call ▪ “Callee Saved”
▪ Callee saves temporary values in its frame before using ▪ Callee restores them before returning to caller
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
45
Carnegie Mellon
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
Return value
%rax
%rdi
%rsi
%rdx
%rcx
%r8
%r9
%r10
%r11
Caller-saved ▪ Can be modified by procedure temporaries
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
46
Arguments
Carnegie Mellon
x86-64 Linux Register Usage #2 %rbx, %r12, %r13, %r14,
%rbx
%r12
%r13
%r14
%r15
%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
%rbp
%rsp
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
47
Special
Carnegie Mellon
Activity
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
48
Carnegie Mellon
Today
Procedures ▪ Mechanisms
▪ Stack Structure
▪ Calling Conventions
▪ Passing control
▪ Passing data
▪ Managing local data
▪ Illustration of Recursion
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
49
Carnegie Mellon
Recursive Function
/* Recursive popcount */
long pcount_r(unsigned long x) {
if (x == 0)
return 0;
else
return (x & 1)
}
+ pcount_r(x >> 1);
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
50
pcount_r:
movl $0, %eax testq %rdi, %rdi je .L6
pushq %rbx
movq %rdi, %rbx andl $1, %ebx shrq %rdi
call pcount_r addq %rbx, %rax popq %rbx
.L6:
rep; ret
Carnegie Mellon
Recursive Function Terminal Case
pcount_r:
movl $0, %eax
testq %rdi, %rdi
je .L6
pushq %rbx
movq %rdi, %rbx andl $1, %ebx shrq %rdi
call pcount_r addq %rbx, %rax popq %rbx
.L6:
rep; ret
/* Recursive popcount */
long pcount_r(unsigned long x) {
if (x == 0)
return 0;
else
return (x & 1)
}
+ pcount_r(x >> 1);
Register
Use(s)
Type
%rdi
x
Argument
%rax
Return value
Return value
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
51
Carnegie Mellon
Recursive Function Register Save
pcount_r:
movl $0, %eax testq %rdi, %rdi je .L6
pushq %rbx
movq %rdi, %rbx andl $1, %ebx shrq %rdi
call pcount_r addq %rbx, %rax popq %rbx
.L6:
rep; ret
/* Recursive popcount */
long pcount_r(unsigned long x) {
if (x == 0)
return 0;
else
return (x & 1)
}
+ pcount_r(x >> 1);
Register
Use(s)
Type
%rdi
x
Argument
.. .
Rtn address
Saved %rbx
%rsp
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
52
Carnegie Mellon
Recursive Function Call Setup
pcount_r:
movl $0, %eax testq %rdi, %rdi je .L6
pushq %rbx
movq %rdi, %rbx andl $1, %ebx shrq %rdi
call pcount_r addq %rbx, %rax popq %rbx
.L6:
rep; ret
/* Recursive popcount */
long pcount_r(unsigned long x) {
if (x == 0)
return 0;
else
return (x & 1)
}
+ pcount_r(x >> 1);
Register
Use(s)
Type
%rdi
x >> 1
Recursive argument
%rbx
x &1
Callee-saved
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
53
Carnegie Mellon
Recursive Function Call
/* Recursive popcount */
long pcount_r(unsigned long x) {
if (x == 0)
return 0;
else
return (x & 1)
}
+ pcount_r(x >> 1);
pcount_r:
movl $0, %eax testq %rdi, %rdi je .L6
pushq %rbx
movq %rdi, %rbx andl $1, %ebx shrq %rdi
call pcount_r addq %rbx, %rax popq %rbx
.L6:
rep; ret
Register
Use(s)
Type
%rbx
x &1
Callee-saved
%rax
Recursive call return value
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
54
Carnegie Mellon
Recursive Function Result
/* Recursive popcount */
long pcount_r(unsigned long x) {
if (x == 0)
return 0;
else
return (x & 1)
}
+ pcount_r(x >> 1);
pcount_r:
movl $0, %eax testq %rdi, %rdi je .L6
pushq %rbx
movq %rdi, %rbx andl $1, %ebx shrq %rdi
call pcount_r addq %rbx, %rax popq %rbx
.L6:
rep; ret
Register
Use(s)
Type
%rbx
x &1
Callee-saved
%rax
Return value
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
55
Carnegie Mellon
Recursive Function Completion
pcount_r:
movl $0, %eax testq %rdi, %rdi je .L6
pushq %rbx
movq %rdi, %rbx andl $1, %ebx shrq %rdi
call pcount_r addq %rbx, %rax popq %rbx
/* Recursive popcount */
long pcount_r(unsigned long x) {
if (x == 0)
return 0;
else
return (x & 1)
}
+ pcount_r(x >> 1);
.L6:
rep; ret
Register
Use(s)
Type
%rax
Return value
Return value
.. .
%rsp
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
56
Carnegie Mellon
Observations About Recursion
Handled Without Special Consideration
▪ Stack frames mean that each function call has private storage
▪ Saved registers & local variables
▪ Saved return pointer
▪ Register saving conventions prevent one function call from corrupting
another’s data
▪ Unless the C code explicitly does so (e.g., buffer overflow in Lecture 9)
▪ Stack discipline follows call / return pattern ▪ If P calls Q, then Q returns before P
▪ Last-In, First-Out
Also works for mutual recursion ▪P calls Q; Q calls P
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
57
Carnegie Mellon
x86-64 Procedure Summary
Important Points
▪Stack is the right data structure for procedure call/return
Arguments 7+
Return Addr
Old %rbp
Saved Registers + Local Variables
Argument Build
▪ If P calls Q, then Q returns before P
Recursion (& mutual recursion) handled by normal calling conventions
▪Can safely store values in local stack frame and in callee-saved registers
▪Put function arguments at top of stack ▪Result return in%rax
Pointers are addresses of values ▪On stack or global
Caller Frame
%rbp
(Optional)
%rsp
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
58