Wrong ICmp folding of `and` and `or`

[bongjunj]

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

Lines 770 to 803 in 11dad2f

	Value *InstCombinerImpl::foldAndOrOfICmpsOfAndWithPow2(ICmpInst *LHS,
	ICmpInst *RHS,
	Instruction *CxtI,
	bool IsAnd,
	bool IsLogical) {
	CmpInst::Predicate Pred = IsAnd ? CmpInst::ICMP_NE : CmpInst::ICMP_EQ;
	if (LHS->getPredicate() != Pred || RHS->getPredicate() != Pred)
	return nullptr;
	if (!match(LHS->getOperand(1), m_Zero()) ||
	!match(RHS->getOperand(1), m_Zero()))
	return nullptr;
	Value *L1, *L2, *R1, *R2;
	if (match(LHS->getOperand(0), m_And(m_Value(L1), m_Value(L2))) &&
	match(RHS->getOperand(0), m_And(m_Value(R1), m_Value(R2)))) {
	if (L1 == R2 || L2 == R2)
	std::swap(R1, R2);
	if (L2 == R1)
	std::swap(L1, L2);
	if (L1 == R1 &&
	isKnownToBeAPowerOfTwo(L2, false, 0, CxtI) &&
	isKnownToBeAPowerOfTwo(R2, false, 0, CxtI)) {
	// If this is a logical and/or, then we must prevent propagation of a
	// poison value from the RHS by inserting freeze.
	if (IsLogical)
	R2 = Builder.CreateFreeze(R2);
	Value *Mask = Builder.CreateOr(L2, R2);
	Value *Masked = Builder.CreateAnd(L1, Mask);
	auto NewPred = IsAnd ? CmpInst::ICMP_EQ : CmpInst::ICMP_NE;
	return Builder.CreateICmp(NewPred, Masked, Mask);
	}
	}

The case below runs the code above:

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

----------------------------------------
define i1 @f(i32 %k, i32 %c1, i32 %c2) {
#0:
  %t = shl i32 1, %c1
  %#1 = and i32 %c2, %t
  %t4 = lshr i32 2147483648, %#1
  %t1 = and i32 %t, %k
  %t2 = icmp eq i32 %t1, 0
  %t5 = and i32 %t4, %k
  %t6 = icmp eq i32 %t5, 0
  %or = or i1 %t2, %t6
  ret i1 %or
}
=>
define i1 @f(i32 %k, i32 %c1, i32 %c2) {
#0:
  %t = shl nuw i32 1, %c1
  %#1 = and i32 %c2, %t
  %t4 = lshr exact i32 2147483648, %#1
  %#2 = or i32 %t, %t4
  %#3 = and i32 %k, %#2
  %or = icmp ne i32 %#3, %#2
  ret i1 %or
}
Transformation doesn't verify!

ERROR: Target's return value is more undefined

Example:
i32 %k = #xc0000001 (3221225473, -1073741823)
i32 %c1 = #x00000000 (0)
i32 %c2 = undef

Source:
i32 %t = #x00000001 (1)
i32 %#1 = #x00000000 (0)	[based on undef value]
i32 %t4 = #x80000000 (2147483648, -2147483648)
i32 %t1 = #x00000001 (1)
i1 %t2 = #x0 (0)
i32 %t5 = #x80000000 (2147483648, -2147483648)
i1 %t6 = #x0 (0)
i1 %or = #x0 (0)

Target:
i32 %t = #x00000001 (1)
i32 %#1 = #x00000000 (0)
i32 %t4 = #x80000000 (2147483648, -2147483648)
i32 %#2 = #x80000001 (2147483649, -2147483647)
i32 %#3 = #x80000001 (2147483649, -2147483647)
i1 %or = #x1 (1)
Source value: #x0 (0)
Target value: #x1 (1)

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

[ParkHanbum]

interesting... this usually be correct. but c1 as treated undef this problem occurred.
maybe we need to handle undef?

define i1 @f(i32 %k, i32 %c1, i32 noundef %c2) {
#0:
%t = shl i32 1, %c1
%#1 = and i32 noundef %c2, %t
%t4 = lshr i32 2147483648, %#1
%t1 = and i32 %t, %k
%t2 = icmp eq i32 %t1, 0
%t5 = and i32 %t4, %k
%t6 = icmp eq i32 %t5, 0
%or = or i1 %t2, %t6
ret i1 %or
}
=>
define i1 @f(i32 %k, i32 %c1, i32 noundef %c2) {
#0:
%t = shl nuw i32 1, %c1
%#1 = and i32 noundef %c2, %t
%t4 = lshr exact i32 2147483648, %#1
%#2 = or i32 %t, %t4
%#3 = and i32 %k, %#2
%or = icmp ne i32 %#3, %#2
ret i1 %or
}
Transformation seems to be correct!

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

@dtcxzyw Do you think it's correct to fix this to handle undef?