[LangRef] Element-wise Integral Reduction Intrinsics

[lebedev.ri]

Summary

This is the proposed wording for the [RFC] Integer Intrinsics for abs, in unsigned/signed min/max.

Link to RFC:
https://lists.llvm.org/pipermail/llvm-dev/2020-June/142257.html

Proposed alive2 implementation: https://github.com/AliveToolkit/alive2/pull/353

[nikic]

I find the naming of these intrinsics somewhat unintuitive. My first association with llvm.reduce.smax is that this is the non-experimental version of llvm.experimental.vector.reduce.smax, because reduction (to me) carries a strong vector reduction connotation. I can still see how these might be "reductions" for min/max (in which case I would expect the intrinsics to be variadic though), but not seeing the analogy at all for abs().

I would suggest to instead call these just llvm.smax, llvm.abs etc, which seems more in line with existing integer intrinsic names.

[xbolva00]

yeah, “reduce” should be dropped

[xbolva00]

llvm/docs/LangRef.rst

15208

What abouts nabs?

We pattern match it currently too.

[lebedev.ri]

Per popular demand, drop .reduce. from intrinsic names.

[spatel]

llvm/docs/LangRef.rst

15082–15088

We should avoid "reduction" vocabulary with any of these operations since that term is already used for vector ops.

abs() belongs in the "Standard C Library Intrinsics" section that starts around line 12099.
If we relax that title to "Standard C/C++ Library Intrinsics", then min/max can live there too?

15108–15109

Return the larger of a and b comparing the values as signed integers.
Vector intrinsics operate on a per-element basis. The larger element of a and b at a given index is returned for that index.

15116

I'd remove the "return type matches..." line above and work that clause in here:
"The argument types must match each other, and the return type must match the argument type."

15137

Return the smaller of a and b comparing the values as signed integers.
Vector intrinsics operate on a per-element basis. The smaller element of a and b at a given index is returned for that index.

15166–15168

Return the larger of a and b comparing the values as unsigned integers.
Vector intrinsics operate on a per-element basis. The larger element of a and b at a given index is returned for that index.

15195–15196

Return the smaller of a and b comparing the values as unsigned integers.
Vector intrinsics operate on a per-element basis. The smaller element of a and b at a given index is returned for that index.

15218–15219

Do we need to include the poison option?

The SDAG node only has:

/// Note: A value of INT_MIN will return INT_MIN, no saturation or overflow
/// is performed.

[nikic]

llvm/docs/LangRef.rst

15208

We do, but it's probably much less common than abs() and doesn't have any backend support. I think we can get away with representing it as 0 - abs(x) (or just the same way we do now).

15218–15219

The poison option is the equivalent of the sub nsw flag that was used previously. It doesn't matter for lowering, but it is used for analysis sometimes, in particular we can only assume that the llvm.abs() result is actually positive if the poison flag is set.

15236

Missing space before "if".

[lebedev.ri]

@spatel @nikic @xbolva00 thank you for taking a look!
Addressing review notes.

[lebedev.ri]

llvm/docs/LangRef.rst

15208

We do indeed have SPF_NABS, but i strongly believe that is again because we have to, not because it's useful.
Given, -(a < 0 ? -a : a), currently, we can't possibly preserve that pattern from sinking negation into it.
And as soon as it's sunk, it is no longer an ABS, and we've lost track of it.
If we have an intrinsic, that will no longer be an issue.
I currently see no need for nabs intinsic.

15218–15219

The poison option is the equivalent of the sub nsw flag that was used previously.

Precisely, yes. This intrinsic will be pretty powerless without that flag.

[simoll]

llvm/docs/LangRef.rst

15218–15219

