# Homework2: RISC-V Toolchain
## Bubble Sort
### Pick up a assembly program from Homework1
* choose bubble sort from [王傑世](https://hackmd.io/4-oWQOprRnCLu3ZeJy31kA?view).
### Rewrite the C code
```cpp=
void _start() {
int arr[5] = {2,3,7,4,1};
int i,j,temp;
for(i=0;i<4;i++){
for(j=0;j<4-i;j++){
if(arr[j]>arr[j+1]){
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
volatile char *tx = (volatile char *)0x40002000;
const char *result = "Sorted array from small to big: ";
while (*result){
*tx = *result;
result++;
}
for (int i = 0; i < 5; i++){
*tx = (char)((arr[i]+'0'));
*tx = ' ';
}
*tx = '\n';
}
```
:::spoiler ### Handwritten Assembly code from 王傑世
```cpp=
.data
arr: .word 2, 3, 7, 4, 1
.text
main:
la s0, arr
mv t3, s0
addi s1, s1, 4
addi t0, zero, -1
jal ra, bbsort
mv t0, zero
addi s1, s1, 1
mv s0, t3
j print
bbsort:
addi sp, sp, -12
sw ra, 8(sp)
sw s1, 4(sp)
sw s0, 0(sp)
oloop:
addi t0, t0, 1
mv t1, zero
sub t2, s1, t0
blt t0, s1, iloop
addi sp, sp, 12
jr ra
iloop:
mv s0, t3
bge t1, t2, oloop
slli t4, t1, 2
add s0, s0, t4
lw a2, 0(s0)
lw a3, 4(s0)
addi t1, t1, 1
blt a2, a3, swap
j iloop
swap:
sw a2, 4(s0)
sw a3, 0(s0)
j iloop
print:
bge t0, s1, end
lw a0, 0(s0)
li a7, 1
ecall
addi t0, t0, 1
addi s0, s0, 4
j print
end:
```
:::
:::spoiler ### Compiler optimized Assembly code by O3
```cpp=
BubbleSort: file format elf32-littleriscv
Disassembly of section .text:
00010054 <_start>:
10054: 000107b7 lui a5,0x10
10058: 20078793 addi a5,a5,512 # 10200 <_start+0x1ac>
1005c: 0007a703 lw a4,0(a5)
10060: 0047a683 lw a3,4(a5)
10064: 0087a583 lw a1,8(a5)
10068: 00c7a603 lw a2,12(a5)
1006c: 0107a783 lw a5,16(a5)
10070: fe010113 addi sp,sp,-32
10074: 00e12623 sw a4,12(sp)
10078: 00d12823 sw a3,16(sp)
1007c: 00b12a23 sw a1,20(sp)
10080: 00c12c23 sw a2,24(sp)
10084: 00f12e23 sw a5,28(sp)
10088: 00e6d663 bge a3,a4,10094 <_start+0x40>
1008c: 00d12623 sw a3,12(sp)
10090: 00e12823 sw a4,16(sp)
10094: 01012783 lw a5,16(sp)
10098: 01412703 lw a4,20(sp)
1009c: 00f75c63 bge a4,a5,100b4 <_start+0x60>
100a0: 00078693 mv a3,a5
100a4: 00e12823 sw a4,16(sp)
100a8: 00f12a23 sw a5,20(sp)
100ac: 00070793 mv a5,a4
100b0: 00068713 mv a4,a3
100b4: 01812603 lw a2,24(sp)
100b8: 00e65c63 bge a2,a4,100d0 <_start+0x7c>
100bc: 00070693 mv a3,a4
100c0: 00c12a23 sw a2,20(sp)
100c4: 00e12c23 sw a4,24(sp)
100c8: 00060713 mv a4,a2
100cc: 00068613 mv a2,a3
100d0: 01c12683 lw a3,28(sp)
100d4: 10c6ce63 blt a3,a2,101f0 <_start+0x19c>
100d8: 00c12683 lw a3,12(sp)
100dc: 00d7dc63 bge a5,a3,100f4 <_start+0xa0>
100e0: 00078593 mv a1,a5
100e4: 00f12623 sw a5,12(sp)
100e8: 00d12823 sw a3,16(sp)
100ec: 00068793 mv a5,a3
100f0: 00058693 mv a3,a1
100f4: 00f75c63 bge a4,a5,1010c <_start+0xb8>
100f8: 00078593 mv a1,a5
100fc: 00e12823 sw a4,16(sp)
10100: 00f12a23 sw a5,20(sp)
10104: 00070793 mv a5,a4
10108: 00058713 mv a4,a1
1010c: 0ce64a63 blt a2,a4,101e0 <_start+0x18c>
10110: 00d7dc63 bge a5,a3,10128 <_start+0xd4>
10114: 00078613 mv a2,a5
10118: 00f12623 sw a5,12(sp)
1011c: 00d12823 sw a3,16(sp)
10120: 00068793 mv a5,a3
10124: 00060693 mv a3,a2
10128: 0af74463 blt a4,a5,101d0 <_start+0x17c>
1012c: 00d7d663 bge a5,a3,10138 <_start+0xe4>
10130: 00f12623 sw a5,12(sp)
10134: 00d12823 sw a3,16(sp)
10138: 000107b7 lui a5,0x10
1013c: 21478793 addi a5,a5,532 # 10214 <_start+0x1c0>
10140: 05300713 li a4,83
10144: 400026b7 lui a3,0x40002
10148: 00e68023 sb a4,0(a3) # 40002000 <__global_pointer$+0x3fff05c8>
1014c: 00178793 addi a5,a5,1
10150: 0007c703 lbu a4,0(a5)
10154: fe071ae3 bnez a4,10148 <_start+0xf4>
10158: 00c12703 lw a4,12(sp)
1015c: 02000793 li a5,32
10160: 03070713 addi a4,a4,48
10164: 0ff77713 andi a4,a4,255
10168: 00e68023 sb a4,0(a3)
1016c: 00f68023 sb a5,0(a3)
10170: 01012703 lw a4,16(sp)
10174: 03070713 addi a4,a4,48
10178: 0ff77713 andi a4,a4,255
1017c: 00e68023 sb a4,0(a3)
10180: 00f68023 sb a5,0(a3)
10184: 01412703 lw a4,20(sp)
10188: 03070713 addi a4,a4,48
1018c: 0ff77713 andi a4,a4,255
10190: 00e68023 sb a4,0(a3)
10194: 00f68023 sb a5,0(a3)
10198: 01812703 lw a4,24(sp)
1019c: 03070713 addi a4,a4,48
101a0: 0ff77713 andi a4,a4,255
101a4: 00e68023 sb a4,0(a3)
101a8: 00f68023 sb a5,0(a3)
101ac: 01c12703 lw a4,28(sp)
101b0: 03070713 addi a4,a4,48
101b4: 0ff77713 andi a4,a4,255
101b8: 00e68023 sb a4,0(a3)
101bc: 00f68023 sb a5,0(a3)
101c0: 00a00793 li a5,10
101c4: 00f68023 sb a5,0(a3)
101c8: 02010113 addi sp,sp,32
101cc: 00008067 ret
101d0: 00f12a23 sw a5,20(sp)
101d4: 00e12823 sw a4,16(sp)
101d8: 00070793 mv a5,a4
101dc: f51ff06f j 1012c <_start+0xd8>
101e0: 00e12c23 sw a4,24(sp)
101e4: 00c12a23 sw a2,20(sp)
101e8: 00060713 mv a4,a2
101ec: f25ff06f j 10110 <_start+0xbc>
101f0: 00c12e23 sw a2,28(sp)
101f4: 00d12c23 sw a3,24(sp)
101f8: 00068613 mv a2,a3
101fc: eddff06f j 100d8 <_start+0x84>
```
:::
### Result by O3
```
./emu-rv32i BubbleSort
Sorted array from big to small: 1 2 3 4 7
>>> Execution time: 4003200 ns
>>> Instruction count: 210 (IPS=52458)
>>> Jumps: 43 (20.48%) - 8 forwards, 35 backwards
>>> Branching T=39 (92.86%) F=3 (7.14%)
```
:::spoiler ### Readelf by O3
```
ELF Header:
Magic: 7f 45 4c 46 01 01 01 00 00 00 00 00 00 00 00 00
Class: ELF32
Data: 2's complement, little endian
Version: 1 (current)
OS/ABI: UNIX - System V
ABI Version: 0
Type: EXEC (Executable file)
Machine: RISC-V
Version: 0x1
Entry point address: 0x10054
Start of program headers: 52 (bytes into file)
Start of section headers: 980 (bytes into file)
Flags: 0x0
Size of this header: 52 (bytes)
Size of program headers: 32 (bytes)
Number of program headers: 1
Size of section headers: 40 (bytes)
Number of section headers: 7
Section header string table index: 6
```
:::
Size by O3
```
text data bss dec hex filename
484 0 0 484 1e4 BubbleSort
```
Google Drive
Gist
Clipboard
Sign in with Wallet
