基于自动变量的绝对最坏情况堆栈大小

Question

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

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

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

Answer 1

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

在堆栈帧中（几乎可以肯定）还有一些额外的开销（数据在调用时添加到堆栈并在 return 上释放）。您需要将所有函数声明为不带参数并 returning void 以确保堆栈中没有程序变量。最后 'return address' 在 return 被压入堆栈后（至少在逻辑上）继续执行函数。

所以在删除所有参数、自动变量和 return 值后 'state' struct 堆栈中仍然会有一些东西 - 可能。

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

您可以通过一大堆 goto 语句（某些条件语句从两个地方逻辑调用函数或通过复制代码来实现。

在内存很小的设备上的嵌入式代码中避免任何动态内存分配并知道任何 'stack-space' 永远不会溢出通常很重要。

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

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

Answer 2

Bonus question: If the assumptions above hold, I could simply declare all automatic variables static and would end up with a "truly" static program?

没有。这将改变程序的功能。 static 变量只初始化一次。比较这 2 个函数：

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

Answer 3

In a C99 program, under the (theoretical) assumption that I'm not using variable-length arrays, and each of my automatic variables can only exist once at a time in the whole stack (by forbidding circular function calls and explicit recursion), if I sum up all the space they are consuming, could I declare that this is the maximal stack size that can ever happen?

不，因为函数指针.....阅读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 suitably invoked with enough optimizations) would make a tail-recursive调用(*fptr)(x)。其他一些编译器不会。

根据您编译代码的方式，它将使用 bounded stack or could produce a stack overflow. With some ABI and calling conventions, both the argument and the result could go thru a processor register 并且不会消耗任何堆栈 space。

在 2020 年用最近的 GCC (e.g. on Linux/x86-64, some GCC 10 进行实验）调用为 gcc -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);
}

as gcc -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    , %eax    #, <retval>
    testl   %edi, %edi  # n
    jle .L1 #,
    .p2align 4,,10
    .p2align 3
   .L2:
    imull   %edi, %eax  # n, <retval>
    subl    , %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"

并且您可以观察到 call stack 并没有增加。

如果您有针对 GCC 的严肃且有据可查的论点，请提交 bug report。

顺便说一句，您可以编写自己的 GCC plugin 来选择随机应用或不应用此类优化。我相信它仍然符合 C 标准。

以上优化对于很多生成C代码的编译器来说都是必不可少的，比如Chicken/Scheme or Bigloo.

一个相关的定理是 Rice's theorem. See also this draft report funded by the CHARIOT 项目。

另请参阅 Compcert 项目。

基于自动变量的绝对最坏情况堆栈大小

Absolute worst case stack size based on automatic varaibles

c

static-analysis

dynamic-memory-allocation

static-memory-allocation

automatic-storage

并且您可以观察到 call stack 并没有增加。