[DAGCombiner] Combine frem into fdiv+ftrunc+fma

[qiucf]

Summary

This helps in C library function fmod. remainder needs similar optimization, but since that's a libcall instead of a IR/DAG op, we can do it in future patches.

[RKSimon]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

14425

comment? // fold (frem x, y) -> (fma (fneg), y, x) ...

14428

Should we check that ftrunc is available?

[foad]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

14425

Is this always preferable, even on targets where FREM is legal?

[foad]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

14425

I see you have added an isLegal check for FREM. But I don't understand why you are doing this as a combine in the first place, instead of changing the way FREM is legalized to do this as a lowering instead of calling a libcall.

[qiucf]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

14425

I'm not sure it's good idea to consider fast-math flags in legalizing.. Here frem just looks like how fdiv is transformed into series of operations in combiner.

[spatel]

I like this as a combine because we can chain it with other combines. For example, the fdiv becomes a reciprocal op in the current tests.

I'd like to see tests for other targets though. I did a quick test, and this may trigger for any of AArch64, AMDGPU, or x86 (use -mattr=avx to make sure ftrunc is supported).

There's an open question about exactly which FMF are needed to enable this transform. Should we require 'reassoc' or others? Is 'reassoc' enough by itself?
The current tests show 'fast' only, so we should reduce at least one of those to whatever we decide is the minimum requirement.

There's also a possible missing constraint when optimizing for minimum size - if we know this node can be lowered to a libcall, is that smaller than the expansion?

We might be able to answer some of these questions and share code with the transforms under DAGCombiner::visitFPOW().

[qiucf]

Add ninf/nsz requirements

[RKSimon]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

16685

Should we check for isOperationLegalOrCustom(ISD::FMA, VT) as well?

[qiucf]

Migrated to https://github.com/llvm/llvm-project/pull/67642

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

 
   // fold (frem c1, c2) -> fmod(c1,c2)
   if (N0CFP && N1CFP)
     return DAG.getNode(ISD::FREM, SDLoc(N), VT, N0, N1);
 
   if (SDValue NewSel = foldBinOpIntoSelect(N))
     return NewSel;
 
