Section 3.7.5 pics also added

Please submit individual source files for coding exercises (see naming conventions below). Your code and answers need to be documented to the point that the graders can understand your thought process. Full credit will not be awarded if sufficient work is not shown. 1. [301 Consider the following x86-64 code loop: movq movi movl %rsi, %rcx $1, %edx $0, %eax testq % rdx, je4 movq %rdx, orq %rdi, %rdx %r8 %r8 .L4: ret The code above was generated by compiling C code (with Arch gcc) that has the following overall form long loop (long a, long b) long result ? i Eor (long mask mask mask > I result -(1 2) return result: Copy the above x86-64 code into a C file as a comment. Annotate each line of the x86-64 code in terms of a, b, result, and mask. Assume that this x86-64 code follows the register usage conventions outlined in B&O'H section 3.7.5 (it does). Then implement the above C function by filling in the blanks so that it's functionally equivalent to the x86-64 code Here are some test runs: loop (1, 5): 1 loop (2, 4): 3 loop (3, 3)3 loop (4, 2) 5 loop (5, 1): 5 Also write a main() function to test your loop function. Hint: the register conventions in B&O'H section 3.7.5 with inform which registers are holding a and b Hint: try compiling your C code to x86-64 using Arch gcc with the-S, -Og flags. Name your source file 4-1.c. E. Indicate the regions of the stack frame that are not used by proc. 3.7.5 Recursive Procedures described in the previous section al The stack and linkage conventions cedures to call themselves recursively. Since each call has its own private space on the stack, the local variables of the multiple outstanding calls do not interfere with one another. Furthermore, the stack discipline naturally provides the proper policy for allocating local storage when the procedure is called and deallocating it when it returns, low pro- 230 Chapter 3 Machine-Level Representation of Programs 1 int rfact (int n) int result; if (n1) result1 else result rfact (n-1) return reault; Figure 3.25 C code for recursive factorial program. Figure 3.25 shows the C code for a recursive factorial function. The assembly code generated by Gcc is shown in Figure 3.26. Let us examine how the machine code will operate when called with argument . The set-up code (lines 2-5) creates a stack frame containing the old version of %ebp, the saved value for callee-save register %ebx, and 4 bytes to hold the argument when it calls itself recursively, as illustrated in Figure 3.27. It uses register %ebx to save a copy of n (line 6). It sets the return value in register %eax to 1 (line 7) in anticipation of the case where 1, it will jump to the completion code. For the recursive case, it computes -1, stores it on the stack, and calls itself (lines 10-12). Upon completion of the code, we can assume ( 1 ) register %eax holds 1rfact: pushl %ebp pushl 8ubl %ebx $4,%esp Set Xebp as frane pointer Sare callaa av register %ebx 2locate 4 bytes on stach result Compare a: irgoto done L53 leal -1 (%ebx) , %eaxonpute n call rfact 12 13 inull %ebx , %eax 4 L53: Call rfact (a-1) Compute result return valuen add1 4, %esp 16 popl %ebx 17 popl %ebp Deallocate 4 bytee fros stack Restore %abx Restore %ebp Figure 3.26 Assembly code for the recursive factorial program in Figure 3.25. Section 3.7 Procedures 231 Figure 3.27 Stack frame for recursive Section 3.7 Procedures 231 Figure 3.27 Stack frame for recursive factorial function. The state of the frame is shown just before the recursive call Stack frame for caling +8 Frame pointer +4Retum address saved%ebz_1 LStack trame | |for rfact Stack pointer the value of n and (2) callee-save register ebx holds the parameter . It therefore multiplies these two quantities (line 13) to generate the return value of the function For both cases the terminal condition and the recursive call the code ceeds to the completion section (lines 15-17) to restore the stack and callee-saved pro- registe r, and then it returns. We can see that calling a function recursively proceeds just like any other function cal. Our stack discipline provides a mechanism where each invocation of a function has its own private storage for state information (saved values of the return location, frame pointer, and callee-save registers). If need be, it can also provide storage for local variables. The stack discipline of allocation and deallocation naturally matches the call-return ordering of functions. This method of implementing function calls and returns even works for more complex patterns, including mutual recursion (for example, when procedure P calls Q, which in turn calls P). Practice Problem 3.34 For a C function having the general structure int rfun(unsigned x) it unsigned nx - Gcc generates the following assembly code (wth the setup and completion code omitted): no 1 8(%ebp), %ebx te t1 %ebx,%ebx je 3 232 Chapter 3 Machine Level Representation of Programs movi shri movi call mov1 %ebx,%eax %eax %eax, (heap) rfun %ebx,%edx aife righe by leal (%edx.xeaz), Xoax 2 L3 A. What value does rfun store in the callee-save register %ebx? B. Fill in the missing expressions in the C code shown above. C. Describe in English what function this code computes