[Bug middle-end/103126] New: Miss vectorization for bit_and/bit_ior/bit_xor reduction

[Bug middle-end/103126] New: Miss vectorization for bit_and/bit_ior/bit_xor reduction

[crazylht at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103126

            Bug ID: 103126
           Summary: Miss vectorization for bit_and/bit_ior/bit_xor
                    reduction
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: normal
          Priority: P3
         Component: middle-end
          Assignee: unassigned at gcc dot gnu.org
          Reporter: crazylht at gmail dot com
  Target Milestone: ---
              Host: x86_64-pc-linux-gnu

Cat test.c

#include<stdint.h>

void xor_bit_arr_nolcd (uint64_t *__restrict mat, uint64_t* a,uint64_t* b,
uint64_t *__restrict ans,
    int64_t n)
{
  int64_t i;
  uint64_t vec1, sum1;
  uint64_t vec2, sum2;

  while (n > 0) {
    sum1 = 0;
    vec1 = a[0];
    sum2 = 0;
    vec2 = b[0];

    for (i = 0; i < 64; i++) {
      uint64_t tmp = mat[i]; // always safe to load
      uint64_t vec1_i = (vec1 >> i);
      uint64_t vec2_i = (vec2 >> i);
      sum1 ^= (vec1_i & 1) ? tmp : 0;
      if (vec2_i&1) sum2 ^= tmp;
    }
    *ans++ ^= sum1;  n--;
    *ans++ ^= sum2;  n--;
  }
}


vectorizer failed exactly the same reason as PR98365 #c3

(In reply to Richard Biener from comment #3)
> The issue is that we hit
> 
>   /* If this isn't a nested cycle or if the nested cycle reduction value
>      is used ouside of the inner loop we cannot handle uses of the reduction
>      value.  */
>   if (nlatch_def_loop_uses > 1 || nphi_def_loop_uses > 1)
>     {
>       if (dump_enabled_p ())
>         dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
>                          "reduction used in loop.\n");
>       return NULL;
>     }
> 
> because cnt_21 is used in both the update and the COND_EXPR.  The reduction
> doesn't fit the cond reductions we support but is a blend of a cond and
> regular reduction.  Making the COND-reduction support handle this case
> should be possible though.
> 
> Using 'int' we arrive at handled IL:
> 
>   # cnt_19 = PHI <cnt_8(7), 0(15)>
>   _ifc__32 = _4 == _7 ? 1 : 0;
>   cnt_8 = cnt_19 + _ifc__32;
> 
> so adjusting if-conversion can indeed help.

I'm working on a patch to extend ifcvt(is_cond_scalar_reduction) to handle
bit_and/bit_ior/bit_xor operation.

[Bug tree-optimization/103126] Miss vectorization for bit_and/bit_ior/bit_xor reduction

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103126

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2021-11-08
     Ever confirmed|0                           |1

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
Confirmed.

[Bug tree-optimization/103126] Miss vectorization for bit_and/bit_ior/bit_xor reduction

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103126

--- Comment #2 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by hongtao Liu <liuhongt@gcc.gnu.org>:

https://gcc.gnu.org/g:249b4eeef1fe30237acb4d8e1832243b39d61e7e

commit r12-5084-g249b4eeef1fe30237acb4d8e1832243b39d61e7e
Author: liuhongt <hongtao.liu@intel.com>
Date:   Mon Nov 8 15:49:17 2021 +0800

    Extend is_cond_scalar_reduction to handle bit_and/bit_xor/bit_ior.

    This will enable transformation like

    -  # sum1_50 = PHI <prephitmp_64(13), 0(4)>
    -  # sum2_52 = PHI <sum2_21(13), 0(4)>
    +  # sum1_50 = PHI <_87(13), 0(4)>
    +  # sum2_52 = PHI <_89(13), 0(4)>
       # ivtmp_62 = PHI <ivtmp_61(13), 64(4)>
       i.2_7 = (long unsigned int) i_49;
       _8 = i.2_7 * 8;
    ...
       vec1_i_38 = vec1_29 >> _10;
       vec2_i_39 = vec2_31 >> _10;
       _11 = vec1_i_38 & 1;
    -  _63 = tmp_37 ^ sum1_50;
    -  prephitmp_64 = _11 == 0 ? sum1_50 : _63;
    +  _ifc__86 = _11 != 0 ? tmp_37 : 0;
    +  _87 = sum1_50 ^ _ifc__86;
       _12 = vec2_i_39 & 1;
    :

    so that vectorizer won't failed due to

      /* If this isn't a nested cycle or if the nested cycle reduction value
         is used ouside of the inner loop we cannot handle uses of the
reduction
         value.  */
      if (nlatch_def_loop_uses > 1 || nphi_def_loop_uses > 1)
        {
          if (dump_enabled_p ())
            dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
                             "reduction used in loop.\n");
          return NULL;
        }

    gcc/ChangeLog:

            PR tree-optimization/103126
            * tree-vect-loop.c (neutral_op_for_reduction): Remove static.
            * tree-vectorizer.h (neutral_op_for_reduction): Declare.
            * tree-if-conv.c : Include tree-vectorizer.h.
            (is_cond_scalar_reduction): Handle
            BIT_XOR_EXPR/BIT_IOR_EXPR/BIT_AND_EXPR.
            (convert_scalar_cond_reduction): Ditto.

    gcc/testsuite/ChangeLog:

            * gcc.target/i386/ifcvt-reduction-logic-op.c: New test.

[Bug tree-optimization/103126] Miss vectorization for bit_and/bit_ior/bit_xor reduction

[crazylht at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103126

Hongtao.liu <crazylht at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|---                         |FIXED

--- Comment #3 from Hongtao.liu <crazylht at gmail dot com> ---
Fixed in GCC12.