Specify Clang vector builtins.

[fhahn]

Summary

This patch specifies a set of vector builtins for Clang, as discussed on
cfe-dev:
https://lists.llvm.org/pipermail/cfe-dev/2021-September/068999.html
https://lists.llvm.org/pipermail/cfe-dev/2021-October/069070.html

[craig.topper]

clang/docs/LanguageExtensions.rst

552

I'm not sure I understand what is being concatenated here.

[scanon]

clang/docs/LanguageExtensions.rst

538

"Prevailing rounding mode" is not super-useful, other than as a spelling for round-to-nearest-ties-to-even (IEEE 754 default rounding). Outside of a FENV_ACCESS ON context, there's not even really a notion of "prevailing rounding mode" to appeal to. I assume the intent is for this to lower to e.g. x86 ROUND* with the dynamic rounding-mode immediate.

I would recommend adding __builtin_elementwise_roundeven(T x) instead, which would statically bind IEEE default rounding (following TS 18661-1 naming) without having to appeal to prevailing rounding mode, and can still lower to ROUND* on x86 outside of FENV_ACCESS ON contexts, which is the norm for vector code (and FRINTN unconditionally on armv8). I think we can punt on rint/nearbyint for now, and add them in the future if there's a need.

[scanon]

clang/docs/LanguageExtensions.rst

565

Should be restricted to integer types.

[scanon]

clang/docs/LanguageExtensions.rst

565

(Never mind, somehow read this as & instead of \+.)

[fhahn]

Try to be more precise about how the reduction steps are performed and replace _round and _rint by roundeven.

[fhahn]

clang/docs/LanguageExtensions.rst

538

I removed rint and round for now and add` _roundeven` with the wording from TS 18661-1

552

I tried to spell it out more clearly. I'm still not sure if that spells it out as clearly as possibly and I'd appreciate any suggestions on how to improve the wording.

[craig.topper]

clang/docs/LanguageExtensions.rst

552

The input is a single vector. I'm not understanding where we get a second vector to concatenate.

[fhahn]

Another stab at phrasing the reduction step. Also added a note that the implementation is work-in-progress.

[fhahn]

clang/docs/LanguageExtensions.rst

552

Oh yes, now I see where the confusion was coming from. I was thinking about the reduction tree and how the input is broken up. Sorry for the confusing wording. I gave it another try, should be much simpler again now.

[scanon]

I'm happy with this now.

clang/docs/LanguageExtensions.rst

552

It's unclear because there's no apparent "first" or "second" vector; there's just a single argument, and the result isn't a vector, it's a scalar. I think you want to say something like: "the operation is repeatedly applied to adjacent pairs of elements until the result is a scalar" and then provide a worked example.

[craig.topper]

clang/docs/LanguageExtensions.rst

552

Should it somehow mention the pair is the even element i and the odd element i+1. There are n-1 adjacent pairs in an n element vector, but we want non-overlapping pairs.

Should probably spell out the non-power2 behavior. Presumably we pad identity elements after the last element to widen the vector out to a power 2 and then proceed normally?

[kparzysz]

clang/docs/LanguageExtensions.rst

553

It's really not clear what "horizontal recursive pairwise" means unless one has read the mailing list discussions. Maybe you could spell it out, e.g. "recursive even-odd pairwise reduction" or something like that.

[fhahn]

Thanks for the latest set of comments!

I tried to incorporate the suggestions about improving the reduction wording. I also added an example.

I also put up 2 patches to start with the implementation of min/max and the abs builtins in D111985 and D111986. I adjusted the supported types for __builtin_elementwise_abs to *signed* integer and floating point types.

[fhahn]

adjust padding wording.

[fhahn]

clang/docs/LanguageExtensions.rst

552

Should it somehow mention the pair is the even element i and the odd element i+1. There are n-1 adjacent pairs in an n element vector, but we want non-overlapping pairs.

Thanks, I tried to update the wording to make it clear that it operates on even-odd non-overlapping pairs.

Should probably spell out the non-power2 behavior. Presumably we pad identity elements after the last element to widen the vector out to a power 2 and then proceed normally?

Good point, done!

I think you want to say something like: "the operation is repeatedly applied to adjacent pairs of elements until the result is a scalar" and then provide a worked example.

Used and added an example.

553

Thanks, I used that wording!

[craig.topper]

clang/docs/LanguageExtensions.rst

557

widening -> widened

[fhahn]

Fix wording: widening -> widened, thanks!

[fhahn]

clang/docs/LanguageExtensions.rst

557

thanks, should be fixed!

[kito-cheng]

clang/docs/LanguageExtensions.rst

579

The example above use __builtin_reduce_fadd, but not listed here? or should we just use __builtin_reduce_add for floating point and fix the example?

[fhahn]

Thanks @kito-cheng, the example should use __builtin_reduce_add instead of _fadd! Fixed

[fhahn]

clang/docs/LanguageExtensions.rst

579

Thanks it should be _add instead of _fadd. fixed.

