[Bug tree-optimization/104595] New: unvectorized loop due to bool condition loaded from memory

[Bug tree-optimization/104595] New: unvectorized loop due to bool condition loaded from memory

[linkw at gcc dot gnu.org]

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

            Bug ID: 104595
           Summary: unvectorized loop due to bool condition loaded from
                    memory
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: linkw at gcc dot gnu.org
  Target Milestone: ---

For the case:

#include "stdbool.h"
#define N 256
typedef char T;
extern T a[N];
extern T b[N];
extern T c[N];
extern bool pb[N];
extern char pc[N];

void predicate_by_bool() {
  for (int i = 0; i < N; i++)
    c[i] = pb[i] ? a[i] : b[i];
}

void predicate_by_char() {
  for (int i = 0; i < N; i++)
    c[i] = pc[i] ? a[i] : b[i];
}

Simply compiled with -Ofast -mcpu=power10, vectorizer can vectorize the 2nd
function predicate_by_char but can't vectorize the first. It seems currently
GCC just supports very limited case with bool types such as some patterns in
vect_recog_bool_pattern.

I guess here the size of bool seems to be a problem, for the size of bool, C
says "An object declared as type _Bool is large enough to store the values 0
and 1.", C++ says "The value of sizeof(bool) is implementation defined and
might differ from 1.". But the "implementation defined" looks to be compiler
defined? then compiler should be aware of it when compiling. If so, we can use
the equivalent size type for the load instead and make it compare with zero to
get the predicate just like the char variant, I think the expectation to see
both these loops vectorized is reasonable then?

[Bug tree-optimization/104595] unvectorized loop due to bool condition loaded from memory

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2022-02-18
             Blocks|                            |53947
           Keywords|                            |missed-optimization
             Status|UNCONFIRMED                 |NEW

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
Confirmed.  I think this is a omission somewhere in bool pattern recog since
we need a

  tem = pb[i] != 0 ? -1 : 0;

kind of computation to generate a mask suitable for vectorization here.  We
might have a duplicate bugreport as well.


Referenced Bugs:

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=53947
[Bug 53947] [meta-bug] vectorizer missed-optimizations

[Bug tree-optimization/104595] unvectorized loop due to bool condition loaded from memory

[segher at gcc dot gnu.org]

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

--- Comment #2 from Segher Boessenkool <segher at gcc dot gnu.org> ---
This is exactly the same as the char case here though, so it is a bit silly
that we miss it :-)

[Bug tree-optimization/104595] unvectorized loop due to bool condition loaded from memory

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |enhancement

[Bug tree-optimization/104595] unvectorized loop due to bool condition loaded from memory

[pinskia at gcc dot gnu.org]

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

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
IR in the bool case:
  _1 = pb[i_13];
  iftmp.0_7 = a[i_13];
  iftmp.0_6 = b[i_13];
  iftmp.0_3 = _1 ? iftmp.0_7 : iftmp.0_6;
  c[i_13] = iftmp.0_3;

IR in the char case:
  _1 = pc[i_13];
  iftmp.1_7 = a[i_13];
  iftmp.1_6 = b[i_13];
  iftmp.1_3 = _1 == 0 ? iftmp.1_6 : iftmp.1_7;
  c[i_13] = iftmp.1_3;


details in the bool case:

/app/example.cpp:12:21: note:   ==> examining statement: iftmp.0_3 = _1 ?
iftmp.0_7 : iftmp.0_6;
/app/example.cpp:12:21: note:   vect_is_simple_use: operand pb[i_13], type of
def: internal
/app/example.cpp:12:21: note:   vect_is_simple_use: vectype vector(32) unsigned
char
/app/example.cpp:11:6: missed:   not vectorized: relevant stmt not supported:
iftmp.0_3 = _1 ? iftmp.0_7 : iftmp.0_6;

details in the char case:
/app/example.cpp:17:21: note:   ==> examining statement: iftmp.1_3 = _1 == 0 ?
iftmp.1_6 : iftmp.1_7;
/app/example.cpp:17:21: note:   vect_is_simple_use: operand pc[i_13], type of
def: internal
/app/example.cpp:17:21: note:   vect_is_simple_use: vectype vector(32) char
/app/example.cpp:17:21: note:   vect_is_simple_use: operand b[i_13], type of
def: internal
/app/example.cpp:17:21: note:   vect_is_simple_use: vectype vector(32) char
/app/example.cpp:17:21: note:   vect_is_simple_use: operand a[i_13], type of
def: internal
/app/example.cpp:17:21: note:   vect_is_simple_use: vectype vector(32) char
/app/example.cpp:17:21: note:   vect_model_simple_cost: inside_cost = 4,
prologue_cost = 4 .

