Recursion in Carnegie Mellon Programming
Learn about recursive functions in Carnegie Mellon programming, including an example of calculating factorial recursively. Explore the observations on recursion handling and register saving conventions in the context of stack frames. Discover the nuances of register usage in x86-64 Linux programming at Carnegie Mellon.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Carnegie Mellon Recursive Functions rfact: pushq %rbp # enter movq %rsp, %rbp # enter subq $16, %rsp # enter moveq $1, %rax # return 1 cmpq $1, %rdi # x - 1 ? jg .L2 # if x>1 jmp .L1 # if x<=1 .L2: # else movq %rdi, -8(%rbp) # save x subq $1, %rdi # rdi = x-1 call rfact # rfact(x-1) # rax = rfact(x-1); rdi = ??? imulq -8(%rbp), %rax # rax=rax*x .L1: leave ret /* Recursive factorial */ long rfact(long x){ if (x<=1) return 1; else return x*rfact(x-1); } C x x86 %rdi %rax return val 1 Bryant and O Hallaron, Computer Systems: A Programmer s Perspective, Third Edition
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 2 Bryant and O Hallaron, Computer Systems: A Programmer s Perspective, Third Edition
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: movq $15213, %rdx call who addq %rdx, %rax ret who: ret subq $18213, %rdx Contents of register %rdx overwritten by who This could be trouble something should be done! Need some coordination 3 Bryant and O Hallaron, Computer Systems: A Programmer s Perspective, Third Edition
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 4 Bryant and O Hallaron, Computer Systems: A Programmer s Perspective, Third Edition
Carnegie Mellon x86-64 Linux Register Usage #1 %rax Return value Also caller-saved Can be modified by procedure %rax %rdi %rsi Return value %rdx %rcx %r8 %r9 %r10 %r11 %rdi, ..., %r9 Arguments Also caller-saved Can be modified by procedure Arguments %r10, %r11 Caller-saved Can be modified by procedure Caller-saved temporaries 5 Bryant and O Hallaron, Computer Systems: A Programmer s Perspective, Third Edition
Carnegie Mellon x86-64 Linux Register Usage #2 %rbx %r12 %r13 %r14 %rbx, %r12, %r13, %r14 Callee-saved Callee must save & restore Callee-saved Temporaries %rbp Callee-saved Callee must save & restore May be used as frame pointer Can mix & match %rbp Special %rsp %rsp Special form of callee save Restored to original value upon exit from procedure 6 Bryant and O Hallaron, Computer Systems: A Programmer s Perspective, Third Edition
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 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 Resulting Stack Structure . . . Rtn address Saved %rbx %rsp+8 15213 %rsp Unused 7 Bryant and O Hallaron, Computer Systems: A Programmer s Perspective, Third Edition
Carnegie Mellon Callee-Saved Example #2 Resulting Stack Structure long call_incr2(long x) { long v1 = 15213; long v2 = incr(&v1, 3000); return x+v2; } . . . Rtn address Saved %rbx %rsp+8 15213 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 %rsp Unused Pre-return Stack Structure . . . Rtn address %rsp 8 Bryant and O Hallaron, Computer Systems: A Programmer s Perspective, Third Edition
Carnegie Mellon x86-64 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 7+ 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 Return Addr Old %rbp %rbp (Optional) Saved Registers + Local Variables Pointers are addresses of values On stack or global Argument Build %rsp 9 Bryant and O Hallaron, Computer Systems: A Programmer s Perspective, Third Edition
