llvm dev - Jun 2020 - [RFC] Integer Intrinsics for abs, in unsigned/signed min/max

Hello all.

This is a proposal to introduce 5 new integer intrinsics:
* absolute value
* signed min
* signed max
* unsigned min
* unsigned max

This is motivated by the fact that we keep working around
not having these intrinsics, and that constantly leads us into
having more workarounds, and causes infinite combine loops.

Here's a (likely incomplete!) list of motivational bugs:

infinite loops:
https://bugs.llvm.org/show_bug.cgi?id=46271 / https://reviews.llvm.org/D81698
https://bugs.llvm.org/show_bug.cgi?id=45539 /
https://reviews.llvm.org/rG01bcc3e93714
https://bugs.llvm.org/show_bug.cgi?id=44835 / https://reviews.llvm.org/D74278
https://reviews.llvm.org/D68408#1976760
https://reviews.llvm.org/D59378
https://bugs.llvm.org/show_bug.cgi?id=38915 / https://reviews.llvm.org/D51964
https://bugs.llvm.org/show_bug.cgi?id=37526 / https://reviews.llvm.org/rL332855

misc:
https://bugs.llvm.org/show_bug.cgi?id=44025
https://bugs.llvm.org/show_bug.cgi?id=43310 / https://reviews.llvm.org/rL372510
https://bugs.llvm.org/show_bug.cgi?id=35607
https://bugs.llvm.org/show_bug.cgi?id=35642 / https://reviews.llvm.org/D41136
https://bugs.llvm.org/show_bug.cgi?id=41083 / https://reviews.llvm.org/D74285
https://reviews.llvm.org/D70148
https://bugs.llvm.org/show_bug.cgi?id=31751 /
https://reviews.llvm.org/D26096 / https://reviews.llvm.org/rL293345

I believe we can do better than that if we stop just treating some IR patterns
as being canonical and desperately trying not to break/loose track of them,
but instead do a sensible thing and actually make them first class citizens,
by introducing intrinsics and use then throughout.

This has been previously discussed in:
https://lists.llvm.org/pipermail/llvm-dev/2016-November/106868.html

Proposed LangRef semantics: https://reviews.llvm.org/D81829
Proposed alive2 implementation: https://github.com/AliveToolkit/alive2/pull/353

Roman.

Thanks for putting this together! I am strongly in favor of this proposal.

My informal proposal in the llvm-dev link from 2016 was at least the 2nd
time this has come up. On each of the previous attempts, we decided that
the cost of analysis for what is usually a 2-instruction icmp+select
sequence was low enough that min/max intrinsics were not worth their
weight.

But that has proven wrong over time - the corner-cases change with each
fix, so we hit a new min/max infinite loop or missed optimization seemingly
every month or so. As noted, the list of problems shown here is only a
small sampling of the total.

We've shown that we can adapt IR analysis to use intrinsics for things like
overflowing/saturating math, and min/max/abs should be about the same level
of work. SelectionDAG already has equivalent nodes for these ops, so
connecting those with IR intrinsics is trivial.

