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

Carnegie Mellon
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
14
–
513
18
–
613

Carnegie Mellon
Machine-Level Programming III: Procedures 15-213/18-213/14-513/15-513/18-613: Introduction to Computer Systems
7th Lecture, September 22, 2020
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition

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
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
4
Image: Arnold Reihnold & MIT Computer Museum

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
5
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
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
7
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
8
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
9
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
10

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
11

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
12

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
Carnegie Mellon
Stack Grows Down (toward lower addresses)
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
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
14

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
15

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
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)
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
17

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
18

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
19

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
20
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
21

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
22

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
23

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
24

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
25

Carnegie Mellon
Today
 Procedures ▪ Mechanisms
▪ Stack 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
26

Carnegie Mellon
Procedure Data Flow Registers
 First 6 integer arguments
Stack
•• •
Arg n
•• •
Arg 8
Arg 7
%rdi
%rsi
%rdx
%rcx
%r8
%r9
 Return value %rax
 Only allocate stack space when needed
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
27

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
28

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
29

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 address
 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
30

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(); •
•
}
31

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
▪ “Tear-down” code
▪ Includes pop by ret instruction
Stack “Top”
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
32

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
33

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
34

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
35

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
36

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
37

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
38

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
39

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
40

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
41

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
42

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
43

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
44

Carnegie Mellon
Example: incr
long incr(long *p, long val) {
long x = *p;
long y = x + val; *p = y;
return x;
}
incr:
movq (%rdi), %rax addq %rax, %rsi movq %rsi, (%rdi) ret
Register
Use(s)
%rdi
Argument p
%rsi
Argument val, y
%rax
x, Return value
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
45

Carnegie Mellon
Example: Calling incr #1
Initial Stack Structure
long call_incr() {
long v1 = 15213;
long v2 = incr(&v1, 3000);
return v1+v2;
}
.. .
Rtn address
%rsp
Resulting Stack Structure
call_incr:
subq $16, %rsp
movq $15213, 8(%rsp)
movl $3000, %esi
leaq 8(%rsp), %rdi
call incr
addq 8(%rsp), %rax
addq $16, %rsp
ret
.. .
Rtn address
15213
Unused
%rsp+8 %rsp
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
46

Carnegie Mellon
Example: Calling incr #2
Stack Structure
long call_incr() {
long v1 = 15213;
long v2 = incr(&v1, 3000);
return v1+v2;
}
.. .
Rtn address
15213
Unused
%rsp+8 %rsp
call_incr:
subq $16, %rsp
movq $15213, 8(%rsp) movl $3000, %esi leaq 8(%rsp), %rdi call incr
addq 8(%rsp), %rax addq $16, %rsp
ret
Register
Use(s)
%rdi
&v1
%rsi
3000
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
47

Carnegie Mellon
Example: Calling incr #2
long call_incr() {
long v1 = 15213;
long v2 = incr(&v1, 3000);
return v1+v2;
}
incr:
Aside 1: movl $3000, %esi Unused
%rsp
.. .
Stack Structure
Rtn address
15213 %rsp+8
• Note: movl -> %exx zeros out high order 32 bits. q $16, %rsp
call_ sub mov
movl $3000, %esi
leaq 8(%rsp), %rdi
call incr
addq 8(%rsp), %rax
addq $16, %rsp
ret
• Why use movl instead of movq? 1 byte shorter. q $15213, 8(%rsp) Register Use(s)
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
48
%rdi
%rsi
&v1
3000

Carnegie Mellon
Example: Calling incr #2
Stack Structure
long call_incr() {
long v1 = 15213;
long v2 = incr(&v1, 3000);
return v1+v2;
}
.. .
%rsp+8 %rsp
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
49
Rtn address
15213
Unused
call_incArs:ide 2: leaq 8(%rsp), %rdi subq $16, %rsp
• Computes %rsp+8 movq $15213, 8(%rsp)
Register
Use(s)
• Actually, used for what it is meant! movl $3000, %esi
%rdi &v1
leaq 8(%rsp), %rdi
call incr
addq 8(%rsp), %rax
addq $16, %rsp
ret
%rsi
3000

Carnegie Mellon
Example: Calling incr #2
Stack Structure
.. .
Rtn address
15213
Unused
long call_incr() {
long v1 = 15213;
long v2 = incr(&v1, 3000);
return v1+v2;
}
%rsp+8 %rsp
call_incr:
subq $16, %rsp
movq $15213, 8(%rsp) movl $3000, %esi leaq 8(%rsp), %rdi call incr
addq 8(%rsp), %rax addq $16, %rsp
ret
Register
Use(s)
%rdi
&v1
%rsi
3000
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
50