Couldn't we add integer overflow flags to CallInsts the same way we have fast math flags? That should make this extra argument redundant.
Also, this would allow us to have nsw, nuw on VP intrinsics (https://llvm.org/docs/LangRef.html#id2355) and other integer intrinsics.

[spatel]

LGTM - see inline for grammar nits. Please remove "Reduction" from the title of this review too.

But we should wait at least a week before pushing in case there is more feedback here or on llvm-dev.

llvm/docs/LangRef.rst

12115

Remove comma after "width".

12132

Remove comma after "type".

12136

typo: a a

12143–12144

First line is a bit awkward to me. How about:
"Returns the magnitude (always positive) of the argument or each element of a vector argument."

12155

Remove comma after "width".

12172

Remove comma after "type".

12184

Remove comma after "width".

12201

Remove comma after "type".

12213

Remove comma after "width".

12230

Remove comma after "type".

12242

Remove comma after "width".

12259

Remove comma after "type".

[lebedev.ri]

@spatel thank you for taking a look!
Addressing various typo nits.

llvm/docs/LangRef.rst

15218–15219

Possibly, but that seems like a more general rework that doesn't have to block this.

[nikic]

LGTM as well.

llvm/docs/LangRef.rst

12125

nit: "returns *the* absolute value"

12143–12144

The (always positive) note seems a bit odd here, given the INT_MIN behavior.

[nhaehnle]

This LGTM, but it shouldn't be committed without an actual implementation.

[lebedev.ri]

In D81829#2100445, @nhaehnle wrote:

This LGTM,

but it shouldn't be committed without an actual implementation.

I'm going to assume that by implementation only the actual addition of the intrinsics is meant,
not any/all of the piping/teaching about the new intrinsics.

[nikic]

@lebedev.ri As we already have the corresponding SDAG nodes, I would expect the initial implementation to just add the intrinsics, the SDAG builder code, and a cursory X86 test that the intrinsics get lowered.

[nikic]

As there hasn't been any further feedback on llvm-dev, time to move forward with this?

[xbolva00]

+1, but initial implementation should be done first, as noted here:

In D81829#2100445, @nhaehnle wrote:

This LGTM, but it shouldn't be committed without an actual implementation.

llvm/docs/LangRef.rst

 .. _int_memcpy:
 
 '``llvm.memcpy``' Intrinsic
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
 Syntax:
 """""""
 
 This is an overloaded intrinsic. You can use ``llvm.memcpy`` on any
 integer bit width and for different address spaces. Not all targets
 support all bit widths however.
 
 ::
 
       declare void @llvm.memcpy.p0i8.p0i8.i32(i8* <dest>, i8* <src>,
                                               i32 <len>, i1 <isvolatile>)
       declare void @llvm.memcpy.p0i8.p0i8.i64(i8* <dest>, i8* <src>,
                                               i64 <len>, i1 <isvolatile>)
 
 Overview:
 """""""""
 
 The '``llvm.memcpy.*``' intrinsics copy a block of memory from the
 source location to the destination location.
 
 Note that, unlike the standard libc function, the ``llvm.memcpy.*``
 intrinsics do not return a value, takes extra isvolatile
 arguments and the pointers can be in specified address spaces.
 
 Arguments:
 """"""""""
 
 The first argument is a pointer to the destination, the second is a
 pointer to the source. The third argument is an integer argument
 specifying the number of bytes to copy, and the fourth is a
 boolean indicating a volatile access.
 
 The :ref:`align <attr_align>` parameter attribute can be provided
 for the first and second arguments.
 
 If the ``isvolatile`` parameter is ``true``, the ``llvm.memcpy`` call is
 a :ref:`volatile operation <volatile>`. The detailed access behavior is not
 very cleanly specified and it is unwise to depend on it.
 
 Semantics:
 """"""""""
 
 The '``llvm.memcpy.*``' intrinsics copy a block of memory from the
 source location to the destination location, which are not allowed to
 overlap. It copies "len" bytes of memory over. If the argument is known
 to be aligned to some boundary, this can be specified as an attribute on
 the argument.
 
 If "len" is 0, the pointers may be NULL or dangling. However, they must still
 be appropriately aligned.
 
 .. _int_memcpy_inline:
 
 '``llvm.memcpy.inline``' Intrinsic
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
 Syntax:
 """""""
 
 This is an overloaded intrinsic. You can use ``llvm.memcpy.inline`` on any
 integer bit width and for different address spaces. Not all targets
 support all bit widths however.
 
 ::
 
       declare void @llvm.memcpy.inline.p0i8.p0i8.i32(i8* <dest>, i8* <src>,
                                                      i32 <len>, i1 <isvolatile>)
       declare void @llvm.memcpy.inline.p0i8.p0i8.i64(i8* <dest>, i8* <src>,
                                                      i64 <len>, i1 <isvolatile>)
 
 Overview:
 """""""""
 
 The '``llvm.memcpy.inline.*``' intrinsics copy a block of memory from the
 source location to the destination location and guarantees that no external
 functions are called.
 
 Note that, unlike the standard libc function, the ``llvm.memcpy.inline.*``
 intrinsics do not return a value, takes extra isvolatile
 arguments and the pointers can be in specified address spaces.
 
 Arguments:
 """"""""""
 
 The first argument is a pointer to the destination, the second is a
 pointer to the source. The third argument is a constant integer argument
 specifying the number of bytes to copy, and the fourth is a
 boolean indicating a volatile access.
 
 The :ref:`align <attr_align>` parameter attribute can be provided
 for the first and second arguments.
 
 If the ``isvolatile`` parameter is ``true``, the ``llvm.memcpy.inline`` call is
 a :ref:`volatile operation <volatile>`. The detailed access behavior is not
 very cleanly specified and it is unwise to depend on it.
 
 Semantics:
 """"""""""
 
 The '``llvm.memcpy.inline.*``' intrinsics copy a block of memory from the
 source location to the destination location, which are not allowed to
 overlap. It copies "len" bytes of memory over. If the argument is known
 to be aligned to some boundary, this can be specified as an attribute on
 the argument.
 
 If "len" is 0, the pointers may be NULL or dangling. However, they must still
 be appropriately aligned.
 
 The generated code is guaranteed not to call any external functions.
 
 .. _int_memmove:
 
 '``llvm.memmove``' Intrinsic
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
 Syntax:
 """""""
 
 This is an overloaded intrinsic. You can use llvm.memmove on any integer
 bit width and for different address space. Not all targets support all
 bit widths however.
 
 ::
 
       declare void @llvm.memmove.p0i8.p0i8.i32(i8* <dest>, i8* <src>,
                                                i32 <len>, i1 <isvolatile>)
       declare void @llvm.memmove.p0i8.p0i8.i64(i8* <dest>, i8* <src>,
                                                i64 <len>, i1 <isvolatile>)
 
 Overview:
 """""""""
 
 The '``llvm.memmove.*``' intrinsics move a block of memory from the
 source location to the destination location. It is similar to the
 '``llvm.memcpy``' intrinsic but allows the two memory locations to
 overlap.
 
 Note that, unlike the standard libc function, the ``llvm.memmove.*``
 intrinsics do not return a value, takes an extra isvolatile
 argument and the pointers can be in specified address spaces.
 
 Arguments:
 """"""""""
 
 The first argument is a pointer to the destination, the second is a
 pointer to the source. The third argument is an integer argument
 specifying the number of bytes to copy, and the fourth is a
 boolean indicating a volatile access.
 
 The :ref:`align <attr_align>` parameter attribute can be provided
 for the first and second arguments.
 
 If the ``isvolatile`` parameter is ``true``, the ``llvm.memmove`` call
 is a :ref:`volatile operation <volatile>`. The detailed access behavior is
 not very cleanly specified and it is unwise to depend on it.
 

 """"""""""
 
 The '``llvm.loop.decrement.*``' intrinsics do a ``SUB`` of the loop iteration
 counter with the given loop decrement value, and return false if the loop
 should exit, this ``SUB`` is not allowed to wrap. The result is a condition
 that is used by the conditional branch controlling the loop.
 
 
+Element-wise Reduction Intrinsics
+---------------------------------
+
+Element-wise reductions between two arguments can be expressed using the
+following intrinsics. Each one takes two operands as an input and applies its
+respective operation to the arguments element-wise, returning result of the
+same type as the argument type.
+
+
+'``llvm.smax.*``' Intrinsic
+^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+Syntax:
+"""""""
+
+This is an overloaded intrinsic. You can use ``@llvm.smax`` on any
+integer bit width, or any vector of integer elements.
+
+::
+
+      declare i32 @llvm.smax.i32(i32 %a, i32 %b)
+      declare <4 x i32> @llvm.smax.v4i32(<4 x i32> %a, <4 x i32> %b)
+
+Overview:
+"""""""""
+
+The '``llvm.smax.*``' intrinsics do a signed integer ``MAX``
+element-wise reduction between the arguments.
+The return type matches the type of the arguments.
+
+Arguments:
+""""""""""
+
+The arguments (``%a`` and ``%b``) may be of any integer type, or a vector with
+integer element type. The return type must match the arguments type.
+``%a`` and ``%b`` are the two values that will undergo element-wise reduction.
+
+
+'``llvm.smin.*``' Intrinsic
+^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+Syntax:
+"""""""
+
+This is an overloaded intrinsic. You can use ``@llvm.smin`` on any
+integer bit width, or any vector of integer elements.
+
+::
+
+      declare i32 @llvm.smin.i32(i32 %a, i32 %b)
+      declare <4 x i32> @llvm.smin.v4i32(<4 x i32> %a, <4 x i32> %b)
+
+Overview:
+"""""""""
+
+The '``llvm.smin.*``' intrinsics do a signed integer ``MIN``
+element-wise reduction between the arguments.
+The return type matches the type of the arguments.
+
+Arguments:
+""""""""""
+
+The arguments (``%a`` and ``%b``) may be of any integer type, or a vector with
+integer element type. The return type must match the arguments type.
+``%a`` and ``%b`` are the two values that will undergo element-wise reduction.
+
+
+'``llvm.umax.*``' Intrinsic
+^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+Syntax:
+"""""""
+
+This is an overloaded intrinsic. You can use ``@llvm.umax`` on any
+integer bit width, or any vector of integer elements.
+
+::
+
+      declare i32 @llvm.umax.i32(i32 %a, i32 %b)
+      declare <4 x i32> @llvm.umax.v4i32(<4 x i32> %a, <4 x i32> %b)
+
+Overview:
+"""""""""
+
+The '``llvm.umax.*``' intrinsics do a unsigned integer ``MAX``
+element-wise reduction between the arguments.
+The return type matches the type of the arguments.
+
+Arguments:
+""""""""""
+
+The arguments (``%a`` and ``%b``) may be of any integer type, or a vector with
+integer element type. The return type must match the arguments type.
+``%a`` and ``%b`` are the two values that will undergo element-wise reduction.
+
+
+'``llvm.umin.*``' Intrinsic
+^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+Syntax:
+"""""""
+
+This is an overloaded intrinsic. You can use ``@llvm.umin`` on any
+integer bit width, or any vector of integer elements.
+
+::
+
+      declare i32 @llvm.umin.i32(i32 %a, i32 %b)
+      declare <4 x i32> @llvm.umin.v4i32(<4 x i32> %a, <4 x i32> %b)
+
+Overview:
+"""""""""
+
+The '``llvm.umin.*``' intrinsics do a unsigned integer ``MIN``
+element-wise reduction between the arguments.
+The return type matches the type of the arguments.
+
+Arguments:
+""""""""""
+
+The arguments (``%a`` and ``%b``) may be of any integer type, or a vector with
+integer element type. The return type must match the arguments type.
+``%a`` and ``%b`` are the two values that will undergo element-wise reduction.
+
+
+'``llvm.abs.*``' Intrinsic
+^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+Syntax:
+"""""""
+
+This is an overloaded intrinsic. You can use ``llvm.abs`` on any
+integer bit width, or any vector of integer elements.
+
+::
+
+      declare i32 @llvm.abs.i32(i32 <src>, i1 <is_int_min_poison>)
+      declare <4 x i32> @llvm.abs.v4i32(<4 x i32> <src>, i1 <is_int_min_poison>)
+
+Overview:
+"""""""""
+
+The '``llvm.abs``' family of intrinsic functions returns absolute value
+of an argument.
+
+Arguments:
+""""""""""
+
+The first argument is the value for which the absolute value is to be returned.
+This argument may be of any integer type, or a vector with integer element type.
+The return type must match the first argument type.
+
+The second argument must be a constant and is a flag to indicate whether the
+result value of the '``llvm.abs``' intrinsic is a a
+:ref:`poison value <poisonvalues>`if the argument is statically or dynamically
+an ``INT_MIN`` value.
+
+Semantics:
+""""""""""
+
+The '``llvm.abs``' intrinsic negates the argument, or each element of
+the argument if it is negative. If the argument is ``INT_MIN``, then the result
+is also ``INT_MIN`` if ``is_int_min_poison == 0`` and ``poison`` otherwise.
+
+.. _int_overflow:
+
+
 Experimental Vector Reduction Intrinsics
 ----------------------------------------
 
 Horizontal reductions of vectors can be expressed using the following
 intrinsics. Each one takes a vector operand as an input and applies its
 respective operation across all elements of the vector, returning a single
 scalar result of the same element type.