Wrong folding of `select` and `shufflevector` (commutativity check)

[bongjunj]

llvm-project/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

Lines 2595 to 2623 in 5d4a0d5

	ArrayRef<int> Mask;
	if (match(TVal, m_OneUse(m_Shuffle(m_Value(X), m_Value(Y), m_Mask(Mask)))) &&
	!is_contained(Mask, PoisonMaskElem) &&
	cast<ShuffleVectorInst>(TVal)->isSelect()) {
	if (X == FVal) {
	// select Cond, (shuf_sel X, Y), X --> shuf_sel X, (select Cond, Y, X)
	Value *NewSel = Builder.CreateSelect(Cond, Y, X, "sel", &Sel);
	return new ShuffleVectorInst(X, NewSel, Mask);
	}
	if (Y == FVal) {
	// select Cond, (shuf_sel X, Y), Y --> shuf_sel (select Cond, X, Y), Y
	Value *NewSel = Builder.CreateSelect(Cond, X, Y, "sel", &Sel);
	return new ShuffleVectorInst(NewSel, Y, Mask);
	}
	}
	if (match(FVal, m_OneUse(m_Shuffle(m_Value(X), m_Value(Y), m_Mask(Mask)))) &&
	!is_contained(Mask, PoisonMaskElem) &&
	cast<ShuffleVectorInst>(FVal)->isSelect()) {
	if (X == TVal) {
	// select Cond, X, (shuf_sel X, Y) --> shuf_sel X, (select Cond, X, Y)
	Value *NewSel = Builder.CreateSelect(Cond, X, Y, "sel", &Sel);
	return new ShuffleVectorInst(X, NewSel, Mask);
	}
	if (Y == TVal) {
	// select Cond, Y, (shuf_sel X, Y) --> shuf_sel (select Cond, Y, X), Y
	Value *NewSel = Builder.CreateSelect(Cond, Y, X, "sel", &Sel);
	return new ShuffleVectorInst(NewSel, Y, Mask);
	}
	}

More specifically,

llvm-project/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

Lines 2599 to 2603 in 5d4a0d5

	if (X == FVal) {
	// select Cond, (shuf_sel X, Y), X --> shuf_sel X, (select Cond, Y, X)
	Value *NewSel = Builder.CreateSelect(Cond, Y, X, "sel", &Sel);
	return new ShuffleVectorInst(X, NewSel, Mask);
	}

llvm-project/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

Lines 2618 to 2623 in 5d4a0d5

	if (Y == TVal) {
	// select Cond, Y, (shuf_sel X, Y) --> shuf_sel (select Cond, Y, X), Y
	Value *NewSel = Builder.CreateSelect(Cond, Y, X, "sel", &Sel);
	return new ShuffleVectorInst(NewSel, Y, Mask);
	}
	}

Alive2 report: https://alive2.llvm.org/ce/z/C_myVe

----------------------------------------
define <4 x i8> @select_cond_with_eq_true_false_elts2.2(<4 x i8> %x, <4 x i8> %y, <4 x i1> %cmp) {
#0:
  %#1 = select <4 x i1> %cmp, <4 x i8> %y, <4 x i8> { 0, 1, 2, 3 }
  %#2 = urem <4 x i8> %y, %#1
  %tval = shufflevector <4 x i8> %x, <4 x i8> %#2, 0, 5, 6, 7
  %cond = shufflevector <4 x i1> %cmp, <4 x i1> %cmp, 0, 1, 0, 1
  %r = select <4 x i1> %cond, <4 x i8> %tval, <4 x i8> %x
  ret <4 x i8> %r
}
=>
define <4 x i8> @select_cond_with_eq_true_false_elts2.2(<4 x i8> %x, <4 x i8> %y, <4 x i1> %cmp) {
#0:
  %cond = shufflevector <4 x i1> %cmp, <4 x i1> poison, 4294967295, 1, 0, 1
  %sel = select <4 x i1> %cond, <4 x i8> { poison, 0, 0, 0 }, <4 x i8> %x
  %r = shufflevector <4 x i8> %x, <4 x i8> %sel, 0, 5, 6, 7
  ret <4 x i8> %r
}
Transformation doesn't verify!

ERROR: Target's return value is more undefined

Example:
<4 x i8> %x = < #x00 (0), #x00 (0), poison, #x01 (1) >
<4 x i8> %y = < #x02 (2), #x01 (1), #x00 (0), #x01 (1) >
<4 x i1> %cmp = < #x1 (1), undef, #x0 (0), #x0 (0) >

Source:
<4 x i8> %#1 = < #x02 (2), #x01 (1), #x02 (2), #x03 (3) >
<4 x i8> %#2 = < #x00 (0), #x00 (0), #x00 (0), #x01 (1) >
<4 x i8> %tval = < #x00 (0), #x00 (0), #x00 (0), #x01 (1) >
<4 x i1> %cond = < #x1 (1), #x0 (0)	[based on undef value], #x1 (1), #x0 (0)	[based on undef value] >
<4 x i8> %r = < #x00 (0), #x00 (0), #x00 (0), #x01 (1) >

Target:
<4 x i1> %cond = < poison, #x0 (0), #x1 (1), #x0 (0)	[based on undef value] >
<4 x i8> %sel = < poison, #x00 (0), #x00 (0), #x01 (1) >
<4 x i8> %r = < #x00 (0), #x00 (0), #x00 (0), #x01 (1) >
Source value: < #x00 (0), #x00 (0), #x00 (0), #x01 (1) >
Target value: < #x00 (0), #x00 (0), #x00 (0), #x01 (1) >


----------------------------------------
define <4 x i8> @sel_shuf_commute3.2(<4 x i8> %y, i1 %cmp) {
#0:
  %blend = shufflevector <4 x i8> { 0, 0, 0, 0 }, <4 x i8> %y, 0, 5, 2, 3
  %r = select i1 %cmp, <4 x i8> %y, <4 x i8> %blend
  ret <4 x i8> %r
}
=>
define <4 x i8> @sel_shuf_commute3.2(<4 x i8> %y, i1 %cmp) {
#0:
  %sel = select i1 %cmp, <4 x i8> %y, <4 x i8> { 0, poison, 0, 0 }
  %r = shufflevector <4 x i8> %sel, <4 x i8> %y, 0, 5, 2, 3
  ret <4 x i8> %r
}
Transformation doesn't verify!

ERROR: Value mismatch

Example:
<4 x i8> %y = < #x00 (0), #x00 (0), undef, #xff (255, -1) >
i1 %cmp = undef

Source:
<4 x i8> %blend = < #x00 (0), #x00 (0), #x00 (0), #x00 (0) >
<4 x i8> %r = < #x00 (0), #x00 (0), #x00 (0), #x00 (0) >

Target:
<4 x i8> %sel = < #x00 (0), poison, #x00 (0), #x00 (0) >
<4 x i8> %r = < #x00 (0), #x00 (0), #x02 (2), #x00 (0) >
Source value: < #x00 (0), #x00 (0), #x00 (0), #x00 (0) >
Target value: < #x00 (0), #x00 (0), #x02 (2), #x00 (0) >

Summary:
  0 correct transformations
  2 incorrect transformations
  0 failed-to-prove transformations
  0 Alive2 errors

[dtcxzyw]

Poison-safety issue in the first test case should be fixed by #114280: https://alive2.llvm.org/ce/z/QzWa-q.