llvm dev - Nov 2018 - Proposed new min and max intrinsics

On Thu, Nov 8, 2018 at 11:35 PM Fabian Giesen via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> What is so complicated about these? Shouldn't they just correspond to
> two compares + selects?
>
> To give a concrete example, x86 MIN[SP][SD] and MAX[SP][SD],
> respectively, correspond exactly to
>
>    MIN*: select(a < b, a, b) (i.e. "a < b ? a : b")
>    MAX*: select(a > b, a, b) (i.e. "a > b ? a : b")
>
> IIRC, MINIMUM and MAXIMUM have the added requirement that they should
> return NaN if _either_ input is NaN, whereas the above will return NaN
> if the second input (i.e. b) is NaN, but not if the first is.
>
> So we need to explicitly catch the case where a is NaN as well. For
> minimum, that works out to something like:
>
>    %3 = fcmp olt float %a, %b
>    %4 = select i1 %3, float %a, float %b ; (a < b) ? a : b
>    %5 = fcmp ord float %a, %a ; true if !isNaN(a)
>    %6 = select i1 %5, float %4, float %a ; if a was NaN, return a
>
> for the entire operation. The logic here is that if isNaN(a) ||
> isNaN(b), the initial comparison will evaluate to false and %4 ends up
> being b. If isNaN(b), this is a NaN value (as required). The case we are
> missing is when isNaN(a) && !isNaN(b), where %4 is not a NaN; the
second
> compare + select fixes that one up.
>
> The first pair of these corresponds to a single (x86-style) MIN/MAX, and
> the second turns into a compare followed by (depending on target
> instruction set) either a BLEND or some logic ops.
>
> For minimumNumber/maximumNumber, you should be able to use a similar
> construction. Showing the example for minimumNumber here:
>
>    %3 = fcmp olt float %a, %b
>    %4 = select i1 %3, float %a, float %b ; (a < b) ? a : b
>    %5 = fcmp ord float %b, %b ; true if !isNaN(b)
>    %6 = select i1 %5, float %4, float %a ; if b was NaN, return a
>
> Starts out the same as before. Here, the tricky case is !isNaN(a)
&&
> isNaN(b). The initial select %4 will result in the (NaN) b in that case,
> and the second compare/select pair switches the result to a instead; we
> will only get a NaN result if both inputs were NaN.
>
> I might be missing something here, but that seems like a fairly harmless
> expansion, as such things go, and going to compiler-rt feels like overkill.
>
+1
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20181109/3bf0c105/attachment.html>

I would agree, but the expansion also has to properly treat negative zero
as less than zero, which leads to something like the following:

;; Find minimum if both zero
%a_sign = fgetsign %a
%b_sign = fgetsign %b
%a_is_lesser_zero = icmp ugt %a_sign, %b_sign
%minimum_zeros = select %a_is_lesser_zero, %a, %b

;; Find minimum if not both zero (from above)
%no_nan_and_a_lesser = fcmp olt %a, %b
%lesser_or_b_if_nan = select %no_nan_and_a_lesser, %a, %b
%a_not_nan = fcmp ord %a, %a
%minimum_not_zeros = select %a_not_nan, %lesser_or_b_if_nan, %a

;; Choose between zeros and not-zeros
%a_is_zero = fcmp oeq %a, 0
%b_is_zero = fcmp oeq %b, 0
%both_zero = and %a_is_zero, %b_is_zero
%minimum = select %both_zero, %minimum_zeros, %minimum_not_zeros

Which is considerably less reasonable.



