Page MenuHomePhabricator

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

Authored by aqjune on Dec 25 2020, 3:30 PM.

Details

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.

Diff Detail

Event Timeline

aqjune created this revision.Dec 25 2020, 3:30 PM
aqjune requested review of this revision.Dec 25 2020, 3:30 PM
Herald added a project: Restricted Project. · View Herald TranscriptDec 25 2020, 3:30 PM

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).

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 added a comment.Jan 2 2021, 4:51 PM

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

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).

Matt added a subscriber: Matt.May 31 2021, 10:03 AM
aqjune updated this revision to Diff 350490.Jun 7 2021, 10:10 PM

Update wordings

aqjune added a comment.EditedJun 7 2021, 10:24 PM

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 added a comment.Jun 8 2021, 9:33 AM

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 added inline comments.Jun 8 2021, 1:41 PM
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.

9445

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 added a comment.Jun 8 2021, 7:13 PM

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 added inline comments.Jun 8 2021, 7:18 PM
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.

9445

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 updated this revision to Diff 350762.Jun 8 2021, 7:29 PM

Address comments