如何使用内联汇编强制编译器生成条件移动

Question

我花了几个小时尝试将以下代码转换为内联汇编 (GCC)，但没有成功：

int new_low = mid + 1;
int new_high = mid - 1;

if (middle < key) {
    low = new_low;
}

if (!(middle < key)) {
    high = new_high;
}

我希望编译器优化掉那些 if，而是使用条件移动。不幸的是，编译器一直在生成跳转。我尝试编写内联汇编，但我并不擅长，而且寄存器破坏存在一些问题，我无法正确处理。我做错了什么？

__asm__ (
    "cmp %[array_middle], %[key];"
    "cmovb %[new_low], %[low];"
    "cmovae %[new_high], %[high];"
    : [low] "=&r"(low), [high] "=&r"(high)
    : [new_low] "r"(new_low), [new_high] "r"(new_high), [array_middle] "r"(middle), [key] "r"(key)
    : "cc"
);

Answer 1

你通常不需要内联汇编，但你的问题是 [low] "=&r"(low) 是只写输出！！您是在告诉编译器变量的旧值无关紧要，它是只写的。但对于 cmov 而言并非如此：它是一个 3 输入指令：src、dst 和 FLAGS。

对low/high（cmov 目标）使用"+&r" read/write 操作数。事实证明，这基本上是的副本，它显示工作的内联 asm 几乎与您的相同（使用 FP 比较而不是整数，但使用相同的 cmov 指令。）

这应该可行，但强制编译器使用比原本需要更多的寄存器。（例如，它可以使用 LEA after CMP 来执行 mid+1 和 mid-1，覆盖 mid。或者甚至使用 LEA + INC 因为 B 和 AE 条件只读CF 和足够新的 CPU 根本没有部分标志停顿，它们只是在必要时让 cmov 分别读取 FLAGS 的两个部分。这就是为什么 cmovbe 在 Skylake 上是一条 2-uop 指令，而对于 1大多数其他条件。）

让编译器无分支：

您是否尝试过三元运算符，例如 low = (middle < key) ? new_low : low;？您是否尝试过配置文件引导优化，以便 GCC 可以看到分支实际上不是很可预测？（表明 if-conversion 到无分支通常只在 -O3 完成，至少在某些情况下是这样。

此外，请记住，无分支会产生数据依赖性，这对于二分查找来说可能更糟；推测执行有效地为您提供内存并行/预取，而不是序列化加载。 (https://agner.org/optimize/)

对于在 L1d 缓存中命中的小型二进制搜索，分支未命中的成本高于加载使用延迟。但是一旦您预计会有一些 L2 缓存未命中，分支恢复比 L3 的加载使用延迟更便宜。 About the branchless binary search.

1/4 和 3/4 元素的软件预取可以帮助缓解这种情况，隐藏加载使用延迟。这利用了内存级并行性（同时有多个负载在运行），即使对于通过需求负载链存在数据依赖性的无分支形式也是如此。

如果您可以选择不同的数据结构，What is the most efficient way to implement a BST in such a way the find(value) function is optimized for random values in the tree on x86? 表明使用 SIMD 可以非常快速地搜索宽隐式树，以平衡计算与延迟，从而只需很少的步骤即可获得成功。它是有序的，所以你可以按顺序遍历它，或者在命中后找到上一个或下一个元素。

如何使用内联汇编强制编译器生成条件移动

How to force compiler to generate conditional move by using inline assembly

x86

gcc

inline-assembly

conditional-move

让编译器无分支：