llvm dev - Jul 2021 - A thought on poison and select semantics

When working on a couple of recent changes in SCEV, I stumbled on a 
couple of gaps around how we optimize the @llvm.umin intrinsics.  If I 
remember correctly, we added these because they needed different poison 
propagation semantics than select, and that memory triggered a thought.

I want to raise the question of whether we should support both possible 
poison propagation semantics for the select instruction. As a brief 
review, the two options are:

 1. Poison propagates only through the selected operand.  e.g. "select
    i1 true, i32 0, i32 poison" is not poison.
 2. Poison propagates if any operand is poison.  e.g. "select i1 true,
    i32 0, i32 poison" is poison.

Each of the two options has advantages.  This was discussed in depth a 
while ago, and we'd picked (1).  I don't want to reopen that discussion;
I want to raise the question of whether we should pick "both".

If we were to add a flag "npo" (for "no poison operand",
bikeshedding
welcome!) to the select instruction, we could represent both options.  
This has a couple of advantages:

  * We can lower all of the umin/etc.. intrinsics to selects and avoid
    having to duplicate folds.  This  would reduce the combinatoric
    space for pattern matching optimizations.  This would probably help
    optimization results in practice.
  * We can restore many of the removed select->arithmetic folds (only
    for the npo selects).
  * We can infer npo flag on a select in many cases.  (e.g. "select i1
    %c, i32 0, i32 57" can be trivially converted to "select npo i1
%c,
    i32 0, i32 57")  This also allows us to factor logic into testable
    pieces whereas current transforms which are npo dependent must
    include the no-poison inference.

The major downside is that transformation code would have to be careful 
to only apply transforms dependent on "no poison operand" if the flag
is
set.

Anyways, I don't have time to actually work on this, so I'm mostly 
throwing out the idea in case anyone with time and motivation finds it 
interesting to pursue.

Philip

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20210701/4495897b/attachment.html>

On Thu, Jul 1, 2021 at 6:44 PM Philip Reames <listmail at
philipreames.com>
wrote:
> When working on a couple of recent changes in SCEV, I stumbled on a couple
> of gaps around how we optimize the @llvm.umin intrinsics.  If I remember
> correctly, we added these because they needed different poison propagation
> semantics than select, and that memory triggered a thought.
>
The min/max intrinsics have the same poison semantics as their select
forms. It's the undef semantics that differ.

However, I believe that the primary motivation for having the intrinsics is
that maintaining canonical SPF form is hard. Especially many InstCombine
optimizations need to be very careful about not breaking canonical SPF
form, because doing so will likely result in an infinite combine loop.
> I want to raise the question of whether we should support both possible
> poison propagation semantics for the select instruction.  As a brief
> review, the two options are:
>
>    1. Poison propagates only through the selected operand.  e.g.
"select
>    i1 true, i32 0, i32 poison" is not poison.
>    2. Poison propagates if any operand is poison.  e.g. "select i1
true,
>    i32 0, i32 poison" is poison.
>
> Each of the two options has advantages.  This was discussed in depth a
> while ago, and we'd picked (1).  I don't want to reopen that
discussion; I
> want to raise the question of whether we should pick "both".
>
> If we were to add a flag "npo" (for "no poison
operand", bikeshedding
> welcome!) to the select instruction, we could represent both options.  This
> has a couple of advantages:
>
>    - We can lower all of the umin/etc.. intrinsics to selects and avoid
>    having to duplicate folds.  This  would reduce the combinatoric space
for
>    pattern matching optimizations.  This would probably help optimization
>    results in practice.
>
> min/max intrinsics currently don't have full support in InstCombine
yet,
because we haven't ported all transforms from SPF min/max. Once that is
done and we canonicalize to the intrinsic form, we can drop the duplicate
SPF folds. From an optimization quality perspective, we're not ready to
canonicalize to intrinsics yet. Unfortunately, SCEVExpander has already
been switched to use intrinsics before this work completed, which is
presumably how you got here.
>
>    -
>    - We can restore many of the removed select->arithmetic folds (only
>    for the npo selects).
>
> Which transforms do you have in mind here? The select -> and/or
transform
is the only one I'm aware of, but in that case we're using select
specifically for it's current poison semantics, to prevent that fold from
happening where it is not legal.
>
>    - We can infer npo flag on a select in many cases.  (e.g. "select
i1
>    %c, i32 0, i32 57" can be trivially converted to "select npo
i1 %c, i32 0,
>    i32 57")  This also allows us to factor logic into testable pieces
whereas
>    current transforms which are npo dependent must include the no-poison
>    inference.
>
> The major downside is that transformation code would have to be careful to
> only apply transforms dependent on "no poison operand" if the
flag is set.
>
> Anyways, I don't have time to actually work on this, so I'm mostly
> throwing out the idea in case anyone with time and motivation finds it
> interesting to pursue.
>
With the above notes in mind, I'm not sure where having the flag would
really be advantageous.

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