[InstCombine] wrong folding of `lshr (mul ...)` to `(add (lshr ..)` for an undefined input

[bongjunj]

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

Lines 1521 to 1530 in 390300d

	// lshr (mul nuw (X, 2^N + 1)), N -> add nuw (X, lshr(X, N))
	if (Op0->hasOneUse()) {
	auto *NewAdd = BinaryOperator::CreateNUWAdd(
	X, Builder.CreateLShr(X, ConstantInt::get(Ty, ShAmtC), "",
	I.isExact()));
	NewAdd->setHasNoSignedWrap(
	cast<OverflowingBinaryOperator>(Op0)->hasNoSignedWrap());
	return NewAdd;
	}
	}

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

Lines 1550 to 1558 in 390300d

	// lshr (mul nsw (X, 2^N + 1)), N -> add nsw (X, lshr(X, N))
	if (match(Op0, m_OneUse(m_NSWMul(m_Value(X), m_APInt(MulC))))) {
	if (BitWidth > 2 && (*MulC - 1).isPowerOf2() &&
	MulC->logBase2() == ShAmtC) {
	return BinaryOperator::CreateNSWAdd(
	X, Builder.CreateLShr(X, ConstantInt::get(Ty, ShAmtC), "",
	I.isExact()));
	}
	}

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

----------------------------------------
define i32 @lshr_mul_times_3_div_2.2(i32 %#0) {
#1:
  %#2 = and i32 %#0, 65535
  %mul = mul nsw nuw i32 %#2, 3
  %lshr = lshr i32 %mul, 1
  ret i32 %lshr
}
=>
define i32 @lshr_mul_times_3_div_2.2(i32 %#0) {
#1:
  %#2 = and i32 %#0, 65535
  %#3 = lshr i32 %#2, 1
  %lshr = add nsw nuw i32 %#2, %#3
  ret i32 %lshr
}
Transformation doesn't verify!

ERROR: Value mismatch

Example:
i32 %#0 = undef

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

Target:
i32 %#2 = #x00000000 (0)
i32 %#3 = #x00000000 (0)
i32 %lshr = #x00000002 (2)
Source value: #x00000000 (0)
Target value: #x00000002 (2)


----------------------------------------
define i32 @mul_splat_fold_no_nuw.2(i32 %x) {
#0:
  %#1 = srem i32 %x, 2
  %m = mul nsw i32 %#1, 65537
  %t = lshr i32 %m, 16
  ret i32 %t
}
=>
define i32 @mul_splat_fold_no_nuw.2(i32 %x) {
#0:
  %#1 = srem i32 %x, 2
  %#2 = lshr i32 %#1, 16
  %t = add nsw i32 %#1, %#2
  ret i32 %t
}
Transformation doesn't verify!

ERROR: Value mismatch

Example:
i32 %x = undef

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

Target:
i32 %#1 = #x00000000 (0)
i32 %#2 = #x00000000 (0)
i32 %t = #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

[topperc]

I believe both of these changes were added in 718ba5a