c - 在x86上给出无分支FP最小值和最大值的指令是什么？

Question

引用(感谢作者开发和共享算法!):

https://tavianator.com/fast-branchless-raybounding-box-intersections/

Since modern floating-point instruction sets can compute min and max without branches

作者对应的代码只是

dmnsn_min(double a, double b)
{
  return a < b ? a : b;
}

我熟悉例如 _mm_max_ps，但这是 vector 指令。上面的代码显然应该以标量形式使用。

问题:

x86上的无标量无分支minmax指令是什么？它是一连串的指示吗？

是否可以安全地假定它将被应用，或者我怎么称呼它？

关心最小/最大的无分支度有意义吗？据我了解，对于raytracer和/或其他viz软件，给定射线盒交叉的例程，没有可靠的模式可供分支预测器使用，因此消除分支确实有意义。我说得对吗？

最重要的是，所讨论的算法是围绕与(+/-)INFINITY进行比较而构建的。我们正在讨论的(未知)指令和浮点标准可靠吗？

以防万一:我熟悉 Use of min and max functions in C++，相信它是相关的，但不是我的问题。

Answer 1

警告:提防编译器即使在严格的FP(非快速运算)模式下也将_mm_min_ps/_mm_max_ps(和_pd)内在函数视为可交换的；即使没有asm指令。 GCC专门似乎有以下错误:在GCC7中已修复的PR72867，但对于_mm_min_ss等标量内在函数(_mm_max_ss has different behavior between clang and gcc，GCC bugzilla PR99497)可能回来了，或者从未修复过。
GCC知道asm指令本身是如何工作的，并且仅使用C/C++内在函数使用它们在普通标量代码中实现严格的FP语义时，就不会出现此问题。
不幸的是，没有一条实现fmin(a,b)的指令(具有保证的NaN传播)，因此您必须在容易检测问题与提高性能之间进行选择。

大多数 vector FP指令具有标量等效项。 MINSS/MAXSS/MINSD/MAXSD是您想要的。他们以您期望的方式处理+/- Infinity。
MINSS a,b根据IEEE规则精确地实现(a<b) ? a : b，它包含与零号，NaN和Infinities有关的所有内容。 (即，它使源操作数b保持无序。)这意味着C++编译器可以将它们用于std::min(b,a)和std::max(b,a)，因为这些函数基于相同的表达式。 请注意b,a函数的std::操作数顺序，与x86 asm的Intel语法相反，但匹配AT＆T语法。MAXSS a,b完全实现(b<a) ? a : b，再次将源操作数(b)保持为无序。像std::max(b,a)一样。
如果存在x = std::min(arr[i], x);(即minss或maxss xmm0, [rsi])循环遍历一个数组，则会从内存中获取一个NaN，然后​​再获取下一个非NaN元素，因为该比较将是无序的。因此，您将获得最后一个NaN之后的元素的最小值或最大值。您通常不希望这样做，因此仅对不包含NaN的数组有用。但这意味着您可以在循环外部以float v = NAN;开头，而不是第一个元素或FLT_MAX或+ Infinity开头，并且可以简化对可能为空的列表的处理。在asm中也很方便，允许pcmpeqd xmm0,xmm0的init生成全为一位的位模式(负QNAN)，但是不幸的是，GCC的NAN使用了不同的位模式。
演示/证明on the Godbolt compiler explorer，包括显示v = std::min(v, arr[i]);(或最大)忽略了数组中的NaN，这是以必须加载到寄存器中然后忽略该寄存器为代价的。
(请注意，数组的min应该使用 vector ，而不是标量；最好使用多个累加器来隐藏FP延迟。最后，减少到一个 vector ，然后对其进行horizontal min，就像对数组求和或做点积一样。)

不要尝试在标量浮点数上使用_mm_min_ss；仅__m128操作数和Intel's intrinsics don't provide any way to get a scalar float into the low element of a __m128 without zeroing the high elements or somehow doing extra work.提供内在函数。即使最终结果不依赖于上层元素中的任何内容，大多数编译器实际上也会发出无用的指令来执行此操作。 (尽管，Clang经常可以避免这种情况，但是可以对无效 vector 元素的内容应用as-if规则。)没有像__m256 _mm256_castps128_ps256 (__m128 a)那样仅将浮点数转换为带有上部元素中的垃圾的__m128的东西。我认为这是设计缺陷。 :/
但幸运的是，您不需要手动执行此操作，编译器知道如何为您使用SSE/SSE2的最小/最大。 只需编写C即可。您问题中的函数是理想的:如下所示(Godbolt链接):

// can and does inline to a single MINSD instruction, and can auto-vectorize easily
static inline double
dmnsn_min(double a, double b) {
  return a < b ? a : b;
}