On Fri, Nov 9, 2018 at 7:00 AM Cameron McInally via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> On Thu, Nov 8, 2018 at 11:35 PM Fabian Giesen via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
>> What is so complicated about these? Shouldn't they just correspond
to
>> two compares + selects?
>>
>> To give a concrete example, x86 MIN[SP][SD] and MAX[SP][SD],
>> respectively, correspond exactly to
>>
>>    MIN*: select(a < b, a, b) (i.e. "a < b ? a : b")
>>    MAX*: select(a > b, a, b) (i.e. "a > b ? a : b")
>>
>> IIRC, MINIMUM and MAXIMUM have the added requirement that they should
>> return NaN if _either_ input is NaN, whereas the above will return NaN
>> if the second input (i.e. b) is NaN, but not if the first is.
>>
>> So we need to explicitly catch the case where a is NaN as well. For
>> minimum, that works out to something like:
>>
>>    %3 = fcmp olt float %a, %b
>>    %4 = select i1 %3, float %a, float %b ; (a < b) ? a : b
>>    %5 = fcmp ord float %a, %a ; true if !isNaN(a)
>>    %6 = select i1 %5, float %4, float %a ; if a was NaN, return a
>>
>> for the entire operation. The logic here is that if isNaN(a) ||
>> isNaN(b), the initial comparison will evaluate to false and %4 ends up
>> being b. If isNaN(b), this is a NaN value (as required). The case we
are
>> missing is when isNaN(a) && !isNaN(b), where %4 is not a NaN;
the second
>> compare + select fixes that one up.
>>
>> The first pair of these corresponds to a single (x86-style) MIN/MAX,
and
>> the second turns into a compare followed by (depending on target
>> instruction set) either a BLEND or some logic ops.
>>
>> For minimumNumber/maximumNumber, you should be able to use a similar
>> construction. Showing the example for minimumNumber here:
>>
>>    %3 = fcmp olt float %a, %b
>>    %4 = select i1 %3, float %a, float %b ; (a < b) ? a : b
>>    %5 = fcmp ord float %b, %b ; true if !isNaN(b)
>>    %6 = select i1 %5, float %4, float %a ; if b was NaN, return a
>>
>> Starts out the same as before. Here, the tricky case is !isNaN(a)
&&
>> isNaN(b). The initial select %4 will result in the (NaN) b in that
case,
>> and the second compare/select pair switches the result to a instead; we
>> will only get a NaN result if both inputs were NaN.
>>
>> I might be missing something here, but that seems like a fairly
harmless
>> expansion, as such things go, and going to compiler-rt feels like
>> overkill.
>>
>
> +1
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20181109/8babe0fb/attachment.html>

On Fri, Nov 9, 2018 at 1:57 PM Thomas Lively <tlively at google.com>
wrote:
> I would agree, but the expansion also has to properly treat negative zero
> as less than zero,
>
I don't think libm does this. I'm also under the impression that
IEEE-754
doesn't specify this either. Could you point me to the clause that does
specify it?