On Mon, Jun 15, 2020 at 4:44 AM Roman Lebedev <lebedev.ri at gmail.com>
wrote:
> Hello all.
>
> This is a proposal to introduce 5 new integer intrinsics:
> * absolute value
> * signed min
> * signed max
> * unsigned min
> * unsigned max
>
> This is motivated by the fact that we keep working around
> not having these intrinsics, and that constantly leads us into
> having more workarounds, and causes infinite combine loops.
>
> Here's a (likely incomplete!) list of motivational bugs:
>
> infinite loops:
> https://bugs.llvm.org/show_bug.cgi?id=46271 /
> https://reviews.llvm.org/D81698
> https://bugs.llvm.org/show_bug.cgi?id=45539 /
> https://reviews.llvm.org/rG01bcc3e93714
> https://bugs.llvm.org/show_bug.cgi?id=44835 /
> https://reviews.llvm.org/D74278
> https://reviews.llvm.org/D68408#1976760
> https://reviews.llvm.org/D59378
> https://bugs.llvm.org/show_bug.cgi?id=38915 /
> https://reviews.llvm.org/D51964
> https://bugs.llvm.org/show_bug.cgi?id=37526 /
> https://reviews.llvm.org/rL332855
>
> misc:
> https://bugs.llvm.org/show_bug.cgi?id=44025
> https://bugs.llvm.org/show_bug.cgi?id=43310 /
> https://reviews.llvm.org/rL372510
> https://bugs.llvm.org/show_bug.cgi?id=35607
> https://bugs.llvm.org/show_bug.cgi?id=35642 /
> https://reviews.llvm.org/D41136
> https://bugs.llvm.org/show_bug.cgi?id=41083 /
> https://reviews.llvm.org/D74285
> https://reviews.llvm.org/D70148
> https://bugs.llvm.org/show_bug.cgi?id=31751 /
> https://reviews.llvm.org/D26096 / https://reviews.llvm.org/rL293345
>
> I believe we can do better than that if we stop just treating some IR
> patterns
> as being canonical and desperately trying not to break/loose track of them,
> but instead do a sensible thing and actually make them first class
> citizens,
> by introducing intrinsics and use then throughout.
>
> This has been previously discussed in:
> https://lists.llvm.org/pipermail/llvm-dev/2016-November/106868.html
>
> Proposed LangRef semantics: https://reviews.llvm.org/D81829
> Proposed alive2 implementation:
> https://github.com/AliveToolkit/alive2/pull/353
>
> Roman.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200615/1cf9a124/attachment.html>

I’m also generally in favor of adding these as target independent intrinsics. 
One question though - how are these “reductions”?  Why not use llvm.umax…
instead of llvm.reduce.umax?

