[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 (SDValue C = DAG.FoldConstantArithmetic(ISD::FREM, SDLoc(N), VT, {N0, N1}))
     return C;
 
   if (SDValue NewSel = foldBinOpIntoSelect(N))
     return NewSel;
 
+  // (frem x, y) -> (fma (fneg (ftrunc (fdiv x, y))), y, x)
+  if (Flags.hasApproximateFuncs() && Flags.hasNoSignedZeros() &&
+      Flags.hasNoInfs() && !TLI.isOperationLegalOrCustom(ISD::FREM, VT) &&
+      TLI.isOperationLegalOrCustom(ISD::FTRUNC, VT) &&
+      TLI.isOperationLegalOrCustom(ISD::FMA, VT)) {
+    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:

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:    stdu 1, -32(1)
-; CHECK-NEXT:    std 0, 48(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:    stdu 1, -32(1)
-; CHECK-NEXT:    std 0, 48(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:    vspltisw 2, -1
+; CHECK-NEXT:    xsredp 0, 2
+; CHECK-NEXT:    fmr 4, 1
+; CHECK-NEXT:    xvcvsxwdp 3, 34
+; 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:    stdu 1, -96(1)
-; CHECK-NEXT:    std 0, 112(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:    stdu 1, -80(1)
-; CHECK-NEXT:    std 0, 96(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
 }