[InstCombine] Implement "A & (~A | B) --> A & B" like transforms for boolean based selects.

[paulwalker-arm]

Summary

Alive2 links for "A & (~A | B) --> A & B":
https://alive2.llvm.org/ce/z/oKiodu (scalar)
https://alive2.llvm.org/ce/z/8yn8GL (vector)

Alive2 links for "A | (~A & B) --> A | B"
https://alive2.llvm.org/ce/z/v5GEKu (scalar)
https://alive2.llvm.org/ce/z/wvtJsj (vector)

NOTE: The commutative variants of these transforms, for example: "(~A | B) & A --> A & B" are already handled by simplifying the underlying selects to normal logical operations due to that combination having simpler poison semantics.

[paulwalker-arm]

Need to be more strict with the handling of poison.

[paulwalker-arm]

Updated to include correct handling of poison.

[paulwalker-arm]

This is a partial fix for https://github.com/llvm/llvm-project/issues/58690

[nikic]

Missing scalar test coverage. Please also add relevant proofs to patch description (e.g. https://alive2.llvm.org/ce/z/oKiodu). What about the de Morgan conjugate?

[spatel]

llvm/test/Transforms/InstCombine/logical-select.ll

1135

This isn't doing what we wanted - the not will get commuted to operand 0.
To keep it as operand 1, we need something like this:

declare i1 @gen()

define i1 @and_commute1(i1 %a) {
  %b = call i1 @gen()
  %nota = xor i1 %a, 1
  %or = or i1 %b, %nota
  %and = select i1 %a, i1 %or, i1 0
  ret i1 %and
}

We also need matching and tests for patterns where the "or-not" is the condition value of the select?

[paulwalker-arm]

llvm/test/Transforms/InstCombine/logical-select.ll

1135

The "or-not is the condition" case already works, whereby it's converted to an "and" (See https://alive2.llvm.org/ce/z/bxZ37W). I'm not sure why that case doesn't have the same poison issues that my case has.

[paulwalker-arm]

Add scalar test cases and fixed switch operand test.

[paulwalker-arm]

In D145157#4164759, @nikic wrote:

Missing scalar test coverage. Please also add relevant proofs to patch description (e.g. https://alive2.llvm.org/ce/z/oKiodu). What about the de Morgan conjugate?

@nikic Can you be more specific as to the meaning of "de Morgan conjugate"? Do you mean switching the operands as @spatel mentioned (which already works) or had you something else in mind.

[nikic]

In D145157#4165054, @paulwalker-arm wrote:

In D145157#4164759, @nikic wrote:

Missing scalar test coverage. Please also add relevant proofs to patch description (e.g. https://alive2.llvm.org/ce/z/oKiodu). What about the de Morgan conjugate?

@nikic Can you be more specific as to the meaning of "de Morgan conjugate"? Do you mean switching the operands as @spatel mentioned (which already works) or had you something else in mind.

The conjugate is A | (~A & B) -> A | B (https://alive2.llvm.org/ce/z/v5GEKu).

[paulwalker-arm]

Thanks for the education @nikic. I'll implement that transformation as well.

[spatel]

llvm/test/Transforms/InstCombine/logical-select.ll

1135

Ah, I see now. We get the commuted case where or is the condition because we use impliesPoison() to convert the select into a regular bitwise logic and, and the fold is handled by matching regular bitwise logic ops.

When the or is the true value of the select, we can't do that. That's because if %b is poison, then the select can prevent it from leaking to the final result value:
https://alive2.llvm.org/ce/z/H-HKdz

[paulwalker-arm]

Add matching combine for "A | (~A & B) --> A | B".

[spatel]

This looks close to me, but see inline comments on the tests, and please pre-commit those with the baseline CHECK lines, so we'll just show test diffs in this patch.

llvm/test/Transforms/InstCombine/logical-select.ll

1153

The test name is a bit misleading here - it's not a commute variation; it's replacing a bitwise 'or' with a 'logical-or'.

1165

Instead of repeating the test with a vector type (which we already verified works in the 2nd test), this test would provide better coverage if it included extra uses of the intermediate logic ops. That shows that the transform is still valid and intentional regardless of other uses.

1176

It would be better to keep this formula synchronized with the test (and the comment on the next line), so commute:
"A & (B | ~A)"

1191

Same comments for this set of tests as above, but a couple of additional potential tests:

1. Include a poison element in the vector constant to show that works too.
2. Add a negative test where 'not %a' is replaced by an arbitary value to show that the transform only works when we have a specific value match.

[paulwalker-arm]

Rebase after updating and precommiting the tests.

[spatel]

LGTM

llvm/test/Transforms/InstCombine/logical-select.ll

1143–1144

Nit: the code comments describe what the tests are checking, so that's good, but we still prefer that tests have a more meaningful name vs. generic "testN". I'd call all of the tests in this set something like "logical_and_or_with_common_not_op" or something like that.
Then the conjugated logic set that ends in or would be "logical_or_and_with_common_not_op".

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

Instruction *InstCombinerImpl::foldSelectOfBools(SelectInst &SI) {
   // select (select a, true, b), true, b -> select a, true, b
   if (match(CondVal, m_Select(m_Value(A), m_One(), m_Value(B))) &&
       match(TrueVal, m_One()) && match(FalseVal, m_Specific(B)))
     return replaceOperand(SI, 0, A);
   // select (select a, b, false), b, false -> select a, b, false
   if (match(CondVal, m_Select(m_Value(A), m_Value(B), m_Zero())) &&
       match(TrueVal, m_Specific(B)) && match(FalseVal, m_Zero()))
     return replaceOperand(SI, 0, A);
+  // select a, (select ~a, true, b), false -> select a, b, false
+  if (match(TrueVal, m_c_LogicalOr(m_Not(m_Specific(CondVal)), m_Value(B))) &&
+      match(FalseVal, m_Zero()))
+    return replaceOperand(SI, 1, B);
+  // select a, true, (select ~a, b, false) -> select a, true, b
+  if (match(FalseVal, m_c_LogicalAnd(m_Not(m_Specific(CondVal)), m_Value(B))) &&
+      match(TrueVal, m_One()))
+    return replaceOperand(SI, 2, B);
 
   // ~(A & B) & (A | B) --> A ^ B
   if (match(&SI, m_c_LogicalAnd(m_Not(m_LogicalAnd(m_Value(A), m_Value(B))),
                                 m_c_LogicalOr(m_Deferred(A), m_Deferred(B)))))
     return BinaryOperator::CreateXor(A, B);
 
   // select (~a | c), a, b -> and a, (or c, freeze(b))
   if (match(CondVal, m_c_Or(m_Not(m_Specific(TrueVal)), m_Value(C))) &&

llvm/test/Transforms/InstCombine/logical-select.ll

;
   %and1 = and i1 %c, %x
   %r = or i1 %and1, %and2
   call void @use1(i1 %and2)
   call void @use1(i1 %and1)
   ret i1 %r
 }
 
 ; A & (~C | B)
-define i1 @test1(i1 %a, i1 %b, i1 %c) {
-; CHECK-LABEL: @test1(
+define i1 @logical_and_or_with_not_op(i1 %a, i1 %b, i1 %c) {
+; CHECK-LABEL: @logical_and_or_with_not_op(
 ; CHECK-NEXT:    [[NOT:%.*]] = xor i1 [[C:%.*]], true
 ; CHECK-NEXT:    [[OR:%.*]] = or i1 [[NOT]], [[B:%.*]]
 ; CHECK-NEXT:    [[AND:%.*]] = select i1 [[A:%.*]], i1 [[OR]], i1 false
 ; CHECK-NEXT:    ret i1 [[AND]]
 ;
   %not = xor i1 %c, true
   %or = or i1 %not, %b
   %and = select i1 %a, i1 %or, i1 zeroinitializer
   ret i1 %and
 }
 
-; As test1 but with C=A
+; As logical_and_or_with_not_op but with C=A
 ; A & (~A | B) --> A & B
-define i1 @test1_variant1(i1 %a, i1 %b) {
-; CHECK-LABEL: @test1_variant1(
-; CHECK-NEXT:    [[NOT:%.*]] = xor i1 [[A:%.*]], true
-; CHECK-NEXT:    [[OR:%.*]] = or i1 [[NOT]], [[B:%.*]]
-; CHECK-NEXT:    [[AND:%.*]] = select i1 [[A]], i1 [[OR]], i1 false
+define i1 @logical_and_or_with_common_not_op_variant1(i1 %a, i1 %b) {
+; CHECK-LABEL: @logical_and_or_with_common_not_op_variant1(
+; CHECK-NEXT:    [[AND:%.*]] = select i1 [[A:%.*]], i1 [[B:%.*]], i1 false
 ; CHECK-NEXT:    ret i1 [[AND]]
 ;
   %not = xor i1 %a, true
   %or = or i1 %not, %b
   %and = select i1 %a, i1 %or, i1 zeroinitializer
   ret i1 %and
 }
 
-; As test1_variant1 but operating on vectors
+; As logical_and_or_with_common_not_op_variant1 but operating on vectors
 ; A & (~A | B) --> A & B
-define <2 x i1> @test1_variant2(<2 x i1> %a, <2 x i1> %b) {
-; CHECK-LABEL: @test1_variant2(
-; CHECK-NEXT:    [[NOT:%.*]] = xor <2 x i1> [[A:%.*]], <i1 true, i1 true>
-; CHECK-NEXT:    [[OR:%.*]] = or <2 x i1> [[NOT]], [[B:%.*]]
-; CHECK-NEXT:    [[AND:%.*]] = select <2 x i1> [[A]], <2 x i1> [[OR]], <2 x i1> zeroinitializer
+define <2 x i1> @logical_and_or_with_common_not_op_variant2(<2 x i1> %a, <2 x i1> %b) {
+; CHECK-LABEL: @logical_and_or_with_common_not_op_variant2(
+; CHECK-NEXT:    [[AND:%.*]] = select <2 x i1> [[A:%.*]], <2 x i1> [[B:%.*]], <2 x i1> zeroinitializer
 ; CHECK-NEXT:    ret <2 x i1> [[AND]]
 ;
   %not = xor <2 x i1> %a, <i1 true, i1 true>
   %or = or <2 x i1> %not, %b
   %and = select <2 x i1> %a, <2 x i1> %or, <2 x i1> zeroinitializer
   ret <2 x i1> %and
 }
 
-; As test1_variant1 but with "or" implemented as "select X, true, Y"
+; As logical_and_or_with_common_not_op_variant1 but with "or" implemented as
+; "select X, true, Y"
 ; A & (~A | B) --> A & B
-define i1 @test1_variant3(i1 %a, i1 %b) {
-; CHECK-LABEL: @test1_variant3(
-; CHECK-NEXT:    [[NOT:%.*]] = xor i1 [[A:%.*]], true
-; CHECK-NEXT:    [[OR:%.*]] = select i1 [[NOT]], i1 true, i1 [[B:%.*]]
-; CHECK-NEXT:    [[AND:%.*]] = select i1 [[A]], i1 [[OR]], i1 false
+define i1 @logical_and_or_with_common_not_op_variant3(i1 %a, i1 %b) {
+; CHECK-LABEL: @logical_and_or_with_common_not_op_variant3(
+; CHECK-NEXT:    [[AND:%.*]] = select i1 [[A:%.*]], i1 [[B:%.*]], i1 false
 ; CHECK-NEXT:    ret i1 [[AND]]
 ;
   %not = xor i1 %a, true
   %or = select i1 %not, i1 true, i1 %b
   %and = select i1 %a, i1 %or, i1 zeroinitializer
   ret i1 %and
 }
 
-; As test1_variant3 but operating on vectors where each operand has other uses
+; As logical_and_or_with_common_not_op_variant3 but operating on vectors where
+; each operand has other uses
 ; A & (~A | B) --> A & B
-define <2 x i1> @test1_variant4(<2 x i1> %a, <2 x i1> %b) {
-; CHECK-LABEL: @test1_variant4(
+define <2 x i1> @logical_and_or_with_common_not_op_variant4(<2 x i1> %a, <2 x i1> %b) {
+; CHECK-LABEL: @logical_and_or_with_common_not_op_variant4(
 ; CHECK-NEXT:    [[NOT:%.*]] = xor <2 x i1> [[A:%.*]], <i1 true, i1 true>
 ; CHECK-NEXT:    [[OR:%.*]] = select <2 x i1> [[NOT]], <2 x i1> <i1 true, i1 true>, <2 x i1> [[B:%.*]]
-; CHECK-NEXT:    [[AND:%.*]] = select <2 x i1> [[A]], <2 x i1> [[OR]], <2 x i1> zeroinitializer
+; CHECK-NEXT:    [[AND:%.*]] = select <2 x i1> [[A]], <2 x i1> [[B]], <2 x i1> zeroinitializer
 ; CHECK-NEXT:    call void @use2(<2 x i1> [[A]])
 ; CHECK-NEXT:    call void @use2(<2 x i1> [[B]])
 ; CHECK-NEXT:    call void @use2(<2 x i1> [[OR]])
 ; CHECK-NEXT:    ret <2 x i1> [[AND]]
 ;
   %not = xor <2 x i1> %a, <i1 true, i1 true>
   %or = select <2 x i1> %not, <2 x i1> <i1 true, i1 true>, <2 x i1> %b
   %and = select <2 x i1> %a, <2 x i1> %or, <2 x i1> zeroinitializer
   call void @use2(<2 x i1> %a)
   call void @use2(<2 x i1> %b)
   call void @use2(<2 x i1> %or)
   ret <2 x i1> %and
 }
 
-; As test1_variant1 but with |'s operands swapped
+; As logical_and_or_with_common_not_op_variant1 but with |'s operands swapped
 ; A & (B | ~A) --> A & B
-define i1 @test1_variant5(i1 %a) {
-; CHECK-LABEL: @test1_variant5(
+define i1 @logical_and_or_with_common_not_op_variant5(i1 %a) {
+; CHECK-LABEL: @logical_and_or_with_common_not_op_variant5(
 ; CHECK-NEXT:    [[B:%.*]] = call i1 @gen()
-; CHECK-NEXT:    [[NOT:%.*]] = xor i1 [[A:%.*]], true
-; CHECK-NEXT:    [[OR:%.*]] = or i1 [[B]], [[NOT]]
-; CHECK-NEXT:    [[AND:%.*]] = select i1 [[A]], i1 [[OR]], i1 false
+; CHECK-NEXT:    [[AND:%.*]] = select i1 [[A:%.*]], i1 [[B]], i1 false
 ; CHECK-NEXT:    ret i1 [[AND]]
 ;
   %b = call i1 @gen()
   %not = xor i1 %a, true
   %or = or i1 %b, %not
   %and = select i1 %a, i1 %or, i1 zeroinitializer
   ret i1 %and
 }
 
 ; A | (~C & B)
-define i1 @test2(i1 %a, i1 %b, i1 %c) {
-; CHECK-LABEL: @test2(
+define i1 @logical_or_and_with_not_op(i1 %a, i1 %b, i1 %c) {
+; CHECK-LABEL: @logical_or_and_with_not_op(
 ; CHECK-NEXT:    [[NOT:%.*]] = xor i1 [[C:%.*]], true
 ; CHECK-NEXT:    [[AND:%.*]] = and i1 [[NOT]], [[B:%.*]]
 ; CHECK-NEXT:    [[OR:%.*]] = select i1 [[A:%.*]], i1 true, i1 [[AND]]
 ; CHECK-NEXT:    ret i1 [[OR]]
 ;
   %not = xor i1 %c, true
   %and = and i1 %not, %b
   %or = select i1 %a, i1 true, i1 %and
   ret i1 %or
 }
 
-; As test2 but with C=A
+; As logical_or_and_with_not_op but with C=A
 ; A | (~A & B) --> A | B
-define i1 @test2_variant1(i1 %a, i1 %b) {
-; CHECK-LABEL: @test2_variant1(
-; CHECK-NEXT:    [[NOT:%.*]] = xor i1 [[A:%.*]], true
-; CHECK-NEXT:    [[AND:%.*]] = and i1 [[NOT]], [[B:%.*]]
-; CHECK-NEXT:    [[OR:%.*]] = select i1 [[A]], i1 true, i1 [[AND]]
+define i1 @logical_or_and_with_common_not_op_variant1(i1 %a, i1 %b) {
+; CHECK-LABEL: @logical_or_and_with_common_not_op_variant1(
+; CHECK-NEXT:    [[OR:%.*]] = select i1 [[A:%.*]], i1 true, i1 [[B:%.*]]
 ; CHECK-NEXT:    ret i1 [[OR]]
 ;
   %not = xor i1 %a, true
   %and = and i1 %not, %b
   %or = select i1 %a, i1 true, i1 %and
   ret i1 %or
 }
 
-; As test2_variant1 but operating on vectors
+; As logical_or_and_with_common_not_op_variant1 but operating on vectors
 ; A | (~A & B) --> A | B
-define <2 x i1> @test2_variant2(<2 x i1> %a, <2 x i1> %b) {
-; CHECK-LABEL: @test2_variant2(
-; CHECK-NEXT:    [[NOT:%.*]] = xor <2 x i1> [[A:%.*]], <i1 true, i1 true>
-; CHECK-NEXT:    [[AND:%.*]] = and <2 x i1> [[NOT]], [[B:%.*]]
-; CHECK-NEXT:    [[OR:%.*]] = select <2 x i1> [[A]], <2 x i1> <i1 true, i1 true>, <2 x i1> [[AND]]
+define <2 x i1> @logical_or_and_with_common_not_op_variant2(<2 x i1> %a, <2 x i1> %b) {
+; CHECK-LABEL: @logical_or_and_with_common_not_op_variant2(
+; CHECK-NEXT:    [[OR:%.*]] = select <2 x i1> [[A:%.*]], <2 x i1> <i1 true, i1 true>, <2 x i1> [[B:%.*]]
 ; CHECK-NEXT:    ret <2 x i1> [[OR]]
 ;
   %not = xor <2 x i1> %a, <i1 true, i1 true>
   %and = and <2 x i1> %not, %b
   %or = select <2 x i1> %a, <2 x i1> <i1 true, i1 true>, <2 x i1> %and
   ret <2 x i1> %or
 }
 
-; As test2_variant1 but with "and" implemented as "select X, Y, false"
+; As logical_or_and_with_common_not_op_variant1 but with "and" implemented as
+; "select X, Y, false"
 ; A | (~A & B) --> A | B
-define i1 @test2_variant3(i1 %a, i1 %b) {
-; CHECK-LABEL: @test2_variant3(
-; CHECK-NEXT:    [[NOT:%.*]] = xor i1 [[A:%.*]], true
-; CHECK-NEXT:    [[AND:%.*]] = select i1 [[NOT]], i1 [[B:%.*]], i1 false
-; CHECK-NEXT:    [[OR:%.*]] = select i1 [[A]], i1 true, i1 [[AND]]
+define i1 @logical_or_and_with_common_not_op_variant3(i1 %a, i1 %b) {
+; CHECK-LABEL: @logical_or_and_with_common_not_op_variant3(
+; CHECK-NEXT:    [[OR:%.*]] = select i1 [[A:%.*]], i1 true, i1 [[B:%.*]]
 ; CHECK-NEXT:    ret i1 [[OR]]
 ;
   %not = xor i1 %a, true
   %and = select i1 %not, i1 %b, i1 false
   %or = select i1 %a, i1 true, i1 %and
   ret i1 %or
 }
 
-; As test2_variant3 but operating on vectors where each operand has other uses
+; As logical_or_and_with_common_not_op_variant3 but operating on vectors where
+; each operand has other uses
 ; A | (~A & B) --> A | B
-define <2 x i1> @test2_variant4(<2 x i1> %a, <2 x i1> %b) {
-; CHECK-LABEL: @test2_variant4(
+define <2 x i1> @logical_or_and_with_common_not_op_variant4(<2 x i1> %a, <2 x i1> %b) {
+; CHECK-LABEL: @logical_or_and_with_common_not_op_variant4(
 ; CHECK-NEXT:    [[NOT:%.*]] = xor <2 x i1> [[A:%.*]], <i1 true, i1 true>
 ; CHECK-NEXT:    [[AND:%.*]] = select <2 x i1> [[NOT]], <2 x i1> [[B:%.*]], <2 x i1> zeroinitializer
-; CHECK-NEXT:    [[OR:%.*]] = select <2 x i1> [[A]], <2 x i1> <i1 true, i1 true>, <2 x i1> [[AND]]
+; CHECK-NEXT:    [[OR:%.*]] = select <2 x i1> [[A]], <2 x i1> <i1 true, i1 true>, <2 x i1> [[B]]
 ; CHECK-NEXT:    call void @use2(<2 x i1> [[A]])
 ; CHECK-NEXT:    call void @use2(<2 x i1> [[B]])
 ; CHECK-NEXT:    call void @use2(<2 x i1> [[AND]])
 ; CHECK-NEXT:    ret <2 x i1> [[OR]]
 ;
   %not = xor <2 x i1> %a, <i1 true, i1 true>
   %and = select <2 x i1> %not, <2 x i1> %b, <2 x i1> zeroinitializer
   %or = select <2 x i1> %a, <2 x i1> <i1 true, i1 true>, <2 x i1> %and
   call void @use2(<2 x i1> %a)
   call void @use2(<2 x i1> %b)
   call void @use2(<2 x i1> %and)
   ret <2 x i1> %or
 }
 
-; As test2_variant1 but with &'s operands swapped
+; As logical_or_and_with_common_not_op_variant1 but with &'s operands swapped
 ; A | (B & ~A) --> A | B
-define i1 @test2_variant5(i1 %a) {
-; CHECK-LABEL: @test2_variant5(
+define i1 @logical_or_and_with_common_not_op_variant5(i1 %a) {
+; CHECK-LABEL: @logical_or_and_with_common_not_op_variant5(
 ; CHECK-NEXT:    [[B:%.*]] = call i1 @gen()
-; CHECK-NEXT:    [[NOT:%.*]] = xor i1 [[A:%.*]], true
-; CHECK-NEXT:    [[AND:%.*]] = and i1 [[B]], [[NOT]]
-; CHECK-NEXT:    [[OR:%.*]] = select i1 [[A]], i1 true, i1 [[AND]]
+; CHECK-NEXT:    [[OR:%.*]] = select i1 [[A:%.*]], i1 true, i1 [[B]]
 ; CHECK-NEXT:    ret i1 [[OR]]
 ;
   %b = call i1 @gen()
   %not = xor i1 %a, true
   %and = and i1 %b, %not
   %or = select i1 %a, i1 true, i1 %and
   ret i1 %or
 }