[InstCombine] Apply deMorgan to (and/or (not cmp1), cmp2) when cmp1 has multiple uses, but cmp2 has a single use

[craig.topper]

Summary

This patch applies demorgan when we detect an icmp of 2 cmps where one cmp is inverted, but the not can't be folded into the predicate because the cmp has another usage. If we are able to fold a not into the other cmp, we can do the transform and hope the remaining not can be folded away further up the chain. And even if its not folded away, we haven't increased the number of operations.

I plan to add more test cases in the InstCombine directory before committing this, but wanted to get an opinion on whether it makes sense.

Interestingly, the one test that changed here is for the transformation that caused the extra xors in my test case too.

[spatel]

The transform seems reasonable, but I wonder if we can pull more of the code for DeMorgan folds together. Maybe this can be added to matchDeMorgansLaws? Also, I'm trying to clean up the block in D32665. Below that, we use "IsFreeToInvert" and that does have a param to account for multi-use cases. Could/should we use IsFreeToInvert instead of writing a special match for this case?

As you said, it would be great to have the tests for various cases under test/Transforms/InstCombine, so we'll know what happens in those cases. I suspect we have a lot of transforms where we're either stopping short because of !hasOneUse() or overstepping because that condition is missing.

[efriedma]

I'm not quite sure about this the way it's written. This doesn't reduce the total number of instructions on its own, and it seems like an overly complicated pattern. You could approach this from a different angle: fold xor(icmp(pred, x, y)) to (icmp (!pred, x, y)) even if the inner icmp has multiple uses. Or maybe this is okay as-is; my intuition about what's right here isn't strong.

[craig.topper]

I guess my thought was that even if we were unable to get rid of the not later, an extra not was slightly preferable to creating a new compare instruction.

[spatel]

In D32725#743679, @efriedma wrote:

I'm not quite sure about this the way it's written. This doesn't reduce the total number of instructions on its own, and it seems like an overly complicated pattern. You could approach this from a different angle: fold xor(icmp(pred, x, y)) to (icmp (!pred, x, y)) even if the inner icmp has multiple uses. Or maybe this is okay as-is; my intuition about what's right here isn't strong.

I think that folding to icmp with inverse predicate (regardless of number of uses) is the right thing to do because it eliminates a dependency between icmp and xor (not). Plus, we have tons of folds/analysis for icmp.

In other words, we should get rid of the m_OneUse here:

