1 1 Machine-Level Programming IV: x86-64 Procedures, Data2 Today  Procedures (x86-64)  Arrays  One-dimensional  Multi-dimensional (nested)  Multi-level  Structures  Allocation  Access4 %rax %rbx %rcx %rdx %rsi %rdi %rsp %rbp x86-64 Integer Registers: Usage Conventions %r8 %r9 %r10 %r11 %r12 %r13 %r14 %r15 Callee saved Callee saved Callee saved Callee saved Callee saved Caller saved Callee saved Stack pointer Caller Saved Return value Argument #4 Argument #1 Argument #3 Argument #2 Argument #6 Argument #55 x86-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 callee saved  2 caller saved  1 return value (also usable as caller saved)  1 special (stack pointer)7 x86-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), %rax movq %rax, -24(%rsp) movq (%rsi), %rax movq %rax, -16(%rsp) movq -16(%rsp), %rax movq %rax, (%rdi) movq -24(%rsp), %rax movq %rax, (%rsi) ret rtn Ptr unused %rsp −8 loc[1] loc[0] −16 −2412 Interesting 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 needed14 Today  Procedures (x86-64)  Arrays  One-dimensional  Multi-dimensional (nested)  Multi-level  Structures15 Basic Data Types  Integral  Stored & operated on in general (integer) registers  Signed vs. unsigned depends on instructions used Intel ASM Bytes C byte b 1 [unsigned] char word w 2 [unsigned] short double word l 4 [unsigned] int quad word q 8 [unsigned] long int (x86-64)  Floating Point  Stored & operated on in floating point registers Intel ASM Bytes C Single s 4 float Double l 8 double Extended t 10/12/16 long double16 Array Allocation  Basic Principle T A[L];  Array of data type T and length L  Contiguously allocated region of L * sizeof(T) bytes char string[12]; x x + 12 int val[5]; x x + 4 x + 8 x + 12 x + 16 x + 20 double a[3]; x + 24 x x + 8 x + 16 char *p[3]; x x + 8 x + 16 x + 24 x x + 4 x + 8 x + 12 IA32 x86-6417 Array Access  Basic Principle T A[L];  Array of data type T and length L  Identifier A can be used as a pointer to array element 0: Type T*  Reference Type Value val[4] int 3 val int * x val+1 int * x + 4 &val[2] int * x + 8 val[5] int ?? *(val+1) int 5 val + i int * x + 4 i int val[5]; 1 5 2 1 3 x x + 4 x + 8 x + 12 x + 16 x + 2018 Array Example  Declaration “zip_dig cmu” equivalent to “int ut[5]”  Example arrays were allocated in successive 20 byte blocks  Not guaranteed to happen in general #define ZLEN 5 typedef int zip_dig[ZLEN]; zip_dig ut = { 7, 8, 7, 1, 2 }; zip_dig mit = { 0, 2, 1, 3, 9 }; zip_dig ucb = { 9, 4, 7, 2, 0 }; zip_dig ut; 7 8 7 1 2 16 20 24 28 32 36 zip_dig mit; 0 2 1 3 9 36 40 44 48 52 56 zip_dig ucb; 9 4 7 2 0 56 60 64 68 72 7619 Array Accessing Example  Register %edx contains starting address of array  Register %eax contains array index  Desired digit at 4*%eax + %edx  Use memory reference (%edx,%eax,4) int get_digit (zip_dig z, int dig) { return z[dig]; } # %edx = z # %eax = dig movl (%edx,%eax,4),%eax # z[dig] IA32 zip_dig ut; 7 8 7 1 2 16 20 24 28 32 3620 # edx = z movl $0, %eax # %eax = i .L4: # loop: addl $1, (%edx,%eax,4) # z[i]++ addl $1, %eax # i++ cmpl $5, %eax # i:5 jne .L4 # if !=, goto loop Array Loop Example (IA32) void zincr(zip_dig z) { int i; for (i = 0; i < ZLEN; i++) z[i]++; }21 Pointer Loop Example (IA32) void zincr_p(zip_dig z) { int *zend = z+ZLEN; do { (*z)++; z++; } while (z != zend); } void zincr_v(zip_dig z) { void *vz = z; int i = 0; do { (*((int *) (vz+i)))++; i += ISIZE; } while (i != ISIZE*ZLEN); } # edx = z = vz movl $0, %eax # i = 0 .L8: # loop: addl $1, (%edx,%eax) # Increment vz+i addl $4, %eax # i += 4 cmpl $20, %eax # Compare i:20 jne .L8 # if !=, goto loop22 Nested Array Example  “zip_dig pgh[4]” equivalent to “int pgh[4][5]”  Variable pgh: array of 4 elements, allocated contiguously  Each element is an array of 5 int’s, allocated contiguously  “Row-Major” ordering of all elements guaranteed #define PCOUNT 4 zip_dig pgh[PCOUNT] = {{1, 5, 2, 0, 6}, {1, 5, 2, 1, 3 }, {1, 5, 2, 1, 7 }, {1, 5, 2, 2, 1 }}; zip_dig pgh[4]; 76 96 116 136 156 1 5 2 0 6 1 5 2 1 3 1 5 2 1 7 1 5 2 2 123 Multidimensional (Nested) Arrays  Declaration T A[R][C];  2D array of data type T  R rows, C columns  Type T element requires K bytes  Array Size  R * C * K bytes  Arrangement  Row-Major Ordering A[0][0] A[0][C-1] A[R-1][0] • • • • • • A[R-1][C-1] • • • • • • int A[R][C]; • • • A [0] [0] A [0] [C-1] • • • A [1] [0] A [1] [C-1] • • • A [R-1] [0] A [R-1] [C-1] • • • 4*R*C Bytes24 • • • Nested Array Row Access  Row Vectors  A[i] is array of C elements  Each element of type T requires K bytes  Starting address A + i * (C * K) • • • A [i] [0] A [i] [C-1] A[i] • • • A [R-1] [0] A [R-1] [C-1] A[R-1] • • • A • • • A [0] [0] A [0] [C-1] A[0] A+i*C*4 A+(R-1)*C*4 int A[R][C];25 Nested Array Row Access Code  Row Vector  pgh[index] is array of 5 int’s  Starting address pgh+20*index  IA32 Code  Computes and returns address  Compute as pgh + 4*(index+4*index) int *get_pgh_zip(int index) { return pgh[index]; } # %eax = index leal (%eax,%eax,4),%eax # 5 * index leal pgh(,%eax,4),%eax # pgh + (20 * index) #define PCOUNT 4 zip_dig pgh[PCOUNT] = {{1, 5, 2, 0, 6}, {1, 5, 2, 1, …