C中的内联汇编
Inlining assembly in C
我正在用 C 编写国际象棋引擎，速度至关重要。国际象棋引擎基于 unsigned long long，我将其表示为 u64，它在很大程度上依赖于最低有效位扫描。到目前为止，我一直在使用 gcc 函数 __builtin_ctzll，它已经很好地完成了工作。然而，我使用 gcc -S -O2 为这个孤立的函数生成了汇编代码。它给了我以下内容：
xorl %eax, %eax
rep bsfq %rdi, %rax
cltq
ret
不过经过一番调查，代码似乎是
rep bsfq %rdi, %rax
ret
在我的国际象棋程序中做同样的事情。然而，它现在慢了约 20%。它应该更快，因为它的指令更少。然而，原始 __builtin_ctzll 内联在我的 C 代码中。这就是我的自定义汇编代码比原始代码慢 运行 的原因吗？因为当我声明函数 ctzll 时，我当然不能在 c 中内联声明它，除非我有一个定义（它不在汇编代码中）。
是否有其他方法可以优化汇编指令，或者我是否应该尝试直接在 c 中使用 asm 内联的新汇编代码？
两者实际上并不等同。具体来说，它们在 %rdi 为 0 的情况下有所不同。
如果输入为 0，bsf 保留目标的先前结果是 semi-defined 行为：Why does breaking the "output dependency" of LZCNT matter?
这意味着 bsf 指令对其输出寄存器具有输入依赖性。将输出寄存器清零显式地打破了这种依赖性，并确保在这种情况下定义了行为。在大多数现代 x86 实现中，使用异或归零发生在寄存器重命名期间，并打破了依赖链。这意味着 xor 本身实际上是免费的。这也意味着可以将 bsf 分派到执行单元，而无需等待之前使用 eax 寄存器，这可能会导致您看到的性能差异。
但是，更有可能的是，无论您放入短程序集如何，都对优化器隐藏了它，从而迫使优化器围绕函数之前内联的位置做出次优选择。
你可能会整体使用内置代码生成更好的代码，这不是因为内置程序本身生成的程序集的任何细节，而是因为编译器知道内置函数的作用。它知道内置函数没有副作用并且不访问内存，因此它可以排除使用相同参数的重复调用。它知道如何通过内置函数“不断折叠”，所以例如它可以用 10 替换 __builtin_ctzll(0x123400)。依此类推。
另一方面，使用内联汇编时，您告诉编译器读取和写入了哪些寄存器，但它必须对汇编的作用做出保守的假设。它不能通过内联汇编不断折叠。它不能假定内联汇编总是对相同的输入产生相同的结果。等等
结论先，使用__builtin_ctzll，结果没有转成64位。如果你想强制编译器使用 tzcnt 或者如果你想制作自己的 built-in.
，下面的内容会很有用
由于@user1937198 解释了所有基础知识，这里有一些相当快速且可移植的代码。
static inline int u64_bsf(u64 x) {
u64 r = 0;
__asm__ ("rep bsfq\t%1, %0" : "+r"(r) : "r"(x));
return r;
}
/*
u64_bsf:
xorl %eax, %eax
rep bsfq %rdi, %rax
ret
*/
如果需要，您可以将 return 类型更改为 unsigned。在包括 x86 在内的大多数平台上，使用 int 或 unsigned 生成最快的代码（有时数组索引除外）。特别是在 x86 上，使用 64 位整数会导致 32 位模式下的软件仿真，以及 64 位模式下更大的代码大小（加上更慢的除法）。您对 64 位 return 类型的使用也混淆了编译器使用冗余 cltq （这是 AT&T 语法中 cdqe 的错误 made-up 名称）。
rep bsf 在支持它的机器上被解码为 tzcnt，而 rep 在不支持它的机器上被丢弃。 tzcnt 更好，因为它（通常）不将输出寄存器作为输入（参见@user1937198 的回答），并且它在 AMD CPU 上运行得更快。
如果您的目标计算机具有 tzcnt 写入
static inline int u64_tzcnt(u64 x) {
u64 r;
__asm__ ("tzcntq\t%1, %0" : "=r"(r) : "r"(x));
return r;
}
/*
u64_tzcnt:
tzcntq %rdi, %rax
ret
*/
阅读 GCC 的联机文档以了解其内联汇编语法 (https://gcc.gnu.org/onlinedocs/gcc/Extended-Asm.html)。
@zwol 的回答提到了常量折叠。这是可以处理持续传播并内联 non-constant 输入的最终代码。
static inline int u64_bsf(u64 x) {
if (__builtin_constant_p(x)) {
return __builtin_ctzll(x);
}
u64 r = 0;
__asm__ ("rep bsfq\t%1, %0" : "+r"(r) : "r"(x));
return r;
}
目前，我基本上已经重新实现了 __builtin_ctzll，但您始终可以通过这种方式创建自己的内在函数。
部分答案涵盖了其他现有答案没有的内容，例如为什么 GCC 显然浪费了 cltq，为什么 xor-zeroing 有帮助，以及为什么 GCC 的 code-gen 有其他选项，例如 -march=skylake 或 -march=sandybridge 不好。
cltq（又名 cdqe）是 __builtin_ctzll() 被定义为 return 一个 int 而不是 long long 的不幸结果].
bsf %rdi, %rax 要么用 0..63 中的数字写入 RAX，要么保持不变（或者在纸面上，保持未定义的值，但实际上英特尔 CPU 与 AMD 文档的行为兼容：离开如果 bsf 或 bsr 的输入为 0，则输出寄存器未修改，这与 tzcnt / lzcnt) 不同。
__builtin_ctzll() 只允许 return 有效 int 值，即使输入 = 0。（GNU C specifies 内置函数如“如果 x 为 0，result 未定义。”不是“行为”，它不是 UB，你仍然 gua运行teed 得到 一些 32位int值。)
当 GCC 不确定 rep bsf 将 运行 作为 tzcnt 而不是 bsf 时，它必须涵盖目的地持有旧垃圾的可能性如果您 return uint64_t 而不是 unsigned 或 int，则高位不是第 31 位的副本。 （返回一个较窄的类型让调用者忽略高垃圾。）
在这种情况下，它也是 xor-zeroing 目的地，gua运行 为 0 输入提供 0 输出，因此无需 sign-extend。除非你想安全地玩，以防万一英特尔（或某些软件 x86 模拟器）停止执行 AMD 记录的操作，并且实际上在 input=0 时产生了旧值以外的东西。
IIRC，rep bsf %edi, %eax 在 Intel 或 AMD 上（我忘了是哪个）does always t运行cate RAX to 32-bit 即使它离开 EAX未修改。但是在其他供应商上却没有。如此有趣的事实，如果仅针对执行最低限度 zero-extension、(uint64_t)(uint32_t)__builtin_ctz(x) 的 CPU，则不需要任何额外的工作。
始终 bsf 的输出依赖性，有时 tzcnt
GCC 有时有点脑残：他们小心翼翼地避免 tzcnt 对通用或 Intel 的输出依赖性，但是 code-gen 似乎忘记了 bsf 的真正依赖性，如果你编译-march=sandybridge 或不支持 TZCNT 的东西。 （在这种情况下，它 只是 使用 bsf，没有 xor-zeroing 目的地。）
显然 xor-zeroing dep-breaking 只是在 以防它 运行 作为英特尔 上的 TZCNT 时才完成。这很讽刺，因为 bsf always 在所有 CPU 上都有输出依赖性，因为在实践中，Intel CPU 与 AMD 文档兼容：input = 0 使输出保持不变bsf/bsr。所以像 cmov 他们需要 dst reg 作为输入。
https://godbolt.org/z/WcY3sManq shows that, and that GCC also doesn't know that -march=skylake fixed the false dep for tz/lzcnt. (Why does breaking the "output dependency" of LZCNT matter?)
我正在用 C 编写国际象棋引擎，速度至关重要。国际象棋引擎基于 unsigned long long，我将其表示为 u64，它在很大程度上依赖于最低有效位扫描。到目前为止，我一直在使用 gcc 函数 __builtin_ctzll，它已经很好地完成了工作。然而，我使用 gcc -S -O2 为这个孤立的函数生成了汇编代码。它给了我以下内容：
xorl %eax, %eax
rep bsfq %rdi, %rax
cltq
ret
不过经过一番调查，代码似乎是
rep bsfq %rdi, %rax
ret
在我的国际象棋程序中做同样的事情。然而，它现在慢了约 20%。它应该更快，因为它的指令更少。然而，原始 __builtin_ctzll 内联在我的 C 代码中。这就是我的自定义汇编代码比原始代码慢 运行 的原因吗？因为当我声明函数 ctzll 时，我当然不能在 c 中内联声明它，除非我有一个定义（它不在汇编代码中）。
是否有其他方法可以优化汇编指令，或者我是否应该尝试直接在 c 中使用 asm 内联的新汇编代码？
两者实际上并不等同。具体来说，它们在 %rdi 为 0 的情况下有所不同。
如果输入为 0，bsf 保留目标的先前结果是 semi-defined 行为：Why does breaking the "output dependency" of LZCNT matter?
这意味着 bsf 指令对其输出寄存器具有输入依赖性。将输出寄存器清零显式地打破了这种依赖性，并确保在这种情况下定义了行为。在大多数现代 x86 实现中，使用异或归零发生在寄存器重命名期间，并打破了依赖链。这意味着 xor 本身实际上是免费的。这也意味着可以将 bsf 分派到执行单元，而无需等待之前使用 eax 寄存器，这可能会导致您看到的性能差异。
但是，更有可能的是，无论您放入短程序集如何，都对优化器隐藏了它，从而迫使优化器围绕函数之前内联的位置做出次优选择。
你可能会整体使用内置代码生成更好的代码，这不是因为内置程序本身生成的程序集的任何细节，而是因为编译器知道内置函数的作用。它知道内置函数没有副作用并且不访问内存，因此它可以排除使用相同参数的重复调用。它知道如何通过内置函数“不断折叠”，所以例如它可以用 10 替换 __builtin_ctzll(0x123400)。依此类推。
另一方面，使用内联汇编时，您告诉编译器读取和写入了哪些寄存器，但它必须对汇编的作用做出保守的假设。它不能通过内联汇编不断折叠。它不能假定内联汇编总是对相同的输入产生相同的结果。等等
结论先，使用__builtin_ctzll，结果没有转成64位。如果你想强制编译器使用 tzcnt 或者如果你想制作自己的 built-in.
由于@user1937198 解释了所有基础知识，这里有一些相当快速且可移植的代码。
static inline int u64_bsf(u64 x) {
u64 r = 0;
__asm__ ("rep bsfq\t%1, %0" : "+r"(r) : "r"(x));
return r;
}
/*
u64_bsf:
xorl %eax, %eax
rep bsfq %rdi, %rax
ret
*/
如果需要，您可以将 return 类型更改为 unsigned。在包括 x86 在内的大多数平台上，使用 int 或 unsigned 生成最快的代码（有时数组索引除外）。特别是在 x86 上，使用 64 位整数会导致 32 位模式下的软件仿真，以及 64 位模式下更大的代码大小（加上更慢的除法）。您对 64 位 return 类型的使用也混淆了编译器使用冗余 cltq （这是 AT&T 语法中 cdqe 的错误 made-up 名称）。
rep bsf 在支持它的机器上被解码为 tzcnt，而 rep 在不支持它的机器上被丢弃。 tzcnt 更好，因为它（通常）不将输出寄存器作为输入（参见@user1937198 的回答），并且它在 AMD CPU 上运行得更快。
如果您的目标计算机具有 tzcnt 写入
static inline int u64_tzcnt(u64 x) {
u64 r;
__asm__ ("tzcntq\t%1, %0" : "=r"(r) : "r"(x));
return r;
}
/*
u64_tzcnt:
tzcntq %rdi, %rax
ret
*/
阅读 GCC 的联机文档以了解其内联汇编语法 (https://gcc.gnu.org/onlinedocs/gcc/Extended-Asm.html)。
@zwol 的回答提到了常量折叠。这是可以处理持续传播并内联 non-constant 输入的最终代码。
static inline int u64_bsf(u64 x) {
if (__builtin_constant_p(x)) {
return __builtin_ctzll(x);
}
u64 r = 0;
__asm__ ("rep bsfq\t%1, %0" : "+r"(r) : "r"(x));
return r;
}
目前，我基本上已经重新实现了 __builtin_ctzll，但您始终可以通过这种方式创建自己的内在函数。
部分答案涵盖了其他现有答案没有的内容，例如为什么 GCC 显然浪费了 cltq，为什么 xor-zeroing 有帮助，以及为什么 GCC 的 code-gen 有其他选项，例如 -march=skylake 或 -march=sandybridge 不好。
cltq（又名 cdqe）是 __builtin_ctzll() 被定义为 return 一个 int 而不是 long long 的不幸结果].
bsf %rdi, %rax 要么用 0..63 中的数字写入 RAX，要么保持不变（或者在纸面上，保持未定义的值，但实际上英特尔 CPU 与 AMD 文档的行为兼容：离开如果 bsf 或 bsr 的输入为 0，则输出寄存器未修改，这与 tzcnt / lzcnt) 不同。
__builtin_ctzll() 只允许 return 有效 int 值，即使输入 = 0。（GNU C specifies 内置函数如“如果 x 为 0，result 未定义。”不是“行为”，它不是 UB，你仍然 gua运行teed 得到 一些 32位int值。)
当 GCC 不确定 rep bsf 将 运行 作为 tzcnt 而不是 bsf 时，它必须涵盖目的地持有旧垃圾的可能性如果您 return uint64_t 而不是 unsigned 或 int，则高位不是第 31 位的副本。 （返回一个较窄的类型让调用者忽略高垃圾。）
在这种情况下，它也是 xor-zeroing 目的地，gua运行 为 0 输入提供 0 输出，因此无需 sign-extend。除非你想安全地玩，以防万一英特尔（或某些软件 x86 模拟器）停止执行 AMD 记录的操作，并且实际上在 input=0 时产生了旧值以外的东西。
IIRC，rep bsf %edi, %eax 在 Intel 或 AMD 上（我忘了是哪个）does always t运行cate RAX to 32-bit 即使它离开 EAX未修改。但是在其他供应商上却没有。如此有趣的事实，如果仅针对执行最低限度 zero-extension、(uint64_t)(uint32_t)__builtin_ctz(x) 的 CPU，则不需要任何额外的工作。
始终 bsf 的输出依赖性，有时 tzcnt
GCC 有时有点脑残：他们小心翼翼地避免 tzcnt 对通用或 Intel 的输出依赖性，但是 code-gen 似乎忘记了 bsf 的真正依赖性，如果你编译-march=sandybridge 或不支持 TZCNT 的东西。 （在这种情况下，它 只是 使用 bsf，没有 xor-zeroing 目的地。）
显然 xor-zeroing dep-breaking 只是在 以防它 运行 作为英特尔 上的 TZCNT 时才完成。这很讽刺，因为 bsf always 在所有 CPU 上都有输出依赖性，因为在实践中，Intel CPU 与 AMD 文档兼容：input = 0 使输出保持不变bsf/bsr。所以像 cmov 他们需要 dst reg 作为输入。
https://godbolt.org/z/WcY3sManq shows that, and that GCC also doesn't know that -march=skylake fixed the false dep for tz/lzcnt. (Why does breaking the "output dependency" of LZCNT matter?)