# Quiz2 of Computer Architecture (2020 Fall)
> Solutions

## Question `A`

For each RISC-V instruction sequence below, provide the ==hex== values of the specified registers after each sequence has been executed. Assume that all registers are initialized to 0 prior to each instruction sequence. Each instruction sequence begins with the line (`. = 0x0`) which indicates that the first instruction of each sequence is at address 0. Assume that each sequence execution ends when it reaches the `UNIMPL` instruction.

. = 0x0
    jal x5, L1    # Value left in x5? __A01__
    jal x6, end   # Value left in x6? __A02__
L1: j L2
    jal x6, end   # Address of label L2? __A03__
L2: jr x5
end:
    UNIMPL

Solutions:
* A01 : ==`0x4`==
* A02 : ==`0x8`==
* A03 : ==`0x10`==

:::spoiler
Illustrations:
1. `pc = 0x0: jal x5 L1` sets x5 to the address of the instruction after `jal L1, x5`, which is 4, and then jumps to L1
2. `pc = 0x8: j L2` jumps to L2
3. `pc = 0x10: jr x5` jumps to the instruction at address 4, which is `jal x6, end`
5. `pc = 0x4: jal x6, end` sets x6 to the address of the instruction after that `jal x6, end`, which is 8
6. `pc = 0x14:` the program stops
7. L2 is at `0x10` because it is 4 words after the first word, which is at `0x0`, so it is $4 \times 4$.
:::

---

## Question `B`

:::info
Pseudo-instructions
– shorthand syntax for common assembly idioms
– `mv rd, rs` = `addi rd, rs, 0`
– `li rd, 13` = `addi rd, x0, 13`
:::

RISC-V sequence B refers to certain locations in memory. Provide the ==hex== values of the specified registers after each sequence has been executed. Assume that the first 5 memory locations starting from address 0x600 have been initialized with the following 5 words. Assume that each sequence execution ends when it reaches the `UNIMPL` instruction.

. = 0x600
# First 5 words at address 0x600
.word 0x60046004
.word 0x87654321
.word 0x12345678
.word 0x00000001

Sequence `B`

. = 0x0
    li x7, 0x600
    mv x8, x7            # Value left in x7? __B01__
loop: addi x8, x8, 4     # Value left in x8? __B02__
    lw x9, 0(x8)
    sw x9, -4(x8)        
    blez x9, loop        # Value left in x9? __B03__
    lw x7, 0(x7)
end:
    UNIMPL

Solutions:
* B01 : ==`0x87654321`==
* B02 : ==`0x608`==
* B03 : ==`0x12345678`==

:::spoiler
Illustrations:
1. The program loops through the given words starting from address `0x604`.
2. It copies each word into the previous word in memory, and then continues looping if that word was less than or equal to 0.
3. `0x87654321` is less than 0 because its most significant bit is set in two’s complement, but `0x12345678` is not, so the program stops looping when `x8 = 0x608` and `x9 = 0x12345678`.
4. x7 still equals to its original value, `0x600` until the last line, but loading `0x600` at the end gives `0x87654321` because the first iteration of the loop overwrote it.
:::

---

## Question `C`

Below is the C code for a recursive implementation of binary search, which finds the index at which an element should be inserted into a sorted array to ensure that the array is still sorted after the insertion. The roughly translated RISC-V assembly follows the C code.

/* A recursive binary search function.
 * It returns location of x in given array arr[l..r]
 * is present, otherwise -1
 */
int binary_search(int arr[], int l, int r, int x) 
{ 
    if (r >= l) { 
        int mid = l + (r - l) / 2; 
  
        /* If the element is present at the middle itself */
        if (arr[mid] == x)
            return mid; 
  
        /* If element is smaller than mid, then it can only be present 
         * in left subarray
         */
        if (arr[mid] > x)
            return binary_search(arr, l, mid - 1, x); 
  
        /* Else the element can only be present in right subarray */
        return binarySearch(arr, mid + 1, r, x); 
    } 
  
    /* We reach here when element is not present in array */
    return -1; 
} 

- [ ] RISC-V Assembly

binary_search:
    addi sp, sp, -8
    sw ra, 4(sp)
    sw s0, 0(sp)
    mv s0, a2
    beq a1, a2, done
    add t0, a1, a2
    srli t0, t0, 1
    slli t1, t0, 2
    add t1, a0, t1
    lw t1, 0(t1)
if_: bge __C01__
    mv a2, t0
    j recurse
else_:
    addi t0, t0, 1
    mv a1, t0
recurse:
    call binary_search
    mv s0, a0
done:
    mv a0, s0
    lw s0, 0(sp)
    lw ra, 4(sp)
L1:
    addi sp, sp, 8
    ret

1. What should be in the blank on the line labeled if to make the assembly implementation match the C code?
> C01 = ==`a2, t1, else_`==

2. How many words will be written to the stack before the program makes each recursive call to the function binary_search? That is, number of words pushed onto stack before each recursive call?
> C02 = ==`2`==

3. The program’s initial call to function binary_search occurs outside of the function definition via the instruction `call binary_search`. The program is interrupted during a recursive call to `binary_search`, just prior to the execution of `addi sp, sp, 8` at label L1. The diagram on the right shows the contents of a region of memory. All addresses and data values are shown in hex. The current value in the SP register is `0xEB0` and points to the location shown in the diagram CONTENT. What are the ==hex== values in the following registers right when the execution of binary_search is interrupted?
Current value of s0?
> C03 = ==`0x6`==

Current value of ra?
> C04 = ==`0xC4`==

