[SDAG] convert sub from (Pow2-1) constant into xor

[spatel]

Summary

An xor with constant should have equivalent perf as sub-from-constant on any target (or better perf in the case that the sub constant is harder to materialize and use).

This is translated from an existing fold in InstCombine, but the pattern can show up in codegen as shown in a variety of test diffs.

Alive2 proof:
https://alive2.llvm.org/ce/z/8CgggY

This might help remove some diffs from D127115. We don't see test diffs on basic x86 examples because this fold already exists somewhere later in that target's codegen, but that may be too late to combine with other transforms.

[RKSimon]

LGTM - I'd be interested to know if this will allow us to remove the x86 specific fold?

[deadalnix]

It doesn't looks like it is helping D127115, but it looks useful on its own.

[spatel]

In D128080#3594009, @deadalnix wrote:

It doesn't looks like it is helping D127115, but it looks useful on its own.

Yes, I stepped through one of those tests, and we'd have to do something else...I'm not sure what that is yet.

I also tracked down where this happens in x86 codegen:
https://github.com/llvm/llvm-project/blob/cd64a427efa0baaf1bb7ae624d4301908afc07f7/llvm/lib/Target/X86/X86InstrCompiler.td#L1535

So this fold and the InstCombine that I copied from are actually over-constrained. We don't need a low-bit-mask constant:
https://alive2.llvm.org/ce/z/OUm6N_

I'll add a TODO comment for now. I can add more tests and generalize the transforms as a follow-up.

[spatel]

In D128080#3594019, @spatel wrote:

I also tracked down where this happens in x86 codegen:
https://github.com/llvm/llvm-project/blob/cd64a427efa0baaf1bb7ae624d4301908afc07f7/llvm/lib/Target/X86/X86InstrCompiler.td#L1535

So this fold and the InstCombine that I copied from are actually over-constrained. We don't need a low-bit-mask constant:
https://alive2.llvm.org/ce/z/OUm6N_

And digging further, that change was added with D48557, but that was a target-limited form of the original patch D48529...and that was the better version of this patch! :)

I applied that patch today, and the PowerPC regression is no longer present, but there's a different test with an extra load immediate. That seems like a minor regression that could be fixed easily.

The AMDGPU diff seen here was considered a regression then, so I'm assuming that's still true now.

There are now RISCV tests with diffs that look like real improvements in test/CodeGen/RISCV/atomic-signext.ll and /test/CodeGen/RISCV/atomic-rmw.ll:

-; RV32IA-NEXT:    li a5, 24
-; RV32IA-NEXT:    sub a3, a5, a3
+; RV32IA-NEXT:    xori a3, a3, 24

@arsenm @craig.topper - given that we have almost this transform in IR as a canonicalization, do we still want to make this target-specific for DAGCombiner?

llvm/test/CodeGen/AMDGPU/ds-sub-offset.ll

112

This diff was called a code-size regression in D48529.

[RKSimon]

llvm/test/CodeGen/AMDGPU/ds-sub-offset.ll

112

@foad Is this still an issue? Not sure if its relevant, but does the loss of the offset:65535 compensate?

[spatel]

I put up D128123 as the potential better/final patch, so we can see the current test diffs.

[foad]

llvm/test/CodeGen/AMDGPU/ds-sub-offset.ll

112

It's still a code size regression and the loss of the offset:65535 does not compensate. Also AMDGPU has a decent set of subrev instructions so I don't think this transform is of any use.

[spatel]

Abandoning - looks like this will need a target hook of some kind along with the more general transform in D128123.

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

if (SDValue Carry = getAsCarry(TLI, N0)) {
       SDValue Zero = DAG.getConstant(0, DL, VT);
       SDValue NegX = DAG.getNode(ISD::SUB, DL, VT, Zero, X);
       return DAG.getNode(ISD::ADDCARRY, DL,
                          DAG.getVTList(VT, Carry.getValueType()), NegX, Zero,
                          Carry);
     }
   }
 
