Carnegie Mellon Machine-Level Programming III: IA32 Procedures and Stack Structure Lecture Overview

Carnegie Mellon Machine-Level Programming III: IA32 Procedures 15-213: Introduction to Computer Systems 6th Lecture, Sep. 9, 2010 Instructors: Randy Bryant and Dave O Hallaron

Carnegie Mellon Today Switch statements IA 32 Procedures Stack Structure Calling Conventions Illustrations of Recursion & Pointers 20

Carnegie Mellon IA32 Stack Stack Bottom Region of memory managed with stack discipline Increasing Addresses Grows toward lower addresses Register %esp contains lowest stack address address of top element Stack Grows Down Stack Pointer: %esp Stack Top 21

Carnegie Mellon IA32 Stack: Push Stack Bottom pushl Src Fetch operand at Src Decrement %esp by 4 Write operand at address given by %esp Src Increasing Addresses Stack Grows Down Stack Pointer: %esp -4 Stack Top 22

Carnegie Mellon IA32 Stack: Pop Stack Bottom Increasing Addresses Stack Grows Down +4 Stack Pointer: %esp Stack Top 23

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 804854e: e8 3d 06 00 00 8048553: 50 Return address = 0x8048553 call 8048b90 <main> pushl %eax Procedure return: ret Pop address from stack Jump to address 24

Carnegie Mellon Procedure Call Example 804854e: 8048553: e8 3d 06 00 00 50 call 8048b90 <main> pushl %eax call 8048b90 0x110 0x110 0x10c 0x10c 0x108 123 0x108 123 0x104 0x8048553 %esp 0x108 %esp 0x104 %eip 0x804854e %eip 0x8048b90 %eip: program counter 25

Carnegie Mellon Procedure Return Example 8048591: c3 ret ret 0x110 0x110 0x10c 0x10c 0x108 123 0x108 123 0x104 0x8048553 0x8048553 %esp 0x104 %esp 0x108 %eip 0x8048591 %eip 0x8048553 %eip: program counter 26

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 Frames 27

Carnegie Mellon Call Chain Example Example Call Chain yoo( ) { who(); } yoo who( ) { amI(); amI(); } who amI amI amI( ) { amI(); } amI amI Procedure amI() is recursive 28

Carnegie Mellon Stack Frames Previous Frame Contents Local variables Return information Temporary space Frame Pointer: %ebp Frame for proc Stack Pointer: %esp Management Space allocated when enter procedure Stack Top Set-up code Deallocated when return Finish code 29

Carnegie Mellon Stack Example yoo yoo( ) { who(); } %ebp yoo yoo who %esp amI amI amI amI 30

