C和C++优化器通常知道哪些函数没有副作用？

Question

比如非常常见的数学函数,例如sin,cos等等...编译器是否意识到它们没有副作用并且能够将它们移动到外部循环？例如

// Unoptimized

double YSinX(double x,int y)
{
   double total = 0.0;
   for (int i = 0; i < y; i++)
      total += sin(x);
   return total;
}

// Manually optimized

double YSinX(double x,int y)
{
   double total = 0.0, sinx = sin(x);
   for (int i = 0; i < y; i++)
      total += sinx;
   return total;
}

如果他们可以,有没有办法声明一个函数没有副作用,因此可以安全地以这种方式进行优化？VS2010应用程序的初始分析表明优化是有益的.

另请参阅这个相关的问题,这个问题很接近但不能完全回答我自己的问题.

编辑:一些很棒的答案.我接受的那个基于它作为答案本身引起的评论,特别是链接的文章,以及在errno设定的情况下(即副作用)可能不会发生提升的事实.因此,在我正在做的事情的背景下,这种类型的手动优化似乎仍然有意义.

Answer 1

GCC具有两个属性,pure并且const,可被用来标记这样的功能.如果函数没有副作用且其结果仅取决于其参数,则应声明函数const,如果结果也可能依赖于某些全局变量,则应声明函数pure.最新版本还有一个-Wsuggest-attribute 警告选项,可以指出应该声明的函数const或pure.

Answer 2

事实上,今天常见的编译器将执行你所询问的循环不变代码运动优化.为了证明这一点,请参阅本文中题为"它会优化吗？"的第二个练习.,或者使用gcc -S -O3和/或clang -S -O3组装下面的例子并检查汇编中的main入口点,就像我出于好奇一样.如果您的VS2010编译器没有执行此优化,则无关紧要; llvm/clang"与MSVC 2010,2012,2013和14 CTP集成".

从理论上看,这两个引号解释了编译器在执行优化时的范围或余量.它们来自C11标准.IIRC C++ 11有类似之处.

§5.1.2.3p4:

在抽象机器中,所有表达式都按语义指定进行计算.实际实现不需要评估表达式的一部分,如果它可以推断出它的值未被使用并且不产生所需的副作用(包括由调用函数或访问易失性对象引起的任何副作用).

§5.1.2.3p6:

符合实施的最低要求是:

- 严格根据抽象机器的规则评估对易失性对象的访问.

- 在程序终止时,写入文件的所有数据应与根据抽象语义产生的程序执行的结果相同.

- 交互设备的输入和输出动态应按照7.21.3的规定进行.这些要求的目的是尽快出现无缓冲或行缓冲输出,以确保在程序等待输入之前实际出现提示消息.

这是该程序的可观察行为.

因此,编译器可以将整个程序提升到编译时评估中,如果可以的话.考虑以下程序,例如:

#include <math.h>
#include <stdio.h>

double YSinX(double x,int y)
{
    double total = 0.0;
    for (int i = 0; i < y; i++)
        total += sin(x);
    return total;
}

int main(void) {
    printf("%f\n", YSinX(M_PI, 4));
}

您的编译器可能会意识到此程序0.0\n每次都会打印,并将您的程序优化为:

int main(void) { puts("0.0"); }

也就是说,提供您的编译器可以证明既sin不会YsinX产生任何所需的副作用.请注意,它们可能(并且可能确实)仍然会产生副作用,但它们不需要生成此程序的输出.

为了演示在实践中应用的理论知识,我通过在我的Windows 10系统上组装(使用/ )上面的代码测试了llvm/clang(3.8.0 from clang --version)和gcc(6.4.0 from gcc --version),这两个编译器都有效地应用了优化如上所述; 在实践中,您可以期望从上面的示例转换为相当于的机器代码.gcc -S -O3clang -S -O3mainint main(void) { printf("%f", 0.0); }

你问了一个关于"编译器"的问题.如果您指的是所有C或C++实现,则无法保证优化,并且C实现甚至不需要是编译器.您需要告诉我们哪个特定的C或C++实现 ; 正如我上面解释的那样,LLVM/Clang"与MSVC 2010,2012,2013和14 CTP集成",因此您可能正在使用它.如果您的C或C++编译器没有生成最佳代码,请获取新的编译器(例如LLVM/Clang)或自行生成优化,最好通过修改编译器,以便您可以向开发人员发送补丁并将优化自动传播到其他的项目.

Answer 3

允许在环路外提升这个子表达式所需要的不是纯度,而是幂等性.

幂等意味着一个函数将具有相同的副作用,并且如果它被调用一次,就好像它被使用相同的参数多次调用一样.因此,编译器可以将函数调用放在循环之外,仅受条件保护(循环至少迭代一次吗？).然后,提升优化后的实际代码为:

double YSinX(double x,int y)
{
   double total = 0.0;
   int i = 0;
   if (i < y) {
       double sinx = sin(x);  // <- this goes between the loop-initialization
                              // first test of the condition expression
                              // and the loop body
       do {
          total += sinx;
          i++;
       } while (i < y);
   }
   return total;
}

区别__attribute__(pure)和之间的区别idempotent是重要的,因为正如adl在他的评论中指出的那样,这些功能确实具有设置的副作用errno.

但要小心,因为幂等仅适用于没有中间指令的重复调用.编译器必须执行数据流分析以证明函数和插入代码不会相互作用(例如,介入代码仅使用其地址永远不会被占用的本地符号),然后才能利用幂等性.当已知该函数是纯的时,这不是必需的.但纯度是一个更强大的条件,不适用于很多功能.

Answer 4

我想是的.如果你得到编译器反汇编输出,你可以看到,在另一个标签中调用sin而不是'for'的循环标签:(用g ++ -O1 -O2 -O3编译)

Leh_func_begin1:
        pushq   %rbp
Ltmp0:
        movq    %rsp, %rbp
Ltmp1:
        pushq   %rbx
        subq    $8, %rsp
Ltmp2:
        testl   %edi, %edi
        jg      LBB1_2
        pxor    %xmm1, %xmm1
        jmp     LBB1_4
LBB1_2:
        movl    %edi, %ebx
        callq   _sin ;sin calculated
        pxor    %xmm1, %xmm1
        .align  4, 0x90
LBB1_3:
        addsd   %xmm0, %xmm1
        decl    %ebx
        jne     LBB1_3 ;loops here till i reaches y
LBB1_4:
        movapd  %xmm1, %xmm0

我希望我是对的.