Carnegie Mellon
Example: Calling incr #3a
Stack Structure
.. .
Rtn address
15213
Unused
long call_incr() {
long v1 = 15213;
long v2 = incr(&v1, 3000);
return v1+v2;
}
%rsp+8 %rsp
call_incr:
subq $16, %rsp
movq $15213, 8(%rsp) movl $3000, %esi leaq 8(%rsp), %rdi call incr
addq 8(%rsp), %rax addq $16, %rsp
ret
Register
Use(s)
%rdi
&v1
%rsi
3000
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
51

Carnegie Mellon
Example: Calling incr #3b
Stack Structure
.. .
Rtn address
18213
Unused
long call_incr() {
long v1 = 15213;
long v2 = incr(&v1, 3000);
return v1+v2;
}
%rsp+8 %rsp
call_incr:
subq $16, %rsp
movq $15213, 8(%rsp) movl $3000, %esi leaq 8(%rsp), %rdi call incr
addq 8(%rsp), %rax addq $16, %rsp
ret
Register
Use(s)
%rdi
&v1
%rsi
3000
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
52

Carnegie Mellon
Example: Calling incr #4
Stack Structure
.. .
Rtn address
18213
Unused
long call_incr() {
long v1 = 15213;
long v2 = incr(&v1, 3000);
return v1+v2;
}
%rsp+8 %rsp
call_incr:
subq $16, %rsp
movq $15213, 8(%rsp) movl $3000, %esi leaq 8(%rsp), %rdi call incr
addq 8(%rsp), %rax addq $16, %rsp
ret
Register
Use(s)
%rax
Return value, 15213
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
53

Carnegie Mellon
Example: Calling incr #5a
Stack Structure
.. .
Rtn address
18213
Unused
long call_incr() {
long v1 = 15213;
long v2 = incr(&v1, 3000);
return v1+v2; }
%rsp+8 %rsp
call_incr:
subq $16, %rsp
movq $15213, 8(%rsp) movl $3000, %esi leaq 8(%rsp), %rdi call incr
addq 8(%rsp), %rax addq $16, %rsp
ret
Register
Use(s)
%rax
Return value
Updated Stack Structure
.. .
Rtn address
%rsp
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
54

Carnegie Mellon
Example: Calling incr #5b
Updated Stack Structure
long call_incr() {
long v1 = 15213;
long v2 = incr(&v1, 3000);
return v1+v2;
}
.. .
Rtn address
%rsp
call_incr:
subq $16, %rsp
movq $15213, 8(%rsp) movl $3000, %esi leaq 8(%rsp), %rdi call incr
addq 8(%rsp), %rax addq $16, %rsp
ret
Register
Use(s)
%rax
Return value
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
55
.. .
Final Stack Structure
%rsp

Carnegie Mellon
Register Saving Conventions
 When procedure yoo calls who: ▪ yoo is the caller
▪ who is the callee
 Can a register be used for temporary storage?
▪ Contents of register %rdx overwritten by who ▪ If a callee clobbers your register, its value is lost!
▪ Need coordination between caller/callee Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
56
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 must save values in its stack frame before call ▪ “Callee Saved”
▪ Callee saves values in its frame before using ▪ Callee restores values before returning
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
57

Carnegie Mellon
x86-64 Linux Register Usage #1
 %rax
▪ Return value
▪ Also caller-saved
▪ Can be modified by procedure
 %rdi, …, %r9
▪ Integer arguments
▪ Also caller-saved
▪ Can be modified by procedure
 %r10, %r11 ▪ Caller-saved
▪ Can be modified by procedure
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Caller-saved Return value
%rax
%rdi
%rsi
%rdx
%rcx
%r8
%r9
%r10
%r11
Caller-saved Arguments
Caller-saved Temporaries
58

Carnegie Mellon
x86-64 Linux Register Usage #2  %rbx, %r12, %r13, %r14
%rbx
%r12
%r13
%r14
%rbp
%rsp
▪ Callee-saved
▪ Callee must save & restore
 %rbp
▪ Callee-saved
▪ Callee must save & restore
▪ May be used as frame pointer ▪ Compiler decides use of rbp
 %rsp
▪ Special form of callee save
▪ Restored to original value upon exit from procedure
Callee-saved Temporaries
Special
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
59

Carnegie Mellon
Quiz Time!
Check out:
https://canvas.cmu.edu/courses/17808
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
60

Carnegie Mellon
Callee-Saved Example #1
Initial Stack Structure
long call_incr2(long x) {
long v1 = 15213;
long v2 = incr(&v1, 3000);
return x+v2;
}
.. .
Rtn address
%rsp
• xcomesinregister%rdi.
• We need %rdi for the call to incr.
• Where should be put x, so we can use
it after the call to incr? Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
61

Carnegie Mellon
Callee-Saved Example #2
Initial Stack Structure
long call_incr2(long x) {
long v1 = 15213;
long v2 = incr(&v1, 3000);
return x+v2;
}
.. .
Rtn address
%rsp
Resulting Stack Structure
call_incr2:
pushq %rbx
subq $16, %rsp
movq %rdi, %rbx
movq $15213, 8(%rsp) movl $3000, %esi leaq 8(%rsp), %rdi call incr
addq %rbx, %rax
addq $16, %rsp
popq %rbx
ret
.. .
Rtn address
Saved %rbx
%rsp
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
62

