[LangRef] Update shufflevector's semantics to return poison if the mask is undef

[aqjune]

Summary

This patch updates shufflevector's semantics to return poison if the mask is undef.
It resolves shufflevector-related bugs which is described at https://reviews.llvm.org/D93586.

This resolves many bugs that are marked as 'LLVM PR44185' at https://web.ist.utl.pt/nuno.lopes/alive2/index.php?hash=3c479a0f6691091c .

*But*, it also makes a few transformations invalid:

Transforms/InstCombine/broadcast.ll: https://bugs.llvm.org/show_bug.cgi?id=43958
Transforms/VectorCombine/X86/load.ll: a transformation that's similar to the previous one
Transforms/InstCombine/sub-of-negatible.ll:

define <2 x i4> @negate_shufflevector_oneinput_second_lane_is_undef(<2 x i4> %x, <2 x i4> %y) {
%0:
  %t0 = shl <2 x i4> { 10, 5 }, %x
  ; t1[2] is undef, not poison
  %t1 = shufflevector <2 x i4> %t0, <2 x i4> undef, 0, 2  
  %t2 = sub <2 x i4> %y, %t1
  ret <2 x i4> %t2
}
=>
define <2 x i4> @negate_shufflevector_oneinput_second_lane_is_undef(<2 x i4> %x, <2 x i4> %y) {
%0:
  %t0.neg = shl <2 x i4> { 6, 11 }, %x
  ; t1[2] is poison
  %t1.neg = shufflevector <2 x i4> %t0.neg, <2 x i4> undef, 0, 4294967295 
  %t2 = add <2 x i4> %t1.neg, %y
  ret <2 x i4> %t2
}
Transformation doesn't verify!
ERROR: Target is more poisonous than source

Transforms/InstCombine/insert-const-shuf.ll:

define <5 x i8> @longerMask(<3 x i8> %x) {
%0:
  ; %shuf[3] = undef
  %shuf = shufflevector <3 x i8> %x, <3 x i8> { undef, 1, 2 }, 2, 1, 4, 3, 0
  %ins = insertelement <5 x i8> %shuf, i8 42, i17 4
  ret <5 x i8> %ins
}
=>
define <5 x i8> @longerMask(<3 x i8> %x) {
%0:
  ; %shuf[3] = poison
  %shuf = shufflevector <3 x i8> %x, <3 x i8> { poison, 1, poison }, 2, 1, 4, 4294967295, 4294967295
  %ins = insertelement <5 x i8> %shuf, i8 42, i17 4
  ret <5 x i8> %ins
}
Transformation doesn't verify!
ERROR: Target is more poisonous than source

I think these transformations are all solvable: we can simply disable these transformations if insertelement/shufflevector's placeholder isn't poison.

[nlopes]

LGTM

[nikic]

Using undef in the shuffle mask to indicate a poison result seems pretty confusing to me. I think we should use poison as the marker instead. We could allow both undef/poison in input IR, but at least the output IR rendering should use poison (the internal representation is something else anyway, as shuffle masks are no longer Values).

[aqjune]

In D93818#2472270, @nikic wrote:

Using undef in the shuffle mask to indicate a poison result seems pretty confusing to me. I think we should use poison as the marker instead. We could allow both undef/poison in input IR, but at least the output IR rendering should use poison (the internal representation is something else anyway, as shuffle masks are no longer Values).

+1, I'll make a patch for this as well.

[aqjune]

It seems IR is already accepting poison masks: https://godbolt.org/z/K8ca84
Printing seems to be the only part to update. :)

[aqjune]

This patch was blocked by the old problematic select -> and/or folding, which is gone.
I'll restart pushing this patch as well as relevant ones (D94380, D93817).

[aqjune]

Update wordings

[aqjune]

Hi all,

Before diving into further updates in InstCombine (D94380 and D93817), what about pinning down this LangRef update first & letting people know via llvm-dev mail?

