[Instcombine] Canonicalize ~((A & B) ^ (A | ?)) -> (A & B) | ~(A | ?)

[bcl5980]

Summary

~((A & B) ^ (A | ?)) -> (A & B) | ~(A | ?)
https://alive2.llvm.org/ce/z/JHN2p4

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

3480

I see that the first match is shared, but this function name and description are not accurate if we add the new fold inside here.

It would be better to create/rename this function as foldNotXor() that has the first match, then it calls or includes sinkNotIntoXor() and includes the new code.

[spatel]

Was there a problem with D139300? That is the same transform as this, but coded differently, right? I find that version easier to read even if it repeats the match for ~xor.

[bcl5980]

In D139299#3975362, @spatel wrote:

Was there a problem with D139300? That is the same transform as this, but coded differently, right? I find that version easier to read even if it repeats the match for ~xor.

The original idea is this patch do
~((A & B) ^ (A | ?)) -> (A & B) | ~(A | ?)

D139300 do
~(A & B) ^ (A | ?) -> (A & B) | ~(A | ?)

Then I find this patch can cover D139300, so I abandon D139300.

[spatel]

LGTM

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

 }
 
 // Transform
 //   ~(x ^ y)
 // into:
 //   (~x) ^ y
 // or into
 //   x ^ (~y)
-static Instruction *sinkNotIntoXor(BinaryOperator &I,
+static Instruction *sinkNotIntoXor(BinaryOperator &I, Value *X, Value *Y,
                                    InstCombiner::BuilderTy &Builder) {
-  Value *X, *Y;
-  // FIXME: one-use check is not needed in general, but currently we are unable
-  // to fold 'not' into 'icmp', if that 'icmp' has multiple uses. (D35182)
-  if (!match(&I, m_Not(m_OneUse(m_Xor(m_Value(X), m_Value(Y))))))
-    return nullptr;
-
   // We only want to do the transform if it is free to do.
   if (InstCombiner::isFreeToInvert(X, X->hasOneUse())) {
     // Ok, good.
   } else if (InstCombiner::isFreeToInvert(Y, Y->hasOneUse())) {
     std::swap(X, Y);
   } else
     return nullptr;
 
   Value *NotX = Builder.CreateNot(X, X->getName() + ".not");
   return BinaryOperator::CreateXor(NotX, Y, I.getName() + ".demorgan");
 }
 
+static Instruction *foldNotXor(BinaryOperator &I,
+                               InstCombiner::BuilderTy &Builder) {
+  Value *X, *Y;
+  // FIXME: one-use check is not needed in general, but currently we are unable
+  // to fold 'not' into 'icmp', if that 'icmp' has multiple uses. (D35182)
+  if (!match(&I, m_Not(m_OneUse(m_Xor(m_Value(X), m_Value(Y))))))
+    return nullptr;
+
+  if (Instruction *NewXor = sinkNotIntoXor(I, X, Y, Builder))
+    return NewXor;
+
+  auto hasCommonOperand = [](Value *A, Value *B, Value *C, Value *D) {
+    return A == C || A == D || B == C || B == D;
+  };
+
+  Value *A, *B, *C, *D;
+  // Canonicalize ~((A & B) ^ (A | ?)) -> (A & B) | ~(A | ?)
+  // 4 commuted variants
+  if (match(X, m_And(m_Value(A), m_Value(B))) &&
+      match(Y, m_Or(m_Value(C), m_Value(D))) && hasCommonOperand(A, B, C, D)) {
+    Value *NotY = Builder.CreateNot(Y);
+    return BinaryOperator::CreateOr(X, NotY);
+  };
+
+  // Canonicalize ~((A | ?) ^ (A & B)) -> (A & B) | ~(A | ?)
+  // 4 commuted variants
+  if (match(Y, m_And(m_Value(A), m_Value(B))) &&
+      match(X, m_Or(m_Value(C), m_Value(D))) && hasCommonOperand(A, B, C, D)) {
+    Value *NotX = Builder.CreateNot(X);
+    return BinaryOperator::CreateOr(Y, NotX);
+  };
+
+  return nullptr;
+}
+
 /// Canonicalize a shifty way to code absolute value to the more common pattern
 /// that uses negation and select.
 static Instruction *canonicalizeAbs(BinaryOperator &Xor,
                                     InstCombiner::BuilderTy &Builder) {
   assert(Xor.getOpcode() == Instruction::Xor && "Expected an xor instruction.");
 
   // There are 4 potential commuted variants. Move the 'ashr' candidate to Op1.
   // We're relying on the fact that we only do this transform when the shift has
if (auto *Sel = dyn_cast<SelectInst>(NotOp)) {
           CmpF->setPredicate(CmpF->getInversePredicate());
         else
           Sel->setFalseValue(ConstantExpr::getNot(cast<Constant>(FV)));
         return replaceInstUsesWith(I, Sel);
       }
     }
   }
 
