c - 除非 Haswell 指定，否则 GCC 编译前导零计数很差

Question

GCC 支持 __builtin_clz(int x) 内置函数，它计算参数中前导零(连续的最高有效零)的数量。

除其他外⁰，这对于有效实现 lg(unsigned int x) 非常有用函数，取 x 的以 2 为底的对数, 向下舍入¹:

/** return the base-2 log of x, where x > 0 */
unsigned lg(unsigned x) {
  return 31U - (unsigned)__builtin_clz(x);
}

这以直接的方式工作 - 特别考虑案例 x == 1和 clz(x) == 31 - 然后 x == 2^0所以lg(x) == 0和 31 - 31 == 0我们得到了正确的结果。 x 的较高值类似地工作。

假设内置函数被有效地实现，这比替代的 pure C solutions 要好得多。 .

碰巧，计数前导零 操作本质上是 bsr 的对偶操作x86 中的指令。这将返回参数中最高有效 1 位 ² 的索引。因此，如果有 10 个前导零，则第一个 1 位在参数的第 21 位中。一般来说我们有31 - clz(x) == bsr(x)所以bsr事实上直接实现了我们想要的lg()功能，没有多余的31U - ...部分。

事实上，您可以从字里行间看出 __builtin_clz函数是用 bsr 实现的请记住:如果参数为零，则它被定义为未定义的行为，当然，当“前导零”操作完全定义为 32(或 int 的任何位大小是) 参数为零。所以__builtin_clz当然是通过有效映射到 bsr 的想法实现的x86 上的说明。

然而，看看 GCC 实际做了什么，在 -O3其他默认选项:它adds a ton of extra junk :

lg(unsigned int):
        bsr     edi, edi
        mov     eax, 31
        xor     edi, 31
        sub     eax, edi
        ret 

xor edi,31行实际上是 not edi对于真正重要的底部 4 位，与 neg edi 相差一个³这变成了 bsr 的结果进入clz .然后 31 - clz(x)进行。

然而 -mtune=haswell , code simplifies完全符合预期的单例bsr说明:

lg(unsigned int):
        bsr     eax, edi
        ret

我不太清楚为什么会这样。 bsr指令在 Haswell 之前已经存在了几十年，行为是，AFAIK，没有改变。这不仅仅是针对特定架构的调整问题，因为bsr + 一堆额外的指令不会比普通的 bsr 更快并进一步使用 -mtune=haswell still results在较慢的代码中。

64位输入和输出的情况是even slightly worse : 有一个额外的 movsx在自 clz 的结果以来似乎什么都不做的关键路径中永远不会是负面的。同样，-march=haswell单个 bsr 变体是最佳的说明。

最后，让我们看看非 Windows 编译器领域的大玩家， icc and clang . icc只是做得不好并添加了多余的东西，例如 neg eax; add eax, 31; neg eax; add eax, 31; - 卧槽？ clang不管 -march 都做得很好.

---

⁰ 例如扫描一个位图寻找第一个设置位。

¹ 0 的对数是不确定的，因此使用 0 参数调用我们的函数是未定义的行为。

² 这里，LSB 是第 0 位，MSB 是第 31 位。

³ 回想一下 -x == ~x + 1二进制补码。

Answer 1

这看起来像是 gcc 的一个已知问题:https://gcc.gnu.org/bugzilla/show_bug.cgi?id=50168