[InstCombine] Fold ((x?1:4)&(y?1:4))==0 to x^y

[marcauberer]

Summary

Fixes issue #57666: https://github.com/llvm/llvm-project/issues/57666

The optimization applies to all constant values that equal to zero when
applied to an bitwise and instruction.

Alive2: https://alive2.llvm.org/ce/z/RrVEyX
Minimalistic Godbolt example: https://godbolt.org/z/3d6h9z4de

[marcauberer]

Will execute clang-format later

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

6486

@spatel do you know how to check for shared bits between C and D the best. The current solution does not work.
Besides that, by feeding C and D with m_APInt to the match function, the vector test case does not work properly. We might need to fall back to m_Value, do we?

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

6486

Before making enhancements to generalize the fold, we have to make sure the transform is sound.

The Alive2 proof says that the select values must be non-zero, but that is not checked. We need more tests to verify that the matching is complete.

Once you're confident that the transform is correct for the basic pattern, look at how to make it handle other patterns:

1. Why are there one-use restrictions? Hint: if we're only creating 1 instruction, then we can never end up with more instructions than we started with.
2. Almost any fold that checks for "X == 0" alone can be generalized to handle "X != 0".
3. We don't need to capture all of the constants if we're looking for equivalent values; use m_Specific or m_Deferred for that. See m_ImmConstant() for a more general match than m_APInt().

[RKSimon]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

6486

You need to use m_Deferred to match later matches of C/D to their first occurrence.

Also, try to use llvm::haveNoCommonBitsSet/isKnownNonZero to match the general cases

[marcauberer]

Rebase

[marcauberer]

Consider more checks and icmp ne as well

[marcauberer]

Add negative tests

[marcauberer]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

6486

Seems like m_Deferred does work in combination with m_Value, but not with m_ImmConstant or m_Constant. Thus I went back to m_Value ...
I also added the variant for "X != 0" in addition to "X == 0" and extended the baseline tests accordingly.

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

6480

The formatting is off.

6481–6483

This shouldn't use the commutative matcher (m_c_And); it should be m_And() with m_Specific().
Ie, we match operand 0 of the 'and' as any select; then, we match operand 1 with constraints based on whatever was matched as operand 0.

6485

If we're using the more general ValueTracking API's, then there should be at least one test for each code path that uses non-constants to exercise that more expensive analysis.

This patch is getting bigger than I originally anticipated, so I'd be fine with making that a small follow-up patch, but see if @RKSimon agrees.

6488

xot -> not ?

6490–6492

It shouldn't matter whether the selects have other uses. We're creating 2 new instructions, so if the 'and' has only one use, then and+icmp will be deleted, and the transform doesn't increase instruction count.

[marcauberer]

Code improvements

[marcauberer]

As of tomorrow I am on vacation for about two weeks. I hope we can put this on hold until I am available again ...

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

6480

That is on purpose to maintain overwiew ...
Will format the change later on

6481–6483

Yes, indeed. Changed it.

[marcauberer]

Rebase and format

[marcauberer]

Rebase

[marcauberer]

Fix bug

[marcauberer]

Rebase

[marcauberer]

llvm/test/Transforms/InstCombine/select_and_icmpne.ll

42–43

That result might be confusing, but as you see on the original test result, the 'ugt' predicate gets transformed to 'ne' and then the transformation can take effect.

[RKSimon]

@marcauberer reverse ping - what's happening with this patch please?

[marcauberer]

Apply latest baseline test changes

[marcauberer]

Rebase

[RKSimon]

@marcauberer reverse-ping?

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

6489

It would reduce alot of duplicate code to handle ne with the eq code and just add the not if Pred == ICMP_NE.

Also probably should add alive2 link for this case too:
https://alive2.llvm.org/ce/z/NhgW3z

[spatel]

Basic support added with:
rG98855059674c
rGeb6f5f1ada6a

There are TODO comments in the code about extending the matching in a variety of ways.

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

if (Instruction *Res = foldVectorCmp(I, Builder))
       return Res;
 
   if (Instruction *Res = foldICmpInvariantGroup(I))
     return Res;
 
   if (Instruction *Res = foldReductionIdiom(I, Builder, DL))
     return Res;
 
