0

在 C99 程序中，在（理论上）假设我没有使用可变长度数组，并且我的每个自动变量在整个堆栈中一次只能存在一次（通过禁止循环函数调用和显式递归），如果我总结他们消耗的所有空间，我可以声明这是可能发生的最大堆栈大小吗？

这里有一点上下文：我告诉一个朋友，我编写了一个程序，不使用动态内存分配（“malloc”）并分配所有内存静态（通过在一个结构中建模我的所有状态变量，然后我将其声明为全局）。然后他告诉我，如果我使用自动变量，我仍然会使用动态内存。我认为我的自动变量不是状态变量而是控制变量，所以我的程序仍然被认为是静态的。然后我们讨论了必须有一种方法来说明我的程序的绝对最坏情况行为，所以我提出了上述问题。

额外的问题：如果上述假设成立，我可以简单地将所有自动变量声明为静态并最终得到一个“真正的”静态程序？

4

3 回答 3

2

即使数组大小是恒定的，C 实现也可以动态分配数组甚至结构。我不知道有任何人（任何人）这样做，而且看起来毫无帮助。但是 C 标准并没有做出这样的保证。

堆栈帧中还有（几乎可以肯定）一些进一步的开销（数据在调用时添加到堆栈并在返回时释放）。您需要将所有函数声明为不带参数并返回void以确保堆栈中没有程序变量。最后，在将返回推入堆栈后（至少在逻辑上），函数将继续执行的“返回地址”。

因此，在删除了所有参数、自动变量和返回值给你的“状态”struct之后，堆栈中仍然会有一些事情发生 - 可能。

我说可能是因为我知道一个（非标准）嵌入式 C 编译器禁止递归，它可以stack通过检查整个程序的调用树并识别达到 peek 大小的调用链来确定最大大小堆。

你可以通过一堆可怕的goto语句来实现这一点（一些条件是从两个地方逻辑调用函数或通过复制代码。

在具有微小内存的设备上的嵌入式代码中，避免任何动态内存分配并知道任何“堆栈空间”永远不会溢出，这通常很重要。

我很高兴这是一个理论讨论。您建议的是一种疯狂的代码编写方式，并且会丢弃 C 提供给程序编码基础设施的大部分（最终有限的）服务（几乎是调用堆栈）

脚注：请参阅下面有关 8 位 PIC 架构的评论。

于 2020-11-27T13:10:36.703 回答
1

额外的问题：如果上述假设成立，我可以简单地将所有自动变量声明为静态并最终得到一个“真正的”静态程序？

不会。这会改变程序的功能。static变量只初始化一次。比较这两个功能：

int canReturn0Or1(void)
{
  static unsigned a=0;
  a++;
  if(a>1)
  {
    return 1;
  }
  return 0;
}

int willAlwaysReturn0(void)
{
  unsigned a=0;
  a++;
  if(a>1)
  {
    return 1;
  }
  return 0;
}
于 2020-11-27T13:24:15.580 回答
0

在 C99 程序中，在（理论上）假设我没有使用可变长度数组，并且我的每个自动变量在整个堆栈中一次只能存在一次（通过禁止循环函数调用和显式递归），如果我总结他们消耗的所有空间，我可以声明这是可能发生的最大堆栈大小吗？

不，因为函数指针.....阅读n1570。

考虑以下代码，其中rand(3)是一些伪随机数生成器（也可能是来自传感器的一些输入）：

typedef int foosig(int);
int foo(int x) {
   foosig* fptr = (x>rand())?&foo:NULL;
   if (fptr) 
     return (*fptr)(x);
   else
     return x+rand();
}

一个优化编译器（例如一些最近适当调用的具有足够优化的GCC）将对(*fptr)(x). 其他一些编译器不会。

根据您编译该代码的方式，它将使用有界堆栈或可能产生堆栈溢出。使用一些ABI和调用约定，参数和结果都可以通过处理器寄存器，并且不会消耗任何堆栈空间。

尝试调用最近的 GCC（例如在 Linux/x86-64 上，2020 年的一些GCC 10gcc -O2 -fverbose-asm -S foo.c ），然后查看内部foo.s。将 更改-O2为-O0.

观察到，可以使用足够好的 C 编译器和优化器将朴素的递归阶乘函数编译成一些迭代机器代码。实际上，Linux 上的 GCC 10 编译以下代码：

int fact(int n)
{
  if (n<1) return 1;
  else return n*fact(n-1);
}

asgcc -O3 -fverbose-asm tmp/fact.c -S -o tmp/fact.s产生以下汇编代码：

    .type   fact, @function
   fact:
   .LFB0:
    .cfi_startproc
    endbr64 
   # tmp/fact.c:3:   if (n<1) return 1;
    movl    $1, %eax    #, <retval>
    testl   %edi, %edi  # n
    jle .L1 #,
    .p2align 4,,10
    .p2align 3
   .L2:
    imull   %edi, %eax  # n, <retval>
    subl    $1, %edi    #, n
    jne .L2 #,
   .L1:
   # tmp/fact.c:5: }
    ret 
    .cfi_endproc
   .LFE0:
    .size   fact, .-fact
    .ident  "GCC: (Ubuntu 10.2.0-5ubuntu1~20.04) 10.2.0"

您可以观察到调用堆栈没有在上面增加。

如果您对 GCC 有严肃且有据可查的论据，请提交错误报告。

顺便说一句，您可以编写自己的GCC 插件，该插件会选择随机应用或不应用这种优化。我相信它仍然符合 C 标准。

上述优化对于许多生成 C 代码的编译器是必不可少的，例如Chicken/Scheme或Bigloo。

一个相关的定理是赖斯定理。另请参阅由CHARIOT项目资助的这份报告草案。

另请参阅Compcert项目。

于 2020-11-27T13:32:15.807 回答