+  // Turn this into xor if N0 is 2^n-1 and the remaining high bits of N1 are
+  // known zero.
+  if (ConstantSDNode *C0 = isConstOrConstSplat(N0)) {
+    const APInt& C0Val = C0->getAPIntValue();
+    if (C0Val.isMask() && (C0Val | DAG.computeKnownBits(N1).Zero).isAllOnes())
+      return DAG.getNode(ISD::XOR, DL, VT, N1, N0);
+  }
+
   return SDValue();
 }
 
 SDValue DAGCombiner::visitSUBSAT(SDNode *N) {
   SDValue N0 = N->getOperand(0);
   SDValue N1 = N->getOperand(1);
   EVT VT = N0.getValueType();
   SDLoc DL(N);

llvm/test/CodeGen/AArch64/sub1.ll

; CHECK-NEXT:    ret
   %r = and i64 %a1, %a2
   ret i64 %r
 }
 
 define i8 @masked_sub_i8(i8 %x) {
 ; CHECK-LABEL: masked_sub_i8:
 ; CHECK:       // %bb.0:
 ; CHECK-NEXT:    mov w8, #5
-; CHECK-NEXT:    mov w9, #7
 ; CHECK-NEXT:    and w8, w0, w8
-; CHECK-NEXT:    sub w0, w9, w8
+; CHECK-NEXT:    eor w0, w8, #0x7
 ; CHECK-NEXT:    ret
   %a = and i8 %x, 5
   %m = sub i8 7, %a
   ret i8 %m
 }
 
 define i8 @not_masked_sub_i8(i8 %x) {
 ; CHECK-LABEL: not_masked_sub_i8:
 ; CHECK:       // %bb.0:
 ; CHECK-NEXT:    mov w8, #7
 ; CHECK-NEXT:    and w9, w0, #0x8
 ; CHECK-NEXT:    sub w0, w8, w9
 ; CHECK-NEXT:    ret
   %a = and i8 %x, 8
   %m = sub i8 7, %a
   ret i8 %m
 }
 
 define i32 @masked_sub_i32(i32 %x) {
 ; CHECK-LABEL: masked_sub_i32:
 ; CHECK:       // %bb.0:
 ; CHECK-NEXT:    mov w8, #9
-; CHECK-NEXT:    mov w9, #31
 ; CHECK-NEXT:    and w8, w0, w8
-; CHECK-NEXT:    sub w0, w9, w8
+; CHECK-NEXT:    eor w0, w8, #0x1f
 ; CHECK-NEXT:    ret
   %a = and i32 %x, 9
   %m = sub i32 31, %a
   ret i32 %m
 }
 
 define <4 x i32> @masked_sub_v4i32(<4 x i32> %x) {
 ; CHECK-LABEL: masked_sub_v4i32:
 ; CHECK:       // %bb.0:
 ; CHECK-NEXT:    movi v1.4s, #42
 ; CHECK-NEXT:    movi v2.4s, #1, msl #8
 ; CHECK-NEXT:    and v0.16b, v0.16b, v1.16b
-; CHECK-NEXT:    sub v0.4s, v2.4s, v0.4s
+; CHECK-NEXT:    eor v0.16b, v0.16b, v2.16b
 ; CHECK-NEXT:    ret
   %a = and <4 x i32> %x, <i32 42, i32 42, i32 42, i32 42>
   %m = sub <4 x i32> <i32 511, i32 511, i32 511, i32 511>, %a
   ret <4 x i32>  %m
 }

llvm/test/CodeGen/AMDGPU/ds-sub-offset.ll

entry:
   store volatile float %fmas, float addrspace(1)* null
   ret void
 }
 
 define amdgpu_kernel void @add_x_shl_neg_to_sub_max_offset() #1 {
 ; CI-LABEL: add_x_shl_neg_to_sub_max_offset:
 ; CI:       ; %bb.0:
 ; CI-NEXT:    v_lshlrev_b32_e32 v0, 2, v0
-; CI-NEXT:    v_sub_i32_e32 v0, vcc, 0, v0
+; CI-NEXT:    v_xor_b32_e32 v0, 0xffff, v0
 ; CI-NEXT:    v_mov_b32_e32 v1, 13
 ; CI-NEXT:    s_mov_b32 m0, -1
-; CI-NEXT:    ds_write_b8 v0, v1 offset:65535
+; CI-NEXT:    ds_write_b8 v0, v1
 ; CI-NEXT:    s_endpgm
 ;
 ; GFX9-LABEL: add_x_shl_neg_to_sub_max_offset:
 ; GFX9:       ; %bb.0:
 ; GFX9-NEXT:    v_lshlrev_b32_e32 v0, 2, v0
-; GFX9-NEXT:    v_sub_u32_e32 v0, 0, v0
+; GFX9-NEXT:    v_xor_b32_e32 v0, 0xffff, v0
 ; GFX9-NEXT:    v_mov_b32_e32 v1, 13
