程序代写代做代考 chain assembly C Java data structure Carnegie Mellon

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 400549: mov %rax,(%rbx)


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 400549: mov %rax,(%rbx)


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 400549: mov %rax,(%rbx)


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 400549: mov %rax,(%rbx)


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 # mult2(x,y) # t in %rax
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