+  if (Flags.hasApproximateFuncs()) {
+    SDLoc Loc(N);
+    SDValue Div = DAG.getNode(ISD::FDIV, Loc, VT, N0, N1);
+    SDValue Trunc = DAG.getNode(ISD::FTRUNC, Loc, VT, Div);
+    return DAG.getNode(ISD::FMA, Loc, VT,
+                       DAG.getNode(ISD::FNEG, Loc, VT, Trunc), N1, N0);
+  }
+
   return SDValue();
 }
 
 SDValue DAGCombiner::visitFSQRT(SDNode *N) {
   SDNodeFlags Flags = N->getFlags();
   const TargetOptions &Options = DAG.getTarget().Options;
 
   // Require 'ninf' flag since sqrt(+Inf) = +Inf, but the estimation goes as:

   if (N1.getOpcode() == ISD::FCOPYSIGN)
     return DAG.getNode(ISD::FCOPYSIGN, SDLoc(N), VT, N0, N1.getOperand(1));
 
   // copysign(x, fp_extend(y)) -> copysign(x, y)
   // copysign(x, fp_round(y)) -> copysign(x, y)
   if (CanCombineFCOPYSIGN_EXTEND_ROUND(N))
     return DAG.getNode(ISD::FCOPYSIGN, SDLoc(N), VT, N0, N1.getOperand(0));
 
   return SDValue();

llvm/test/CodeGen/AMDGPU/frem.ll

 ; SI-NEXT:    s_mov_b32 s3, s11
 ; SI-NEXT:    buffer_load_ushort v0, off, s[4:7], 0
 ; SI-NEXT:    s_waitcnt vmcnt(0)
 ; SI-NEXT:    v_cvt_f32_f16_e32 v0, v0
 ; SI-NEXT:    buffer_load_ushort v1, off, s[0:3], 0 offset:8
 ; SI-NEXT:    s_waitcnt vmcnt(0)
 ; SI-NEXT:    v_cvt_f32_f16_e32 v1, v1
 ; SI-NEXT:    v_rcp_f32_e32 v2, v1
-; SI-NEXT:    v_mul_f32_e32 v2, v0, v2
+; SI-NEXT:    v_mul_f32_e32 v2, v2, v0
 ; SI-NEXT:    v_trunc_f32_e32 v2, v2
 ; SI-NEXT:    v_fma_f32 v0, -v2, v1, v0
 ; SI-NEXT:    v_cvt_f16_f32_e32 v0, v0
 ; SI-NEXT:    buffer_store_short v0, off, s[8:11], 0
 ; SI-NEXT:    s_endpgm
 ;
 ; CI-LABEL: fast_frem_f16:
 ; CI:       ; %bb.0:

 ; CI-NEXT:    s_mov_b32 s6, s10
 ; CI-NEXT:    s_mov_b32 s7, s11
 ; CI-NEXT:    buffer_load_ushort v0, off, s[4:7], 0
 ; CI-NEXT:    s_waitcnt vmcnt(1)
 ; CI-NEXT:    v_cvt_f32_f16_e32 v1, v1
 ; CI-NEXT:    v_rcp_f32_e32 v2, v1
 ; CI-NEXT:    s_waitcnt vmcnt(0)
 ; CI-NEXT:    v_cvt_f32_f16_e32 v0, v0
-; CI-NEXT:    v_mul_f32_e32 v2, v0, v2
+; CI-NEXT:    v_mul_f32_e32 v2, v2, v0
 ; CI-NEXT:    v_trunc_f32_e32 v2, v2
 ; CI-NEXT:    v_fma_f32 v0, -v2, v1, v0
 ; CI-NEXT:    v_cvt_f16_f32_e32 v0, v0
 ; CI-NEXT:    buffer_store_short v0, off, s[8:11], 0
 ; CI-NEXT:    s_endpgm
 ;
 ; VI-LABEL: fast_frem_f16:
 ; VI:       ; %bb.0:

 ; SI-NEXT:    s_mov_b32 s6, s10
 ; SI-NEXT:    s_mov_b32 s7, s11
 ; SI-NEXT:    s_mov_b32 s2, s10
 ; SI-NEXT:    s_mov_b32 s3, s11
 ; SI-NEXT:    buffer_load_dword v0, off, s[4:7], 0
 ; SI-NEXT:    buffer_load_dword v1, off, s[0:3], 0 offset:16
 ; SI-NEXT:    s_waitcnt vmcnt(0)
 ; SI-NEXT:    v_rcp_f32_e32 v2, v1
-; SI-NEXT:    v_mul_f32_e32 v2, v0, v2
+; SI-NEXT:    v_mul_f32_e32 v2, v2, v0
 ; SI-NEXT:    v_trunc_f32_e32 v2, v2
 ; SI-NEXT:    v_fma_f32 v0, -v2, v1, v0
 ; SI-NEXT:    buffer_store_dword v0, off, s[8:11], 0
 ; SI-NEXT:    s_endpgm
 ;
 ; CI-LABEL: fast_frem_f32:
 ; CI:       ; %bb.0:
 ; CI-NEXT:    s_load_dwordx4 s[4:7], s[0:1], 0x9
 ; CI-NEXT:    s_load_dwordx2 s[0:1], s[0:1], 0xd
 ; CI-NEXT:    s_mov_b32 s11, 0xf000
 ; CI-NEXT:    s_mov_b32 s10, -1
 ; CI-NEXT:    s_mov_b32 s2, s10
 ; CI-NEXT:    s_waitcnt lgkmcnt(0)
 ; CI-NEXT:    s_mov_b32 s8, s4
 ; CI-NEXT:    s_mov_b32 s9, s5
 ; CI-NEXT:    s_mov_b32 s4, s6
 ; CI-NEXT:    s_mov_b32 s5, s7
 ; CI-NEXT:    s_mov_b32 s6, s10
 ; CI-NEXT:    s_mov_b32 s7, s11
 ; CI-NEXT:    s_mov_b32 s3, s11
 ; CI-NEXT:    buffer_load_dword v0, off, s[4:7], 0
 ; CI-NEXT:    buffer_load_dword v1, off, s[0:3], 0 offset:16
 ; CI-NEXT:    s_waitcnt vmcnt(0)
 ; CI-NEXT:    v_rcp_f32_e32 v2, v1
-; CI-NEXT:    v_mul_f32_e32 v2, v0, v2
+; CI-NEXT:    v_mul_f32_e32 v2, v2, v0
 ; CI-NEXT:    v_trunc_f32_e32 v2, v2
 ; CI-NEXT:    v_fma_f32 v0, -v2, v1, v0
 ; CI-NEXT:    buffer_store_dword v0, off, s[8:11], 0
 ; CI-NEXT:    s_endpgm
 ;
 ; VI-LABEL: fast_frem_f32:
 ; VI:       ; %bb.0:
 ; VI-NEXT:    s_load_dwordx4 s[4:7], s[0:1], 0x24
 ; VI-NEXT:    s_load_dwordx2 s[0:1], s[0:1], 0x34
 ; VI-NEXT:    s_waitcnt lgkmcnt(0)
 ; VI-NEXT:    v_mov_b32_e32 v2, s6
 ; VI-NEXT:    s_add_u32 s0, s0, 16
 ; VI-NEXT:    v_mov_b32_e32 v3, s7
 ; VI-NEXT:    s_addc_u32 s1, s1, 0
 ; VI-NEXT:    flat_load_dword v4, v[2:3]
 ; VI-NEXT:    v_mov_b32_e32 v3, s1
 ; VI-NEXT:    v_mov_b32_e32 v2, s0
 ; VI-NEXT:    flat_load_dword v2, v[2:3]
 ; VI-NEXT:    v_mov_b32_e32 v0, s4
 ; VI-NEXT:    v_mov_b32_e32 v1, s5
 ; VI-NEXT:    s_waitcnt vmcnt(0)
 ; VI-NEXT:    v_rcp_f32_e32 v3, v2
-; VI-NEXT:    v_mul_f32_e32 v3, v4, v3
+; VI-NEXT:    v_mul_f32_e32 v3, v3, v4
 ; VI-NEXT:    v_trunc_f32_e32 v3, v3
 ; VI-NEXT:    v_fma_f32 v2, -v3, v2, v4
 ; VI-NEXT:    flat_store_dword v[0:1], v2
 ; VI-NEXT:    s_endpgm
 ;
 ; GFX9-LABEL: fast_frem_f32:
 ; GFX9:       ; %bb.0:
 ; GFX9-NEXT:    s_load_dwordx4 s[4:7], s[0:1], 0x24
 ; GFX9-NEXT:    s_load_dwordx2 s[2:3], s[0:1], 0x34
 ; GFX9-NEXT:    v_mov_b32_e32 v0, 0
 ; GFX9-NEXT:    s_waitcnt lgkmcnt(0)
 ; GFX9-NEXT:    global_load_dword v1, v0, s[6:7]
 ; GFX9-NEXT:    global_load_dword v2, v0, s[2:3] offset:16
 ; GFX9-NEXT:    s_waitcnt vmcnt(0)
 ; GFX9-NEXT:    v_rcp_f32_e32 v3, v2
-; GFX9-NEXT:    v_mul_f32_e32 v3, v1, v3
+; GFX9-NEXT:    v_mul_f32_e32 v3, v3, v1
 ; GFX9-NEXT:    v_trunc_f32_e32 v3, v3
 ; GFX9-NEXT:    v_fma_f32 v1, -v3, v2, v1
 ; GFX9-NEXT:    global_store_dword v0, v1, s[4:5]
 ; GFX9-NEXT:    s_endpgm
 ;
 ; GFX10-LABEL: fast_frem_f32:
 ; GFX10:       ; %bb.0:
 ; GFX10-NEXT:    s_clause 0x1
 ; GFX10-NEXT:    s_load_dwordx4 s[4:7], s[0:1], 0x24
 ; GFX10-NEXT:    s_load_dwordx2 s[2:3], s[0:1], 0x34
 ; GFX10-NEXT:    v_mov_b32_e32 v0, 0
 ; GFX10-NEXT:    s_waitcnt lgkmcnt(0)
 ; GFX10-NEXT:    s_clause 0x1
 ; GFX10-NEXT:    global_load_dword v1, v0, s[6:7]
 ; GFX10-NEXT:    global_load_dword v2, v0, s[2:3] offset:16
 ; GFX10-NEXT:    s_waitcnt vmcnt(0)
 ; GFX10-NEXT:    v_rcp_f32_e32 v3, v2
-; GFX10-NEXT:    v_mul_f32_e32 v3, v1, v3
+; GFX10-NEXT:    v_mul_f32_e32 v3, v3, v1
 ; GFX10-NEXT:    v_trunc_f32_e32 v3, v3
 ; GFX10-NEXT:    v_fmac_f32_e64 v1, -v3, v2
 ; GFX10-NEXT:    global_store_dword v0, v1, s[4:5]
 ; GFX10-NEXT:    s_endpgm
                       float addrspace(1)* %in2) #0 {
    %gep2 = getelementptr float, float addrspace(1)* %in2, i32 4
    %r0 = load float, float addrspace(1)* %in1, align 4
    %r1 = load float, float addrspace(1)* %gep2, align 4

