public inbox for gcc-patches@gcc.gnu.org
 help / color / mirror / Atom feed
* [PATCH 0/9] Native complex operations
@ 2023-07-17  9:02 Sylvain Noiry
  2023-07-17  9:02 ` [PATCH 1/9] Native complex operations: Conditional lowering Sylvain Noiry
                   ` (8 more replies)
  0 siblings, 9 replies; 24+ messages in thread
From: Sylvain Noiry @ 2023-07-17  9:02 UTC (permalink / raw)
  To: gcc-patches; +Cc: Sylvain Noiry

Hi,

I have recently started a discussion about exposing complex operations directly
to the backends, to better exploit ISA with complex instructions. The title of 
the original message is "[RFC] Exposing complex numbers to target backends" [1].

This message starts a serie of 9 patches of the implementation that I've done. 
8 patches are about generic code, split by features. The last one is an 
experimental update of the x86 backend which exploits the newly exposed 
complex operations.

My original work was on the KVX backend from Kalray, where the ISA has complex
instructions. So I have obtained huge performance gains, on par with a code 
which uses builtins. On x86 there are gains without -ffast-math because less
calls to helpers are performed, but gains are marginal with -ffast-math due to
the lack of complex instructions.

[1] https://gcc.gnu.org/pipermail/gcc/2023-July/241998.html

Summary of the 9 patches:
  1/9: Conditional lowering of complex operations using the backend + update 
       on the TREE complex constants
  2/9: Move of read_complex_part and write_complex_part to target hooks to let
       the backend decide
  3/9: Add a gen_rtx_complex target hook to let the backend use its preferred 
       representation of complex in rtl
  4/9: Support and optimize the use of classical registers to represent complex
  5/9: Expose the conjugate operation down to the backend
  6/9: Expose and optimize complex rotations using internals functions and 
       conditional lowering
  7/9: Allow the vectorizer to work on complex type like it does on scalars
  8/9: Add explicit vectors of complex. This remains optional
  9/9: Experimental update on the x86 backend to exploit some of the previous
       features

The following sections explains the features added by each patch and 
illustrates them with examples on KVX, because of the backend support all the
new features. All examples are compiled with -O2 -ffast-math.

Patches 1 to 4 are required to have the minimal set of features which allows a
backend to exploit native complex operations.

PATCH 1/9: 
  - Change the TREE complex constants by adding a new field called "both" in 
    the tree_complex struct, which holds a vector of the real and imaginary 
    parts. This make the handling of constants during the cplxlower and expand
    passes easier. Any change to the one part will also affect the vector, 
    so very few changes are needed elsewhere.
  - Check in the optab for a complex pattern for almost all operations in the 
    cplxlower pass. The lowering is done only if an optab code is found. Some 
    conditions on presence on constants in the operands were also added, which 
    can be a subject of discussions.
  - Add a complex component for both parts in the cplxlower pass. When an 
    operation is lowered, the both part is recreated using a COMPLEX_EXPR. 
    When an operation is kept non-lowerd, real and imaginary parts are 
    extracted using REALPART_EXPR and IMAGPART_EXPR.

PATCH 2/9:
  - Move the inner implementation of read_complex_part and write_complex_part 
    to target hooks. This allows each backend to have its own implementation, 
    while the default ones are almost the same as before. Going back to 
    standard functions may be a point to discuss if no incompatible change are 
    done by the target to the default implementation.
  - Change the signature of read_complex_part and write_complex_part, to allow 
    both parts as a part. This affects all the calls to these functions.

PATCH 3/9:
  - Add a new target hook to replace gen_rtx_CONCAT when a complex element 
    needs to be created. The default implementation uses gen_rtx_CONCAT, but 
    the KVX implementation simply created a register with a complex type. 
    A previous attempt was to deal with generating_concat_p in gen_rtx_reg, 
    but no good solutions was found.

PATCH 4/9:
  - Adapt and optimize for the use of native complex operation in rtl, 
    aswell as register of complex types. After this patch, it's now possible 
    to re-implement the three new hooks and write some complex pattern. 
  
  Considering the following example:
  
    _Complex float mul(_Complex float a, _Complex float b)
    { 
      return a * b;
    }

  Previously, the generated code was:
    mul:
        copyw $r3 = $r0
        extfz $r5 = $r0, 32+32-1, 32 ; extract imag part
        ;;      # (end cycle 0)
        fmulw $r4 = $r3, $r1         ; float mul
        ;;      # (end cycle 1)
        fmulw $r2 = $r5, $r1         ; float mul
        extfz $r1 = $r1, 32+32-1, 32 ; extract real part
        ;;      # (end cycle 2)      
        ffmsw $r4 = $r5, $r1         ; float FMS
        ;;      # (end cycle 5)
        ffmaw $r2 = $r3, $r1	     : float FMA
        ;;      # (end cycle 6)
        insf $r0 = $r4, 32+0-1, 0    ; insert real part
        ;;      # (end cycle 9)
        insf $r0 = $r2, 32+32-1, 32  ; insert imag part
        ret
        ;;      # (end cycle 10)

  The KVX has a complex float multiplication instruction, so now the result is:
    mul:
	fmulwc $r0 = $r0, $r1        ; float complex mul
	ret
	;;	# (end cycle 0)

  Similar results are obtains for additions, subtractions, and negations.

  Moreover, if complex FMA and FMS patterns are defined, these operations will 
  be caught exactly like scalars. Indeed most passes of GCC will work out of 
  the box for complex types.


