[Codegen] TargetLowering::SimplifySetCC(): omit urem when possible

[lebedev.ri]

Summary

This addresses the regression that is being exposed by D50222 in test/CodeGen/X86/jump_sign.ll
The missing fold, at least partially, looks trivial:
https://rise4fun.com/Alive/Zsln
i.e. if we are comparing with zero, and comparing the urem-by-non-power-of-two,
and the urem is of something that may at most have a single bit set (or no bits set at all),
the urem is not needed.

[xbolva00]

Thanks, you fixed it!

Can you add some new explicit tests for this fold?

[lebedev.ri]

+Standalone test coverage

[xbolva00]

Looks fine.

Thanks for alive proof as well!

[spatel]

LGTM. I have no idea if it's worth the trade-off, but we could do this sooner in IR (instcombine) instead of or in addition to SDAG?

[lebedev.ri]

Thank you for the reviews.

In D63390#1546676, @spatel wrote:

LGTM. I have no idea if it's worth the trade-off, but we could do this sooner in IR (instcombine) instead of or in addition to SDAG?

Indeed, this fold is missed in middle-end too, but the regression at hand is in back-end test,
so i'm not sure if we should just hand-wave and only fix it in middle-end.
Also, where should the middle-end fix be? Again InstCombine?

I'm also not sure if this is the best approach, the fold doesn't care *where* those bits are,
it only cares about the *count* of ones, and is thus easily defeated by shift operations,
as it is seen from tests.

[spatel]

In D63390#1546687, @lebedev.ri wrote:

Thank you for the reviews.

In D63390#1546676, @spatel wrote:

LGTM. I have no idea if it's worth the trade-off, but we could do this sooner in IR (instcombine) instead of or in addition to SDAG?

Indeed, this fold is missed in middle-end too, but the regression at hand is in back-end test,
so i'm not sure if we should just hand-wave and only fix it in middle-end.
Also, where should the middle-end fix be? Again InstCombine?

Yep, yet another clause under InstCombiner::visitICmpInst().

I'm also not sure if this is the best approach, the fold doesn't care *where* those bits are,
it only cares about the *count* of ones, and is thus easily defeated by shift operations,
as it is seen from tests.

True, although without some real-world evidence that this matters, I'd say "good enough". :)

[lebedev.ri]

:]

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

if (N0.getOpcode() == ISD::ZERO_EXTEND) {
         if (Op0.getOpcode() == ISD::AssertZext &&
             cast<VTSDNode>(Op0.getOperand(1))->getVT() == MVT::i1)
           return DAG.getSetCC(dl, VT, Op0,
                               DAG.getConstant(0, dl, Op0.getValueType()),
                               Cond == ISD::SETEQ ? ISD::SETNE : ISD::SETEQ);
       }
     }
 
+    // Given:
+    //   icmp eq/ne (urem %x, %y), 0
+    // Iff %x has 0 or 1 bits set, and %y has at least 2 bits set, omit 'urem':
+    //   icmp eq/ne %x, 0
+    if (N0.getOpcode() == ISD::UREM && N1C->isNullValue() &&
+        (Cond == ISD::SETEQ || Cond == ISD::SETNE)) {
+      KnownBits XKnown = DAG.computeKnownBits(N0.getOperand(0));
+      KnownBits YKnown = DAG.computeKnownBits(N0.getOperand(1));
+      if (XKnown.countMaxPopulation() == 1 && YKnown.countMinPopulation() >= 2)
+        return DAG.getSetCC(dl, VT, N0.getOperand(0), N1, Cond);
+    }
+
     if (SDValue V =
             optimizeSetCCOfSignedTruncationCheck(VT, N0, N1, Cond, DCI, dl))
       return V;
   }
 
   // These simplifications apply to splat vectors as well.
   // TODO: Handle more splat vector cases.
   if (auto *N1C = isConstOrConstSplat(N1)) {

llvm/test/CodeGen/X86/omit-urem-of-power-of-two-or-zero-when-comparing-with-zero.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mtriple=x86_64-unknown-unknown -mattr=+sse,+sse2,+avx,+avx2 | FileCheck %s
 
 ; Given:
 ;   icmp eq/ne (urem %x, C), 0
 ; Iff C is not a power of two (those should not get to here though),
 ; and %x may have at most one bit set, omit the 'urem':
 ;   icmp eq/ne %x, 0
 
 ;------------------------------------------------------------------------------;
 ; Basic scalar tests
 ;------------------------------------------------------------------------------;
 
 define i1 @p0_scalar_urem_by_const(i32 %x, i32 %y) {
 ; CHECK-LABEL: p0_scalar_urem_by_const:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    # kill: def $edi killed $edi def $rdi
-; CHECK-NEXT:    andl $128, %edi
-; CHECK-NEXT:    movl $2863311531, %eax # imm = 0xAAAAAAAB
-; CHECK-NEXT:    imulq %rdi, %rax
-; CHECK-NEXT:    shrq $34, %rax
-; CHECK-NEXT:    addl %eax, %eax
-; CHECK-NEXT:    leal (%rax,%rax,2), %eax
-; CHECK-NEXT:    cmpl %eax, %edi
+; CHECK-NEXT:    testb $-128, %dil
 ; CHECK-NEXT:    sete %al
 ; CHECK-NEXT:    retq
   %t0 = and i32 %x, 128 ; clearly a power-of-two or zero
   %t1 = urem i32 %t0, 6 ; '6' is clearly not a power of two
   %t2 = icmp eq i32 %t1, 0
   ret i1 %t2
 }
 
 define i1 @p1_scalar_urem_by_nonconst(i32 %x, i32 %y) {
 ; CHECK-LABEL: p1_scalar_urem_by_nonconst:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    movl %edi, %eax
-; CHECK-NEXT:    andl $128, %eax
-; CHECK-NEXT:    orl $6, %esi
-; CHECK-NEXT:    xorl %edx, %edx
-; CHECK-NEXT:    divl %esi
-; CHECK-NEXT:    testl %edx, %edx
+; CHECK-NEXT:    testb $-128, %dil
 ; CHECK-NEXT:    sete %al
 ; CHECK-NEXT:    retq
   %t0 = and i32 %x, 128 ; clearly a power-of-two or zero
   %t1 = or i32 %y, 6 ; two bits set, clearly not a power of two
   %t2 = urem i32 %t0, %t1
   %t3 = icmp eq i32 %t2, 0
   ret i1 %t3
 }