It should not be too hard to if we had _1 ? : to change it to _1 != 0 right?

[Bug tree-optimization/104595] unvectorized loop due to bool condition loaded from memory

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
           Assignee|unassigned at gcc dot gnu.org      |rguenth at gcc dot gnu.org

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
Let me have a quick look.

[Bug tree-optimization/104595] unvectorized loop due to bool condition loaded from memory

[rguenth at gcc dot gnu.org]

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

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
diff --git a/gcc/tree-vect-patterns.cc b/gcc/tree-vect-patterns.cc
index 217bdfd7045..ff9a628321f 100644
--- a/gcc/tree-vect-patterns.cc
+++ b/gcc/tree-vect-patterns.cc
@@ -4450,18 +4450,16 @@ vect_recog_bool_pattern (vec_info *vinfo,
       if (get_vectype_for_scalar_type (vinfo, type) == NULL_TREE)
        return NULL;

-      if (!check_bool_pattern (var, vinfo, bool_stmts))
-       return NULL;
-
-      rhs = adjust_bool_stmts (vinfo, bool_stmts, type, stmt_vinfo);
+      if (check_bool_pattern (var, vinfo, bool_stmts))
+       var = adjust_bool_stmts (vinfo, bool_stmts, type, stmt_vinfo);

       lhs = vect_recog_temp_ssa_var (TREE_TYPE (lhs), NULL);
       pattern_stmt 
-         = gimple_build_assign (lhs, COND_EXPR,
-                                build2 (NE_EXPR, boolean_type_node,
-                                        rhs, build_int_cst (type, 0)),
-                                gimple_assign_rhs2 (last_stmt),
-                                gimple_assign_rhs3 (last_stmt));
+       = gimple_build_assign (lhs, COND_EXPR,
+                              build2 (NE_EXPR, boolean_type_node,
+                                      var, build_int_cst (TREE_TYPE (var),
0)),
+                              gimple_assign_rhs2 (last_stmt),
+                              gimple_assign_rhs3 (last_stmt));
       *type_out = vectype;
       vect_pattern_detected ("vect_recog_bool_pattern", last_stmt);

[Bug tree-optimization/104595] unvectorized loop due to bool condition loaded from memory

[rguenth at gcc dot gnu.org]

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

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
The patch doesn't really work, it regresses some AVX512 stuff in i386.exp,
notably

FAIL: gcc.target/i386/avx512vl-vdivps-2.c (internal compiler error: in
vect_get_
vec_defs_for_operand, at tree-vect-stmts.cc:1508)
...
FAIL: gcc.target/i386/mask-pack-prefer128.c scan-tree-dump-times vect
"vectorized 1 loops" 10
FAIL: gcc.target/i386/mask-pack-prefer256.c scan-tree-dump-times vect
"vectorized 1 loops" 10
FAIL: gcc.target/i386/mask-pack.c scan-tree-dump-times vect "vectorized 1
loops" 10
FAIL: gcc.target/i386/mask-unpack.c scan-tree-dump-times vect "vectorized 1
loops" 10


There's an additional case:

#define N 256
typedef short T;
extern T a[N];
extern T b[N];
extern T c[N];
extern _Bool pb[N];

void predicate_by_bool()
{
  for (int i = 0; i < N; i++)
    c[i] = pb[i] ? a[i] : b[i];
}

where we expect vect_recog_mask_conversion_pattern to trigger here.  That
case can be fixed with

@@ -4658,9 +4660,9 @@ vect_recog_mask_conversion_pattern (vec_info *vinfo,

       if (TREE_CODE (rhs1) == SSA_NAME)
        {
-         rhs1_type = integer_type_for_mask (rhs1, vinfo);
-         if (!rhs1_type)
+         if (integer_type_for_mask (rhs1, vinfo))
            return NULL;
+         rhs1_type = TREE_TYPE (rhs1);
        }
       else if (COMPARISON_CLASS_P (rhs1))
        {

but we then run into the original issue again:

t.c:10:6: missed:   not vectorized: relevant stmt not supported: patt_28 =
(<signed-boolean:16>) _1;

The cruical difference between working and not working is the _1 != 0 ?: vs.
_1 ?:  - I think we do have a duplicate bugreport here, possibly involving
combinations of different from memory bools.

Trying to make bool pattern recog inserting the relevant compensation code
is really iffy, the mask conversion pattern confuses things here - what
we are missing seems really be transforming the leafs.

Note that we do not try to patter-recog a pattern thus we cannot at the moment
have both, vect_recog_bool_pattern and vect_recog_mask_conversion_pattern
at the same time on the ?: stmt.

Note IIRC vect_recog_bool_pattern has to come last but it's now after
vect_recog_mask_conversion_pattern.  Unfortunately swapping things does
not make vect_recog_bool_pattern recognize and fixup

  patt_24 = (<signed-boolean:16>) _1;

[Bug tree-optimization/104595] unvectorized loop due to bool condition loaded from memory

[rguenth at gcc dot gnu.org]

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

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> ---
bool patterns are to distinguish flag uses from data uses since a vectorized
flag true will be -1 while the unvectorized flag is 1 but of course any
data uses have to be retained.  What we are missing here is the reverse,
convert unvectorized flag 1 to vectorized flag -1 for data.  Since there
may be data and non-data uses we have to insert fixups (patterns) at use
sites.  For the bool vs. char case that's the

  iftmp.0_3 = _1 ? iftmp.0_7 : iftmp.0_6;

case.  Since we generally assume a bool LHS will be vectorized to a mask
we don't do our job here since obviously bool loads do not.  Conversions
do not either and the code to handle those is a bit awkward as well,
handling bool source and bool destination differently for some reason
(but not both at the same time?).

This all needs a bit of dis-entangling and probably re-ordering of
vect_recog_bool_pattern and vect_recog_mask_conversion_pattern.

[Bug tree-optimization/104595] unvectorized loop due to bool condition loaded from memory

[linkw at gcc dot gnu.org]

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

--- Comment #8 from Kewen Lin <linkw at gcc dot gnu.org> ---
I had one local hack and just found it can survive on x86 bootstrapping and
regression testing. I guess maybe it's good to post here. Just ignore this if
it looks like noise. :) The point is to do the conversion for the loaded bool
value from memory, normally it should be like a nop, but for this test case, it
can help us to generate the expected char comparison.

diff --git a/gcc/tree-vect-patterns.cc b/gcc/tree-vect-patterns.cc
index 2baf974627e..d4b8920203b 100644
--- a/gcc/tree-vect-patterns.cc
+++ b/gcc/tree-vect-patterns.cc
@@ -3911,6 +3911,11 @@ check_bool_pattern (tree var, vec_info *vinfo,
hash_set<gimple *> &stmts)
        return false;
       break;

+    case ARRAY_REF:
+      if (TYPE_PRECISION (TREE_TYPE (var)) != 1)
+       return false;
+      break;
+
     default:
       if (TREE_CODE_CLASS (rhs_code) == tcc_comparison)
        {
@@ -4005,6 +4010,19 @@ adjust_bool_pattern (vec_info *vinfo, tree var, tree
out_type,
                               SSA_NAME, irhs1);
       break;

+    case ARRAY_REF:
+      {
+       itype = TREE_TYPE (var);
+       gcc_assert (TYPE_PRECISION (itype) == 1);
+       machine_mode mode = TYPE_MODE (itype);
+       tree scalar_type = build_nonstandard_integer_type (
+         GET_MODE_BITSIZE (mode).to_constant (), TYPE_UNSIGNED (itype));
+       pattern_stmt
+         = gimple_build_assign (vect_recog_temp_ssa_var (scalar_type, NULL),
+                                CONVERT_EXPR, var);
+      }
+      break;
+
     case BIT_NOT_EXPR:
       irhs1 = *defs.get (rhs1);
       itype = TREE_TYPE (irhs1);

[Bug tree-optimization/104595] unvectorized loop due to bool condition loaded from memory

[rguenther at suse dot de]

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

--- Comment #9 from rguenther at suse dot de <rguenther at suse dot de> ---
On Wed, 23 Feb 2022, linkw at gcc dot gnu.org wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=104595
> 
> --- Comment #8 from Kewen Lin <linkw at gcc dot gnu.org> ---
> I had one local hack and just found it can survive on x86 bootstrapping and
> regression testing. I guess maybe it's good to post here. Just ignore this if
> it looks like noise. :) The point is to do the conversion for the loaded bool
> value from memory, normally it should be like a nop, but for this test case, it
> can help us to generate the expected char comparison.

Yes, but see my posted patch for a better fix.  There's some underlying
missing things we have in bool pattern recog that need to be fixed.

Treating "external" (that includes memory) bools as 'char' would work
but the type has effect on other IL which causes some ripple down effect
and thus I think doing this isn't going to work in the end.

> diff --git a/gcc/tree-vect-patterns.cc b/gcc/tree-vect-patterns.cc
> index 2baf974627e..d4b8920203b 100644
> --- a/gcc/tree-vect-patterns.cc
> +++ b/gcc/tree-vect-patterns.cc
> @@ -3911,6 +3911,11 @@ check_bool_pattern (tree var, vec_info *vinfo,
> hash_set<gimple *> &stmts)
>         return false;
>        break;
> 
> +    case ARRAY_REF:
> +      if (TYPE_PRECISION (TREE_TYPE (var)) != 1)
> +       return false;
> +      break;
> +
>      default:
>        if (TREE_CODE_CLASS (rhs_code) == tcc_comparison)
>         {
> @@ -4005,6 +4010,19 @@ adjust_bool_pattern (vec_info *vinfo, tree var, tree
> out_type,
>                                SSA_NAME, irhs1);
>        break;
> 
> +    case ARRAY_REF:
> +      {
> +       itype = TREE_TYPE (var);
> +       gcc_assert (TYPE_PRECISION (itype) == 1);
> +       machine_mode mode = TYPE_MODE (itype);
> +       tree scalar_type = build_nonstandard_integer_type (
> +         GET_MODE_BITSIZE (mode).to_constant (), TYPE_UNSIGNED (itype));
> +       pattern_stmt
> +         = gimple_build_assign (vect_recog_temp_ssa_var (scalar_type, NULL),
> +                                CONVERT_EXPR, var);
> +      }
> +      break;
> +
>      case BIT_NOT_EXPR:
>        irhs1 = *defs.get (rhs1);
>        itype = TREE_TYPE (irhs1);
> 
>

[Bug tree-optimization/104595] unvectorized loop due to bool condition loaded from memory

[linkw at gcc dot gnu.org]

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

--- Comment #10 from Kewen Lin <linkw at gcc dot gnu.org> ---
(In reply to rguenther@suse.de from comment #9)
> On Wed, 23 Feb 2022, linkw at gcc dot gnu.org wrote:
> 
> > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=104595
> > 
> > --- Comment #8 from Kewen Lin <linkw at gcc dot gnu.org> ---
> > I had one local hack and just found it can survive on x86 bootstrapping and
> > regression testing. I guess maybe it's good to post here. Just ignore this if
> > it looks like noise. :) The point is to do the conversion for the loaded bool
> > value from memory, normally it should be like a nop, but for this test case, it
> > can help us to generate the expected char comparison.
> 
> Yes, but see my posted patch for a better fix.  There's some underlying
> missing things we have in bool pattern recog that need to be fixed.
> 
> Treating "external" (that includes memory) bools as 'char' would work
> but the type has effect on other IL which causes some ripple down effect
> and thus I think doing this isn't going to work in the end.
> 

Got it, thanks for the explanation!

[Bug tree-optimization/104595] unvectorized loop due to bool condition loaded from memory

[cvs-commit at gcc dot gnu.org]

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

--- Comment #11 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Richard Biener <rguenth@gcc.gnu.org>:

https://gcc.gnu.org/g:938a02a589dc22cef65bba2b131fc9e4874baddb

commit r13-128-g938a02a589dc22cef65bba2b131fc9e4874baddb
Author: Richard Biener <rguenther@suse.de>
Date:   Mon Feb 21 11:05:58 2022 +0100

    tree-optimization/104595 - vectorization of COND_EXPR with bool load

    The following fixes an omission in bool pattern detection that
    makes it fail when check_bool_pattern fails for COND_EXPR.  That's
    not what it should do, instead it should still pattern recog
    to var != 0 even if no further adjustments to the def chain are
    necessary when var is not a mask already.

    2022-02-21  Richard Biener  <rguenther@suse.de>

            PR tree-optimization/104595
            * tree-vect-patterns.cc (vect_recog_bool_pattern): For
            COND_EXPR do not fail if check_bool_pattern returns false.

            * gcc.dg/vect/pr104595.c: New testcase.

[Bug tree-optimization/104595] unvectorized loop due to bool condition loaded from memory

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|---                         |FIXED
      Known to work|                            |13.0
             Status|ASSIGNED                    |RESOLVED

--- Comment #12 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed, I've opened PR105490 for the case where we need widening.