[X86] Transform `(icmp eq/ne Abs(A), Pow2)` -> `(and/or (icmp eq/ne A,Pow2), (icmp eq/ne A,-Pow2))`

[goldstein.w.n]

Summary

Only if Abs(A) has one use, in which case the `(and/or (icmp eq/ne
A,Pow2), (icmp eq/ne A,-Pow2))` can be optimized in
DAGCombiner::foldAndOrOfSETCC.

Alive Links:
EQ: https://alive2.llvm.org/ce/z/gTxSgV
NE: https://alive2.llvm.org/ce/z/MUf57Y

[RKSimon]

llvm/lib/Target/X86/X86ISelLowering.cpp

53394

const APInt &CInt

[goldstein.w.n]

Use reference

[RKSimon]

Please can you add alive links?

llvm/lib/Target/X86/X86ISelLowering.cpp

53410

Add comment explaining the fold:

// Fold (icmp eq/ne Abs(A), Pow2)
//  --> (or/and (icmp eq/ne A,Pow2), (icmp eq/ne A,-Pow2))

53414

APInt::isPowerOf2() shouldn't require a isZero check?

[goldstein.w.n]

Comment better + remove redundant iszero check

[goldstein.w.n]

llvm/lib/Target/X86/X86ISelLowering.cpp

53414

APInt::isPowerOf2() shouldn't require a isZero check?

Is redundant, updated D142344 aswell.

[goldstein.w.n]

Rebase

[pengfei]

llvm/lib/Target/X86/X86ISelLowering.cpp

53411

Seems for 0 and INT_MIN, we can simply transform to icmp eq/ne A, C. Should we do it together given we already got the constant, or a follow?

[goldstein.w.n]

llvm/lib/Target/X86/X86ISelLowering.cpp

53411

We can although I don't that that IR ever really reaches the backend as the middle-end would clean up that pattern.
My thought it strange IR shouldn't cause broken transforms, but its fine for it to cause missed optimizations.

Although can add those two cases if you'd like, dont really have strong opinions on the matter.

[nikic]

llvm/lib/Target/X86/X86ISelLowering.cpp

53411

The general rule of thumb is that DAGCombiner should only copy IR folds if the pattern appears as a result of legalization of canonical IR.

[goldstein.w.n]

llvm/lib/Target/X86/X86ISelLowering.cpp

53411

The general rule of thumb is that DAGCombiner should only copy IR folds if the pattern appears as a result of legalization of canonical IR.

@pengfei made: D142666 but agree with nikic its probably unnecessary. Didn't see any test changes and don't know of any cases where it would reasonably appear.

[goldstein.w.n]

llvm/lib/Target/X86/X86ISelLowering.cpp

53411

The general rule of thumb is that DAGCombiner should only copy IR folds if the pattern appears as a result of legalization of canonical IR.

@nikic do you think InstCombine should cannocicalize (or/and (icmp eq/ne X, C), (icmp eq/ne X, -C)) <--> (icmp eq/ne ABS(X), ABS(C))? I'm sure which was more useful if either.

[pengfei]

llvm/lib/Target/X86/X86ISelLowering.cpp

53411

Thanks @nikic for the inputs! My comment was inspired when reviewering test cases like eq_pow_or, abs_eq_pow2_zero etc.
I did have the same concern, but I'm not clear of it. This also makes me worrying whether the similar thing this patch does is necessary or not and what's important how we check for that? Any pointers would help.

llvm/test/CodeGen/X86/icmp-pow2-logic-npow2.ll

11–30

So we may remove these tests instead? We should avoid to add dud tests.

[goldstein.w.n]

llvm/lib/Target/X86/X86ISelLowering.cpp

53411

Thanks @nikic for the inputs! My comment was inspired when reviewering test cases like eq_pow_or, abs_eq_pow2_zero etc.
I did have the same concern, but I'm not clear of it. This also makes me worrying whether the similar thing this patch does is necessary or not and what's important how we check for that? Any pointers would help.

I can drop the checks, it still seems to be correct w.o them: https://alive2.llvm.org/ce/z/Q3PTMv

Guess my feeling is we know its the wrong thing to do, and if it does come up, we don't want to be
hiding it. Up to you.

[goldstein.w.n]

llvm/test/CodeGen/X86/icmp-pow2-logic-npow2.ll

11–30

So we may remove these tests instead? We should avoid to add dud tests.

This test is for D142344 where it is not a dud.
Do you mean abs_eq_pow2_zero and abs_ne_pow2_signed_min?

[goldstein.w.n]

llvm/lib/Target/X86/X86ISelLowering.cpp

53411

Thanks @nikic for the inputs! My comment was inspired when reviewering test cases like eq_pow_or, abs_eq_pow2_zero etc.
I did have the same concern, but I'm not clear of it. This also makes me worrying whether the similar thing this patch does is necessary or not and what's important how we check for that? Any pointers would help.

I can drop the checks, it still seems to be correct w.o them: https://alive2.llvm.org/ce/z/Q3PTMv

Guess my feeling is we know its the wrong thing to do, and if it does come up, we don't want to be
hiding it. Up to you.