Carnegie Mellon Stack Example yoo yoo( ) { who(); } } who( ) { amI(); amI(); yoo yoo who %ebp who amI amI %esp amI amI 31

Carnegie Mellon Stack Example yoo yoo( ) { who(); } } } who( ) { amI(); amI(); amI(); yoo yoo amI( ) { who who amI amI %ebp amI amI %esp amI 32

Carnegie Mellon Stack Example yoo yoo( ) { who(); } } } who( ) { amI(); amI(); amI(); yoo yoo amI( ) { who amI( ) { amI(); } who amI amI amI amI %ebp amI amI %esp 33

Carnegie Mellon Stack Example yoo yoo( ) { who(); } } } who( ) { amI(); amI(); amI(); yoo yoo amI( ) { who amI( ) { amI(); } } who amI amI amI( ) { amI(); amI amI amI amI %ebp amI %esp 34

Carnegie Mellon Stack Example yoo yoo( ) { who(); } } } who( ) { amI(); amI(); amI(); yoo yoo amI( ) { who amI( ) { amI(); } who amI amI amI amI %ebp amI amI %esp 35

Carnegie Mellon Stack Example yoo yoo( ) { who(); } } } who( ) { amI(); amI(); amI(); yoo yoo amI( ) { who who amI amI %ebp amI amI %esp amI 36

Carnegie Mellon Stack Example yoo yoo( ) { who(); } } who( ) { amI(); amI(); yoo yoo who %ebp who amI amI %esp amI amI 37

Carnegie Mellon Stack Example yoo yoo( ) { who(); } } } who( ) { amI(); amI(); amI(); yoo yoo amI( ) { who who amI amI %ebp amI amI %esp amI 38

Carnegie Mellon Stack Example yoo yoo( ) { who(); } } who( ) { amI(); amI(); yoo yoo who %ebp who amI amI %esp amI amI 39

Carnegie Mellon Stack Example yoo %ebp yoo( ) { who(); } yoo yoo who %esp amI amI amI amI 40

Carnegie Mellon IA32/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 Caller Frame Arguments Return Addr Old %ebp Frame pointer %ebp Saved Registers + Local Variables Caller Stack Frame Return address Pushed by call instruction Arguments for this call Argument Build Stack pointer %esp 41

Carnegie Mellon Revisiting swap Calling swap from call_swap int course1 = 15213; int course2 = 18243; call_swap: subl movl movl call $8, %esp $course2, 4(%esp) $course1, (%esp) swap void call_swap() { swap(&course1, &course2); } Resulting Stack void swap(int *xp, int *yp) { int t0 = *xp; int t1 = *yp; *xp = t1; *yp = t0; } %esp &course 2 &course 1 Rtn adr subl %esp call %esp 42

Carnegie Mellon Revisiting swap swap: pushl %ebp movl %esp, %ebp pushl %ebx Set Up void swap(int *xp, int *yp) { int t0 = *xp; int t1 = *yp; *xp = t1; *yp = t0; } movl 8(%ebp), %edx movl 12(%ebp), %ecx movl (%edx), %ebx movl (%ecx), %eax movl %eax, (%edx) movl %ebx, (%ecx) Body popl %ebx popl %ebp ret Finish 43

Carnegie Mellon swap Setup #1 Entering Stack Resulting Stack %ebp %ebp &course2 yp &course1 xp %esp Rtn adr Rtn adr Old %ebp %esp swap: pushl %ebp movl %esp,%ebp pushl %ebx 44

Carnegie Mellon swap Setup #2 Entering Stack Resulting Stack %ebp &course2 yp &course1 xp %esp Rtn adr Rtn adr %ebp %esp Old %ebp swap: pushl %ebp movl %esp,%ebp pushl %ebx 45

Carnegie Mellon swap Setup #3 Entering Stack Resulting Stack %ebp &course2 yp &course1 xp %esp Rtn adr Rtn adr Old %ebp %ebp Old %ebx %esp swap: pushl %ebp movl %esp,%ebp pushl %ebx 46

Carnegie Mellon swap Body Entering Stack Resulting Stack %ebp Offset relative to %ebp 12 &course2 yp 8 &course1 xp %esp 4 Rtn adr Rtn adr Old %ebp %ebp Old %ebx %esp movl 8(%ebp),%edx # get xp movl 12(%ebp),%ecx # get yp . . . 47

Carnegie Mellon swap Finish Stack Before Finish Resulting Stack %ebp popl popl %ebx %ebp yp yp xp xp %esp Rtn adr Rtn adr %ebp %esp Old %ebp Old %ebx Observation Saved and restored register %ebx Not so for %eax, %ecx, %edx 48

Carnegie Mellon Disassembled swap 08048384 <swap>: 8048384: 55 8048385: 89 e5 8048387: 53 8048388: 8b 55 08 804838b: 8b 4d 0c 804838e: 8b 1a 8048390: 8b 01 8048392: 89 02 8048394: 89 19 8048396: 5b 8048397: 5d 8048398: c3 Calling Code push %ebp mov %esp,%ebp push %ebx mov 0x8(%ebp),%edx mov 0xc(%ebp),%ecx mov (%edx),%ebx mov (%ecx),%eax mov %eax,(%edx) mov %ebx,(%ecx) pop %ebx pop %ebp ret 80483b4: movl $0x8049658,0x4(%esp) # Copy &course2 80483bc: movl $0x8049654,(%esp) 80483c3: call 8048384 <swap> 80483c8: leave 80483c9: ret # Copy &course1 # Call swap # Prepare to return # Return 49

Carnegie Mellon Today Switch statements IA 32 Procedures Stack Structure Calling Conventions Illustrations of Recursion & Pointers 50

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? yoo: movl $15213, %edx call who addl %edx, %eax ret who: movl 8(%ebp), %edx addl $18243, %edx ret Contents of register %edx overwritten by who This could be trouble something should be done! Need some coordination 51

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 Save Caller saves temporary values in its frame before the call Callee Save Callee saves temporary values in its frame before using 52

Carnegie Mellon IA32/Linux+Windows Register Usage %eax, %edx, %ecx Caller saves prior to call if values are used later %eax %edx %ecx %ebx %esi %edi %esp %ebp Caller-Save Temporaries %eax also used to return integer value Callee-Save Temporaries %ebx, %esi, %edi Callee saves if wants to use them Special %esp, %ebp special form of callee save Restored to original values upon exit from procedure 53

Carnegie Mellon Today Switch statements IA 32 Procedures Stack Structure Calling Conventions Illustrations of Recursion & Pointers 54

Carnegie Mellon Recursive Function pcount_r: pushl %ebp movl %esp, %ebp pushl %ebx subl $4, %esp movl 8(%ebp), %ebx movl $0, %eax testl %ebx, %ebx je .L3 movl %ebx, %eax shrl %eax movl %eax, (%esp) call pcount_r movl %ebx, %edx andl $1, %edx leal (%edx,%eax), %eax .L3: addl $4, %esp popl %ebx popl %ebp ret /* Recursive popcount */ int pcount_r(unsigned x) { if (x == 0) return 0; else return (x & 1) + pcount_r(x >> 1); } Registers %eax, %edx used without first saving %ebx used, but saved at beginning & restored at end 55

Carnegie Mellon pcount_r: pushl %ebp movl %esp, %ebp pushl %ebx subl $4, %esp movl 8(%ebp), %ebx Recursive Call #1 /* Recursive popcount */ int pcount_r(unsigned x) { if (x == 0) return 0; else return (x & 1) + pcount_r(x >> 1); } Actions Save old value of %ebx on stack Allocate space for argument to recursive call Store x in %ebx x Rtn adr %ebp Old %ebp Old %ebx %ebx %esp x 56

Carnegie Mellon Recursive Call #2 movl $0, %eax testl %ebx, %ebx je .L3 .L3: ret /* Recursive popcount */ int pcount_r(unsigned x) { if (x == 0) return 0; else return (x & 1) + pcount_r(x >> 1); } Actions If x == 0, return with %eax set to 0 %ebx x 57

Carnegie Mellon Recursive Call #3 movl %ebx, %eax shrl %eax movl %eax, (%esp) call pcount_r /* Recursive popcount */ int pcount_r(unsigned x) { if (x == 0) return 0; else return (x & 1) + pcount_r(x >> 1); } Actions Store x >> 1 on stack Make recursive call Rtn adr Effect %eax set to function result %ebx still has value of x %ebp Old %ebp Old %ebx %esp x >> 1 %ebx x 58

Carnegie Mellon Recursive Call #4 /* Recursive popcount */ int pcount_r(unsigned x) { if (x == 0) return 0; else return (x & 1) + pcount_r(x >> 1); } movl %ebx, %edx andl $1, %edx leal (%edx,%eax), %eax Assume %eaxholds value from recursive call %ebxholds x %ebx x Actions Compute (x & 1) + computed value Effect %eax set to function result 59

Carnegie Mellon Recursive Call #5 /* Recursive popcount */ int pcount_r(unsigned x) { if (x == 0) return 0; else return (x & 1) + pcount_r(x >> 1); } L3: addl $4, %esp popl %ebx popl %ebp ret %ebp Actions Restore values of %ebx and %ebp Restore %esp %esp Rtn adr %ebp Old %ebp %ebx Old %ebx Old %ebx %esp 60

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 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 61

Carnegie Mellon Pointer Code Generating Pointer /* Compute x + 3 */ int add3(int x) { int localx = x; incrk(&localx, 3); return localx; } Referencing Pointer /* Increment value by k */ void incrk(int *ip, int k) { *ip += k; } add3 creates pointer and passes it to incrk 62

Carnegie Mellon Creating and Initializing Local Variable Variable localx must be stored on stack Because: Need to create pointer to it int add3(int x) { int localx = x; incrk(&localx, 3); return localx; } Compute pointer as -4(%ebp) 8 x 4 Rtn adr 0 %ebp Old %ebp localx = x First part of add3 add3: pushl %ebp movl %esp, %ebp subl $24, %esp movl 8(%ebp), %eax movl %eax, -4(%ebp) # Set localx to x -4 -8 -12 Unused # Alloc. 24 bytes -16 -20 -24 %esp 63

Carnegie Mellon Creating Pointer as Argument Use leal instruction to compute address of localx int add3(int x) { int localx = x; incrk(&localx, 3); return localx; } 8 x 4 Rtn adr 0 %ebp Old %ebp Middle part of add3 movl $3, 4(%esp) # 2nd arg = 3 leal -4(%ebp), %eax # &localx movl %eax, (%esp) # 1st arg = &localx call incrk -4 localx -8 -12 Unused -16 -20 -24 %esp+4 3 %esp 64

Carnegie Mellon Retrieving local variable Retrieve localx from stack as return value int add3(int x) { int localx = x; incrk(&localx, 3); return localx; } 8 x 4 Rtn adr 0 %ebp Old %ebp Final part of add3 movl -4(%ebp), %eax # Return val= localx leave ret -4 localx -8 -12 Unused -16 -20 -24 %esp 65

Carnegie Mellon IA 32 Procedure Summary Important Points Stack is the right data structure for procedure call / return Caller Frame If P calls Q, then Q returns before P Arguments 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 %eax Return Addr Old %ebp %ebp Saved Registers + Local Variables Pointers are addresses of values On stack or global Argument Build %esp 66