InstCombine: match De Morgan's Law hidden by zext ops (PR22723)

[spatel]

Summary

This is a fix for PR22723:
https://llvm.org/bugs/show_bug.cgi?id=22723

My first attempt at this was to change what I thought was the root problem:

xor (zext i1 X to i32), 1 --> zext (xor i1 X, true) to i32

...but we create the opposite pattern in InstCombiner::visitZExt(), so infinite loop!

My next idea was to fix the matchIfNot() implementation in PatternMatch, but that would mean potentially returning a different size for the match than what was input. I think this would require all users of m_Not to check the size of the returned match, so I abandoned that idea.

I settled on just fixing the exact case presented in the PR. I hope this limited patch is acceptable if not the most general. It does allow the 2 functions in PR22723 to compile identically (x86):

bool test(bool x, bool y) { return !x | !y; }
bool test(bool x, bool y) { return !x || !y; }
...
andb	%sil, %dil
xorb	$1, %dil
movb	%dil, %al
retq

[spatel]

Ping.

[spatel]

Ping * 2.

[sanjoy]

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1240

Do you need to check if C1 fits in an uint64_t? Or is that checked earlier?

Actually, I think it'll be easier to just use C1->isOne().

[spatel]

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1240

Ah - I didn't know about that function. Fixed.

[spatel]

Patch updated to use 'isOne()'.

[hfinkel]

test/Transforms/InstCombine/demorgan-zext.ll

14–16

Please check here (and below) for the correct operands to these operations.

[spatel]

Patch updated: check operands in tests.

[hfinkel]

LGTM.

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

 /// Match De Morgan's Laws:
 /// (~A & ~B) == (~(A | B))
 /// (~A | ~B) == (~(A & B))
 static Instruction *matchDeMorgansLaws(BinaryOperator &I,
                                        InstCombiner::BuilderTy *Builder) {
   auto Opcode = I.getOpcode();
   assert((Opcode == Instruction::And || Opcode == Instruction::Or) &&
          "Trying to match De Morgan's Laws with something other than and/or");
+  // Flip the logic operation.
+  if (Opcode == Instruction::And)
+    Opcode = Instruction::Or;
+  else
+    Opcode = Instruction::And;
 
   Value *Op0 = I.getOperand(0);
   Value *Op1 = I.getOperand(1);
   // TODO: Use pattern matchers instead of dyn_cast.
   if (Value *Op0NotVal = dyn_castNotVal(Op0))
     if (Value *Op1NotVal = dyn_castNotVal(Op1))
       if (Op0->hasOneUse() && Op1->hasOneUse()) {
-        // Flip the logic operation.
-        if (Opcode == Instruction::And)
-          Opcode = Instruction::Or;
-        else
-          Opcode = Instruction::And;
         Value *LogicOp = Builder->CreateBinOp(Opcode, Op0NotVal, Op1NotVal,
                                               I.getName() + ".demorgan");
         return BinaryOperator::CreateNot(LogicOp);
       }
 
+  // De Morgan's Law in disguise:
+  // (zext(bool A) ^ 1) & (zext(bool B) ^ 1) -> zext(~(A | B))
+  // (zext(bool A) ^ 1) | (zext(bool B) ^ 1) -> zext(~(A & B))
+  Value *A = nullptr;
+  Value *B = nullptr;
+  ConstantInt *C1 = nullptr;
+  if (match(Op0, m_OneUse(m_Xor(m_ZExt(m_Value(A)), m_ConstantInt(C1)))) &&
+      match(Op1, m_OneUse(m_Xor(m_ZExt(m_Value(B)), m_Specific(C1))))) {
+    // TODO: This check could be loosened to handle different type sizes.
+    // Alternatively, we could fix the definition of m_Not to recognize a not
+    // operation hidden by a zext?
+    if (A->getType()->isIntegerTy(1) && B->getType()->isIntegerTy(1) &&
+        C1->getZExtValue() == 1) {
+      Value *LogicOp = Builder->CreateBinOp(Opcode, A, B,
+                                            I.getName() + ".demorgan");
+      Value *Not = Builder->CreateNot(LogicOp);
+      return CastInst::CreateZExtOrBitCast(Not, I.getType());
+    }
+  }
+
   return nullptr;
 }
 
 Instruction *InstCombiner::visitAnd(BinaryOperator &I) {
   bool Changed = SimplifyAssociativeOrCommutative(I);
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 
   if (Value *V = SimplifyVectorOp(I))

test/Transforms/InstCombine/demorgan-zext.ll

 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 ; PR22723: Recognize De Morgan's Laws when obfuscated by zexts.
 
 define i32 @demorgan_or(i1 %X, i1 %Y) {
   %zextX = zext i1 %X to i32
   %zextY = zext i1 %Y to i32
   %notX  = xor i32 %zextX, 1
   %notY  = xor i32 %zextY, 1
   %or    = or i32 %notX, %notY
   ret i32 %or
 
 ; CHECK-LABEL: demorgan_or(
-; CHECK-NEXT:  = zext
-; CHECK-NEXT:  = zext
-; CHECK-NEXT:  = xor
-; CHECK-NEXT:  = xor
-; CHECK-NEXT:  = or
+; CHECK-NEXT:  = and
+; CHECK-DAG:   = xor
+; CHECK-DAG:   = zext
 ; CHECK-NEXT:  ret
 }
 
 define i32 @demorgan_and(i1 %X, i1 %Y) {
   %zextX = zext i1 %X to i32
   %zextY = zext i1 %Y to i32
   %notX  = xor i32 %zextX, 1
   %notY  = xor i32 %zextY, 1
   %and   = and i32 %notX, %notY
   ret i32 %and
 
 ; CHECK-LABEL: demorgan_and(
-; CHECK-NEXT:  = zext
-; CHECK-NEXT:  = zext
-; CHECK-NEXT:  = xor
-; CHECK-NEXT:  = xor
-; CHECK-NEXT:  = and
+; CHECK-NEXT:  = or
+; CHECK-DAG:   = xor
+; CHECK-DAG:   = zext
 ; CHECK-NEXT:  ret
 }