# Lab1: RV32I Simulator

## Add Digits([Leetcode.258 Add Digits](https://leetcode.com/problems/add-digits/))

- Problem's Description:
Given an integer num, repeatedly add all its digits until the result has only one digit, and return it.

>Example:
>Input:38
>Output:2
>Explanation: The process is
38 --> 3 + 8 --> 11
11 --> 1 + 1 --> 2
Since 2 has only one digit, return it.
## C

int addDigits(int num){
    int ans ;
	while (num >= 10) {
		ans = 0;
		while (num != 0) {
			ans = ans + (num % 10);
			num = num / 10;
		}
		num = ans;
	}
	return num;
}

## RISC-V Assembly code

.data
arg:  .word 38                    #You can change this arugment
str1: .string "The result is " 

.text
main: lw a0, arg
      mv a1,zero
      jal ra, Add_Digits

      #print
      la a0 ,str1
      li a7 ,4
      ecall
      mv a0 ,a1
      li a7 ,1
      ecall
      
      li a7,10
      ecall
exit:


Add_Digits: 
            mv t5, a0
            
    loop1:  slti t1, t5, 10 
            bne t1, zero, end2
            mv t4, zero
    loop2:  
            beq t5, zero, end1
            li t2,10
            rem t3, t5, t2
            add t4, t4, t3
            div t5, t5, t2 
            j loop2
    end1:   mv t5,t4
            j loop1
    end2:   mv a1, t5
            ret

### Result
##### when input is 38.

## Translated RISC-V code by Ripes

00000000 <main>:
	0:		10000517		auipc x10 0x10000
	4:		00052503		lw x10 0 x10
	8:		00000593		addi x11 x0 0
	c:		028000ef		jal x1 40 <exit>
	10:		10000517		auipc x10 0x10000
	14:		ff450513		addi x10 x10 -12
	18:		00400893		addi x17 x0 4
	1c:		00000073		ecall
	20:		00058513		addi x10 x11 0
	24:		00100893		addi x17 x0 1
	28:		00000073		ecall
	2c:		00a00893		addi x17 x0 10
	30:		00000073		ecall

00000034 <exit>:
	34:		00050f13		addi x30 x10 0

00000038 <loop1>:
	38:		00af2313		slti x6 x30 10
	3c:		02031463		bne x6 x0 40 <end2>
	40:		00000e93		addi x29 x0 0

00000044 <loop2>:
	44:		000f0c63		beq x30 x0 24 <end1>
	48:		00a00393		addi x7 x0 10
	4c:		027f6e33		rem x28 x30 x7
	50:		01ce8eb3		add x29 x29 x28
	54:		027f4f33		div x30 x30 x7
	58:		fedff06f		jal x0 -20 <loop2>

0000005c <end1>:
	5c:		000e8f13		addi x30 x29 0
	60:		fd9ff06f		jal x0 -40 <loop1>

00000064 <end2>:
	64:		000f0593		addi x11 x30 0
	68:		00008067		jalr x0 x1 0

The above RISC-V code is generated from Ripes. I observe some instructions I write are replaced to another instructions. By the way, the name of registers I named alse be change.
All changed instructions are belongs to pseudo instruction.For example," **mv** "," **la**","**li**",these pseudo instructions are not translated to machine code, so Ripes have to replace these instructions to the others it can execute.

## Analysis
#### Five stage explanation
**IF**: The address generated from PC is send to instruction memory to find instruction.
**ID**: The instruction's machine is decoded to some parts about opcode, register's number, funct3, funct7, immediate.
Control Unit will generate diffrant signals according to different instruction.
Then, the value of registers and immediate are send to next stage.
**EX**: ALU will process the data which are from ID stage or forwarding from MEM and WB stage. In addition, branch is decide to taken or not taken.
**MEM**: Read or Write the Data Memory if "MemWrite" or "MemRead" is set. Maybe some data is need to forward to EX stage.
**WB** : Make the result of ALU or data of Data Memory write back to register file. Maybe some data is need to forward to EX or MEM stage.

#### Hazard issue
There are three type of pipeline hazard that were Structure hazard, Data hazard and Control hazard. But, in this homework, I only encounter the Control Hazard.

For example:

We can see the first instruction "**beq x30 x0 24**". Condition branch of this instruction happans at 28th clock when condition is attained . Therefore, the next two instruction "**addi x7 x0 10**" and "**rem x28 x30 x7**" after "**beq x30 x0 24**" are flushed in the EX stage and ID stage respectively. About this case, I will show more detail below.

Besides, We also see the instructions displayed in the above image's bottom. "**addi x30 x29 0**" and "**jal x0 -40**" after "**jal x0 -20**" are also flushed in the earlier clock(26th clock).

#### Analysis about "beq" condition branch start at 26 th clock as example
**IF**
##### "beq x30 x0 24"
We can see this instruction's address is **0x00000044**.
"beq x30 x0 24" 's machine code is **0x000f0c63**.
The next instruction's address is **0x00000048**.

**ID**

"0x000f0c63" is decode to some parts.
* **opcode : beq**
* **rs1: 0x1e**
* **rs2: 0x00**
* **Imm: 0x00000018** (pc+Imm is next instruction's address if branch happens)
In the ID stage,We can see the rs1's register number and value .Then, rs2 is also like this.

**EX**

The rs1 register and the rs2 register are both **0x00000000**.
One of ALU'source is from this instruction's address,and the other is from Imm.
Because the two register's value is same, the condition of this branch is achieved.Thus,the result of alu will be the next instruction's address **(0x0000005c)**.
**Branch will be taken.**

**Mem**

Because Branch is taken. The instructions in ID and EX stage are both flushed.
At the same time, We can see the result generated from ALU in the last clock is the address of the instruction in the IF stage

**WB**

In the WB stage, because this is the "beq" instruction, it neither need to make ALU's result write back to register file nor send data of data memory to register.

## Reference
[risc-v-spec-v2.2](https://riscv.org/wp-content/uploads/2017/05/riscv-spec-v2.2.pdf)
[Ripes](https://github.com/mortbopet/Ripes)
[Hackmd](https://hackmd.io/s/features)