c - 切换特定位

Question

所以我看到了像这样的问题 toggle a bit at ith positon和 How do you set, clear, and toggle a single bit? , 但我想知道是否有一种好方法可以在 x86-64 程序集的第 i 个位置切换位？

我试着用 C 语言编写它并查看了程序集，但不太明白为什么会有一些东西在那里。

C:

unsigned long toggle(unsigned long num, unsigned long bit)
{
  num ^= 1 << bit;
  return num;
}

int main()
{
  printf("%ld\n", toggle(100, 60));
  return 0;
}

从 GDB 切换函数汇编:

<toggle>
push rbp
mov rbp, rsp
mov QWORD PTR [rbp-0x8],rdi
mov QWORD PTR [rbp-0x10],rsi
mov rax, QWORD PTR [rbp-0x10]
mov edx, 0x1
mov ecx, eax
shl edx, cl
mov eax, edx
cdqe
xor QWORD PTR [rbp-0x8],rax
mov rax, QWORD PTR [rbp-0x8]
pop rbp
ret

谁能告诉我在汇编级别发生了什么，以便我能更好地理解这一点并在 x86-64 中编写我自己的切换函数？

Answer 1

I was wondering if there was a good way to toggle a bit in the ith position in x86-64 assembly?

是的，x86's BTC (Bit Test and Complement) instruction does exactly that (以及将 CF 设置为该位的旧值)，并在所有现代 CPU 上高效运行。

• 英特尔 SnB 系列:1 uop，1c 延迟，每个时钟吞吐量 2。 (Nehalem 及更早版本:每个时钟 1 个)
• Silvermont/KNL:1 uop，1c 延迟，每个时钟吞吐量 1。
• AMD Ryzen:2 微指令、2c 延迟、每个时钟吞吐量 2
• AMD Bulldozer 系列/Jaguar:2 微指令，2c 延迟，每个时钟吞吐量 1
• AMD K8/K10:2 微指令，2c 延迟，每个时钟吞吐量 1

来源:Agner Fog's instruction tables and x86 optimization guide .另请参阅 x86 中的其他性能链接标记维基。

toggle:
    mov  rax, rdi
    btc  rax, rsi
    ret

(如果您在 C 中正确编写了 toggle)。

不要使用 btc使用内存操作数:位串指令具有疯狂的 CISC 语义，其中位索引不限于寻址模式选择的双字内。 (所以 btc m,r 是 10 微指令，在 Skylake 上每 5c 吞吐量一个)。但是对于寄存器操作数，移位计数与可变计数移位完全一样被屏蔽。

不幸的是，gcc 和 clang 错过了这个窥视孔优化，即使是 -march=haswell或 -mtune=intel .即使在 AMD 上也值得使用，但在 Intel 上效率更高。

---

重复使用相同的 1ULL << bit具有多个输入

在 AMD CPU 上 btc比 xor 慢, 值得在寄存器中生成掩码并使用 xor .甚至在 Intel CPU 上，在内存中切换一下也是值得的。 (内存目标 xor 比内存目标 btc 好得多)。

对于数组中的多个元素，使用 SSE2 pxor .您可以使用以下方法生成掩码:

pcmpeqd  xmm0, xmm0        ; -1 all bits set
psrlq    xmm0, 63          ;  1 just a single bit set

movd     xmm1, esi
psllq    xmm0, xmm1        ; 1<<bit


; then inside a loop, with data in xmm1
pxor     xmm1, xmm0        ; flip bit in each qword element

---

don't quite understand exactly why there are some things that are there.

所有这些废话都是因为你在没有优化的情况下编译，并且因为你使用了签名的 int常量。

---

甚至不值得查看所有从 -O0 到内存的溢出/重新加载。代码。用 -O3 -march=native 编译如果你想要不烂的代码。

另见 How to remove "noise" from GCC/clang assembly output?和 Matt Godbolt 的 CppCon2017 演讲:“What Has My Compiler Done for Me Lately? Unbolting the Compiler's Lid” 了解编译器生成的 asm 的良好介绍。

---

使用签名 int常量 1 << bit解释了为什么 gcc 做了一个 32 位移位然后 cdqe . num ^= 1 << bit;相当于

int mask = 1;
mask <<= bit;   // still signed int
num ^= mask;    // mask is sign-extended to 64-bit here.

在 gcc -O3 输出中，我们得到

    mov     edx, 1
    sal     edx, cl           # 1<<bit   (32-bit)
    movsx   rax, edx          # sign-extend, like cdqe does for eax->rax
    xor     rax, rdi

---

如果我们写 toggle正确地:

uint64_t toggle64(uint64_t num, uint32_t bit) {
  num ^= 1ULL << bit;
  return num;
}

(source+asm on the Godbolt compiler explorer)

gcc 和 clang 仍然无法使用 btc ，但这并不可怕。有趣的是，MSVC 确实发现了 btc窥孔，但浪费了一条 MOV 指令:

toggle64 PROC
    mov      eax, edx
    btc      rcx, rax
    mov      rax, rcx
    ret      0

使用 uint64_t位避免了额外的 MOV。这是不必要的，因为 btc带有寄存器目标的索引用 & 63 屏蔽索引.高垃圾不是问题，但 MSVC 不知道这一点。

gcc 和 clang 发出的代码如您所料，但 gcc 通过生成 1ULL <<bit 浪费了 MOV 指令在rdx并且必须复制到 rax .

 ; clang output.
    mov     eax, 1
    mov     ecx, esi
    shl     rax, cl
    xor     rax, rdi
    ret