-  if (Instruction *NewXor = sinkNotIntoXor(I, Builder))
+  if (Instruction *NewXor = foldNotXor(I, Builder))
     return NewXor;
 
   return nullptr;
 }
 
 // FIXME: We use commutative matchers (m_c_*) for some, but not all, matches
 // here. We should standardize that construct where it is needed or choose some
 // other way to ensure that commutated variants of patterns are not missed.

llvm/test/Transforms/InstCombine/xor2.ll

;
   %xor1 = xor i8 %B, %A
   %not = xor i8 %A, 33
   %xor2 = xor i8 %not, %B
   %and = and i8 %xor2, %xor1
   %res = mul i8 %and, %xor2 ; to increase the use count for the xor
   ret i8 %res
 }
 
-; TODO: Canonicalize ~((A & B) ^ (A | ?)) -> (A & B) | ~(A | ?)
+; Canonicalize ~((A & B) ^ (A | ?)) -> (A & B) | ~(A | ?)
 
 define i3 @not_xor_to_or_not1(i3 %a, i3 %b, i3 %c) {
 ; CHECK-LABEL: @not_xor_to_or_not1(
 ; CHECK-NEXT:    [[OR:%.*]] = or i3 [[B:%.*]], [[C:%.*]]
 ; CHECK-NEXT:    [[AND:%.*]] = and i3 [[A:%.*]], [[C]]
-; CHECK-NEXT:    [[XOR:%.*]] = xor i3 [[AND]], [[OR]]
-; CHECK-NEXT:    [[NOT:%.*]] = xor i3 [[XOR]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i3 [[OR]], -1
+; CHECK-NEXT:    [[NOT:%.*]] = or i3 [[AND]], [[TMP1]]
 ; CHECK-NEXT:    ret i3 [[NOT]]
 ;
   %or = or i3 %b, %c
   %and = and i3 %a, %c
   %xor = xor i3 %and, %or
   %not = xor i3 %xor, -1
   ret i3 %not
 }
 
 define i3 @not_xor_to_or_not2(i3 %a, i3 %b, i3 %c) {
 ; CHECK-LABEL: @not_xor_to_or_not2(
 ; CHECK-NEXT:    [[OR:%.*]] = or i3 [[C:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    [[AND:%.*]] = and i3 [[A:%.*]], [[C]]
-; CHECK-NEXT:    [[XOR:%.*]] = xor i3 [[AND]], [[OR]]
-; CHECK-NEXT:    [[NOT:%.*]] = xor i3 [[XOR]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i3 [[OR]], -1
+; CHECK-NEXT:    [[NOT:%.*]] = or i3 [[AND]], [[TMP1]]
 ; CHECK-NEXT:    ret i3 [[NOT]]
 ;
   %or = or i3 %c, %b
   %and = and i3 %a, %c
   %xor = xor i3 %and, %or
   %not = xor i3 %xor, -1
   ret i3 %not
 }
 
 define i3 @not_xor_to_or_not3(i3 %a, i3 %b, i3 %c) {
 ; CHECK-LABEL: @not_xor_to_or_not3(
 ; CHECK-NEXT:    [[OR:%.*]] = or i3 [[C:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    [[AND:%.*]] = and i3 [[C]], [[A:%.*]]
-; CHECK-NEXT:    [[XOR:%.*]] = xor i3 [[AND]], [[OR]]
-; CHECK-NEXT:    [[NOT:%.*]] = xor i3 [[XOR]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i3 [[OR]], -1
+; CHECK-NEXT:    [[NOT:%.*]] = or i3 [[AND]], [[TMP1]]
 ; CHECK-NEXT:    ret i3 [[NOT]]
 ;
   %or = or i3 %c, %b
   %and = and i3 %c, %a
   %xor = xor i3 %and, %or
   %not = xor i3 %xor, -1
   ret i3 %not
 }
 
 define i3 @not_xor_to_or_not4(i3 %a, i3 %b, i3 %c) {
 ; CHECK-LABEL: @not_xor_to_or_not4(
 ; CHECK-NEXT:    [[OR:%.*]] = or i3 [[B:%.*]], [[C:%.*]]
 ; CHECK-NEXT:    [[AND:%.*]] = and i3 [[C]], [[A:%.*]]
-; CHECK-NEXT:    [[XOR:%.*]] = xor i3 [[AND]], [[OR]]
-; CHECK-NEXT:    [[NOT:%.*]] = xor i3 [[XOR]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i3 [[OR]], -1
+; CHECK-NEXT:    [[NOT:%.*]] = or i3 [[AND]], [[TMP1]]
 ; CHECK-NEXT:    ret i3 [[NOT]]
 ;
   %or = or i3 %b, %c
   %and = and i3 %c, %a
   %xor = xor i3 %and, %or
   %not = xor i3 %xor, -1
   ret i3 %not
 }
 
 define <3 x i5> @not_xor_to_or_not_vector(<3 x i5> %a, <3 x i5> %b, <3 x i5> %c) {
 ; CHECK-LABEL: @not_xor_to_or_not_vector(
 ; CHECK-NEXT:    [[OR:%.*]] = or <3 x i5> [[B:%.*]], [[C:%.*]]
 ; CHECK-NEXT:    [[AND:%.*]] = and <3 x i5> [[A:%.*]], [[C]]
-; CHECK-NEXT:    [[XOR:%.*]] = xor <3 x i5> [[OR]], [[AND]]
-; CHECK-NEXT:    [[NOT:%.*]] = xor <3 x i5> [[XOR]], <i5 -1, i5 -1, i5 -1>
+; CHECK-NEXT:    [[TMP1:%.*]] = xor <3 x i5> [[OR]], <i5 -1, i5 -1, i5 -1>
+; CHECK-NEXT:    [[NOT:%.*]] = or <3 x i5> [[AND]], [[TMP1]]
 ; CHECK-NEXT:    ret <3 x i5> [[NOT]]
 ;
   %or = or <3 x i5> %b, %c
   %and = and <3 x i5> %a, %c
   %xor = xor <3 x i5> %or, %and
   %not = xor <3 x i5> %xor, <i5 -1, i5 -1, i5 -1>
   ret <3 x i5> %not
 }
 
 define <3 x i5> @not_xor_to_or_not_vector_poison(<3 x i5> %a, <3 x i5> %b, <3 x i5> %c) {
 ; CHECK-LABEL: @not_xor_to_or_not_vector_poison(
 ; CHECK-NEXT:    [[OR:%.*]] = or <3 x i5> [[B:%.*]], [[C:%.*]]
 ; CHECK-NEXT:    [[AND:%.*]] = and <3 x i5> [[A:%.*]], [[C]]
-; CHECK-NEXT:    [[XOR:%.*]] = xor <3 x i5> [[OR]], [[AND]]
-; CHECK-NEXT:    [[NOT:%.*]] = xor <3 x i5> [[XOR]], <i5 poison, i5 -1, i5 -1>
+; CHECK-NEXT:    [[TMP1:%.*]] = xor <3 x i5> [[OR]], <i5 -1, i5 -1, i5 -1>
+; CHECK-NEXT:    [[NOT:%.*]] = or <3 x i5> [[AND]], [[TMP1]]
 ; CHECK-NEXT:    ret <3 x i5> [[NOT]]
 ;
   %or = or <3 x i5> %b, %c
   %and = and <3 x i5> %a, %c
   %xor = xor <3 x i5> %or, %and
   %not = xor <3 x i5> %xor, <i5 poison, i5 -1, i5 -1>
   ret <3 x i5> %not
 }
 
+; negative test : not one use
+
 define i3 @not_xor_to_or_not_2use(i3 %a, i3 %b, i3 %c) {
 ; CHECK-LABEL: @not_xor_to_or_not_2use(
 ; CHECK-NEXT:    [[OR:%.*]] = or i3 [[B:%.*]], [[C:%.*]]
 ; CHECK-NEXT:    [[AND:%.*]] = and i3 [[A:%.*]], [[C]]
 ; CHECK-NEXT:    [[XOR:%.*]] = xor i3 [[AND]], [[OR]]
 ; CHECK-NEXT:    [[NOT:%.*]] = xor i3 [[XOR]], -1
 ; CHECK-NEXT:    call void @use3(i3 [[XOR]])
 ; CHECK-NEXT:    ret i3 [[NOT]]
 ;
   %or = or i3 %b, %c
   %and = and i3 %a, %c
   %xor = xor i3 %and, %or
   %not = xor i3 %xor, -1
   call void @use3(i3 %xor)
   ret i3 %not
 }
 
-; TODO: Canonicalize ~(A & B) ^ (A | ?) -> (A & B) | ~(A | ?)
+; Canonicalize ~(A & B) ^ (A | ?) -> (A & B) | ~(A | ?)
 
 define i3 @xor_notand_to_or_not1(i3 %a, i3 %b, i3 %c) {
 ; CHECK-LABEL: @xor_notand_to_or_not1(
 ; CHECK-NEXT:    [[OR:%.*]] = or i3 [[B:%.*]], [[C:%.*]]
 ; CHECK-NEXT:    [[AND:%.*]] = and i3 [[A:%.*]], [[C]]
-; CHECK-NEXT:    [[TMP1:%.*]] = xor i3 [[AND]], [[OR]]
-; CHECK-NEXT:    [[XOR:%.*]] = xor i3 [[TMP1]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i3 [[OR]], -1
+; CHECK-NEXT:    [[XOR:%.*]] = or i3 [[AND]], [[TMP1]]
 ; CHECK-NEXT:    ret i3 [[XOR]]
 ;
   %or = or i3 %b, %c
   %and = and i3 %a, %c
   %not = xor i3 %and, -1
   %xor = xor i3 %not, %or
   ret i3 %xor
 }
 
 define i3 @xor_notand_to_or_not2(i3 %a, i3 %b, i3 %c) {
 ; CHECK-LABEL: @xor_notand_to_or_not2(
 ; CHECK-NEXT:    [[OR:%.*]] = or i3 [[C:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    [[AND:%.*]] = and i3 [[A:%.*]], [[C]]
-; CHECK-NEXT:    [[TMP1:%.*]] = xor i3 [[AND]], [[OR]]
-; CHECK-NEXT:    [[XOR:%.*]] = xor i3 [[TMP1]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i3 [[OR]], -1
+; CHECK-NEXT:    [[XOR:%.*]] = or i3 [[AND]], [[TMP1]]
 ; CHECK-NEXT:    ret i3 [[XOR]]
 ;
   %or = or i3 %c, %b
   %and = and i3 %a, %c
   %not = xor i3 %and, -1
   %xor = xor i3 %not, %or
   ret i3 %xor
 }
 
 define i3 @xor_notand_to_or_not3(i3 %a, i3 %b, i3 %c) {
 ; CHECK-LABEL: @xor_notand_to_or_not3(
 ; CHECK-NEXT:    [[OR:%.*]] = or i3 [[C:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    [[AND:%.*]] = and i3 [[C]], [[A:%.*]]
-; CHECK-NEXT:    [[TMP1:%.*]] = xor i3 [[AND]], [[OR]]
-; CHECK-NEXT:    [[XOR:%.*]] = xor i3 [[TMP1]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i3 [[OR]], -1
+; CHECK-NEXT:    [[XOR:%.*]] = or i3 [[AND]], [[TMP1]]
 ; CHECK-NEXT:    ret i3 [[XOR]]
 ;
   %or = or i3 %c, %b
   %and = and i3 %c, %a
   %not = xor i3 %and, -1
   %xor = xor i3 %not, %or
   ret i3 %xor
 }
 
 define i3 @xor_notand_to_or_not4(i3 %a, i3 %b, i3 %c) {
 ; CHECK-LABEL: @xor_notand_to_or_not4(
 ; CHECK-NEXT:    [[OR:%.*]] = or i3 [[B:%.*]], [[C:%.*]]
 ; CHECK-NEXT:    [[AND:%.*]] = and i3 [[C]], [[A:%.*]]
-; CHECK-NEXT:    [[TMP1:%.*]] = xor i3 [[AND]], [[OR]]
-; CHECK-NEXT:    [[XOR:%.*]] = xor i3 [[TMP1]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i3 [[OR]], -1
+; CHECK-NEXT:    [[XOR:%.*]] = or i3 [[AND]], [[TMP1]]
 ; CHECK-NEXT:    ret i3 [[XOR]]
 ;
   %or = or i3 %b, %c
   %and = and i3 %c, %a
   %not = xor i3 %and, -1
   %xor = xor i3 %not, %or
   ret i3 %xor
 }
 
 define <3 x i5> @xor_notand_to_or_not_vector(<3 x i5> %a, <3 x i5> %b, <3 x i5> %c) {
 ; CHECK-LABEL: @xor_notand_to_or_not_vector(
 ; CHECK-NEXT:    [[OR:%.*]] = or <3 x i5> [[B:%.*]], [[C:%.*]]
 ; CHECK-NEXT:    [[AND:%.*]] = and <3 x i5> [[A:%.*]], [[C]]
-; CHECK-NEXT:    [[TMP1:%.*]] = xor <3 x i5> [[AND]], [[OR]]
-; CHECK-NEXT:    [[XOR:%.*]] = xor <3 x i5> [[TMP1]], <i5 -1, i5 -1, i5 -1>
+; CHECK-NEXT:    [[TMP1:%.*]] = xor <3 x i5> [[OR]], <i5 -1, i5 -1, i5 -1>
+; CHECK-NEXT:    [[XOR:%.*]] = or <3 x i5> [[AND]], [[TMP1]]
 ; CHECK-NEXT:    ret <3 x i5> [[XOR]]
 ;
   %or = or <3 x i5> %b, %c
   %and = and <3 x i5> %a, %c
   %not = xor <3 x i5> %and, <i5 -1, i5 -1, i5 -1>
   %xor = xor <3 x i5> %not, %or
   ret <3 x i5> %xor
 }
 
 define <3 x i5> @xor_notand_to_or_not_vector_poison(<3 x i5> %a, <3 x i5> %b, <3 x i5> %c) {
 ; CHECK-LABEL: @xor_notand_to_or_not_vector_poison(
 ; CHECK-NEXT:    [[OR:%.*]] = or <3 x i5> [[B:%.*]], [[C:%.*]]
 ; CHECK-NEXT:    [[AND:%.*]] = and <3 x i5> [[A:%.*]], [[C]]
-; CHECK-NEXT:    [[TMP1:%.*]] = xor <3 x i5> [[AND]], [[OR]]
-; CHECK-NEXT:    [[XOR:%.*]] = xor <3 x i5> [[TMP1]], <i5 -1, i5 poison, i5 -1>
+; CHECK-NEXT:    [[TMP1:%.*]] = xor <3 x i5> [[OR]], <i5 -1, i5 -1, i5 -1>
+; CHECK-NEXT:    [[XOR:%.*]] = or <3 x i5> [[AND]], [[TMP1]]
 ; CHECK-NEXT:    ret <3 x i5> [[XOR]]
 ;
   %or = or <3 x i5> %b, %c
   %and = and <3 x i5> %a, %c
   %not = xor <3 x i5> %and, <i5 -1, i5 poison, i5 -1>
   %xor = xor <3 x i5> %not, %or
   ret <3 x i5> %xor
 }
 
+; negative test : not one use
+
 define i3 @xor_notand_to_or_not_2use(i3 %a, i3 %b, i3 %c) {
 ; CHECK-LABEL: @xor_notand_to_or_not_2use(
 ; CHECK-NEXT:    [[OR:%.*]] = or i3 [[B:%.*]], [[C:%.*]]
 ; CHECK-NEXT:    [[AND:%.*]] = and i3 [[A:%.*]], [[C]]
 ; CHECK-NEXT:    [[NOT:%.*]] = xor i3 [[AND]], -1
 ; CHECK-NEXT:    [[XOR:%.*]] = xor i3 [[OR]], [[NOT]]
 ; CHECK-NEXT:    call void @use3(i3 [[NOT]])
 ; CHECK-NEXT:    ret i3 [[XOR]]