[RFC/RFA] [PATCH 02/12] Add built-ins and tests for bit-forward and bit-reversed CRCs

[RFC/RFA] [PATCH 02/12] Add built-ins and tests for bit-forward and bit-reversed CRCs

[Mariam Arutunian]

[-- Attachment #1.1: Type: text/plain, Size: 4649 bytes --]

This patch introduces new built-in functions to GCC for computing
bit-forward and bit-reversed CRCs.
These builtins aim to provide efficient CRC calculation capabilities.
When the target architecture supports CRC operations (as indicated by the
presence of a CRC optab),
the builtins will utilize the expander to generate CRC code.
In the absence of hardware support, the builtins default to generating code
for a table-based CRC calculation.

The builtins are defined as follows:
__builtin_rev_crc16_data8,
__builtin_rev_crc32_data8, __builtin_rev_crc32_data16,
__builtin_rev_crc32_data32
__builtin_crc8_data8,
__builtin_crc16_data16, __builtin_crc16_data8,
__builtin_crc32_data8, __builtin_crc32_data16, __builtin_crc32_data32,
__builtin_crc64_data8, __builtin_crc64_data16,  __builtin_crc64_data32,
__builtin_crc64_data64

Each builtin takes three parameters:
crc: The initial CRC value.
data: The data to be processed.
polynomial: The CRC polynomial without the leading 1.

To validate the correctness of these builtins, this patch also includes
additions to the GCC testsuite.
This enhancement allows GCC to offer developers high-performance CRC
computation options
that automatically adapt to the capabilities of the target hardware.

Co-authored-by: Joern Rennecke <joern.rennecke@embecosm.com>

Not complete. May continue the work if these built-ins are needed.

gcc/

 * builtin-types.def (BT_FN_UINT8_UINT8_UINT8_CONST_SIZE): Define.
 (BT_FN_UINT16_UINT16_UINT8_CONST_SIZE): Likewise.
          (BT_FN_UINT16_UINT16_UINT16_CONST_SIZE): Likewise.
          (BT_FN_UINT32_UINT32_UINT8_CONST_SIZE): Likewise.
          (BT_FN_UINT32_UINT32_UINT16_CONST_SIZE): Likewise.
          (BT_FN_UINT32_UINT32_UINT32_CONST_SIZE): Likewise.
          (BT_FN_UINT64_UINT64_UINT8_CONST_SIZE): Likewise.
          (BT_FN_UINT64_UINT64_UINT16_CONST_SIZE): Likewise.
          (BT_FN_UINT64_UINT64_UINT32_CONST_SIZE): Likewise.
          (BT_FN_UINT64_UINT64_UINT64_CONST_SIZE): Likewise.
          * builtins.cc (associated_internal_fn): Handle
BUILT_IN_CRC8_DATA8,
          BUILT_IN_CRC16_DATA8, BUILT_IN_CRC16_DATA16,
          BUILT_IN_CRC32_DATA8, BUILT_IN_CRC32_DATA16,
BUILT_IN_CRC32_DATA32,
          BUILT_IN_CRC64_DATA8, BUILT_IN_CRC64_DATA16,
BUILT_IN_CRC64_DATA32,
          BUILT_IN_CRC64_DATA64,
          BUILT_IN_REV_CRC8_DATA8,
          BUILT_IN_REV_CRC16_DATA8, BUILT_IN_REV_CRC16_DATA16,
          BUILT_IN_REV_CRC32_DATA8, BUILT_IN_REV_CRC32_DATA16,
BUILT_IN_REV_CRC32_DATA32.
          (expand_builtin_crc_table_based): New function.
          (expand_builtin): Handle BUILT_IN_CRC8_DATA8,
          BUILT_IN_CRC16_DATA8, BUILT_IN_CRC16_DATA16,
          BUILT_IN_CRC32_DATA8, BUILT_IN_CRC32_DATA16,
BUILT_IN_CRC32_DATA32,
          BUILT_IN_CRC64_DATA8, BUILT_IN_CRC64_DATA16,
BUILT_IN_CRC64_DATA32,
          BUILT_IN_CRC64_DATA64,
          BUILT_IN_REV_CRC8_DATA8,
          BUILT_IN_REV_CRC16_DATA8, BUILT_IN_REV_CRC16_DATA16,
          BUILT_IN_REV_CRC32_DATA8, BUILT_IN_REV_CRC32_DATA16,
BUILT_IN_REV_CRC32_DATA32.
          * builtins.def (BUILT_IN_CRC8_DATA8): New builtin.
          (BUILT_IN_CRC16_DATA8): Likewise.
          (BUILT_IN_CRC16_DATA16): Likewise.
          (BUILT_IN_CRC32_DATA8): Likewise.
          (BUILT_IN_CRC32_DATA16): Likewise.
          (BUILT_IN_CRC32_DATA32): Likewise.
          (BUILT_IN_CRC64_DATA8): Likewise.
          (BUILT_IN_CRC64_DATA16): Likewise.
          (BUILT_IN_CRC64_DATA32): Likewise.
          (BUILT_IN_CRC64_DATA64): Likewise.
          (BUILT_IN_REV_CRC8_DATA8): New builtin.
          (BUILT_IN_REV_CRC16_DATA8): Likewise.
          (BUILT_IN_REV_CRC16_DATA16): Likewise.
          (BUILT_IN_REV_CRC32_DATA8): Likewise.
          (BUILT_IN_REV_CRC32_DATA16): Likewise.
          (BUILT_IN_REV_CRC32_DATA32): Likewise.
          * builtins.h (expand_builtin_crc_table_based): New function
declaration.
          * doc/extend.texti (__builtin_rev_crc16_data8,
          (__builtin_rev_crc32_data32, __builtin_rev_crc32_data8,
          __builtin_rev_crc32_data16, __builtin_crc8_data8,
          __builtin_crc16_data16, __builtin_crc16_data8,
          __builtin_crc32_data32, __builtin_crc32_data8,
          __builtin_crc32_data16, __builtin_crc64_data64,
          __builtin_crc64_data8, __builtin_crc64_data16,
          __builtin_crc64_data32): Document.

      gcc/testsuite/

         * gcc.c-torture/compile/crc-builtin-rev-target32.c
         * gcc.c-torture/compile/crc-builtin-rev-target64.c
         * gcc.c-torture/compile/crc-builtin-target32.c
         * gcc.c-torture/compile/crc-builtin-target64.c

Signed-off-by: Mariam Arutunian <mariamarutunian@gmail.com>

[-- Attachment #2: 0002-Add-built-ins-and-tests-for-bit-forward-and-bit-reve.patch --]
[-- Type: application/x-patch, Size: 19880 bytes --]

Re: [RFC/RFA] [PATCH 02/12] Add built-ins and tests for bit-forward and bit-reversed CRCs

[Jeff Law]

On 5/24/24 2:41 AM, Mariam Arutunian wrote:
> This patch introduces new built-in functions to GCC for computing bit- 
> forward and bit-reversed CRCs.
> These builtins aim to provide efficient CRC calculation capabilities.
> When the target architecture supports CRC operations (as indicated by 
> the presence of a CRC optab),
> the builtins will utilize the expander to generate CRC code.
> In the absence of hardware support, the builtins default to generating 
> code for a table-based CRC calculation.
> 
> The builtins are defined as follows:
> __builtin_rev_crc16_data8,
> __builtin_rev_crc32_data8, __builtin_rev_crc32_data16, 
> __builtin_rev_crc32_data32
> __builtin_crc8_data8,
> __builtin_crc16_data16, __builtin_crc16_data8,
> __builtin_crc32_data8, __builtin_crc32_data16, __builtin_crc32_data32,
> __builtin_crc64_data8, __builtin_crc64_data16,  __builtin_crc64_data32, 
> __builtin_crc64_data64
> 
> Each builtin takes three parameters:
> crc: The initial CRC value.
> data: The data to be processed.
> polynomial: The CRC polynomial without the leading 1.
> 
> To validate the correctness of these builtins, this patch also includes 
> additions to the GCC testsuite.
> This enhancement allows GCC to offer developers high-performance CRC 
> computation options
> that automatically adapt to the capabilities of the target hardware.
> 
> Co-authored-by: Joern Rennecke <joern.rennecke@embecosm.com 
> <mailto:joern.rennecke@embecosm.com>>
> 
> Not complete. May continue the work if these built-ins are needed.
> 
> gcc/
> 
>   * builtin-types.def (BT_FN_UINT8_UINT8_UINT8_CONST_SIZE): Define.
>   (BT_FN_UINT16_UINT16_UINT8_CONST_SIZE): Likewise.
>            (BT_FN_UINT16_UINT16_UINT16_CONST_SIZE): Likewise.
>            (BT_FN_UINT32_UINT32_UINT8_CONST_SIZE): Likewise.
>            (BT_FN_UINT32_UINT32_UINT16_CONST_SIZE): Likewise.
>            (BT_FN_UINT32_UINT32_UINT32_CONST_SIZE): Likewise.
>            (BT_FN_UINT64_UINT64_UINT8_CONST_SIZE): Likewise.
>            (BT_FN_UINT64_UINT64_UINT16_CONST_SIZE): Likewise.
>            (BT_FN_UINT64_UINT64_UINT32_CONST_SIZE): Likewise.
>            (BT_FN_UINT64_UINT64_UINT64_CONST_SIZE): Likewise.
>            * builtins.cc (associated_internal_fn): Handle 
> BUILT_IN_CRC8_DATA8,
>            BUILT_IN_CRC16_DATA8, BUILT_IN_CRC16_DATA16,
>            BUILT_IN_CRC32_DATA8, BUILT_IN_CRC32_DATA16, 
> BUILT_IN_CRC32_DATA32,
>            BUILT_IN_CRC64_DATA8, BUILT_IN_CRC64_DATA16, 
> BUILT_IN_CRC64_DATA32,
>            BUILT_IN_CRC64_DATA64,
>            BUILT_IN_REV_CRC8_DATA8,
>            BUILT_IN_REV_CRC16_DATA8, BUILT_IN_REV_CRC16_DATA16,
>            BUILT_IN_REV_CRC32_DATA8, BUILT_IN_REV_CRC32_DATA16, 
> BUILT_IN_REV_CRC32_DATA32.
>            (expand_builtin_crc_table_based): New function.
>            (expand_builtin): Handle BUILT_IN_CRC8_DATA8,
>            BUILT_IN_CRC16_DATA8, BUILT_IN_CRC16_DATA16,
>            BUILT_IN_CRC32_DATA8, BUILT_IN_CRC32_DATA16, 
> BUILT_IN_CRC32_DATA32,
>            BUILT_IN_CRC64_DATA8, BUILT_IN_CRC64_DATA16, 
> BUILT_IN_CRC64_DATA32,
>            BUILT_IN_CRC64_DATA64,
>            BUILT_IN_REV_CRC8_DATA8,
>            BUILT_IN_REV_CRC16_DATA8, BUILT_IN_REV_CRC16_DATA16,
>            BUILT_IN_REV_CRC32_DATA8, BUILT_IN_REV_CRC32_DATA16, 
> BUILT_IN_REV_CRC32_DATA32.
>            * builtins.def (BUILT_IN_CRC8_DATA8): New builtin.
>            (BUILT_IN_CRC16_DATA8): Likewise.
>            (BUILT_IN_CRC16_DATA16): Likewise.
>            (BUILT_IN_CRC32_DATA8): Likewise.
>            (BUILT_IN_CRC32_DATA16): Likewise.
>            (BUILT_IN_CRC32_DATA32): Likewise.
>            (BUILT_IN_CRC64_DATA8): Likewise.
>            (BUILT_IN_CRC64_DATA16): Likewise.
>            (BUILT_IN_CRC64_DATA32): Likewise.
>            (BUILT_IN_CRC64_DATA64): Likewise.
>            (BUILT_IN_REV_CRC8_DATA8): New builtin.
>            (BUILT_IN_REV_CRC16_DATA8): Likewise.
>            (BUILT_IN_REV_CRC16_DATA16): Likewise.
>            (BUILT_IN_REV_CRC32_DATA8): Likewise.
>            (BUILT_IN_REV_CRC32_DATA16): Likewise.
>            (BUILT_IN_REV_CRC32_DATA32): Likewise.
>            * builtins.h (expand_builtin_crc_table_based): New function 
> declaration.
>            * doc/extend.texti (__builtin_rev_crc16_data8,
>            (__builtin_rev_crc32_data32, __builtin_rev_crc32_data8,
>            __builtin_rev_crc32_data16, __builtin_crc8_data8,
>            __builtin_crc16_data16, __builtin_crc16_data8,
>            __builtin_crc32_data32, __builtin_crc32_data8,
>            __builtin_crc32_data16, __builtin_crc64_data64,
>            __builtin_crc64_data8, __builtin_crc64_data16,
>            __builtin_crc64_data32): Document.
> 
>        gcc/testsuite/
> 
>           * gcc.c-torture/compile/crc-builtin-rev-target32.c
>           * gcc.c-torture/compile/crc-builtin-rev-target64.c
>           * gcc.c-torture/compile/crc-builtin-target32.c
>           * gcc.c-torture/compile/crc-builtin-target64.c
> 
> Signed-off-by: Mariam Arutunian <mariamarutunian@gmail.com 
> <mailto:mariamarutunian@gmail.com>>

> diff --git a/gcc/builtins.cc b/gcc/builtins.cc
> index f8d94c4b435..b662de91e49 100644
> --- a/gcc/builtins.cc
> +++ b/gcc/builtins.cc
> @@ -2207,7 +2207,24 @@ associated_internal_fn (built_in_function fn, tree return_type)
>        if (REAL_MODE_FORMAT (TYPE_MODE (return_type))->b == 2)
>  	return IFN_LDEXP;
>        return IFN_LAST;
> -
> +    case BUILT_IN_CRC8_DATA8:
> +    case BUILT_IN_CRC16_DATA8:
> +    case BUILT_IN_CRC16_DATA16:
> +    case BUILT_IN_CRC32_DATA8:
> +    case BUILT_IN_CRC32_DATA16:
> +    case BUILT_IN_CRC32_DATA32:
> +    case BUILT_IN_CRC64_DATA8:
> +    case BUILT_IN_CRC64_DATA16:
> +    case BUILT_IN_CRC64_DATA32:
> +    case BUILT_IN_CRC64_DATA64:
> +      return IFN_CRC;
> +    case BUILT_IN_REV_CRC8_DATA8:
> +    case BUILT_IN_REV_CRC16_DATA8:
> +    case BUILT_IN_REV_CRC16_DATA16:
> +    case BUILT_IN_REV_CRC32_DATA8:
> +    case BUILT_IN_REV_CRC32_DATA16:
> +    case BUILT_IN_REV_CRC32_DATA32:
> +      return IFN_CRC_REV;
So no REV_CRC64?  Just want to make sure it's intentional and not an 
oversight.



> @@ -7751,6 +7768,37 @@ expand_speculation_safe_value (machine_mode mode, tree exp, rtx target,
>    return targetm.speculation_safe_value (mode, target, val, failsafe);
>  }
>  
> +/* Expand CRC* or REV_CRC* built-ins.  */
> +
> +rtx
> +expand_builtin_crc_table_based (internal_fn fn, machine_mode data_mode,
> +				machine_mode crc_mode, machine_mode mode,
> +				tree exp, rtx target)
Line up parameters.


> +{
> +  tree rhs1 = CALL_EXPR_ARG (exp, 0); // crc
> +  tree rhs2 = CALL_EXPR_ARG (exp, 1); // data
> +  tree rhs3 = CALL_EXPR_ARG (exp, 2); // polynomial
> +
> +  gcc_assert (word_mode >= crc_mode);
> +
> +  if (!target || mode == VOIDmode)
> +    target = gen_reg_rtx (crc_mode);
I'm kindof curious, did we ever see a case where mode was VOIDmode? 
Would that check be better as a gcc_assert?


> +
> +  rtx op1 = expand_normal (rhs1);
> +  rtx op2 = expand_normal (rhs2);
> +  gcc_assert (TREE_CODE (rhs3) == INTEGER_CST);
> +  rtx op3 = gen_rtx_CONST_INT (crc_mode, TREE_INT_CST_LOW (rhs3));
I think we probably want to use gen_int_mode rather than gen_rtx_CONST_INT.


> diff --git a/gcc/builtins.h b/gcc/builtins.h
> index 8d93f75a9a4..e94dec68ed2 100644
> --- a/gcc/builtins.h
> +++ b/gcc/builtins.h
> @@ -133,6 +133,9 @@ extern void expand_builtin_trap (void);
>  extern void expand_ifn_atomic_bit_test_and (gcall *);
>  extern void expand_ifn_atomic_compare_exchange (gcall *);
>  extern void expand_ifn_atomic_op_fetch_cmp_0 (gcall *);
> +extern rtx expand_builtin_crc_table_based (internal_fn, machine_mode,
> +					   machine_mode, machine_mode,
> +					   tree, rtx);
The usual formatting nit here :-)

Generally pretty good.  Please repost after fixing the issues noted 
above.  Thanks.

jeff

Re: [RFC/RFA] [PATCH 02/12] Add built-ins and tests for bit-forward and bit-reversed CRCs

[Richard Biener]

On Fri, May 24, 2024 at 10:44 AM Mariam Arutunian
<mariamarutunian@gmail.com> wrote:
>
> This patch introduces new built-in functions to GCC for computing bit-forward and bit-reversed CRCs.
> These builtins aim to provide efficient CRC calculation capabilities.
> When the target architecture supports CRC operations (as indicated by the presence of a CRC optab),
> the builtins will utilize the expander to generate CRC code.
> In the absence of hardware support, the builtins default to generating code for a table-based CRC calculation.

I wonder whether for embedded target use we should arrange for the
table-based CRC calculation
to be out-of-line and implemented in a way so uses across TUs can be
merged?  I guess a generic implementation
inside libgcc is difficult?

>
> The builtins are defined as follows:
> __builtin_rev_crc16_data8,
> __builtin_rev_crc32_data8, __builtin_rev_crc32_data16, __builtin_rev_crc32_data32
> __builtin_crc8_data8,
> __builtin_crc16_data16, __builtin_crc16_data8,
> __builtin_crc32_data8, __builtin_crc32_data16, __builtin_crc32_data32,
> __builtin_crc64_data8, __builtin_crc64_data16,  __builtin_crc64_data32, __builtin_crc64_data64
>
> Each builtin takes three parameters:
> crc: The initial CRC value.
> data: The data to be processed.
> polynomial: The CRC polynomial without the leading 1.
>
> To validate the correctness of these builtins, this patch also includes additions to the GCC testsuite.
> This enhancement allows GCC to offer developers high-performance CRC computation options
> that automatically adapt to the capabilities of the target hardware.
>
> Co-authored-by: Joern Rennecke <joern.rennecke@embecosm.com>
>
> Not complete. May continue the work if these built-ins are needed.
>
> gcc/
>
>  * builtin-types.def (BT_FN_UINT8_UINT8_UINT8_CONST_SIZE): Define.
>  (BT_FN_UINT16_UINT16_UINT8_CONST_SIZE): Likewise.
>           (BT_FN_UINT16_UINT16_UINT16_CONST_SIZE): Likewise.
>           (BT_FN_UINT32_UINT32_UINT8_CONST_SIZE): Likewise.
>           (BT_FN_UINT32_UINT32_UINT16_CONST_SIZE): Likewise.
>           (BT_FN_UINT32_UINT32_UINT32_CONST_SIZE): Likewise.
>           (BT_FN_UINT64_UINT64_UINT8_CONST_SIZE): Likewise.
>           (BT_FN_UINT64_UINT64_UINT16_CONST_SIZE): Likewise.
>           (BT_FN_UINT64_UINT64_UINT32_CONST_SIZE): Likewise.
>           (BT_FN_UINT64_UINT64_UINT64_CONST_SIZE): Likewise.
>           * builtins.cc (associated_internal_fn): Handle BUILT_IN_CRC8_DATA8,
>           BUILT_IN_CRC16_DATA8, BUILT_IN_CRC16_DATA16,
>           BUILT_IN_CRC32_DATA8, BUILT_IN_CRC32_DATA16, BUILT_IN_CRC32_DATA32,
>           BUILT_IN_CRC64_DATA8, BUILT_IN_CRC64_DATA16, BUILT_IN_CRC64_DATA32,
>           BUILT_IN_CRC64_DATA64,
>           BUILT_IN_REV_CRC8_DATA8,
>           BUILT_IN_REV_CRC16_DATA8, BUILT_IN_REV_CRC16_DATA16,
>           BUILT_IN_REV_CRC32_DATA8, BUILT_IN_REV_CRC32_DATA16, BUILT_IN_REV_CRC32_DATA32.
>           (expand_builtin_crc_table_based): New function.
>           (expand_builtin): Handle BUILT_IN_CRC8_DATA8,
>           BUILT_IN_CRC16_DATA8, BUILT_IN_CRC16_DATA16,
>           BUILT_IN_CRC32_DATA8, BUILT_IN_CRC32_DATA16, BUILT_IN_CRC32_DATA32,
>           BUILT_IN_CRC64_DATA8, BUILT_IN_CRC64_DATA16, BUILT_IN_CRC64_DATA32,
>           BUILT_IN_CRC64_DATA64,
>           BUILT_IN_REV_CRC8_DATA8,
>           BUILT_IN_REV_CRC16_DATA8, BUILT_IN_REV_CRC16_DATA16,
>           BUILT_IN_REV_CRC32_DATA8, BUILT_IN_REV_CRC32_DATA16, BUILT_IN_REV_CRC32_DATA32.
>           * builtins.def (BUILT_IN_CRC8_DATA8): New builtin.
>           (BUILT_IN_CRC16_DATA8): Likewise.
>           (BUILT_IN_CRC16_DATA16): Likewise.
>           (BUILT_IN_CRC32_DATA8): Likewise.
>           (BUILT_IN_CRC32_DATA16): Likewise.
>           (BUILT_IN_CRC32_DATA32): Likewise.
>           (BUILT_IN_CRC64_DATA8): Likewise.
>           (BUILT_IN_CRC64_DATA16): Likewise.
>           (BUILT_IN_CRC64_DATA32): Likewise.
>           (BUILT_IN_CRC64_DATA64): Likewise.
>           (BUILT_IN_REV_CRC8_DATA8): New builtin.
>           (BUILT_IN_REV_CRC16_DATA8): Likewise.
>           (BUILT_IN_REV_CRC16_DATA16): Likewise.
>           (BUILT_IN_REV_CRC32_DATA8): Likewise.
>           (BUILT_IN_REV_CRC32_DATA16): Likewise.
>           (BUILT_IN_REV_CRC32_DATA32): Likewise.
>           * builtins.h (expand_builtin_crc_table_based): New function declaration.
>           * doc/extend.texti (__builtin_rev_crc16_data8,
>           (__builtin_rev_crc32_data32, __builtin_rev_crc32_data8,
>           __builtin_rev_crc32_data16, __builtin_crc8_data8,
>           __builtin_crc16_data16, __builtin_crc16_data8,
>           __builtin_crc32_data32, __builtin_crc32_data8,
>           __builtin_crc32_data16, __builtin_crc64_data64,
>           __builtin_crc64_data8, __builtin_crc64_data16,
>           __builtin_crc64_data32): Document.
>
>       gcc/testsuite/
>
>          * gcc.c-torture/compile/crc-builtin-rev-target32.c
>          * gcc.c-torture/compile/crc-builtin-rev-target64.c
>          * gcc.c-torture/compile/crc-builtin-target32.c
>          * gcc.c-torture/compile/crc-builtin-target64.c
>
> Signed-off-by: Mariam Arutunian <mariamarutunian@gmail.com>

Re: [RFC/RFA] [PATCH 02/12] Add built-ins and tests for bit-forward and bit-reversed CRCs

[Jeff Law]

On 5/27/24 12:38 AM, Richard Biener wrote:
> On Fri, May 24, 2024 at 10:44 AM Mariam Arutunian
> <mariamarutunian@gmail.com> wrote:
>>
>> This patch introduces new built-in functions to GCC for computing bit-forward and bit-reversed CRCs.
>> These builtins aim to provide efficient CRC calculation capabilities.
>> When the target architecture supports CRC operations (as indicated by the presence of a CRC optab),
>> the builtins will utilize the expander to generate CRC code.
>> In the absence of hardware support, the builtins default to generating code for a table-based CRC calculation.
> 
> I wonder whether for embedded target use we should arrange for the 
> table-based CRC calculation to be out-of-line and implemented in a
> way so uses across TUs can be merged?  I guess a generic
> implementation inside libgcc is difficult?
I think the difficulty is the table is dependent upon the polynomial. 
So we'd have to arrange to generate, then pass in the table.

In theory we could have the linker fold away duplicate tables as those 
should be in read only sections without relocations to internal members. 
  So much like we do for constant pool entries.  Though this hasn't been 
tested.

The CRC implementation itself could be subject to ICF if it's off in its 
own function.  If it's inlined (and that's a real possibility), then 
there's little hope of ICF helping on the codesize.

Or we could just not do any of this for -Os/-Oz if the target doesn't 
have a carryless multiply or crc with the appropriate polynomial.  Given 
the CRC table is probably larger than all the code in a bitwise 
impementation, disabling for -Os/-Oz seems like a very reasonable choice.


jeff

Re: [RFC/RFA] [PATCH 02/12] Add built-ins and tests for bit-forward and bit-reversed CRCs

[Richard Biener]

On Mon, May 27, 2024 at 5:16 PM Jeff Law <jeffreyalaw@gmail.com> wrote:
>
>
>
> On 5/27/24 12:38 AM, Richard Biener wrote:
> > On Fri, May 24, 2024 at 10:44 AM Mariam Arutunian
> > <mariamarutunian@gmail.com> wrote:
> >>
> >> This patch introduces new built-in functions to GCC for computing bit-forward and bit-reversed CRCs.
> >> These builtins aim to provide efficient CRC calculation capabilities.
> >> When the target architecture supports CRC operations (as indicated by the presence of a CRC optab),
> >> the builtins will utilize the expander to generate CRC code.
> >> In the absence of hardware support, the builtins default to generating code for a table-based CRC calculation.
> >
> > I wonder whether for embedded target use we should arrange for the
> > table-based CRC calculation to be out-of-line and implemented in a
> > way so uses across TUs can be merged?  I guess a generic
> > implementation inside libgcc is difficult?
> I think the difficulty is the table is dependent upon the polynomial.
> So we'd have to arrange to generate, then pass in the table.
>
> In theory we could have the linker fold away duplicate tables as those
> should be in read only sections without relocations to internal members.
>   So much like we do for constant pool entries.  Though this hasn't been
> tested.
>
> The CRC implementation itself could be subject to ICF if it's off in its
> own function.  If it's inlined (and that's a real possibility), then
> there's little hope of ICF helping on the codesize.

I was wondering of doing some "standard" mangling in the implementation
namespace and using comdat groups for both code and data?

> Or we could just not do any of this for -Os/-Oz if the target doesn't
> have a carryless multiply or crc with the appropriate polynomial.  Given
> the CRC table is probably larger than all the code in a bitwise
> impementation, disabling for -Os/-Oz seems like a very reasonable choice.

I was mainly thinking about the case where the user uses the new builtins,
but yes, when optimizing for size we can disable the recognition of open-coded
variants.

Richard.

>
> jeff

Re: [RFC/RFA] [PATCH 02/12] Add built-ins and tests for bit-forward and bit-reversed CRCs

[Jeff Law]

On 5/28/24 12:44 AM, Richard Biener wrote:
> On Mon, May 27, 2024 at 5:16 PM Jeff Law <jeffreyalaw@gmail.com> wrote:
>>
>>
>>
>> On 5/27/24 12:38 AM, Richard Biener wrote:
>>> On Fri, May 24, 2024 at 10:44 AM Mariam Arutunian
>>> <mariamarutunian@gmail.com> wrote:
>>>>
>>>> This patch introduces new built-in functions to GCC for computing bit-forward and bit-reversed CRCs.
>>>> These builtins aim to provide efficient CRC calculation capabilities.
>>>> When the target architecture supports CRC operations (as indicated by the presence of a CRC optab),
>>>> the builtins will utilize the expander to generate CRC code.
>>>> In the absence of hardware support, the builtins default to generating code for a table-based CRC calculation.
>>>
>>> I wonder whether for embedded target use we should arrange for the
>>> table-based CRC calculation to be out-of-line and implemented in a
>>> way so uses across TUs can be merged?  I guess a generic
>>> implementation inside libgcc is difficult?
>> I think the difficulty is the table is dependent upon the polynomial.
>> So we'd have to arrange to generate, then pass in the table.
>>
>> In theory we could have the linker fold away duplicate tables as those
>> should be in read only sections without relocations to internal members.
>>    So much like we do for constant pool entries.  Though this hasn't been
>> tested.
>>
>> The CRC implementation itself could be subject to ICF if it's off in its
>> own function.  If it's inlined (and that's a real possibility), then
>> there's little hope of ICF helping on the codesize.
> 
> I was wondering of doing some "standard" mangling in the implementation
> namespace and using comdat groups for both code and data?
But I'm not sure how that really solves anything given the dependencies 
on the polynomial.  ie, the contents of the table varies based on that 
polynomial and the polynomial can (and will) differ across CRC 
implementations.




> 
>> Or we could just not do any of this for -Os/-Oz if the target doesn't
>> have a carryless multiply or crc with the appropriate polynomial.  Given
>> the CRC table is probably larger than all the code in a bitwise
>> impementation, disabling for -Os/-Oz seems like a very reasonable choice.
> 
> I was mainly thinking about the case where the user uses the new builtins,
> but yes, when optimizing for size we can disable the recognition of open-coded
> variants.
Turns out Mariam's patch already disables this for -Os.  :-)

For someone directly using the builtin, they're going to have to pass 
the polynomial as a constant to the builtin, with the possible exception 
of when the target has a crc instruction where the polynomial is defined 
by the hardware.

Jeff