假设您有一个没有外部 RAM 的 8051 微 Controller 。内部 RAM 为 128 字节,您有大约 80 字节可用。并且您想为堆栈语言编写编译器。
假设你想编译一个 RPN 表达式 2 3 +
。 8051 有原生的 push
和 pop
指令,所以你可以写
push #2
push #3
然后你可以将
+
实现为:pop A ; pop 2 into register A
pop B ; pop 3 into register B
add A, B ; A = A + B
push A ; push the result on the stack
很简单吧?但在这种情况下,
+
是作为内联程序集实现的。如果你想重用这段代码,并把它放到一个子程序中怎么办?幸运的是,8051 有 lcall
和 ret
指令。 lcall LABEL
将返回地址压入堆栈并跳转到 LABEL,而 ret
返回到堆栈顶部指定的地址。然而,这些操作会干扰我们的堆栈,所以如果我们执行 lcall
跳转到我们的 +
实现,第一条指令 pop A
将弹出返回地址,而不是我们想要操作的值。在我们预先知道每个函数的参数数量的语言中,我们可以重新排列堆栈顶部的几个值并将参数放在堆栈顶部,并将返回地址进一步向下推。但是对于基于堆栈的语言,我们不知道每个函数需要多少个参数。
那么,在这些情况下可以采取哪些方法来实现函数调用?
下面是 8051 指令集描述:http://sites.fas.harvard.edu/~phys123/8051_refs/8051_instruc_set_ref.pdf
最佳答案
这是一台非常有限的机器。
好吧,最大的问题是你想用“堆栈”来保存操作数,但它也保存着返回地址。所以解决方法是:当返回地址妨碍时将返回地址移开,完成后将其放回原处。
你的例子:
push #2
push #3
lcall my_add
...
myadd:
pop r6 ; save the return address
pop r7
pop a
pop b
add a, b
push a
push r7
push r8
ret
我的猜测是“保存退货地址”,
“恢复退货地址”将非常普遍。我不知道如何对“保存返回地址”进行空间优化,但是您可以使大多数子例程的尾端通用:
myadd:
pop r6 ; save the return address
pop r7
pop a
pop b
add a, b
jmp push_a_return
...
; compiler library of commonly used code:
push_ab_return: ; used by subroutines that return answer in AB
push b
push_a_return: ; used by subroutines that return answer in A
push a
return: ; used by subroutines that don't produce a result in register
push r7
push r6
ret
push_b_return: ; used by subroutines that compute answer in B
push b
jmpshort return
但是,您的大部分麻烦似乎是坚持要将操作数压入堆栈。那么你在返回地址方面遇到了麻烦。您的编译器当然可以处理这个问题,但您遇到问题的事实表明您应该做其他事情,例如,如果可以帮助,请不要将操作数放在堆栈上。
相反,您的编译器也可以生成面向寄存器的代码,尽可能将操作数保存在寄存器中。毕竟,您有 8 个(我认为)R0..R7 以及 A 和 B 很容易访问。
所以你应该做的是,首先弄清楚所有的操作数(都由原始程序员命名,以及编译器需要的临时变量[比如 3 地址代码]和操作在你的代码中。第二,应用某种寄存器分配(查找寄存器着色作为一个很好的例子)来确定哪些操作数将在 R0..R7 中,应用相同的技术将未分配给寄存器的命名变量分配给您的直接可寻址(将它们分配给位置 8-'top' , 说), 第三次是你有一些额外空间的临时文件 (将它们的位置指定为 'top' 到 64). 这迫使其余的进入堆栈, 当它们生成时, 有位置 65 到 127. (坦率地说,我怀疑您最终会在堆栈中使用此方案,除非您的程序对于 8051 来说太大了)。
一旦每个操作数都有一个分配的位置,代码生成就很容易了。
如果操作数已分配在寄存器中,则使用 A、B 和算术适本地计算它,或者使用 MOV 来填充或存储它,如三地址指令所指示的那样。
如果操作数在堆栈上,则将其弹出到 A 或 B 如果在顶部;如果它在堆栈中“深入”嵌套,您可能会做一些奇特的寻址以到达其实际位置。如果生成的代码在被调用的子程序中并且操作数在堆栈中,则使用返回地址保存技巧;如果 R6 和 R7 忙,则将返回地址保存在另一个寄存器组中。对于每个子程序,您可能最多只需要保存一次返回值。
如果堆栈由交错的返回地址和变量组成,编译器实际上可以计算所需变量的位置,并使用堆栈指针的复杂索引来获取它。只有当您处理多个嵌套函数调用时才会发生这种情况;大多数 C 实现不允许这样做(GCC 允许)。所以你可以取缔这种情况,或者根据你的野心决定处理它。
所以对于程序(C风格)
byte X=2;
byte Y=3;
{ word Q=X*Y;
call W()
}
byte S;
W()
{ S=Q; }
我们可能会分配(使用寄存器分配算法)
X to R1
Y to location 17
Q to the stack
S to R3
并生成代码
MOV R1,2
MOV A, 3
MOV 17, A
MOV A, 17
MOV B, A
MOV A, R1
MUL
PUSH A ; Q lives on the stack
PUSH B
CALL W
POP A ; Q no longer needed
POP B
...
W:
POP R6
POP R7
POP A
POP B
MOV R3, B
JMP PUSH_AB_RETURN
你几乎可以得到合理的代码。
(蛮好玩的)。