[InstCombine] wrong negation of PHI

[bongjunj]

The follow lines are executed:

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

Lines 308 to 326 in 9a7519f

	case Instruction::PHI: {
	// `phi` is negatible if all the incoming values are negatible.
	auto *PHI = cast<PHINode>(I);
	SmallVector<Value *, 4> NegatedIncomingValues(PHI->getNumOperands());
	for (auto I : zip(PHI->incoming_values(), NegatedIncomingValues)) {
	// Don't negate indvars to avoid infinite loops.
	if (DT.dominates(PHI->getParent(), std::get<0>(I)))
	return nullptr;
	if (!(std::get<1>(I) =
	negate(std::get<0>(I), IsNSW, Depth + 1))) // Early return.
	return nullptr;
	}
	// All incoming values are indeed negatible. Create negated PHI node.
	PHINode *NegatedPHI = Builder.CreatePHI(
	PHI->getType(), PHI->getNumOperands(), PHI->getName() + ".neg");
	for (auto I : zip(NegatedIncomingValues, PHI->blocks()))
	NegatedPHI->addIncoming(std::get<0>(I), std::get<1>(I));
	return NegatedPHI;
	}

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

----------------------------------------
define i32 @pr50308.2(i1 %c1, i32 %v1, i32 %v2, i32 %v3) {
entry:
  br i1 %c1, label %cond.true, label %cond.end

cond.true:
  %#0 = sext i1 %c1 to i32
  %#1 = xor i32 1, %#0
  %#2 = add i32 %#0, %v1
  %#3 = and i32 %v1, %#2
  %#4 = sdiv i32 %#3, %#1
  br label %cond.end

cond.end:
  %cond = phi i32 [ %#4, %cond.true ], [ 0, %entry ]
  %sub = sub nuw i32 %v3, %cond
  ret i32 %sub
}
=>
define i32 @pr50308.2(i1 %c1, i32 %v1, i32 %v2, i32 %v3) {
entry:
  br i1 %c1, label %cond.true, label %cond.end

cond.true:
  %#0 = add i32 %v1, 4294967295
  %#1 = and i32 %v1, %#0
  %.neg = ashr exact i32 %#1, 1
  br label %cond.end

cond.end:
  %cond.neg = phi i32 [ %.neg, %cond.true ], [ 0, %entry ]
  %sub = add i32 %cond.neg, %v3
  ret i32 %sub
}
Transformation doesn't verify!

ERROR: Target is more poisonous than source

Example:
i1 %c1 = #x1 (1)
i32 %v1 = undef
i32 %v2 = poison
i32 %v3 = #xffffffff (4294967295, -1)

Source:
  >> Jump to %cond.true
i32 %#0 = #xffffffff (4294967295, -1)
i32 %#1 = #xfffffffe (4294967294, -2)
i32 %#2 = #xffffffff (4294967295, -1)	[based on undef value]
i32 %#3 = #x00000000 (0)	[based on undef value]
i32 %#4 = #x00000000 (0)
  >> Jump to %cond.end
i32 %cond = #x00000000 (0)	[based on undef value]
i32 %sub = #xffffffff (4294967295, -1)

Target:
  >> Jump to %cond.true
i32 %#0 = #xffffffff (4294967295, -1)	[based on undef value]
i32 %#1 = #x00000000 (0)	[based on undef value]
i32 %.neg = #x00000000 (0)
  >> Jump to %cond.end
i32 %cond.neg = poison
i32 %sub = poison
Source value: #xffffffff (4294967295, -1)
Target value: poison

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