System Programming CSCI 2122 Winter 2021
Assignment 5 Due: 7 April, 11:00pm
(1) The following code transposes the elements of an M ×M array, where M is
a constant defined by # define:
void transpose(long A[M][M]) {
long i, j;
for (i = 0; i < M; i++)
for (j = 0; j < i; j++) {
long t = A[i][j];
A[i][j] = A[j][i];
A[j][i] = t;
}
}
When compiled, with optimization level −O1, GCC generates the following
code for the inner loop of the function.
1 .L1:
2 movq (%rdx), %rcx
3 movq (%rax), %rsi
4 movq %rsi, (%rdx)
5 movq %rcx, (%rax)
6 addq $8, %rdx
7 addq $120, %rax
8 cmpq %rdi, %rax
9 jne .L1
We can see that GCC has converted the array indexing to pointer code.
(a) Which register holds a pointer to array element A[i][j]?
(b) Which register holds a pointer to array element A[j][i]?
(c) What is the value of M?
(2) (a) The assembly code of the table below 2c was generated by compiling the
C code of Table 1.
(b) Find the expression for the unknown macro expressions (A) and (B)
appearing in Table 1. [Hint: they are both only in terms of variable ‘n’.]
(c) Identify the line numbers in the assembly code that correspond to the
following operations from the C code:
• long result = 0;
• result += A[i][j];
• i < NR(n);
1
2Table 1. C code for column-sum function. (A) and (B) represent the
unknown definitions for the macro expressions that you are required to
find.
#define NR(n) ( (A) )
#define NC(n) ( (B) )
long col sum(long n, long A[NR(n)][NC(n)], long j)
{
long i;
long result = 0;
for (i = 0; i < NR(n); i++)
result += A[i][j];
return result;
}
Assembly code for mystery function. Note that the line numbers in the
first column have no functional value, but are supplied to help you answer
the problem
1. col sum:
2. leaq 1(,%rdi, 4), %r8
3. leaq (%rdi, %rdi, 2), %rax
4. movq %rax, %rdi
5. testq %rax, %rax
6. jle .L4
7. salq $3, %r8
8. leaq (%rsi, %rdx, 8), %rcx
9. movl $0, %eax
10. movl $0, %edx
11. .L3
12. addq (%rcx), %rax
13. addq $1, %rdx
14. addq %r8, %rcx
15. cmpq %rdi, %rdx
16. jne .L3
17. ret
18. .L4
19. movl $0, %eax
20. ret
3(3) For this exercise, you will examine the code generated by gcc for functions
that have structures as arguments and return values, and from this see how
these language features are typically implemented. The following C code has
a function process having structures as argument and return values, and a
function eval that calls process:
1 typedef struct {
2 long a[2];
3 long *p;
4 } strA;
5
6 typedef struct {
7 long u[2];
8 long q;
9 } strB;
10
11 strB process(strA s) {
12 strB r;
13 r.u[0] = s.a[1];
14 r.u[1] = s.a[0];
15 r.q = *s.p;
16 return r;
17 }
18
19 long eval(long x, long y, long z){
20 strA s;
21 s.a[0] = x;
22 s.a[1] = y;
23 s.p = &z;
24 strB r = process(s);
25 return r.u[0] + r.u[1] + r.q;
26 }
4Gcc generates the following code for the two functions.
strB process(strA s)
1 process:
2 movq %rdi, %rax
3 movq 24(%rsp), %rdx
4 movq (%rdx), %rdx
5 movq 16(%rsp), %rcx
6 movq %rcx, (%rdi)
7 movq 8(%rsp), %rcx
8 movq %rcx, 8(%rdi)
9 movq %rdx, 16(%rdi)
10 ret
long eval(long x, long y, long z)
x in %rdi, y in %rsi, z in %rdx
1 eval:
2 subq $104, %rsp
3 movq %rdx, 24(%rsp)
4 leaq 24(%rsp), %rax
5 movq %rdi, (%rsp)
6 movq %rsi, 8(%rsp)
7 movq %rax, 16(%rsp)
8 leaq 64(%rsp), %rdi
9 call process
10 movq 72(%rsp), %rax
11 addq 64(%rsp), %rax
12 addq 80(%rsp), %rax
13 addq $104, %rsp
14 ret
(a) In line 2 of function eval that it allocates 104 bytes on the stack.
Diagram the stack frame for eval, showing the values it stores on the
stack prior to calling process.
(b) What value does eval pass in its call to process?
(c) How does the code for process access elements of structure argument s?
(d) How does the code for process set the fields of result structure r?
(e) Complete your diagram of the stack frame for eval, showing how eval
accesses the elements of structure r following the return from process.
5(f) What general principle can you discern about how structure values are
passed as function arguments and how they are returned as function
results?
学霸联盟