3.66.md

3.66

Consider the following source code, where NR and NC are macro expressions de- clared with #define that compute the dimensions of array A in terms of parame- ter n. This code computes the sum of the elements of column j of the array.

long sum_col(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;
}

# n in %rdi
# A in $rsi
# j in %rdx
sum_col:
  leaq    1(,%rdi,4), %r8       # %r8 = 1 + 4n
  leaq    (%rdi,%rdi,2), %rax   # %rax = 3n
  movq    %rax, %rdi            # %rdi = %rax = 3n
  testq   %rax, %rax            # test whether %rax is zero, pos, neg
  jle     .L4                   # Jump to .L4 if (%rax <= 0)
  salq    $3, %r8               # (%r8 << 3) is equivalent to (1 + 4n)*8
  leaq    (%rsi,%rdx,8), %rcx   # %rcx = A + 8j
  movl    $0, %eax              # %eax = 0   # result = 0
  movl    $0, %edx              # %edx = 0   # i = 0

.L3:
  addq    (%rcx), %rax          # %rax = *rcx =  A + 8j
  addq    $1, %rdx              # %rdx = %rdx + 1   # i++
  addq    %r8, %rcx             # rdc + %r8 == [(A + 8j) + ((1 + 4n)*8)]
  cmpq    %rdi, %rdx            # compare %rdi and %rdx
  jne     .L3                   # if (3n != j+1) jump to .L3
  rep;    ret                   # return result

.L4:
  movl    $0, %eax             # return 0
  ret

What is NR?

In C code, we are doing i < NR(n) comparision the for loop.

rdx register holds the value of i , we know this because .L3 is the for loop, and on each iteration, i is incremented by one.

addq    $1, %rdx              # %rdx = %rdx + 1   # i++

Then within .L3 there is a comparision

cmpq    %rdi, %rdx            # compare %rdi and %rdx

rdi holds 3n, therefore, NR(n) is 3n

i < NR(n) equivalent to i < 3n

What is NC?

addq    (%rcx), %rax          # %rax = *rcx =  A + 8j
addq    $1, %rdx              # %rdx = %rdx + 1   # i++
addq    %r8, %rdc             # rdc + %r8 == [(A + 8j) + ((1 + 4n)*8)]

NC is 1+ 4n