[InstCombine] simplify (~A | B) ^ A --> ~( A & B)

[MehrHeidar]

Summary

This bug is reported at : https://bugs.llvm.org/show_bug.cgi?id=52518

According to the Alive2, https://alive2.llvm.org/ce/z/gLrYPk, the transformation seems to be correct and -O2/-O3 does not do it.

[foad]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

3627

This probably needs some m_OneUses (but I'm not sure how you decide exactly where to put them).

[spatel]

1. Please commit the baseline tests, so we see diffs here.
2. I expect that will show that the commuted variations are not testing what they claim to be testing (you'll need to add instructions to prevent commuting).
3. Please add tests with extra uses - since we're creating 2 instructions, the fold should be good as long as any one of the intermediate values can be eliminated (has one use).

Side note: @rampitec recently added a matcher that takes a binary opcode as an input. It probably doesn't make sense here, but it's something to think about if we're trying to make logic folds more regular/predictable ('DeMorganize' folds so we handle patterns where 'and' and 'or' operations are swapped).

[MehrHeidar]

In D114339#3146382, @spatel wrote:

1. Please commit the baseline tests, so we see diffs here.
2. I expect that will show that the commuted variations are not testing what they claim to be testing (you'll need to add instructions to prevent commuting).
3. Please add tests with extra uses - since we're creating 2 instructions, the fold should be good as long as any one of the intermediate values can be eliminated (has one use).

Side note: @rampitec recently added a matcher that takes a binary opcode as an input. It probably doesn't make sense here, but it's something to think about if we're trying to make logic folds more regular/predictable ('DeMorganize' folds so we handle patterns where 'and' and 'or' operations are swapped).

Thanks for you suggestion.
I have modified the tests and committed them in D114436;
I did change the code as well;
Though it's still conservative in terms that both should have only use. Since, we were removing an instruction from a combination of 3, I thought if any of them have an extra use then the number of instructions after fold will remains 3.
Also, regarding your last suggestion, I am agree that it's a good idea to make these logic folds more predictable. I will start in this direction.

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

3627

Thank you!
I added the m_OneUse as per you suggestion in new commit.

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

3627

I'm not sure how the matching logic or one-use logic works here. It seems dangerous to overwrite the Op0/Op1 locals.

If you want a conservative use check, just put that on the 'or' instruction - as long as we're eliminating that instruction, this transform is a win:

// (~A | B) ^ A --> ~(A & B)
if (match(Op0, m_OneUse(m_c_Or(m_Not(m_Specific(Op1)), m_Value(B)))))
  return BinaryOperator::CreateNot(Builder.CreateAnd(Op1, B));

// A ^ (~A | B) --> ~(A & B)
if (match(Op1, m_OneUse(m_c_Or(m_Not(m_Specific(Op0)), m_Value(B)))))
  return BinaryOperator::CreateNot(Builder.CreateAnd(Op0, B));

But I think we're missing a test where the 'not A' has another use. Please add and make sure that looks right.

[MehrHeidar]

Addressing review comments.

[MehrHeidar]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

3627

Thank you for your suggestions, I was not aware that overwriting the operands might be dangerous. I changed the code.
About the missing test case for an extra use of NotA, I had the test but because previous code was also checking for NotA to have only a single use, we were not actually folding this pattern.
However now, by putting m_OneUse on the or instruction, folding is done and the changes can be shown against the base result.

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

3632–3633

Is this logically different than the m_Specific(Op0) code pattern that I suggested?
Unless I'm missing something, you don't need to use m_Deferred either way. In this code, the clause before && must run and capture 'A' before it is matched as Op0.

[MehrHeidar]

Addressing review comments.

[MehrHeidar]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

3632–3633

Sorry for delay on following this issue.

Is this logically different than the m_Specific(Op0) code pattern that I suggested?
Unless I'm missing something, you don't need to use m_Deferred either way. In this code, the clause before && must run and capture 'A' before it is matched as Op0.

Oh, I see. I think I misunderstood your previous comment then. I tried to avoid any use of Op0/Op1 in any of the m_Specific/m_Value/m_Deferred, so I wrote the code in that way in the previous commit. I did replace the code as your suggestion.

Thanks.

3632–3633

Is this logically different than the m_Specific(Op0) code pattern that I suggested?
Unless I'm missing something, you don't need to use m_Deferred either way. In this code, the clause before && must run and capture 'A' before it is matched as Op0.

[spatel]

LGTM

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

Instruction *InstCombinerImpl::visitXor(BinaryOperator &I) {
   if (match(Op0, m_c_And(m_Value(A), m_Not(m_Value(B)))) &&
       match(Op1, m_Not(m_Specific(A))))
     return BinaryOperator::CreateNot(Builder.CreateAnd(A, B));
 
   // (~A & B) ^ A --> A | B -- There are 4 commuted variants.
   if (match(&I, m_c_Xor(m_c_And(m_Not(m_Value(A)), m_Value(B)), m_Deferred(A))))
     return BinaryOperator::CreateOr(A, B);
 
+  // (~A | B) ^ A --> ~(A & B)
+  if (match(Op0, m_OneUse(m_c_Or(m_Not(m_Specific(Op1)), m_Value(B)))))
+    return BinaryOperator::CreateNot(Builder.CreateAnd(Op1, B));
+
+  // A ^ (~A | B) --> ~(A & B)
+  if (match(Op1, m_OneUse(m_c_Or(m_Not(m_Specific(Op0)), m_Value(B)))))
+    return BinaryOperator::CreateNot(Builder.CreateAnd(Op0, B));
+
   // (A | B) ^ (A | C) --> (B ^ C) & ~A -- There are 4 commuted variants.
   // TODO: Loosen one-use restriction if common operand is a constant.
   Value *D;
   if (match(Op0, m_OneUse(m_Or(m_Value(A), m_Value(B)))) &&
       match(Op1, m_OneUse(m_Or(m_Value(C), m_Value(D))))) {
     if (B == C || B == D)
       std::swap(A, B);
     if (A == C)

llvm/test/Transforms/InstCombine/xor.ll

;
   %z = xor i32 %a, %r
   ret i32 %z
 }
 
 ; (~A | B) ^ A --> ~(A & B)
 
 define <2 x i64> @xor_orn(<2 x i64> %a, <2 x i64> %b) {
 ; CHECK-LABEL: @xor_orn(
-; CHECK-NEXT:    [[NOTA:%.*]] = xor <2 x i64> [[A:%.*]], <i64 -1, i64 -1>
-; CHECK-NEXT:    [[L:%.*]] = or <2 x i64> [[NOTA]], [[B:%.*]]
-; CHECK-NEXT:    [[Z:%.*]] = xor <2 x i64> [[L]], [[A]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i64> [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[Z:%.*]] = xor <2 x i64> [[TMP1]], <i64 -1, i64 -1>
 ; CHECK-NEXT:    ret <2 x i64> [[Z]]
 ;
   %nota = xor <2 x i64> %a, <i64 -1, i64 -1>
   %l = or <2 x i64> %nota, %b
   %z = xor <2 x i64> %l, %a
   ret <2 x i64> %z
 }
 
 ; A  ^ (~A | B) --> ~(A & B)
 
 define i8 @xor_orn_commute1(i8 %pa, i8 %b) {
 ; CHECK-LABEL: @xor_orn_commute1(
 ; CHECK-NEXT:    [[A:%.*]] = udiv i8 42, [[PA:%.*]]
-; CHECK-NEXT:    [[NOTA:%.*]] = xor i8 [[A]], -1
-; CHECK-NEXT:    [[L:%.*]] = or i8 [[NOTA]], [[B:%.*]]
-; CHECK-NEXT:    [[Z:%.*]] = xor i8 [[A]], [[L]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[A]], [[B:%.*]]
+; CHECK-NEXT:    [[Z:%.*]] = xor i8 [[TMP1]], -1
 ; CHECK-NEXT:    ret i8 [[Z]]
 ;
   %a = udiv i8 42, %pa
   %nota = xor i8 %a, -1
   %l = or i8 %nota, %b
   %z = xor i8 %a, %l
   ret i8 %z
 }
 
 ; (B | ~A) ^ A --> ~(A & B)
 
 define i32 @xor_orn_commute2(i32 %a, i32 %pb,i32* %s) {
 ; CHECK-LABEL: @xor_orn_commute2(
 ; CHECK-NEXT:    [[B:%.*]] = udiv i32 42, [[PB:%.*]]
-; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
-; CHECK-NEXT:    [[L:%.*]] = or i32 [[B]], [[NOTA]]
-; CHECK-NEXT:    [[Z:%.*]] = xor i32 [[L]], [[A]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[B]], [[A:%.*]]
+; CHECK-NEXT:    [[Z:%.*]] = xor i32 [[TMP1]], -1
 ; CHECK-NEXT:    ret i32 [[Z]]
 ;
   %b = udiv i32 42, %pb
   %nota = xor i32 %a, -1
   %l = or i32 %b, %nota
   %z = xor i32 %l, %a
   ret i32 %z
 }
 
-
 define i32 @xor_orn_commute2_1use(i32 %a, i32 %pb,i32* %s) {
 ; CHECK-LABEL: @xor_orn_commute2_1use(
 ; CHECK-NEXT:    [[B:%.*]] = udiv i32 42, [[PB:%.*]]
 ; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
-; CHECK-NEXT:    [[L:%.*]] = or i32 [[B]], [[NOTA]]
 ; CHECK-NEXT:    store i32 [[NOTA]], i32* [[S:%.*]], align 4
-; CHECK-NEXT:    [[Z:%.*]] = xor i32 [[L]], [[A]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[B]], [[A]]
+; CHECK-NEXT:    [[Z:%.*]] = xor i32 [[TMP1]], -1
 ; CHECK-NEXT:    ret i32 [[Z]]
 ;
   %b = udiv i32 42, %pb
   %nota = xor i32 %a, -1
   %l = or i32 %b, %nota
   store i32 %nota, i32* %s
   %z = xor i32 %l, %a
   ret i32 %z
 }
 
 ; A ^ (B | ~A) --> ~(A & B)
 
 define i67 @xor_orn_commute3(i67 %pa, i67 %pb, i67* %s) {
 ; CHECK-LABEL: @xor_orn_commute3(
 ; CHECK-NEXT:    [[A:%.*]] = udiv i67 42, [[PA:%.*]]
 ; CHECK-NEXT:    [[B:%.*]] = udiv i67 42, [[PB:%.*]]
-; CHECK-NEXT:    [[NOTA:%.*]] = xor i67 [[A]], -1
-; CHECK-NEXT:    [[L:%.*]] = or i67 [[B]], [[NOTA]]
-; CHECK-NEXT:    [[Z:%.*]] = xor i67 [[A]], [[L]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i67 [[A]], [[B]]
+; CHECK-NEXT:    [[Z:%.*]] = xor i67 [[TMP1]], -1
 ; CHECK-NEXT:    ret i67 [[Z]]
 ;
   %a = udiv i67 42, %pa
   %b = udiv i67 42, %pb
   %nota = xor i67 %a, -1
   %l = or i67 %b, %nota
   %z = xor i67 %a, %l
   ret i67 %z
;
   %b = udiv i67 42, %pb
   %nota = xor i67 %a, -1
   %l = or i67 %b, %nota
   store i67 %l, i67* %s
   %z = xor i67 %a, %l
   ret i67 %z
 }
 
-
 define i32 @xor_orn_2use(i32 %a, i32 %b, i32* %s1, i32* %s2) {
 ; CHECK-LABEL: @xor_orn_2use(
 ; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
 ; CHECK-NEXT:    store i32 [[NOTA]], i32* [[S1:%.*]], align 4
 ; CHECK-NEXT:    [[L:%.*]] = or i32 [[NOTA]], [[B:%.*]]
 ; CHECK-NEXT:    store i32 [[L]], i32* [[S2:%.*]], align 4
 ; CHECK-NEXT:    [[Z:%.*]] = xor i32 [[L]], [[A]]
 ; CHECK-NEXT:    ret i32 [[Z]]
 ;
   %nota = xor i32 %a, -1
   store i32 %nota, i32* %s1
   %l = or i32 %nota, %b
   store i32 %l, i32* %s2
   %z = xor i32 %l, %a
   ret i32 %z
 }