-; GFX9-NEXT:    ds_write_b8 v0, v1 offset:65535
+; GFX9-NEXT:    ds_write_b8 v0, v1
 ; GFX9-NEXT:    s_endpgm
 ;
 ; GFX10-LABEL: add_x_shl_neg_to_sub_max_offset:
 ; GFX10:       ; %bb.0:
 ; GFX10-NEXT:    v_lshlrev_b32_e32 v0, 2, v0
 ; GFX10-NEXT:    v_mov_b32_e32 v1, 13
-; GFX10-NEXT:    v_sub_nc_u32_e32 v0, 0, v0
-; GFX10-NEXT:    ds_write_b8 v0, v1 offset:65535
+; GFX10-NEXT:    v_xor_b32_e32 v0, 0xffff, v0
+; GFX10-NEXT:    ds_write_b8 v0, v1
 ; GFX10-NEXT:    s_endpgm
   %x.i = call i32 @llvm.amdgcn.workitem.id.x() #0
   %neg = sub i32 0, %x.i
   %shl = shl i32 %neg, 2
   %add = add i32 65535, %shl
   %ptr = inttoptr i32 %add to i8 addrspace(3)*
   store i8 13, i8 addrspace(3)* %ptr
   ret void

llvm/test/CodeGen/AMDGPU/setcc-multiple-use.ll

 define i32 @f() {
 ; CHECK-LABEL: f:
 ; CHECK:       ; %bb.0: ; %bb
 ; CHECK-NEXT:    s_waitcnt vmcnt(0) expcnt(0) lgkmcnt(0)
 ; CHECK-NEXT:    s_waitcnt_vscnt null, 0x0
 ; CHECK-NEXT:    v_mov_b32_e32 v0, 0
 ; CHECK-NEXT:    ds_read_b32 v0, v0
 ; CHECK-NEXT:    s_waitcnt lgkmcnt(0)
+; CHECK-NEXT:    v_cmp_eq_u32_e32 vcc_lo, 0, v0
+; CHECK-NEXT:    v_cndmask_b32_e64 v1, 0, 1, vcc_lo
 ; CHECK-NEXT:    v_cmp_ne_u32_e32 vcc_lo, 0, v0
-; CHECK-NEXT:    s_cmpk_lg_u32 vcc_lo, 0x0
-; CHECK-NEXT:    s_subb_u32 s4, 1, 0
-; CHECK-NEXT:    v_cndmask_b32_e64 v0, 0, s4, vcc_lo
+; CHECK-NEXT:    v_cndmask_b32_e32 v0, 0, v1, vcc_lo
 ; CHECK-NEXT:    s_setpc_b64 s[30:31]
 bb:
   %i = load i32, i32 addrspace(3)* null, align 16
   %i6 = icmp ult i32 0, %i
   %i7 = sext i1 %i6 to i32
   %i8 = add i32 %i7, 1
   %i9 = and i32 %i8, %i7
   ret i32 %i9
 }

llvm/test/CodeGen/ARM/intrinsics-overflow.ll

define i32 @usub_overflow(i32 %a, i32 %b) #0 {
   %2 = zext i1 %1 to i32
   ret i32 %2
 
   ; CHECK-LABEL: usub_overflow:
 
   ; ARM: subs    r[[R0:[0-9]+]], r[[R0]], r[[R1:[0-9]+]]
   ; ARM: mov     r[[R2:[0-9]+]], #0
   ; ARM: adc     r[[R0]], r[[R2]], #0
-  ; ARM: rsb     r[[R0]], r[[R0]], #1
+  ; ARM: eor     r[[R0]], r[[R0]], #1
 
   ; THUMBV6: movs    r[[R2:[0-9]+]], #0
   ; THUMBV6: subs    r[[R0:[0-9]+]], r[[R0]], r[[R1:[0-9]+]]
   ; THUMBV6: adcs    r[[R2]], r[[R2]]
   ; THUMBV6: movs    r[[R0]], #1
-  ; THUMBV6: subs    r[[R0]], r[[R0]], r[[R2]]
+  ; THUMBV6: eors    r[[R0]], r[[R2]]
 
   ; THUMBV7: subs    r[[R0:[0-9]+]], r[[R0]], r[[R1:[0-9]+]]
   ; THUMBV7: mov.w   r[[R2:[0-9]+]], #0
   ; THUMBV7: adc     r[[R0]], r[[R2]], #0