+  {
+    Value *A, *B, *C, *D;
+
+    // Find hidden xor optimization (only if `C` and `D` have no common bits)
+    // (icmp eq (and (select A, C, D), (select B, C, D)), 0) --> (xor A, B)
+    if (I.getPredicate() == ICmpInst::ICMP_EQ &&
+        match(Op0, m_And(m_Select(m_Value(A), m_Value(C), m_Value(D)),
+                         m_Select(m_Value(B), m_Deferred(C), m_Deferred(D)))) &&
+        match(Op1, m_Zero()) &&
+        isKnownNonZero(C, DL, /*Depth*/ 0, &AC, &I, &DT) &&
+        isKnownNonZero(D, DL, /*Depth*/ 0, &AC, &I, &DT) &&
+        haveNoCommonBitsSet(C, D, DL, &AC, &I, &DT)) {
+      return BinaryOperator::CreateXor(A, B);
+    }
+    // (icmp ne (and (select A, C, D), (select B, C, D)), 0) --> (not (xor A,
+    // B), true)
+    if (I.getPredicate() == ICmpInst::ICMP_NE &&
+        match(Op0, m_OneUse(m_And(
+                       m_Select(m_Value(A), m_Value(C), m_Value(D)),
+                       m_Select(m_Value(B), m_Deferred(C), m_Deferred(D))))) &&
+        match(Op1, m_Zero()) &&
+        isKnownNonZero(C, DL, /*Depth*/ 0, &AC, &I, &DT) &&
+        isKnownNonZero(D, DL, /*Depth*/ 0, &AC, &I, &DT) &&
+        haveNoCommonBitsSet(C, D, DL, &AC, &I, &DT)) {
+      Value *Xor = Builder.CreateXor(A, B);
+      return BinaryOperator::CreateNeg(Xor);
+    }
+  }
+
   return Changed ? &I : nullptr;
 }
 
 /// Fold fcmp ([us]itofp x, cst) if possible.
 Instruction *InstCombinerImpl::foldFCmpIntToFPConst(FCmpInst &I,
                                                     Instruction *LHSI,
                                                     Constant *RHSC) {
   if (!isa<ConstantFP>(RHSC)) return nullptr;

llvm/test/Transforms/InstCombine/select_and_icmpeq.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -passes=instcombine -S | FileCheck %s
 
 define i1 @select_and_icmpeq_i32(i1 %x, i1 %y) {
 ; CHECK-LABEL: @select_and_icmpeq_i32(
-; CHECK-NEXT:    [[S1:%.*]] = select i1 [[X:%.*]], i32 2, i32 1
-; CHECK-NEXT:    [[S2:%.*]] = select i1 [[Y:%.*]], i32 2, i32 1
-; CHECK-NEXT:    [[AND:%.*]] = and i32 [[S1]], [[S2]]
-; CHECK-NEXT:    [[ICMP:%.*]] = icmp eq i32 [[AND]], 0
+; CHECK-NEXT:    [[ICMP:%.*]] = xor i1 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    ret i1 [[ICMP]]
 ;
   %s1 = select i1 %x, i32 2, i32 1
   %s2 = select i1 %y, i32 2, i32 1
   %and = and i32 %s1, %s2
   %icmp = icmp eq i32 %and, 0
   ret i1 %icmp
 }
 
 define i1 @select_and_icmpeq_i9(i1 %x, i1 %y) {
 ; CHECK-LABEL: @select_and_icmpeq_i9(
-; CHECK-NEXT:    [[S1:%.*]] = select i1 [[X:%.*]], i9 3, i9 16
-; CHECK-NEXT:    [[S2:%.*]] = select i1 [[Y:%.*]], i9 3, i9 16
-; CHECK-NEXT:    [[AND:%.*]] = and i9 [[S2]], [[S1]]
-; CHECK-NEXT:    [[ICMP:%.*]] = icmp eq i9 [[AND]], 0
+; CHECK-NEXT:    [[ICMP:%.*]] = xor i1 [[Y:%.*]], [[X:%.*]]
 ; CHECK-NEXT:    ret i1 [[ICMP]]
 ;
   %s1 = select i1 %x, i9 3, i9 16
   %s2 = select i1 %y, i9 3, i9 16
   %and = and i9 %s2, %s1
   %icmp = icmp eq i9 %and, 0
   ret i1 %icmp
 }
 
 define <5 x i1> @select_and_icmpeq_i1vec(<5 x i1> %x, <5 x i1> %y) {
 ; CHECK-LABEL: @select_and_icmpeq_i1vec(
-; CHECK-NEXT:    [[S1:%.*]] = select <5 x i1> [[X:%.*]], <5 x i32> <i32 7, i32 6, i32 5, i32 4, i32 3>, <5 x i32> <i32 8, i32 24, i32 16, i32 256, i32 192>
-; CHECK-NEXT:    [[S2:%.*]] = select <5 x i1> [[Y:%.*]], <5 x i32> <i32 7, i32 6, i32 5, i32 4, i32 3>, <5 x i32> <i32 8, i32 24, i32 16, i32 256, i32 192>
-; CHECK-NEXT:    [[AND:%.*]] = and <5 x i32> [[S2]], [[S1]]
-; CHECK-NEXT:    [[ICMP:%.*]] = icmp eq <5 x i32> [[AND]], zeroinitializer
+; CHECK-NEXT:    [[ICMP:%.*]] = xor <5 x i1> [[Y:%.*]], [[X:%.*]]
 ; CHECK-NEXT:    ret <5 x i1> [[ICMP]]
 ;
   %s1 = select <5 x i1> %x, <5 x i32> <i32 7, i32 6, i32 5, i32 4, i32 3>, <5 x i32> <i32 8, i32 24, i32 16, i32 256, i32 192>
   %s2 = select <5 x i1> %y, <5 x i32> <i32 7, i32 6, i32 5, i32 4, i32 3>, <5 x i32> <i32 8, i32 24, i32 16, i32 256, i32 192>
   %and = and <5 x i32> %s2, %s1
   %icmp = icmp eq <5 x i32> %and, <i32 0, i32 0, i32 0, i32 0, i32 0>
   ret <5 x i1> %icmp
 }

llvm/test/Transforms/InstCombine/select_and_icmpne.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -passes=instcombine -S | FileCheck %s
 
 define i1 @select_and_icmpne_i32(i1 %x, i1 %y) {
 ; CHECK-LABEL: @select_and_icmpne_i32(
-; CHECK-NEXT:    [[S1:%.*]] = select i1 [[X:%.*]], i32 2, i32 1
-; CHECK-NEXT:    [[S2:%.*]] = select i1 [[Y:%.*]], i32 2, i32 1
-; CHECK-NEXT:    [[AND:%.*]] = and i32 [[S1]], [[S2]]
-; CHECK-NEXT:    [[ICMP:%.*]] = icmp ne i32 [[AND]], 0
-; CHECK-NEXT:    ret i1 [[ICMP]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i1 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    ret i1 [[TMP1]]
 ;
   %s1 = select i1 %x, i32 2, i32 1
   %s2 = select i1 %y, i32 2, i32 1
   %and = and i32 %s1, %s2
   %icmp = icmp ne i32 %and, 0
   ret i1 %icmp
 }
 
 define i1 @select_and_icmpne_i9(i1 %x, i1 %y) {
 ; CHECK-LABEL: @select_and_icmpne_i9(
-; CHECK-NEXT:    [[S1:%.*]] = select i1 [[X:%.*]], i9 3, i9 16
-; CHECK-NEXT:    [[S2:%.*]] = select i1 [[Y:%.*]], i9 3, i9 16
-; CHECK-NEXT:    [[AND:%.*]] = and i9 [[S2]], [[S1]]
-; CHECK-NEXT:    [[ICMP:%.*]] = icmp ne i9 [[AND]], 0
-; CHECK-NEXT:    ret i1 [[ICMP]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i1 [[Y:%.*]], [[X:%.*]]
+; CHECK-NEXT:    ret i1 [[TMP1]]
 ;
   %s1 = select i1 %x, i9 3, i9 16
   %s2 = select i1 %y, i9 3, i9 16
   %and = and i9 %s2, %s1
   %icmp = icmp ne i9 %and, 0
   ret i1 %icmp
 }
 
 define <5 x i1> @select_and_icmpne_i1vec(<5 x i1> %x, <5 x i1> %y) {
 ; CHECK-LABEL: @select_and_icmpne_i1vec(
-; CHECK-NEXT:    [[S1:%.*]] = select <5 x i1> [[X:%.*]], <5 x i32> <i32 7, i32 6, i32 5, i32 4, i32 3>, <5 x i32> <i32 8, i32 24, i32 16, i32 256, i32 192>
-; CHECK-NEXT:    [[S2:%.*]] = select <5 x i1> [[Y:%.*]], <5 x i32> <i32 7, i32 6, i32 5, i32 4, i32 3>, <5 x i32> <i32 8, i32 24, i32 16, i32 256, i32 192>
-; CHECK-NEXT:    [[AND:%.*]] = and <5 x i32> [[S2]], [[S1]]
-; CHECK-NEXT:    [[ICMP:%.*]] = icmp ne <5 x i32> [[AND]], zeroinitializer
-; CHECK-NEXT:    ret <5 x i1> [[ICMP]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor <5 x i1> [[Y:%.*]], [[X:%.*]]
+; CHECK-NEXT:    ret <5 x i1> [[TMP1]]
 ;
   %s1 = select <5 x i1> %x, <5 x i32> <i32 7, i32 6, i32 5, i32 4, i32 3>, <5 x i32> <i32 8, i32 24, i32 16, i32 256, i32 192>
   %s2 = select <5 x i1> %y, <5 x i32> <i32 7, i32 6, i32 5, i32 4, i32 3>, <5 x i32> <i32 8, i32 24, i32 16, i32 256, i32 192>
   %and = and <5 x i32> %s2, %s1
   %icmp = icmp ne <5 x i32> %and, <i32 0, i32 0, i32 0, i32 0, i32 0>
   ret <5 x i1> %icmp
 }
 
 define i1 @select_and_icmpne_i8_negative_other_pred(i1 %x, i1 %y) {
 ; CHECK-LABEL: @select_and_icmpne_i8_negative_other_pred(
-; CHECK-NEXT:    [[S1:%.*]] = select i1 [[X:%.*]], i8 1, i8 8
-; CHECK-NEXT:    [[S2:%.*]] = select i1 [[Y:%.*]], i8 1, i8 8
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[S1]], [[S2]]
-; CHECK-NEXT:    [[ICMP:%.*]] = icmp ne i8 [[AND]], 0
-; CHECK-NEXT:    ret i1 [[ICMP]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i1 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    ret i1 [[TMP1]]
 ;
   %s1 = select i1 %x, i8 1, i8 8
   %s2 = select i1 %y, i8 1, i8 8
   %and = and i8 %s1, %s2
   %icmp = icmp ugt i8 %and, 0
   ret i1 %icmp
 }