Wrong select folding for undef conditions by InstCombine

[bongjunj]

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

Lines 3582 to 3585 in 7eae9bb

	if (Value *S = simplifyWithOpReplaced(FalseVal, CondVal,
	ConstantInt::getFalse(CondType), SQ,
	/* AllowRefinement */ true))
	return replaceOperand(SI, 2, S);

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

----------------------------------------
define <2 x i1> @fun0(<2 x i1> %val0, <2 x i1> %val1) {
#0:
  %val2 = select <2 x i1> %val0, <2 x i1> %val0, <2 x i1> %val0
  %val3 = select <2 x i1> { undef, 1 }, <2 x i1> { 1, 1 }, <2 x i1> %val2
  ret <2 x i1> %val3
}
=>
define <2 x i1> @fun0(<2 x i1> %val0, <2 x i1> %val1) {
#0:
  ret <2 x i1> { poison, 1 }
}
Transformation doesn't verify!

ERROR: Target is more poisonous than source

Example:
<2 x i1> %val0 = < #x0 (0), #x0 (0) >
<2 x i1> %val1 = < #x0 (0), #x0 (0) >

Source:
<2 x i1> %val2 = < #x0 (0), #x0 (0) >
<2 x i1> %val3 = < #x0 (0)	[based on undef value], #x1 (1) >

Target:
Source value: < #x0 (0), #x1 (1) >
Target value: < poison, #x1 (1) >

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

[jf-botto]

Would this issue be to fix InstCombine to not try to optimise it or get InstCombine to pick <2 x i1> { 1, 1 } because undef let's it pick either values and picking a constant vector is better than picking a variable?

[nikic]

The problematic step seems to be this one: https://alive2.llvm.org/ce/z/C2waWU

I don't think the quoted code is responsible for this, as it is guarded by !isa<Constant>(CondVal).

[jf-botto]

I think the problem is with how SimplifyDemandedVectorElts handles the undef:

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

Lines 1721 to 1760 in af80d3a

	case Instruction::Select: {
	// If this is a vector select, try to transform the select condition based
	// on the current demanded elements.
	SelectInst *Sel = cast<SelectInst>(I);
	if (Sel->getCondition()->getType()->isVectorTy()) {
	// TODO: We are not doing anything with PoisonElts based on this call.
	// It is overwritten below based on the other select operands. If an
	// element of the select condition is known undef, then we are free to
	// choose the output value from either arm of the select. If we know that
	// one of those values is undef, then the output can be undef.
	simplifyAndSetOp(I, 0, DemandedElts, PoisonElts);
	}
	// Next, see if we can transform the arms of the select.
	APInt DemandedLHS(DemandedElts), DemandedRHS(DemandedElts);
	if (auto *CV = dyn_cast<ConstantVector>(Sel->getCondition())) {
	for (unsigned i = 0; i < VWidth; i++) {
	// isNullValue() always returns false when called on a ConstantExpr.
	// Skip constant expressions to avoid propagating incorrect information.
	Constant *CElt = CV->getAggregateElement(i);
	if (isa<ConstantExpr>(CElt))
	continue;
	// TODO: If a select condition element is undef, we can demand from
	// either side. If one side is known undef, choosing that side would
	// propagate undef.
	if (CElt->isNullValue())
	DemandedLHS.clearBit(i);
	else
	DemandedRHS.clearBit(i);
	}
	}
	simplifyAndSetOp(I, 1, DemandedLHS, PoisonElts2);
	simplifyAndSetOp(I, 2, DemandedRHS, PoisonElts3);
	// Output elements are undefined if the element from each arm is undefined.
	// TODO: This can be improved. See comment in select condition handling.
	PoisonElts = PoisonElts2 & PoisonElts3;
	break;
	}

[nikic]

@jf-botto Agree. It assumes that !isNullValue() means "is true", which is not the case.