llvm/test/CodeGen/PowerPC/frem.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc -mtriple=powerpc64le -mcpu=pwr9 < %s | FileCheck %s
 
 define float @frem32(float %a, float %b) {
 ; CHECK-LABEL: frem32:
 ; CHECK:       # %bb.0: # %entry
-; CHECK-NEXT:    mflr 0
-; CHECK-NEXT:    std 0, 16(1)
-; CHECK-NEXT:    stdu 1, -32(1)
-; CHECK-NEXT:    .cfi_def_cfa_offset 32
-; CHECK-NEXT:    .cfi_offset lr, 16
-; CHECK-NEXT:    bl fmodf
-; CHECK-NEXT:    nop
-; CHECK-NEXT:    addi 1, 1, 32
-; CHECK-NEXT:    ld 0, 16(1)
-; CHECK-NEXT:    mtlr 0
+; CHECK-NEXT:    xsresp 0, 2
+; CHECK-NEXT:    fmr 4, 1
+; CHECK-NEXT:    xsmulsp 3, 1, 0
+; CHECK-NEXT:    xsnmsubasp 4, 2, 3
+; CHECK-NEXT:    xsmaddasp 3, 0, 4
+; CHECK-NEXT:    xsrdpiz 0, 3
+; CHECK-NEXT:    xsnmsubasp 1, 0, 2
 ; CHECK-NEXT:    blr
 entry:
   %rem = frem fast float %a, %b
   ret float %rem
 }
 
 define double @frem64(double %a, double %b) {
 ; CHECK-LABEL: frem64:
 ; CHECK:       # %bb.0: # %entry
-; CHECK-NEXT:    mflr 0
-; CHECK-NEXT:    std 0, 16(1)
-; CHECK-NEXT:    stdu 1, -32(1)
-; CHECK-NEXT:    .cfi_def_cfa_offset 32
-; CHECK-NEXT:    .cfi_offset lr, 16
-; CHECK-NEXT:    bl fmod
-; CHECK-NEXT:    nop
-; CHECK-NEXT:    addi 1, 1, 32
-; CHECK-NEXT:    ld 0, 16(1)
-; CHECK-NEXT:    mtlr 0
+; CHECK-NEXT:    addis 3, 2, .LCPI1_0@toc@ha
+; CHECK-NEXT:    xsredp 0, 2
+; CHECK-NEXT:    fmr 4, 1
+; CHECK-NEXT:    lfs 3, .LCPI1_0@toc@l(3)
+; CHECK-NEXT:    xsmaddadp 3, 2, 0
+; CHECK-NEXT:    xsnmsubadp 0, 0, 3
+; CHECK-NEXT:    xsmuldp 3, 1, 0
+; CHECK-NEXT:    xsnmsubadp 4, 2, 3
+; CHECK-NEXT:    xsmaddadp 3, 0, 4
+; CHECK-NEXT:    xsrdpiz 0, 3
+; CHECK-NEXT:    xsnmsubadp 1, 0, 2
 ; CHECK-NEXT:    blr
 entry:
   %rem = frem fast double %a, %b
   ret double %rem
 }
 
 define <4 x float> @frem4x32(<4 x float> %a, <4 x float> %b) {
 ; CHECK-LABEL: frem4x32:
 ; CHECK:       # %bb.0: # %entry
-; CHECK-NEXT:    mflr 0
-; CHECK-NEXT:    std 0, 16(1)
-; CHECK-NEXT:    stdu 1, -96(1)
-; CHECK-NEXT:    .cfi_def_cfa_offset 96
-; CHECK-NEXT:    .cfi_offset lr, 16
-; CHECK-NEXT:    .cfi_offset v28, -64
-; CHECK-NEXT:    .cfi_offset v29, -48
-; CHECK-NEXT:    .cfi_offset v30, -32
-; CHECK-NEXT:    .cfi_offset v31, -16
-; CHECK-NEXT:    xxsldwi 0, 34, 34, 3
-; CHECK-NEXT:    stxv 60, 32(1) # 16-byte Folded Spill
-; CHECK-NEXT:    xscvspdpn 1, 0
-; CHECK-NEXT:    xxsldwi 0, 35, 35, 3
-; CHECK-NEXT:    stxv 61, 48(1) # 16-byte Folded Spill
-; CHECK-NEXT:    stxv 62, 64(1) # 16-byte Folded Spill
-; CHECK-NEXT:    stxv 63, 80(1) # 16-byte Folded Spill
-; CHECK-NEXT:    xscvspdpn 2, 0
-; CHECK-NEXT:    vmr 31, 3
-; CHECK-NEXT:    vmr 30, 2
-; CHECK-NEXT:    bl fmodf
-; CHECK-NEXT:    nop
-; CHECK-NEXT:    xxsldwi 0, 62, 62, 1
-; CHECK-NEXT:    xscpsgndp 61, 1, 1
-; CHECK-NEXT:    xscvspdpn 1, 0
-; CHECK-NEXT:    xxsldwi 0, 63, 63, 1
-; CHECK-NEXT:    xscvspdpn 2, 0
-; CHECK-NEXT:    bl fmodf
-; CHECK-NEXT:    nop
-; CHECK-NEXT:    # kill: def $f1 killed $f1 def $vsl1
-; CHECK-NEXT:    xxmrghd 0, 1, 61
-; CHECK-NEXT:    xscvspdpn 1, 62
-; CHECK-NEXT:    xscvspdpn 2, 63
-; CHECK-NEXT:    xvcvdpsp 60, 0
-; CHECK-NEXT:    bl fmodf
-; CHECK-NEXT:    nop
-; CHECK-NEXT:    xxswapd 0, 62
-; CHECK-NEXT:    xscpsgndp 61, 1, 1
-; CHECK-NEXT:    xscvspdpn 1, 0
-; CHECK-NEXT:    xxswapd 0, 63
-; CHECK-NEXT:    xscvspdpn 2, 0
-; CHECK-NEXT:    bl fmodf
-; CHECK-NEXT:    nop
-; CHECK-NEXT:    # kill: def $f1 killed $f1 def $vsl1
-; CHECK-NEXT:    xxmrghd 0, 61, 1
-; CHECK-NEXT:    lxv 63, 80(1) # 16-byte Folded Reload
-; CHECK-NEXT:    lxv 62, 64(1) # 16-byte Folded Reload
-; CHECK-NEXT:    lxv 61, 48(1) # 16-byte Folded Reload
-; CHECK-NEXT:    xvcvdpsp 34, 0
-; CHECK-NEXT:    vmrgew 2, 2, 28
-; CHECK-NEXT:    lxv 60, 32(1) # 16-byte Folded Reload
-; CHECK-NEXT:    addi 1, 1, 96
-; CHECK-NEXT:    ld 0, 16(1)
-; CHECK-NEXT:    mtlr 0
+; CHECK-NEXT:    xvresp 0, 35
+; CHECK-NEXT:    vmr 4, 2
+; CHECK-NEXT:    xvmulsp 1, 34, 0
+; CHECK-NEXT:    xvnmsubasp 36, 35, 1
+; CHECK-NEXT:    xvmaddasp 1, 0, 36
+; CHECK-NEXT:    xvrspiz 0, 1
+; CHECK-NEXT:    xvnmsubasp 34, 0, 35
 ; CHECK-NEXT:    blr
 entry:
   %rem = frem fast <4 x float> %a, %b
   ret <4 x float> %rem
 }
 
 define <2 x double> @frem2x64(<2 x double> %a, <2 x double> %b) {
 ; CHECK-LABEL: frem2x64:
 ; CHECK:       # %bb.0: # %entry
-; CHECK-NEXT:    mflr 0
-; CHECK-NEXT:    std 0, 16(1)
-; CHECK-NEXT:    stdu 1, -80(1)
-; CHECK-NEXT:    .cfi_def_cfa_offset 80
-; CHECK-NEXT:    .cfi_offset lr, 16
-; CHECK-NEXT:    .cfi_offset v29, -48
-; CHECK-NEXT:    .cfi_offset v30, -32
-; CHECK-NEXT:    .cfi_offset v31, -16
-; CHECK-NEXT:    stxv 62, 48(1) # 16-byte Folded Spill
-; CHECK-NEXT:    stxv 63, 64(1) # 16-byte Folded Spill
-; CHECK-NEXT:    vmr 31, 3
-; CHECK-NEXT:    xscpsgndp 2, 63, 63
-; CHECK-NEXT:    vmr 30, 2
-; CHECK-NEXT:    xscpsgndp 1, 62, 62
-; CHECK-NEXT:    stxv 61, 32(1) # 16-byte Folded Spill
-; CHECK-NEXT:    bl fmod
-; CHECK-NEXT:    nop
-; CHECK-NEXT:    xscpsgndp 61, 1, 1
-; CHECK-NEXT:    xxswapd 1, 62
-; CHECK-NEXT:    xxswapd 2, 63
-; CHECK-NEXT:    # kill: def $f1 killed $f1 killed $vsl1
-; CHECK-NEXT:    # kill: def $f2 killed $f2 killed $vsl2
-; CHECK-NEXT:    bl fmod
-; CHECK-NEXT:    nop
-; CHECK-NEXT:    # kill: def $f1 killed $f1 def $vsl1
-; CHECK-NEXT:    xxmrghd 34, 61, 1
-; CHECK-NEXT:    lxv 63, 64(1) # 16-byte Folded Reload
-; CHECK-NEXT:    lxv 62, 48(1) # 16-byte Folded Reload
-; CHECK-NEXT:    lxv 61, 32(1) # 16-byte Folded Reload
-; CHECK-NEXT:    addi 1, 1, 80
-; CHECK-NEXT:    ld 0, 16(1)
-; CHECK-NEXT:    mtlr 0
+; CHECK-NEXT:    addis 3, 2, .LCPI3_0@toc@ha
+; CHECK-NEXT:    xvredp 0, 35
+; CHECK-NEXT:    vmr 4, 2
+; CHECK-NEXT:    addi 3, 3, .LCPI3_0@toc@l
+; CHECK-NEXT:    lxv 1, 0(3)
+; CHECK-NEXT:    xvmaddadp 1, 35, 0
+; CHECK-NEXT:    xvnmsubadp 0, 0, 1
+; CHECK-NEXT:    xvmuldp 1, 34, 0
+; CHECK-NEXT:    xvnmsubadp 36, 35, 1
+; CHECK-NEXT:    xvmaddadp 1, 0, 36
+; CHECK-NEXT:    xvrdpiz 0, 1
+; CHECK-NEXT:    xvnmsubadp 34, 0, 35
 ; CHECK-NEXT:    blr
 entry:
   %rem = frem fast <2 x double> %a, %b
   ret <2 x double> %rem
 }