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

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 improvement

When performing front-end-optimization, the -faggressive-function-elimination option allows the removal of duplicate function calls even for impure functions.

Compiler Optimization (Wikipedia)

For example, in some languages functions are not permitted to have side effects. Therefore, if a program makes several calls to the same function with the same arguments, the compiler can immediately infer that the function's result need be computed only once. In languages where functions are allowed to have side effects, another strategy is possible. The optimizer can determine which function has no side effects, and restrict such optimizations to side effect free functions. This optimization is only possible when the optimizer has access to the called function.

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

这两个片段向我提出了两个问题。

1. 如果函数不是纯函数，编译器如何能够安全地进行此优化？ (如-faggressive-function-elimination)
2. 编译器如何判断一个函数是否是纯函数？ (如维基百科文章中建议的策略)

最后:

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

如果这些是愚蠢或不合逻辑的问题，我深表歉意。它们只是我最近好奇的一些事情。 :)

Answer 1

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

<小时/>

优化器可以

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

稍微修改一下你的例子，并用 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;

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

<小时/>

修改 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;

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

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

<小时/>

总结:

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

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

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

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

极限在哪里？

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

<小时/>

所有测试均使用 VC2008，“发布”版本的默认优化设置。