# Homework 2 - RISC-V Toolchain

###### tags: `Computer Architecture 2022`

## Pick up one problem
I choose the problem from [李協儒-Reverse Linked List (LeetCode 206)](https://hackmd.io/@DotandLog/BJcgekYzi#Reverse-Linked-List). The reason why I choose this probelm is that I want to learn how to use RISC-V implement Linked list. Because the last homework I choose is about array operation.

### Origin Solution

#include <stdio.h>
#include <stdlib.h>

typedef struct ListNode {
    int val;
    struct ListNode* next;
} * Node;

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* curr = head;
    struct ListNode* next = NULL;
    struct ListNode* prev = NULL;

    while (curr != NULL) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

Node initListNode(int input[], int size) {
    Node head = malloc(sizeof(Node));
    Node curr = head;
    head->val = input[0];

    for (int i = 1; i < size; i++) {
        Node newNode = malloc(sizeof(Node));
        newNode->val = input[i];
        curr->next = newNode;
        curr = newNode;
    }
    curr->next = NULL;
    return head;
}

void printNode(Node head, char InorOut) {
    Node curr = head;
    (InorOut == 'I') ? printf("Input:[") : printf("Output:[");
    while (curr) {
        printf("%d,", curr->val);
        curr = curr->next;
    }
    printf("]\n");
}

void freeNode(Node head) {
    while (head) {
        Node temp = head;
        head = head->next;
        free(temp);
    }
}

void runTest(Node head) {
    printNode(head, 'I');
    head = reverseList(head);
    printNode(head, 'O');
    freeNode(head);
}

int main() {
    Node head1, head2, head3;
    int test1[] = {1, 2, 3, 4, 5};
    int test2[] = {1, 2};
    int test3[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    head1 = initListNode(test1, 5);
    head2 = initListNode(test2, 2);
    head3 = initListNode(test3, 10);
    runTest(head1);
    runTest(head2);
    runTest(head3);
}    

### Origin Assembly

.data 
test1:.word 1, 2, 3, 4, 5
test2:.word 1, 2
test3:.word 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
start_input_line:.string "Input:["
start_output_line:.string "Output:["
endline:.string "]\n"

.text 
main:
    la a0, test1 # a0 = test1[0]
    addi a1, a1, 5 # a1 = test1_sizes

    jal ra, initListNode
    jal ra, runTest

    la a0, test2 # a0 = test2[0]
    addi a1, a1, 2 # a1 = test2_sizes

    jal ra, initListNode
    jal ra, runTest

    la a0, test3 # a0 = test3[0]
    addi a1, a1, 10 # a1 = test3_sizes

    jal ra, initListNode
    jal ra, runTest

    j exit
initListNode:
    addi sp, sp, -8
    sw ra, 0(sp)

    addi t0, a1, 0
    mv t1, a0
    lw t2, 0(t1) # load test[0]'s value
    li s0, 0x20000000 # s0 save the address of Node
    sw s0, 4(s0) # load the list head to the stack

    jal ra node_alloc # alloc memory for  node
    sw t3, s0 # Node curr = head
    sw t2, 0(s0) # head->val = test[0]
    
    addi s0, s0, 8 #offset to next arry
    li s1, 1 # set i = 1

loop:
    jal ra node_alloc # Node newNode = malloc

    addi t1, t1, 4 # find the next value in test by 4(int)
    lw t2, 0(t1) # load test[i+1]
    sw t2, 0(s0) # newNode->val = test[i]

    sw s0, 4(t3) # curr->next = newNode
    addi s0, s0, 8 
    addi t3, t3, 8 
    addi s1, 1 # i++
    
    bne s1,t0 loop # for statement

    addi s0, s0, 4
    sw x0, 4(t3)

    lw ra, 0(sp)
    lw a0, 4(sp)
    addi sp, sp, 8

    jr ra
runTest:
    la a0, start_input_line 
    li a7, 4
    ecall

    jal ra printNode

    jal ra reverseNode

    la a0, end_input_line
    li a7, 4
    ecall

    jal ra printNode

    jal ra freeNode

    jr ra
printNode:
    lw a0, 0(t1)
    li a7, 1
    ecall

    li a0, 9
    li a7, 11
    ecall

    lw t1,4(t1)

    bne t1, x0 printNode

    li a0, 10
    li a7, 11
    ecall

    ja ra

reverseNode:
     lw a0, 0(a0)
    beqz a0, done
    addi t0, t0, 0
loop2:
    lw t1, 0(a0)
    sw t0, 0(a0)
    addi t0, a0, 0
    addi a0, t1, 0
    bnez t1,loop2
done:
    jr ra
freeNode:
node_alloc:
    li a7, 214
    ecall 
    jr ra
exit:
    li a7, 10
    ecall      

### Modified C code
When I compile C code to elf file, I find some warning and error that I can't compile the C code. This problem happened when I choose optimized level O2, O3, Ofast and Os (O0 and O1 are fine).

Homework2/HW2.c: In function 'initListNode':
Homework2/HW2.c:26:9: warning: array subscript 'struct ListNode[0]' is partly outside array bounds of 'unsigned char[4]' [-Warray-bounds]
   26 |     head->val = input[0];
      |         ^~
Homework2/HW2.c:24:17: note: object of size 4 allocated by 'malloc'
   24 |     Node head = malloc(sizeof(Node));
      |                 ^~~~~~~~~~~~~~~~~~~~
Homework2/HW2.c:34:9: warning: array subscript 'struct ListNode[0]' is partly outside array bounds of 'struct ListNode[0]' [-Warray-bounds]
   34 |     curr->next = NULL;
      |         ^~
Homework2/HW2.c:24:17: note: object of size 4 allocated by 'malloc'
   24 |     Node head = malloc(sizeof(Node));
      |                 ^~~~~~~~~~~~~~~~~~~~
Homework2/HW2.c:29:24: note: object of size 4 allocated by 'malloc'
   29 |         Node newNode = malloc(sizeof(Node));
      |                        ^~~~~~~~~~~~~~~~~~~~
Homework2/HW2.c:30:16: warning: array subscript 'struct ListNode[0]' is partly outside array bounds of 'unsigned char[4]' [-Warray-bounds]
   30 |         newNode->val = input[i];
      |                ^~
Homework2/HW2.c:29:24: note: object of size 4 allocated by 'malloc'
   29 |         Node newNode = malloc(sizeof(Node));
      |                        ^~~~~~~~~~~~~~~~~~~~
Homework2/HW2.c:31:13: warning: array subscript 'struct ListNode[0]' is partly outside array bounds of 'struct ListNode[0]' [-Warray-bounds]
   31 |         curr->next = newNode;
      |             ^~
Homework2/HW2.c:24:17: note: object of size 4 allocated by 'malloc'
   24 |     Node head = malloc(sizeof(Node));
      |                 ^~~~~~~~~~~~~~~~~~~~
Homework2/HW2.c:29:24: note: object of size 4 allocated by 'malloc'
   29 |         Node newNode = malloc(sizeof(Node));
      |        

Then I find the origin code malloc the size of `Node`. `Node` is the pointer point to `ListNode` which is just four bytes. `ListNode` need to malloc 8 bytes.

I modify `malloc(sizeof(Node))` to `malloc(sizeof(struct ListNode))` than O2, O3, Ofast, Os optimized level can run without probelm.

#include <stdio.h>
#include <stdlib.h>

typedef struct ListNode {
    int val;
    struct ListNode* next;
} * Node;

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* curr = head;
    struct ListNode* next = NULL;
    struct ListNode* prev = NULL;
    
    while (curr != NULL) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

Node initListNode(int input[], int size) {
-   Node head = malloc(sizeof(Node));
+   Node head = malloc(sizeof(struct ListNode));
    Node curr = head;
    head->val = input[0];

    for (int i = 1; i < size; i++) {
-       Node newNode = malloc(sizeof(Node));
+       Node newNode = malloc(sizeof(struct ListNode));
        newNode->val = input[i];
        curr->next = newNode;
        curr = newNode;
    }
    curr->next = NULL;
    return head;
}

void printNode(Node head, char InorOut) {
    Node curr = head;
    (InorOut == 'I') ? printf("Input:[") : printf("Output:[");
    while (curr) {
        printf("%d,", curr->val);
        curr = curr->next;
    }
    printf("]\n");
}

void freeNode(Node head) {
    while (head) {
        Node temp = head;
        head = head->next;
        free(temp);
    }
}

void runTest(Node head) {
    printNode(head, 'I');
    head = reverseList(head);
    printNode(head, 'O');
    freeNode(head);
}

int main() {
    Node head1, head2, head3;
    int test1[] = {1, 2, 3, 4, 5};
    int test2[] = {1, 2};
    int test3[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    head1 = initListNode(test1, 5);
    runTest(head1);
    head2 = initListNode(test2, 2);
    runTest(head2);
    head3 = initListNode(test3, 10);
    runTest(head3);
}    

### Modified Assembly

When I put these code into Ripes, it can't run successful. I try to debug these code.

:::info
**line 12 18 24 :** I use `lw a1, len` to replace `addi a1,a1,5` because a1 will be plus many time, a1 will be incorrect num

**line 38 :** I use `sw s0, 4(sp)` to replace `sw s0, 4(s0)`, s0 need to save in stack

**line 41 :** I use `mv t3, s0` to replace `sw t3, s0`, this is the grammar error

**line 57 :** I use `addi s1, s1, 1` to replace `addi s1, 1`, this is the grammar error

**runTest :** Because this program does not save any ra register, it can't return to main function. Need to save ra register to stack and load ra before return to main. And I add some code to obey calling convention.

**reverseNode :** In `line 111` and `112`, need to load and save the address of a0 plus four, because a0 is point to the value in linked list and a0+4 is the address point to next node.
:::

And I modify some code to make sure this program can execute by RV32emu

:::info
1. `jal ra label` need to revise to `jal ra, label`
2. `bne t1, s0 label` need to revise to `bne t1, s0, label`
:::

The following program has been modified.

# RISC-V assembly program to print "Hello World!" to stdout.

.org 0
# Provide program starting address to linker
.global _start
/* newlib system calls */
.set SYSEXIT,  93
.set SYSWRITE, 64

.data 
test1:.word 1, 2, 3, 4, 5
len1: .word 5
test2:.word 1, 2
len2: .word 2
test3:.word 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
len3: .word 10
start_input_line:.string "Input:["
start_output_line:.string "Output:["
endline:.string "]\n"

.text 

main: 
    la a0, test1        # a0 = test1[0]
-   addi a1, a1, 5
+   lw a1, len1         # a1 = len(test1)

    jal ra, initListNode
    jal ra, runTest

    la a0, test2        # a0 = test2[0]
-   addi a1, a1, 2
+   lw a1, len2

    jal ra, initListNode
    jal ra, runTest

    la a0, test3 # a0 = test3[0]
-   addi a1, a1, 10
+   lw a1, len3

    jal ra, initListNode
    jal ra, runTest

    j exit
    
initListNode:
    addi sp, sp, -8
    sw ra, 0(sp)

    mv t0, a1          # t0 is the size of linked list
    mv t1, a0          # t1 is the address of array
    lw t2, 0(t1)       # load test[0]'s value
    li s0, 0x20000000  # s0 save the address of Node
-   sw s0, 4(s0)
+   sw s0, 4(sp)       # load the list head to the stack #

    jal ra, node_alloc  # alloc memory for node
-   sw t3, s0
+   mv t3, s0          # Node curr = head #
    sw t2, 0(s0)       # head->val = test[0]
    
    addi s0, s0, 8     # offset to next array (8 is the ListNode size)
    li s1, 1           # set i = 1

loop:
    jal ra, node_alloc  # Node newNode = malloc

    addi t1, t1, 4     # find the next value in test by 4(int)
    lw t2, 0(t1)       # load test[i+1]
    sw t2, 0(s0)       # newNode->val = test[i]

    sw s0, 4(t3)       # curr->next = newNode
    addi s0, s0, 8     # To get the next 
    addi t3, t3, 8 
-   addi s1, 1
+   addi s1,s1, 1      # i++
    
    bne s1,t0, loop     # for statement

    addi s0, s0, 4
    sw x0, 4(t3)

    lw ra, 0(sp)
    lw a0, 4(sp)
    addi sp, sp, 8

    jr ra
    
runTest:
+   addi sp, sp, -8
+   sw ra,0(sp)
+   sw a0,4(sp)
    
    la a0, start_input_line 
    li a7, 4
    ecall
    
+   lw t1,4(sp)
    jal ra, printNode
+   lw a0,4(sp)
    jal ra, reverseNode
+   sw a0,4(sp)                # save the new head to stack
    la a0, start_output_line
    li a7, 4
    ecall
    
+   lw t1,4(sp)
    jal ra, printNode

    jal ra, freeNode
    
+   lw ra,0(sp)
+   addi sp, sp, 8
    jr ra
    
printNode:
    lw a0, 0(t1)
    li a7, 1
    ecall

    li a0, 9
    li a7, 11
    ecall

    lw t1,4(t1)

    bne t1, x0, printNode

    li a0, 10
    li a7, 11
    ecall

    jr ra
    
- reverseNode:
-     lw a0, 0(a0)
-     beqz a0, done
-     addi t0, t0, 0
- loop2:
-     lw t1, 0(a0)
-     sw t0, 0(a0)
-     addi t0, a0, 0
-     addi a0, t1, 0
-     bnez t1,loop2
- done:
-     jr ra
    
+ reverseNode:
+     mv t1,a0        # t1 is curr
+     beqz a0, done
+     addi t4,x0,0
+ loop2:
+     lw t2,4(t1)     # t2 is next
+     sw t4,4(t1)
+     mv t4,t1        # t4 is prev
+     mv t1,t2
+     bnez t1,loop2
+ done:
+     mv a0,t4        # return prev
+     jr ra

freeNode:
node_alloc:
    li a7, 214
    ecall 
    jr ra
exit:
    li a7, 10
    ecall   

## Disassemble the ELF files and Analysis

if we want to translate C to executable file, we need to use the following command. We can change "-O0" to -O0, -O1, -O2, -O3, -Ofast, -Os. They are different optimized level.

riscv-none-elf-gcc -Wall -march=rv32i -mabi=ilp32 -O0 HW2.c -o HW2.elf

This command can know the size of elf file.

riscv-none-elf-size HW2.elf

And I use this command to output .elf to .txt.

riscv-none-elf-objdump -d HW2.elf > HW2.txt

The assembly code is long . We focus on the main section of the code to better demonstrate the effect of compiler optimization.

### Handwrite Assembly code

reverseNode:
    mv t1,a0        # t1 is curr
    beqz a0, done
    addi t4,x0,0
loop2:
    lw t2,4(t1)     # t2 is next
    sw t4,4(t1)
    mv t4,t1        # t4 is prev
    mv t1,t2
    bnez t1,loop2
done:
    mv a0,t4        # return prev
    jr ra

**Observation**
- LOC: 10
- Rigister used
- S register: none
- A register: a0
- T register: t1,t2,t4
- Other: none
- Total: 4
- Stack used: 0 bytes
- Number of load/save: 2
- Branch Number: 2

### O0

00010184 <reverseList>:
   10184:	fd010113          	addi	sp,sp,-48
   10188:	02812623          	sw	s0,44(sp)
   1018c:	03010413          	addi	s0,sp,48
   10190:	fca42e23          	sw	a0,-36(s0)
   10194:	fdc42783          	lw	a5,-36(s0)
   10198:	fef42623          	sw	a5,-20(s0)
   1019c:	fe042223          	sw	zero,-28(s0)
   101a0:	fe042423          	sw	zero,-24(s0)
   101a4:	02c0006f          	j	101d0 <reverseList+0x4c>
   101a8:	fec42783          	lw	a5,-20(s0)
   101ac:	0047a783          	lw	a5,4(a5)
   101b0:	fef42223          	sw	a5,-28(s0)
   101b4:	fec42783          	lw	a5,-20(s0)
   101b8:	fe842703          	lw	a4,-24(s0)
   101bc:	00e7a223          	sw	a4,4(a5)
   101c0:	fec42783          	lw	a5,-20(s0)
   101c4:	fef42423          	sw	a5,-24(s0)
   101c8:	fe442783          	lw	a5,-28(s0)
   101cc:	fef42623          	sw	a5,-20(s0)
   101d0:	fec42783          	lw	a5,-20(s0)
   101d4:	fc079ae3          	bnez	a5,101a8 <reverseList+0x24>
   101d8:	fe842783          	lw	a5,-24(s0)
   101dc:	00078513          	mv	a0,a5
   101e0:	02c12403          	lw	s0,44(sp)
   101e4:	03010113          	addi	sp,sp,48
   101e8:	00008067          	ret

**size**

   text	   data	    bss	    dec	    hex	filename
  75816	   2816	    812	  79444	  13654	Homework2/HW2_O0.elf

**CSR cycle**

**Observation**
- LOC: 27
- Rigister used
- S register: s0
- A register: a0,a4,a5
- T register: none
- Other: sp
- Total: 4
- Stack used: 48 bytes
- Number of load/save: 19
- Branch Number: 1

**Explanation Code**
- Before jump into `reverselist`, `a0` and `s0` is save the address of linked list head.
- `line2` allocate 48 bytes memory in stack.
- `line3` save `s0` which is equal `a0` in stack
- `line4` replace `s0` into the address which is point to the stack position that has not yet entered the label
- `line5` and `line6` are equal to `mv t1, a0` and save data to save to `-36(s0)`, which is equal to save to `12(sp)`
- `line7` save data to `-20(s0)`. `-36(s0)` and `44(sp)` is also save the same data (`line3` and `line5` do this).
- `line8` and `line9` save `zero` to `-28(s0)` and `-24(s0)`. I think allocate these spaces to zero is that I have declared two pointer point to NULL.
- `line10` jump to `line21` and load `-20(s0)` into `a5` ( `-20(s0)` have been saved in `a5`, so `line10` mean `mv a5,a5` )
- `line22` is judge that if a5 is not equal zero, jump to `line11`
- `line11` is equal `line21`, which mean `mv a5,a5`
- `line12` load `a5->next` in `a5`.
- `line13` save `a5->next` in `-28(s0)`. I thick `-28(s0)` save `next` in C code.
- `line14` load `curr` in `a5`.
- `line15` load zero in `a4`.
- `line16` load `a5->next` in `a4`.
- `line17` and `line18` load `curr` in `a5` (same as `line14`) and save to `-24(s0)`. I thick `-24(s0)` save `prev` in C code.
- `line19` load `curr->next` in `a5` and `line20` save `curr->next` in `-20(s0)`. I think `-20(s0)` save `curr` in C code.
- `line21` load `next` in `curr`

**Conculsion**

I think use `O0` optimized level will get lots of redundant code. It save the same value in different space in stack. There is a very different way from others. That is if we want to do like `mv a0, a5`, it usually save `a5` to stack and load the same memory to `a0`. It will be two instruction to finish `mv a0,a5`. I think this is the reason why it will generate more than handwrite assembly code.

### O1

00010184 <reverseList>:
   10184:	02050063          	beqz	a0,101a4 <reverseList+0x20>
   10188:	00000713          	li	a4,0
   1018c:	0080006f          	j	10194 <reverseList+0x10>
   10190:	00078513          	mv	a0,a5
   10194:	00452783          	lw	a5,4(a0)
   10198:	00e52223          	sw	a4,4(a0)
   1019c:	00050713          	mv	a4,a0
   101a0:	fe0798e3          	bnez	a5,10190 <reverseList+0xc>
   101a4:	00008067          	ret

**Size**

   text	   data	    bss	    dec	    hex	filename
  75544	   2816	    812	  79172	  13544	Homework2/HW2_O1.elf

**CSR cycle**

**Observation**
- LOC: 10
- Rigister used
- S register: none
- A register: a0, a4, a5
- T register: none
- Other: none
- Total: 3
- Stack used: 0 bytes
- Number of load/save: 3
- Branch Number: 2

### O2

00010264 <reverseList>:
   10264:	02050063          	beqz	a0,10284 <reverseList+0x20>
   10268:	00000713          	li	a4,0
   1026c:	0080006f          	j	10274 <reverseList+0x10>
   10270:	00078513          	mv	a0,a5
   10274:	00452783          	lw	a5,4(a0)
   10278:	00e52223          	sw	a4,4(a0)
   1027c:	00050713          	mv	a4,a0
   10280:	fe0798e3          	bnez	a5,10270 <reverseList+0xc>
   10284:	00008067          	ret

**Size**

   text	   data	    bss	    dec	    hex	filename
  75748	   2816	    812	  79376	  13610	Homework2/HW2_O2.elf

**CSR cycle**

**Observation**
- LOC: 10
- Rigister used
- S register: none
- A register: a0, a4, a5
- T register: none
- Other: none
- Total: 3
- Stack used: 0 bytes
- Number of load/save: 3
- Branch Number: 2

### O3

00010264 <reverseList>:
   10264:	02050063          	beqz	a0,10284 <reverseList+0x20>
   10268:	00000713          	li	a4,0
   1026c:	0080006f          	j	10274 <reverseList+0x10>
   10270:	00078513          	mv	a0,a5
   10274:	00452783          	lw	a5,4(a0)
   10278:	00e52223          	sw	a4,4(a0)
   1027c:	00050713          	mv	a4,a0
   10280:	fe0798e3          	bnez	a5,10270 <reverseList+0xc>
   10284:	00008067          	ret

**size**

   text	   data	    bss	    dec	    hex	filename
  75748	   2816	    812	  79376	  13610	Homework2/HW2_O3.elf

**CSR cycle**

**Observation**
- LOC: 10
- Rigister used
- S register: none
- A register: a0, a4, a5
- T register: none
- Other: none
- Total: 3
- Stack used: 0 bytes
- Number of load/save: 3
- Branch Number: 2

### Ofast

00010264 <reverseList>:
   10264:	02050063          	beqz	a0,10284 <reverseList+0x20>
   10268:	00000713          	li	a4,0
   1026c:	0080006f          	j	10274 <reverseList+0x10>
   10270:	00078513          	mv	a0,a5
   10274:	00452783          	lw	a5,4(a0)
   10278:	00e52223          	sw	a4,4(a0)
   1027c:	00050713          	mv	a4,a0
   10280:	fe0798e3          	bnez	a5,10270 <reverseList+0xc>
   10284:	00008067          	ret

**size**

   text	   data	    bss	    dec	    hex	filename
  75748	   2816	    812	  79376	  13610	Homework2/HW2_Ofast.elf

**CSR cycle**

**Observation**
- LOC: 10
- Rigister used
- S register: none
- A register: a0, a4, a5
- T register: none
- Other: none
- Total: 3
- Stack used: 0 bytes
- Number of load/save: 3
- Branch Number: 2

**Explanation**

We can see that use optimized level O1, O2, O3, Ofast will get the same code in this function.

- `a0` is the head of linkedist.
- `line2` judge if `a0` equal zero, return the function.
- `line3` initialize `a4` to be zero.
- `line4` jump to `line6` .
- `line6` load `curr->next` in `a5`. I thick `a5` is `next` in C code.
- `line7` save `a4` to `4(a0)` . I thick `4(a0)` store `curr->next` in C code and `a4` is `prev`.
- `line8` mean `prev = curr` in C code.
- `line9` jump to `line5` if `a5` is not zero.
- `line5` mean `curr = next`
- if the loop end, it will not jump to `line5`. It mean that `prev = curr` and we need to return `prev`. `a0` is just equal to `a4` and return `prev`.

**Conclusion**
I thick use `O1`, `O2`, `O3`, `Ofast` level to optimize can generate less code than O0.

### Os

0001020c <reverseList>:
   1020c:	00050793          	mv	a5,a0
   10210:	00000513          	li	a0,0
   10214:	00079463          	bnez	a5,1021c <reverseList+0x10>
   10218:	00008067          	ret
   1021c:	0047a703          	lw	a4,4(a5)
   10220:	00a7a223          	sw	a0,4(a5)
   10224:	00078513          	mv	a0,a5
   10228:	00070793          	mv	a5,a4
   1022c:	fe9ff06f          	j	10214 <reverseList+0x8>

**size**

   text	   data	    bss	    dec	    hex	filename
  75460	   2816	    812	  79088	  134f0	Homework2/HW2_Os.elf

**Observation**
- LOC: 10
- Rigister used
- S register: none
- A register: a0, a4, a5
- T register: none
- Other: none
- Total: 3
- Stack used: 0 bytes
- Number of load/save: 3
- Branch Number: 1

**CSR cycle**

**Explanation**
- `a0` is the head fo linkedlist
- `line2` mean `curr = head` in C code. I thick `a5` is `curr` in C code.
- `line3` initialize `a0` to zero.
- `line4` judge if `a5` not equal to zero, jump to `line6`. if `a5` equal to zero, return the function
- `line6` load `curr->next` to `a4`. I think `a4` is `next` in C code.
- `line7` save `a0` in `curr->next`
- `line8` mean `prev = curr` in C code. I think in this loop `a0` is `prev`.
- `line9` mean `curr = next` in C code.
- `line10` jump to `line4`

**Conclusion**
I thick use `Os` optimized level can get the nearest handwrite assembly code and there is no redundant code. The sequence of code is also the nearest handwrite assembly code. This level is also the shost code.

## Check the results and optimize the code
After the above results, we can compare CSR cycle between each optimized level.

| Optimized level | O0 | O1 | O2 | O3 | Ofast | Os|
| -------- | -------- | -------- | -------- | -------- | -------- |-------- |
| CSR cycle | 26905 | 26187 |26122|26122|26122|26280|

But these CSR cycle is the whole program CSR cycle, we want to compare the main function in this program. I try to delete `printNode` function and calculate CSR cycle before enter `reverseList` and after enter `reverseList`. Subtract two results to get the `reverseList` CSR cycle.

| Optimized level | Before enter the function | After enter the function | reverseList CSR cycle|
| -------- | -------- | -------- |-------- |
| O0 | 1175 | 1291 |116|
| O1 | 1033 | 1081 |48|
| O2 | 1043 | 1083 |40|
| O3 | 1043 | 1083 |40|
| Ofast | 1043 | 1083 |40|
| Os | 1147 | 1181 |34|
| handwrite (by ripes) | 234 | 312 | 78 |

I think the function `initListNode` implementation is different between C code and Assembly (EX: malloc). It make them have different CSR cycle.

I also think that if the pipeline of rv32emu and ripes are different. It make them have different CSR cycle.

### Try to optimize
Modiavte by `Os`, I simplify a reigster and an instruction.

**Origin assembly**

reverseNode:
    mv t1,a0        # t1 is curr
    beqz a0, done
    addi t4,x0,0
loop2:
    lw t2,4(t1)     # t2 is next
    sw t4,4(t1)
    mv t4,t1        # t4 is prev
    mv t1,t2
    bnez t1,loop2
done:
    mv a0,t4        # return prev
    jr ra

CSR cycle : 312 (by ripes)

**Observation**
- LOC: 13
- Rigister used
- S register: none
- A register: a0
- T register: t1, t2, t4
- Other: none
- Total: 4
- Stack used: 0 bytes
- Number of load/save: 2
- Branch Number: 2

**Modify assembly**

reverseNode:
    mv t1,a0        # t1 is curr
    beqz a0, done
    addi a0,x0,0
loop2:
    lw t2,4(t1)     # t2 is next
    sw a0,4(t1)
    mv a0,t1 
    mv t1,t2
    bnez t1,loop2
done:
    jr ra

CSR cycle : 311 (ripes)

**Observation**
- LOC: 12
- Rigister used
- S register: none
- A register: a0
- T register: t1, t2
- Other: none
- Total: 3
- Stack used: 0 bytes
- Number of load/save: 2
- Branch Number: 2