[InstCombine] wrong folding of multiplication to shift for an undefined input

[bongjunj]

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

Lines 1769 to 1783 in 390300d

	const APInt *MulC;
	if (match(Op0, m_OneUse(m_NSWMul(m_Value(X), m_APInt(MulC)))) &&
	(BitWidth > 2 && (*MulC - 1).isPowerOf2() &&
	MulC->logBase2() == ShAmt &&
	(ShAmt < BitWidth - 1))) /* Minus 1 for the sign bit */ {
	// ashr (mul nsw (X, 2^N + 1)), N -> add nsw (X, ashr(X, N))
	auto *NewAdd = BinaryOperator::CreateNSWAdd(
	X,
	Builder.CreateAShr(X, ConstantInt::get(Ty, ShAmt), "", I.isExact()));
	NewAdd->setHasNoUnsignedWrap(
	cast<OverflowingBinaryOperator>(Op0)->hasNoUnsignedWrap());
	return NewAdd;
	}
	}

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

----------------------------------------
define i32 @ashr_mul_times_3_div_2_exact_2.2(i32 %x) {
#0:
  %#1 = sdiv i32 %x, 65535
  %mul = mul nsw i32 %#1, 3
  %ashr = ashr i32 %mul, 1
  ret i32 %ashr
}
=>
define i32 @ashr_mul_times_3_div_2_exact_2.2(i32 %x) {
#0:
  %#1 = sdiv i32 %x, 65535
  %#2 = ashr i32 %#1, 1
  %ashr = add nsw i32 %#1, %#2
  ret i32 %ashr
}
Transformation doesn't verify!

ERROR: Value mismatch

Example:
i32 %x = undef

Source:
i32 %#1 = #x00000000 (0)	[based on undef value]
i32 %mul = #x00000000 (0)
i32 %ashr = #x00000000 (0)

Target:
i32 %#1 = #x00000000 (0)
i32 %#2 = #x00000000 (0)
i32 %ashr = #x00000080 (128)
Source value: #x00000000 (0)
Target value: #x00000080 (128)


----------------------------------------
define i32 @ashr_mul_times_3_div_2_exact.2(i32 %x) {
#0:
  %#1 = srem i32 %x, 2
  %mul = mul nsw i32 %#1, 3
  %ashr = ashr i32 %mul, 1
  ret i32 %ashr
}
=>
define i32 @ashr_mul_times_3_div_2_exact.2(i32 %x) {
#0:
  %#1 = srem i32 %x, 2
  %#2 = ashr i32 %#1, 1
  %ashr = add nsw i32 %#1, %#2
  ret i32 %ashr
}
Transformation doesn't verify!

ERROR: Value mismatch

Example:
i32 %x = undef

Source:
i32 %#1 = #x00000000 (0)	[based on undef value]
i32 %mul = #x00000000 (0)
i32 %ashr = #x00000000 (0)

Target:
i32 %#1 = #x00000000 (0)
i32 %#2 = #x00000000 (0)
i32 %ashr = #xffffffff (4294967295, -1)
Source value: #x00000000 (0)
Target value: #xffffffff (4294967295, -1)

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