-Chris
> On Jun 15, 2020, at 6:03 AM, Sanjay Patel via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> Thanks for putting this together! I am strongly in favor of this proposal.
> 
> My informal proposal in the llvm-dev link from 2016 was at least the 2nd
time this has come up. On each of the previous attempts, we decided that the
cost of analysis for what is usually a 2-instruction icmp+select sequence was
low enough that min/max intrinsics were not worth their weight.
> 
> But that has proven wrong over time - the corner-cases change with each
fix, so we hit a new min/max infinite loop or missed optimization seemingly
every month or so. As noted, the list of problems shown here is only a small
sampling of the total.
> 
> We've shown that we can adapt IR analysis to use intrinsics for things
like overflowing/saturating math, and min/max/abs should be about the same level
of work. SelectionDAG already has equivalent nodes for these ops, so connecting
those with IR intrinsics is trivial.
> 
> On Mon, Jun 15, 2020 at 4:44 AM Roman Lebedev <lebedev.ri at gmail.com
<mailto:lebedev.ri at gmail.com>> wrote:
> Hello all.
> 
> This is a proposal to introduce 5 new integer intrinsics:
> * absolute value
> * signed min
> * signed max
> * unsigned min
> * unsigned max
> 
> This is motivated by the fact that we keep working around
> not having these intrinsics, and that constantly leads us into
> having more workarounds, and causes infinite combine loops.
> 
> Here's a (likely incomplete!) list of motivational bugs:
> 
> infinite loops:
> https://bugs.llvm.org/show_bug.cgi?id=46271
<https://bugs.llvm.org/show_bug.cgi?id=46271> /
https://reviews.llvm.org/D81698 <https://reviews.llvm.org/D81698>
> https://bugs.llvm.org/show_bug.cgi?id=45539
<https://bugs.llvm.org/show_bug.cgi?id=45539> /
> https://reviews.llvm.org/rG01bcc3e93714
<https://reviews.llvm.org/rG01bcc3e93714>
> https://bugs.llvm.org/show_bug.cgi?id=44835
<https://bugs.llvm.org/show_bug.cgi?id=44835> /
https://reviews.llvm.org/D74278 <https://reviews.llvm.org/D74278>
> https://reviews.llvm.org/D68408#1976760
<https://reviews.llvm.org/D68408#1976760>
> https://reviews.llvm.org/D59378 <https://reviews.llvm.org/D59378>
> https://bugs.llvm.org/show_bug.cgi?id=38915
<https://bugs.llvm.org/show_bug.cgi?id=38915> /
https://reviews.llvm.org/D51964 <https://reviews.llvm.org/D51964>
> https://bugs.llvm.org/show_bug.cgi?id=37526
<https://bugs.llvm.org/show_bug.cgi?id=37526> /
https://reviews.llvm.org/rL332855 <https://reviews.llvm.org/rL332855>
> 
> misc:
> https://bugs.llvm.org/show_bug.cgi?id=44025
<https://bugs.llvm.org/show_bug.cgi?id=44025>
> https://bugs.llvm.org/show_bug.cgi?id=43310
<https://bugs.llvm.org/show_bug.cgi?id=43310> /
https://reviews.llvm.org/rL372510 <https://reviews.llvm.org/rL372510>
> https://bugs.llvm.org/show_bug.cgi?id=35607
<https://bugs.llvm.org/show_bug.cgi?id=35607>
> https://bugs.llvm.org/show_bug.cgi?id=35642
<https://bugs.llvm.org/show_bug.cgi?id=35642> /
https://reviews.llvm.org/D41136 <https://reviews.llvm.org/D41136>
> https://bugs.llvm.org/show_bug.cgi?id=41083
<https://bugs.llvm.org/show_bug.cgi?id=41083> /
https://reviews.llvm.org/D74285 <https://reviews.llvm.org/D74285>
> https://reviews.llvm.org/D70148 <https://reviews.llvm.org/D70148>
> https://bugs.llvm.org/show_bug.cgi?id=31751
<https://bugs.llvm.org/show_bug.cgi?id=31751> /
> https://reviews.llvm.org/D26096 <https://reviews.llvm.org/D26096> /
https://reviews.llvm.org/rL293345 <https://reviews.llvm.org/rL293345>
> 
> I believe we can do better than that if we stop just treating some IR
patterns
> as being canonical and desperately trying not to break/loose track of them,
> but instead do a sensible thing and actually make them first class
citizens,
> by introducing intrinsics and use then throughout.
> 
> This has been previously discussed in:
> https://lists.llvm.org/pipermail/llvm-dev/2016-November/106868.html
<https://lists.llvm.org/pipermail/llvm-dev/2016-November/106868.html>
> 
> Proposed LangRef semantics: https://reviews.llvm.org/D81829
<https://reviews.llvm.org/D81829>
> Proposed alive2 implementation:
https://github.com/AliveToolkit/alive2/pull/353
<https://github.com/AliveToolkit/alive2/pull/353>
> 
> Roman.
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://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/20200615/2d4f60aa/attachment.html>

I'll note that I was one of the folks previously skeptical of this 
idea.  I've been following activity on this in the meantime, and while 
I'm not 100% convinced this is the right direction, I'm also nowhere 
near as sure as I was that it isn't. :)

So, not quite a +1 from me, but not a -1 either.

I think it's completely reasonable to try this approach.  At worst, we 
decide it doesn't work either and simply canonicalize the new intrinsics 
to the existing IR patterns.  :)

Philip

