# Assignment1: RISC-V Assembly and Instruction Pipeline
contributed by < [`anfong-query`](https://github.com/anfong-query) >

###### tags: `RISC-V`, `jserv`

[toc]

## Leetcode268 - [Missing Number](https://leetcode.com/problems/missing-number)

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

### Example 1
>**Input**: nums = [3,0,1]
**Output**: 2
**Explanation**: n = 3 since there are 3 numbers, so all numbers are in the range $[0,3]$. 2 is the missing number in the range since it does not appear in nums.

### Example 2
>**Input**: nums = [0,1]
**Output**: 2
**Explanation**: n = 2 since there are 2 numbers, so all numbers are in the range $[0,2]$. 2 is the missing number in the range since it does not appear in nums.

## Implementation
Since the size of the array must be one less than the given array. Thus, we can easily add up the index value of the array while subtracting the value at the index of the array to obtain the "missing number".

Moreover you can find the source code [here](https://github.com/anfong-query/Leetcode268-missing_number). Feel free to fork and modify it.

### C code

I use an array of length 3 to implement the above method. You can change the length or elements to see whether the result is still correct.

#include <stdio.h>

int missingNumber(int* nums, int numsSize){
	int sum = numsSize;
	for(int i = 0; i < numsSize; i++){
		sum += i;
		sum -= nums[i];
	}
	return sum;
}

int main(){
	int nums[] = {3,0,1};
	printf("%d\n", missingNumber(nums,3));
	return 0;
}

:::info
Think of the following:

int missingNumber(int* nums, int numsSize)
{
    int res = 0;
    for (int i = 0; i < numsSize; ++i)
        res += nums[i];
    return numsSize * (numsSize + 1) / 2 - res;
}

Then, optimize the RISC-V code.

:notes: jserv
:::

:::info
Using Trapezoidal formula to calculate the sum of the array is an effective way to reducing the number of instructions in each loop.

I will rewrite my RISC-V code at the bottom of this page.
Thanks jserv for the suggestion. :+1:

AnfongLee
:::

### Assembly code

.data
arr: .word 3, 0, 1
len: .word 3
str: .string "The missing number is "

.text
# s1 = arr base address
# t0 = i
# t1 = nums[i]
# s2 = sum
# s3 = numsSize

main:
    la s1, arr        # s1 = pointer to nums[0]
    lw s2, len        # s2 = sum
    lw s3, len        # s3 = numsSize
    add t0, x0, x0    # i = 0
    jal ra, loop      # jump to foor loop
    jal ra, print     # jump to foor loop
    li a7, 10         # end program
    ecall
        
loop:
    add s2, s2, t0    # sum += i
    lw t1, 0(s1)      # t1 = nums[i]
    addi s1, s1, 4    # nums++ (address move forward)
    sub s2, s2, t1    # sum -= nums[i]
    addi t0, t0, 1    # i++
    blt t0, s3, loop  # if i < array length
    jr ra             # else, return to main

print:
    la a0, str        # load string
    li a7, 4          # print string
    ecall
    add a0, s2, x0    # load result
    li a7, 1          # print integer
    ecall
    jr ra             # go back to main

## How to use
You can change the arr content and its responding size to find the missing number.
Then, check the result in the console.


## Result
We can check the result of example1 in the console


## Analysis

We test our code using [Ripes](https://github.com/mortbopet/Ripes) simulator.

### Pseudo instruction

Ripes change register name from ABI name to sequencial one.
The translated code looks like:

00000000 <main>:
	0:	10000497	auipc x9 0x10000
	4:	00048493	addi x9 x9 0
	8:	10000917	auipc x18 0x10000
	c:	00492903	lw x18 4 x18
	10:	10000997	auipc x19 0x10000
	14:	ffc9a983	lw x19 -4 x19
	18:	000002b3	add x5 x0 x0
	1c:	010000ef	jal x1 16 <loop>
	20:	028000ef	jal x1 40 <print>
	24:	00a00893	addi x17 x0 10
	28:	00000073	ecall

0000002c <loop>:
	2c:	00590933	add x18 x18 x5
	30:	0004a303	lw x6 0 x9
	34:	00448493	addi x9 x9 4
	38:	40690933	sub x18 x18 x6
	3c:	00128293	addi x5 x5 1
	40:	ff32c6e3	blt x5 x19 -20 <loop>
	44:	00008067	jalr x0 x1 0

00000048 <print>:
	48:	10000517	auipc x10 0x10000
	4c:	fc850513	addi x10 x10 -56
	50:	00400893	addi x17 x0 4
	54:	00000073	ecall
	58:	00090533	add x10 x18 x0
	5c:	00100893	addi x17 x0 1
	60:	00000073	ecall
	64:	00008067	jalr x0 x1 0

### Ripes simulator

The ripes simulator provides a 5-stages processor as bellow.


The "5-stage" means this processor using five-stage pipeline to parallelize instructions. Each rectangle between every stages represent the "pipeline register". The stages are:

1. **Instruction fetch (IF)**
+ Fetch the instruction
+ Update program counter
+ Sequential code, Branch and jump
2. **Instruction decode and register fetch (ID)**
+ Decode the instruction
+ Get the value from register
3. **Excute (EX)**
+ ALU operations
4. **Memory access (MEM)**
+ Read the data from the data memory
+ Store the data to the data memory
7. **Register write back (WB)**
+ Write the data back to the register

### Pipeline Hazard
>**Definition:** The pipeline hazard refers to the situation where the pipeline cannot execute the next command in the next clock.

Pipeline Hazard has classified into three types of bellow categories:

1. **Data Hazard:** Data hazards occur when instructions that exhibit data dependence modify data in different stages of a pipeline.
2. **Control Hazard:** Control hazard occurs when the pipeline makes wrong decisions on branch prediction and therefore brings instructions into the pipeline that must subsequently be discarded.
3. **Structure Hazard:** Structural hazard occurs when two (or more) instructions that are already in pipeline need the same resource.

It is easy to find pipeline hazards during the execution of the bellow assembly code.

#### Control Hazzard

>+ As shown in the assembly code below, the jump and link(jal) instruction should jump to <loop>, but it will not execute the instruction until the EX state, so two clock cycles are wasted.
>
>
>
>
>+ RISC-V takes two clock cycles to flush the wrong instruction.
>
>
>
>
>
>**Solution of Control Hazard**
>- Branch Prediction
> + Static prediction: Always jump or not.
> + Dynamic prediction: Check the state last time to determine the state of this time.
>
>
>

## 10/29 Rewrite the RISC-V code

.data
arr: .word 3, 0, 1
len: .word 3
str: .string "The missing number is "

.text
# s1 = arr base address
# s2 = res
# s3 = numsSize
# s4 = ans
# t0 = i
# t1 = nums[i]

main:
    la s1, arr        # s1 = pointer to nums[0]
    add s2, x0, x0    # s2 = res
    lw s3, len        # s3 = numsSize
    add t0, x0, x0    # i = 0
    jal ra, loop      # jump to foor loop
    addi t2, s3, 1    # numsSize += 1
    mul t3, t2, s3    # numsSize * (numsSize + 1)
    srai t3, t3, 1    # devide by 2
    sub s4, t3, s2    # -res
    jal ra, print     # jump to foor loop
    li a7, 10         # end program
    ecall
        
loop:
    lw t1, 0(s1)      # t1 = nums[i]
    addi s1, s1, 4    # nums++ (address move forward)
    add s2, s2, t1    # res += nums[i]
    addi t0, t0, 1    # i++
    blt t0, s3, loop  # if i < array length
    jr ra             # else, return to main

print:
    la a0, str        # load string
    li a7, 4          # print string
    ecall
    add a0, s4, x0    # load result
    li a7, 1          # print integer
    ecall
    jr ra             # go back to main

## Reference
* [RISC-V instruction intro](https://ithelp.ithome.com.tw/articles/10194907)
* [The RISC-V Instruction Set Manual: Volume I: Unprivileged ISA](https://riscv.org/wp-content/uploads/2019/06/riscv-spec.pdf)
* [Hazard (computer architecture)](https://en.wikipedia.org/wiki/Hazard_(computer_architecture)#Types)