Wrong canonicalization of `add` and bitwise logic operation

[bongjunj]

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

Lines 2158 to 2200 in f1ade1f

	// Match
	// (X + C2) | C
	// (X + C2) ^ C
	// (X + C2) & C
	// and convert to do the bitwise logic first:
	// (X | C) + C2
	// (X ^ C) + C2
	// (X & C) + C2
	// iff bits affected by logic op are lower than last bit affected by math op
	static Instruction *canonicalizeLogicFirst(BinaryOperator &I,
	InstCombiner::BuilderTy &Builder) {
	Type *Ty = I.getType();
	Instruction::BinaryOps OpC = I.getOpcode();
	Value *Op0 = I.getOperand(0);
	Value *Op1 = I.getOperand(1);
	Value *X;
	const APInt *C, *C2;
	if (!(match(Op0, m_OneUse(m_Add(m_Value(X), m_APInt(C2)))) &&
	match(Op1, m_APInt(C))))
	return nullptr;
	unsigned Width = Ty->getScalarSizeInBits();
	unsigned LastOneMath = Width - C2->countr_zero();
	switch (OpC) {
	case Instruction::And:
	if (C->countl_one() < LastOneMath)
	return nullptr;
	break;
	case Instruction::Xor:
	case Instruction::Or:
	if (C->countl_zero() < LastOneMath)
	return nullptr;
	break;
	default:
	llvm_unreachable("Unexpected BinaryOp!");
	}
	Value *NewBinOp = Builder.CreateBinOp(OpC, X, ConstantInt::get(Ty, *C));
	return BinaryOperator::CreateWithCopiedFlags(Instruction::Add, NewBinOp,
	ConstantInt::get(Ty, *C2), Op0);
	}

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

----------------------------------------
define <2 x i8> @t5_splat_undef_0b1000.2(<2 x i8> %x) {
#0:
  %#1 = xor <2 x i8> %x, { 15, undef }
  %x.lowbits.are.zero = icmp eq <2 x i8> %#1, { 0, 0 }
  %x.biased = add <2 x i8> %x, { 16, 16 }
  %x.biased.highbits = and <2 x i8> %x.biased, { 240, 240 }
  %x.roundedup = select <2 x i1> %x.lowbits.are.zero, <2 x i8> %x, <2 x i8> %x.biased.highbits
  ret <2 x i8> %x.roundedup
}
=>
define <2 x i8> @t5_splat_undef_0b1000.2(<2 x i8> %x) {
#0:
  %x.lowbits.are.zero = icmp eq <2 x i8> %x, { 15, undef }
  %#1 = and <2 x i8> %x, { 240, 240 }
  %x.biased.highbits = add <2 x i8> %#1, { 16, 16 }
  %x.roundedup = select <2 x i1> %x.lowbits.are.zero, <2 x i8> { 15, undef }, <2 x i8> %x.biased.highbits
  ret <2 x i8> %x.roundedup
}
Transformation doesn't verify!

ERROR: Value mismatch

Example:
<2 x i8> %x = < #x00 (0), #x00 (0) >

Source:
<2 x i8> %#1 = < #x0f (15), #x00 (0)	[based on undef value] >
<2 x i1> %x.lowbits.are.zero = < #x0 (0), #x1 (1) >
<2 x i8> %x.biased = < #x10 (16), #x10 (16) >
<2 x i8> %x.biased.highbits = < #x10 (16), #x10 (16) >
<2 x i8> %x.roundedup = < #x10 (16), #x00 (0) >

Target:
<2 x i1> %x.lowbits.are.zero = < #x0 (0), #x1 (1) >
<2 x i8> %#1 = < #x00 (0), #x00 (0) >
<2 x i8> %x.biased.highbits = < #x10 (16), #x10 (16) >
<2 x i8> %x.roundedup = < #x10 (16), #x02 (2) >
Source value: < #x10 (16), #x00 (0) >
Target value: < #x10 (16), #x02 (2) >


----------------------------------------
define i8 @t5_splat_undef_0b1000.3(i8 %x) {
#0:
  %#1 = xor i8 %x, undef
  %x.lowbits.are.zero = icmp eq i8 %#1, 0
  %x.biased = add i8 %x, 16
  %x.biased.highbits = and i8 %x.biased, 240
  %x.roundedup = select i1 %x.lowbits.are.zero, i8 %x, i8 %x.biased.highbits
  ret i8 %x.roundedup
}
=>
define i8 @t5_splat_undef_0b1000.3(i8 %x) {
#0:
  ret i8 %x
}
Transformation seems to be correct!

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

[duk-37]

This seems to be the underlying transform failing verification: https://alive2.llvm.org/ce/z/bs8v-9

[nikic]

The problematic fold is:

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

Lines 1928 to 1938 in 86f7f08

	if (CmpRHS != CmpLHS && isa<Constant>(CmpRHS) && !isa<Constant>(CmpLHS)) {
	if (CmpLHS == TrueVal && Pred == ICmpInst::ICMP_EQ) {
	// Transform (X == C) ? X : Y -> (X == C) ? C : Y
	replaceOperand(SI, 1, CmpRHS);
	Changed = true;
	} else if (CmpLHS == FalseVal && Pred == ICmpInst::ICMP_NE) {
	// Transform (X != C) ? Y : X -> (X != C) ? Y : C
	replaceOperand(SI, 2, CmpRHS);
	Changed = true;
	}
	}

Unlike the generic select value equivalence fold, this one does not handle undef correctly.

[nikic]

We can fix this by removing the separate fold: #117746