PATCH 5/9:
  - Expose the complex conjugate operation to backend. This is done through a 
    new conj optab and a new conj rtl operation. CONJ_EXPR can now be kept and 
    expanded if a conj pattern exists.

  considering the following example:
    
    _Complex float conjugate(_Complex float a)
      { 
	return ~a;
      }

  Previously, the generated code was:
    conjugate:
        extfz $r1 = $r0, 32+32-1, 32 ; extract imag part
        copyw $r2 = $r0
        ;;      # (end cycle 0)
        fnegw $r1 = $r1		     ; float negate
        insf $r0 = $r2, 32+0-1, 0    ; insert real part
        ;;      # (end cycle 1)
        insf $r0 = $r1, 32+32-1, 32  ; insert imag part
        ret
        ;;      # (end cycle 2)

  Now, considering that the imag part is in the upper part of a 64-bit register, 
  the generated code is:
    conjugate:
	fnegd $r0 = $r0              ; double negate
	ret
	;;	# (end cycle 0)

  The KVX can also conjugate one operand before doing an operation. The backend 
  programmer only has to write the pattern and the combiner pass is now able to
  catch it. For the following example:
 
     _Complex float mulc(_Complex float a, _Complex float b)
      { 
        return a * ~b;
      }

  The generated code is:
    mulc:
	fmulwc.c $r0 = $r1, $r0 ; complex mul with conj
	ret
	;;	# (end cycle 0)

PATCH 6/9:
  - Catch complex rotation by 90° and 270° in fold-const.cc like before, but 
    now convert them into the new COMPLEX_ROT90 and COMPLEX_ROT270 internal 
    functions
  - Add crot90 and crot270 optabs to expose these operation the backends.
  - Conditionnaly lower COMPLEX_ROT90/COMPLEX_ROT270 by checking if 
    crot90/crot270 are in the optab
  - convert a + crot90/270(b) into cadd90/270(a, b) in a similar way than FMAs.
    This approach is different than the one implement a few years ago by 
    Tamar Christina. The main advantage is that it does not try to recognize 
    a rotation among the lowered operations, so there are less misses.

  Considering the following example:
    _Complex float crot90(_Complex float a)
      { 
	return a * I;
      }

  Previously the generated code was:
    rot90:
        extfz $r1 = $r0, 32+32-1, 32 ; extract imag part
        copyw $r2 = $r0	
        ;;      # (end cycle 0)
        fnegw $r1 = $r1		     ; float negate
        ;;      # (end cycle 1)
        insf $r0 = $r1, 32+0-1, 0    ; insert real part
        ;;      # (end cycle 5)
        insf $r0 = $r2, 32+32-1, 32  ; insert imag part
        ret
        ;;      # (end cycle 6)

  Even if the KVX does not have a unique instruction for the complex rotation,
  a define_expand pattern can already bring gains:
    crot90:
	fnegd $r0 = $r0		     	    ; double negate
	;;	# (end cycle 0)
	sbmm8 $r0 = $r0, 0x0804020180402010 ; swap real imag
	ret
	;;	# (end cycle 1)


PATCH 7/9:
  - Add vector of complex inner types
  - Adapt or duplicate several functions and target hooks to deal with vectors 
    of complex and not just scalars.
  
  After these changes the vectorize works out of box for native complex 
  operations. Considering the following example:
    void
    fmaconjcplx (float complex a[restrict N], float complex b[restrict N],
	         float complex c[restrict N], float complex d[restrict N])
    {
      for (int i = 0; i < N; i++)
	d[i] = c[i] + a[i] * b[i];
    }

  The vectorizer has done its job and the KVX has some SIMD complex 
  instructions, so the result is:
    fmacplx:
        make $r4 = 0
        make $r5 = 32
        ;;      # (end cycle 0)
        loopdo $r5, .L56               ; begin hardware loop
        ;;      # (end cycle 1)
    .L53:
        lq.xs $r10r11 = $r4[$r1]       ; load 128-bit
        ;;      # (end cycle 0)
        lq.xs $r8r9 = $r4[$r0]	       ; load 128-bit
        ;;      # (end cycle 1)
        lq.xs $r6r7 = $r4[$r2]	       ; load 128-bit
        ;;      # (end cycle 2)
        ffmawcp $r6r7 = $r10r11, $r8r9 ; float complex FMA two lanes
        ;;      # (end cycle 5)
        sq.xs $r4[$r3] = $r6r7	       ; store 128-bit
        addd $r4 = $r4, 1
        ;;      # (end cycle 8)
        # loopdo end
    .L56:
        ret