On 6/15/20 1:43 AM, Roman Lebedev via llvm-dev wrote:
> Hello all.
>
> This is a proposal to introduce 5 new integer intrinsics:
> * absolute value
> * signed min
> * signed max
> * unsigned min
> * unsigned max
>
> This is motivated by the fact that we keep working around
> not having these intrinsics, and that constantly leads us into
> having more workarounds, and causes infinite combine loops.
>
> Here's a (likely incomplete!) list of motivational bugs:
>
> infinite loops:
> https://bugs.llvm.org/show_bug.cgi?id=46271 /
https://reviews.llvm.org/D81698
> https://bugs.llvm.org/show_bug.cgi?id=45539 /
> https://reviews.llvm.org/rG01bcc3e93714
> https://bugs.llvm.org/show_bug.cgi?id=44835 /
https://reviews.llvm.org/D74278
> https://reviews.llvm.org/D68408#1976760
> https://reviews.llvm.org/D59378
> https://bugs.llvm.org/show_bug.cgi?id=38915 /
https://reviews.llvm.org/D51964
> https://bugs.llvm.org/show_bug.cgi?id=37526 /
https://reviews.llvm.org/rL332855
>
> misc:
> https://bugs.llvm.org/show_bug.cgi?id=44025
> https://bugs.llvm.org/show_bug.cgi?id=43310 /
https://reviews.llvm.org/rL372510
> https://bugs.llvm.org/show_bug.cgi?id=35607
> https://bugs.llvm.org/show_bug.cgi?id=35642 /
https://reviews.llvm.org/D41136
> https://bugs.llvm.org/show_bug.cgi?id=41083 /
https://reviews.llvm.org/D74285
> https://reviews.llvm.org/D70148
> https://bugs.llvm.org/show_bug.cgi?id=31751 /
> https://reviews.llvm.org/D26096 / https://reviews.llvm.org/rL293345
>
> I believe we can do better than that if we stop just treating some IR
patterns
> as being canonical and desperately trying not to break/loose track of them,
> but instead do a sensible thing and actually make them first class
citizens,
> by introducing intrinsics and use then throughout.
>
> This has been previously discussed in:
> https://lists.llvm.org/pipermail/llvm-dev/2016-November/106868.html
>
> Proposed LangRef semantics: https://reviews.llvm.org/D81829
> Proposed alive2 implementation:
https://github.com/AliveToolkit/alive2/pull/353
>
> Roman.
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

On Mon, Jun 15, 2020 at 10:44 AM Roman Lebedev via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> Hello all.
>
> This is a proposal to introduce 5 new integer intrinsics:
> * absolute value
> * signed min
> * signed max
> * unsigned min
> * unsigned max
>
> This is motivated by the fact that we keep working around
> not having these intrinsics, and that constantly leads us into
> having more workarounds, and causes infinite combine loops.
>
> Here's a (likely incomplete!) list of motivational bugs:
>
> infinite loops:
> https://bugs.llvm.org/show_bug.cgi?id=46271 /
> https://reviews.llvm.org/D81698
> https://bugs.llvm.org/show_bug.cgi?id=45539 /
> https://reviews.llvm.org/rG01bcc3e93714
> https://bugs.llvm.org/show_bug.cgi?id=44835 /
> https://reviews.llvm.org/D74278
> https://reviews.llvm.org/D68408#1976760
> https://reviews.llvm.org/D59378
> https://bugs.llvm.org/show_bug.cgi?id=38915 /
> https://reviews.llvm.org/D51964
> https://bugs.llvm.org/show_bug.cgi?id=37526 /
> https://reviews.llvm.org/rL332855
>
> misc:
> https://bugs.llvm.org/show_bug.cgi?id=44025
> https://bugs.llvm.org/show_bug.cgi?id=43310 /
> https://reviews.llvm.org/rL372510
> https://bugs.llvm.org/show_bug.cgi?id=35607
> https://bugs.llvm.org/show_bug.cgi?id=35642 /
> https://reviews.llvm.org/D41136
> https://bugs.llvm.org/show_bug.cgi?id=41083 /
> https://reviews.llvm.org/D74285
> https://reviews.llvm.org/D70148
> https://bugs.llvm.org/show_bug.cgi?id=31751 /
> https://reviews.llvm.org/D26096 / https://reviews.llvm.org/rL293345
>
> I believe we can do better than that if we stop just treating some IR
> patterns
> as being canonical and desperately trying not to break/loose track of them,
> but instead do a sensible thing and actually make them first class
> citizens,
> by introducing intrinsics and use then throughout.
>
> This has been previously discussed in:
> https://lists.llvm.org/pipermail/llvm-dev/2016-November/106868.html
>
> Proposed LangRef semantics: https://reviews.llvm.org/D81829
> Proposed alive2 implementation:
> https://github.com/AliveToolkit/alive2/pull/353
>
I'm also strongly in favor of this proposal.