请注意它们与NaN的不对称行为:如果操作数是无序的，则为dest = src(即，如果两个操作数均为NaN，则第二个操作数将为第二个操作数)。这对于SIMD条件更新很有用，请参阅下文。
(如果 a和 b中的任何一个都是NaN，它们都是无序的。这意味着 a<b， a==b和 a>b均为false。请参见 Bruce Dawson's series of articles on floating point for lots of FP gotchas。)
取决于编译器，相应的 _mm_min_ss/ _mm_min_ps内部函数可能具有也可能没有这种行为。
我认为内在函数应该具有与asm指令相同的操作数顺序语义，但是gcc甚至长时间不使用_mm_min_ps，甚至gcc4.4或更早的版本，都将-ffast-math的操作数视为可交换的。 GCC 7最终将其更改为与ICC和clang匹配。
英特尔的在线内部函数查找器没有记录该功能的行为，但可能并不详尽。 asm insn ref手册没有说内在函数不具有该属性。它只是列出 _mm_min_ss作为MINSS的内在函数。
当我在 "_mm_min_ps" NaN上搜索时，我发现 this real code以及其他有关使用内在函数处理NaN的讨论，因此很明显，许多人期望内在函数的行为类似于asm指令。 (这是我昨天编写的一些代码的结果，并且我已经在考虑将其编写为自我回答的问题与解答。)
鉴于存在这个长期存在的gcc错误，想要利用MINPS的NaN处理功能的可移植代码需要采取预防措施。如果现有的Linux发行版中的标准gcc版本取决于操作数到 _mm_min_ps的顺序，则会错误地编译您的代码。因此，您可能需要一个 #ifdef来检测实际的gcc(而不是clang等)，以及一种替代方法。或者只是以不同的方式来做它:/也许使用 _mm_cmplt_ps和 bool 值AND/ANDNOT/OR。
启用 -ffast-math也会使 _mm_min_ps在所有编译器上都可交换。

像往常一样，编译器知道如何使用指令集正确实现C语义。 MINSS和MAXSS是 faster than anything you could do with a branch anyway，因此只需编写可编译为其中之一的代码即可。
可交换 _mm_min_ps问题仅适用于内在函数:gcc确切了解MINSS/MINPS的工作方式，并使用它们正确实现严格的FP语义(当您不使用-ffast-math时)。
您通常不需要做任何特殊的事情就可以从编译器中获得不错的标量代码。但是，如果您要花时间关注编译器使用的指令，则可能应该首先从手动矢量化代码开始，如果编译器不这样做的话。
(在极少数情况下，如果条件几乎总是一成不变，并且延迟比吞吐量更重要，那么分支是最佳选择。MINPS延迟大约是3个周期，但是完美预测的分支会将0个周期添加到关键事件的依赖关系链中。小路。)

在C++中，使用std::min和std::max ，它们是根据 >或 <定义的，并且对NaN行为的要求与 fmin和 fmax相同。 除非您需要NaN行为，否则请避免 fmin and fmax 来提高性能。
在C语言中，我认为只需编写自己的 min和 max函数(或宏，如果您安全地执行此操作)。

C & asm on the Godbolt compiler explorer

float minfloat(float a, float b) {
  return (a<b) ? a : b;
}
# any decent compiler (gcc, clang, icc), without any -ffast-math or anything:
    minss   xmm0, xmm1
    ret

// C++
float minfloat_std(float a, float b) { return std::min(a,b); }
  # This implementation of std::min uses (b<a) : b : a;
  # So it can produce the result only in the register that b was in
  # This isn't worse (when inlined), just opposite
    minss   xmm1, xmm0
    movaps  xmm0, xmm1
    ret


float minfloat_fmin(float a, float b) { return fminf(a, b); }

# clang inlines fmin; other compilers just tailcall it.
minfloat_fmin(float, float):
    movaps  xmm2, xmm0
    cmpunordss      xmm2, xmm2
    movaps  xmm3, xmm2
    andps   xmm3, xmm1
    minss   xmm1, xmm0
    andnps  xmm2, xmm1
    orps    xmm2, xmm3
    movaps  xmm0, xmm2
    ret
   # Obviously you don't want this if you don't need it.

如果要自己使用 _mm_min_ss/ _mm_min_ps，请编写即使没有-ffast-math也可以使编译器实现良好asm的代码。
如果您不希望使用NaN，或者想专门处理NaN，请编写以下内容:

lowest = _mm_min_ps(lowest, some_loop_variable);

因此保存 lowest的寄存器可以就地更新(即使没有AVX)。

利用MINPS的NaN行为:
说你的标量代码就像

if(some condition)
    lowest = min(lowest, x);

假设可以使用CMPPS对条件进行矢量化处理，因此您有一个元素 vector ，这些元素的位全部置1或全部清零。 (或者，也许您可​​以直接使用浮点数上的ANDPS/ORPS/XORPS，如果您只关心它们的符号而不关心负零的话。这会在符号位中创建一个真值，并在其他地方带有垃圾。BLENDVPS着眼于仅符号位，因此这可能 super 有用。或者您可以使用 PSRAD xmm, 31广播符号位。)
实现此目的的直接方法是根据条件掩码将 x与 +Inf混合。或者执行 newval = min(lowest, x);并将newval混合到 lowest中。 (BLENDVPS或AND/ANDNOT/OR)。
但是诀窍是 全一位是NaN，按位OR会将其传播。所以:

__m128 inverse_condition = _mm_cmplt_ps(foo, bar);
__m128 x = whatever;


x = _mm_or_ps(x, condition);   // turn elements into NaN where the mask is all-ones
lowest = _mm_min_ps(x, lowest);  // NaN elements in x mean no change in lowest
//  REQUIRES NON-COMMUTATIVE _mm_min_ps: no -ffast-math
//  AND DOESN'T WORK AT ALL WITH MOST GCC VERSIONS.

因此，仅使用SSE2，我们已经在两条额外的指令(ORPS和MOVAPS，除非循环展开允许MOVAPS消失)中完成了有条件的MINPS。
没有SSE4.1 BLENDVPS的替代方案是ANDPS/ANDNPS/ORPS混合在一起，外加一个额外的MOVAPS。无论如何，ORPS比BLENDVPS更有效率(在大多数CPU上是2 uops)。