MIPS 中的数组递归
Recursion in MIPS with arrays
我是使用 MARS 进行 MIPS 语言编程的初学者。我开始研究递归，我在 java 中写了一个小方法，它接受一个数组和一个索引的输入，并对它的所有元素进行递归求和。但是我不知道用mips语言怎么写，有人可以帮我吗？
public int recursiveSum(int i, int[] array)
{
if(i == array.length-1)
return array[i];
return array[i]+recursiveSum(i+1, array);
}
当您在 mips 中创建递归函数时，您需要将 return 地址（寄存器 $ra）保存在您为函数调用的持续时间创建的堆栈帧上，恢复它在退出时（和 removing/popping 框架）。
简单的函数只需 $ra 的 save/restore 就可以达到最低限度，但是，对于递归函数，它们通常还必须 save/restore 一些参数。
除了 mips 指令集参考之外，您需要查阅的一件事是 mips ABI 文档，因为它列出了哪些寄存器在哪些上下文中用于哪些目的。这在编写递归代码时尤为重要。
这是一个通过单元测试实现您的功能的程序。它有两个不同的递归函数实现，以帮助说明您在 asm 中[可以做]的一些技巧。
请注意顶部评论中的原始函数和修改后的函数，该函数删除了 "non-standard" return 语句。也就是说，当使用高级语言作为 asm 的伪代码时，只需使用 single return 语句，因为这就是 asm 的实现方式。在 HLL 中保持简单很重要。越简单越直译为asm.
此外，有些事情您可以在 asm [特别是 mips] 中完成，而这些在 HLL 中是 done/modeled 无法做到的。 mips 有 32 个寄存器。想象一下，将不变值 [例如数组的地址] 放入 "global" 寄存器中，这些寄存器在所有调用中都会保留。该地址在 register 中，而不是在堆栈或全局 memory 中，因此它非常 快。
没有与此对应的 HLL。顺便说一句，如果你知道 C，我会在里面做伪代码而不是 java。 C 有指针 [和显式内存地址]，而 java 没有，指针是 asm.
无论如何，这是代码。它有很好的注释，因此，希望它易于阅读：
# recursive sum
#
#@+
# // original function:
# public int recursiveSum(int i, int[] array)
# {
#
# if (i == (array.length - 1))
# return array[i];
#
# return array[i] + recursiveSum(i + 1,array);
# }
#
# // function as it could be implemented:
# public int recursiveSum(int i, int[] array)
# {
# int ret;
#
# if (i == (array.length - 1))
# ret = 0;
# else
# ret = recursiveSum(i + 1,array);
#
# return array[i] + ret;
# }
#
# // function as it _was_ be implemented:
# public int[] array; // in a global register
#
# public int recursiveSum(int i)
# {
# int ret;
#
# if (i == (array.length - 1))
# ret = 0;
# else
# ret = recursiveSum(i + 1);
#
# return array[i] + ret;
# }
#@-
.data
sdata:
array:
.word 1,2,3,4,5,6,7,8,9,10
.word 11,12,13,14,15,16,17,18,19,20
.word 11,22,23,24,25,26,27,28,29,30
arrend:
msg_simple: .asciiz "simple sum is: "
msg_recur1: .asciiz "recursive sum (method 1) is: "
msg_recur2: .asciiz "recursive sum (method 2) is: "
msg_match: .asciiz "difference is: "
msg_nl: .asciiz "\n"
.text
.globl main
# main -- main program
#
# registers:
# s0 -- array count (i.e. number of integers/words)
# s1 -- array pointer
# s2 -- array count - 1
#
# s3 -- simple sum
# s4 -- recursive sum
main:
la $s1,array # get array address
la $s0,arrend # get address of array end
subu $s0,$s0,$s1 # get byte length of array
srl $s0,$s0,2 # count = len / 4
subi $s2,$s0,1 # save count - 1
# get simple sum for reference
jal sumsimple # get simple sum
move $s3,$v0 # save for compare
# show the simple sum results
la $a0,msg_simple
move $a1,$v0
jal showsum
# get recursive sum (method 1)
li $a0,0 # i = 0
jal sumrecurs1 # get recursive sum
move $s4,$v0 # save for compare
# show the recursive sum results
la $a0,msg_recur1
move $a1,$v0
jal showsum
# get recursive sum (method 2)
li $a0,0 # i = 0
jal sumrecurs2 # get recursive sum
# show the recursive sum results
la $a0,msg_recur2
move $a1,$v0
jal showsum
# show the difference in values between simple and method 1
subu $a1,$s4,$s3 # difference of values
la $a0,msg_match
jal showsum
# exit the program
li $v0,10
syscall
# sumsimple -- compute simple sum by looping through array
#
# RETURNS:
# v0 -- sum
#
# registers:
# t0 -- array count
# t1 -- array pointer
sumsimple:
move $t0,$s0 # get array count
move $t1,$s1 # get array address
li $v0,0 # sum = 0
j sumsimple_test
sumsimple_loop:
lw $t2,0($t1) # get array[i]
add $v0,$v0,$t2 # sum += array[i]
addi $t1,$t1,4 # advance pointer to array[i + 1]
subi $t0,$t0,1 # decrement count
sumsimple_test:
bgtz $t0,sumsimple_loop # are we done? if no, loop
jr $ra # return
# sumrecurs1 -- compute recursive sum
#
# RETURNS:
# v0 -- sum
#
# arguments:
# a0 -- array index (i)
# s1 -- array pointer
#
# NOTES:
# (1) in the mips ABI, the second argument is normally passed in a1 [which can
# be trashed] but we are using s1 as a "global" register
# (2) this saves an extra [and unnecessary push/pop to stack] as s1 _must_ be
# preserved
# (3) we do, however, preserve the array index (a0) on the stack
sumrecurs1:
# save return address and argument on a stack frame we setup
subiu $sp,$sp,8
sw $ra,0($sp)
sw $a0,4($sp)
blt $a0,$s2,sumrecurs1_call # at the end? if no, fly
li $v0,0 # yes, simulate call return of 0
j sumrecurs1_done # skip to function epilog
sumrecurs1_call:
addi $a0,$a0,1 # bump up the index
jal sumrecurs1 # recursive call
# get back the index we were called with from our stack frame
# NOTES:
# (1) while we _could_ just subtract one from a0 here because of the way
# sumrecurs is implemented, we _don't_ because, in general, under the
# standard mips ABI the called function is at liberty to _trash_ it
# (2) the index value restored in the epilog of our recursive function
# call is _not_ _our_ value "i", but "i + 1", so we need to get our
# "i" value from _our_ stack frame
# (3) see sumrecurs2 for the faster method where we "cheat" and violate
# the ABI
lw $a0,4($sp)
sumrecurs1_done:
sll $t2,$a0,2 # get byte offset for index i
add $t2,$s1,$t2 # get address of array[i]
lw $t2,0($t2) # fetch array[i]
add $v0,$t2,$v0 # sum our value and callee's
# restore return address from stack
lw $ra,0($sp)
lw $a0,4($sp)
addiu $sp,$sp,8
jr $ra
# sumrecurs2 -- compute recursive sum
#
# RETURNS:
# v0 -- sum
#
# arguments:
# a0 -- array index (i)
# s1 -- array pointer
#
# NOTES:
# (1) in the mips ABI, the second argument is normally passed in a1 [which can
# be trashed] but we are using s1 as a "global" register
# (2) this saves an extra [and unnecessary push/pop to stack] as s1 _must_ be
# preserved
# (3) we do, however, preserve the array index (a0) on the stack
sumrecurs2:
# save _only_ return address on a stack frame we setup
subiu $sp,$sp,4
sw $ra,0($sp)
blt $a0,$s2,sumrecurs2_call # at the end? if no, fly
li $v0,0 # yes, simulate call return of 0
j sumrecurs2_done # skip to function epilog
sumrecurs2_call:
addi $a0,$a0,1 # bump up the index
jal sumrecurs2 # recursive call
subi $a0,$a0,1 # bump down the index
sumrecurs2_done:
sll $t2,$a0,2 # get byte offset for index i
add $t2,$s1,$t2 # get address of array[i]
lw $t2,0($t2) # fetch array[i]
add $v0,$t2,$v0 # sum our value and callee's
# restore return address from stack
lw $ra,0($sp)
addiu $sp,$sp,4
jr $ra
# showsum -- output a message
#
# arguments:
# a0 -- message
# a1 -- number value
showsum:
li $v0,4 # puts
syscall
move $a0,$a1 # get number to print
li $v0,1 # prtint
syscall
la $a0,msg_nl
li $v0,4 # puts
syscall
jr $ra
我是使用 MARS 进行 MIPS 语言编程的初学者。我开始研究递归，我在 java 中写了一个小方法，它接受一个数组和一个索引的输入，并对它的所有元素进行递归求和。但是我不知道用mips语言怎么写，有人可以帮我吗？
public int recursiveSum(int i, int[] array)
{
if(i == array.length-1)
return array[i];
return array[i]+recursiveSum(i+1, array);
}
当您在 mips 中创建递归函数时，您需要将 return 地址（寄存器 $ra）保存在您为函数调用的持续时间创建的堆栈帧上，恢复它在退出时（和 removing/popping 框架）。
简单的函数只需 $ra 的 save/restore 就可以达到最低限度，但是，对于递归函数，它们通常还必须 save/restore 一些参数。
除了 mips 指令集参考之外，您需要查阅的一件事是 mips ABI 文档，因为它列出了哪些寄存器在哪些上下文中用于哪些目的。这在编写递归代码时尤为重要。
这是一个通过单元测试实现您的功能的程序。它有两个不同的递归函数实现，以帮助说明您在 asm 中[可以做]的一些技巧。
请注意顶部评论中的原始函数和修改后的函数，该函数删除了 "non-standard" return 语句。也就是说，当使用高级语言作为 asm 的伪代码时，只需使用 single return 语句，因为这就是 asm 的实现方式。在 HLL 中保持简单很重要。越简单越直译为asm.
此外，有些事情您可以在 asm [特别是 mips] 中完成，而这些在 HLL 中是 done/modeled 无法做到的。 mips 有 32 个寄存器。想象一下，将不变值 [例如数组的地址] 放入 "global" 寄存器中，这些寄存器在所有调用中都会保留。该地址在 register 中，而不是在堆栈或全局 memory 中，因此它非常 快。
没有与此对应的 HLL。顺便说一句，如果你知道 C，我会在里面做伪代码而不是 java。 C 有指针 [和显式内存地址]，而 java 没有，指针是 asm.
无论如何，这是代码。它有很好的注释，因此，希望它易于阅读：
# recursive sum
#
#@+
# // original function:
# public int recursiveSum(int i, int[] array)
# {
#
# if (i == (array.length - 1))
# return array[i];
#
# return array[i] + recursiveSum(i + 1,array);
# }
#
# // function as it could be implemented:
# public int recursiveSum(int i, int[] array)
# {
# int ret;
#
# if (i == (array.length - 1))
# ret = 0;
# else
# ret = recursiveSum(i + 1,array);
#
# return array[i] + ret;
# }
#
# // function as it _was_ be implemented:
# public int[] array; // in a global register
#
# public int recursiveSum(int i)
# {
# int ret;
#
# if (i == (array.length - 1))
# ret = 0;
# else
# ret = recursiveSum(i + 1);
#
# return array[i] + ret;
# }
#@-
.data
sdata:
array:
.word 1,2,3,4,5,6,7,8,9,10
.word 11,12,13,14,15,16,17,18,19,20
.word 11,22,23,24,25,26,27,28,29,30
arrend:
msg_simple: .asciiz "simple sum is: "
msg_recur1: .asciiz "recursive sum (method 1) is: "
msg_recur2: .asciiz "recursive sum (method 2) is: "
msg_match: .asciiz "difference is: "
msg_nl: .asciiz "\n"
.text
.globl main
# main -- main program
#
# registers:
# s0 -- array count (i.e. number of integers/words)
# s1 -- array pointer
# s2 -- array count - 1
#
# s3 -- simple sum
# s4 -- recursive sum
main:
la $s1,array # get array address
la $s0,arrend # get address of array end
subu $s0,$s0,$s1 # get byte length of array
srl $s0,$s0,2 # count = len / 4
subi $s2,$s0,1 # save count - 1
# get simple sum for reference
jal sumsimple # get simple sum
move $s3,$v0 # save for compare
# show the simple sum results
la $a0,msg_simple
move $a1,$v0
jal showsum
# get recursive sum (method 1)
li $a0,0 # i = 0
jal sumrecurs1 # get recursive sum
move $s4,$v0 # save for compare
# show the recursive sum results
la $a0,msg_recur1
move $a1,$v0
jal showsum
# get recursive sum (method 2)
li $a0,0 # i = 0
jal sumrecurs2 # get recursive sum
# show the recursive sum results
la $a0,msg_recur2
move $a1,$v0
jal showsum
# show the difference in values between simple and method 1
subu $a1,$s4,$s3 # difference of values
la $a0,msg_match
jal showsum
# exit the program
li $v0,10
syscall
# sumsimple -- compute simple sum by looping through array
#
# RETURNS:
# v0 -- sum
#
# registers:
# t0 -- array count
# t1 -- array pointer
sumsimple:
move $t0,$s0 # get array count
move $t1,$s1 # get array address
li $v0,0 # sum = 0
j sumsimple_test
sumsimple_loop:
lw $t2,0($t1) # get array[i]
add $v0,$v0,$t2 # sum += array[i]
addi $t1,$t1,4 # advance pointer to array[i + 1]
subi $t0,$t0,1 # decrement count
sumsimple_test:
bgtz $t0,sumsimple_loop # are we done? if no, loop
jr $ra # return
# sumrecurs1 -- compute recursive sum
#
# RETURNS:
# v0 -- sum
#
# arguments:
# a0 -- array index (i)
# s1 -- array pointer
#
# NOTES:
# (1) in the mips ABI, the second argument is normally passed in a1 [which can
# be trashed] but we are using s1 as a "global" register
# (2) this saves an extra [and unnecessary push/pop to stack] as s1 _must_ be
# preserved
# (3) we do, however, preserve the array index (a0) on the stack
sumrecurs1:
# save return address and argument on a stack frame we setup
subiu $sp,$sp,8
sw $ra,0($sp)
sw $a0,4($sp)
blt $a0,$s2,sumrecurs1_call # at the end? if no, fly
li $v0,0 # yes, simulate call return of 0
j sumrecurs1_done # skip to function epilog
sumrecurs1_call:
addi $a0,$a0,1 # bump up the index
jal sumrecurs1 # recursive call
# get back the index we were called with from our stack frame
# NOTES:
# (1) while we _could_ just subtract one from a0 here because of the way
# sumrecurs is implemented, we _don't_ because, in general, under the
# standard mips ABI the called function is at liberty to _trash_ it
# (2) the index value restored in the epilog of our recursive function
# call is _not_ _our_ value "i", but "i + 1", so we need to get our
# "i" value from _our_ stack frame
# (3) see sumrecurs2 for the faster method where we "cheat" and violate
# the ABI
lw $a0,4($sp)
sumrecurs1_done:
sll $t2,$a0,2 # get byte offset for index i
add $t2,$s1,$t2 # get address of array[i]
lw $t2,0($t2) # fetch array[i]
add $v0,$t2,$v0 # sum our value and callee's
# restore return address from stack
lw $ra,0($sp)
lw $a0,4($sp)
addiu $sp,$sp,8
jr $ra
# sumrecurs2 -- compute recursive sum
#
# RETURNS:
# v0 -- sum
#
# arguments:
# a0 -- array index (i)
# s1 -- array pointer
#
# NOTES:
# (1) in the mips ABI, the second argument is normally passed in a1 [which can
# be trashed] but we are using s1 as a "global" register
# (2) this saves an extra [and unnecessary push/pop to stack] as s1 _must_ be
# preserved
# (3) we do, however, preserve the array index (a0) on the stack
sumrecurs2:
# save _only_ return address on a stack frame we setup
subiu $sp,$sp,4
sw $ra,0($sp)
blt $a0,$s2,sumrecurs2_call # at the end? if no, fly
li $v0,0 # yes, simulate call return of 0
j sumrecurs2_done # skip to function epilog
sumrecurs2_call:
addi $a0,$a0,1 # bump up the index
jal sumrecurs2 # recursive call
subi $a0,$a0,1 # bump down the index
sumrecurs2_done:
sll $t2,$a0,2 # get byte offset for index i
add $t2,$s1,$t2 # get address of array[i]
lw $t2,0($t2) # fetch array[i]
add $v0,$t2,$v0 # sum our value and callee's
# restore return address from stack
lw $ra,0($sp)
addiu $sp,$sp,4
jr $ra
# showsum -- output a message
#
# arguments:
# a0 -- message
# a1 -- number value
showsum:
li $v0,4 # puts
syscall
move $a0,$a1 # get number to print
li $v0,1 # prtint
syscall
la $a0,msg_nl
li $v0,4 # puts
syscall
jr $ra