[InstCombine] reduce icmp_eq0-of-and-of-select-of-constants

[spatel]

Summary

This is the most basic patch to handle fixing issue #57666.

D133919 proposes to handle much more than this in a single patch, but I've used 10 regression tests just to make sure this part is doing what I expected and nothing more, and it already shows even more potential TODO items.

The more general proofs from D133919 are correct, but we should enable this in smaller steps to reduce risk:
https://alive2.llvm.org/ce/z/RrVEyX

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

1901

Can this just be match(X, m_Select(m_Value(A), m_APInt(TC), m_APInt(FC)) and the m_SpecificInt in the match on Y?

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

1901

Sure - I was actually backtracking from the more general patch in this version, but I can adjust that to be the more direct matcher.

[spatel]

Patch updated: use the more direct m_SpecificInt matchers (expected to generalize that in follow-up patches).

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

1898

Is the plan to handle the ICMP_NE case in another patch?

1898

Is the plan to handle the ICMP_NE case in another patch?

Ignore, see TODO.

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

1896

You could also match other predicates i.e ((x?1:4)&(y?1:4))<2

Also it seems we already have some logic for match some other predicates in this case (although I can't find it):
https://godbolt.org/z/hjzMGKqKz

although it seems to have an off by-1 issue (see ugt and ugt3)

[goldstein.w.n]

LGTM (although I'm not a maintainer so may want to find a bit at least for someone more familiar to checkoff).

[spatel]

In D142847#4091133, @goldstein.w.n wrote:

LGTM (although I'm not a maintainer so may want to find a bit at least for someone more familiar to checkoff).

Thanks! This has been under development in D133919 for a while, so I feel good about it. Stamping out all of the tests for the planned enhancements is the larger effort at this point.

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

1896

From what I see in the debug spew, some of those examples reduce via demanded bits - we shrink a select constant because some bit(s) is/are irrelevant given the compare constants. That leads to further folding via FoldOpIntoSelect or some other transform.

But there's no general transform along these lines that I see. Ie, if we choose some other arbitrary set of constants in the tests, it may or may not fold.

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

1896

From what I see in the debug spew, some of those examples reduce via demanded bits - we shrink a select constant because some bit(s) is/are irrelevant given the compare constants. That leads to further folding via FoldOpIntoSelect or some other transform.

But there's no general transform along these lines that I see. Ie, if we choose some other arbitrary set of constants in the tests, it may or may not fold.

I see, then I would definetly add as a TODO to handle "other predicates" instead of just "ne".

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

Instruction *InstCombinerImpl::foldICmpAndConstant(ICmpInst &Cmp,
   // X & -C != -C -> X <= u ~C
   //   iff C is a power of 2
   if (Cmp.getOperand(1) == Y && C.isNegatedPowerOf2()) {
     auto NewPred =
         Pred == CmpInst::ICMP_EQ ? CmpInst::ICMP_UGT : CmpInst::ICMP_ULE;
     return new ICmpInst(NewPred, X, SubOne(cast<Constant>(Cmp.getOperand(1))));
   }
 
+  // If we are testing the intersection of 2 select-of-nonzero-constants with no
+  // common bits set, it's the same as checking if exactly one select condition
+  // is set:
+  // ((A ? TC : FC) & (B ? TC : FC)) == 0 --> xor A, B
+  // TODO: Generalize for non-constant values.
+  // TODO: Invert with a "ne" predicate.
+  // TODO: Handle signed/unsigned predicates.
+  // TODO: Handle other bitwise logic connectors.
+  // TODO: Extend to handle a non-zero compare constant.
+  if (Pred == CmpInst::ICMP_EQ && C.isZero()) {
+    Value *A, *B;
+    const APInt *TC, *FC;
+    if (match(X, m_Select(m_Value(A), m_APInt(TC), m_APInt(FC))) &&
+        match(Y,
+              m_Select(m_Value(B), m_SpecificInt(*TC), m_SpecificInt(*FC))) &&
+        !TC->isZero() && !FC->isZero() && !TC->intersects(*FC))
+      return BinaryOperator::CreateXor(A, B);
+  }
+
   // ((zext i1 X) & Y) == 0 --> !((trunc Y) & X)
   // ((zext i1 X) & Y) != 0 -->  ((trunc Y) & X)
   // ((zext i1 X) & Y) == 1 -->  ((trunc Y) & X)
   // ((zext i1 X) & Y) != 1 --> !((trunc Y) & X)
   if (match(And, m_OneUse(m_c_And(m_OneUse(m_ZExt(m_Value(X))), m_Value(Y)))) &&
       X->getType()->isIntOrIntVectorTy(1) && (C.isZero() || C.isOne())) {
     Value *TruncY = Builder.CreateTrunc(Y, X->getType());
     if (C.isZero() ^ (Pred == CmpInst::ICMP_NE)) {

llvm/test/Transforms/InstCombine/icmp-select.ll

;
   %cmp1 = icmp eq i8 %x, 0
   %sel = select i1 %cmp1, i8 0, i8 %min
   %cmp2 = icmp eq i8 %sel, %x
   ret i1 %cmp2
 }
 
 define i1 @select_constants_and_icmp_eq0(i1 %x, i1 %y) {
 ; CHECK-LABEL: @select_constants_and_icmp_eq0(
-; CHECK-NEXT:    [[S1:%.*]] = select i1 [[X:%.*]], i8 2, i8 1
-; CHECK-NEXT:    [[S2:%.*]] = select i1 [[Y:%.*]], i8 2, i8 1
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[S1]], [[S2]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[AND]], 0
+; CHECK-NEXT:    [[CMP:%.*]] = xor i1 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %s1 = select i1 %x, i8 2, i8 1
   %s2 = select i1 %y, i8 2, i8 1
   %and = and i8 %s1, %s2
   %cmp = icmp eq i8 %and, 0
   ret i1 %cmp
 }
 
+; extra uses on all intermediates are ok
+
 define i1 @select_constants_and_icmp_eq0_uses(i1 %x, i1 %y) {
 ; CHECK-LABEL: @select_constants_and_icmp_eq0_uses(
 ; CHECK-NEXT:    [[S1:%.*]] = select i1 [[X:%.*]], i8 2, i8 1
 ; CHECK-NEXT:    call void @use(i8 [[S1]])
 ; CHECK-NEXT:    [[S2:%.*]] = select i1 [[Y:%.*]], i8 2, i8 1
 ; CHECK-NEXT:    call void @use(i8 [[S2]])
 ; CHECK-NEXT:    [[AND:%.*]] = and i8 [[S1]], [[S2]]
 ; CHECK-NEXT:    call void @use(i8 [[AND]])
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[AND]], 0
+; CHECK-NEXT:    [[CMP:%.*]] = xor i1 [[X]], [[Y]]
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %s1 = select i1 %x, i8 2, i8 1
   call void @use(i8 %s1)
   %s2 = select i1 %y, i8 2, i8 1
   call void @use(i8 %s2)
   %and = and i8 %s1, %s2
   call void @use(i8 %and)
   %cmp = icmp eq i8 %and, 0
   ret i1 %cmp
 }
 
+; vector splat constants are ok
+
 define <2 x i1> @select_constants_and_icmp_eq0_vec_splat(<2 x i1> %x, <2 x i1> %y) {
 ; CHECK-LABEL: @select_constants_and_icmp_eq0_vec_splat(
-; CHECK-NEXT:    [[S1:%.*]] = select <2 x i1> [[X:%.*]], <2 x i9> <i9 3, i9 3>, <2 x i9> <i9 48, i9 48>
-; CHECK-NEXT:    [[S2:%.*]] = select <2 x i1> [[Y:%.*]], <2 x i9> <i9 3, i9 3>, <2 x i9> <i9 48, i9 48>
-; CHECK-NEXT:    [[AND:%.*]] = and <2 x i9> [[S1]], [[S2]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq <2 x i9> [[AND]], zeroinitializer
+; CHECK-NEXT:    [[CMP:%.*]] = xor <2 x i1> [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    ret <2 x i1> [[CMP]]
 ;
   %s1 = select <2 x i1> %x, <2 x i9> <i9 3, i9 3>, <2 x i9> <i9 48, i9 48>
   %s2 = select <2 x i1> %y, <2 x i9> <i9 3, i9 3>, <2 x i9> <i9 48, i9 48>
   %and = and <2 x i9> %s1, %s2
   %cmp = icmp eq <2 x i9> %and, zeroinitializer
   ret <2 x i1> %cmp
 }
 
+; common bit set - simplified via known bits
+
 define i1 @select_constants_and_icmp_eq0_common_bit(i1 %x, i1 %y) {
 ; CHECK-LABEL: @select_constants_and_icmp_eq0_common_bit(
 ; CHECK-NEXT:    ret i1 false
 ;
   %s1 = select i1 %x, i8 2, i8 3
   %s2 = select i1 %y, i8 2, i8 3
   %and = and i8 %s1, %s2
   %cmp = icmp eq i8 %and, 0
   ret i1 %cmp
 }
 
+; negative test - need matching constants
+
 define i1 @select_constants_and_icmp_eq0_no_common_op1(i1 %x, i1 %y) {
 ; CHECK-LABEL: @select_constants_and_icmp_eq0_no_common_op1(
 ; CHECK-NEXT:    [[S1:%.*]] = select i1 [[X:%.*]], i8 16, i8 3
 ; CHECK-NEXT:    [[S2:%.*]] = select i1 [[Y:%.*]], i8 24, i8 3
 ; CHECK-NEXT:    [[AND:%.*]] = and i8 [[S1]], [[S2]]
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[AND]], 0
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %s1 = select i1 %x, i8 16, i8 3
   %s2 = select i1 %y, i8 24, i8 3
   %and = and i8 %s1, %s2
   %cmp = icmp eq i8 %and, 0
   ret i1 %cmp
 }
 
+; negative test - need matching constants
+
 define i1 @select_constants_and_icmp_eq0_no_common_op2(i1 %x, i1 %y) {
 ; CHECK-LABEL: @select_constants_and_icmp_eq0_no_common_op2(
 ; CHECK-NEXT:    [[S1:%.*]] = select i1 [[X:%.*]], i8 16, i8 3
 ; CHECK-NEXT:    [[S2:%.*]] = select i1 [[Y:%.*]], i8 16, i8 7
 ; CHECK-NEXT:    [[AND:%.*]] = and i8 [[S1]], [[S2]]
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[AND]], 0
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %s1 = select i1 %x, i8 16, i8 3
   %s2 = select i1 %y, i8 16, i8 7
   %and = and i8 %s1, %s2
   %cmp = icmp eq i8 %and, 0
   ret i1 %cmp
 }
 
+; reduces via FoldOpInstSelect, but this could be a simple 'or'
+
 define i1 @select_constants_and_icmp_eq0_zero_tval(i1 %x, i1 %y) {
 ; CHECK-LABEL: @select_constants_and_icmp_eq0_zero_tval(
 ; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[X:%.*]], i1 true, i1 [[Y:%.*]]
 ; CHECK-NEXT:    ret i1 [[TMP1]]
 ;
   %s1 = select i1 %x, i8 0, i8 12
   %s2 = select i1 %y, i8 0, i8 12
   %and = and i8 %s1, %s2
   %cmp = icmp eq i8 %and, 0
   ret i1 %cmp
 }
 
+; reduces via FoldOpInstSelect, but this could be a simple 'not-of-and'
+
 define i1 @select_constants_and_icmp_eq0_zero_fval(i1 %x, i1 %y) {
 ; CHECK-LABEL: @select_constants_and_icmp_eq0_zero_fval(
 ; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[X:%.*]], i1 [[Y:%.*]], i1 false
 ; CHECK-NEXT:    [[NOT_:%.*]] = xor i1 [[TMP1]], true
 ; CHECK-NEXT:    ret i1 [[NOT_]]
 ;
   %s1 = select i1 %x, i8 12, i8 0
   %s2 = select i1 %y, i8 12, i8 0
   %and = and i8 %s1, %s2
   %cmp = icmp eq i8 %and, 0
   ret i1 %cmp
 }
 
+; TODO: x & y
+
 define i1 @select_constants_and_icmp_eq_tval(i1 %x, i1 %y) {
 ; CHECK-LABEL: @select_constants_and_icmp_eq_tval(
 ; CHECK-NEXT:    [[S1:%.*]] = select i1 [[X:%.*]], i8 6, i8 1
 ; CHECK-NEXT:    [[S2:%.*]] = select i1 [[Y:%.*]], i8 6, i8 1
 ; CHECK-NEXT:    [[AND:%.*]] = and i8 [[S1]], [[S2]]
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[AND]], 6
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %s1 = select i1 %x, i8 6, i8 1
   %s2 = select i1 %y, i8 6, i8 1
   %and = and i8 %s1, %s2
   %cmp = icmp eq i8 %and, 6
   ret i1 %cmp
 }
 
+; TODO: ~(x | y)
+
 define i1 @select_constants_and_icmp_eq_fval(i1 %x, i1 %y) {
 ; CHECK-LABEL: @select_constants_and_icmp_eq_fval(
 ; CHECK-NEXT:    [[S1:%.*]] = select i1 [[X:%.*]], i8 12, i8 3
 ; CHECK-NEXT:    [[S2:%.*]] = select i1 [[Y:%.*]], i8 12, i8 3
 ; CHECK-NEXT:    [[AND:%.*]] = and i8 [[S1]], [[S2]]
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[AND]], 3
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %s1 = select i1 %x, i8 12, i8 3
   %s2 = select i1 %y, i8 12, i8 3
   %and = and i8 %s1, %s2
   %cmp = icmp eq i8 %and, 3
   ret i1 %cmp
 }