为什么函数中的本地数组似乎会阻止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试图进行一些展开操作，但最终仍会调用该函数)。Variant 2的总拥有成本与预期不谋而合。

是不是局部数组中的某些东西使得优化尾部调用变得不可能？

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受到总拥有成本的限制，那么将只有一个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实例。