[fhahn]

Following feedback from D111986, explicitly spell out abs behavior of most negative integer as undefined.

[fhahn]

As @scanon pointed out in D111986, most simd implementations should handle abs(INT_MIN) consistently by returngin INT_MIN. It's therefore better to avoid defining abs(INT_MIN) as UB, which would make the intrinsic more difficult to use. I updated the abs definition to spell out the behavior of abs(INT_MIN) as returning INT_MIN.

clang/docs/LanguageExtensions.rst

 See also :ref:`langext-__builtin_shufflevector`, :ref:`langext-__builtin_convertvector`.
 
 .. [#] ternary operator(?:) has different behaviors depending on condition
   operand's vector type. If the condition is a GNU vector (i.e. __vector_size__),
   it's only available in C++ and uses normal bool conversions (that is, != 0).
   If it's an extension (OpenCL) vector, it's only available in C and OpenCL C.
   And it selects base on signedness of the condition operands (OpenCL v1.1 s6.3.9).
 
+Vector Builtins
+---------------
+
+**Note: The implementation of vector builtins is work-in-progress and incomplete.**
+
+In addition to the operators mentioned above, Clang provides a set of builtins
+to perform additional operations on certain scalar and vector types.
+
+Let ``T`` be one of the following types:
+
+* an integer type (as in C2x 6.2.5p19), but excluding enumerated types and _Bool
+* the standard floating types float or double
+* a half-precision floating point type, if one is supported on the target
+* a vector type.
+
+For scalar types, consider the operation applied to a vector with a single element.
+
+*Elementwise Builtins*
+
+Each builtin returns a vector equivalent to applying the specified operation
+elementwise to the input.
+
+Unless specified otherwise operation(±0) = ±0 and operation(±infinity) = ±infinity
+
+========================================= ================================================================ =========================================
+         Name                              Operation                                                        Supported element types
+========================================= ================================================================ =========================================
+ T __builtin_elementwise_abs(T x)          return the absolute value of a number x; the absolute value of   signed integer and floating point types
+                                           the most negative integer remains the most negative integer
+ T __builtin_elementwise_ceil(T x)         return the smallest integral value greater than or equal to x    floating point types
+ T __builtin_elementwise_floor(T x)        return the largest integral value less than or equal to x        floating point types
+ T __builtin_elementwise_roundeven(T x)    round x to the nearest integer value in floating point format,   floating point types
+                                           rounding halfway cases to even (that is, to the nearest value
+                                           that is an even integer), regardless of the current rounding
+                                           direction.
+ T__builtin_elementwise_trunc(T x)         return the integral value nearest to but no larger in            floating point types
+                                           magnitude than x
+ T __builtin_elementwise_max(T x, T y)     return x or y, whichever is larger                               integer and floating point types
+ T __builtin_elementwise_min(T x, T y)     return x or y, whichever is smaller                              integer and floating point types
+========================================= ================================================================ =========================================
+
+
+*Reduction Builtins*
+
+Each builtin returns a scalar equivalent to applying the specified
+operation(x, y) as recursive even-odd pairwise reduction to all vector
+elements. ``operation(x, y)`` is repeatedly applied to each non-overlapping
+even-odd element pair with indices ``i * 2`` and ``i * 2 + 1`` with
+``i in [0, Number of elements / 2)``. If the numbers of elements is not a
+power of 2, the vector is widened with neutral elements for the reduction
+at the end to the next power of 2.
+
+Example:
+
+.. code-block:: c++
+
+    __builtin_reduce_add([e3, e2, e1, e0]) = __builtin_reduced_add([e3 + e2, e1 + e0])
+                                           = (e3 + e2) + (e1 + e0)
+
+
+Let ``VT`` be a vector type and ``ET`` the element type of ``VT``.
+
+======================================= ================================================================ ==================================
+         Name                            Operation                                                        Supported element types
+======================================= ================================================================ ==================================
+ ET __builtin_reduce_max(VT a)           return x or y, whichever is larger; If exactly one argument is   integer and floating point types
+                                         a NaN, return the other argument. If both arguments are NaNs,
+                                         fmax() return a NaN.
+ ET __builtin_reduce_min(VT a)           return x or y, whichever is smaller; If exactly one argument     integer and floating point types
+                                         is a NaN, return the other argument. If both arguments are
+                                         NaNs, fmax() return a NaN.
+ ET __builtin_reduce_add(VT a)           \+                                                               integer and floating point types
+ ET __builtin_reduce_and(VT a)           &                                                                integer types
+ ET __builtin_reduce_or(VT a)            \|                                                               integer types
+ ET __builtin_reduce_xor(VT a)           ^                                                                integer types
+======================================= ================================================================ ==================================
+
 Matrix Types
 ============
 
 Clang provides an extension for matrix types, which is currently being
 implemented. See :ref:`the draft specification <matrixtypes>` for more details.
 
 For example, the code below uses the matrix types extension to multiply two 4x4
 float matrices and add the result to a third 4x4 matrix.