展开框架,但不要在C中返回

Question

我的编程语言编译为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？

Answer 1

不要尝试自己这样做。一个好的 C 编译器可以在许多情况下执行尾调用消除，并且将会这样做。相比之下，使用内联汇编的黑客很可能会以难以调试的方式出错。

例如，请参阅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

请注意，尾调用已被消除。唯一的call就是puts。

Answer 2

我会建议一个黑客。call编译器使用x86指令来翻译函数调用，将返回地址压入堆栈，然后执行跳转。

您可以做的是一些堆栈操作，使用一些内联汇编和可能的一些宏来避免一些头痛。您基本上必须覆盖堆栈上的返回地址，您可以在调用的函数中立即执行此操作。您可以有一个包装器函数，它会覆盖返回地址并调用您的函数 - 然后控制流将返回到包装器，然后包装器移动到您指向的任何位置。