-  ; THUMBV7: rsb.w   r[[R0]], r[[R0]], #1
+  ; THUMBV7: eor     r[[R0]], r[[R0]], #1
 
   ; We should know that the overflow is just 1 bit,
   ; no need to clear any other bit
   ; CHECK-NOT: and
 }
 
 define i32 @ssub_overflow(i32 %a, i32 %b) #0 {
   %sadd = tail call { i32, i1 } @llvm.ssub.with.overflow.i32(i32 %a, i32 %b)

llvm/test/CodeGen/ARM/usub_sat.ll

 ; CHECK-T1-NEXT:    push {r4, lr}
 ; CHECK-T1-NEXT:    mov r4, r1
 ; CHECK-T1-NEXT:    movs r1, #0
 ; CHECK-T1-NEXT:    subs r2, r0, r2
 ; CHECK-T1-NEXT:    sbcs r4, r3
 ; CHECK-T1-NEXT:    mov r0, r1
 ; CHECK-T1-NEXT:    adcs r0, r1
 ; CHECK-T1-NEXT:    movs r3, #1
-; CHECK-T1-NEXT:    subs r3, r3, r0
+; CHECK-T1-NEXT:    eors r3, r0
 ; CHECK-T1-NEXT:    mov r0, r1
 ; CHECK-T1-NEXT:    beq .LBB1_3
 ; CHECK-T1-NEXT:  @ %bb.1:
 ; CHECK-T1-NEXT:    cmp r3, #0
 ; CHECK-T1-NEXT:    beq .LBB1_4
 ; CHECK-T1-NEXT:  .LBB1_2:
 ; CHECK-T1-NEXT:    pop {r4, pc}
 ; CHECK-T1-NEXT:  .LBB1_3:
 ; CHECK-T1-NEXT:    mov r0, r2
 ; CHECK-T1-NEXT:    cmp r3, #0
 ; CHECK-T1-NEXT:    bne .LBB1_2
 ; CHECK-T1-NEXT:  .LBB1_4:
 ; CHECK-T1-NEXT:    mov r1, r4
 ; CHECK-T1-NEXT:    pop {r4, pc}
 ;
 ; CHECK-T2-LABEL: func2:
 ; CHECK-T2:       @ %bb.0:
 ; CHECK-T2-NEXT:    subs r0, r0, r2
 ; CHECK-T2-NEXT:    mov.w r12, #0
 ; CHECK-T2-NEXT:    sbcs r1, r3
 ; CHECK-T2-NEXT:    adc r2, r12, #0
-; CHECK-T2-NEXT:    rsbs.w r2, r2, #1
+; CHECK-T2-NEXT:    eors r2, r2, #1
 ; CHECK-T2-NEXT:    itt ne
 ; CHECK-T2-NEXT:    movne r0, #0
 ; CHECK-T2-NEXT:    movne r1, #0
 ; CHECK-T2-NEXT:    bx lr
 ;
 ; CHECK-ARM-LABEL: func2:
 ; CHECK-ARM:       @ %bb.0:
 ; CHECK-ARM-NEXT:    subs r0, r0, r2
 ; CHECK-ARM-NEXT:    mov r12, #0
 ; CHECK-ARM-NEXT:    sbcs r1, r1, r3
 ; CHECK-ARM-NEXT:    adc r2, r12, #0
