C++常量折叠素数循环

Question

看了之前的问题1 , 2 ，我想知道是否可以强制编译器对以下打印素数的代码执行常量折叠。

#include <iostream>

using namespace std;

inline bool is_prime(int n)
{
    if(n<2)
        return false;
    for(int i=2;i*i<=n;i++)
        if(n%i==0)
            return false;
    return true;
}

int main()
{
    for(int i=0;i<20;i++)
        if(is_prime(i))
            cout<<i<<endl;
    return 0;
}

我通过以下方式构建它:

g++ -O3 -S main.cpp -o main.asm

结果有几个:

2,3,5,7,11,13,17,19

我想强制编译器查看类似于

的代码

for(int x:{2,3,5,7,11,13,17,19})
    cout<<x<<endl;

或

cout<<  2 <<endl;
cout<<  3 <<endl;
cout<<  5 <<endl;
cout<<  7 <<endl;
cout<< 11 <<endl;
cout<< 13 <<endl;
cout<< 17 <<endl;
cout<< 19 <<endl;

但是阅读程序集表明什么都没有发生。

我什至使用了 __builtin_expect 但它没有用。

有没有办法强制编译器优化器读取for循环并利用输出数据已知的优势？

我想在不使用模板元编程的情况下做到这一点。

PS. 我的真正目的只是测试编译器，而不是计算素数的有效方法。我只是想向我的 friend 们炫耀一下C++编译器的强大。

---

如果 is_prime 的分离是一个值得关注的问题，我将所有内容都放在 main 中并且没有观察到任何差异:

#include <iostream>

using namespace std;

int main()
{
    for(int n=2;n<20;n++)
    {
        bool is_prime=true;
        for(int i=2;i*i<=n;i++)
            if(n%i==0)
            {
                is_prime=false;
                break;
            }
        if(is_prime)
            cout<<n<<endl;
    }
    return 0;
}

---

甚至还有一个进一步的例子，编译器没有任何借口:

#include <iostream>
#include <vector>

using namespace std;

int prime_after6000()
{
    int n=6000;
    do
    {
        bool is_prime=true;
        for(int i=2;i*i<=n;i++)
            if(n%i==0)
            {
                is_prime=false;
                break;
            }
        if(is_prime)
            return n;
        n++;
    }while(true);
}

int main()
{
    cout<<prime_after6000()<<endl;
    return 0;
}

组装:

...
main:
.LFB1907:
    .cfi_startproc
    subq    $8, %rsp
    .cfi_def_cfa_offset 16
    movl    $6000, %esi   ;;;;;;;;;;;;;;;;;;;; bad
.L18:
    testb   $1, %sil
    je  .L15
    movl    $2, %ecx
    jmp .L16
    .p2align 4,,10
    .p2align 3
.L17:
    movl    %esi, %eax
    cltd
    idivl   %ecx
    testl   %edx, %edx
    je  .L15
.L16:
    addl    $1, %ecx
    movl    %ecx, %eax
    imull   %ecx, %eax
    cmpl    %esi, %eax
    jle .L17
    movl    $_ZSt4cout, %edi
    call    _ZNSolsEi
    movq    %rax, %rdi
    call    _ZSt4endlIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_
    xorl    %eax, %eax
    addq    $8, %rsp
    .cfi_remember_state
    .cfi_def_cfa_offset 8
    ret
    .p2align 4,,10
    .p2align 3
.L15:
    .cfi_restore_state
    addl    $1, %esi
    jmp .L18
    .cfi_endproc
.LFE1907:
    .size   main, .-main
    .p2align 4,,15
    .type   _GLOBAL__sub_I__Z15prime_after6000v, @function
_GLOBAL__sub_I__Z15prime_after6000v:
...

Answer 1

这里存在对编译器的根本误解。让我们仔细检查您编写的程序，并考虑您期望编译器为您做什么。

该程序的主要特点是它不接受任何输入，但它通过写入 cout 来发出输出。 .请记住 is_prime函数不是 compiler intrinsic ;编译器将其视为另一个函数。这很重要，我稍后会回来讨论。

现在编译器将如何按照您描述的方式转换程序？它怎么能做那样的事情？也就是说，编译器如何将这两个嵌套循环转换为将整数写入 cout 的简单语句序列？它可能做到这一点的唯一方法是通过执行程序找出需要写入 cout 的所有值。 .

这没有任何意义，是吗？让我们看看这里的大图，并考虑具有相同特征的所有程序(或语句序列)；那些不接受任何输入但发出输出的。问题会变成:为什么编译器不执行源代码而只发出写入输出值的代码？由于以下原因:

• 如果程序执行时间太长怎么办？如果其中有一个错误导致它运行了意想不到的时间怎么办？甚至不能保证 program will ever halt .编译器究竟应该做什么？
• 最终，编译器的目的不是执行源代码，而是生成功能等效且可能经过优化的 native 代码。毕竟，如果程序不接受任何输入(比如您的代码)，您可以同样轻松地编译代码并运行一次以查看输出。 无论如何，代码都必须由编译器或通过运行可执行二进制文件来执行，并且无论哪种方式都将花费相同的时间。在这两种情况下，都必须编译和执行代码。因此，这种优化不会增加任何实际值(value)。但是，这与模板形成对比，模板旨在在编译时由编译器缩减为常规代码。此外，解释将是此类程序更好的执行模型。您不想为编译代码而烦恼吗？继续使用 Python 解释器或任何解释器。
• 实现此类优化一般来说可能很困难或不可能。如果用于发出输出的机制具有可以改变 future 输出值的副作用怎么办？编译器并不完全知道当您写入 cout 时会发生什么.标准输出流可以重定向到一些奇怪的东西。因此，不接受任何输入的程序不一定更容易被编译器优化。

也就是说，可以在非常有限的时间内求值的简单代码片段确实由编译器求值。此优化称为 constant folding .对程序状态没有任何影响的代码片段可以在不执行的情况下被删除。例如，如果您删除了 cout<<i<<endl; ，编译器只会优化掉其余的代码。这叫做 dead code elimination .编译器进行这些优化是因为它们可以由编译器以系统的方式完成，并且因为它们在实际代码库上非常有效。

但是如果 is_prime 会发生什么？函数是编译器固有的？在这种情况下，编译器可能有一个内置的常用素数表和一个非常快速的素数测试实现。然后您可以期望编译器展开 loop在主函数中多次，甚至可能完全包含输出语句，基本上执行您正在寻找的转换。