为何C/C++编译器无法优化该递归链表求和实验？

实验背景与测试用例 #

我在研究函数式编程技术、递归、常量性及链表相关内容时，设计了两个实验测试编译器性能。理论上编译器应能优化递归（注：后续发现提供的函数并非尾递归，其尾递归变体可在下方找到），在编译阶段直接得出结果，无需在运行时构建数据结构。

数组版本（符合预期优化） #

代码如下：

/**
 * @file test1.c
 */

static inline int my_array_sum(const int n, const int * const xs) {
    if (n == 0) {
        return n;
    } else {
        return n + my_array_sum(n - 1, xs + 1);
    }
}

int main(int argc, char **argv)
{    
    const int xs[] = {1, 2, 3, 4, 5, 6, 7, 8};
    const int n = 8;    
    const int sum = my_array_sum(n, xs); 

    return sum;
}

使用gcc test1.c -o test1.obj -c -O3编译，通过objdump -D test1.obj查看目标代码，在MinGW/MSys 64位和Linux Mint 64位环境下，main函数直接返回常量0x24（即36），完全符合编译期求值的预期。

栈上常量链表版本（未得到预期优化） #

代码如下：

/**
 * @file test2.c
 */

typedef struct Cons {
    const int x;
    const struct Cons * const next;
} Cons;

static inline int cons_sum(const Cons c) {
    if (c.next == 0) {
        return c.x;
    } else {
        return c.x + cons_sum(*(c.next));
    }
}

int main(int argc, char **argv)
{    
    // 构建栈上本地链表，尾节点为s0，头节点为h
    const Cons s0 = {8, 0};
    const Cons s1 = {7, &s0};
    const Cons s2 = {6, &s1};
    const Cons s3 = {5, &s2};
    const Cons s4 = {4, &s3};
    const Cons s5 = {3, &s4};
    const Cons s6 = {2, &s5};
    const Cons h = {1, &s6};    
    
    // 生成返回值（预期为36）
    const int sum = cons_sum(h); 

    return sum;
}

使用相同编译命令gcc test2.c -o test2.obj -c -O3后，反汇编结果显示编译器仍会在栈上构建链表结构，并执行循环/递归求和操作，未直接返回常量结果。同时测试了C和C++编译，反汇编结果基本一致。

问题 #

是C/C++标准明确规定此类栈上常量链表无法像数组那样被深度优化，还是当前编译器的技术限制未来可能改进，或是我遗漏了特定的优化编译标志？

解答 #

• C/C++标准无明确禁止：标准并未规定编译器不能对这种栈上常量链表进行编译期求值优化，仅要求优化行为符合“as-if”规则——只要程序可观察行为与未优化时一致，编译器可自由选择优化方式。
• 当前编译器的技术限制：
  • 数组内存布局连续且可预测，编译器能轻松识别元素访问模式，在编译期完成求和计算；而链表通过指针关联节点，即便所有节点都是栈上常量，编译器的数据流分析和常量传播逻辑处理这类链式结构的复杂度远高于数组。
  • 你的cons_sum函数按值传递结构体，每次递归都会复制结构体数据，这进一步干扰了编译器的编译期求值判断。若改为传递指针（const Cons* c），优化效果可能略有改善，但仍无法达到数组版本的完全编译期求值水平。
• 优化标志的尝试方向：
  • 除-O3外，可尝试添加-flto（链接时优化），让编译器在链接阶段进行全局分析，有可能识别链表的常量结构并完成优化，但实际测试中效果有限。
  • GCC的-fwhole-program（全程序优化）已被-flto替代，无需单独使用。
• 未来改进可能性：随着编译器优化技术（尤其是常量传播、数据流分析能力）的发展，未来主流编译器完全有可能支持这类栈上常量链表的编译期求值优化，目前已有实验性优化思路针对这类函数式风格结构，但尚未进入稳定版本。

内容的提问来源于stack exchange，提问作者Dmytro