> which leads to something like the following:
>
> ;; Find minimum if both zero
> %a_sign = fgetsign %a
> %b_sign = fgetsign %b
> %a_is_lesser_zero = icmp ugt %a_sign, %b_sign
> %minimum_zeros = select %a_is_lesser_zero, %a, %b
>
> ;; Find minimum if not both zero (from above)
> %no_nan_and_a_lesser = fcmp olt %a, %b
> %lesser_or_b_if_nan = select %no_nan_and_a_lesser, %a, %b
> %a_not_nan = fcmp ord %a, %a
> %minimum_not_zeros = select %a_not_nan, %lesser_or_b_if_nan, %a
>
> ;; Choose between zeros and not-zeros
> %a_is_zero = fcmp oeq %a, 0
> %b_is_zero = fcmp oeq %b, 0
> %both_zero = and %a_is_zero, %b_is_zero
> %minimum = select %both_zero, %minimum_zeros, %minimum_not_zeros
>
> Which is considerably less reasonable.
>
>
>
> On Fri, Nov 9, 2018 at 7:00 AM Cameron McInally via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
>> On Thu, Nov 8, 2018 at 11:35 PM Fabian Giesen via llvm-dev <
>> llvm-dev at lists.llvm.org> wrote:
>>
>>> What is so complicated about these? Shouldn't they just
correspond to
>>> two compares + selects?
>>>
>>> To give a concrete example, x86 MIN[SP][SD] and MAX[SP][SD],
>>> respectively, correspond exactly to
>>>
>>>    MIN*: select(a < b, a, b) (i.e. "a < b ? a : b")
>>>    MAX*: select(a > b, a, b) (i.e. "a > b ? a : b")
>>>
>>> IIRC, MINIMUM and MAXIMUM have the added requirement that they
should
>>> return NaN if _either_ input is NaN, whereas the above will return
NaN
>>> if the second input (i.e. b) is NaN, but not if the first is.
>>>
>>> So we need to explicitly catch the case where a is NaN as well. For
>>> minimum, that works out to something like:
>>>
>>>    %3 = fcmp olt float %a, %b
>>>    %4 = select i1 %3, float %a, float %b ; (a < b) ? a : b
>>>    %5 = fcmp ord float %a, %a ; true if !isNaN(a)
>>>    %6 = select i1 %5, float %4, float %a ; if a was NaN, return a
>>>
>>> for the entire operation. The logic here is that if isNaN(a) ||
>>> isNaN(b), the initial comparison will evaluate to false and %4 ends
up
>>> being b. If isNaN(b), this is a NaN value (as required). The case
we are
>>> missing is when isNaN(a) && !isNaN(b), where %4 is not a
NaN; the second
>>> compare + select fixes that one up.
>>>
>>> The first pair of these corresponds to a single (x86-style)
MIN/MAX, and
>>> the second turns into a compare followed by (depending on target
>>> instruction set) either a BLEND or some logic ops.
>>>
>>> For minimumNumber/maximumNumber, you should be able to use a
similar
>>> construction. Showing the example for minimumNumber here:
>>>
>>>    %3 = fcmp olt float %a, %b
>>>    %4 = select i1 %3, float %a, float %b ; (a < b) ? a : b
>>>    %5 = fcmp ord float %b, %b ; true if !isNaN(b)
>>>    %6 = select i1 %5, float %4, float %a ; if b was NaN, return a
>>>
>>> Starts out the same as before. Here, the tricky case is !isNaN(a)
&&
>>> isNaN(b). The initial select %4 will result in the (NaN) b in that
case,
>>> and the second compare/select pair switches the result to a
instead; we
>>> will only get a NaN result if both inputs were NaN.
>>>
>>> I might be missing something here, but that seems like a fairly
harmless
>>> expansion, as such things go, and going to compiler-rt feels like
>>> overkill.
>>>
>>
>> +1
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>
<https://urldefense.proofpoint.com/v2/url?u=http-3A__lists.llvm.org_cgi-2Dbin_mailman_listinfo_llvm-2Ddev&d=DwMFaQ&c=slrrB7dE8n7gBJbeO0g-IQ&r=O_4M49EtSpZ_-BQYeigzGv0P4__noMcSu2RYEjS1vKs&m=z5knBS-gNPEpc4ggdvRihjkzXuNMBoct19biXn7wwik&s=1cTiDQsdNprlvfeQYApN9ha9XRIuGNHANCtF2RvbWPk&e=>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20181109/53340539/attachment.html>

Ah, forget about the +-0 issue!

Slightly different way to handle them: XOR the two arguments, AND to 
keep only the sign bit, then OR it back into the result at the end (for 
minimum; maximum would do a bit clear/and-not).

The argument goes as follows:
1) If the two sign bits agree, this does nothing
2) If the two sign bits disagree:
   2.1) If the comparison was unordered, we already return a NaN; this 
makes us return a NaN with sign bit set. (But still a NaN. I don't see 
anything in the rules for minimum/maximum guaranteeing a specific NaN.)
   2.2) If the comparison was ordered and not between two 0s, the value 
with the sign bit set is the smaller one, so the OR ends up doing nothing.
   2.3) If the comparison was ordered and between two 0s, the OR 
guarantees we return a negative 0.

If you write this out with the required bitcasts it probably still gets 
lengthy in LLVM IR form (so might still want to put it in compiler-rt), 
but this seems like a preferable implementation provided the target lets 
you do the required bitwise ops on FP registers.

-Fabian

