# Assignment2: Bare-Metal Programing
## Lab2: RISC-V Instruction Set Simulator and System Emulator
contributed by < [hbshub](https://github.com/hbshub/ca2025-hw2) >
>[!Note] AI tools usage
>I use ChatGPT by providing code explanations, grammar revisions, pre-work research, code summaries.
According to the instruction in [Lab2](https://hackmd.io/@sysprog/Sko2Ja5pel), I build the rv32emu simulator and set the system emulation enabled. Ensure `tests/system/playground` is fully verified.
In this lab，I learn how to run program in bare-metal environment.
In the playground directory has some files.
```
start.S - Startup code with BSS initialization
linker.ld - Arrange entry point .text .data .bss .stack in memory
perfcounter.S - CSR access routines
Makefile -
```
`start.S` file
1. set up `sp` (stack pointer)
2. clear `bss` (block started by symbol) section, which holds uninitialized `global` variables
3. zero `bss` loop, writing zero to every word, ensuring all C global variables start at 0.
4. call `main` transfer control to C program, handle C return and exit executes `ecall`
```asm=
# Startup code for bare metal RISC-V
.section .text._start
.globl _start
.type _start, @function
_start:
# Set up stack pointer
la sp, __stack_top
# Clear BSS
la t0, __bss_start
la t1, __bss_end
1:
bge t0, t1, 2f
sw zero, 0(t0)
addi t0, t0, 4
j 1b
2:
# Call main
call main
# Exit syscall (if main returns)
li a7, 93 # exit syscall number
li a0, 0 # exit code
ecall
# Infinite loop (should never reach here)
3:
j 3b
.size _start, .-_start
# Provide BSS markers if linker script doesn't define them
.weak __bss_start
.weak __bss_end
.weak __stack_top
```
`linker.ld`
1. Sets the output architecture to riscv and the program entry point to _start.
2. The program is set to start at memory address 0x10000
3. `Code Section (.text)` : Places the _start function's code first, followed by all other program code.
4. `Data Section (.data)` : Groups all initialized global variables.
5. `BSS Section (.bss)` : Defines symbols __bss_start and __bss_end which are used by start.S to know which memory region to clear (zero-out).
6. `Stack Section (.stack)` : Reserves 4096 bytes of memory for the stack and defines the __stack_top symbol, which start.S uses to initialize the stack pointer (sp).
```asm=
OUTPUT_ARCH( "riscv" )
ENTRY(_start)
SECTIONS
{
. = 0x10000;
.text : {
*(.text._start)
*(.text)
}
.data : { *(.data) }
.bss : {
__bss_start = .;
*(.bss)
__bss_end = .;
}
.stack (NOLOAD) : {
. = ALIGN(16);
. += 4096;
__stack_top = .;
}
}
```
`perfCounter.S`
1. Provides functions to safely read 64-bit performance counters (cycle and instret) on a 32-bit RISC-V system.
2. The code uses a "read-high, read-low, read-high-again" loop.
3. The function returns the consistent 64-bit value in the a1:a0 register pair, as per the 32-bit ABI.
```asm=
# Performance counter functions for RISC-V
# Read 64-bit cycle counter
.text
.globl get_cycles
.align 2
get_cycles:
csrr a1, cycleh
csrr a0, cycle
csrr a2, cycleh
bne a1, a2, get_cycles
ret
.size get_cycles,.-get_cycles
# Read 64-bit instruction retired counter
.globl get_instret
.align 2
get_instret:
csrr a1, instreth
csrr a0, instret
csrr a2, instreth
bne a1, a2, get_instret
ret
.size get_instret,.-get_instret
```
`Makefile`
1. Builds the test.elf executable from C and Assembly sources and provides `.PHONY` target to execute it in the rv32emu emulator.
2. `run`、`clean`、`dump` target is auxiliary commands.
3. Contains the rules for compilation, assembly, and linking.
```bash=
RV32EMU_PATH = /home/beta10/riscv-none-elf-gcc/rv32emu
include $(RV32EMU_PATH)/mk/toolchain.mk
ARCH = -march=rv32izicsr
LINKER_SCRIPT = linker.ld
EMU ?= $(RV32EMU_PATH)/build/rv32emu
AFLAGS = -g $(ARCH)
CFLAGS = -g -march=rv32i_zicsr
LDFLAGS = -T $(LINKER_SCRIPT)
EXEC = test.elf
CC = $(CROSS_COMPILE)gcc
AS = $(CROSS_COMPILE)as
LD = $(CROSS_COMPILE)ld
OBJDUMP = $(CROSS_COMPILE)objdump
OBJS = start.o main.o perfcounter.o q1-uf8.o
.PHONY: all run dump clean
all: $(EXEC)
$(EXEC): $(OBJS) $(LINKER_SCRIPT)
$(LD) $(LDFLAGS) -o $@ $(OBJS)
%.o: %.S
$(AS) $(AFLAGS) $< -o $@
%.o: %.c
$(CC) $(CFLAGS) $< -o $@ -c
run: $(EXEC)
@test -f $(EMU) || (echo "Error: $(EMU) not found" && exit 1)
@grep -q "ENABLE_ELF_LOADER=1" $(RV32EMU_PATH)/build/.config || (echo "Error: ENABLE_ELF_LOADER=1 not set" && exit 1)
@grep -q "ENABLE_SYSTEM=1" $(RV32EMU_PATH)/build/.config || (echo "Error: ENABLE_SYSTEM=1 not set" && exit 1)
$(EMU) $<
dump: $(EXEC)
$(OBJDUMP) -Ds $< | less
clean:
rm -f $(EXEC) $(OBJS)
```
## Programs run in Bare-Metal
## Quiz1 Problem B [link](https://hackmd.io/@sysprog/arch2025-quiz1-sol)
:::spoiler asm code
```asm=
.data
str1: .string ": produces value "
.equ str1_len, . - str1 - 1
str2: .string " but encodes back to "
.equ str2_len, . - str2 - 1
str3: .string ": value "
.equ str3_len, . - str3 - 1
str4: .string " <= previous_value "
.equ str4_len, . - str4 - 1
str5: .string "\n"
.equ str5_len, . - str5 - 1
str6: .string "All tests passed\n"
.equ str6_len, . - str6 - 1
.text
.globl run_q1_uf8 # Declare global symbol
.extern print_dec # Declare external C function
run_q1_uf8:
# ABI: Allocate 32 bytes (16-byte aligned) for 6 registers
addi sp, sp, -32
sw ra, 28(sp) # Save ra (return address to C)
sw s0, 24(sp) # Save s0
sw s1, 20(sp) # Save s1
sw s2, 16(sp) # Save s2
sw s3, 12(sp) # Save s3
sw s5, 8(sp) # Save s5
li s0, 0 # s0 = i / fl (0..255)
li s1, -1 # s1 = previous_value
li s2, 256 # s2 = remaining count
li s3, 1 # s3 = passed (1=ok, 0=fail)
li s5, 15 # s5 = cmp value
jal test # run test
bne a0, x0, print_suc_msg
main_c:
# ABI: Restore all saved registers
lw ra, 28(sp)
lw s0, 24(sp)
lw s1, 20(sp)
lw s2, 16(sp)
lw s3, 12(sp)
lw s5, 8(sp)
addi sp, sp, 32 # Restore stack
ret
# round-trip test
test:
# ABI: 'test' is a callee, must save callee-saved registers (s4)
addi sp, sp, -16 # 16-byte align
sw ra, 12(sp) # Save ra
sw s4, 8(sp) # Save s4
loop:
beqz s2, test_end
andi a0, s0, 255 # load fl = (uint8_t)i
# --- INLINED uf8_decode ---
# This replaces 'jal uf8_decode' to save cycles
srli t0, a0, 4
andi a0, a0, 0x0F
addi a0, a0, 16
sll a0, a0, t0
addi a0, a0, -16
# --- End Inlined uf8_decode ---
addi s4, a0, 0 # s4 = value = uf8_decode(fl)
jal uf8_encode # Call optimized uf8_encode
andi a0, a0, 255
bne s0, a0, set_fail # fl != fl2 ? fail
check_mono_inc:
blt s1, s4, ok # previous_value < value ? ok
li s3, 0 # passed = 0
li t3, 1 # for debug
jal print_fail_msg
ok:
addi s1, s4, 0 # previous_value = value
addi s0, s0, 1 # i++
addi s2, s2, -1 # remaining--
j loop
set_fail:
li s3, 0 # passed = 0
li t3, 0 # for debug
mv t4, a0 # t4 = fl2
jal print_fail_msg
j check_mono_inc
test_end:
addi a0, s3, 0 # a0 = return value (1=pass, 0=fail)
lw ra, 12(sp) # Restore ra
lw s4, 8(sp) # Restore s4
addi sp, sp, 16 # Restore sp
ret
# ------------------------------------------------------------
# Note: uf8_decode function was removed and inlined into 'test'
# ------------------------------------------------------------
uf8_encode:
li t3, 16
bge a0, t3, e_not_zero
ret
e_not_zero:
# We must save 'ra' because we 'jal clz'.
# We use 't4' to save 'a0', avoiding sw/lw for it.
addi sp, sp, -16
sw ra, 12(sp)
mv t4, a0
jal ra, clz
li t3, 31
sub t0, t3, a0
mv a0, t4
lw ra, 12(sp)
addi sp, sp, 16
li t1, 0
li t2, 0
li t3, 5
blt t0, t3, find_exa_exp
addi t1, t0, -4
# Replaced O(n) loop with O(1) formula & removed s5 dependency.
sltiu t3, t1, 16
beqz t3, set_exp_15 # if (t1 >= 16), set exp = 15
j build_of_once
set_exp_15:
li t1, 15
build_of_once:
# Build 'of' using O(1) formula: of = ((1<<exp) - 1) << 4
li t2, 1
sll t2, t2, t1
addi t2, t2, -1
slli t2, t2, 4
j adj_exp
adj_exp:
ble t1, x0, find_exa_exp
bge a0, t2, find_exa_exp
addi t2, t2, -16
srli t2, t2, 1
addi t1, t1, -1
j adj_exp
find_exa_exp:
bge t1, s5, calc_m
slli t0, t2, 1
addi t0, t0, 16
blt a0, t0, calc_m
mv t2, t0
addi t1, t1, 1
j find_exa_exp
calc_m:
sub t0, a0, t2
srl t0, t0, t1
ble t0, s5, cmb_num
li t0, 15
cmb_num:
slli t1, t1, 4
or a0, t1, t0
ret
# ------------------------------------------------------------
# clz(x) for RV32I, binary-search unrolled (shift-only)
# ------------------------------------------------------------
clz:
beq a0, x0, clz_zero # Handle special case: x == 0
li t0, 0 # n = 0 (leading zero count)
# 1. Check top 16 bits (bits 31-16)
srli t1, a0, 16
bnez t1, check_8_bits
addi t0, t0, 16
slli a0, a0, 16
check_8_bits:
# 2. Check top 8 bits (bits 23-16 of original, now 31-24)
srli t1, a0, 24
bnez t1, check_4_bits
addi t0, t0, 8
slli a0, a0, 8
check_4_bits:
# 3. Check top 4 bits (bits 27-24 of original, now 31-28)
srli t1, a0, 28
bnez t1, check_2_bits
addi t0, t0, 4
slli a0, a0, 4
check_2_bits:
# 4. Check top 2 bits (bits 29-28 of original, now 31-30)
srli t1, a0, 30
bnez t1, check_1_bit
addi t0, t0, 2
slli a0, a0, 2
check_1_bit:
# 5. Check top 1 bit (bit 30 of original, now 31)
srli t1, a0, 31
bnez t1, clz_finish
addi t0, t0, 1
clz_finish:
mv a0, t0
ret
clz_zero:
li a0, 32
ret
# --- End clz function ---
# ------------------------------------------------------------
# --- Helper Functions ---
# ------------------------------------------------------------
# Helper: printstr_asm(a0 = string_addr, a1 = string_len)
# Uses ecall 64 (sys_write)
printstr_asm:
mv t1, a0
mv t2, a1
li a7, 64
li a0, 1
mv a1, t1
mv a2, t2
ecall
ret
# Helper: void print_fail_msg(void)
print_fail_msg:
# ABI: 'test' relies on s0, s1, s4.
# Must save them before calling C function 'print_dec'.
addi sp, sp, -16
sw ra, 12(sp)
sw s0, 8(sp)
sw s1, 4(sp)
sw s4, 0(sp)
bnez t3, t3_1
# Error 0: fl != fl2 (t3 = 0)
mv a0, s0
jal print_dec
la a0, str1
li a1, str1_len
jal printstr_asm
mv a0, s4
jal print_dec
la a0, str2
li a1, str2_len
jal printstr_asm
mv a0, t4
jal print_dec
la a0, str5
li a1, str5_len
jal printstr_asm
j print_fail_end
t3_1:
# Error 1: previous_value >= value (t3 = 1)
mv a0, s0
jal print_dec
la a0, str3
li a1, str3_len
jal printstr_asm
mv a0, s4
jal print_dec
la a0, str4
li a1, str4_len
jal printstr_asm
mv a0, s1
jal print_dec
la a0, str5
li a1, str5_len
jal printstr_asm
print_fail_end:
lw ra, 12(sp)
lw s0, 8(sp)
lw s1, 4(sp)
lw s4, 0(sp)
addi sp, sp, 16
ret
# Helper: void print_suc_msg(void)
print_suc_msg:
la a0, str6
li a1, str6_len
jal printstr_asm
j main_c
```
:::
:::spoiler main.c code snippets
```c=
start_cycles = get_cycles();
start_instret = get_instret();
int passed = run_q1_uf8();
end_cycles = get_cycles();
end_instret = get_instret();
```
:::
**make with no flag**
**riscv-none-elf-size test.elf**
**make with -Ofast**
**riscv-none-elf-size test_Ofast.elf**
**make with -Os**
**riscv-none-elf-size test_Os.elf**
### Analysis of print_dec Assembly: no flag vs. -Os
This analysis compares the assembly output of the print_dec C function under two different compilation flags. The goal is to observe the optimization strategies used by the gcc compiler.
1. (No flag) Version
```asm=
000103d8 <print_dec>:
103d8: fc010113 addi sp,sp,-64
103dc: 02112e23 sw ra,60(sp)
103e0: 02812c23 sw s0,56(sp)
103e4: 04010413 addi s0,sp,64
103e8: fca42623 sw a0,-52(s0)
103ec: fd840793 addi a5,s0,-40
103f0: 01378793 addi a5,a5,19
103f4: fef42623 sw a5,-20(s0)
103f8: fcc42783 lw a5,-52(s0)
103fc: 06079063 bnez a5,1045c <print_dec+0x84>
10400: fec42783 lw a5,-20(s0)
10404: 03000713 li a4,48
10408: 00e78023 sb a4,0(a5)
1040c: fec42783 lw a5,-20(s0)
10410: fff78793 addi a5,a5,-1
10414: fef42623 sw a5,-20(s0)
10418: 04c0006f j 10464 <print_dec+0x8c>
1041c: 00a00593 li a1,10
10420: fcc42503 lw a0,-52(s0)
10424: d55ff0ef jal 10178 <umod>
10428: 00050793 mv a5,a0
1042c: 0ff7f793 zext.b a5,a5
10430: 03078793 addi a5,a5,48
10434: 0ff7f713 zext.b a4,a5
10438: fec42783 lw a5,-20(s0)
1043c: 00e78023 sb a4,0(a5)
10440: fec42783 lw a5,-20(s0)
10444: fff78793 addi a5,a5,-1
10448: fef42623 sw a5,-20(s0)
1044c: 00a00593 li a1,10
10450: fcc42503 lw a0,-52(s0)
10454: c61ff0ef jal 100b4 <udiv>
10458: fca42623 sw a0,-52(s0)
1045c: fcc42783 lw a5,-52(s0)
10460: fa079ee3 bnez a5,1041c <print_dec+0x44>
10464: fec42783 lw a5,-20(s0)
10468: 00178793 addi a5,a5,1
1046c: fef42623 sw a5,-20(s0)
10470: fd840793 addi a5,s0,-40
10474: 01478793 addi a5,a5,20
10478: fec42703 lw a4,-20(s0)
1047c: 40e78733 sub a4,a5,a4
10480: fec42783 lw a5,-20(s0)
10484: 04000893 li a7,64
10488: 00100513 li a0,1
1048c: 00f005b3 add a1,zero,a5
10490: 00070613 mv a2,a4
10494: 00000073 ecall
10498: 00000013 nop
1049c: 03c12083 lw ra,60(sp)
104a0: 03812403 lw s0,56(sp)
104a4: 04010113 addi sp,sp,64
104a8: 00008067 ret
```
- This version is a literal, unoptimized translation of the C code.
- Heavy Stack & Memory Use: The function allocates a large 64-byte stack frame (addi sp,sp,-64). It constantly saves (sw) and loads (lw) C variables (like val and p) to and from the stack inside the loop. This is extremely inefficient.
- External Function Calls: It makes expensive jal (function call) instructions to the **`umod`** and **`udiv`** functions on every iteration of the loop.
- Code Structure: The assembly code is easy to follow because it directly maps to the C code's if (val == 0) and while (val > 0) structure.
- Conclusion: This version is large, slow, and wastes cycles by prioritizing literal translation over performance.
2. -Os (Optimized for Size) Version
```asm=
0001008c <print_dec>:
1008c: fe010113 addi sp,sp,-32
10090: 0a051663 bnez a0,1013c <print_dec+0xb0>
10094: 03000793 li a5,48
10098: 00f10fa3 sb a5,31(sp)
1009c: 01e10713 addi a4,sp,30
100a0: 00170713 addi a4,a4,1
100a4: 02010793 addi a5,sp,32
100a8: 40e787b3 sub a5,a5,a4
100ac: 04000893 li a7,64
100b0: 00100513 li a0,1
100b4: 00e005b3 add a1,zero,a4
100b8: 00078613 mv a2,a5
100bc: 00000073 ecall
100c0: 02010113 addi sp,sp,32
100c4: 00008067 ret
100c8: 00d55633 srl a2,a0,a3
100cc: 00179793 slli a5,a5,0x1
100d0: 00167613 andi a2,a2,1
100d4: 00f667b3 or a5,a2,a5
100d8: 00f87463 bgeu a6,a5,100e0 <print_dec+0x54>
100dc: ff678793 addi a5,a5,-10
100e0: fff68693 addi a3,a3,-1
100e4: ff1692e3 bne a3,a7,100c8 <print_dec+0x3c>
100e8: 03078793 addi a5,a5,48
100ec: 00f70023 sb a5,0(a4)
100f0: 00000613 li a2,0
100f4: fff70713 addi a4,a4,-1
100f8: 01f00693 li a3,31
100fc: 00000793 li a5,0
10100: 00d555b3 srl a1,a0,a3
10104: 00179793 slli a5,a5,0x1
10108: 0015f593 andi a1,a1,1
1010c: 00f5e7b3 or a5,a1,a5
10110: 00f87863 bgeu a6,a5,10120 <print_dec+0x94>
10114: 00d315b3 sll a1,t1,a3
10118: ff678793 addi a5,a5,-10
1011c: 00b66633 or a2,a2,a1
10120: fff68693 addi a3,a3,-1
10124: fd169ee3 bne a3,a7,10100 <print_dec+0x74>
10128: f6060ce3 beqz a2,100a0 <print_dec+0x14>
1012c: 00060513 mv a0,a2
10130: 01f00693 li a3,31
10134: 00000793 li a5,0
10138: f91ff06f j 100c8 <print_dec+0x3c>
1013c: 01f10713 addi a4,sp,31
10140: 00900813 li a6,9
10144: fff00893 li a7,-1
10148: 00100313 li t1,1
1014c: fe5ff06f j 10130 <print_dec+0xa4>
```
- This version is a highly optimized and restructured piece of code. The compiler has completely rewritten the function's logic to be smaller and faster.
- Minimal Stack Use: It only allocates a 32-byte stack frame (addi sp,sp,-32), which is used only as the char buf[20] buffer. It does not save ra or s0.
- Function Inlining: This is the most significant optimization. The compiler has inlined the **`umod`** and **`udiv`** functions. The logic for division and modulo is now built directly into the print_dec assembly, eliminating all expensive jal calls.
- Register-Based Logic: All variables (val, p, remainder) are kept in registers (a0-a7, t1). Slow lw/sw operations to the stack are almost completely gone, replaced by fast register operations.
- Code Structure: The code is unreadable and does not resemble the original C code's if/while structure. The compiler has rebuilt it into a more efficient "goto-style" flow (using bnez and beqz) to minimize branches and instructions.
- Conclusion: This version is far superior. It is smaller and much faster because it avoids function calls through inlining and avoids slow memory access by using registers.
### Analysis of memcpy Assembly: -Os vs. -Ofast vs. no flag
This analysis compares the assembly output of the memcpy C function, a fundamental memory operation, under two different compilation flags. This clearly highlights the trade-offs between optimizing for code size and optimizing for speed.
1. -Os (Optimized for Size) Version
```asm=
0001003c <memcpy>:
1003c: 00000793 li a5,0
10040: 00f61463 bne a2,a5,10048 <memcpy+0xc>
10044: 00008067 ret
10048: 00f58733 add a4,a1,a5
1004c: 00074683 lbu a3,0(a4)
10050: 00f50733 add a4,a0,a5
10054: 00178793 addi a5,a5,1
10058: 00d70023 sb a3,0(a4)
1005c: fe5ff06f j 10040 <memcpy+0x4>
```
- This version prioritizes minimal code size for memcpy.
- Strategy: Simple Byte-by-Byte Copy: The compiler generates a very straightforward loop that copies data one byte at a time.
- It checks if n (the number of bytes to copy) is zero (bne a2,a5,10048).
- Inside the loop (10048 to 1005c), it uses lbu (load byte unsigned) to fetch one byte from the source and sb (store byte) to write it to the destination.
- The loop continues until all bytes are copied (j 10040).
- Code Size: This implementation is extremely compact, consisting of only 9 instructions (excluding the initial ret for n=0).
- Performance: While compact, this method is inherently slow for larger data blocks, as it performs byte-level operations and loop overhead for every single byte.
- Complexity: Very low.
- Conclusion: This version perfectly exemplifies optimization for size, resulting in a small footprint at the cost of execution speed for bulk operations.
2. -Ofast (Optimized for Speed) Version
```asm=
0001003c <memcpy>:
1003c: fff60813 addi a6,a2,-1
10040: 08060e63 beqz a2,100dc <memcpy+0xa0>
10044: 00600793 li a5,6
10048: 00158713 addi a4,a1,1
1004c: 0707fa63 bgeu a5,a6,100c0 <memcpy+0x84>
10050: 00b567b3 or a5,a0,a1
10054: 0037f793 andi a5,a5,3
10058: 00158713 addi a4,a1,1
1005c: 06079263 bnez a5,100c0 <memcpy+0x84>
10060: 40e507b3 sub a5,a0,a4
10064: 0037b793 sltiu a5,a5,3
10068: 04079c63 bnez a5,100c0 <memcpy+0x84>
1006c: ffc67893 andi a7,a2,-4
10070: 011586b3 add a3,a1,a7
10074: 00050793 mv a5,a0
10078: 0005a703 lw a4,0(a1)
1007c: 00458593 addi a1,a1,4
10080: 00478793 addi a5,a5,4
10084: fee7ae23 sw a4,-4(a5)
10088: feb698e3 bne a3,a1,10078 <memcpy+0x3c>
1008c: 41180833 sub a6,a6,a7
10090: 011507b3 add a5,a0,a7
10094: 05160463 beq a2,a7,100dc <memcpy+0xa0>
10098: 0006c703 lbu a4,0(a3)
1009c: 00e78023 sb a4,0(a5)
100a0: 02080e63 beqz a6,100dc <memcpy+0xa0>
100a4: 0016c603 lbu a2,1(a3)
100a8: 00100713 li a4,1
100ac: 00c780a3 sb a2,1(a5)
100b0: 02e80663 beq a6,a4,100dc <memcpy+0xa0>
100b4: 0026c703 lbu a4,2(a3)
100b8: 00e78123 sb a4,2(a5)
100bc: 00008067 ret
100c0: 00c50633 add a2,a0,a2
100c4: 00050793 mv a5,a0
100c8: fff74683 lbu a3,-1(a4)
100cc: 00178793 addi a5,a5,1
100d0: 00170713 addi a4,a4,1
100d4: fed78fa3 sb a3,-1(a5)
100d8: fec798e3 bne a5,a2,100c8 <memcpy+0x8c>
100dc: 00008067 ret
```
- This version prioritizes maximum execution speed for memcpy, even if it means significantly increasing code size and complexity.
- Strategy: Aggressive Word-by-Word Copy with Alignment Handling: The compiler uses a much more sophisticated strategy to leverage the processor's ability to move data in 4-byte (word) chunks.
- Alignment Checks: The function starts with complex logic (10044 to 10068) to check if the source and destination memory addresses are 4-byte aligned. Misaligned accesses can be slower or require special handling.
- Fast Path (Word-by-Word Copy): If both addresses are aligned, the code enters a highly optimized main loop (10078 to 10088):
- It uses lw (load word, 4 bytes) to load data and sw (store word, 4 bytes) to store it. This is significantly faster than byte-by-byte copies.
- Partial Copy / Cleanup Logic: After the main word-by-word loop, there's additional logic (10098 to 100bc) to handle any remaining 1, 2, or 3 bytes that couldn't be copied in full 4-byte chunks. There's also a "slow path" (100c0) which copies byte-by-byte if addresses are misaligned.
- Code Size: This implementation is substantially larger (over 40 instructions) due to the added complexity of alignment checks, branching, and handling partial copies.
- Performance: This version is much faster for copying large blocks of data because it maximizes the use of the 32-bit data bus.
- Complexity: Very high.
- Conclusion: This version is a prime example of optimization for speed, trading significant code size and complexity for superior execution performance in data-intensive tasks.
3. -O0 (No Optimization) Version
```asm=
0001003c <memcpy>:
1003c: fd010113 addi sp,sp,-48
10040: 02112623 sw ra,44(sp)
10044: 02812423 sw s0,40(sp)
10048: 03010413 addi s0,sp,48
1004c: fca42e23 sw a0,-36(s0)
10050: fcb42c23 sw a1,-40(s0)
10054: fcc42a23 sw a2,-44(s0)
10058: fdc42783 lw a5,-36(s0)
1005c: fef42623 sw a5,-20(s0)
10060: fd842783 lw a5,-40(s0)
10064: fef42423 sw a5,-24(s0)
10068: 0240006f j 1008c <memcpy+0x50>
1006c: fe842703 lw a4,-24(s0)
10070: 00170793 addi a5,a4,1
10074: fef42423 sw a5,-24(s0)
10078: fec42783 lw a5,-20(s0)
1007c: 00178693 addi a3,a5,1
10080: fed42623 sw a3,-20(s0)
10084: 00074703 lbu a4,0(a4)
10088: 00e78023 sb a4,0(a5)
1008c: fd442783 lw a5,-44(s0)
10090: fff78713 addi a4,a5,-1
10094: fce42a23 sw a4,-44(s0)
10098: fc079ae3 bnez a5,1006c <memcpy+0x30>
1009c: fdc42783 lw a5,-36(s0)
100a0: 00078513 mv a0,a5
100a4: 02c12083 lw ra,44(sp)
100a8: 02812403 lw s0,40(sp)
100ac: 03010113 addi sp,sp,48
100b0: 00008067 ret
```
- This version prioritizes literal translation and debuggability, resulting in the slowest and most inefficient code.
- Strategy: Literal Byte-by-Byte, Stack-Heavy: The compiler generates a "dumb" translation of the C code. It allocates a large 48-byte stack frame and saves all C arguments (dest, src, n) to memory before starting.
- Alignment Checks: None. The logic is too simple to check for alignment.
- Fast Path (Word-by-Word Copy): None. The function only contains a "slow path."
- Partial Copy / Cleanup Logic: The entire function is the slow path. The loop (from 1006c to 10098) loads and saves variables from the stack for every single byte, performing lbu and sb one byte at a time.
- Code Size: Substantially large (around 30 instructions), not because of complex logic, but because of the massive inefficiency of constant, repetitive lw and sw instructions to the stack.
- Performance: Extremely slow. The loop performs multiple high-cost memory accesses (stack lw/sw) for every byte copied, leading to massive pipeline stalls.
- Complexity: The logic is simple, but the implementation is highly inefficient.
- Conclusion: This version is a prime example of no optimization. It is slow and bloated, prioritizing a literal translation for debugging over any form of performance.
## Quiz2 Problem A [link](https://hackmd.io/@sysprog/arch2025-quiz2-sol)
:::spoiler original asm code
```asm=
# --- External Function Declarations ---
.extern print_dec # Declare external C function 'print_dec' to be linked
# --- Text Section ---
.text
.globl run_q2_game_hanoi
run_q2_game_hanoi:
# 1. PROLOGUE (Modified)
# We need to call an external function (jal print_dec), so we must save ra (x1)
# Allocate 48 bytes (16-byte aligned)
# 0-19: s0-s4 (x8, x9, x18, x19, x20)
# 20-31: Disk array
# 32: ra (x1)
# 36-37: Temp char buffer for 'A'/'B'/'C'
addi x2, x2, -48
sw x8, 0(x2)
sw x9, 4(x2)
sw x18, 8(x2)
sw x19, 12(x2)
sw x20, 16(x2)
sw x1, 32(x2) # <-- Key: Save the return address (ra)
# ... (Disk position initialization is unchanged) ...
sw x0, 20(x2)
sw x0, 24(x2)
sw x0, 28(x2)
addi x8, x0, 1
game_loop:
addi x5, x0, 8
beq x8, x5, finish_game
# --- (Gray code and move logic is unchanged) ---
srli x5, x8, 1
xor x6, x8, x5
addi x7, x8, -1
srli x28, x7, 1
xor x7, x7, x28
xor x5, x6, x7
addi x9, x0, 0
andi x6, x5, 1
bne x6, x0, disk_found
addi x9, x0, 1
andi x6, x5, 2
bne x6, x0, disk_found
addi x9, x0, 2
disk_found:
andi x30, x5, 5
addi x31, x0, 5
beq x30, x31, pattern_match
jal x0, continue_move
pattern_match:
continue_move:
slli x5, x9, 2
addi x5, x5, 20
add x5, x2, x5
lw x18, 0(x5) # x18 = source peg (0, 1, 2)
bne x9, x0, handle_large
addi x19, x18, 2
addi x6, x0, 3
blt x19, x6, display_move
sub x19, x19, x6
jal x0, display_move
handle_large:
lw x6, 20(x2)
addi x19, x0, 3
sub x19, x19, x18
sub x19, x19, x6 # x19 = destination peg (0, 1, 2)
# x9 = disk_id, x18 = from_peg, x19 = to_peg
# --- 2. DISPLAY SECTION (Rewritten to use sys_write and print_dec) ---
display_move:
# 1. Print "Move Disk " (using sys_write, a7=64)
# This is identical to the asm volatile in your C macro
add a7, x0, 0x40 # a7 = 64 (sys_write)
add a0, x0, 1 # a0 = 1 (stdout)
la a1, str1 # a1 = pointer to string
addi a2, x0, 11 # a2 = length of "Move Disk "
ecall
# 2. Print the disk number (call C function)
addi a0, x9, 1 # a0 = argument (x9+1)
jal ra, print_dec # Call C function
# 3. Print " from " (using sys_write)
add a7, x0, 0x40
add a0, x0, 1
la a1, str2
addi a2, x0, 6 # length of " from "
ecall
# 4. Print 'from' peg (A/B/C)
la x20, obdata
add x5, x20, x18 # x18 = 'from' index
lbu x11, 0(x5)
li x6, 0x6F
xor x11, x11, x6
addi x11, x11, -0x12 # x11 = 'A', 'B', or 'C'
# Store the character 'A'/'B'/'C' into the temp buffer on the stack
sb x11, 36(x2)
# Print that 1-byte buffer
add a7, x0, 0x40
add a0, x0, 1
add a1, x2, 36 # a1 = pointer to stack buffer
addi a2, x0, 1 # a2 = length (1)
ecall
# 5. Print " to " (using sys_write)
add a7, x0, 0x40
add a0, x0, 1
la a1, str3
addi a2, x0, 4 # length of " to "
ecall
# 6. Print 'to' peg (A/B/C)
add x5, x20, x19 # x19 = 'to' index
lbu x12, 0(x5)
xor x12, x12, x6
addi x12, x12, -0x12 # x12 = 'A', 'B', or 'C'
sb x12, 37(x2) # Store to a different location on the stack
add a7, x0, 0x40
add a0, x0, 1
add a1, x2, 37 # a1 = pointer
addi a2, x0, 1 # a2 = length (1)
ecall
# 7. Print newline character '\n' (using sys_write)
add a7, x0, 0x40
add a0, x0, 1
la a1, str_nl
addi a2, x0, 1 # length (1)
ecall
# --- (State update logic is unchanged) ---
slli x5, x9, 2
addi x5, x5, 20
add x5, x2, x5
sw x19, 0(x5) # Update disk position
addi x8, x8, 1
jal x0, game_loop
# --- 3. FINISH SECTION (Modified) ---
finish_game:
# Restore all registers
lw x8, 0(x2)
lw x9, 4(x2)
lw x18, 8(x2)
lw x19, 12(x2)
lw x20, 16(x2)
lw x1, 32(x2) # <-- Key: Restore the return address (ra)
# Deallocate the stack
addi x2, x2, 48
# [Modified] Use ret instruction to return to C code
ret
.data
obdata: .byte 0x3c, 0x3b, 0x3a
str1: .asciz "Move Disk " # length 11
str2: .asciz " from " # length 6
str3: .asciz " to " # length 4
str_nl: .byte 10 # Newline (ASCII 10)
```
:::
### Optimization Method
#### Add detail illustrate and cycles compare
:::info
1. Data De-obfuscation
- Concept: The original code used complex logic (`obdata` array combined with XOR `0x6F` and subtraction `0x12`) to convert the numbers 0, 1, and 2 into the characters 'A', 'B', and 'C'. This required multiple CPU arithmetic instructions to be executed in every loop iteration.
- Optimization: We created a direct lookup table (`peg_names: .asciz "ABC"`) in the `.data` section. Now, the code simply adds the index to the base address to retrieve the corresponding character directly, eliminating all redundant arithmetic operations inside the loop.
```asm
.data
# obdata: .byte 0x3c, 0x3b, 0x3a
peg_names: .asciz "ABC" # directly save in ASCII
.text
# remove arithmetic operation in display_move loop：
# la x20, obdata
# add x5, x20, x18 # x18 = index
# lbu x11, 0(x5) # read obdata byte
# li x6, 0x6F
# xor x11, x11, x6 # XOR decode
# addi x11, x11, -0x12 # sub correction -> get 'A'/'B'/'C'
```
:::
:::info
2. Direct I/O Addressing
- Concept: The original approach for printing peg names ('A'/'B'/'C') involved first reading the character from `.data` (`lbu`), writing it to a temporary buffer on the stack (`sb`), and then passing the stack address to the system call. This created unnecessary memory read/write operations.
- Optimization: We leveraged the fact that sys_write only requires a "memory address." We directly calculated the original memory address of the character within the `.data` section (`peg_names base + index`) and passed this address directly to `a1`. This eliminates the intermediate step of copying the character to the stack, reducing both the instruction count and memory accesses.
```asm
# assume x11 store 'A'
# sb x11, 44(x2) # write to stack
# add a1, x2, 44 # a1 points to stack
# x25 (s9) store peg_names base addr, x18 = index
# no sb and stack operation
add a1, x25, x18 # a1 directly points to 'A' in .data.
li a0, 1
li a7, 64
li a2, 1
ecall
```
:::
:::info
3. Loop-Invariant Code Motion
- Concept: In assembly, `la` (Load Address) is a pseudo-instruction that is typically expanded into 2 actual instructions (`auipc` + `addi`). The original code executed `la` inside every loop iteration to reload the addresses of strings (like "Move Disk "), even though these addresses never change.
- Optimization: We moved the loading of these constant string addresses to the Prologue phase (before the `game_loop` label) and stored them in s (Saved) registers. Inside the loop, we switched to using a single `mv` instruction to access these addresses, reducing the total instruction count within the loop.
```asm
run_q2_game_hanoi:
# --- Prologue ---
la x21, str1 # store addr to s5 (x21)
la x22, str2 # store addr to s6 (x22)
# ... other string ...
game_loop:
# ...
display_move:
# in each iteration, la (auipc + addi) is executed.
# la a1, str1
mv a1, x21 # use s5, just 1 instruction
li a0, 1
li a7, 64
li a2, 11
ecall
# other string ......
```
:::
:::info
4. Redundant Code Elimination
- Concept: The original code contained a check after the `disk_found` label to see if `x5` was equal to 5 (using `andi`, `addi`, `beq`). However, based on the mathematical properties of Gray Code, `x5` is the result of Gray(n) XOR Gray(n-1), which is always a power of 2 (1, 2, 4...), meaning it can absolutely never equal 5.
- Optimization: We directly deleted this code block that checked for an impossible condition. This saves 4 useless instructions per iteration, purely reducing the CPU burden.
```asm
disk_found:
# remove 4 never-executed instructions
# andi x30, x5, 5
# addi x31, x0, 5
# beq x30, x31, pattern_match
# jal x0, continue_move
# pattern_match:
# continue_move:
slli x5, x9, 2
# ...
```
:::
| method with no flag | cycles | improvement |
|:------------------------ |:------:|:-----------:|
| **no use** | 9289 | - |
| **opt with 1. 2.** | 9226 | 0.7% |
| **opt with 3.** | 9274 | 0.016% |
| **opt with 4.** | 9261 | 0.3% |
| **opt with 1. 2. 3. 4.** | 9149 | 1.5% |
5. Optimized Code
```asm=
# --- External Function Declarations ---
.extern print_dec # Declare external C function 'print_dec' to be linked
# --- Text Section ---
.text
.globl run_q2_game_hanoi
run_q2_game_hanoi:
# 1. PROLOGUE (Expanded)
# Allocate 64 bytes (16-byte aligned) to store:
# s0-s4 (x8, x9, x18, x19, x20) (5 regs * 4B = 20B)
# ra (x1) (1 reg * 4B = 4B)
# s5-s9 (x21-x25) (5 regs * 4B = 20B)
# disk array (3 regs * 4B = 12B)
# Total = 20 + 4 + 20 + 12 = 56B. Align to 16B, allocate 64B.
addi x2, x2, -64
sw x8, 0(x2) # s0 (loop_count)
sw x9, 4(x2) # s1 (disk_id)
sw x18, 8(x2) # s2 (from_peg)
sw x19, 12(x2) # s3 (to_peg)
sw x20, 16(x2) # s4 (disk_array_base)
sw x1, 20(x2) # ra (because we will jal print_dec)
sw x21, 24(x2) # s5 (ptr: str1)
sw x22, 28(x2) # s6 (ptr: str2)
sw x23, 32(x2) # s7 (ptr: str3)
sw x24, 36(x2) # s8 (ptr: str_nl)
sw x25, 40(x2) # s9 (ptr: peg_names)
# The base of the disk position array will be at 48(x2)
# 【Optimization 2】: Loop-invariant code motion
la x21, str1
la x22, str2
la x23, str3
la x24, str_nl
la x25, peg_names # 【Optimization 1】
# Set s4 (x20) as the base address for the disk array
addi x20, x2, 48
# ... (Disk position initialization) ...
sw x0, 0(x20) # Disk 0 position
sw x0, 4(x20) # Disk 1 position
sw x0, 8(x20) # Disk 2 position
addi x8, x0, 1
game_loop:
addi x5, x0, 8
beq x8, x5, finish_game
# --- (Gray code and move logic) ---
srli x5, x8, 1
xor x6, x8, x5
addi x7, x8, -1
srli x28, x7, 1
xor x7, x7, x28
xor x5, x6, x7
addi x9, x0, 0
andi x6, x5, 1
bne x6, x0, disk_found
addi x9, x0, 1
andi x6, x5, 2
bne x6, x0, disk_found
addi x9, x0, 2
disk_found:
# 【Optimization 3】: Removed 4 redundant instructions
# x5 store the result of Gray(n) XOR Gray(n-1)
# result must be 1,2,4,8 (power of 2)
# BLANK 16: Check impossible pattern (multiple bits)
# andi x30, x5, 5
# addi x31, x0, 5
# beq x30, x31, pattern_match
# jal x0, continue_move
# pattern_match:
# continue_move:
slli x5, x9, 2
add x5, x20, x5
lw x18, 0(x5) # x18 = source peg (0, 1, 2)
bne x9, x0, handle_large
# Disk 0 logic
addi x19, x18, 2
addi x6, x0, 3
blt x19, x6, display_move
sub x19, x19, x6
jal x0, display_move
handle_large:
# Disk 1/2 logic
lw x6, 0(x20)
addi x19, x0, 3
sub x19, x19, x18
sub x19, x19, x6 # x19 = destination peg (0, 1, 2)
# Thread will automatically fall through to display_move
display_move:
# --- 2. DISPLAY SECTION (Optimized) ---
# 1. Print "Move Disk "
add a7, x0, 0x40
add a0, x0, 1
mv a1, x21 # 【Optimization 2】: Use s5
addi a2, x0, 11
ecall
# 2. Print the disk number (call C function)
addi a0, x9, 1
jal ra, print_dec
# 3. Print " from "
add a7, x0, 0x40
add a0, x0, 1
mv a1, x22 # 【Optimization 2】: Use s6
addi a2, x0, 6
ecall
# 4. Print 'from' peg (A/B/C)
# 【Optimization 4】: Use peg_names address directly, no more copying to stack
add a1, x25, x18 # a1 = peg_names + from_index
add a7, x0, 0x40
add a0, x0, 1
addi a2, x0, 1 # a2 = length (1)
ecall
# 5. Print " to "
add a7, x0, 0x40
add a0, x0, 1
mv a1, x23 # 【Optimization 2】: Use s7
addi a2, x0, 4
ecall
# 6. Print 'to' peg (A/B/C)
# 【Optimization 4】: Use peg_names address directly, no more copying to stack
add a1, x25, x19 # a1 = peg_names + to_index
add a7, x0, 0x40
add a0, x0, 1
addi a2, x0, 1 # a2 = length (1)
ecall
# 7. Print newline '\n'
add a7, x0, 0x40
add a0, x0, 1
mv a1, x24 # 【Optimization 2】: Use s8
addi a2, x0, 1
ecall
# --- (State update logic) ---
slli x5, x9, 2
add x5, x20, x5
sw x19, 0(x5) # Update disk position
addi x8, x8, 1
jal x0, game_loop
# --- 3. FINISH SECTION (Epilogue) ---
finish_game:
# Restore all registers
lw x8, 0(x2)
lw x9, 4(x2)
lw x18, 8(x2)
lw x19, 12(x2)
lw x20, 16(x2)
lw x1, 20(x2) # Restore ra
lw x21, 24(x2) # Restore s5
lw x22, 28(x2) # Restore s6
lw x23, 32(x2) # Restore s7
lw x24, 36(x2) # Restore s8
lw x25, 40(x2) # Restore s9
# Deallocate the stack
addi x2, x2, 64
ret
.data
# 【Optimization 1】: Removed obdata, using a direct lookup table
peg_names: .asciz "ABC"
str1: .asciz "Move Disk " # length 11
str2: .asciz " from " # length 6
str3: .asciz " to " # length 4
str_nl: .byte 10 # Newline (ASCII 10)
```
Run in Bare-Metal environment
In main.c call external asm function.
```c=
start_cycles = get_cycles();
start_instret = get_instret();
int passed = run_q2_game_hanoi();
end_cycles = get_cycles();
end_instret = get_instret();
```
### make run result
(1) Before Optimized
(2) Optimized (make with no flag)
(3) Optimized (make with -Ofast)
(4) Optimized (make with -Os)
| method | cycles | improvement |
|:---------------------------- |:------:|:-----------:|
| **(1) before opt** | 9289 | - |
| **(2) after hand write opt** | 9149 | 1.5% |
| **(3) -Ofast** | 3988 | 57% |
| **(4) -Os** | 3876 | 58% |
### Observation
Analysis:
1. From (1) to (2): My Own Optimization
- My optimized hanoi.S (e.g., removing obdata, removing redundant instructions).
- The C Library was unchanged (both compiled with default).
- Result: My handwritten assembly optimization saved 9289 - 9149 = 140 cycles.
2. From (2) to (3): The C Library Optimization
- hanoi.S was unchanged.
- The C Library (containing print_dec) went from no optimization to -Ofast (aggressive optimization).
- Result: The C Library's efficiency massively improved, saving 9149 - 3988 = 5161 cycles.
- This proves that in tests (1) and (2), the vast majority of the inefficiency was coming from the unoptimized C library (especially print_dec).
3. From (3) to (4): The Battle of Optimization Flags
- hanoi.S was unchanged.
- The C Library was compiled with -Os instead of -Ofast.
- Result: The machine code for print_dec (and other C startup code) generated by -Os executes fewer total instructions than the version generated by -Ofast.
- The difference is 3988 - 3876 = 112 fewer instructions executed.
4. -Ofast's "optimization" was not helpful in this specific situation, resulting in a C library that "requires more instructions to execute", so the total cycle number will be higher.
## Quiz3 Problem C [link](https://hackmd.io/@sysprog/arch2025-quiz3-sol)
In Quiz 3 Problem C, we try to implement the **Fast Inverse Square Root** ( $\frac{65536}{\sqrt{x}}$ )
algorithm and run the test suite in a bare-metal environment.
First, we implement the `fast_rsqrt` algorithm following the steps provided by the instructor.
1. The first step is lookup table initialization: we use `clz` to find the position of the most significant bit (MSB) of the input value `x`, then use that index to fetch the initial guess from the `rsqrt_table`.
2. The second step is linear interpolation: if `x` isn’t an exact power of two, we refine the initial guess by interpolating between table entries to reduce the error.
3. The third step is **Newton–Raphson iteration**: we perform two iterations to further improve the accuracy of the result.
```c
static const uint16_t rsqrt_table[32] = {
65536, 46341, 32768, 23170, 16384, /* 2^0 to 2^4 */
11585, 8192, 5793, 4096, 2896, /* 2^5 to 2^9 */
2048, 1448, 1024, 724, 512, /* 2^10 to 2^14 */
362, 256, 181, 128, 90, /* 2^15 to 2^19 */
64, 45, 32, 23, 16, /* 2^20 to 2^24 */
11, 8, 6, 4, 3, /* 2^25 to 2^ 29 */
2, 1 /* 2^3O, 2^3l */
} ;
uint32_t fast_rsqrt(uint32_t x)
{
if (x == 0) return 0xFFFFFFFF; // Handle zero case
if (x == 1) return 65536; // Handle exact case for 1
// Step 1: Find MSB position
int exp = 31 - clz(x); // Count leading zeros
uint32_t y = rsqrt_table[exp]; // Initial estimate
// Step 2: Linear interpolation for non-power-of-2 inputs
if (x > (1u << exp)) {
uint32_t y_next = (exp < 31) ? rsqrt_table[exp + 1] : 0; // Next estimate
uint32_t delta = y - y_next; // Difference between estimates
uint32_t frac =(uint32_t) ((((uint64_t)x - (1UL << exp)) << 16) >> exp);
y -= (uint32_t) ((delta * frac) >> 16); // Interpolate
}
// Step 3: Newton-Raphson iterations
for (int iter = 0; iter < 2; iter++) {
uint32_t y2 = (uint32_t)mul32(y, y); // y^2 in Q0.32
uint32_t xy2 = (uint32_t)(mul32(x, y2) >> 16); // x * y^2 in Q16.16
y = (uint32_t)(mul32(y, (3u << 16) - xy2) >> 17); // Newton step
}
return y;
}
```
### Examples: `fast_rsqrt(1024)` and `fast_rsqrt(100)`
To illustrate how the algorithm works, walk through two example inputs: `fast_rsqrt(1024)` and `fast_rsqrt(100)`.
1. **`fast_rsqrt(1024)`**
* **Step 1: Finding the MSB (Exponent)**
* The code uses `clz(1024)` to determine the position of the Most Significant Bit (MSB), which gives us the exponent `exp = 10`.
* We look up the corresponding value in the table: `y = 2048` (which is $65536 / \sqrt{2^{10}}$).
* **Step 2: The Execution Check (Skipping the Math)**
* The code checks the condition: `if (x > (1u << exp))`?
* The test is `if (1024 > 1024)`, which is **False**.
* **Step 3: Execution Path**
* The entire block containing the complex calculations (interpolation and Newton-Raphson iterations) is **skipped**. Since the table value for $2^{exp}$ is exact, no refinement is needed.
* **Result**
* The function returns the precise table value: **2048**.
---
2. **`fast_rsqrt(100)`**
Full calculation path because **100 falls between two powers of two** ($2^6$ and $2^7$).
* **Step 1: Finding the MSB (Exponent)**
* `clz(100)` tells us the MSB is at position 6, so the initial exponent is exp = 6 ($2^6=64$).
* The code takes the table value for $2^6$ as the starting point: `y = 8192`.
* **Step 2: The Execution Check (Entering the Math Block)**
* The code checks the condition: `if (x > (1u << exp))`?
* The test is `if (100 > 64)`, which is **True**. This triggers the full calculation.
* **Step 3: Execution Path**
* The code **enters** the calculation block to refine the estimate:
1. **Linear Interpolation:** A fractional term is calculated (based on the distance between 100 and 64) and used to adjust `y` from 8192 downwards.
2. **Newton-Raphson:** The two iterations are run on the already improved `y` value to ensure high final accuracy.
* **Result**
* The function returns the fully refined value, approximately **6553**.
I write a test suite function to check several case values.
* **run_q3_rsqrt()** : test suite function.
* **check_exact()** : checks whether the two values are exactly the same.
* **check_approx()** : not only compares the values but also checks whether their difference exceeds a given tolerance.
```c
int run_q3_rsqrt() {
int all_passed = 1;
// Edge/Special Cases
check_exact("rsqrt(0)", fast_rsqrt(0), 0xFFFFFFFF, 0, &all_passed);
check_exact("rsqrt(1)", fast_rsqrt(1), 65536, 0, &all_passed);
check_exact("rsqrt(0xFFFFFFFF)", fast_rsqrt(0xFFFFFFFF), 1, 0, &all_passed);
// Powers of 2
check_exact("rsqrt(4)", fast_rsqrt(4), 32768, 0, &all_passed);
check_exact("rsqrt(16)", fast_rsqrt(16), 16384, 0, &all_passed);
check_exact("rsqrt(1024)", fast_rsqrt(1024), 2048, 0, &all_passed);
check_exact("rsqrt(65536)", fast_rsqrt(65536), 256, 0, &all_passed);
check_exact("rsqrt(1048576)", fast_rsqrt(1048576), 64, 0, &all_passed);
// General Cases (10% tolerance)
check_approx("rsqrt(100)", fast_rsqrt(100), 6554, 10, 0, &all_passed);
check_approx("rsqrt(2)", fast_rsqrt(2), 46341, 10, 0, &all_passed);
check_approx("rsqrt(10)", fast_rsqrt(10), 20723, 10, 0, &all_passed);
check_approx("rsqrt(42)", fast_rsqrt(42), 10103, 10, 0, &all_passed);
check_approx("rsqrt(12345)", fast_rsqrt(12345), 590, 10, 0, &all_passed);
check_approx("rsqrt(1000000)", fast_rsqrt(1000000), 66, 10, 0, &all_passed);
check_approx("rsqrt(2000000000)", fast_rsqrt(2000000000), 1, 10, 0, &all_passed);
return all_passed;
}
```
Running in a Bare-Metal environment and observe the result.
```bash
=== HW2 FastRsqrt Tests in Bare Metal ===
Running fast_rsqrt test suite...
Testing edge cases...
-> Calling rsqrt(0)...
[PASS] rsqrt(0) | Cycles: 45
-> Calling rsqrt(1)...
[PASS] rsqrt(1) | Cycles: 48
-> Calling rsqrt(0xFFFFFFFF)...
[PASS] rsqrt(0xFFFFFFFF) | Cycles: 3141
Testing powers of 2...
[PASS] rsqrt(4) | Cycles: 114
[PASS] rsqrt(16) | Cycles: 114
[PASS] rsqrt(1024) | Cycles: 108
[PASS] rsqrt(65536) | Cycles: 114
[PASS] rsqrt(1048576) | Cycles: 108
Testing general cases (10% tolerance)...
[PASS] rsqrt(100) (Got: 6553) | Cycles: 4225
[PASS] rsqrt(2) (Got: 46341) | Cycles: 117
[PASS] rsqrt(10) (Got: 20724) | Cycles: 4473
[PASS] rsqrt(42) (Got: 10112) | Cycles: 4295
[PASS] rsqrt(12345) (Got: 589) | Cycles: 4157
[PASS] rsqrt(1000000) (Got: 65) | Cycles: 3615
[PASS] rsqrt(2000000000) (Got: 1) | Cycles: 3414
q3-rsqrt Test Suite: PASSED
Total Cycles: 150174 Total Instructions: 150174
=== All Tests Completed ===
```
We can see that if the value **isn’t** a power of two or one of an edge case, the computation takes many more cycles.
My test suite mainly calls `fast_rsqrt`, which itself relies on `clz` and `mul32`. If we want to reduce the cycle count, we’ll need to implement the computation in a lower-level way.
### Rewrite `clz` in assembly
In my implementation, I replaced the large constant masks with `srli` because loading big constants in RISC-V usually takes two instructions(`lui` + `addi`), while a shift only needs one. For the final 31-bit check, I used `bltz` to test the sign bit, so there’s no need for another `srli` and constant load.
```asm
.global clz
# -----------------------------------------------------------------------
# clz (Count Leading Zeros)
# Input: a0
# Output: a0
# -----------------------------------------------------------------------
clz:
# 1. Handle special case: input is 0
beqz a0, is_zero # If a0 == 0, jump to is_zero
# 2. Initialize counter (t0)
li t0, 0
# --- Check upper 16 bits ---
srli t1, a0, 16
bnez t1, check_8 # If upper 16 bits are not zero, go check upper 8 bits
addi t0, t0, 16 # Otherwise n += 16
slli a0, a0, 16 # x <<= 16
check_8:
# --- Check upper 8 bits ---
srli t1, a0, 24
bnez t1, check_4
addi t0, t0, 8
slli a0, a0, 8
check_4:
# --- Check upper 4 bits ---
srli t1, a0, 28
bnez t1, check_2
addi t0, t0, 4
slli a0, a0, 4
check_2:
# --- Check upper 2 bits ---
srli t1, a0, 30
bnez t1, check_1
addi t0, t0, 2
slli a0, a0, 2
check_1:
# --- Check highest bit (Bit 31) ---
bltz a0, done # If a0 < 0 (Bit 31 == 1), done
addi t0, t0, 1 # Otherwise n += 1
done:
mv a0, t0 # Move result into a0
ret
is_zero:
li a0, 32 # Special return value when input is zero
ret
```
I actually tested a branchless version of CLZ, but it was slower than the branching version in every single case. So, I ended up sticking with the branching one.
I suspect my branchless implementation might have been a bit inefficient.
```asm
.global clz_brless
# -----------------------------------------------------------------------
# clz_branchless_binary
# Branchless CLZ implementation using a binary search pattern.
# Input: a0
# Output: a0
# -----------------------------------------------------------------------
clz_brless
# Preserve original input for zero correction
mv t5, a0
# Initialize counter
li t0, 0
# Check upper 16 bits
srli t1, a0, 16
sltiu t2, t1, 1 # t2 = (t1 == 0)
slli t3, t2, 4 # shift amount = 16 or 0
add t0, t0, t3
sll a0, a0, t3
# Check upper 8 bits
srli t1, a0, 24
sltiu t2, t1, 1
slli t3, t2, 3 # shift amount = 8 or 0
add t0, t0, t3
sll a0, a0, t3
# Check upper 4 bits
srli t1, a0, 28
sltiu t2, t1, 1
slli t3, t2, 2 # shift amount = 4 or 0
add t0, t0, t3
sll a0, a0, t3
# Check upper 2 bits
srli t1, a0, 30
sltiu t2, t1, 1
slli t3, t2, 1 # shift amount = 2 or 0
add t0, t0, t3
sll a0, a0, t3
# Check MSB
srli t1, a0, 31
sltiu t2, t1, 1
add t0, t0, t2
# Zero-input adjustment (CLZ(0) = 32)
seqz t4, t5
add a0, t0, t4
ret
```
### Rewrite`mul32` in assembly
Compare with C code, my implementaion hava some advantages.
1. **Early Exit Mechanism**: Unlike the original code that forces 32 iterations, my code checks if the remaining multiplier is zero. If it is, it terminates the loop immediately to save time.
2. **Zero Skip Logic**: I also implemented a "Zero Skip" check inside the loop. If the current bit is zero, it bypasses the addition instructions entirely and only performs the shift, saving unnecessary cycles.
3. **Optimized Shifting**: Instead of calculating a large shift (<< i) from scratch, I use an efficient incremental shift of 1 in each step.
4. **Leaf Function Efficiency**: Finally, it’s a leaf function that runs purely on registers. There is absolutely no stack usage or memory access overhead.
```c
static uint64_t mul32(uint32_t a, uint32_t b) {
uint64_t r = 0;
for (int i = 0; i < 32; i++) {
if (b & ( 1U << i ))
r += (uint64_t)a << i ;
}
return r;
}
```
```asm
.global mul32
# -----------------------------------------------------------------------
# mul32: Unsigned 32x32 -> 64-bit multiplication
# Input: a0 = a, a1 = b
# Output: a1:a0 = result (hi:lo)
# -----------------------------------------------------------------------
mul32:
# Clear result accumulators
# t0 = res_lo, t1 = res_hi
li t0, 0
li t1, 0
# Extend 'a' to 64-bit. t2 holds the upper 32 bits.
li t2, 0
mul32_loop:
# Early exit if multiplier is empty
beqz a1, mul32_done
# Check LSB. Skip add if bit is 0.
andi t3, a1, 1
beqz t3, mul32_shift
# --- Add 'a' to result (64-bit) ---
add t0, t0, a0 # res_lo += a_lo
sltu t3, t0, a0 # Carry bit? (1 if wrapped around, else 0)
add t1, t1, t2 # res_hi += a_hi
add t1, t1, t3 # res_hi += carry
mul32_shift:
# --- Shift 'a' left by 1 (64-bit) ---
# Need to bridge the MSB of a_lo to LSB of a_hi
srli t3, a0, 31 # Grab MSB from low part
slli a0, a0, 1 # a_lo << 1
slli t2, t2, 1 # a_hi << 1
or t2, t2, t3 # Merge MSB into high part
# Shift multiplier right
srli a1, a1, 1
j mul32_loop
mul32_done:
# Set return values
mv a0, t0
mv a1, t1
ret
```
After rewrite and test **`clz`** 、 **`clz_brless`**、**`mul32`**, we can look at the results cycles again to see how it performs.
| Input | (1)orginal | (2)clz | (3)clz_brless | (4)mul32 | (5)clz + mul32 | (1) vs (5) |
|:------------------- |:---------- |:------ |:------------- |:-------- |:-------------- | :----------|
| `rsqrt(0)` | 45 | 45 | 45 | 45 | 45 | 0% |
| `rsqrt(1)` | 48 | 48 | 48 | 48 | 48 | 0% |
| `rsqrt(0xFFFFFFFF)` | 3141 | 3126 | 3141 | 925 | 910 | 71% |
| `rsqrt(4)` | 114 | 85 | 93 | 114 | 85 | 25% |
| `rsqrt(16)` | 114 | 85 | 93 | 114 | 85 | 25% |
| `rsqrt(1024)` | 108 | 83 | 93 | 108 | 83 | 23% |
| `rsqrt(65536)` | 114 | 85 | 93 | 114 | 85 | 25% |
| `rsqrt(1048576)` | 108 | 83 | 93 | 108 | 83 | 23% |
| `rsqrt(100)` | 4225 | 4200 | 4210 | 1720 | 1695 | 60% |
| `rsqrt(2)` | 117 | 86 | 93 | 117 | 86 | 26.5% |
| `rsqrt(10)` | 4473 | 4446 | 4455 | 1838 | 1811 | 60% |
| `rsqrt(42)` | 4295 | 4268 | 4277 | 1760 | 1733 | 60% |
| `rsqrt(12345)` | 4157 | 4134 | 4145 | 1538 | 1515 | 64% |
| `rsqrt(1000000)` | 3615 | 3592 | 3603 | 1296 | 1273 | 65% |
| `rsqrt(2000000000)` | 3414 | 3397 | 3411 | 974 | 957 | 72% |
The bottleneck here is the `mul32` operation—the 32-bit multiplication. Unless we're dealing with edge cases or values that can be handled by a lookup table, we're seeing a cycle reduction of at least **60%**. On the other hand, `clz` doesn't help much performance-wise since it's such a lightweight calculation, though it still offers a slight improvement.
### Compile with -Ofast and -Os Flag
Let's check the performance of what the compiler spits out versus what we wrote by hand.
#### Overview
| Input Case | -O0 (Handwrite Asm) | -Ofast (Speed) | -Os (Size) |
|:--------------------- |:------------------- |:-------------- |:---------- |
| **Code Size (Bytes)** | 9146 | 6680 | **5492** |
| `rsqrt(0)` | 45 | 8 | 8 |
| `rsqrt(1)` | 48 | 8 | 8 |
| `rsqrt(0xFFFFFFFF)` | 910 | 1636 | 1486 |
| `rsqrt(4)` | 85 | 52 | 57 |
| `rsqrt(16)` | 85 | 52 | 57 |
| `rsqrt(1024)` | 83 | 50 | 55 |
| `rsqrt(65536)` | 85 | 53 | 60 |
| `rsqrt(1048576)` | 83 | 51 | 58 |
| `rsqrt(100)` | 1695 | 1957 | 2425 |
| `rsqrt(2)` | 86 | 53 | 59 |
| `rsqrt(10)` | 1811 | 2055 | 2619 |
| `rsqrt(42)` | 1733 | 1981 | 2482 |
| `rsqrt(12345)` | 1515 | 1972 | 2353 |
| `rsqrt(1000000)` | 1273 | 1812 | 1915 |
| `rsqrt(2000000000)` | 957 | 1752 | 1753 |
---
#### Analysis & Observations
- **Code Size:**
- Comparing `-Os` and `-Ofast`: `-Os` gives the smallest code size, and `-Ofast` is actually pretty decent too. But our hand-written version is way bigger simply because we didn't strip out the unused code.
- **Bottleneck Analysis:**
- We can see that `-Ofast` is slightly less efficient than our version on the `mul32` part, but it actually handles edge cases and lookups better. `-Os` takes a hit on `mul32`, but for the edge cases, it’s pretty much on par with `-Ofast`.
Sign in with Wallet
Connect another wallet