# Assignment1: RISC-V Assembly and Instruction Pipeline
contributed by < [`qoo332001`](https://github.com/qoo332001) >
###### tags: `RISC-V` `computer architure 2021`
## homework
[maxSubArray](https://leetcode.com/problems/maximum-subarray/submissions/)
### c code
```c
#include<stdio.h>
int maxSubArray(int* nums, int numsSize);
int main(){
int a[9]={-2,1,-3,4,-1,2,1,-5,4};
int len1=sizeof(a)/sizeof(int);
int best,i;
best=maxSubArray(a,len1);
printf("best= %d\n",best);
}
int maxSubArray(int* nums, int numsSize)
{
int i;
int best = 0x80000000;
int currsum = 0;
for (i = 0; i < numsSize; i++) {
if(currsum<0){
currsum =nums[i];
}else{
currsum = currsum + nums[i];
}
if(best<currsum)
best=currsum;
}
return best;
}
```
### assembly code
```c
.data
arr1: .word -2,1,-3,4,-1,2,1,-5,4
len1: .word 9
minint: .word 0x80000000
.text
# s1 = nums base address
# s2 = array1 length
# s3 = min_Integer
# t0=i
# t1=best
# t2=currsum
main:
la s1,arr1 #load array address to s1
lw s2,len1 #load array size to s2
lw s3,minint #load the smallest integer to s3
add a0,s1,zero #set parameter to a0
add a1,s2,zero #set parameter to a1
jal maxSubArray #and set ra=PC+4 and jump to labet "maxSubArray"
li a7, 1 # set system call number:print a0 register as integer
ecall
addi a0,zero,1
li a7, 10 # set system call number:end program
ecall
maxSubArray:
addi sp,sp,-20 #change stackpointer and push to stack to save main fucntion local variables
sw t0,16(sp) #push t0 register
sw t1,12(sp) #push t1 register
sw t2,8(sp) #push t2 register
sw t3,4(sp) #push t3 register
sw t4,0(sp) #push t4 register
add t0,zero,zero #i=0
add t1,s3,zero #best=min_Integer
add t2,zero,zero #currsum=0
loop:
slt t3,t0,a1 #if(i < numsSize) then t3=1
beq t3,zero,next #if(t3!=1) then break loop
slli t3,t0,2 #t3=i*4
add t4,s1,t3 #t4=nums[i] address
lw t4,0(t4) #t4=nums[i]
slt t3,t2,zero #if(currsum<0) then t3=1
bne t3,zero,L1 #if(t3!=0) then jump L1
add t2,t2,t4 #else currsum = currsum + nums[i];
j L2
L1:
add t2,t4,zero #currsum=nums[i]
L2:
slt t3,t1,t2 # if(best<currsum) then t3=1
beq t3,zero,L3 # if(t3==0) then jump L3
add t1,t2,zero # best=currsum
L3:
addi t0,t0,1 #i++
j loop
next:
add a0,zero,t1 #return best
lw t0,16(sp) #restore the saved register t0
lw t1,12(sp) #restore the saved register t1
lw t2,8(sp) #restore the saved register t2
lw t3,4(sp) #restore the saved register t3
lw t4,0(sp) #restore the saved register t4
addi sp,sp,20 #change stackpointer to finish stack pop
jr ra #jump to main functionc
```
:::warning
Can you use fewer instructions?
:notes: jserv
:::
## Analysis
### Pseudo Instructions
Ripe translated abi code to asm code:
```
00000000 <main>:
0: 10000497 auipc x9 0x10000
4: 00048493 addi x9 x9 0
8: 10000917 auipc x18 0x10000
c: 01c92903 lw x18 28 x18
10: 10000997 auipc x19 0x10000
14: 0189a983 lw x19 24 x19
18: 00048533 add x10 x9 x0
1c: 000905b3 add x11 x18 x0
20: 018000ef jal x1 24 <maxSubArray>
24: 00100893 addi x17 x0 1
28: 00000073 ecall
2c: 00100513 addi x10 x0 1
30: 00a00893 addi x17 x0 10
34: 00000073 ecall
00000038 <maxSubArray>:
38: fec10113 addi x2 x2 -20
3c: 00512023 sw x5 0 x2
40: 00612223 sw x6 4 x2
44: 00712423 sw x7 8 x2
48: 01c12623 sw x28 12 x2
4c: 01d12823 sw x29 16 x2
50: 000002b3 add x5 x0 x0
54: 00098333 add x6 x19 x0
58: 000003b3 add x7 x0 x0
0000005c <loop>:
5c: 00b2ae33 slt x28 x5 x11
60: 020e0c63 beq x28 x0 56 <next>
64: 00229e13 slli x28 x5 2
68: 01c48eb3 add x29 x9 x28
6c: 000eae83 lw x29 0 x29
70: 0003ae33 slt x28 x7 x0
74: 000e1663 bne x28 x0 12 <L1>
78: 01d383b3 add x7 x7 x29
7c: 0080006f jal x0 8 <L2>
00000080 <L1>:
80: 000e83b3 add x7 x29 x0
00000084 <L2>:
84: 00732e33 slt x28 x6 x7
88: 000e0463 beq x28 x0 8 <L3>
8c: 00038333 add x6 x7 x0
00000090 <L3>:
90: 00128293 addi x5 x5 1
94: fc9ff06f jal x0 -56 <loop>
00000098 <next>:
98: 00600533 add x10 x0 x6
9c: 00012283 lw x5 0 x2
a0: 00412303 lw x6 4 x2
a4: 00812383 lw x7 8 x2
a8: 00c12e03 lw x28 12 x2
ac: 01012e83 lw x29 16 x2
b0: 01410113 addi x2 x2 20
b4: 00008067 jalr x0 x1 0
```
### illustrate each stage in pipeline
* `IF`:fetch instruction from memory
* `ID`:decoder the instructions include opcode and operands.
* `EX`:perform the ALU calculation for result or effective address
* `MEM`:access memory if needed
* `WB`:write the result to destination register
### Control Hazards
after jal instruction there are two instruction has been loaded when a jump is detected,it will be flush loaded instruction and load new instruction after jump.
### Data Hazards
when next instruction's source register need to use the last instruction's destination source,it will happen Data Hazard.
two way to slove Data Hazard:
1. Data forwarding:forwarding data from stage MEM to EX
2. add two NOP instructions
data forwarding register x28 from stage MEM to EXE,for slove data hazard.
### local variables
To protect main function variables,it need to push all register you changed in callee to stack.
push to stack at the beginning of fuction:
```
38: fec10113 addi x2 x2 -20
3c: 00512023 sw x5 0 x2
40: 00612223 sw x6 4 x2
44: 00712423 sw x7 8 x2
48: 01c12623 sw x28 12 x2
4c: 01d12823 sw x29 16 x2
```
pop from stack at the end of fuction:
```
9c: 00012283 lw x5 0 x2
a0: 00412303 lw x6 4 x2
a4: 00812383 lw x7 8 x2
a8: 00c12e03 lw x28 12 x2
ac: 01012e83 lw x29 16 x2
b0: 01410113 addi x2 x2 20
```
register will not change after executing the function
before call function:
after execution function:
## Memory
* .data from 0x10000000 to 0x10000028
* .text from 0x00000000 to 0x000000bc
.
.
.
Sign in with Wallet
Connect another wallet