[Instcombine] Fix uses of undef (PR46940)

[kazu]

Summary

Without this patch, we attempt to distribute And over Xor even in
unsafe circumstances like so:

undef & (true ^ true)  ==>  (undef & true) ^ (undef & true)

and evaluate it to undef instead of false. Note that "true ^ true"
may show up implicitly with one true being part of a PHI node.

This patch fixes the problem by teaching SimplifyAndInst and
SimplifyUsingDistributiveLaws to not use undef as part of
simplifications when they distribute And over Xor.

[nikic]

Oops, looks like we were working on this in parallel. I just submitted D85684 for the InstSimplify part of the problem.

[kazu]

In D85687#2208099, @nikic wrote:

Oops, looks like we were working on this in parallel. I just submitted D85684 for the InstSimplify part of the problem.

Oh, OK. In that case, once your patch lands. I will drop the InstructionSimplify.cpp portion of my patch. Note that for my testcase in this patch to pass, I need both changes, the one in InstructionSimplify.cpp and the other in InstructionCombining.cpp.

[nikic]

D85684 has landed now. After rebasing, you can also use SQ.getWithoutUndef() to reduce the boilerplate for creating a new SimplifyQuery.

[kazu]

I've rebased this patch on top of https://reviews.llvm.org/D85684.

[kazu]

Please thank a look. Thanks!

[nikic]

LGTM

llvm/test/Transforms/InstCombine/dont-distribute-phi.ll

2

Please use llvm/util/update_test_checks.py to generate CHECK lines.

[kazu]

I've llvm/util/update_test_checks.py to update CHECK lines.

[jdoerfert]

In D85687#2211569, @kazu wrote:

I've llvm/util/update_test_checks.py to update CHECK lines.

I don't think this worked though.

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

Value *InstCombinerImpl::SimplifyUsingDistributiveLaws(BinaryOperator &I) {
 
   // Expansion.
   if (Op0 && rightDistributesOverLeft(Op0->getOpcode(), TopLevelOpcode)) {
     // The instruction has the form "(A op' B) op C".  See if expanding it out
     // to "(A op C) op' (B op C)" results in simplifications.
     Value *A = Op0->getOperand(0), *B = Op0->getOperand(1), *C = RHS;
     Instruction::BinaryOps InnerOpcode = Op0->getOpcode(); // op'
 
-    Value *L = SimplifyBinOp(TopLevelOpcode, A, C, SQ.getWithInstruction(&I));
-    Value *R = SimplifyBinOp(TopLevelOpcode, B, C, SQ.getWithInstruction(&I));
+    // Disable the use of undef because it's not safe to distribute undef.
+    auto SQDistributive = SQ.getWithInstruction(&I).getWithoutUndef();
+    Value *L = SimplifyBinOp(TopLevelOpcode, A, C, SQDistributive);
+    Value *R = SimplifyBinOp(TopLevelOpcode, B, C, SQDistributive);
 
     // Do "A op C" and "B op C" both simplify?
     if (L && R) {
       // They do! Return "L op' R".
       ++NumExpand;
       C = Builder.CreateBinOp(InnerOpcode, L, R);
       C->takeName(&I);
       return C;
Value *InstCombinerImpl::SimplifyUsingDistributiveLaws(BinaryOperator &I) {
   }
 
   if (Op1 && leftDistributesOverRight(TopLevelOpcode, Op1->getOpcode())) {
     // The instruction has the form "A op (B op' C)".  See if expanding it out
     // to "(A op B) op' (A op C)" results in simplifications.
     Value *A = LHS, *B = Op1->getOperand(0), *C = Op1->getOperand(1);
     Instruction::BinaryOps InnerOpcode = Op1->getOpcode(); // op'
 
-    Value *L = SimplifyBinOp(TopLevelOpcode, A, B, SQ.getWithInstruction(&I));
-    Value *R = SimplifyBinOp(TopLevelOpcode, A, C, SQ.getWithInstruction(&I));
+    // Disable the use of undef because it's not safe to distribute undef.
+    auto SQDistributive = SQ.getWithInstruction(&I).getWithoutUndef();
+    Value *L = SimplifyBinOp(TopLevelOpcode, A, B, SQDistributive);
+    Value *R = SimplifyBinOp(TopLevelOpcode, A, C, SQDistributive);
 
     // Do "A op B" and "A op C" both simplify?
     if (L && R) {
       // They do! Return "L op' R".
       ++NumExpand;
       A = Builder.CreateBinOp(InnerOpcode, L, R);
       A->takeName(&I);
       return A;

llvm/test/Transforms/InstCombine/dont-distribute-phi.ll

+; RUN: opt < %s -instcombine -S | FileCheck %s
+;
+; This test ensures that InstCombine does not distribute And over Xor
+; using simplifications involving undef.
+
+define zeroext i1 @foo(i32 %arg) {
+; CHECK-LABEL: @foo(
+
+entry:
+  %cmp1 = icmp eq i32 %arg, 37
+  br i1 %cmp1, label %bb_then, label %bb_else
+
+bb_then:
+  call void @bar()
+  br label %bb_exit
+
+bb_else:
+  %cmp2 = icmp slt i32 %arg, 17
+  br label %bb_exit
+
+; CHECK:       bb_exit:
+; CHECK-NEXT:    [[PHI1:%.*]] = phi i1 [ [[CMP2:%.*]], [[BB_ELSE:%.*]] ], [ undef, [[BB_THEN:%.*]] ]
+; CHECK-NEXT:    [[XOR1:%.*]] = xor i1 [[CMP1:%.*]], true
+; CHECK-NEXT:    [[AND1:%.*]] = and i1 [[PHI1]], [[XOR1]]
+; CHECK-NEXT:    ret i1 [[AND1]]
+bb_exit:
+  %phi1 = phi i1 [ %cmp2, %bb_else ], [ undef, %bb_then ]
+  %xor1 = xor i1 %cmp1, true
+  %and1 = and i1 %phi1, %xor1
+  ret i1 %and1
+}
+
+declare void @bar()