GCC 出于什么目的创建应用于移位项的单独位掩码？

Question

以下是一个最小的可重现代码示例，我必须在给定的

uint_fast64_t

x的情况下生成八叉树分支内3D坐标的“数组”（其1字节元素被打包到结果

z

中） 

和

y

位置：

#include <stdint.h>

void test(uint_fast64_t *const coord, const uint_fast8_t x, const uint_fast8_t z, const uint_fast8_t y) {
    static const uint_fast64_t m = 0x2040810204081ULL, a = 0x101010101010101ULL;
    *coord = (x * m & a) | (z * m & a) << 1 | (y * m & a) << 2;
}

从汇编来看，GCC 似乎只生成了

m

常量的一个“变体”，但是

variants

常量的三个

a

，包括

0x404040404040404

和

0x202020202020202

。

test:
        movabs  rax, 567382630219905 ; 0x2040810204081
        movzx   edx, dl
        movzx   esi, sil
        movzx   ecx, cl
        movabs  r8, 144680345676153346 ; 0x202020202020202
        imul    rdx, rax
        imul    rsi, rax
        imul    rcx, rax
        movabs  rax, 289360691352306692 ; 0x404040404040404
        add     rdx, rdx
        and     rdx, r8
        movabs  r8, 72340172838076673 ; 0x101010101010101
        and     rsi, r8
        sal     rcx, 2
        or      rdx, rsi
        and     rcx, rax
        or      rdx, rcx
        mov     QWORD PTR [rdi], rdx
        ret

无论出于何种原因，GCC 似乎都会将

<< 1

和

<< 2

“不断传播”到这些掩码，并将它们单独存储，而同一个掩码可以通过先执行

and

然后进行位移位来使用。这就是令人困惑的地方。

另一方面，

Clang 将位移完全传播到常量，因此程序集包含 6 个 64 位常量，但没有与

<< 1

和

<< 2

对应的移位操作。这似乎是以尺寸为代价的速度优化。

但我对海湾合作委员会的处理感到困惑。有些常量是“折叠”的，但有些则不是，并且它们不折叠的方式没有提供明显的好处。

我的问题是：

• 出于某种晦涩的原因，先执行移位然后再执行

  and

  掩码是否有一些优势，即使是以在代码中存储额外常量为代价？
• 如果没有，是否有一些 hack 或编译器标志我可以用来规避这个问题，并强制 GCC 首先简单地

  and

  然后进行转换，以避免存储这些常量？

这是“编译器将优化代码，忘记它吧”的情况之一。并没有真正起作用，因为这种“优化”本身就是我觉得有问题的。

我知道 16 字节的操作码“不多”，但我仍然很好奇为什么 GCC 会执行这种“优化”，尽管对于未经训练的人来说似乎是一种损失。 积极的尺寸优化甚至会发生这种情况。

Answer 1

我只能推测 GCC 代码生成器被简单地编程为始终计算相对于最终位置的位掩码，即使这意味着位掩码的数量正在增长。

GCC 还有其他启发式方法，例如与不等式进行比较时将立即数减少 1。

if (a < 2)

转换为

if (a <= 1)

，如果还需要计算

if (a == 2)

用于其他用途，则没有意义。

---

无论如何，我们都可以通过优化屏障来阻止 GCC 和 clang 进行一些优化

asm("" :"+r"(a))

——结合将常量作为非常量变量。

屏障通知包含

a

的寄存器正在被asm语句以某种方式

修改，这意味着

a

不再包含常量。随后 

a << 1, a << 2

 也不再可从 

a

 派生出立即数。

void test(uint_fast64_t *const coord, const uint_fast8_t x, const uint_fast8_t z, const uint_fast8_t y) {
     uint_fast64_t m = 0x2040810204081ULL, a = 0x101010101010101ULL;
     asm("" : "+r"(a));
     uint_fast64_t xm = x * m & a;
     uint_fast64_t ym = y * m & a;
     uint_fast64_t zm = z * m & a;
    *coord = xm | (zm << 1) | (ym << 2);
}

在这种特殊情况下，显然也可以使用

void test(uint_fast64_t *const coord, const uint_fast8_t x, const uint_fast8_t z, const uint_fast8_t y) {
    static const uint_fast64_t m = 0x2040810204081ULL, a = 0x101010101010101ULL;
    *coord = (x * m & a) + (z * m & a) * 2 + (y * m & a) * 4;
}

对于

test:
        movabs  r8, 567382630219905
        movzx   ecx, cl
        movzx   edx, dl
        movabs  rax, 72340172838076673
        imul    rcx, r8
        movzx   esi, sil
        imul    rdx, r8
        imul    rsi, r8
        and     rcx, rax
        add     rcx, rcx
        and     rdx, rax
        add     rcx, rdx
        and     rsi, rax
        add     rcx, rcx
        add     rcx, rsi
        mov     QWORD PTR [rdi], rcx
        ret

在这种情况下，我实际上期望使用

lea rax, [rax + 4*rbx]

 格式，而不是两个单独的 

add rcx, rcx

 左移 1，因为它会累积在比必要的更长的依赖链中。