相当不错的努力。
回答你的问题:你可以简单地在以下位置建立一个堆栈帧function
进入并最后从中恢复。
我确实必须重新调整用途$s0
稍微存储一个中间值并将其添加到堆栈帧中存储的值(即堆栈帧现在是 3 个字而不是 2 个)。
无论如何,这是更正后的代码。我尝试对其进行一些注释(IMO,在 asm 中,不存在“太多评论”这样的事情) [请原谅无偿的清理方式]:
.data
prompt1: .asciiz "Enter the value for the recursive function f(n) = 2f(n-1)+3f(n-2)+1: "
prompt2: .asciiz "Result: "
numberEntered: .word 0
answer: .word 0
.text
main:
# Ask for the value
li $v0,4
la $a0,prompt1
syscall
# enter value
li $v0,5
syscall
sw $v0,numberEntered # stores the number
# call the function
lw $a0,numberEntered
jal function
sw $v0,answer
# Print out the result
li $v0,4
la $a0,prompt2
syscall
lw $a0,answer
li $v0,1
syscall
li $v0,10
syscall
.globl function
# function -- calculation
# v0 -- return value
# a0 -- current n value
# s0 -- intermediate result
function:
subi $sp,$sp,12 # establish our stack frame
sw $ra,8($sp) # save return address
sw $a0,4($sp) # save n
sw $s0,0($sp) # save intermediate result
# base case
# NOTE: with the addition of n-2, the "beq" was insufficient
li $v0,1
ble $a0,$zero,done
# calling f(n-1)
sub $a0,$a0,1 # get n-1
jal function
# NOTE: these could be combined into a single instruction
mul $v0,$v0,2 # get 2f(n-1)
move $s0,$v0 # save it
# calling f(n-2)
sub $a0,$a0,1 # get n-2
jal function
mul $v0,$v0,3 # get 3f(n-2)
# get 2f(n-1) + 3f(n-2) + 1
add $v0,$s0,$v0
add $v0,$v0,1
done:
lw $ra,8($sp) # restore return address
lw $a0,4($sp) # restore n
lw $s0,0($sp) # restore intermediate result
addi $sp,$sp,12 # pop stack frame
jr $ra # returns
UPDATE:
这个解决方案比我想象的要简单得多。
这可能是因为堆栈帧在 asm [或 C] 中完成的方式所致。
考虑一个现代 C 程序:
int
whatever(int n)
{
int x;
// point A
x = other(1);
// do lots more stuff ...
{
// point B
int y = other(2);
// do lots more stuff ...
// point C
n *= (x + y);
}
// do lots more stuff ...
n += ...;
return n;
}
C编译器将在进入时建立一个堆栈帧whatever
将会保留space for x
and y
虽然y
只是set很久以后。大多数 C 程序员没有意识到这一点。
在解释语言中(例如java
, python
等)空间y
没有被保留until代码位于point B
is executed。而且,他们[通常]会在以下情况下取消分配它:y
“超出范围”[之后point C
].
大多数 C 程序员think具有作用域声明 [例如y
] 节省堆栈空间。 (即)在作用域块中,编译器将增加堆栈帧大小以适应y
并再次缩小它y
不再需要。
这简直就是not正确的。 C编译器将设置堆栈帧并为以下内容保留空间all函数作用域变量,即使它们是在函数后期或内部作用域内声明的 [例如y
].
这正是我们在您的项目中所做的function
。即使我们不需要/利用堆栈空间 [在偏移量 0 处] 也是如此$s0
直到函数的中间。
所以,我猜你使用其他语言的经历do动态地[有效地]保留空间,或者关于 C 的常识可能会引导您建立一个您认为需要的更复杂的模型。因此你原来的问题是:我必须“结束”堆栈两次吗?
我还应该提到的是function
is not符合 ABI。这是完美如果它是自包含的(即不调用其他任何东西)就很好。也就是说,在asm中,对于“叶子”函数,我们可以定义任何我们想要的。
原因是$a0
调用被修改/删除callee。我们从堆栈中保存/恢复它,但调用另一个函数可能会把事情搞砸。补救措施就是使用另一个寄存器来保存该值[或保存/恢复到堆栈帧中的额外位置],因此如果function
最终调用了其他东西。