On 11/9/18 10:56 AM, Thomas Lively wrote:
> I would agree, but the expansion also has to properly treat negative 
> zero as less than zero, which leads to something like the following:
>
> ;; Find minimum if both zero
> %a_sign = fgetsign %a
> %b_sign = fgetsign %b
> %a_is_lesser_zero = icmp ugt %a_sign, %b_sign
> %minimum_zeros = select %a_is_lesser_zero, %a, %b
>
> ;; Find minimum if not both zero (from above)
> %no_nan_and_a_lesser = fcmp olt %a, %b
> %lesser_or_b_if_nan = select %no_nan_and_a_lesser, %a, %b
> %a_not_nan = fcmp ord %a, %a
> %minimum_not_zeros = select %a_not_nan, %lesser_or_b_if_nan, %a
>
> ;; Choose between zeros and not-zeros
> %a_is_zero = fcmp oeq %a, 0
> %b_is_zero = fcmp oeq %b, 0
> %both_zero = and %a_is_zero, %b_is_zero
> %minimum = select %both_zero, %minimum_zeros, %minimum_not_zeros
>
> Which is considerably less reasonable.
>
>
>
> On Fri, Nov 9, 2018 at 7:00 AM Cameron McInally via llvm-dev 
> <llvm-dev at lists.llvm.org <mailto:llvm-dev at
lists.llvm.org>> wrote:
>
>     On Thu, Nov 8, 2018 at 11:35 PM Fabian Giesen via llvm-dev
>     <llvm-dev at lists.llvm.org <mailto:llvm-dev at
lists.llvm.org>> wrote:
>
>         What is so complicated about these? Shouldn't they just
>         correspond to
>         two compares + selects?
>
>         To give a concrete example, x86 MIN[SP][SD] and MAX[SP][SD],
>         respectively, correspond exactly to
>
>            MIN*: select(a < b, a, b) (i.e. "a < b ? a : b")
>            MAX*: select(a > b, a, b) (i.e. "a > b ? a : b")
>
>         IIRC, MINIMUM and MAXIMUM have the added requirement that they
>         should
>         return NaN if _either_ input is NaN, whereas the above will
>         return NaN
>         if the second input (i.e. b) is NaN, but not if the first is.
>
>         So we need to explicitly catch the case where a is NaN as
>         well. For
>         minimum, that works out to something like:
>
>            %3 = fcmp olt float %a, %b
>            %4 = select i1 %3, float %a, float %b ; (a < b) ? a : b
>            %5 = fcmp ord float %a, %a ; true if !isNaN(a)
>            %6 = select i1 %5, float %4, float %a ; if a was NaN, return a
>
>         for the entire operation. The logic here is that if isNaN(a) ||
>         isNaN(b), the initial comparison will evaluate to false and %4
>         ends up
>         being b. If isNaN(b), this is a NaN value (as required). The
>         case we are
>         missing is when isNaN(a) && !isNaN(b), where %4 is not a
NaN;
>         the second
>         compare + select fixes that one up.
>
>         The first pair of these corresponds to a single (x86-style)
>         MIN/MAX, and
>         the second turns into a compare followed by (depending on target
>         instruction set) either a BLEND or some logic ops.
>
>         For minimumNumber/maximumNumber, you should be able to use a
>         similar
>         construction. Showing the example for minimumNumber here:
>
>            %3 = fcmp olt float %a, %b
>            %4 = select i1 %3, float %a, float %b ; (a < b) ? a : b
>            %5 = fcmp ord float %b, %b ; true if !isNaN(b)
>            %6 = select i1 %5, float %4, float %a ; if b was NaN, return a
>
>         Starts out the same as before. Here, the tricky case is
>         !isNaN(a) &&
>         isNaN(b). The initial select %4 will result in the (NaN) b in
>         that case,
>         and the second compare/select pair switches the result to a
>         instead; we
>         will only get a NaN result if both inputs were NaN.
>
>         I might be missing something here, but that seems like a
>         fairly harmless
>         expansion, as such things go, and going to compiler-rt feels
>         like overkill.
>
>
>     +1
>     _______________________________________________
>     LLVM Developers mailing list
>     llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
>     http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>