编译器如何将函数消除应用于不纯函数？

Question

通常在编写代码时,我发现自己多次使用来自特定函数调用的值.我意识到明显的优化是在变量中捕获这些重复使用的值.这个(伪代码):

function add1(foo){ foo + 1; }
...
do_something(foo(1));
do_something_else(foo(1));

变为:

function add1(foo){ foo + 1; }
...
bar = foo(1);
do_something(bar);
do_something_else(bar);

但是,根据我的经验,这样做明确地使代码的可读性降低.如果我们选择的语言允许函数产生副作用,我认为编译器无法进行这种优化.

最近我调查了这个,如果我理解正确的话,这个优化是/可以用于函数必须纯粹的语言.这并不让我感到惊讶,但据说这也可以用于不纯的功能.通过一些快速的谷歌搜索,我发现了这些片段: GCC 4.7 Fortran改进

执行前端优化时,-faggressive-function-elimination选项允许删除重复的函数调用,即使对于不纯的函数也是如此.

编译器优化(维基百科)

例如,在某些语言中,不允许函数产生副作用.因此,如果程序使用相同的参数对同一函数进行多次调用,则编译器可以立即推断函数的结果只需要计算一次.在允许函数具有副作用的语言中,可以采用另一种策略.优化器可以确定哪个函数没有副作用,并将此类优化限制为无副作用函数.只有在优化程序可以访问被调用函数时,才能进行此优化.

根据我的理解,这意味着优化器可以确定函数何时是纯的,并在函数执行时执行此优化.我这样说是因为如果一个函数在给定相同的输入时总是产生相同的输出,并且没有副作用,那么它将满足两个条件被认为是纯粹的.

这两个片段为我提出了两个问题.

1. 如果函数不纯,编译器如何能够安全地进行优化？(作为in -faggressive-functional-elimination)
2. 编译器如何确定函数是否纯粹？(如维基百科文章中提出的策略)

最后:

• 这种优化是否可以应用于任何语言,或仅在满足某些条件时？
• 即使对于非常简单的功能,这种优化是否也是值得的？
• 存储和检索堆栈中的值会产生多少开销？

如果这些是愚蠢或不合逻辑的问题,我道歉.它们只是我最近一直很好奇的一些东西.:)

Answer 1

免责声明：我不是编译器/优化器人员，我只是倾向于查看生成的代码，并且喜欢阅读有关这些内容的内容 - 所以这不是权威的。快速搜索并没有发现太多有关 -faggressive-function-elimination 的信息，因此它可能会产生一些此处未解释的额外魔力。

优化器可以

• 尝试内联函数调用（使用链接时代码生成，这甚至可以跨编译单元工作）
• 执行公共子表达式消除，并且可能执行副作用重新排序。

稍微修改一下你的例子，并用 C++ 来做：

extern volatile int RW_A = 0;  // see note below

int foo(int a)  { return a * a; }
void bar(int x) { RW_A = x; }

int _tmain(int argc, _TCHAR* argv[])
{
   bar(foo(2));
   bar(foo(2));
}

解析为（伪代码）

<register> = 4;
RW_A = register;
RW_A = register;

（注意：读取和写入易失性变量是“可观察到的副作用”，优化器必须按照代码给出的相同顺序保留该副作用。）

修改示例以foo产生副作用：

extern volatile int RW_A = 0;
extern volatile int RW_B = 0;
int accu = 1;

int foo(int a)  { accu *= 2; return a * a; }
void bar(int x) { RW_A = x; }

int _tmain(int argc, _TCHAR* argv[])
{
   bar(foo(2));
   bar(foo(2));

   RW_B = accu;
   return 0;
}

生成以下伪代码：

registerA = accu;
registerA += registerA;
accu = registerA;

registerA += registerA;
registerC = 4;
accu = registerA;

RW_A = registerC;
RW_A = registerC;

RW_B = registerA;

我们观察到公共子表达式消除仍然完成，并且与副作用分开。内联和重新排序允许将副作用与“纯”部分分开。

请注意，编译器会读取并急切地写回accu，但这是不必要的。我不确定这里的理由。

总结一下：

编译器不需要测试纯度。它可以识别需要保留的副作用，然后将其余的转化为它喜欢的。

即使对于微不足道的功能，这样的优化也是值得的，因为除其他外，

• CPU和内存是共享资源，你使用的东西可能会从别人那里拿走
• 电池寿命
• 较小的优化可能是通向较大优化的途径

堆栈内存访问的开销通常约为 1 个周期，因为堆栈顶部通常已位于 1 级缓存中。请注意，通常应该以粗体显示：它可以“甚至更好”，因为读/写可能会被优化掉，或者它可能会更糟，因为 L1 缓存上增加的压力将一些其他重要数据刷新回 L2。

极限在哪里？

理论上，编译时间。在实践中，优化器的可预测性和正确性是额外的权衡。

所有测试均使用VC2008，默认优化设置为“Release”构建。