我的编程语言编译为 C,我想实现尾递归优化。这里的问题是如何在不从当前函数“返回”的情况下将控制权传递给另一个函数。
如果将控件传递给同一个函数就很容易了:
void f() {
__begin:
do something here...
goto __begin; // "call" itself
}
如您所见,没有返回值也没有参数,它们在一个由全局变量寻址的单独堆栈中传递。
另一种选择是使用内联汇编:
#ifdef __clang__
#define tail_call(func_name) asm("jmp " func_name " + 8");
#else
#define tail_call(func_name) asm("jmp " func_name " + 4");
#endif
void f() {
__begin:
do something here...
tail_call(f); // "call" itself
}
这与 goto
类似,但 goto 将控制权传递给函数中的第一条语句,跳过编译器生成的“入口代码”,jmp
不同,它的参数是一个函数指针,你需要添加4或8个字节来跳过入口代码。
以上两者都可以工作,但前提是被调用者和调用者对由被调用者的入口代码分配的局部变量使用相同数量的堆栈。
我想用内联汇编手动执行 leave
,然后替换堆栈上的返回地址,然后执行 legal
函数调用,如 f()
。但是我的尝试都失败了。您需要以某种方式修改 BP
和 SP
。
那么,如何为 x64 实现这个呢? (同样,假设函数没有参数并返回 void
)。没有内联汇编的便携方式更好,但汇编是可以接受的。也许可以使用longjump
?
也许您甚至可以将被调用者地址压入堆栈,替换原来的返回地址,然后只是ret
?
最佳答案
不要尝试自己做。一个好的 C 编译器可以在许多情况下执行尾调用消除,并且会这样做。相比之下,使用内联汇编的 hack 很可能会以难以调试的方式出错。
例如,参见 this snippet在 godbolt.org 上。要在此处复制它:
我使用的 C 代码是:
int foo(int n, int o)
{
if (n == 0) return o;
puts("***\n");
return foo(n - 1, o + 1);
}
编译为:
.LC0:
.string "***\n"
foo:
test edi, edi
je .L4
push r12
mov r12d, edi
push rbp
mov ebp, esi
push rbx
mov ebx, edi
.L3:
mov edi, OFFSET FLAT:.LC0
call puts
sub ebx, 1
jne .L3
lea eax, [r12+rbp]
pop rbx
pop rbp
pop r12
ret
.L4:
mov eax, esi
ret
请注意尾调用已被删除。唯一的调用
是puts
。
关于c - 展开框架但不在 C 中返回,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48646517/