# Assignment2: GNU Toolchain
contributed by <[`shhung`](https://github.com/shhung/Image-scaling-with-Bilinear-interpolation-by-float32-multiplication)>
## Motivation
The work I selected is the [Image scaling with Bilinear interpolation](https://github.com/linyu425/ComputerArchitecture/tree/main/hw1) done by [linyu0425](https://hackmd.io/@linyu0425/SJHkb8lWT).
Due to the interesting work, I selected the work for my assignment 2. In addition, I want to review more floating-point processing that has been implemented in the work, such as addition and multiplication.
## Make C program be executed with rv32emu
Compiling C program is quite easy by gcc for risc-v.
```shell
$ riscv-none-elf-gcc -march=rv32i -mabi=ilp32 -o ImgScale ImgScale.S
$ rv32emu ImgScale
```
## Make assembly program be executed with rv32emu
By referencing [asm-hello](https://github.com/sysprog21/rv32emu/tree/master/tests/asm-hello) which is the demo in rv32emu for [System calls](https://github.com/sysprog21/rv32emu/blob/master/docs/syscall.md), we could have a `Makefile` and linker script for ours project.
### Modification
All that needs to be done is modifying the syscall part in the original program, as Ripes has its own design for syscalls.
In order to focus on the performance of the process logic, I deleted the part that outputs to the console.
### Optimization method
Since this work implements multiple sub-functions used for image scaling, I have split it into several parts. Due to this process, we can analyze each unit of image scaling and find out the parts to be optimized.
The function structure is shown in the figure below, and the performance of each part will be discussed later.
```
─── ImgScale
├── count_leading_zeros
├── imul32
├── fmul32
└── fadd32
```
### Bug
During testing the parts of the whole program, I found that the functions `imul32` and `fmul32` have a bit of error, and this error occurs in both the C and assembly programs.
Additionally, the `imul32` returns a 32-bit signed integer, which could lead to overflow. The same problem occurs in `fmul32` as well. Even so, there is no problem with the overall logic, so optimization will still be done based on the buggy program.
## Execute the program
The workable code is available at [src](https://github.com/shhung/Image-scaling-with-Bilinear-interpolation-by-float32-multiplication/tree/main/src), and the Makefile is provided to generate ELF file which is runable on the rv32emu.
1. Buile the ELF file
Following the command, you will get `main.elf` and `ImgScaleFromC.elf`.
```shell
$ make
```
2. Run each of it
Make sure you have already installed `rv32emu` and set the path for `rv32emu`. If not, check the [Lab2: RISC-V RV32I[MACF] emulator with ELF support](https://hackmd.io/@sysprog/SJAR5XMmi) to setup your environment.
```shell
$ rv32emu main.elf
```
```shell
$ rv32emu ImgScaleFromC.elf
```
Expected output:
For `main.elf` and `ImgScaleFromC.elf`, the output would only differ at elapsed cycle.
```shell
0.954780 0.877887 0.800995 0.724102 0.647210
0.921899 0.826679 0.731460 0.636240 0.541020
0.889018 0.775471 0.661924 0.548377 0.434830
0.856138 0.724263 0.592389 0.460514 0.328640
0.823257 0.673055 0.522853 0.372652 0.222450
elapsed cycle: 39580
inferior exit code 0
```
## Contrast the handwritten and compiler-optimized assembly code
By following the example of [ticks.c](https://github.com/sysprog21/rv32emu/blob/master/tests/ticks.c), we can evaluate our work by accumulating cycle count.
| | Handwritten | O0 | O1 | O2 | O3 | Os | Ofast |
| ----- | ----------- | ----- | ----- | ----- | ----- | ----- | ----- |
| Size | 56998 | 83940 | 82384 | 82364 | 83244 | 82364 | 83244 |
| Cycle | 39610 | 39065 | 16162 | 16459 | 12183 | 17012 | 12183 |
It can be obviously observed that the cycle count has a significant improvement when compiler optimization is applied. However, the size is not affected much.
Below, we will describe the difference between the assembly code generated by the compiler and the handwritten assembly code. The complete code is accessible at [shhung](https://github.com/shhung/Image-scaling-with-Bilinear-interpolation-by-float32-multiplication/tree/main/src/disasm).
### count_leading_zeros
Since `count_leading_zeros` is already simplified, there is almost nothing to be optimized. The only thing that can be optimized is omitting store/load operations by replacing callee-saved registers with caller-saved registers.
### imul32
By replacing callee-saved registers with caller-saved registers, store/load operations are not required in `imul32`.
### fadd32
Since `count_leading_zeros` is only used once in `fadd32`, `-O2` optimization and further levels replace the function call to `count_leading_zeros` in `fadd32` with directly writing the operation logic in fadd32.
### fmul32
Same as `imul32`, `-O1` optimization generated code uses fewer callee-saved registers. This operation results in fewer load/store instructions.
For `-O2` optimization and further levels, the function is branchless, and store/load operations are not required due to replacing callee-saved registers with caller-saved registers.
### Difference
Based on the above observation results, it can be found that the purpose and method of optimization are very similar, so we only list the differences between handwritten and compiler-optimized code for `fadd32`.
It can be obviously found that there are no store/load operations at the prologue/epilogue of the compiler-optimized code. Additionally, please check line 30 of the compiler-optimized code. Comparing it with the handwritten code, you will find that `count_leading_zeros` is executed here. By embedding it directly into `fadd32`, you can reduce the possible delays caused by function calls.
Handwritten:
```c
fadd32:
addi sp , sp , -52
sw s0 , 0(sp)
sw s1 , 4(sp)
sw s2 , 8(sp)
sw s3 , 12(sp)
sw s4 , 16(sp)
sw s5 , 20(sp)
sw s6 , 24(sp)
sw s7 , 28(sp)
sw s8 , 32(sp)
sw s9 , 36(sp)
sw s10 , 40(sp)
sw s11 , 44(sp)
sw ra , 48(sp)
mv s0 , a0
mv s1 , a1
li t0 , 0x7fffffff
and t1 , s0 , t0
and t2 , s1 , t0
blt t2 , t1 , noswap
mv t0 , s0
mv s0 , s1
mv s1 , t0
noswap:
li t0 , 31
srl s2 , s0 , t0
srl s3 , s1 , t0
li t0 , 0x7fffff
li t1 , 0x800000
and t2 , s0 , t0
or s4 , t2 , t1
and t2 , s1 , t0
or s5 , t2 , t1
li t0 , 23
li t1 , 0xff
srl t2 , s0 , t0
and s6 , t2 , t1
srl t2 , s1 , t0
and s7 , t2 , t1
sub t0 , s6 , s7
li t1 , 24
blt t1 , t0 , setalign_1
mv s8 , t0
j setalign_exit
setalign_1:
mv s8 , t1
setalign_exit:
srl s5 , s5 ,s8
or t0 , s2 , s3
bne t0 , x0 , setma_1
add s4 , s4 , s5
j setma_exit
setma_1:
sub s4 , s4 , s5
setma_exit:
mv a0 , s4
call count_leading_zeros
mv s9 , a0
mv s10 , x0
li t0 , 8
blt t0 , s9 , shift_false
li t0 , 8
sub s10 , t0 , s9
srl s4 , s4 , s10
add s6 , s6 , s10
j shift_exit
shift_false:
li t0 , 8
sub s10 , s9 , t0
sll s4 , s4 , s10
sub s6 , s6 , s10
shift_exit:
li t0 , 0x80000000
and t0 , s0 , t0
li t1 , 23
sll t1 , s6 , t1
li t2 , 0x7fffff
and t2 , s4 , t2
or t0 , t0 , t1
or a0 , t0 , t2
lw s0 , 0(sp)
lw s1 , 4(sp)
lw s2 , 8(sp)
lw s3 , 12(sp)
lw s4 , 16(sp)
lw s5 , 20(sp)
lw s6 , 24(sp)
lw s7 , 28(sp)
lw s8 , 32(sp)
lw s9 , 36(sp)
lw s10 , 40(sp)
lw s11 , 44(sp)
lw ra , 48(sp)
addi sp , sp , 52
ret
count_leading_zeros:
addi sp , sp , -8
sw s0 , 0(sp)
sw ra , 4(sp)
mv s0 , a0 # s0 = x
srli t0 , s0 , 1
or s0 , s0 ,t0
srli t0 , s0 , 2
or s0 , s0 ,t0
srli t0 , s0 , 4
or s0 , s0 ,t0
srli t0 , s0 , 8
or s0 , s0 ,t0
srli t0 , s0 , 16
or s0 , s0 ,t0
srli t0 , s0 , 1
li t1 , 0x55555555
and t0 , t0 , t1
sub s0 , s0 , t0
li t1 , 0x33333333
and t2 , s0 , t1
srli t0 , s0 , 2
li t1 , 0x33333333
and t0 , t0 , t1
add s0 , t0 , t2
srli t0 , s0 , 4
add t0 , t0 , s0
li t1 , 0x0f0f0f0f
and s0 , t0 , t1
srli t0 , s0 , 8
add s0 , s0 , t0
srli t0 , s0 , 16
add s0 , s0 , t0
li t0 , 32
andi t1 , s0 , 0x7f
sub a0 , t0 , t1
lw s0 , 0(sp)
lw ra , 4(sp)
addi sp , sp , 8
ret
```
Compiler-optimized:
```c
00010830 <fadd32>:
10830: 800007b7 lui a5,0x80000
10834: fff78793 add a5,a5,-1 # 7fffffff <__BSS_END__+0x7ffdb0db>
10838: 00a7f733 and a4,a5,a0
1083c: 00b7f7b3 and a5,a5,a1
10840: 00050813 mv a6,a0
10844: 00058613 mv a2,a1
10848: 00f74663 blt a4,a5,10854 <fadd32+0x24>
1084c: 00050613 mv a2,a0
10850: 00058813 mv a6,a1
10854: 00800537 lui a0,0x800
10858: 41765693 sra a3,a2,0x17
1085c: 41785793 sra a5,a6,0x17
10860: fff50713 add a4,a0,-1 # 7fffff <__BSS_END__+0x7db0db>
10864: 0ff6f693 zext.b a3,a3
10868: 0ff7f793 zext.b a5,a5
1086c: 00e675b3 and a1,a2,a4
10870: 40f687b3 sub a5,a3,a5
10874: 00e87733 and a4,a6,a4
10878: 01800893 li a7,24
1087c: 00a5e5b3 or a1,a1,a0
10880: 00a76733 or a4,a4,a0
10884: 00f8d463 bge a7,a5,1088c <fadd32+0x5c>
10888: 01800793 li a5,24
1088c: 40f757b3 sra a5,a4,a5
10890: 01066833 or a6,a2,a6
10894: 00f58733 add a4,a1,a5
10898: 00085463 bgez a6,108a0 <fadd32+0x70>
1089c: 40f58733 sub a4,a1,a5
108a0: 00175793 srl a5,a4,0x1
108a4: 00e7e7b3 or a5,a5,a4
108a8: 0027d593 srl a1,a5,0x2
108ac: 00b7e7b3 or a5,a5,a1
108b0: 0047d593 srl a1,a5,0x4
108b4: 00b7e7b3 or a5,a5,a1
108b8: 0087d593 srl a1,a5,0x8
108bc: 00b7e7b3 or a5,a5,a1
108c0: 0107d593 srl a1,a5,0x10
108c4: 00b7e7b3 or a5,a5,a1
108c8: 55555537 lui a0,0x55555
108cc: 0017d593 srl a1,a5,0x1
108d0: 55550513 add a0,a0,1365 # 55555555 <__BSS_END__+0x55530631>
108d4: 00a5f5b3 and a1,a1,a0
108d8: 40b787b3 sub a5,a5,a1
108dc: 33333537 lui a0,0x33333
108e0: 33350513 add a0,a0,819 # 33333333 <__BSS_END__+0x3330e40f>
108e4: 0027d593 srl a1,a5,0x2
108e8: 00a5f5b3 and a1,a1,a0
108ec: 00a7f7b3 and a5,a5,a0
108f0: 00f585b3 add a1,a1,a5
108f4: 0045d793 srl a5,a1,0x4
108f8: 0f0f1537 lui a0,0xf0f1
108fc: 00b787b3 add a5,a5,a1
10900: f0f50513 add a0,a0,-241 # f0f0f0f <__BSS_END__+0xf0cbfeb>
10904: 00a7f7b3 and a5,a5,a0
10908: 0087d593 srl a1,a5,0x8
1090c: 00b787b3 add a5,a5,a1
10910: 0107d593 srl a1,a5,0x10
10914: 00b787b3 add a5,a5,a1
10918: 07f7f793 and a5,a5,127
1091c: 02000593 li a1,32
10920: 40f585b3 sub a1,a1,a5
10924: 00800513 li a0,8
10928: 02b54863 blt a0,a1,10958 <fadd32+0x128>
1092c: fe878793 add a5,a5,-24
10930: 40f75733 sra a4,a4,a5
10934: 00f686b3 add a3,a3,a5
10938: 00971713 sll a4,a4,0x9
1093c: 01769693 sll a3,a3,0x17
10940: 800007b7 lui a5,0x80000
10944: 00975713 srl a4,a4,0x9
10948: 00d76733 or a4,a4,a3
1094c: 00f67533 and a0,a2,a5
10950: 00a76533 or a0,a4,a0
10954: 00008067 ret
10958: 01800593 li a1,24
1095c: 40f587b3 sub a5,a1,a5
10960: 00f71733 sll a4,a4,a5
10964: 40f686b3 sub a3,a3,a5
10968: 00971713 sll a4,a4,0x9
1096c: 01769693 sll a3,a3,0x17
10970: 800007b7 lui a5,0x80000
10974: 00975713 srl a4,a4,0x9
10978: 00d76733 or a4,a4,a3
1097c: 00f67533 and a0,a2,a5
10980: 00a76533 or a0,a4,a0
10984: 00008067 ret
```
### Cycle count for each part
| | count_leading_zeros | imul32 | fadd32 | fmul32 |
| ----- | --- | ------ | ------ | ------ |
| O0 | 81 | 105 | 191 | 284 |
| O1 | 11 | 67 | 106 | 197 |
| O2 | 11 | 11 | 107 | 195 |
| O3 | 0 | 0 | 103 | 191 |
| Os | 11 | 68 | 107 | 209 |
| Ofast | 0 | 0 | 103 | 191 |
### Summary
Through the process of reviewing optimized assembly code, I found some rules for writing efficient assembly code:
1. Fewer store/load operations are better for callable functions.
2. Rearrange instructions to reduce unnecessary conditional branches.
By following these rules when writing assembly code, you can create a relatively clear and efficient program. This will make it more convenient to carry out subsequent optimizations based on this foundation.
Sign in with Wallet
Connect another wallet