Australian National University Machine-Level Programming II: Control PDF

Australian National University Carnegie Mellon Convener: Prof John Taylor 1  Carnegie Mellon Course Update ¢ Public Holiday Monday 7 October ¢ Make-up Lecture...

Australian National University Carnegie Mellon Convener: Prof John Taylor 1  Carnegie Mellon Course Update ¢ Public Holiday Monday 7 October ¢ Make-up Lecture § When: Tuesday 8 October, 14:00-16:00 § Where: Copland Lecture Theatre ¢ Quiz 1 – released on Tuesday § On Wattle § Covers all of week 1 and 2 § To help you assess your performance 2  Carnegie Mellon Machine-Level Programming II: Control Acknowledgement of material: With changes suited to ANU needs, the slides are obtained from Carnegie Mellon University: https://www.cs.cmu.edu/~213/ Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 3  Today ¢ Control: Condition codes ¢ Conditional branches ¢ Loops ¢ Switch Statements Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 4  Processor State (x86-64, Partial) ¢ Information about currently executing Registers program %rax %r8 § Temporary data %rbx %r9 ( %rax, … ) %rcx %r10 § Location of runtime stack %rdx %r11 ( %rsp ) %rsi %r12 § Location of current code %rdi %r13 control point %rsp %r14 ( %rip, … ) %rbp %r15 § Status of recent tests ( CF, ZF, SF, OF ) %rip Instruction pointer Current stack top CF ZF SF OF Condition codes Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 5  Condition Codes (Implicit Setting) ¢ Single bit registers CF Carry Flag (for unsigned) SF Sign Flag (for signed) ZF Zero Flag OF Overflow Flag (for signed) ¢ Implicitly set (think of it as side effect) by arithmetic operations Example: addq Src,Dest ↔ t = a+b CF set if carry out from most significant bit (unsigned overflow) ZF set if t == 0 SF set if t < 0 (as signed) OF set if two’s-complement (signed) overflow (a>0 && b>0 && t movzbl %al, %eax # Zero rest of %rax ret Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 11  Today ¢ Control: Condition codes ¢ Conditional branches ¢ Loops ¢ Switch Statements Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 12  Jumping ¢ jX Instructions § Jump to different part of code depending on condition codes jX Condition Description jmp 1 Unconditional je ZF Equal / Zero jne ~ZF Not Equal / Not Zero js SF Negative jns ~SF Nonnegative jg ~(SF^OF)&~ZF Greater (Signed) jge ~(SF^OF) Greater or Equal (Signed) jl (SF^OF) Less (Signed) jle (SF^OF)|ZF Less or Equal (Signed) ja ~CF&~ZF Above (unsigned) jb CF Below (unsigned) Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 13  Conditional Branch Example (Old Style) ¢ Generation linux> gcc –Og -S –fno-if-conversion control.c absdiff: long absdiff cmpq %rsi, %rdi # x:y (long x, long y) jle.L4 { movq %rdi, %rax long result; subq %rsi, %rax if (x > y) ret result = x-y;.L4: # x y) int ntest = x y ? x-y : y-x; Goto Version ntest = !Test; § Create separate code regions for if (ntest) goto Else; then & else expressions val = Then_Expr; goto Done; § Execute appropriate one Else: val = Else_Expr; Done:... Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 16  Using Conditional Moves ¢ Conditional Move Instructions § Instruction supports: if (Test) Dest ß Src § Supported in post-1995 x86 processors C Code § GCC tries to use them val = Test § But, only when known to be safe ? Then_Expr : Else_Expr; ¢ Why? § Branches are very disruptive to instruction flow through pipelines Goto Version § Conditional moves do not require result = Then_Expr; control transfer eval = Else_Expr; nt = !Test; if (nt) result = eval; return result; Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 17  Conditional Move Example long absdiff (long x, long y) { Register Use(s) long result; if (x > y) %rdi Argument x result = x-y; %rsi Argument y else %rax Return value result = y-x; return result; } absdiff: movq %rdi, %rax # x subq %rsi, %rax # result = x-y movq %rsi, %rdx subq %rdi, %rdx # eval = y-x cmpq %rsi, %rdi # x:y cmovle %rdx, %rax # if 0 ? x*=7 : x+=3; ¢ Both values get computed – x changes! ¢ Must be side-effect free Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 19  Today ¢ Control: Condition codes ¢ Conditional branches ¢ Loops ¢ Switch Statements Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 20  “Do-While” Loop Example C Code Goto Version long pcount_do long pcount_goto (unsigned long x) { (unsigned long x) { long result = 0; long result = 0; do { loop: result += x & 0x1; result += x & 0x1; x >>= 1; x >>= 1; } while (x); if(x) goto loop; return result; return result; } } ¢ Count number of 1’s in argument x (“popcount”) ¢ Use conditional branch to either continue looping or to exit loop Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 21  “Do-While” Loop Compilation Goto Version long pcount_goto (unsigned long x) { Register Use(s) long result = 0; loop: %rdi Argument x result += x & 0x1; %rax result x >>= 1; if(x) goto loop; return result; } movl $0, %eax # result = 0.L2: # loop: movq %rdi, %rdx andl $1, %edx # t = x & 0x1 addq %rdx, %rax # result += t shrq %rdi # x >>= 1 jne.L2 # if (x) goto loop rep; ret Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 22  General “Do-While” Translation C Code Goto Version do loop: Body Body while (Test); if (Test) goto loop ¢ Body: { Statement1; Statement2; … Statementn; } Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 23  General “While” Translation #1 ¢ “Jump-to-middle” translation ¢ Used with -Og Goto Version goto test; loop: While version Body while (Test) test: Body if (Test) goto loop; done: Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 24  While Loop Example #1 C Code Jump to Middle long pcount_while Version long pcount_goto_jtm (unsigned long x) { (unsigned long x) { long result = 0; long result = 0; while (x) { goto test; result += x & 0x1; loop: x >>= 1; result += x & 0x1; } x >>= 1; return result; test: } if(x) goto loop; return result; } ¢ Compare to do-while version of function ¢ Initial goto starts loop at test Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 25  General “While” Translation #2 While version ¢ “Do-while” conversion while (Test) ¢ Used with –O1 Body Goto Version Do-While Version if (!Test) if (!Test) goto done; goto done; loop: do Body Body if (Test) while(Test); goto loop; done: done: Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 26  While Loop Example #2 C Code Do-While Version long pcount_while long pcount_goto_dw (unsigned long x) { (unsigned long x) { long result = 0; long result = 0; while (x) { if (!x) goto done; result += x & 0x1; loop: x >>= 1; result += x & 0x1; } x >>= 1; return result; if(x) goto loop; } done: return result; } ¢ Compare to do-while version of function ¢ Initial conditional guards entrance to loop Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 27  “For” Loop Form Init General Form i = 0 for (Init; Test; Update ) Test Body i < WSIZE #define WSIZE 8*sizeof(int) Update long pcount_for i++ (unsigned long x) { size_t i; Body long result = 0; { for (i = 0; i < WSIZE; i++) unsigned bit = { (x >> i) & 0x1; unsigned bit = result += bit; (x >> i) & 0x1; } result += bit; } return result; } Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 28  “For” Loop à While Loop For Version for (Init; Test; Update ) Body While Version Init; while (Test ) { Body Update; } Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 29  For-While Conversion long pcount_for_while Init (unsigned long x) { i = 0 size_t i; long result = 0; Test i = 0; i < WSIZE while (i < WSIZE) { Update unsigned bit = (x >> i) & 0x1; i++ result += bit; i++; Body } { return result; unsigned bit = } (x >> i) & 0x1; result += bit; } Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 30  “For” Loop Do-While Conversion Goto Version C Code long pcount_for_goto_dw (unsigned long x) { long pcount_for size_t i; (unsigned long x) long result = 0; { i = 0; Init size_t i; if (!(i < WSIZE)) long result = 0; goto done; !Test for (i = 0; i < WSIZE; i++) loop: { { unsigned bit = unsigned bit = (x >> i) & 0x1; (x >> i) & 0x1; Body result += bit; result += bit; } } return result; i++; Update } if (i < WSIZE) Test goto loop; ¢ Initial test can be optimized done: away return result; } Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 31  Today ¢ Control: Condition codes ¢ Conditional branches ¢ Loops ¢ Switch Statements Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 32  long switch_eg (long x, long y, long z) Switch Statement { long w = 1; Example switch(x) { case 1: w = y*z; ¢ Multiple case labels break; § Here: 5 & 6 case 2: w = y/z; ¢ Fall through cases § Here: 2 case 3: w += z; ¢ Missing cases break; § Here: 4 case 5: case 6: w -= z; break; default: w = 2; } return w; } Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 33  Jump Table Structure Switch Form Jump Table Jump Targets switch(x) { jtab: Targ0 Targ0: Code Block case val_0: 0 Block 0 Targ1 case val_1: Targ2 Targ1: Block 1 Code Block 1 case val_n-1: Block n–1 Targ2: Code Block } Targn-1 2 Translation (Extended C) goto *JTab[x]; Targn-1: Code Block n–1 Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 34  Switch Statement Example long switch_eg(long x, long y, long z) { long w = 1; switch(x) {... } return w; } Setup: Register Use(s) switch_eg: movq %rdx, %rcx %rdi Argument x cmpq $6, %rdi # x:6 %rsi Argument y ja.L8 jmp *.L4(,%rdi,8) %rdx Argument z %rax Return value What range of values Note that w not takes default? Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition initialized here 35  Switch Statement Example long switch_eg(long x, long y, long z) { long w = 1; switch(x) {... Jump table.section.rodata }.align 8 return w;.L4: }.quad.L8 # x = 0.quad.L3 # x = 1.quad.L5 # x = 2 Setup:.quad.L9 # x = 3.quad.L8 # x = 4 switch_eg:.quad.L7 # x = 5 movq %rdx, %rcx.quad.L7 # x = 6 cmpq $6, %rdi # x:6 ja.L8 # Use default Indirect jmp *.L4(,%rdi,8) # goto *JTab[x] jump Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 36  Assembly Setup Explanation ¢ Table Structure Jump table § Each target requires 8 bytes.section.rodata § Base address at.L4.align 8.L4:.quad.L8 # x = 0.quad.L3 # x = 1 ¢ Jumping.quad.L5 # x = 2.quad.L9 # x = 3 § Direct: jmp.L8.quad.L8 # x = 4 § Jump target is denoted by label.L8.quad.quad.L7 # x.L7 # x = = 5 6 § Indirect: jmp *.L4(,%rdi,8) § Start of jump table:.L4 § Must scale by factor of 8 (addresses are 8 bytes) § Fetch target from effective Address.L4 + x*8 § Only for 0 ≤ x ≤ 6 Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 37  Jump Table Jump table switch(x) {.section.rodata case 1: //.L3.align 8 w = y*z;.L4: break;.quad.L8 # x = 0.quad.L3 # x = 1 case 2: //.L5.quad.L5 # x = 2 w = y/z;.quad.L9 # x = 3.quad.L8 # x = 4 case 3: //.L9.quad.L7 # x = 5.quad.L7 # x = 6 w += z; break; case 5: case 6: //.L7 w -= z; break; default: //.L8 w = 2; } Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 38  Code Blocks (x == 1) switch(x) {.L3: case 1: //.L3 movq %rsi, %rax # y w = y*z; imulq %rdx, %rax # y*z break; ret... } Register Use(s) %rdi Argument x %rsi Argument y %rdx Argument z %rax Return value Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 39  Handling Fall-Through long w = 1;... switch(x) { case 2:... w = y/z; case 2: goto merge; w = y/z; case 3: w += z; break;... case 3: } w = 1; merge: w += z; Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 40  Code Blocks (x == 2, x == 3).L5: # Case 2 long w = 1; movq %rsi, %rax... cqto switch(x) { idivq %rcx # y/z... jmp.L6 # goto merge case 2:.L9: # Case 3 w = y/z; movl $1, %eax # w = 1.L6: # merge: case 3: addq %rcx, %rax # w += z w += z; ret break;... } Register Use(s) %rdi Argument x %rsi Argument y %rdx Argument z %rax Return value Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 41  Code Blocks (x == 5, x == 6, default) switch(x) {.L7: # Case 5,6... movl $1, %eax # w = 1 case 5: //.L7 subq %rdx, %rax # w -= z case 6: //.L7 ret w -= z;.L8: # Default: break; movl $2, %eax # 2 default: //.L8 ret w = 2; } Register Use(s) %rdi Argument x %rsi Argument y %rdx Argument z %rax Return value Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 42  Summarizing ¢ C Control § if-then-else § do-while § while, for § switch ¢ Assembler Control § Conditional jump § Conditional move § Indirect jump (via jump tables) § Compiler generates code sequence to implement more complex control ¢ Standard Techniques § Loops converted to do-while or jump-to-middle form § Large switch statements use jump tables § Sparse switch statements may use decision trees (if-elseif-elseif-else) Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 43  Summary ¢ Today § Control: Condition codes § Conditional branches & conditional moves § Loops § Switch statements ¢ Next Time § Stack § Call / return § Procedure call discipline Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 44  Australian National University Convener: Prof John Taylor Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 45  Machine-Level Programming III: Procedures Acknowledgement of material: With changes suited to ANU needs, the slides are obtained from Carnegie Mellon University: https://www.cs.cmu.edu/~213/ Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 46  Mechanisms in Procedures P(…) { ¢ Passing control § To beginning of procedure code y = Q(x); § Back to return point print(y) ¢ Passing data } § Procedure arguments § Return value ¢ Memory management int Q(int i) { § Allocate during procedure execution int t = 3*i; § Deallocate upon return int v; ¢ Mechanisms all implemented with machine instructions return v[t]; } ¢ x86-64 implementation of a procedure uses only the required mechanisms Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 47  Today ¢ Procedures § 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 48  x86-64 Stack Stack “Bottom” ¢ Region of memory managed with stack discipline ¢ Grows toward lower addresses Increasing Addresses ¢ Register %rsp contains lowest stack address § address of “top” element Stack Grows Down Stack Pointer: %rsp Stack “Top” Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 49  x86-64 Stack: Push Stack “Bottom” ¢ pushq Src § Fetch operand at Src § Decrement %rsp by 8 Increasing Addresses § Write operand at address given by %rsp Stack Grows Down Stack Pointer: %rsp -8 Stack “Top” Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 50  x86-64 Stack: Pop Stack “Bottom” ¢ popq Dest § Read value at address given by %rsp § Increment %rsp by 8 Increasing Addresses § Store value at Dest (must be register) Stack Grows +8 Down Stack Pointer: %rsp Stack “Top” Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 51  Today ¢ Procedures § 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 52  void multstore Code Examples { (long x, long y, long *dest) long t = mult2(x, y); *dest = t; } 0000000000400540 : 400540: push %rbx # Save %rbx 400541: mov %rdx,%rbx # Save dest 400544: callq 400550 # mult2(x,y) 400549: mov %rax,(%rbx) # Save at dest 40054c: pop %rbx # Restore %rbx 40054d: retq # Return long mult2 0000000000400550 : (long a, long b) 400550: mov %rdi,%rax # a { 400553: imul %rsi,%rax # a * b long s = a * b; 400557: retq # Return return s; } Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 53  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 54  Control Flow Example #1 0000000000400540 : 0x130 0x128 0x120 400544: callq 400550 400549: mov %rax,(%rbx) %rsp 0x120 %rip 0x400544 0000000000400550 : 400550: mov %rdi,%rax 400557: retq Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 55  Control Flow Example #2 0000000000400540 : 0x130 0x128 0x120 400544: callq 400550 400549: mov %rax,(%rbx) 0x118 0x400549 %rsp 0x118 %rip 0x400550 0000000000400550 : 400550: mov %rdi,%rax 400557: retq Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 56  Control Flow Example #3 0000000000400540 : 0x130 0x128 0x120 400544: callq 400550 400549: mov %rax,(%rbx) 0x118 0x400549 %rsp 0x118 %rip 0x400557 0000000000400550 : 400550: mov %rdi,%rax 400557: retq Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 57  Control Flow Example #4 0000000000400540 : 0x130 0x128 0x120 400544: callq 400550 400549: mov %rax,(%rbx) %rsp 0x120 %rip 0x400549 0000000000400550 : 400550: mov %rdi,%rax 400557: retq Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 58  Today ¢ Procedures § 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 59  Procedure Data Flow Registers Stack ¢ First 6 arguments %rdi %rsi Arg n %rdx %rcx %r8 Arg 8 %r9 Arg 7 ¢ Return value %rax ¢ Only allocate stack space when needed Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 60  void multstore Data Flow (long x, long y, long *dest) { Examples long t = mult2(x, y); *dest = t; } 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 0000000000400550 : (long a, long b) # a in %rdi, b in %rsi { 400550: mov %rdi,%rax # a long s = a * b; 400553: imul %rsi,%rax # a * b return s; # s in %rax } 400557: retq # Return Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 61  Today ¢ Procedures § 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 62  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 63  Call Chain Example Example yoo(…) Call Chain { yoo who(…) who(); { who amI(); } amI(…) amI amI { amI(); amI } amI(); amI } Procedure amI() is recursive Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 64  Stack Frames Previous Frame ¢ Contents § Return information Frame Pointer: %rbp § Local storage (if needed) (Optional) x § Temporary space (if needed) Frame for proc Stack Pointer: %rsp ¢ Management § Space allocated when enter procedure Stack “Top” § “Set-up” code § Includes push by call instruction § Deallocated when return § “Finish” code § Includes pop by ret instruction Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 65  Stack Example yoo(…) yoo %rbp { yoo yoo who %rsp who(); amI amI } amI amI Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 66  Stack Example yoo(…) yoo { who(…) { yoo yoo who %rbp amI(); who(); amI amI who amI(); %rsp } } amI amI Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 67  Stack Example yoo(…) yoo { who(…) { yoo yoo amI(…) who { amI(); who(); who amI amI amI(); } amI(); %rbp } amI amI %rsp } amI Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 68  Stack Example yoo(…) yoo { who(…) { yoo yoo amI(…) who { amI(); who(); amI(…) who { amI amI amI(); } amI(); } amI amI amI(); } %rbp amI } amI %rsp Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 69  Stack Example yoo(…) yoo { who(…) { yoo yoo amI(…) who { amI(); who(); amI(…) who { amI amI amI(); amI(…) } amI(); { } amI amI amI(); } amI(); amI } amI } %rbp amI %rsp Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 70  Stack Example yoo(…) yoo { who(…) { yoo yoo amI(…) who { amI(); who(); amI(…) who { amI amI amI(); } amI(); } amI amI amI(); } %rbp amI } amI %rsp Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 71  Stack Example yoo(…) yoo { who(…) { yoo yoo amI(…) who { amI(); who(); who amI amI amI(); } amI(); %rbp } amI amI %rsp } amI Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 72  Stack Example yoo(…) yoo { who(…) { yoo yoo who %rbp amI(); who(); amI amI who amI(); %rsp } } amI amI Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 73  Stack Example yoo(…) yoo { who(…) { yoo yoo amI(…) who { amI(); who(); who amI amI amI(); } amI(); %rbp } amI amI %rsp } amI Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 74  Stack Example yoo(…) yoo { who(…) { yoo yoo who %rbp amI(); who(); amI amI who amI(); %rsp } } amI amI Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 75  Stack Example yoo yoo(…) %rbp { yoo yoo who %rsp who(); amI amI } amI amI Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 76  x86-64/Linux Stack Frame ¢ Current Stack Frame (“Top” to Bottom) § “Argument build:” Parameters for function about to call Caller Frame § Local variables Arguments If can’t keep in registers 7+ § Saved register context Frame pointer Return Addr § Old frame pointer (optional) %rbp Old %rbp (Optional) Saved ¢ Caller Stack Frame Registers + § Return address Local § Pushed by call instruction Variables § Arguments for this call Argument Stack pointer Build %rsp (Optional) Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 77  Example: incr long incr(long *p, long val) { long x = *p; long y = x + val; *p = y; return x; } incr: Register Use(s) movq (%rdi), %rax addq %rax, %rsi %rdi Argument p movq %rsi, (%rdi) %rsi Argument val, y ret %rax x, Return value Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 78  Example: Calling incr #1 Initial Stack Structure long call_incr() { long v1 = 15213; long v2 = incr(&v1, 3000);... return v1+v2; } Rtn address %rsp call_incr: subq $16, %rsp Resulting Stack Structure movq $15213, 8(%rsp) movl $3000, %esi leaq 8(%rsp), %rdi... call incr addq 8(%rsp), %rax Rtn address addq $16, %rsp ret 15213 %rsp+8 Unused %rsp Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 79  Example: Calling incr #2 Stack Structure long call_incr() { long v1 = 15213; long v2 = incr(&v1, 3000);... return v1+v2; } Rtn address 15213 %rsp+8 Unused %rsp call_incr: subq $16, %rsp movq $15213, 8(%rsp) Register Use(s) movl $3000, %esi %rdi &v1 leaq 8(%rsp), %rdi call incr %rsi 3000 addq 8(%rsp), %rax addq $16, %rsp ret Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 80  Example: Calling incr #3 Stack Structure long call_incr() { long v1 = 15213; long v2 = incr(&v1, 3000);... return v1+v2; } Rtn address 18213 %rsp+8 Unused %rsp call_incr: subq $16, %rsp movq $15213, 8(%rsp) Register Use(s) movl $3000, %esi %rdi &v1 leaq 8(%rsp), %rdi call incr %rsi 3000 addq 8(%rsp), %rax addq $16, %rsp ret Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 81  Example: Calling incr #4 Stack Structure long call_incr() { long v1 = 15213;... long v2 = incr(&v1, 3000); return v1+v2; Rtn address } 18213 %rsp+8 Unused %rsp call_incr: subq $16, %rsp Register Use(s) movq $15213, 8(%rsp) %rax Return value movl $3000, %esi leaq 8(%rsp), %rdi Updated Stack Structure call incr addq 8(%rsp), %rax addq $16, %rsp... ret Rtn address %rsp Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 82  Example: Calling incr #5 long call_incr() { Updated Stack Structure long v1 = 15213; long v2 = incr(&v1, 3000);... return v1+v2; } Rtn address %rsp call_incr: subq $16, %rsp Register Use(s) movq $15213, 8(%rsp) %rax Return value movl $3000, %esi leaq 8(%rsp), %rdi Final Stack Structure call incr addq 8(%rsp), %rax addq $16, %rsp... ret %rsp Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 83  Register Saving Conventions ¢ When procedure yoo calls who: § yoo is the caller § who is the callee ¢ Can register be used for temporary storage? yoo: who: movq $15213, %rdx subq $18213, %rdx call who addq %rdx, %rax ret ret § 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 84  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 85  x86-64 Linux Register Usage #1 ¢ %rax Return value %rax § Return value § Also caller-saved %rdi § Can be modified by procedure %rsi ¢ %rdi,..., %r9 %rdx Arguments § Arguments %rcx § Also caller-saved %r8 § Can be modified by procedure %r9 ¢ %r10, %r11 § Caller-saved %r10 Caller-saved § Can be modified by procedure temporaries %r11 Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 86  x86-64 Linux Register Usage #2 ¢ %rbx, %r12, %r13, %r14 %rbx § Callee-saved Callee-saved %r12 § Callee must save & restore Temporaries %r13 ¢ %rbp %r14 § Callee-saved %rbp § Callee must save & restore Special § May be used as frame pointer %rsp § Can mix & match ¢ %rsp § Special form of callee save § Restored to original value upon exit from procedure Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 87  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 Resulting Stack Structure movq %rdi, %rbx movq $15213, 8(%rsp)... movl $3000, %esi leaq 8(%rsp), %rdi call incr Rtn address addq %rbx, %rax Saved %rbx addq $16, %rsp 15213 %rsp+8 popq %rbx ret Unused %rsp Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 88  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 15213 %rsp+8 call_incr2: pushq %rbx Unused %rsp subq $16, %rsp movq %rdi, %rbx movq $15213, 8(%rsp) Pre-return Stack Structure movl $3000, %esi leaq 8(%rsp), %rdi call incr... addq %rbx, %rax addq $16, %rsp Rtn address %rsp popq %rbx ret Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 89  Today ¢ Procedures § 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 90  Recursive Function pcount_r: movl $0, %eax testq %rdi, %rdi long pcount_r(unsigned long x) { je.L6 if (x == 0) pushq %rbx return 0; movq %rdi, %rbx else andl $1, %ebx return (x & 1) shrq %rdi # (by 1) + pcount_r(x >> 1); call pcount_r } addq %rbx, %rax popq %rbx.L6: rep; ret Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 91  Recursive Function Terminal Case pcount_r: long pcount_r(unsigned long x) { movl $0, %eax if (x == 0) testq %rdi, %rdi return 0; je.L6 else pushq %rbx return (x & 1) movq %rdi, %rbx + pcount_r(x >> 1); andl $1, %ebx } shrq %rdi # (by 1) call pcount_r addq %rbx, %rax popq %rbx.L6: rep; ret Register Use(s) Type %rdi x Argument %rax Return value Return value Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 92  Recursive Function Register Save pcount_r: movl $0, %eax long pcount_r(unsigned long x) { testq %rdi, %rdi if (x == 0) je.L6 return 0; pushq %rbx else movq %rdi, %rbx return (x & 1) andl $1, %ebx + pcount_r(x >> 1); shrq %rdi # (by 1) } call pcount_r addq %rbx, %rax popq %rbx.L6: rep; ret Register Use(s) Type %rdi x Argument... Rtn address Saved %rbx %rsp Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 93  Recursive Function Call Setup pcount_r: long pcount_r(unsigned long x) { movl $0, %eax if (x == 0) testq %rdi, %rdi return 0; je.L6 else pushq %rbx return (x & 1) movq %rdi, %rbx + pcount_r(x >> 1); andl $1, %ebx } shrq %rdi # (by 1) call pcount_r addq %rbx, %rax popq %rbx.L6: rep; ret Register Use(s) Type %rdi x >> 1 Rec. argument %rbx x & 1 Callee-saved Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 94  Recursive Function Call pcount_r: long pcount_r(unsigned long x) { movl $0, %eax if (x == 0) testq %rdi, %rdi return 0; je.L6 else pushq %rbx return (x & 1) movq %rdi, %rbx + pcount_r(x >> 1); andl $1, %ebx } shrq %rdi # (by 1) 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 95  Recursive Function Result pcount_r: long pcount_r(unsigned long x) { movl $0, %eax if (x == 0) testq %rdi, %rdi return 0; je.L6 else pushq %rbx return (x & 1) movq %rdi, %rbx + pcount_r(x >> 1); andl $1, %ebx } shrq %rdi # (by 1) 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 96  Recursive Function Completion pcount_r: movl $0, %eax long pcount_r(unsigned long x) { testq %rdi, %rdi if (x == 0) je.L6 return 0; pushq %rbx else movq %rdi, %rbx return (x & 1) andl $1, %ebx + pcount_r(x >> 1); shrq %rdi # (by 1) } call pcount_r addq %rbx, %rax popq %rbx.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 97  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) § 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 98  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 ¢ Recursion (& mutual recursion) handled by 7+ normal calling conventions Return Addr %rbp Old %rbp § Can safely store values in local stack frame and in (Optional) callee-saved registers Saved § Put function arguments at top of stack Registers § Result return in %rax + Local ¢ Pointers are addresses of values Variables § On stack or global Argument Build %rsp Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 99  Australian National University Carnegie Mellon Convener: Prof John Taylor 100  Machine-Level Programming IV: Data Acknowledgement of material: With changes suited to ANU needs, the