Problem 4. Note: For this problem you will need to read and understand Section 3.7 of your text, especially 3.7.4 through 3.7.6. Consider this recursive version of the popcount function, which returns the number of 1 bits in its argument. int recpopcount(unsigned long n) { if (n==0) return 0; /* n != 0 */ int temp = recpopcount(n>>1); return temp + (n&1); } As described in Section 3.7.6, recursive functions have to stash values normally stored in registers on the stack. The code above generates machine code (via gcc -S -Og recpopcount.c; extraneous assembler directives have been removed). recpopcount: testq %rdi, %rdi jne .L8 movl $0, %eax ret .L8: pushq %rbx movq %rdi, %rbx shrq %rdi 3

call recpopcount andl $1, %ebx addl %ebx, %eax popq %rbx ret Recall that the first argument is passed in %rdi, and the return value will be in %eax when the final ret is executed. a. The value of n (i.e., the value in %rdi) is used after the recursive call returns. Where is it saved before the call (what instruction)? b. Suppose the function is called with the argument 7, and suppose that at the time of that call the register %rbx contains 100. Draw a diagram showing the contents of the stack immediately after that call, assuming the address of the instruction after the call to recpopcount is 0x555500a6. Draw the stack with the top of the stack (i.e., the quadword containing the return address) at the bottom. (The instructor will give an example in class or on the assignment page.) c. Draw another diagram showing the stack contents immediately after the first recursive call. Your diagram should show everything from the previous part, plus anything pushed on the stack after that initial call. d. Draw another diagram showing the stack contents (including the previous parts), immediately after the last recursive call. Again, show anything pushed on the stack in the meantime.