[CorrelatedPropagation] `and X, C` wrongly replaced to `X (!range ...)`

[bongjunj]

llvm-project/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

Lines 1181 to 1202 in 84ce230

	static bool processAnd(BinaryOperator *BinOp, LazyValueInfo *LVI) {
	using namespace llvm::PatternMatch;
	// Pattern match (and lhs, C) where C includes a superset of bits which might
	// be set in lhs. This is a common truncation idiom created by instcombine.
	const Use &LHS = BinOp->getOperandUse(0);
	const APInt *RHS;
	if (!match(BinOp->getOperand(1), m_LowBitMask(RHS)))
	return false;
	// We can only replace the AND with LHS based on range info if the range does
	// not include undef.
	ConstantRange LRange =
	LVI->getConstantRangeAtUse(LHS, /*UndefAllowed=*/false);
	if (!LRange.getUnsignedMax().ule(*RHS))
	return false;
	BinOp->replaceAllUsesWith(LHS);
	BinOp->eraseFromParent();
	NumAnd++;
	return true;
	}

LHS could be undef.

Alive2 report: https://alive2.llvm.org/ce/z/7aNRWo

----------------------------------------
define i16 @foo.2(i16 %x) {
#0:
  %#1 = mul i16 %x, 65535
  %t1 = and i16 %x, %#1
  %t2 = zext i16 %t1 to i32
  %t3 = icmp ult i32 %t2, 255
  %t4 = select i1 %t3, i32 %t2, i32 255
  %t5 = trunc i32 %t4 to i16
  %t6 = and i16 %t5, 255
  ret i16 %t6
}
=>
define i16 @foo.2(i16 %x) {
#0:
  %#1 = mul i16 %x, 65535
  %t1 = and i16 %x, %#1
  %t2 = zext i16 %t1 to i32
  %t3 = icmp ult i32 %t2, 255
  %t4 = select i1 %t3, i32 %t2, i32 255
  %t5 = trunc i32 %t4 to i16
  %#range_0_%t5 = !range i16 %t5, i16 0, i16 256
  ret i16 %#range_0_%t5
}
Transformation doesn't verify!

ERROR: Target is more poisonous than source

Example:
i16 %x = undef

Source:
i16 %#1 = #x0000 (0)	[based on undef value]
i16 %t1 = #x0000 (0)
i32 %t2 = #x00000000 (0)
i1 %t3 = #x1 (1)
i32 %t4 = #x00000000 (0)	[based on undef value]
i16 %t5 = #x0000 (0)
i16 %t6 = #x0000 (0)

Target:
i16 %#1 = #x0000 (0)
i16 %t1 = #x0000 (0)
i32 %t2 = #x00000000 (0)
i1 %t3 = #x1 (1)
i32 %t4 = #x00007fff (32767)
i16 %t5 = #x7fff (32767)
i16 %#range_0_%t5 = poison
Source value: #x0000 (0)
Target value: poison


----------------------------------------
define i16 @foo.3(i16 %x) {
#0:
  %#1 = add i16 %x, 255
  %t2 = zext i16 %#1 to i32
  %t3 = icmp ult i32 %t2, 255
  %t4 = select i1 %t3, i32 %t2, i32 255
  %t5 = trunc i32 %t4 to i16
  %t6 = and i16 %t5, 255
  ret i16 %t6
}
=>
define i16 @foo.3(i16 %x) {
#0:
  %#1 = add i16 %x, 255
  %t2 = zext i16 %#1 to i32
  %t3 = icmp ult i32 %t2, 255
  %t4 = select i1 %t3, i32 %t2, i32 255
  %t5 = trunc i32 %t4 to i16
  %#range_0_%t5 = !range i16 %t5, i16 0, i16 256
  ret i16 %#range_0_%t5
}
Transformation doesn't verify!

ERROR: Target is more poisonous than source

Example:
i16 %x = undef

Source:
i16 %#1 = #x00ff (255)	[based on undef value]
i32 %t2 = #x000000ff (255)
i1 %t3 = #x0 (0)
i32 %t4 = #x000000ff (255)
i16 %t5 = #x00ff (255)
i16 %t6 = #x00ff (255)

Target:
i16 %#1 = #x007f (127)
i32 %t2 = #x0000007f (127)
i1 %t3 = #x1 (1)
i32 %t4 = #x00000100 (256)
i16 %t5 = #x0100 (256)
i16 %#range_0_%t5 = poison
Source value: #x00ff (255)
Target value: poison


----------------------------------------
define i16 @foo.4(i16 %x) {
#0:
  %#1 = add i16 %x, 255
  %#2 = sext i16 %#1 to i32
  %t3 = icmp ult i32 %#2, 255
  %t4 = select i1 %t3, i32 %#2, i32 255
  %t5 = trunc i32 %t4 to i16
  %t6 = and i16 %t5, 255
  ret i16 %t6
}
=>
define i16 @foo.4(i16 %x) {
#0:
  %#1 = add i16 %x, 255
  %#2 = sext i16 %#1 to i32
  %t3 = icmp ult i32 %#2, 255
  %t4 = select i1 %t3, i32 %#2, i32 255
  %t5 = trunc i32 %t4 to i16
  %#range_0_%t5 = !range i16 %t5, i16 0, i16 256
  ret i16 %#range_0_%t5
}
Transformation doesn't verify!

ERROR: Target is more poisonous than source

Example:
i16 %x = undef

Source:
i16 %#1 = #x00ff (255)	[based on undef value]
i32 %#2 = #x000000ff (255)
i1 %t3 = #x0 (0)
i32 %t4 = #x000000ff (255)
i16 %t5 = #x00ff (255)
i16 %t6 = #x00ff (255)

Target:
i16 %#1 = #x007f (127)
i32 %#2 = #x0000007f (127)
i1 %t3 = #x1 (1)
i32 %t4 = #x00000100 (256)
i16 %t5 = #x0100 (256)
i16 %#range_0_%t5 = poison
Source value: #x00ff (255)
Target value: poison

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

[nikic]

I think this is because of the SPF matching in LVI, which doesn't have the same undef checks as the generic select handling. As we canonicalize SPF to intrinsics anyway, we can probably delete this code.

[nikic]

Tested this in #115305. Removing the SPF support fixes this issue, but it does cause some regressions for phase ordering reasons.