// xor (cmp A, B), true = not (cmp A, B) = !cmp A, B
ICmpInst::Predicate Pred;
if (match(Op0, m_OneUse(m_Cmp(Pred, m_Value(), m_Value()))) &&

There was at least one missing fold exposed by this change in a regression test when I checked it previously.

[craig.topper]

should we also lift the one use check for compares in IsFreeToInvert?

What about floating point compares? We probably don't have as many folds for them.

[spatel]

In D32725#744881, @craig.topper wrote:

should we also lift the one use check for compares in IsFreeToInvert?

Yes, I think that makes sense. @efriedma - do you foresee problems?
I forgot that I already filed this bug that will result if we lift the one-use restriction for // xor (cmp A, B), true = not (cmp A, B) = !cmp A, B :
https://bugs.llvm.org/show_bug.cgi?id=32791

What about floating point compares? We probably don't have as many folds for them.

IMO, it's just a bonus that we have lots of icmp folds. The main reason we should not care about uses for these folds is that we always reduce the dependency chain by inverting the predicate. If we're missing folds based on inverted predicates, we can add those (and might need to do that first to avoid regressions). If either icmp or fcmp is less efficient than 'not' for some target, then it can invert this in the backend.

Examples:

declare void @bar(i1, i1)

define void @icmp_neg(i8 %a) {
  %cmp = icmp eq i8 %a, 1
  %neg = xor i1 %cmp, -1  <--- must wait for cmp
  call void @bar(i1 %cmp, i1 %neg)
  ret void
}

define void @icmp_inv(i8 %a) {
  %cmp = icmp eq i8 %a, 1
  %neg = icmp ne i8 %a, 1    <--- can execute immediately
  call void @bar(i1 %cmp, i1 %neg)
  ret void
}

define void @fcmp_neg(float %a) {
  %cmp = fcmp oeq float %a, 1.0
  %neg = xor i1 %cmp, -1
  call void @bar(i1 %cmp, i1 %neg)
  ret void
}

define void @fcmp_inv(float %a) {
  %cmp = fcmp oeq float %a, 1.0
  %neg = fcmp une float %a, 1.0
  call void @bar(i1 %cmp, i1 %neg)
  ret void
}

[spatel]

I forgot that I already filed this bug that will result if we lift the one-use restriction for // xor (cmp A, B), true = not (cmp A, B) = !cmp A, B :
https://bugs.llvm.org/show_bug.cgi?id=32791

The opposite transform was suggested in:
https://bugs.llvm.org/show_bug.cgi?id=27431
Ie, turning an inverted predicate into a 'not' op might already be a recognized pattern by other passes.

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

Instruction *InstCombiner::visitAnd(BinaryOperator &I) {
   }
 
   // If and'ing two fcmp, try combine them into one.
   if (FCmpInst *LHS = dyn_cast<FCmpInst>(I.getOperand(0)))
     if (FCmpInst *RHS = dyn_cast<FCmpInst>(I.getOperand(1)))
       if (Value *Res = FoldAndOfFCmps(LHS, RHS))
         return replaceInstUsesWith(I, Res);
 
+  // Fold (and (not cmp1), cmp2) -> (not (or cmp1, (not cmp2)))
+  // If cmp1 has multiple uses that prevent the not from folding, but cmp2
+  // can absorb the not.
+  {
+    ICmpInst::Predicate Pred;
+    Value *A;
+    if (match(Op0, m_OneUse(m_Cmp(Pred, m_Value(), m_Value()))) &&
+        match(Op1, m_OneUse(m_Not(m_Value(A))))) {
+      if (match(A, m_Cmp()) && !A->hasOneUse()) {
+        cast<CmpInst>(Op0)->setPredicate(CmpInst::getInversePredicate(Pred));
+        return BinaryOperator::CreateNot(Builder->CreateOr(Op0, A));
+      }
+    }
+
+    if (match(Op1, m_OneUse(m_Cmp(Pred, m_Value(), m_Value()))) &&
+        match(Op0, m_OneUse(m_Not(m_Value(A))))) {
+      if (match(A, m_Cmp()) && !A->hasOneUse()) {
+        cast<CmpInst>(Op1)->setPredicate(CmpInst::getInversePredicate(Pred));
+        return BinaryOperator::CreateNot(Builder->CreateOr(A, Op1));
+      }
+    }
+  }
+
   if (Instruction *CastedAnd = foldCastedBitwiseLogic(I))
     return CastedAnd;
 
   if (Instruction *Select = foldBoolSextMaskToSelect(I))
     return Select;
 
   return Changed ? &I : nullptr;
 }
Instruction *InstCombiner::visitOr(BinaryOperator &I) {
   }
 
   // (fcmp uno x, c) | (fcmp uno y, c)  -> (fcmp uno x, y)
   if (FCmpInst *LHS = dyn_cast<FCmpInst>(I.getOperand(0)))
     if (FCmpInst *RHS = dyn_cast<FCmpInst>(I.getOperand(1)))
       if (Value *Res = FoldOrOfFCmps(LHS, RHS))
         return replaceInstUsesWith(I, Res);
 