Next to the issues already mentioned, this also fixes issues related to
undef handling. For example, umax(%x, C) is not actually guaranteed to
be
>= C. That's because the current umax representation has two uses of %x,
which may take on independent values if %x is undef. This makes a number of
"common sense" folds invalid. Having dedicated min/max intrinsics
avoids
that problem.

Regards,
Nikita
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200615/3e4d827c/attachment.html>

As per popular demand i've dropped misleading "reduction"
wording/naming from them, updated https://reviews.llvm.org/D81829

So far all the responses are favorable to this proposal.

Roman.

On Mon, Jun 15, 2020 at 11:58 PM Nikita Popov <nikita.ppv at gmail.com>
wrote:
>
> On Mon, Jun 15, 2020 at 10:44 AM Roman Lebedev via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
>>
>> Hello all.
>>
>> This is a proposal to introduce 5 new integer intrinsics:
>> * absolute value
>> * signed min
>> * signed max
>> * unsigned min
>> * unsigned max
>>
>> This is motivated by the fact that we keep working around
>> not having these intrinsics, and that constantly leads us into
>> having more workarounds, and causes infinite combine loops.
>>
>> Here's a (likely incomplete!) list of motivational bugs:
>>
>> infinite loops:
>> https://bugs.llvm.org/show_bug.cgi?id=46271 /
https://reviews.llvm.org/D81698
>> https://bugs.llvm.org/show_bug.cgi?id=45539 /
>> https://reviews.llvm.org/rG01bcc3e93714
>> https://bugs.llvm.org/show_bug.cgi?id=44835 /
https://reviews.llvm.org/D74278
>> https://reviews.llvm.org/D68408#1976760
>> https://reviews.llvm.org/D59378
>> https://bugs.llvm.org/show_bug.cgi?id=38915 /
https://reviews.llvm.org/D51964
>> https://bugs.llvm.org/show_bug.cgi?id=37526 /
https://reviews.llvm.org/rL332855
>>
>> misc:
>> https://bugs.llvm.org/show_bug.cgi?id=44025
>> https://bugs.llvm.org/show_bug.cgi?id=43310 /
https://reviews.llvm.org/rL372510
>> https://bugs.llvm.org/show_bug.cgi?id=35607
>> https://bugs.llvm.org/show_bug.cgi?id=35642 /
https://reviews.llvm.org/D41136
>> https://bugs.llvm.org/show_bug.cgi?id=41083 /
https://reviews.llvm.org/D74285
>> https://reviews.llvm.org/D70148
>> https://bugs.llvm.org/show_bug.cgi?id=31751 /
>> https://reviews.llvm.org/D26096 / https://reviews.llvm.org/rL293345
>>
>> I believe we can do better than that if we stop just treating some IR
patterns
>> as being canonical and desperately trying not to break/loose track of
them,
>> but instead do a sensible thing and actually make them first class
citizens,
>> by introducing intrinsics and use then throughout.
>>
>> This has been previously discussed in:
>> https://lists.llvm.org/pipermail/llvm-dev/2016-November/106868.html
>>
>> Proposed LangRef semantics: https://reviews.llvm.org/D81829
>> Proposed alive2 implementation:
https://github.com/AliveToolkit/alive2/pull/353
>
>
> I'm also strongly in favor of this proposal.
>
> Next to the issues already mentioned, this also fixes issues related to
undef handling. For example, umax(%x, C) is not actually guaranteed to be >=
C. That's because the current umax representation has two uses of %x, which
may take on independent values if %x is undef. This makes a number of
"common sense" folds invalid. Having dedicated min/max intrinsics
avoids that problem.
>
> Regards,
> Nikita