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. 我的真正目的只是测试编译器而不是计算素数的有效方法.我只想向朋友炫耀一下C++编译器的强大功能.

---

如果分离is_prime是关注的问题,我把所有东西放在主要内部并且没有观察到任何差异:

#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函数不是编译器内部函数；编译器将其视为另一个函数。这很重要，我稍后会再谈。

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

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

• 如果程序执行时间过长怎么办？如果其中存在错误导致其运行时间超出预期怎么办？甚至无法保证该计划将永远停止。编译器到底应该做什么？
• 最终，编译器的目的不是执行源代码，而是生成功能等效且可能优化的本机代码。毕竟，如果程序不接受任何输入（如您的代码），您可以轻松地编译代码并运行一次以查看输出。无论如何，代码都必须由编译器或运行可执行二进制文件来执行，并且无论哪种方式都将花费相同的时间。在这两种情况下，都必须编译并执行代码。所以这样的优化并没有增加任何实际价值。然而，这与模板相反，模板旨在由编译器在编译时简化为常规代码。此外，解释对于此类程序来说将是更好的执行模型。您不想费心编译代码吗？继续使用 Python 解释器或任何解释器。
• 一般来说，实施这种优化可能很困难或不可能。如果用于发出输出的机制具有可以改变未来输出值的副作用怎么办？编译器并不确切知道当您写入cout. 标准输出流可以重定向到一些奇怪的东西。因此，不接受任何输入的程序不一定更容易让编译器优化。

也就是说，可以在非常有限的时间内计算的简单代码片段确实是由编译器计算的。这种优化称为常量折叠。对程序状态没有任何影响的代码片段可以被删除而不执行。例如，如果您删除了cout<<i<<endl;，编译器将优化掉其余的代码。这称为死代码消除。编译器进行这些优化是因为它们可以由编译器以系统的方式完成，并且因为它们在实际代码库上非常有效。

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