---
tags: Computer Architecture 2022
---
# Lab1 RV32I
## Move Zeroes
This problem is based on leetcode problem 283. Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements.
## Assembly Code

main:
    li s0 0                    #array base addr
    addi s1 x0 5               #array_size = 5
    
    #start filling up array [1,0,0,2,5]
    li t0 1
    sw t0 0(s0)
    li t0 0
    sw t0 4(s0)
    sw t0 8(s0)
    li t0 2
    sw t0 12(s0)
    li t0 5
    sw t0 16(s0)
    
    
    #call function moveZeroes
    jal t6 moveZeroes
    
    #Print Result Array
    #li     a0, 0                # return 0
    lw a0 0(s0)                  # print s[0]
    jal printInt
    lw a0 4(s0)                  # print s[1]
    jal printInt
    lw a0 8(s0)                  # print s[2]
    jal printInt
    lw a0 12(s0)                  # print s[3]
    jal printInt
    lw a0 16(s0)                  # print s[4]
    jal printInt
    li     a7, 10                # Exit code
    ecall
moveZeroes:
    li s2 0 #next non zero index
    addi s3 x0 -1 # i = -1
    addi t1 x0 0
    loop:
        addi s3 s3 1             #i++
        bge s3 s1 exit           #i >= array_size exit
        slli t1 s3 2             #i*4
        add t1 s0 t1             #array + i*4
        lw t3 0(t1)              #t3 = array[i]
        beq t3 x0 loop
        slli t2 s2 2             #next_nonzero_index * 4
        add t2 t2 s0             #array + next_nonzero_index * 4
        sw t3 0(t2)              #array[next_nonzero_index] = array[i]
        beq s2 s3 do             #if(next_nonzero_index != i)
        sw x0 0(t1)              #store 0 to array[i]
    do:
        addi s2 s2 1             #next_nonzero_index++
        j loop
 
 exit:
    jr t6

printInt:
    li a7, 1
    ecall
    jr ra

:::warning
:warning: Can you use fewer instructions?
:notes: jserv
:::
## Edit

.data
nums1:
    .word 1
    .word 0
    .word 0
    .word 2
    .word 5
    
nums2:
    .word 1
    .word 9
    .word 0
    .word 6
    .word 7

nums3:
    .word 0
    .word 0
    .word 0
    .word 0
    .word 4

.text
main:
    la s0 nums1                 # load nums base address to s0
    addi s1 x0 5               #nums_size = 5
    
    #call function moveZeroes
    add a0 s0 x0            # a0 which stands for address of nums array is the first argument
    add a1 s1 x0            # a1 which stands for array size of nums is the second argument
    jal ra moveZeroes        #jump to moveZeroes function
    
    #PrintArray
    jal ra printArray
    li a7 10
    ecall
    
moveZeroes:
    addi sp sp -12
    sw ra 0(sp)
    sw s0 4(sp)
    sw s1 8(sp)
    li s1 0                    #next non zero index = 0
    addi s2 x0 0                 # i = 0
    loop:
        bge s2 a1 exit           #i >= array_size exit
        slli t0 s2 2             #i * 4
        add t0 a0 t0             #array + i*4
        lw t1 0(t0)              #t1 = array[i]
        beq t1 x0 next_iter
        slli t2 s1 2             #next_nonzero_index * 4
        add t2 t2 a0             #array + next_nonzero_index * 4
        sw t1 0(t2)              #array[next_nonzero_index] = array[i]
        beq s1 s2 next_iter_addIndex             #if(next_nonzero_index != i)
        sw x0 0(t0)              #store 0 to array[i]
    next_iter_addIndex:
        addi s1 s1 1             #next_nonzero_index++
    next_iter:
        addi s2 s2 1             #i++
        j loop
 exit:
    lw ra 0(sp)
    lw s0 4(sp)
    lw s1 8(sp)
    addi sp sp 12
    jr ra
 
printArray:
    li a7 1
    addi sp sp -8
    sw ra 0(sp)
    sw s0 4(sp)
    add s0 a0 x0 # s1 = pointer to array
    add t0 x0 x0 # t0 = i in for loop
    printloop:
        bge t0 a1 finish_print_loop
        slli t1 t0 2 # t1 = i * 4
        add t1 t1 s0 # t1 = t1 + array address
        lw a0 0(t1) # a0 = element in nums[i]
        li a7 1
        ecall
        addi t0 t0 1
        j printloop
    finish_print_loop:
        lw ra 0(sp)
        lw s0 4(sp)
        addi sp sp 8
        jr ra

## Analysis
### Jump and Link
(image from : https://inst.eecs.berkeley.edu/~cs61c/resources/su18_lec/Lecture7.pdf)
jal is an UJ-format instruction. It saves PC+4 in register rd (the return address), then set PC to PC+offset. Target somewhere within +-$2^{19}$ locations.
In my code, "jal ra moveZeroes" instruction store PC+4 to ra register, and jump to label "moveZeroes". The point is jal instruction won't know where to jump until it moves on to EX stage. Control Hazard occurs, so the next two instructions will be flush.
### Data Hazard
Here is a read after write(RAW) situation happened. In pipeline, we only get data from memory at MEM stage. The two instructions after lw will stall for a cycle(do same thing again) to ensure that it gets the right data from register.