c++ - 为什么函数中的局部数组似乎可以防止 TCO？

Question

看起来你的函数中有一个本地数组会阻止在我检查过的所有编译器上对其进行尾调用优化:

int foo(int*);

int tco_test() {
    // int arr[5]={1, 2, 3, 4, 5}; // <-- variant 1
    // int* arr = new int[5]; // <-- variant 2
    int x = foo(arr);
    return x > 0 ? tco_test() : x;
}

当 variant 1 处于事件状态时，最终会真正调用 tco_test() (gcc 之前尝试做一些展开，但它仍然调用函数到底)。 变体 2 按预期执行 TCO。

本地数组中是否有某些东西导致无法优化尾调用？

Answer 1

如果编译器仍然执行 TCO，那么所有外部 foo(arr) 调用都会收到相同的指针。这是一个可见的语义变化，因此不再是纯粹的优化。

所讨论的局部变量是一个数组这一事实在这里可能是一个转移注意力的问题；重要的是它通过指针对外部的可见性。

考虑这个程序:

#include <stdio.h>

int *valptr[7], **curptr = valptr, **endptr = valptr + 7;

void reset(void)
{
  curptr = valptr;

}

int record(int *ptr)
{
  if (curptr >= endptr)
    return 1;
  *curptr++ = ptr;
  return 0;
}

int tally(void)
{
  int **pp;
  int count = 0;

  for (pp = valptr; pp < curptr; pp++)
    count += **pp;

  return count;
}

int tail_function(int x)
{
  return record(&x) ? tally() : tail_function(x + 1);
}

int main(void)
{
  printf("tail_function(0) = %d\n", tail_function(0));
  return 0;
}

随着 tail_function 递归，它通过尾调用执行，record 函数记录局部变量 x 的不同实例的地址>。当它用完空间时，它返回 1，这会触发 tail_function 调用 tally 并返回。 tally 扫描记录的内存位置并添加它们的值。

如果 tally 受 TCO 约束，那么将只有一个 x 实例。实际上，它会是这样的:

int tail_function(int x)
{
tail:
  if (record(&x))
    return tally();
  x = x + 1;
  goto tail;
}

所以现在，record 一遍又一遍地记录相同的位置，导致 tally 计算出一个错误的值，而不是预期的 21.

record 和 tally 的逻辑取决于 x 在作用域的每次激活时实际实例化，并且作用域的外部激活有一个持续到内在生命终止的生命。该要求阻止 tail_function 在常量空间中递归；它必须分配单独的 x 实例。