时间戳

首页 > 解决方案 > 为什么这个 Risc-V 二叉树检查器不起作用？

assembly - 为什么这个 Risc-V 二叉树检查器不起作用？

问题描述

我正在尝试编写一个 Risc-V 树检查器：每棵树的节点都由三个单词组成：

1) 0 或 1

2) 左节点地址

3) 右节点地址

我的程序应该探索树并返回第一个节点以 1 作为第一个单词的深度，这是代码：

.data
tree:   .word n01
n01:    .word 0, n02, n03
n02:    .word 0, n04, n05
n03:    .word 0, n06, n07
n04:    .word 0, 0, 0
n05:    .word 0, 0, 0
n06:    .word 1, 0, 0
n07:    .word 0, 0, 0
.text
    lw a0, tree
    jal altezza
    addi a0, a0, -1
    li a7, 1
    ecall
    li a7, 10
    ecall

altezza:
    bne a0, zero, altezza_ric  
    jalr zero, ra, 0    

altezza_ric:
    addi sp, sp, -12  
    lw t1, 0(a0)
    sw ra, 0(sp)    
    bne t1, zero, skip_numb

    sw a0, 4(sp)    
    lw a0, 4(a0)    
    jal altezza
    sw a0, 8(sp)    
    lw a0, 4(sp)    
    lw a0, 8(a0)    
    jal altezza

    lw t0, 8(sp)    
    bne a0, zero, scelta
    mv a0, t0
    bne a0, zero, scelta
    jal skip
scelta:
    ble a0,t0,skip_add
    mv a0, t0


skip_add:  
    addi a0, a0, 1  #ad a0 inremento 1
skip:   lw ra, 0(sp)
    addi sp, sp, 12 
    jalr zero, ra, 0    

skip_numb:
    add a0, zero, zero
    jal skip_add

标签： assemblybinary-treeriscv

解决方案

Try single stepping in the debugger to see if each instruction has the effect you want.

Make your initial test cases as small as possible, because debugging recursive functions can be very confusing.  So try it with just one node, for example; then just two nodes (e.g. a root node with a left; a root node with a right).

Eventually you'll see this:

lw a0, 4(sp)    <------- the result of this load is discarded
lw a0, 8(a0)

Here the first load is meaningless, because the a0 value it obtains is (immediately) overwritten by the second load.

    bne a0, zero, scelta
    jal skip
scelta:
    ble a0,t0,skip_add
    mv a0, t0
skip_add:

Don't use jal for simple branching, use j instead.  While here it doesn't hurt, it does update ra, which you don't want in the context of a simple if-then-else.  If you had a leaf function that doesn't save ra in the stack, this would be bad.

As this sequence has a conditional branch that jumps around an unconditional branch, this can be simplified to eliminate the unconditional branch and a label (scelta:) as follows:

    beq a0, zero, skip  <--- reverse the condition and branch to the other target
                        <--- eliminate/omit the unconditional branch and other label
    ble a0,t0,skip_add
    mv a0, t0
skip_add:

推荐阅读