| Memory address | Data content |
| -------------- | ------------ |
| 0xEA4 | 0x0 |
| 0xEA8 | 0x5 |
| 0xEAC | 0xC4 |
| SP→ 0xEB0 | 0x6 |
| 0xEB4 | 0xC4 |
| 0xEB8 | 0x6 |
| 0xEBC | 0xC4 |
| 0xEC0 | 0xA |
| 0xEC4 | 0xC4 |
| 0xEC8 | 0x3E |
| 0xECC | 0xCA4 |
| 0xED0 | 0xCED |

> diagram: CONTENT, `sp` points to `0xEB0`.

4. What is the hex address of the `ret` instruction?
Address of ret instruction?
> C05 = ==`0xD8`==
:::spoiler
`0xC4` is address of `mv s0, a0`. Add 4 for each instruction until you reach ret which is at `0xD8`.
:::

---

## Question `D`

The following functions are missing code to save/restore registers to/from the stack. Identify the registers that need to be saved to the stack at any point in the function. You do not need to provide the missing code. If the RISC-V calling convention does not require any registers to be saved to / restored from the stack, write `none`.

- [ ] Case `1`

# register save/restore code missing
func:
    beqz a0, done
    mv s0, a0
    addi a0, a0, -1
    jal func
    # use return value of func:
    add a0, s0, a0
done:
    ret

registers needing saving (or "none")?
> D01 = ==`s0, ra`==

- [ ] Case `2`

# register save/restore code missing
func:
    li t0, 0x5F3759DF
    xor t0, a0, t0
loop:
    beqz t0, end
    srli t0, t0, 1
    andi t0, t0, 0x1
    beqz t0, lsb_zero
    addi s0, s0, 1
    j loop
lsb_zero:
    addi s1, s1, 1
    j loop
end:
    ret

registers needing saving (or "none")?
> D02 = ==`s0, s1`==

---

## Question `E`

Below is the C code and translated RISC-V assembly.

int func(int m, int n)
{
    if (m == 0)
        return n + 1;
    if (n == 0) /* m_nonzero */
        return func(m - 1, 1);
    /* both_nonzero */
    return func(m - 1, func(m, n - 1));
}

- [ ] RISC-V Assembly (`X` is unknown.)

func:
    bnez a0, m_nonzero
    addi a0, a1, 1
    ret
m_nonzero:
    addi sp, sp, -X
    sw ra, 0(sp)
    bnez a1, both_nonzero
    addi a0, a0, -1
    li a1, 1
    call func
    lw ra, 0(sp)
    addi sp, sp, X
    ret
both_nonzero:
    sw a0, 4(sp)
    # inner call
    addi a1, a1, -1
    call func
    mv a1, a0
    lw a0, 4(sp)
    # outer call
    addi a0, a0, -1
    call func
    lw ra, 0(sp)
    addi sp, sp, X
    ret

What is the minimum value of `X`, the number of bytes needed on the stack?
> E01 = ==8==

---

## Question `F`

You are given the following C code along with an incomplete translation of this code into RISC-V assembly. Assume that execution ends when it reaches the `UNIMPL` instruction.

    int a[4] = {0x1, 0x2, 0x4, 0x8};
    int b = 0x5;
    int c = 0;
    for (int i = 3; i >= 0; i = i-1) {
        c = a[i] & b;
        if (c) break;
    }

- [ ] Translation into RISC-V assembly

. = 0x0
    li a0, 0x800 // starting address of array
    li a1, 0x5
    li a2, 0x3
loop:
    mv t0, a2
    __F01__
    add t0, a0, t0    # Value left in t0? __F02__
    lw t1, 0(t0)
    and t1, t1, a1
    bnez t1, end;    # Value left in t1? __F03__
    addi a2, a2, -1
    bgez a2, loop    # Value left in a2? __F04__
end:
    UNIMPL
   
. = 0x800 # contents of array a, where a[0] is at 0x800
.word 0x1
.word 0x2
.word 0x4
.word 0x8

> F01 = ==`slli t0, t0, 2`==

Provide the ==hex== values left in the registers below following the execution of the corrected code.
* Value left in t0?
> F02 = ==`0x808`==
* Value left in t1?
> F03 = ==`0x4`==
* Value left in a2?
> F04 = ==`0x2`==

---

## Question `G`

Consider the C procedure below and its translation to RISC-V assembly code, shown in the later.

int f(int a, int b)
{
    int c = b – a;
    if (c & G01 == 0) /* c is a multiple of 4 */
        return 1;
    int d = f(a – 1, b + 2);
    return 3 * (d + a);
}

- [ ] RISC-V Assembly (`G01` is unknown.)

f:  sub a2, a1, a0
    andi a2, a2, G01
    bnez a2, ELSE
    li a0, 1
    jr ra
ELSE:
    addi sp, sp, -8
    sw a0, 0(sp)
    sw ra, 4(sp)
    addi a0, a0, -1
    addi a1, a1, 2
    jal ra, f
A4: lw a1, 0(sp)
    lw ra, 4(sp)
L1: add a0, a0, a1
    slli a1, a0, 1
    add a0, a0, a1
    addi sp, sp, 8
    jr ra

1. What value should the `G01` term in the C code and the assembly be replaced with to make the if statement correctly check if the variable ‘c’ is a multiple of 4?
> G01 = ==`3`==
:::spoiler
AND with 0b11 (or 0x3 or just 3) to check if last 2 bits are 0, indicating a multiple of 4
:::

2. How many words will be written to the stack before the program makes each recursive call to the function f? That is, number of words pushed onto stack before each recursive call?
> G02 = ==`2`==