编译器会进行什么类型的分析来发现通过调用内置函数来减少整个代码块的机会？

Question

我什至不确定我是否使用了适当的术语来表达这个问题，但以下是我的意思（这里是编译器资源管理器上的完整示例）。

采用此代码，它计算输入中设置的位数

int

：

int foo(int a) {
    int count = 0;
    while (a) {
        ++count;
        a &= a - 1;
    }
    return count;
}

Clang，当针对 Haswell 架构时，可以将其编译为仅对

popcntl

的一次调用（即使某些版本添加了冗余指令）：

foo(int):                                # @foo(int)
        popcntl %edi, %eax
        retq

但是为什么它不能对下面的“愚蠢”版本做同样的事情呢？

int foo(int a) {
    int count = 0;
    while (a) {
        count += 1 & a;
        a >>= 1;
    }
    return count;
}

这编译为

foo(int):                                # @foo(int)
        xor     eax, eax
        test    edi, edi
        je      .LBB0_2
.LBB0_1:                                # =>This Inner Loop Header: Depth=1
        mov     ecx, edi
        and     ecx, 1
        add     eax, ecx
        sar     edi
        jne     .LBB0_1
.LBB0_2:
        ret

它非常好地映射到 C++ 代码片段。

我认为后一种代码（C++ 及其相应的汇编）更接近人类方法。

仍然是相同的编译器，具有相同的选项，看不到它在做相同的事情。

这是为什么？

• 编译器只是在源代码上根据已知习语映射应用某种模式匹配吗？
  这种方法意味着编译器只是重新应用人类的方法来读取代码并得出其正在执行的操作的结论，因此它只是转到其拥有的内置函数列表并选择执行相同操作的内置函数；因此，如果在第二个片段中没有成功，则仅意味着编写编译器的人考虑了第一个片段，而不是第二个片段（理所当然！）。

• 或者也许只是对代码片段应用连续的简化/重新加工，而这些代码片段恰好最终出现在前一个代码片段的最佳场景中，但不适用于后者？
  如果是这样的话，那么这两个片段之间的关键区别是什么？是否能够获得圆满的结局？

---

¹ 我测试代码的唯一方法是验证以下

main

 返回 0：

int main() {
    for (auto i = 0; i != 100000; ++i) {
        if (foo(i) != bar(i)) {
            return 1;
        }
    }
    return 0;
}

Answer 1

LLVM 简化第一个函数的点是

LoopDeletionPass

（参见 

https://godbolt.org/z/z1GT7Kx9q），它将整个循环变成：

%0 = call i32 @llvm.ctpop.i32(i32 %a) 您可以看到，此优化过程仅在应用了许多其他优化过程后才执行。 通常，优化可以实现其他优化，反过来，优化又可以实现其他优化。 重复此操作，直到达到固定的通行限制。

经过进一步优化后，剩下的就是 IR：

define dso_local noundef i32 @foo(int)(i32 noundef %a) local_unnamed_addr {
entry:
  %0 = icmp eq i32 %a, 0
  %1 = tail call i32 @llvm.ctpop.i32(i32 %a)
  %spec.select = select i1 %0, i32 0, i32 %1
  ret i32 %spec.select
}

本质上，编译器识别某些模式（例如执行某些操作的循环）并将它们转换为一组执行相同但更好的指令（例如调用 LLVM 内部函数）。这称为

窥孔优化。

是否可以执行优化通常归结为编译器开发人员是否费心指定模式。可以识别哪些模式似乎是任意的。