为什么函数中的本地数组似乎会阻止尾调用优化？

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;
}

当变量1激活时，在结尾处会真正调用tco_test()（gcc试图在之前进行一些展开，但最终仍会调用该函数）。变量2按预期执行尾递归优化。

是否有本地数组中的某些内容使得无法优化尾递归调用？

- SergeyA

---

这不是一个尾调用。GCC仍然可以根据as-if规则转换调用并将其优化为类似尾调用的形式。 - Konrad Rudolph

你使用的是哪个版本的 GCC？你向编译器传递了哪些标志？ - Some programmer dude

此外，递归调用是另一个表达式的一部分，因此它实际上并不是尾调用。 - Some programmer dude

@JoachimPileborg，variant2 作为尾调用进行了优化。无论如何，切换到 return tco_test() 并没有什么区别，只是为了防止编译器认为我在那里存在未定义的行为。 - SergeyA

@KonradRudolph，请查看我对Joachim的回答。 - SergeyA

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实例。

- Kaz

---

不确定我是否理解。您在这种情况下所说的“外部foo”是什么意思？也许有一些说明性的代码？ - SergeyA

由于没有范围内的定义，无法内联调用 foo。 - Kaz

@KonradRudolph 我已经添加了一个说明性的例子，展示了导出局部变量地址如何创建程序语义，这会在常量空间递归下产生错误。 - Kaz

我不明白这个例子。在外部可见性方面，数组与单指针有何不同？我的 variant2 也可以采用 int* arr = &static_int_variable 的形式，并且仍然可以进行尾调用优化（当然，它是非法的）。也许您可以重新表述一下您的例子，使其更简洁，并强调数组在此处与指针的区别。 - SergeyA

@Kaz 我知道。就像我说的那样：在解释中，我只是简单地把“foo”误认为是递归函数。 - Konrad Rudolph