assembly MIPS -如果$a0大于或等于1,如何进行分支和链接?

taor4pac  于 2023-02-08  发布在  其他
关注(0)|答案(1)|浏览(137)

我的程序有一个递归函数,它接受一个整数作为输入并打印n,n-1...1,0,0,1...n
下面是递归函数:

RDemo:
    
    addi $sp, $sp -4
    sw $ra, 0($sp)
    
    #print $a0
    li $v0, 1
    syscall
    
    addi $a0, $a0, -1
    bgezal $a0, RDemo
    addi $a0, $a0, 1
    li $v0, 1
    syscall
    
    lw $ra, 0($sp)
    addi $sp, $sp, 4
    jr $ra

问题是我需要它停在1而不是0
例如,如果输入为3,则应输出(3,2,1,1,2,3),而不是(3,2,1,0,0,1,2,3)
我使用bgezal指令(大于等于0时分支并链接)是因为它最接近我所需要的(大于等于1时分支并链接)。
据我所知,只有两个MIPS分支和链接指令。begzal和bltzal(分支如果小于和链接)
有没有一种方法可以完成我想做的事情,而不创建任何其他子程序?

egdjgwm8

egdjgwm81#

你可以使用普通的blez而不是无条件的bal(相对)或jal(绝对段);或者将你的计数器偏移1(到另一个寄存器中)以获得分支;或者在这种情况下将你的代码优化为2个循环而不是递归,不使用堆栈空间而不是O(n)空间。
不幸的是,slt不能直接与bgezal/bltzal一起工作,两者都只检查符号位,但是slt生成0或1,两者都是非负的。

RDemo:
    addi $sp, $sp -4
    sw $ra, 0($sp)
    
    #print $a0
    li $v0, 1
    syscall

    addi $t0, $a0, -2       # tmp = n-2
    addi $a0, $a0, -1       # n--
    bgezal $t0, RDemo       # if (n-1 >= 0) RDemo(n);
         # returns with $a0 unchanged, custom calling convention
    addi $a0, $a0, 1
    li $v0, 1
    syscall
    
    lw $ra, 0($sp)
    addi $sp, $sp, 4
    jr $ra

tmp = n-2在原来的n上,而不是tmp = new_n - 1,有更好的指令级并行性。一个CPU能够运行多个指令每周期可以并行运行这两个,因为它们之间没有RAW依赖关系。
在这种情况下,**n-1**可能不需要考虑整数溢出,我们只需比原始代码多一条指令,并且仍然使用条件b与链接,而不是围绕无条件调用进行分支。a0-1 >= 0将不同于a0 >= 1。由于我们使用addi而不是常规的addiu,因此这实际上将在有符号溢出时捕获,并且如果使用该参数调用-2147483647,则只打印-2147483647两次。不打印2^31次(或在递归堆栈溢出时实际停止。)
顺便说一句,您的“递归”使用的是自定义调用约定,其中调用“返回”$a0中的n,而标准MIPS调用约定中的返回值是$v0,和$a arg-passing寄存器被调用重写。https://godbolt.org/z/hrx4rdqaM显示了GCC如何使用堆栈空间来保存调用中传入的arg(如果您不使用t不要用返回值写入它。
这是介于迭代和递归之间的一种方法,在调用中保持寄存器,但是你可以用a0 = RDemo(a0)向C编译器描述它,因为只有一个参数。

MIPS32r6

如果你在为MIPS 32 r6MIPS manual from dec 2016)编程,BGTZALC rt, offset是可用的,它是一个完整的分支-链接集,带有任何常用的比较 predicate 。“C”代表“紧凑”-没有分支延迟槽。
真实的的MIPS确实有分支延迟槽,但您的代码看起来像是针对没有分支延迟槽的简化MIPS,否则addi $a0, $a0, 1将在被调用方之前运行。MIPS 32 r6删除了旧的bgezal,除了bgezal $zero情况,即无条件bal
MARS可以模拟MIPS 32,但不能模拟重组了一些操作码的MIPS 32 r6。(除了体系结构设计选择之外,MIPS 32 r6目前的兴趣有限;拥有伊萨的开发公司已经切换到RISC-V。)

相关问题