除非Haswell指定,否则GCC会很难编制前导零计数

Question

GCC支持__builtin_clz(int x)内置,它计算参数中前导零(连续最重要的零)的数量.

除了其他东西^0之外,这对于有效地实现lg(unsigned int x)函数非常有用,该函数采用基数2的对数x,舍入为¹:

/** 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工作价值.

假设内置程序有效实现,这比备用纯C解决方案更好.

现在,它发生了,计数前导零操作基本上是bsrx86中指令的双重.返回参数中最重要的1位²的索引.因此,如果有10个前导零,则第一个1位位于参数的第21位.一般来说,我们有31 - clz(x) == bsr(x),并在这样bsr的事实,直接实现我们所期望的lg()功能,无需多余的31U - ...部分.

事实上,你可以在行之间读取并看到__builtin_clz函数是在实现的时候实现的bsr:如果参数为零,它被定义为未定义的行为,当然"当前的零"操作被完美地定义为32(或者无论比特大小int是什么),零参数.因此__builtin_clz,有效地实现了有效映射到bsrx86 上的指令的想法.

然而,看看GCC实际上做了什么,-O3以及其他默认选项:它增加了大量的额外垃圾:

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,代码简化为预期的单个bsr指令:

lg(unsigned int):
        bsr     eax, edi
        ret

为什么会这样,我很不清楚.bsr在哈斯韦尔之前,这个指令已经存在了几十年,并且AFAIK的行为没有改变.这不仅仅是针对特定arch 进行调优的问题,因为bsr+一堆额外指令不会比普通指令快bsr,而且使用-mtune=haswell 仍会导致代码速度变慢.

对于这种情况的64位输入和输出是甚至略差:有一个多余movsx的,这似乎什么也不做,因为从结果的关键路径clz绝不会是负的.同样,该-march=haswell变体在单个bsr指令中是最佳的.

最后,让我们检查在非Windows编译器空间的大玩家,icc和clang.icc只做一个糟糕的工作,并添加多余的东西,如neg eax; add eax, 31; neg eax; add eax, 31;-wtf？clang无论如何都做得很好-march.

---

⁰如扫描一个位图的第一集合的位.

¹ 0的对数是未定义的,因此使用0参数调用我们的函数是未定义的行为.

²这里,LSB是第0位,MSB是第31位.

³回想一下,-x == ~x + 1在二重补充中.

Answer 1

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