c++ - 为什么函数中的局部数组似乎会阻止TCO？

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

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处于 Activity 状态时，最终会真正调用tco_test()(gcc会在之前进行一些展开，但最终仍会调用该函数)。 Variant 2按预期进行TCO。

局部数组中是否存在无法优化尾调用的内容？

最佳答案

如果编译器执行了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的逻辑取决于Scopet每次激活时实际实例化的x，并且范围的外部激活具有一个生存期，该生存期一直持续到内部的激活终止为止。该要求阻止了tail_function在恒定空间中递归；它必须分配单独的x实例。