Carnegie MellonIntroduction to Computer Systems15-213/18-243, spring 20098thLecture, Feb. 5thInstructors:Gregory Kesden and Markus PüschelCarnegie MellonLast Time For loops for loop → while loop → do-while loop → goto version for loop → while loop → goto “jump to middle” version Switch statements Jump tables: jmp *.L62(,%edx,4) Decision trees (not shown)Jump table.section .rodata.align 4.L62:.long .L61 # x = 0.long .L56 # x = 1.long .L57 # x = 2.long .L58 # x = 3.long .L61 # x = 4.long .L60 # x = 5.long .L60 # x = 6Carnegie MellonLast Time Procedures (IA32) call / return %esp, %ebp local variables recursive functionsReturn AddrSavedRegisters+LocalVariablesArgumentBuildOld %ebpArgumentsCallerFrame%ebp%esp%eax%edx%ecx%ebx%esi%edi%esp%ebpCaller-SaveCallee-SaveSpecialCarnegie MellonToday Procedures (x86-64) Arrays One-dimensional Multi-dimensional (nested) Multi-level StructuresCarnegie Mellon%rax%rbx%rcx%rdx%rsi%rdi%rsp%rbpx86-64 Integer Registers Twice the number of registers Accessible as 8, 16, 32, 64 bits%eax%ebx%ecx%edx%esi%edi%esp%ebp%r8%r9%r10%r11%r12%r13%r14%r15%r8d%r9d%r10d%r11d%r12d%r13d%r14d%r15dCarnegie Mellon%rax%rbx%rcx%rdx%rsi%rdi%rsp%rbpx86-64 Integer Registers%r8%r9%r10%r11%r12%r13%r14%r15Callee savedCallee savedCallee savedCallee savedC: Callee savedCallee savedCallee savedStack pointerUsed for linkingReturn valueArgument #4Argument #1Argument #3Argument #2Argument #6Argument #5Carnegie Mellonx86-64 Registers Arguments passed to functions via registers If more than 6 integral parameters, then pass rest on stack These registers can be used as caller-saved as well All references to stack frame via stack pointer Eliminates need to update %ebp/%rbp Other Registers 6+1 callee saved 2 or 3 have special usesCarnegie Mellonx86-64 Long Swap Operands passed in registers First (xp) in %rdi, second (yp) in %rsi 64-bit pointers No stack operations required (except ret) Avoiding stack Can hold all local information in registersvoid swap(long *xp, long *yp) {long t0 = *xp;long t1 = *yp;*xp = t1;*yp = t0;}swap:movq (%rdi), %rdxmovq (%rsi), %raxmovq %rax, (%rdi)movq %rdx, (%rsi)retCarnegie Mellonx86-64 Locals in the Red Zone Avoiding Stack Pointer Change Can hold all information within small window beyond stack pointer/* Swap, using local array */void swap_a(long *xp, long *yp) {volatile long loc[2];loc[0] = *xp;loc[1] = *yp;*xp = loc[1];*yp = loc[0];}swap_a:movq (%rdi), %raxmovq %rax, -24(%rsp)movq (%rsi), %raxmovq %rax, -16(%rsp)movq -16(%rsp), %raxmovq %rax, (%rdi)movq -24(%rsp), %raxmovq %rax, (%rsi)retrtn Ptrunused%rsp−8loc[1]loc[0]−16−24Carnegie Mellonx86-64 NonLeaf without Stack Frame No values held while swap being invoked No callee save registers neededlong scount = 0;/* Swap a[i] & a[i+1] */void swap_ele_se(long a[], int i){swap(&a[i], &a[i+1]);scount++;}swap_ele_se:movslq %esi,%rsi # Sign extend ileaq (%rdi,%rsi,8), %rdi # &a[i]leaq 8(%rdi), %rsi # &a[i+1]call swap # swap()incq scount(%rip) # scount++;retCarnegie Mellonx86-64 Call using Jumplong scount = 0;/* Swap a[i] & a[i+1] */void swap_ele(long a[], int i){swap(&a[i], &a[i+1]);}swap_ele:movslq %esi,%rsi # Sign extend ileaq (%rdi,%rsi,8), %rdi # &a[i]leaq 8(%rdi), %rsi # &a[i+1]jmp swap # swap()Will disappearBlackboard?Carnegie Mellonx86-64 Call using Jump When swap executes ret, it will return from swap_ele Possible since swap is a “tail call”(no instructions afterwards)long scount = 0;/* Swap a[i] & a[i+1] */void swap_ele(long a[], int i){swap(&a[i], &a[i+1]);}swap_ele:movslq %esi,%rsi # Sign extend ileaq (%rdi,%rsi,8), %rdi # &a[i]leaq 8(%rdi), %rsi # &a[i+1]jmp swap # swap()Carnegie Mellonx86-64 Stack Frame Example Keeps values of a and i in callee save registers Must set up stack frame to save these registerslong sum = 0;/* Swap a[i] & a[i+1] */void swap_ele_su(long a[], int i){swap(&a[i], &a[i+1]);sum += a[i];}swap_ele_su:movq %rbx, -16(%rsp)movslq %esi,%rbxmovq %r12, -8(%rsp)movq %rdi, %r12leaq (%rdi,%rbx,8), %rdisubq $16, %rspleaq 8(%rdi), %rsicall swapmovq (%r12,%rbx,8), %raxaddq %rax, sum(%rip)movq (%rsp), %rbxmovq 8(%rsp), %r12addq $16, %rspretBlackboard?Carnegie MellonUnderstanding x86-64 Stack Frameswap_ele_su:movq %rbx, -16(%rsp) # Save %rbxmovslq %esi,%rbx # Extend & save imovq %r12, -8(%rsp) # Save %r12movq %rdi, %r12 # Save aleaq (%rdi,%rbx,8), %rdi # &a[i]subq $16, %rsp # Allocate stack frameleaq 8(%rdi), %rsi # &a[i+1]call swap # swap()movq (%r12,%rbx,8), %rax # a[i]addq %rax, sum(%rip) # sum += a[i]movq (%rsp), %rbx # Restore %rbxmovq 8(%rsp), %r12 # Restore %r12addq $16, %rsp # Deallocate stack frameretCarnegie MellonUnderstanding x86-64 Stack Frameswap_ele_su:movq %rbx, -16(%rsp) # Save %rbxmovslq %esi,%rbx # Extend & save imovq %r12, -8(%rsp) # Save %r12movq %rdi, %r12 # Save aleaq (%rdi,%rbx,8), %rdi # &a[i]subq $16, %rsp # Allocate stack frameleaq 8(%rdi), %rsi # &a[i+1]call swap # swap()movq (%r12,%rbx,8), %rax # a[i]addq %rax, sum(%rip) # sum += a[i]movq (%rsp), %rbx # Restore %rbxmovq 8(%rsp), %r12 # Restore %r12addq $16, %rsp # Deallocate stack frameretrtn addr%r12%rsp−8%rbx−16rtn addr%r12%rsp+8%rbxCarnegie MellonInteresting Features of Stack Frame Allocate entire frame at once All stack accesses can be relative to %rsp Do by decrementing stack pointer Can delay allocation, since safe to temporarily use red zone Simple deallocation Increment stack pointer No base/frame pointer neededCarnegie Mellonx86-64 Procedure Summary Heavy use of registers Parameter passing More temporaries since more registers Minimal use of stack Sometimes none Allocate/deallocate entire block Many tricky optimizations What kind of stack frame to use Calling with jump Various allocation techniquesCarnegie MellonToday Procedures (x86-64) Arrays One-dimensional Multi-dimensional (nested) Multi-level StructuresCarnegie MellonBasic Data Types Integral Stored & operated on in general (integer) registers Signed vs. unsigned depends on instructions usedIntel GAS Bytes Cbyte b 1 [unsigned] charword w 2 [unsigned] shortdouble word l 4 [unsigned] intquad word q 8 [unsigned] long int (x86-64) Floating Point
View Full Document