+  // Fold (or (not cmp1), cmp2) -> (not (and cmp1, (not cmp2)))
+  // If cmp1 has multiple uses that prevent the not from folding, but cmp2
+  // can absorb the not.
+  {
+    ICmpInst::Predicate Pred;
+    Value *A;
+    if (match(Op0, m_OneUse(m_Cmp(Pred, m_Value(), m_Value()))) &&
+        match(Op1, m_OneUse(m_Not(m_Value(A))))) {
+      if (match(A, m_Cmp()) && !A->hasOneUse()) {
+        cast<CmpInst>(Op0)->setPredicate(CmpInst::getInversePredicate(Pred));
+        return BinaryOperator::CreateNot(Builder->CreateAnd(Op0, A));
+      }
+    }
+
+    if (match(Op1, m_OneUse(m_Cmp(Pred, m_Value(), m_Value()))) &&
+        match(Op0, m_OneUse(m_Not(m_Value(A))))) {
+      if (match(A, m_Cmp()) && !A->hasOneUse()) {
+        cast<CmpInst>(Op1)->setPredicate(CmpInst::getInversePredicate(Pred));
+        return BinaryOperator::CreateNot(Builder->CreateAnd(A, Op1));
+      }
+    }
+  }
+
   if (Instruction *CastedOr = foldCastedBitwiseLogic(I))
     return CastedOr;
 
   // or(sext(A), B) / or(B, sext(A)) --> A ? -1 : B, where A is i1 or <N x i1>.
   if (match(Op0, m_OneUse(m_SExt(m_Value(A)))) &&
       A->getType()->getScalarType()->isIntegerTy(1))
     return SelectInst::Create(A, ConstantInt::getSigned(I.getType(), -1), Op1);
   if (match(Op1, m_OneUse(m_SExt(m_Value(A)))) &&

test/Transforms/SimplifyCFG/merge-cond-stores.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -simplifycfg -instcombine < %s -simplifycfg-merge-cond-stores=true -simplifycfg-merge-cond-stores-aggressively=false -phi-node-folding-threshold=2 -S | FileCheck %s
 
 ; This test should succeed and end up if-converted.
 define void @test_simple(i32* %p, i32 %a, i32 %b) {
 ; CHECK-LABEL: @test_simple(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[TMP0:%.*]] = icmp ne i32 [[A:%.*]], 0
-; CHECK-NEXT:    [[X2:%.*]] = icmp eq i32 [[B:%.*]], 0
-; CHECK-NEXT:    [[TMP1:%.*]] = xor i1 [[X2]], true
-; CHECK-NEXT:    [[TMP2:%.*]] = or i1 [[TMP0]], [[TMP1]]
-; CHECK-NEXT:    br i1 [[TMP2]], label [[TMP3:%.*]], label [[TMP4:%.*]]
-; CHECK:         [[NOT_X2:%.*]] = xor i1 [[X2]], true
-; CHECK-NEXT:    [[DOT:%.*]] = zext i1 [[NOT_X2]] to i32
+; CHECK-NEXT:    [[TMP0:%.*]] = or i32 [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i32 [[TMP0]], 0
+; CHECK-NEXT:    br i1 [[TMP1]], label [[TMP3:%.*]], label [[TMP2:%.*]]
+; CHECK:         [[X2:%.*]] = icmp ne i32 [[B]], 0
+; CHECK-NEXT:    [[DOT:%.*]] = zext i1 [[X2]] to i32
 ; CHECK-NEXT:    store i32 [[DOT]], i32* [[P:%.*]], align 4
-; CHECK-NEXT:    br label [[TMP4]]
+; CHECK-NEXT:    br label [[TMP3]]
 ; CHECK:         ret void
 ;
 entry:
   %x1 = icmp eq i32 %a, 0
   br i1 %x1, label %fallthrough, label %yes1
 
 yes1:
   store i32 0, i32* %p

 end:
   ret void
 }
 
 ; This test should entirely fold away, leaving one large basic block.
 define void @test_recursive(i32* %p, i32 %a, i32 %b, i32 %c, i32 %d) {
 ; CHECK-LABEL: @test_recursive(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[TMP0:%.*]] = or i32 [[B:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[X4:%.*]] = icmp eq i32 [[D:%.*]], 0
+; CHECK-NEXT:    [[TMP0:%.*]] = or i32 [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    [[TMP1:%.*]] = or i32 [[TMP0]], [[C:%.*]]
-; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne i32 [[TMP1]], 0
-; CHECK-NEXT:    [[TMP2:%.*]] = xor i1 [[X4]], true
-; CHECK-NEXT:    [[TMP4:%.*]] = or i1 [[TMP3]], [[TMP2]]
-; CHECK-NEXT:    br i1 [[TMP4]], label [[TMP5:%.*]], label [[TMP6:%.*]]
-; CHECK:         [[X3:%.*]] = icmp eq i32 [[C]], 0
-; CHECK-NEXT:    [[NOT_X2:%.*]] = icmp ne i32 [[B]], 0
-; CHECK-NEXT:    [[DOT:%.*]] = zext i1 [[NOT_X2]] to i32
+; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[D:%.*]]
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq i32 [[TMP2]], 0
+; CHECK-NEXT:    br i1 [[TMP3]], label [[TMP5:%.*]], label [[TMP4:%.*]]
+; CHECK:         [[X4:%.*]] = icmp eq i32 [[D]], 0
+; CHECK-NEXT:    [[X3:%.*]] = icmp eq i32 [[C]], 0
+; CHECK-NEXT:    [[X2:%.*]] = icmp ne i32 [[B]], 0
+; CHECK-NEXT:    [[DOT:%.*]] = zext i1 [[X2]] to i32
 ; CHECK-NEXT:    [[DOT_:%.*]] = select i1 [[X3]], i32 [[DOT]], i32 2
 ; CHECK-NEXT:    [[DOT__:%.*]] = select i1 [[X4]], i32 [[DOT_]], i32 3
 ; CHECK-NEXT:    store i32 [[DOT__]], i32* [[P:%.*]], align 4
-; CHECK-NEXT:    br label [[TMP6]]
+; CHECK-NEXT:    br label [[TMP5]]
 ; CHECK:         ret void
 ;
 entry:
   %x1 = icmp eq i32 %a, 0
   br i1 %x1, label %fallthrough, label %yes1
 
 yes1:
   store i32 0, i32* %p