Personal preference is:
leave checks in and ignore the case > handle the case with D142666 > remove the branches

[pengfei]

llvm/lib/Target/X86/X86ISelLowering.cpp

53411

It looks awkward to me that neither do I want to increase unnecessary code complexity nor can assert these cases never happen.
I don't have preference. I suggest to add comments to explain they are no worth to handle if you want to keep them.

Tips: Phabricator will set the link for it e.g., D142666 if you don't put `` around it.

llvm/test/CodeGen/X86/icmp-pow2-logic-npow2.ll

11–30

Yes. Sorry for the mistake.

[goldstein.w.n]

Rebase

[goldstein.w.n]

llvm/test/CodeGen/X86/icmp-pow2-logic-npow2.ll

11–30

Yes. Sorry for the mistake.

11–30

So we may remove these tests instead? We should avoid to add dud tests.

Removed those, although did add a few other tests for negative cases that were missing.
Unlike the 0/intmin case, they can actually catch a bug, but lmk if I should drop them.

[RKSimon]

LGTM

[goldstein.w.n]

Rebase

llvm/lib/Target/X86/X86ISelLowering.cpp

static SDValue promoteExtBeforeAdd(SDNode *Ext, SelectionDAG &DAG,
   Flags.setNoUnsignedWrap(NUW);
   return DAG.getNode(ISD::ADD, SDLoc(Add), VT, NewExt, NewConstant, Flags);
 }
 
 // If we face {ANY,SIGN,ZERO}_EXTEND that is applied to a CMOV with constant
 // operands and the result of CMOV is not used anywhere else - promote CMOV
 // itself instead of promoting its result. This could be beneficial, because:
 //     1) X86TargetLowering::EmitLoweredSelect later can do merging of two
 //        (or more) pseudo-CMOVs only when they go one-after-another and
 //        getting rid of result extension code after CMOV will help that.
 //     2) Promotion of constant CMOV arguments is free, hence the
 //        {ANY,SIGN,ZERO}_EXTEND will just be deleted.
 //     3) 16-bit CMOV encoding is 4 bytes, 32-bit CMOV is 3-byte, so this
 //        promotion is also good in terms of code-size.
 //        (64-bit CMOV is 4-bytes, that's why we don't do 32-bit => 64-bit
 //         promotion).
 static SDValue combineToExtendCMOV(SDNode *Extend, SelectionDAG &DAG) {
   SDValue CMovN = Extend->getOperand(0);
   if (CMovN.getOpcode() != X86ISD::CMOV || !CMovN.hasOneUse())
     return SDValue();
 
   EVT TargetVT = Extend->getValueType(0);
   unsigned ExtendOpcode = Extend->getOpcode();
   SDLoc DL(Extend);
 
   EVT VT = CMovN.getValueType();
   SDValue CMovOp0 = CMovN.getOperand(0);
   SDValue CMovOp1 = CMovN.getOperand(1);
 
   if (!isa<ConstantSDNode>(CMovOp0.getNode()) ||
       !isa<ConstantSDNode>(CMovOp1.getNode()))
     return SDValue();
 
   // Only extend to i32 or i64.
   if (TargetVT != MVT::i32 && TargetVT != MVT::i64)
     return SDValue();
 
if (OpVT.isScalarInteger()) {
         APInt UpperBits = APInt::getBitsSetFrom(SrcVT.getScalarSizeInBits(),
                                                 OpVT.getScalarSizeInBits());
         const TargetLowering &TLI = DAG.getTargetLoweringInfo();
         if (DAG.MaskedValueIsZero(LHS.getOperand(0), UpperBits) &&
             TLI.isTypeLegal(LHS.getOperand(0).getValueType()))
           return DAG.getSetCC(DL, VT, LHS.getOperand(0),
                               DAG.getConstant(0, DL, SrcVT), CC);
       }
+
+      // With C as a power of 2 and C != 0 and C != INT_MIN:
+      //    icmp eq Abs(X) C ->
+      //        (icmp eq A, C) | (icmp eq A, -C)
+      //    icmp ne Abs(X) C ->
+      //        (icmp ne A, C) & (icmp ne A, -C)
+      // Both of these patterns can be better optimized in
+      // DAGCombiner::foldAndOrOfSETCC. Note this only applies for scalar
+      // integers which is checked above.
+      if (LHS.getOpcode() == ISD::ABS && LHS.hasOneUse()) {
+        if (auto *C = dyn_cast<ConstantSDNode>(RHS)) {
+          const APInt &CInt = C->getAPIntValue();
+          // We can better optimize this case in DAGCombiner::foldAndOrOfSETCC.
+          if (CInt.isPowerOf2() && !CInt.isMinSignedValue()) {
+            SDValue BaseOp = LHS.getOperand(0);
+            SDValue SETCC0 = DAG.getSetCC(DL, VT, BaseOp, RHS, CC);
+            SDValue SETCC1 = DAG.getSetCC(
+                DL, VT, BaseOp, DAG.getConstant(-CInt, DL, OpVT), CC);
+            return DAG.getNode(CC == ISD::SETEQ ? ISD::OR : ISD::AND, DL, VT,
+                               SETCC0, SETCC1);
+          }
+        }
+      }
     }
   }
 
   if (VT.isVector() && VT.getVectorElementType() == MVT::i1 &&
       (CC == ISD::SETNE || CC == ISD::SETEQ || ISD::isSignedIntSetCC(CC))) {
     // Using temporaries to avoid messing up operand ordering for later
     // transformations if this doesn't work.
     SDValue Op0 = LHS;

llvm/test/CodeGen/X86/icmp-pow2-logic-npow2.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc -mtriple=i686-unknown-linux-gnu < %s | FileCheck %s --check-prefixes=X86
 ; RUN: llc -mtriple=x86_64-unknown-linux-gnu < %s | FileCheck %s --check-prefixes=X64
 
 declare i64 @llvm.abs.i64(i64, i1)
 declare <2 x i64> @llvm.abs.2xi64(<2 x i64>, i1)
 declare i32 @llvm.abs.i32(i32, i1)
 declare i16 @llvm.abs.i16(i16, i1)
 declare i8 @llvm.abs.i8(i8, i1)
 
 define i1 @eq_pow_or(i32 %0) nounwind {
 ; X86-LABEL: eq_pow_or:
 ; X86:       # %bb.0:
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    addl $32, %eax
 ; X86-NEXT:    testl $-65, %eax
 ; X86-NEXT:    sete %al
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: eq_pow_or:
 ; X64:       # %bb.0:
 ; X64-NEXT:    addl $32, %edi
 ; X64-NEXT:    testl $-65, %edi
 ; X64-NEXT:    sete %al
 ; X64-NEXT:    retq
   %2 = icmp eq i32 %0, 32
   %3 = icmp eq i32 %0, -32
   %4 = or i1 %2, %3
   ret i1 %4
 }
 
 define i1 @ne_pow_and(i8 %0) nounwind {
 ; X86-LABEL: ne_pow_and:
 ; X86:       # %bb.0:
 ; X86-NEXT:    movzbl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    addb $16, %al
 ; X86-NEXT:    testb $-33, %al
 ; X86-NEXT:    setne %al
; X64-NEXT:    retq
   %4 = and i1 %2, %3
   ret i1 %4
 }
 
 define i1 @abs_eq_pow2(i32 %0) nounwind {
 ; X86-LABEL: abs_eq_pow2:
 ; X86:       # %bb.0:
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
-; X86-NEXT:    movl %eax, %ecx
-; X86-NEXT:    sarl $31, %ecx
-; X86-NEXT:    xorl %ecx, %eax
-; X86-NEXT:    subl %ecx, %eax
-; X86-NEXT:    cmpl $4, %eax
+; X86-NEXT:    addl $4, %eax
+; X86-NEXT:    testl $-9, %eax
 ; X86-NEXT:    sete %al
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: abs_eq_pow2:
 ; X64:       # %bb.0:
-; X64-NEXT:    movl %edi, %eax
-; X64-NEXT:    negl %eax
-; X64-NEXT:    cmovsl %edi, %eax
-; X64-NEXT:    cmpl $4, %eax
+; X64-NEXT:    addl $4, %edi
+; X64-NEXT:    testl $-9, %edi
 ; X64-NEXT:    sete %al
 ; X64-NEXT:    retq
   %2 = tail call i32 @llvm.abs.i32(i32 %0, i1 true)
   %3 = icmp eq i32 %2, 4
   ret i1 %3
 }
 
 define i1 @abs_ne_pow2(i64 %0) nounwind {
 ; X86-LABEL: abs_ne_pow2:
 ; X86:       # %bb.0:
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
-; X86-NEXT:    movl %eax, %ecx
-; X86-NEXT:    sarl $31, %ecx
-; X86-NEXT:    xorl %ecx, %eax
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %edx
-; X86-NEXT:    xorl %ecx, %edx
-; X86-NEXT:    subl %ecx, %edx
-; X86-NEXT:    sbbl %ecx, %eax
-; X86-NEXT:    xorl $2, %edx
-; X86-NEXT:    orl %eax, %edx
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
+; X86-NEXT:    addl $2, %eax
+; X86-NEXT:    adcl $0, %ecx
+; X86-NEXT:    andl $-5, %eax
+; X86-NEXT:    orl %ecx, %eax
 ; X86-NEXT:    setne %al
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: abs_ne_pow2:
 ; X64:       # %bb.0:
-; X64-NEXT:    movq %rdi, %rax
-; X64-NEXT:    negq %rax
-; X64-NEXT:    cmovsq %rdi, %rax
-; X64-NEXT:    cmpq $2, %rax
+; X64-NEXT:    addq $2, %rdi
+; X64-NEXT:    testq $-5, %rdi
 ; X64-NEXT:    setne %al
 ; X64-NEXT:    retq
   %2 = tail call i64 @llvm.abs.i64(i64 %0, i1 true)
   %3 = icmp ne i64 %2, 2
   ret i1 %3
 }
 
 define i1 @abs_ne_nonpow2(i16 %0) nounwind {