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

Question

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

因为现代浮点指令集可以在没有分支的情况下计算最小值和最大值

相应的代码由作者只是

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

• x86上的标量无分支minmax指令是什么？是一系列指令吗？
• 假设它将被应用是否安全，或者如何调用它？
• 为最小/最大值的无分支性而烦恼有意义吗？根据我的理解，对于raytracer和/或其他viz软件，给定一个射线盒相交例程，没有可靠的模式可供分支预测器拾取，因此消除分支是有意义的。我说的对吗？
最重要的是，所讨论的算法是建立在与(+/-)无穷大比较的基础上的。这个可靠的W.R.T是我们讨论的（未知）指令和浮点标准吗？

以防万一：我很熟悉C++中min和max函数的使用，相信这是相关的，但不完全是我的问题。

Answer 1

警告：当心编译器将_mm_min_ps/_mm_max_ps（和_pd)本质视为可交换的，即使在严格的FP（非快速数学）模式下也是如此；即使asm指令不是。GCC似乎有这个错误:PR72867，它在GCC7中被修复，但可能会恢复或永远不会修复_mm_min_ss等标量本质(_mm_max_ss在clang和GCC之间有不同的行为，GCC bugzilla PR99497)。

GCC知道asm指令本身是如何工作的，并且在使用它们以纯标量代码实现严格的FP语义时没有这个问题，只使用C/C++的本质。

不幸的是，没有一条指令实现fmin(a,b)（具有保证的NaN传播），因此您必须在容易检测问题和更高的性能之间做出选择。

大多数向量FP指令都有标量等价物。MINSS/MAXSS/MINSD/MAXSD是您想要的。他们以你所期望的方式处理+/-无穷大。

MINSS a,B完全实现了(a 根据IEEE规则，包含关于带符号的零、NaN和无穷大的所有内容。（即，它使源操作数 b处于无序状态。）这意味着C++编译器可以将它们用于 std::min(b,a)和 std::max(b,a)，因为这些函数基于相同的表达式。请注意 std::函数的 b、a操作数顺序，与x86 asm的Intel-语法相反，但与AT&T语法匹配。

maxss a,b完全实现了(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生成一个全1位模式（负QNAN)，但不幸的是gcc的NAN使用了不同的位模式。

Godbolt编译器资源管理器上的演示/证明，包括显示v=std::min(v,arr[i])；（或max）忽略数组中的NAN，代价是必须加载到一个寄存器中，然后将minss加载到该寄存器中。

（注意，数组最小化应该使用向量，而不是标量；最好使用多个累加器来隐藏FP延迟。最后，减少到一个向量，然后对其进行水平最小化，就像对数组求和或做点积一样。）

不要尝试在标量浮点上使用_mm_min_ss；本征函数仅可用于__m128操作数，而Intel的本征函数不提供任何方法，在不将高元素清零或以某种方式进行额外工作的情况下，将标量浮动到__m128的低元素中。大多数编译器实际上会发出无用的指令来执行这些操作，即使最终结果并不依赖于上层元素中的任何内容。（但是，Clang经常可以避免这种情况，对死向量元素的内容应用as-if规则。）没有什么比__m256_mm256_castps128_ps256(__m128a)更简单的方法可以将浮点转换为在上面元素中带有垃圾的__m128。我认为这是一个设计缺陷。：/

但幸运的是，您不需要手动执行此操作，编译器知道如何为您使用sse/sse2min/max。只要写你的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 、 A==b和 A>B都是假的。请参阅Bruce Dawson关于浮点的系列文章，了解大量的FP错误。）

对应的_mm_min_ss/_mm_min_ps内蕴可能具有或不具有此行为，具体取决于编译器。

我认为本机应该具有与asm指令相同的操作数顺序语义，但是很长一段时间以来，GCC4.4或更早的版本都将_mm_min_ps的操作数视为可交换的，即使没有-ffast-math。GCC 7最后把它改成了匹配ICC和Clang。

Intel的在线intrinsics finder没有记录该函数的行为，但它可能不应该是详尽无遗的。asm insn ref手册没有说内蕴不具有该属性；它只是将_mm_min_ss列为MINSS的内在属性。

当我在“_mm_min_ps”nan上搜索时，我发现了这段真实的代码和一些关于使用intrinsic处理NaNs的其他讨论，所以很明显，许多人希望intrinsic的行为与asm指令类似。（这是我昨天编写的一些代码中出现的，我已经在考虑将其作为一个自我回答的问答来编写。）

考虑到这个长期存在的gcc bug的存在，想要利用MINPS的NaN处理的可移植代码需要采取预防措施。许多现有Linux发行版上的标准gcc版本如果依赖于_mm_min_ps的操作数顺序，就会错误编译代码。因此，您可能需要#ifdef来检测实际的gcc（而不是clang等），还有一个替代选项。或者一开始就以不同的方式执行：/可能使用_mm_cmplt_ps和布尔值和/ANDNOT/Or。

启用-ffast-math还使_mm_min_ps在所有编译器上可交换。

像往常一样，编译器知道如何使用指令集来正确实现C语义。MINSS和MAXSS的速度比使用分支所能做的任何事情都快，所以只需编写可以编译到其中之一的代码即可。

交换性的-_mm_min_ps问题仅适用于内部：gcc确切知道MINS/MINP的工作方式，并使用它们正确实现严格的FP语义（当不使用-ffast-math时）。

您通常不需要做任何特别的事情来从编译器中获得像样的标量代码。但是，如果您要花时间关心编译器使用什么指令，那么您可能应该从手动向量化代码开始，如果编译器没有这样做的话。

（可能有一个分支最好的罕见情况，如果条件几乎总是单向的，延迟比吞吐量更重要。MINPS延迟是~3个周期，但一个完美预测的分支给关键路径的依赖链增加了0个周期。）

在C++中，使用std::min和std::max，它们是根据或<定义的，对NaN行为的要求与fmin和fmax不同。避免fmin和fmax以提高性能，除非您需要它们的NaN行为。

在C中，我认为只需编写自己的min和max函数（如果安全的话，也可以编写宏）。

Godbolt编译器资源管理器上的C&asm

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，或者想要特别处理它们，那么可以编写如下内容

lowest = _mm_min_ps(lowest, some_loop_variable);

假设您的标量代码类似于

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

假设条件可以用CMPP向量化，所以您有一个位全部设置或全部清零的元素向量。（或者，如果您只关心它们的符号，而不关心负零，您也可以直接使用浮点上的andps/orps/xorps。这会在符号位中创建一个真值，在其他地方产生垃圾。BLENDVPS只查看符号位，因此这会非常有用。或者您可以使用psrad xmm,31广播符号位。）

实现这一点的直接方法是基于条件掩码混合x和+inf。或者执行newval=min（最低，x)；并将newval混合到最低中。（可以是BLENDVPS或and/andnot/or）。

但诀窍在于，全一位是一个NaN，按位或将传播它。所以：

__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个UOP）。