CSE 410 20wi Homework 3

Out: Saturday, 22 January
Due: Friday, 28 January, 11:59 pm
Turnin: Gradescope

Introduction

Have a look at the following program, written in C. The first two lines simply provide the compiler with the types of functions printInt and fib and do not cause any assembler code to be emitted. (We have to declare the types of functions in C before any calls to them.) The function fib() is included in this file, but after the call to it. The function printInt is implemented only in assembler, so there is no C function with that name.

Here's the assembler code produced by compiling the C program above using the CSE 410 tools. In CSE410, the assembly implementation of printInt() is automatically appended to the assembler produced by the compiler before assembling to machine code, and another assembly language function, prologue(), is prepended. When run, execution actually starts in prologue.

The assembler code is formatted so you can print this assignment and write your answers to question in the blank spaces provided. We expect turn-in to involve providing your answers via gradescope, but that is not yet set up.

Questions

  1. For each instruction in the assembly code, indicate which line of of the C source program caused that line of assembler to be generated.

    See above.

  2. Where is variable F, declared in the C program on line 3, stored at run time?

    -20(s0)

  3. In lines 40 and 41 of the assembly program, what are the names in the C program of the variables referred to as -20(s0) and -24(s0)?

    x0 and x1

  4. How much stack space is used when this program runs? That is, given the value in register sp just before line 1 of the assembler code is executed, how much lower will the sp point before the program returns from main?

    The invocation of main uses 48 bytes of stack space. The invocation of fib() in main will cause it to be invoked 19 times before any of those calls return. Each invocation uses 32 bytes of stack. So the total is 48 + 19*32 = 656 bytes (0x290 bytes).

  5. [OPTIONAL] The recursion in fib() ends if n equals either 0 or 1. That allows fib() to behave reasonably if some user calls it with n==0. (In all other cases, the check for n==0 is never true.) What code might you add to the implementation of fib to make it even more resilient to things some calling code might do, either intentionally or by error?

    (A) fib() could check for n<0 and return an error indication (the value -1, say), when it occurred. (Note: C does not have exceptions, so errors must be returned through the values returned. In this case, there isn't an int value that is clearly not the correct result as the nth term in some Fibonacci sequence. So, using -1 to mean "error" is not ideal.)

    (B) The Fibonacci sequence grows very quickly, and will overflow even for quite small values of n. The implementation could check for overflow and return an error indication.

    (C) Fibonacci overflows so fast that a better (faster) implementation would be to simply store Fib(n) as an array of (approximately 48, for 32 bit int result) constants and return the nth element.

Appendix A

In case you're interested, the C program is available to you at klaatu:/courses/cse410/22wi/hw3/h3-fib.c. On klaatu, you can copy it to your current working directory with: 

    $ cp /courses/cse410/22wi/hw3-fib.c .
You can compile it to RISC-V assembler with: 
    $CtoAsm hw3-fib.c
That will produce file hw3-fib.asm.

You can also copy the assembler code file, which is at klaatu:/courses/cse410/22wi/hw3/hw3-fib.asm. You can run the simulator on that code if you'd like.

Appendix B

The assembler code in the assignment was created by asking the compiler to turn off all optimizations when compiling. That causes it to produce the most easily understood code, which is generated basically by it looking at one source line at a time.

At the other extreme, the compiler is capable of compiling by looking at all the code available to it and finding optimizations. Below is the result of compiling the same program with optimizations on. It's pretty incredible what the compiler manages to do. In case you're interested, here's what it produces. (Remember that the compiler code must be sure that what it produces "always works" -- always gets the same result as the unoptimized code.)