(Since this patch has been a while, D93586's description will be helpful to remind the context)

Since we have poison constant now, there is no big obstacle for making this semantic change.
I'd like to share the status & semantic change at llvm-dev so people don't accidentally introduce undef placeholders anymore.
I sent one mail in the last year (link) and got one positive feedback.

The remaining updates at D94380 and D93817 are about non-syntactic changes; before them, many syntactic updates to make the placeholder poison have been done so far (D9381 has links to such patches).
Actually, the two patches are still correct after this LangRef change; they're for recovering performance after poison is used as a don't-care vector.

[spatel]

In D93818#2804522, @aqjune wrote:

Hi all,

Before diving into further updates in InstCombine (D94380 and D93817), what about pinning down this LangRef update first & letting people know via llvm-dev mail?

That sounds good to me. I'm not sure about the different pieces that are left. I know we already updated many, but not all, places in IR to use poison *vector operand* for shufflevector with the change to IRBuilder, so making things consistent for that seems like an obviously good step. Changing the shuffle *mask* has different concerns? If there is still regression potential, can you re-describe those (here or on llvm-dev)?

The remaining updates at D94380 and D93817 are about non-syntactic changes; before them, many syntactic updates to make the placeholder poison have been done so far (D9381 has links to such patches).

Lost a digit in that link (D9381?).

[efriedma]

llvm/docs/LangRef.rst

9385

This seems like a weird thing to say. It's not really a semantic rule, just a suggestion for frontend and/or optimizations. Not sure it's really worth saying anything here at all. I mean, if we just want to give general advice to frontend/optimizations authors, it would just be "prefer poison over undef where possible", which isn't really specific to insertelement. Maybe we could just add an example to the "example" block.

9446

Maybe also explicitly note that if we select an undef element from an input vector, the resulting element is undef?

Any thoughts on whether we need to do anything for bitcode autoupgrade? I mean, it's unlikely to be a practical issue, but we could theoretically break the semantics of old IR. We could freeze the result to preserve the semantics of old bitcode.

[aqjune]

In D93818#2805725, @spatel wrote:

In D93818#2804522, @aqjune wrote:

Hi all,

Before diving into further updates in InstCombine (D94380 and D93817), what about pinning down this LangRef update first & letting people know via llvm-dev mail?

That sounds good to me. I'm not sure about the different pieces that are left. I know we already updated many, but not all, places in IR to use poison *vector operand* for shufflevector with the change to IRBuilder, so making things consistent for that seems like an obviously good step. Changing the shuffle *mask* has different concerns? If there is still regression potential, can you re-describe those (here or on llvm-dev)?

The left pieces are mainly about transformations that should preserve undefinedness of the don't-care vector. Consider this optimization

(InstCombineCast's shrinkSplatShuffle)
    // trunc (shuf X, Undef, SplatMask) --> shuf (trunc X), Undef, SplatMask

Since shufflevector's placeholder value is now poison, we can naively fix to this:

// trunc (shuf X, poison, SplatMask) --> shuf (trunc X), poison, SplatMask

But it means this transformation won't fire if the placeholder value was (accidentally) undef.
Avoiding this regression requires patches to contain more than simple syntactic UndefValue->PoisonValue replacement.

The difference between poison *vector operand* and poison *shuffle mask*: yep, they are different things, but related as well.
The whole story was as follows:
(1) To fix the bugs, it was concluded that insertelement's operand and shuffle mask must be poison.
(2) It was suggested that shufflevector's vector operand should be poison as well, since many transformations simply reuse insertelement's don't-care vector to create shufflevector with don't-care vector operand.
(3) A series of patches were made to fix insertelement/shufflevector's don't-care vector operand to be poison.
This LangRef is the first patch to make shuffle mask poison.

IMO there is no regression potential in theory. As select->and/or was done well, if transformations are properly updated things will work fine.

The remaining updates at D94380 and D93817 are about non-syntactic changes; before them, many syntactic updates to make the placeholder poison have been done so far (D9381 has links to such patches).

Lost a digit in that link (D9381?).

Oops, it was D93817, sorry.

[aqjune]

llvm/docs/LangRef.rst

9385

This is Arguments block, so I think talking about it is okay.
I think adding an example is a good idea, will put one to the example block.

9446

Maybe also explicitly note that if we select an undef element from an input vector, the resulting element is under?

+1

Any thoughts on whether we need to do anything for bitcode autoupgrade? I mean, it's unlikely to be a practical issue, but we could theoretically break the semantics of old IR. We could freeze the result to preserve the semantics of old bitcode.

This sounds legit, but it will introduce a lot of freeze instructions with extractelement/insertelement combined.
I'd like to hear other reviewer's opinion as well.

[aqjune]

Address comments

[jdoerfert]

llvm/docs/LangRef.rst

9460

Don't we need to talk about both poison and undef now? Sufflemask, for example, can still be undef, no?

[aqjune]

llvm/docs/LangRef.rst

9460

Combined with D103874, a mask value is constrained to either a constant integer or poison value.
This is to avoid confusion - an undef mask and a poison mask have no difference.

[aqjune]

llvm/docs/LangRef.rst

9460

I was wrong, it can still be undef because the patch is not fixing the parser.

Allowing undef masks helps avoid parsing errors that will happen if the frontend emits a shufflevector with an undef mask.
I will explicitly state that shufflevector is still accepting an undef mask, but it will be printed as a poison mask.

[aqjune]

Explicitly state that undef can be given as a shuffle mask and its meaning is equivalent to that of the poison mask

llvm/docs/LangRef.rst

 """"""""""
 
 The first operand of an '``insertelement``' instruction is a value of
 :ref:`vector <t_vector>` type. The second operand is a scalar value whose
 type must equal the element type of the first operand. The third operand
 is an index indicating the position at which to insert the value. The
 index may be a variable of any integer type.
 
+``poison`` vector is used for ``val`` if the input is a don't-care vector.
+using ``undef`` for ``val`` is not recommended because it prohibits
+optimizations to '``shufflevector``' with ``poison`` masks.
+
 Semantics:
 """"""""""
 
 The result is a vector of the same type as ``val``. Its element values
 are those of ``val`` except at position ``idx``, where it gets the value
 ``elt``. If ``idx`` exceeds the length of ``val`` for a fixed-length vector,
 the result is a :ref:`poison value <poisonvalues>`. For a scalable vector,
 if the value of ``idx`` exceeds the runtime length of the vector, the result
 is a :ref:`poison value <poisonvalues>`.
 
 Example:
 """"""""
 
 .. code-block:: text
 
       <result> = insertelement <4 x i32> %vec, i32 1, i32 0    ; yields <4 x i32>
+      <result> = insertelement <4 x i32> poison, i32 1, i32 0  ; creates <4 x i32> from a don't-care vector with the first element set to 1 and returns it
 
 .. _i_shufflevector:
 
 '``shufflevector``' Instruction
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
 Syntax:
 """""""

 the input and length that is the same as the shuffle mask.
 
 Arguments:
 """"""""""
 
 The first two operands of a '``shufflevector``' instruction are vectors
 with the same type. The third argument is a shuffle mask vector constant
 whose element type is ``i32``. The mask vector elements must be constant
-integers or ``undef`` values. The result of the instruction is a vector
+integers or ``poison`` values. The result of the instruction is a vector
 whose length is the same as the shuffle mask and whose element type is the
 same as the element type of the first two operands.
 
 Semantics:
 """"""""""
 
 The elements of the two input vectors are numbered from left to right
 across both of the vectors. For each element of the result vector, the
 shuffle mask selects an element from one of the input vectors to copy
 to the result. Non-negative elements in the mask represent an index
 into the concatenated pair of input vectors.
 
-If the shuffle mask is undefined, the result vector is undefined. If
-the shuffle mask selects an undefined element from one of the input
-vectors, the resulting element is undefined. An undefined element
-in the mask vector specifies that the resulting element is undefined.
-An undefined element in the mask vector prevents a poisoned vector
-element from propagating.
+If the shuffle mask is ``poison``, the result vector is ``poison``. If
+the shuffle mask selects a ``poison`` element from one of the input vectors,
+the resulting element is ``poison``. Similarly, if an ``undef`` element
+is selected, the result is ``undef`` as well. A ``poison`` element
+in the mask vector specifies that the resulting element is ``poison``.
+
+If the shuffle mask is ``undef``, the result vector is ``poison``. An ``undef``
+element in the mask vector specifies that the resulting element is ``poison``.
+Therefore, the result of ``shufflevector`` does not change even if the
+``poison`` mask is used instead of ``undef``, and vice versa.
+LLVM's assembly printer will print ``poison`` if ``undef`` was given to the
+shuffle mask because LLVM does not distinguish between them internally.
 
 For scalable vectors, the only valid mask values at present are
-``zeroinitializer`` and ``undef``, since we cannot write all indices as
-literals for a vector with a length unknown at compile time.
+``zeroinitializer``, ``undef`` and ``poison``, since we cannot write all
+indices as literals for a vector with a length unknown at compile time.
 
 Example:
 """"""""
 
 .. code-block:: text
 
       <result> = shufflevector <4 x i32> %v1, <4 x i32> %v2,
                               <4 x i32> <i32 0, i32 4, i32 1, i32 5>  ; yields <4 x i32>
-      <result> = shufflevector <4 x i32> %v1, <4 x i32> undef,
+      <result> = shufflevector <4 x i32> %v1, <4 x i32> poison,
                               <4 x i32> <i32 0, i32 1, i32 2, i32 3>  ; yields <4 x i32> - Identity shuffle.
-      <result> = shufflevector <8 x i32> %v1, <8 x i32> undef,
+      <result> = shufflevector <8 x i32> %v1, <8 x i32> poison,
                               <4 x i32> <i32 0, i32 1, i32 2, i32 3>  ; yields <4 x i32>
       <result> = shufflevector <4 x i32> %v1, <4 x i32> %v2,
                               <8 x i32> <i32 0, i32 1, i32 2, i32 3, i32 4, i32 5, i32 6, i32 7 >  ; yields <8 x i32>
 
 Aggregate Operations
 --------------------
 
 LLVM supports several instructions for working with