441 lines
6.8 KiB
ArmAsm
441 lines
6.8 KiB
ArmAsm
|
.text
|
||
|
|
.attribute 4, 16
|
||
|
|
.attribute 5, "rv64i2p0_m2p0_a2p0_f2p0_d2p0_c2p0"
|
||
|
|
.file "11_BST.sy"
|
||
|
|
.globl search
|
||
|
|
.p2align 1
|
||
|
|
.type search,@function
|
||
|
|
search:
|
||
|
|
li a7, -1
|
||
|
|
srli a6, a7, 32
|
||
|
|
beq a0, a7, .LBB0_6
|
||
|
|
lui a2, %hi(value)
|
||
|
|
addi a4, a2, %lo(value)
|
||
|
|
lui a2, %hi(left_child)
|
||
|
|
addi t0, a2, %lo(left_child)
|
||
|
|
lui a2, %hi(right_child)
|
||
|
|
addi a2, a2, %lo(right_child)
|
||
|
|
j .LBB0_3
|
||
|
|
.LBB0_2:
|
||
|
|
add a0, a0, a3
|
||
|
|
lw a0, 0(a0)
|
||
|
|
beq a0, a7, .LBB0_6
|
||
|
|
.LBB0_3:
|
||
|
|
sext.w a3, a0
|
||
|
|
slli a3, a3, 2
|
||
|
|
add a5, a3, a4
|
||
|
|
lw a5, 0(a5)
|
||
|
|
beq a5, a1, .LBB0_7
|
||
|
|
mv a0, a2
|
||
|
|
blt a5, a1, .LBB0_2
|
||
|
|
mv a0, t0
|
||
|
|
j .LBB0_2
|
||
|
|
.LBB0_6:
|
||
|
|
mv a0, a6
|
||
|
|
.LBB0_7:
|
||
|
|
sext.w a0, a0
|
||
|
|
ret
|
||
|
|
.Lfunc_end0:
|
||
|
|
.size search, .Lfunc_end0-search
|
||
|
|
|
||
|
|
.globl find_minimum
|
||
|
|
.p2align 1
|
||
|
|
.type find_minimum,@function
|
||
|
|
find_minimum:
|
||
|
|
li a2, -1
|
||
|
|
lui a1, %hi(left_child)
|
||
|
|
addi a3, a1, %lo(left_child)
|
||
|
|
.LBB1_1:
|
||
|
|
sext.w a1, a0
|
||
|
|
beq a1, a2, .LBB1_3
|
||
|
|
slli a0, a1, 2
|
||
|
|
add a0, a0, a3
|
||
|
|
lw a0, 0(a0)
|
||
|
|
bne a0, a2, .LBB1_1
|
||
|
|
.LBB1_3:
|
||
|
|
mv a0, a1
|
||
|
|
ret
|
||
|
|
.Lfunc_end1:
|
||
|
|
.size find_minimum, .Lfunc_end1-find_minimum
|
||
|
|
|
||
|
|
.globl new_node
|
||
|
|
.p2align 1
|
||
|
|
.type new_node,@function
|
||
|
|
new_node:
|
||
|
|
lui a2, %hi(now)
|
||
|
|
lw a1, %lo(now)(a2)
|
||
|
|
lui a3, %hi(value)
|
||
|
|
addi a3, a3, %lo(value)
|
||
|
|
slli a4, a1, 2
|
||
|
|
add a3, a3, a4
|
||
|
|
sw a0, 0(a3)
|
||
|
|
lui a0, %hi(left_child)
|
||
|
|
addi a0, a0, %lo(left_child)
|
||
|
|
add a0, a0, a4
|
||
|
|
li a3, -1
|
||
|
|
sw a3, 0(a0)
|
||
|
|
lui a0, %hi(right_child)
|
||
|
|
addi a0, a0, %lo(right_child)
|
||
|
|
add a0, a0, a4
|
||
|
|
sw a3, 0(a0)
|
||
|
|
addiw a0, a1, 1
|
||
|
|
sw a0, %lo(now)(a2)
|
||
|
|
mv a0, a1
|
||
|
|
ret
|
||
|
|
.Lfunc_end2:
|
||
|
|
.size new_node, .Lfunc_end2-new_node
|
||
|
|
|
||
|
|
.globl insert
|
||
|
|
.p2align 1
|
||
|
|
.type insert,@function
|
||
|
|
insert:
|
||
|
|
addi sp, sp, -32
|
||
|
|
sd ra, 24(sp)
|
||
|
|
sd s0, 16(sp)
|
||
|
|
sd s1, 8(sp)
|
||
|
|
li a2, -1
|
||
|
|
beq a0, a2, .LBB3_3
|
||
|
|
mv s0, a0
|
||
|
|
lui a0, %hi(value)
|
||
|
|
addi a0, a0, %lo(value)
|
||
|
|
slli a2, s0, 2
|
||
|
|
add a0, a0, a2
|
||
|
|
lw a0, 0(a0)
|
||
|
|
bge a0, a1, .LBB3_4
|
||
|
|
lui a0, %hi(right_child)
|
||
|
|
addi a0, a0, %lo(right_child)
|
||
|
|
j .LBB3_5
|
||
|
|
.LBB3_3:
|
||
|
|
lui a0, %hi(now)
|
||
|
|
lw s0, %lo(now)(a0)
|
||
|
|
lui a3, %hi(value)
|
||
|
|
addi a3, a3, %lo(value)
|
||
|
|
slli a4, s0, 2
|
||
|
|
add a3, a3, a4
|
||
|
|
sw a1, 0(a3)
|
||
|
|
lui a1, %hi(left_child)
|
||
|
|
addi a1, a1, %lo(left_child)
|
||
|
|
add a1, a1, a4
|
||
|
|
sw a2, 0(a1)
|
||
|
|
lui a1, %hi(right_child)
|
||
|
|
addi a1, a1, %lo(right_child)
|
||
|
|
add a1, a1, a4
|
||
|
|
sw a2, 0(a1)
|
||
|
|
addiw a1, s0, 1
|
||
|
|
sw a1, %lo(now)(a0)
|
||
|
|
j .LBB3_6
|
||
|
|
.LBB3_4:
|
||
|
|
lui a0, %hi(left_child)
|
||
|
|
addi a0, a0, %lo(left_child)
|
||
|
|
.LBB3_5:
|
||
|
|
slli a2, s0, 2
|
||
|
|
add s1, a2, a0
|
||
|
|
lw a0, 0(s1)
|
||
|
|
call insert
|
||
|
|
sw a0, 0(s1)
|
||
|
|
.LBB3_6:
|
||
|
|
mv a0, s0
|
||
|
|
ld ra, 24(sp)
|
||
|
|
ld s0, 16(sp)
|
||
|
|
ld s1, 8(sp)
|
||
|
|
addi sp, sp, 32
|
||
|
|
ret
|
||
|
|
.Lfunc_end3:
|
||
|
|
.size insert, .Lfunc_end3-insert
|
||
|
|
|
||
|
|
.globl delete
|
||
|
|
.p2align 1
|
||
|
|
.type delete,@function
|
||
|
|
delete:
|
||
|
|
addi sp, sp, -32
|
||
|
|
sd ra, 24(sp)
|
||
|
|
sd s0, 16(sp)
|
||
|
|
sd s1, 8(sp)
|
||
|
|
li a2, -1
|
||
|
|
beq a0, a2, .LBB4_3
|
||
|
|
mv s0, a0
|
||
|
|
lui a0, %hi(value)
|
||
|
|
addi a0, a0, %lo(value)
|
||
|
|
slli a2, s0, 2
|
||
|
|
add a3, a2, a0
|
||
|
|
lw a0, 0(a3)
|
||
|
|
bge a0, a1, .LBB4_4
|
||
|
|
lui a0, %hi(right_child)
|
||
|
|
addi a0, a0, %lo(right_child)
|
||
|
|
slli a2, s0, 2
|
||
|
|
add s1, a2, a0
|
||
|
|
lw a0, 0(s1)
|
||
|
|
j .LBB4_11
|
||
|
|
.LBB4_3:
|
||
|
|
srli a2, a2, 32
|
||
|
|
j .LBB4_12
|
||
|
|
.LBB4_4:
|
||
|
|
lui a2, %hi(left_child)
|
||
|
|
addi a2, a2, %lo(left_child)
|
||
|
|
slli a4, s0, 2
|
||
|
|
add s1, a4, a2
|
||
|
|
lw a2, 0(s1)
|
||
|
|
bge a1, a0, .LBB4_6
|
||
|
|
mv a0, a2
|
||
|
|
j .LBB4_11
|
||
|
|
.LBB4_6:
|
||
|
|
lui a0, %hi(right_child)
|
||
|
|
addi a0, a0, %lo(right_child)
|
||
|
|
add s1, a4, a0
|
||
|
|
lw a0, 0(s1)
|
||
|
|
li a1, -1
|
||
|
|
beq a2, a1, .LBB4_13
|
||
|
|
beq a0, a1, .LBB4_12
|
||
|
|
lui a1, %hi(left_child)
|
||
|
|
addi a1, a1, %lo(left_child)
|
||
|
|
li a2, -1
|
||
|
|
mv a5, a0
|
||
|
|
.LBB4_9:
|
||
|
|
slli a4, a5, 2
|
||
|
|
add a5, a4, a1
|
||
|
|
lw a5, 0(a5)
|
||
|
|
bne a5, a2, .LBB4_9
|
||
|
|
lui a1, %hi(value)
|
||
|
|
addi a1, a1, %lo(value)
|
||
|
|
add a1, a1, a4
|
||
|
|
lw a2, 0(a1)
|
||
|
|
sw a2, 0(a3)
|
||
|
|
lw a1, 0(a1)
|
||
|
|
.LBB4_11:
|
||
|
|
call delete
|
||
|
|
sw a0, 0(s1)
|
||
|
|
mv a2, s0
|
||
|
|
.LBB4_12:
|
||
|
|
sext.w a0, a2
|
||
|
|
ld ra, 24(sp)
|
||
|
|
ld s0, 16(sp)
|
||
|
|
ld s1, 8(sp)
|
||
|
|
addi sp, sp, 32
|
||
|
|
ret
|
||
|
|
.LBB4_13:
|
||
|
|
mv a2, a0
|
||
|
|
j .LBB4_12
|
||
|
|
.Lfunc_end4:
|
||
|
|
.size delete, .Lfunc_end4-delete
|
||
|
|
|
||
|
|
.globl inorder
|
||
|
|
.p2align 1
|
||
|
|
.type inorder,@function
|
||
|
|
inorder:
|
||
|
|
addi sp, sp, -48
|
||
|
|
sd ra, 40(sp)
|
||
|
|
sd s0, 32(sp)
|
||
|
|
sd s1, 24(sp)
|
||
|
|
sd s2, 16(sp)
|
||
|
|
sd s3, 8(sp)
|
||
|
|
sd s4, 0(sp)
|
||
|
|
li s2, -1
|
||
|
|
beq a0, s2, .LBB5_3
|
||
|
|
lui a1, %hi(left_child)
|
||
|
|
addi s3, a1, %lo(left_child)
|
||
|
|
lui a1, %hi(value)
|
||
|
|
addi s4, a1, %lo(value)
|
||
|
|
lui a1, %hi(right_child)
|
||
|
|
addi s1, a1, %lo(right_child)
|
||
|
|
.LBB5_2:
|
||
|
|
sext.w a0, a0
|
||
|
|
slli s0, a0, 2
|
||
|
|
add a0, s0, s3
|
||
|
|
lw a0, 0(a0)
|
||
|
|
call inorder
|
||
|
|
add a0, s0, s4
|
||
|
|
lw a0, 0(a0)
|
||
|
|
call putint
|
||
|
|
li a0, 32
|
||
|
|
call putch
|
||
|
|
add a0, s0, s1
|
||
|
|
lw a0, 0(a0)
|
||
|
|
bne a0, s2, .LBB5_2
|
||
|
|
.LBB5_3:
|
||
|
|
ld ra, 40(sp)
|
||
|
|
ld s0, 32(sp)
|
||
|
|
ld s1, 24(sp)
|
||
|
|
ld s2, 16(sp)
|
||
|
|
ld s3, 8(sp)
|
||
|
|
ld s4, 0(sp)
|
||
|
|
addi sp, sp, 48
|
||
|
|
ret
|
||
|
|
.Lfunc_end5:
|
||
|
|
.size inorder, .Lfunc_end5-inorder
|
||
|
|
|
||
|
|
.globl main
|
||
|
|
.p2align 1
|
||
|
|
.type main,@function
|
||
|
|
main:
|
||
|
|
addi sp, sp, -48
|
||
|
|
sd ra, 40(sp)
|
||
|
|
sd s0, 32(sp)
|
||
|
|
sd s1, 24(sp)
|
||
|
|
sd s2, 16(sp)
|
||
|
|
sd s3, 8(sp)
|
||
|
|
lui s2, %hi(now)
|
||
|
|
sw zero, %lo(now)(s2)
|
||
|
|
call getint
|
||
|
|
beqz a0, .LBB6_8
|
||
|
|
mv s3, a0
|
||
|
|
call getint
|
||
|
|
lw s0, %lo(now)(s2)
|
||
|
|
lui a1, %hi(value)
|
||
|
|
addi a1, a1, %lo(value)
|
||
|
|
slli a2, s0, 2
|
||
|
|
add a1, a1, a2
|
||
|
|
sw a0, 0(a1)
|
||
|
|
lui a0, %hi(left_child)
|
||
|
|
addi a0, a0, %lo(left_child)
|
||
|
|
add a0, a0, a2
|
||
|
|
li a1, -1
|
||
|
|
sw a1, 0(a0)
|
||
|
|
lui a0, %hi(right_child)
|
||
|
|
addi a0, a0, %lo(right_child)
|
||
|
|
add a0, a0, a2
|
||
|
|
sw a1, 0(a0)
|
||
|
|
addiw a0, s0, 1
|
||
|
|
li a1, 2
|
||
|
|
sw a0, %lo(now)(s2)
|
||
|
|
blt s3, a1, .LBB6_4
|
||
|
|
li s1, 1
|
||
|
|
.LBB6_3:
|
||
|
|
call getint
|
||
|
|
mv a1, a0
|
||
|
|
mv a0, s0
|
||
|
|
call insert
|
||
|
|
addiw s1, s1, 1
|
||
|
|
blt s1, s3, .LBB6_3
|
||
|
|
.LBB6_4:
|
||
|
|
mv a0, s0
|
||
|
|
call inorder
|
||
|
|
li a0, 10
|
||
|
|
call putch
|
||
|
|
call getint
|
||
|
|
blez a0, .LBB6_7
|
||
|
|
mv s2, a0
|
||
|
|
li s1, 0
|
||
|
|
.LBB6_6:
|
||
|
|
call getint
|
||
|
|
mv a1, a0
|
||
|
|
sext.w a0, s0
|
||
|
|
call delete
|
||
|
|
addiw s1, s1, 1
|
||
|
|
mv s0, a0
|
||
|
|
blt s1, s2, .LBB6_6
|
||
|
|
.LBB6_7:
|
||
|
|
mv a0, s0
|
||
|
|
call inorder
|
||
|
|
li a0, 10
|
||
|
|
call putch
|
||
|
|
.LBB6_8:
|
||
|
|
li a0, 0
|
||
|
|
ld ra, 40(sp)
|
||
|
|
ld s0, 32(sp)
|
||
|
|
ld s1, 24(sp)
|
||
|
|
ld s2, 16(sp)
|
||
|
|
ld s3, 8(sp)
|
||
|
|
addi sp, sp, 48
|
||
|
|
ret
|
||
|
|
.Lfunc_end6:
|
||
|
|
.size main, .Lfunc_end6-main
|
||
|
|
|
||
|
|
.type value,@object
|
||
|
|
.bss
|
||
|
|
.globl value
|
||
|
|
.p2align 2
|
||
|
|
value:
|
||
|
|
.zero 40000
|
||
|
|
.size value, 40000
|
||
|
|
|
||
|
|
.type right_child,@object
|
||
|
|
.globl right_child
|
||
|
|
.p2align 2
|
||
|
|
right_child:
|
||
|
|
.zero 40000
|
||
|
|
.size right_child, 40000
|
||
|
|
|
||
|
|
.type left_child,@object
|
||
|
|
.globl left_child
|
||
|
|
.p2align 2
|
||
|
|
left_child:
|
||
|
|
.zero 40000
|
||
|
|
.size left_child, 40000
|
||
|
|
|
||
|
|
.type now,@object
|
||
|
|
.section .sbss,"aw",@nobits
|
||
|
|
.globl now
|
||
|
|
.p2align 2
|
||
|
|
now:
|
||
|
|
.word 0
|
||
|
|
.size now, 4
|
||
|
|
|
||
|
|
.type _sysy_start,@object
|
||
|
|
.bss
|
||
|
|
.globl _sysy_start
|
||
|
|
.p2align 3
|
||
|
|
_sysy_start:
|
||
|
|
.zero 16
|
||
|
|
.size _sysy_start, 16
|
||
|
|
|
||
|
|
.type _sysy_end,@object
|
||
|
|
.globl _sysy_end
|
||
|
|
.p2align 3
|
||
|
|
_sysy_end:
|
||
|
|
.zero 16
|
||
|
|
.size _sysy_end, 16
|
||
|
|
|
||
|
|
.type _sysy_l1,@object
|
||
|
|
.globl _sysy_l1
|
||
|
|
.p2align 2
|
||
|
|
_sysy_l1:
|
||
|
|
.zero 4096
|
||
|
|
.size _sysy_l1, 4096
|
||
|
|
|
||
|
|
.type _sysy_l2,@object
|
||
|
|
.globl _sysy_l2
|
||
|
|
.p2align 2
|
||
|
|
_sysy_l2:
|
||
|
|
.zero 4096
|
||
|
|
.size _sysy_l2, 4096
|
||
|
|
|
||
|
|
.type _sysy_h,@object
|
||
|
|
.globl _sysy_h
|
||
|
|
.p2align 2
|
||
|
|
_sysy_h:
|
||
|
|
.zero 4096
|
||
|
|
.size _sysy_h, 4096
|
||
|
|
|
||
|
|
.type _sysy_m,@object
|
||
|
|
.globl _sysy_m
|
||
|
|
.p2align 2
|
||
|
|
_sysy_m:
|
||
|
|
.zero 4096
|
||
|
|
.size _sysy_m, 4096
|
||
|
|
|
||
|
|
.type _sysy_s,@object
|
||
|
|
.globl _sysy_s
|
||
|
|
.p2align 2
|
||
|
|
_sysy_s:
|
||
|
|
.zero 4096
|
||
|
|
.size _sysy_s, 4096
|
||
|
|
|
||
|
|
.type _sysy_us,@object
|
||
|
|
.globl _sysy_us
|
||
|
|
.p2align 2
|
||
|
|
_sysy_us:
|
||
|
|
.zero 4096
|
||
|
|
.size _sysy_us, 4096
|
||
|
|
|
||
|
|
.type _sysy_idx,@object
|
||
|
|
.section .sbss,"aw",@nobits
|
||
|
|
.globl _sysy_idx
|
||
|
|
.p2align 2
|
||
|
|
_sysy_idx:
|
||
|
|
.word 0
|
||
|
|
.size _sysy_idx, 4
|
||
|
|
|
||
|
|
.ident "Debian clang version 14.0.6"
|
||
|
|
.section ".note.GNU-stack","",@progbits
|
||
|
|
.addrsig
|