提问人：Eric 提问时间：11/27/2020 最后编辑：Jonathan LefflerEric 更新时间：11/27/2020 访问量：205
基于自动可变值的绝对最坏情况堆栈大小
Absolute worst case stack size based on automatic varaibles
问：
在 C99 程序中，在（理论上）假设我没有使用可变长度数组，并且我的每个自动变量在整个堆栈中一次只能存在一次（通过禁止循环函数调用和显式递归），如果我总结它们消耗的所有空间，我可以声明这是可能发生的最大堆栈大小吗？
这里有一些上下文：我告诉一个朋友，我编写了一个不使用动态内存分配（“malloc”）的程序，并分配所有静态内存（通过在结构中对我的所有状态变量进行建模，然后我将其声明为全局变量）。然后他告诉我，如果我使用自动变量，我仍然会使用动态内存。我认为我的自动变量不是状态变量，而是控制变量，所以我的程序仍然被认为是静态的。然后我们讨论了必须有一种方法可以对我的程序的绝对最坏情况行为做出声明，所以我提出了上述问题。
奖励问题：如果上面的假设成立，我可以简单地将所有自动变量声明为静态，并最终得到一个“真正”静态的程序？
答：
2赞
Persixty
11/27/2020
#1
即使数组大小是恒定的，C 实现也可以动态分配数组甚至结构。我不知道有没有人这样做（任何人），这似乎很有帮助。但是C标准并没有做出这样的保证。
堆栈帧中（几乎可以肯定）还有一些进一步的开销（在调用时添加到堆栈并在返回时释放的数据）。
您需要将所有函数声明为不带参数并返回以确保堆栈中没有程序变量。最后，返回被推送到堆栈上后，函数的“返回地址”将继续执行（至少在逻辑上）。void
因此，在删除了所有参数、自动变量并将值返回给你的“状态”之后，堆栈仍然会有一些事情发生——可能。struct
我之所以这么说，可能是因为我知道有一个（非标准的）嵌入式 C 编译器，它禁止递归，它可以通过检查整个程序的调用树来确定最大大小，并确定达到堆栈速览大小的调用链。stack
你可以通过一堆可怕的语句来实现这一点（一些条件语句，其中函数从两个地方逻辑地调用或通过复制代码。goto
在具有微小内存的设备上的嵌入式代码中，避免任何动态内存分配并知道任何“堆栈空间”永远不会溢出通常很重要。
我很高兴这是一个理论讨论。你建议的是一种疯狂的代码编写方式，并且会抛弃 C 为过程编码基础设施（几乎是调用堆栈）提供的大部分（最终是有限的）服务
脚注：请参阅下面有关 8 位 PIC 体系结构的评论。
评论
1赞
12431234123412341234123
11/27/2020
有些体系结构（如 8 位 PIC）不使用完整堆栈，而是只能保存返回地址。这不允许递归。所有需要的内存在编译结束时就知道了。
0赞
Persixty
11/27/2020
感谢您的引用。我只是通过有一个使用过这种嵌入式设备的朋友来了解它们。它很可能是PIC。在一些古老的BASIC方言中，这并不遥远。GOSUBRETURN
0赞
Eric
11/28/2020
该程序实际上是为嵌入式设备 （esp32） 编写的。我们在学校里了解到嵌入式设备上的动态分配“很糟糕”，因此我和我的朋友开始讨论自动可变配置与动态内存分配的关系。最终，自动变量不是另一个动态的，我们应该尽量避免它吗？我可以说我的程序不使用动态内存，即使自动变量似乎在某种程度上是动态的吗？我指的不是动态堆内存，而是“更通用的动态内存”。
1赞
Persixty
11/28/2020
在某种程度上，自动变量是动态分配的。但它们是在堆栈上分配的。当我们谈论动态内存分配时，我们通常谈论的是堆分配和 。在嵌入式中，它不是首选，因为它有开销，并且通常很难证明当所有内容都“最大化”时可能会耗尽内存。大多数嵌入式应用程序都是以固定大小构建的，用于所有东西（有多少个传感器、气缸、喷气发动机！）或需要多少个“先前”读数。...malloc()free()
2赞
12431234123412341234123
11/28/2020
@Eric 看到这个问题 stackoverflow.com/questions/6387614/...
1赞
12431234123412341234123
11/27/2020
#2
奖励问题：如果上述假设成立，我可以简单地声明 所有自动变量都是静态的，最终会得到一个“真正”的静态变量 程序？
不。这将改变程序的功能。 变量仅初始化一次。
比较这 2 个函数：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;
}
评论
0赞
Eric
11/28/2020
好点子...但是如果我写“静态无符号 a=0;a=0;“？所以在第二次调用时显式将其设置为 0？
0赞
12431234123412341234123
12/1/2020
@Eric Thin 也是一样的，当你有一个中断访问同一个函数时，你使用超过 1 个线程或你有递归。
0赞
Basile Starynkevitch
11/27/2020
#3
在 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 10）调用，然后查看内部。将 更改为 .gcc -O2 -fverbose-asm -S foo.cfoo.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 $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 项目。
评论
malloc()