Carnegie Mellon
Callee-Saved Example #3
Initial Stack Structure
long call_incr2(long x) {
long v1 = 15213;
long v2 = incr(&v1, 3000);
return x+v2;
}
.. .
Rtn address
Saved %rbx
%rsp
Resulting Stack Structure
call_incr2:
pushq %rbx
subq $16, %rsp
movq %rdi, %rbx
movq $15213, 8(%rsp) movl $3000, %esi leaq 8(%rsp), %rdi call incr
addq %rbx, %rax
addq $16, %rsp
popq %rbx
ret
.. .
Rtn address
Saved %rbx
%rsp+8 %rsp
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
63

Carnegie Mellon
Callee-Saved Example #4
Stack Structure
.. .
Rtn address
Saved %rbx
long call_incr2(long x) {
long v1 = 15213;
long v2 = incr(&v1, 3000);
return x+v2;
}
%rsp+8 %rsp
call_incr2:
pushq %rbx
subq $16, %rsp
movq %rdi, %rbx
movq $15213, 8(%rsp) movl $3000, %esi leaq 8(%rsp), %rdi call incr
addq %rbx, %rax
addq $16, %rsp
popq %rbx
ret
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
64
• x is saved in %rbx,
a callee saved register

Carnegie Mellon
Callee-Saved Example #5
Stack Structure
.. .
Rtn address
Saved %rbx
15213
Unused
long call_incr2(long x) {
long v1 = 15213;
long v2 = incr(&v1, 3000);
return x+v2;
}
%rsp+8 %rsp
call_incr2:
pushq %rbx
subq $16, %rsp
movq %rdi, %rbx
movq $15213, 8(%rsp) movl $3000, %esi leaq 8(%rsp), %rdi call incr
addq %rbx, %rax
addq $16, %rsp
popq %rbx
ret
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
65
• x is saved in %rbx,
a callee saved register

Carnegie Mellon
Callee-Saved Example #6
Stack Structure
.. .
Rtn address
Saved %rbx
18213
Unused
long call_incr2(long x) {
long v1 = 15213;
long v2 = incr(&v1, 3000);
return x+v2;
}
%rsp+8 %rsp
Upon return from incr:
• x safe in %rbx
• Return val v2 in %rax
• Compute x+v2:
addq %rbx, %rax
call_incr2:
pushq %rbx
subq $16, %rsp
movq %rdi, %rbx
movq $15213, 8(%rsp) movl $3000, %esi leaq 8(%rsp), %rdi call incr
addq %rbx, %rax
addq $16, %rsp
popq %rbx
ret
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
66

Carnegie Mellon
Callee-Saved Example #7
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Stack Structure
.. .
Rtn address
Saved %rbx
18213
Unused
long call_incr2(long x) {
long v1 = 15213;
long v2 = incr(&v1, 3000);
return x+v2;
}
%rsp
call_incr2:
pushq %rbx
subq $16, %rsp
movq %rdi, %rbx
movq $15213, 8(%rsp) movl $3000, %esi leaq 8(%rsp), %rdi call incr
addq %rbx, %rax
addq $16, %rsp
popq %rbx
ret
• Return result in %rax 67

Callee-Saved Example #8
Initial Stack Structure
Carnegie Mellon
.. .
Rtn address
Saved %rbx
18213
Unused
long call_incr2(long x) {
long v1 = 15213;
long v2 = incr(&v1, 3000);
return x+v2;
}
%rsp
final Stack Structure
call_incr2:
pushq %rbx
subq $16, %rsp
movq %rdi, %rbx
movq $15213, 8(%rsp) movl $3000, %esi leaq 8(%rsp), %rdi call incr
addq %rbx, %rax
addq $16, %rsp
popq %rbx
ret
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
68
.. .
Rtn address
Saved %rbx
18213
Unused
%rsp

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
70

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
71
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
72

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
73

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
74

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
75

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
76

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
77

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
78

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 7+ 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
79

Carnegie Mellon
Small Exercise
long add5(long b0, long b1, long b2, long b3, long b4) { return b0+b1+b2+b3+b4;
}
long add10(long a0, long a1, long a2, long a3, long a4, long a5, long a6, long a7, long a8, long a9) {
return add5(a0, a1, a2, a3, a4)+
}
add5(a5, a6, a7, a8, a9);
 Where are a0,…, a9 passed?
rdi, rsi, rdx, rcx, r8, r9, stack
 Where are b0,…, b4 passed? rdi, rsi, rdx, rcx, r8
 Which registers do we need to save? Ill-posed question. Need assembly.
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
80