-; CHECK-ARM-NEXT:    rsbs r2, r2, #1
+; CHECK-ARM-NEXT:    eors r2, r2, #1
 ; CHECK-ARM-NEXT:    movwne r0, #0
 ; CHECK-ARM-NEXT:    movwne r1, #0
 ; CHECK-ARM-NEXT:    bx lr
   %tmp = call i64 @llvm.usub.sat.i64(i64 %x, i64 %y)
   ret i64 %tmp
 }
 
 define zeroext i16 @func16(i16 zeroext %x, i16 zeroext %y) nounwind {

llvm/test/CodeGen/ARM/usub_sat_plus.ll

 ; CHECK-T1-NEXT:    movs r1, #0
 ; CHECK-T1-NEXT:    ldr r4, [sp, #12]
 ; CHECK-T1-NEXT:    ldr r3, [sp, #8]
 ; CHECK-T1-NEXT:    subs r3, r0, r3
 ; CHECK-T1-NEXT:    sbcs r2, r4
 ; CHECK-T1-NEXT:    mov r0, r1
 ; CHECK-T1-NEXT:    adcs r0, r1
 ; CHECK-T1-NEXT:    movs r4, #1
-; CHECK-T1-NEXT:    subs r4, r4, r0
+; CHECK-T1-NEXT:    eors r4, r0
 ; CHECK-T1-NEXT:    mov r0, r1
 ; CHECK-T1-NEXT:    beq .LBB1_3
 ; CHECK-T1-NEXT:  @ %bb.1:
 ; CHECK-T1-NEXT:    cmp r4, #0
 ; CHECK-T1-NEXT:    beq .LBB1_4
 ; CHECK-T1-NEXT:  .LBB1_2:
 ; CHECK-T1-NEXT:    pop {r4, pc}
 ; CHECK-T1-NEXT:  .LBB1_3:
 ; CHECK-T1-NEXT:    mov r0, r3
 ; CHECK-T1-NEXT:    cmp r4, #0
 ; CHECK-T1-NEXT:    bne .LBB1_2
 ; CHECK-T1-NEXT:  .LBB1_4:
 ; CHECK-T1-NEXT:    mov r1, r2
 ; CHECK-T1-NEXT:    pop {r4, pc}
 ;
 ; CHECK-T2-LABEL: func64:
 ; CHECK-T2:       @ %bb.0:
 ; CHECK-T2-NEXT:    ldrd r2, r3, [sp]
 ; CHECK-T2-NEXT:    mov.w r12, #0
 ; CHECK-T2-NEXT:    subs r0, r0, r2
 ; CHECK-T2-NEXT:    sbcs r1, r3
 ; CHECK-T2-NEXT:    adc r2, r12, #0
-; CHECK-T2-NEXT:    rsbs.w r2, r2, #1
+; CHECK-T2-NEXT:    eors r2, r2, #1
 ; CHECK-T2-NEXT:    itt ne
 ; CHECK-T2-NEXT:    movne r0, #0
 ; CHECK-T2-NEXT:    movne r1, #0
 ; CHECK-T2-NEXT:    bx lr
 ;
 ; CHECK-ARM-LABEL: func64:
 ; CHECK-ARM:       @ %bb.0:
 ; CHECK-ARM-NEXT:    ldr r2, [sp]
 ; CHECK-ARM-NEXT:    mov r12, #0
 ; CHECK-ARM-NEXT:    ldr r3, [sp, #4]
 ; CHECK-ARM-NEXT:    subs r0, r0, r2
 ; CHECK-ARM-NEXT:    sbcs r1, r1, r3
 ; CHECK-ARM-NEXT:    adc r2, r12, #0
-; CHECK-ARM-NEXT:    rsbs r2, r2, #1
+; CHECK-ARM-NEXT:    eors r2, r2, #1
 ; CHECK-ARM-NEXT:    movwne r0, #0
 ; CHECK-ARM-NEXT:    movwne r1, #0
 ; CHECK-ARM-NEXT:    bx lr
   %a = mul i64 %y, %z
   %tmp = call i64 @llvm.usub.sat.i64(i64 %x, i64 %z)
   ret i64 %tmp
 }
 

llvm/test/CodeGen/PowerPC/select_const.ll

; NO_ISEL-NEXT:    blr
   %bo = srem i8 120, %sel
   ret i8 %bo
 }
 
 define i8 @sel_constants_urem_constant(i1 %cond) {
 ; ALL-LABEL: sel_constants_urem_constant:
 ; ALL:       # %bb.0:
 ; ALL-NEXT:    clrldi 3, 3, 63
-; ALL-NEXT:    subfic 3, 3, 3
+; ALL-NEXT:    xori 3, 3, 3
 ; ALL-NEXT:    blr
   %sel = select i1 %cond, i8 -4, i8 23
   %bo = urem i8 %sel, 5
   ret i8 %bo
 }
 
 define i8 @urem_constant_sel_constants(i1 %cond) {
 ; ISEL-LABEL: urem_constant_sel_constants:

llvm/test/CodeGen/SPARC/64bit.ll

entry:
   %arraydecay = getelementptr inbounds [32 x i8], [32 x i8]* %b, i64 0, i64 0
   call void @g(i8* %arraydecay) #2
   ret void
 }
 
 declare void @g(i8*)
 
 ; CHECK: expand_setcc
-; CHECK: cmp %i0, 1
-; CHECK: movl %xcc, 1,
+; CHECK: cmp %i0, 0
+; CHECK: movg %xcc, 1, %i1
 define i32 @expand_setcc(i64 %a) {
   %cond = icmp sle i64 %a, 0
   %cast2 = zext i1 %cond to i32
   %RV = sub i32 1, %cast2
   ret i32 %RV
 }
 
 ; CHECK: spill_i64