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

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

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



作者对应的代码只是

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++，相信它是相关的，但不是我的问题。

最佳答案

大多数 vector FP指令具有标量等效项。 MINSS / MAXSS / MINSD / MAXSD是您想要的。他们以您期望的方式处理+/- Infinity。
MINSS a,b根据IEEE规则精确地实现(a<b) ? a : b，它包含与零号，NaN和Infinities有关的所有内容。 (即，它使源操作数b保持无序。)这意味着编译器可以将它们用于std::min(b,a)和std::max(b,a)，因为这些函数基于相同的表达式。MAXSS a,b完全实现(b<a) ? a : b，再次将源操作数保持为无序。如果该数组包含任何NaN，则使用maxss xmm0, [rsi]循环遍历该数组将导致NaN，这将像其他FP操作一样在计算中传播NaN。这也意味着您可以使用NaN(使用xmm0)而不是-Inf或第一个数组元素来初始化pcmpeqd xmm0,xmm0；这可能会简化处理可能为空的列表的过程。

不要尝试在标量浮点数上使用_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.才提供内在函数。即使最终结果不依赖于上层元素中的任何内容，大多数编译器实际上也会发出无用的指令来执行此操作。没有什么像__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(boolean) 值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函数(或宏，如果您安全地执行此操作)。

[Godbolt编译器浏览器上的C和asm] [7]

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也可以使编译器实现良好的汇编的代码。
如果您不希望使用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)。
[7]:http://gcc.godbolt.org/#g:!((g:!((g:!((h:codeEditor,i:(j:1,options:(compileOnChange:'0'),source:'%23include+%3Calgorithm%3E%0A%23include+%3Ccmath%3E%0A%0Ausing+namespace+std%3B%0A%0Afloat+minfloat(float+a,+float+b)+%7B%0A++return+(a%3Cb)+%3F+a+:+b%3B++//+just+minss%0A%7D%0A%0Afloat+minfloat_std_nomov(float+a,+float+b)+%7B+return+std::min(b,+a)%3B+%7D%0A//+this+requires+a+movaps+because+it+can+only+produce+the+result+in+the+register+that+b+was+in%0A//+When+inlined+into+a+function,+that+might+be+fine:+this+isn!'t+%22worse%22,+just+opposite.%0A//+With+AVX,+the+result+can+go+in+any+register,+so+no+wasted+MOVAPS+instructions%0Afloat+minfloat_std_mov(float+a,+float+b)+%7B+return+std::min(a,b)%3B+%7D%0A%0A%0Afloat+minfloat_slow(float+a,+float+b)+%7B%0A++return+(a%3C%3Db)+%3F+a+:+b%3B+//+requires+NaN+and/or+negative-0+handling+different+from+what+minss+does%0A++//+icc+still+compiles+this+to+just+minss,+though%0A%7D%0A%0Afloat+minfloat_fmin(float+a,+float+b)+%7B%0A++return+fminf(a,+b)%3B%0A%7D%0A%0A%0A%0A%0A%23include+%3Cimmintrin.h%3E%0A%0A//+gcc+before+7.0+(at+least+as+far+back+as+gcc4.4.7)%0A//+treats+_mm_min_ps+as+commutative,+even+though+the+MINPS+instruction+isn!'t.%0A//+(MINPS+always+returns+the+2nd+operand+if+they!'re+unordered).%0A//+gcc+CSEs+tmp1+and+tmp2+into+a+single+MINPS,+instead+of+two+instructions+with%0A//+reversed+operands,+even+without+-ffast-math.%0A%0A//+from+https://github.com/Microsoft/ChakraCore/blob/master/lib/Runtime/Language/SimdFloat32x4OperationX86X64.cpp%23L230%0A__m128+minps_nan(const+__m128+a,+const+__m128+b)%0A%7B%0A++++++++//+if+tmp1+and+tmp2+are+not+identical+then+either%0A++++++++//+1)+at+least+one+value+is+NaN,+then+the+OR+will+set+that+lane+to+NaN%0A++++++++//+2)+one+value+is+0.0+and+the+other+is+-0.0,+the+OR+will+set+the+sign+bit+to+have+-0.0%0A++++++++__m128+tmp1+%3D+_mm_min_ps(a,+b)%3B%0A++++++++__m128+tmp2+%3D+_mm_min_ps(b,+a)%3B%0A++++++++__m128+x86Result+%3D+_mm_or_ps(tmp1,+tmp2)%3B%0A%0A++++++++return+x86Result%3B%0A%7D%0A//+ICC+and+clang+do+respect+the+order+of+the+args+to+_mm_min_ps,+even+though+Intel!'s%0A//+online+intrinsics+finder+doesn!'t+mention+that+behaviour+for+the+function.%0A//+It!'s+not+clear+whether+the+intrinsic+is+supposed+to+have+the+exact+semantics%0A//+of+the+MINPS+instruction,+or+not.%0A%0A//+IDK+if+that+was+intentional,+or+just+a+long-standing+bug.%0A//+https://gcc.gnu.org/ml/gcc/2005-01/msg00795.html+mentions+it+in+2005,+and+it+was+going+to+get+fixed+then.%0A%0A//+amusingly,+gcc+still+uses+a+MOVAPS+instructions,+because+I+guess+it+doesn!'t+CSE%0A//+until+after+deciding+that+it+needs+to+preserve+a+copy+of+a.%0A%0A%0A%23if+0%0A//+different+compilers+do+some+interesting+things+when+comparing+floats+against+0.%0A_Bool+double_neq_0(double+x)%0A%7B%0A%09return+x%3B%0A%7D%0A%0A_Bool+double_eq_0(double+x)%0A%7B%0A%09return+!!x%3B+//+%3D%3D+0%3B%0A%7D%0A%0A_Bool+double_notnot(double+x)%0A%7B%0A%09return+!!!!x%3B%0A%7D%0A%23endif'),l:'5',n:'1',o:'C%2B%2B+source+%231',t:'0')),k:50,l:'4',n:'0',o:'',s:0,t:'0'),(g:!((g:!((h:compiler,i:(compiler:g62,filters:(b:'0',commentOnly:'0',directives:'0',intel:'0'),options:'-Wall+-fno-fast-math+-O3+-fverbose-asm'),l:'5',n:'0',o:'%231+with+x86-64+gcc+6.2',t:'0')),k:50,l:'4',m:85.5392156862745,n:'0',o:'',s:0,t:'0'),(g:!((h:output,i:(compiler:1,editor:1),l:'5',n:'0',o:'%231+with+x86-64+gcc+6.2',t:'0')),l:'4',m:14.460784313725494,n:'0',o:'',s:0,t:'0')),k:50,l:'3',n:'0',o:'',t:'0')),l:'2',n:'0',o:'',t:'0'))，版本:4