PATCH 8/9:
  - allow the creation of explicit complex vectors in C using 
    __attribute__ ((vector_size ()))

  This patch adds a feature in C, so it's optional and has more implications
  than just GCC.

PATCH 9/9:
  - Experimental support of complex operation in the x86 backend
  - Only in SCmode for now
  - Add (scalar) addition, subtraction, negation, conjugate, move, and mult

  Small examples can show interesting gains even if there is no complex 
  instruction on x86. However the patterns can be implemented using multiple
  instructions in a define_expand. Considering the same complex multiplication
  as the first example compiled with -mavx, the generated code can is:
    mul:
	vshufps	$20, %xmm1, %xmm1, %xmm1
	vshufps	$68, %xmm0, %xmm0, %xmm0 
	vmulps	%xmm1, %xmm0, %xmm0
	vshufps	$13, %xmm0, %xmm0, %xmm1
	vshufps	$8, %xmm0, %xmm0, %xmm0
	vaddsubps %xmm1, %xmm0, %xmm0
	ret

  Howether complete tests like an FFTs only show marginal gains. Huge gains can
  be although be obtained without -ffast-math. But it is still experimental and
  I am not an expert of the x86 backend, so improvement are certainly possible.

Thanks,

Sylvain
  
  

































^ permalink raw reply	[flat|nested] 24+ messages in thread
end of thread, other threads:[~2023-09-13  6:50 UTC | newest]

Thread overview: 24+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2023-07-17  9:02 [PATCH 0/9] Native complex operations Sylvain Noiry
2023-07-17  9:02 ` [PATCH 1/9] Native complex operations: Conditional lowering Sylvain Noiry
2023-07-17  9:02 ` [PATCH 2/9] Native complex operations: Move functions to hooks Sylvain Noiry
2023-07-17  9:02 ` [PATCH 3/9] Native complex operations: Add gen_rtx_complex hook Sylvain Noiry
2023-07-17  9:02 ` [PATCH 4/9] Native complex operations: Allow native complex regs and ops in rtl Sylvain Noiry
2023-07-17  9:02 ` [PATCH 5/9] Native complex operations: Add the conjugate op in optabs Sylvain Noiry
2023-07-17  9:02 ` [PATCH 6/9] Native complex operations: Update how complex rotations are handled Sylvain Noiry
2023-07-17  9:02 ` [PATCH 7/9] Native complex operations: Vectorization of native complex operations Sylvain Noiry
2023-07-17  9:02 ` [PATCH 8/9] Native complex operations: Add explicit vector of complex Sylvain Noiry
2023-07-17  9:02 ` [PATCH 9/9] Native complex operation: Experimental support in x86 backend Sylvain Noiry
2023-09-12 10:07   ` [PATCH v2 0/11] Native complex operations Sylvain Noiry
2023-09-12 10:07     ` [PATCH v2 01/11] Native complex ops : Conditional lowering Sylvain Noiry
2023-09-12 10:07     ` [PATCH v2 02/11] Native complex ops: Move functions to hooks Sylvain Noiry
2023-09-12 10:07     ` [PATCH v2 03/11] Native complex ops: Add gen_rtx_complex hook Sylvain Noiry
2023-09-12 10:07     ` [PATCH v2 04/11] Native complex ops: Allow native complex regs and ops in rtl Sylvain Noiry
2023-09-12 10:07     ` [PATCH v2 05/11] Native complex ops: Add the conjugate op in optabs Sylvain Noiry
2023-09-12 10:07     ` [PATCH v2 06/11] Native complex ops: Update how complex rotations are handled Sylvain Noiry
2023-09-12 10:07     ` [PATCH v2 07/11] Native complex ops: Vectorization of native complex operations Sylvain Noiry
2023-09-12 10:07     ` [PATCH v2 08/11] Native complex ops: Add explicit vector of complex Sylvain Noiry
2023-09-12 17:25       ` Joseph Myers
2023-09-13  6:48         ` Richard Biener
2023-09-12 10:07     ` [PATCH v2 09/11] Native complex ops: remove useless special cases Sylvain Noiry
2023-09-12 10:07     ` [PATCH v2 10/11] Native complex ops: Add a fast complex multiplication pattern Sylvain Noiry
2023-09-12 10:07     ` [PATCH v2 11/11] Native complex ops: Experimental support in x86 backend Sylvain Noiry

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).