[Bug c/112961] New: middle-end Missed vectorization: failed to vectorize simple reduction max since GCC-13

[Bug c/112961] New: middle-end Missed vectorization: failed to vectorize simple reduction max since GCC-13

[juzhe.zhong at rivai dot ai]

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

            Bug ID: 112961
           Summary: middle-end Missed vectorization: failed to vectorize
                    simple reduction max since GCC-13
           Product: gcc
           Version: 14.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c
          Assignee: unassigned at gcc dot gnu.org
          Reporter: juzhe.zhong at rivai dot ai
  Target Milestone: ---

#include <algorithm>

int foo(int *a, int n) {
  int max = -987654321;
  for (int i = 0; i < n; ++i)
    max = std::max(max, a[i]);

  return max;
}

This is a simple loop reduction max.

Reference: https://godbolt.org/z/WMvfobK4b

From the reference, we can know GCC-12 can vectorize it but failed to vectorize
it on both GCC-13 and GCC-14.

[Bug tree-optimization/112961] middle-end Missed vectorization: failed to vectorize simple reduction max since GCC-13

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Blocks|                            |53947
          Component|c                           |tree-optimization

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
  _29 = MAX_EXPR <_16, prephitmp_18>;
  prephitmp_23 = _29;


Referenced Bugs:

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

[Bug tree-optimization/112961] [13/14 Regression] middle-end Missed vectorization: failed to vectorize simple reduction max since GCC-13

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|middle-end Missed           |[13/14 Regression]
                   |vectorization: failed to    |middle-end Missed
                   |vectorize simple reduction  |vectorization: failed to
                   |max since GCC-13            |vectorize simple reduction
                   |                            |max since GCC-13
   Target Milestone|---                         |13.3

[Bug tree-optimization/112961] [13/14 Regression] middle-end Missed vectorization: failed to vectorize simple reduction max since GCC-13

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2023-12-11

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Confirmed.

The difference in IR is minor but causes the confusion:

  _29 = MAX_EXPR <_16, prephitmp_18>;
  prephitmp_23 = _29;

vs:
  prephitmp_23 = MAX_EXPR <_16, prephitmp_18>;

[Bug tree-optimization/112961] [13/14 Regression] middle-end Missed vectorization: failed to vectorize simple reduction max since GCC-13

[rguenth at gcc dot gnu.org]

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

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 #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
Yup, unpropagated copies can confuse the vectorizer.  Let me look into it.

[Bug tree-optimization/112961] [13/14 Regression] middle-end Missed vectorization: failed to vectorize simple reduction max since GCC-13

[rguenth at gcc dot gnu.org]

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

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
So in this case VN doesn't "fix" it because

Value numbering stmt = _29 = MAX_EXPR <_16, prephitmp_18>;
Setting value number of _29 to _29 (changed)
Making available beyond BB3 _29 for value _29
Value numbering stmt = prephitmp_23 = _29;
Setting value number of prephitmp_23 to _29 (changed)
...
Keeping eliminated stmt live as copy because of out-of-region uses

as the loop header is using this on the backedge and we are explicitly
excluding the latch block from processing to avoid CSE of PHIs(?).
I think including the latch block should be fine, but PR90402 is what
I added this special case for (the testcase still passes after reverting).

[Bug tree-optimization/112961] [13/14 Regression] middle-end Missed vectorization: failed to vectorize simple reduction max since GCC-13

[cvs-commit at gcc dot gnu.org]

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

--- Comment #5 from GCC 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:878cb5acf0c499702ffd315e273f55e8bd0970b8

commit r14-6457-g878cb5acf0c499702ffd315e273f55e8bd0970b8
Author: Richard Biener <rguenther@suse.de>
Date:   Tue Dec 12 14:01:47 2023 +0100

    tree-optimization/112961 - include latch in if-conversion CSE

    The following makes sure to also process the (empty) latch when
    performing CSE on the if-converted loop body.  That's important
    to get all uses of copies propagated out on the backedge as well.
    To avoid CSE on the PHI nodes itself which is prohibitive
    (see PR90402) this temporarily adds a fake entry edge to the loop.

            PR tree-optimization/112961
            * tree-if-conv.cc (tree_if_conversion): Instead of excluding
            the latch block from VN, add a fake entry edge.

            * g++.dg/vect/pr112961.cc: New testcase.

[Bug tree-optimization/112961] [13 Regression] middle-end Missed vectorization: failed to vectorize simple reduction max since GCC-13

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|                            |14.0
           Priority|P3                          |P2
            Summary|[13/14 Regression]          |[13 Regression] middle-end
                   |middle-end Missed           |Missed vectorization:
                   |vectorization: failed to    |failed to vectorize simple
                   |vectorize simple reduction  |reduction max since GCC-13
                   |max since GCC-13            |

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed on trunk sofar.

[Bug tree-optimization/112961] [13 Regression] middle-end Missed vectorization: failed to vectorize simple reduction max since GCC-13

[juzhe.zhong at rivai dot ai]

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

JuzheZhong <juzhe.zhong at rivai dot ai> changed:

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

--- Comment #7 from JuzheZhong <juzhe.zhong at rivai dot ai> ---
Thanks Richard.

Fixed.

[Bug tree-optimization/112961] [13 Regression] middle-end Missed vectorization: failed to vectorize simple reduction max since GCC-13

[rguenth at gcc dot gnu.org]

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

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

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

--- Comment #8 from Richard Biener <rguenth at gcc dot gnu.org> ---
Still eventually for backporting.

[Bug tree-optimization/112961] [13 Regression] middle-end Missed vectorization: failed to vectorize simple reduction max since GCC-13

[juzhe.zhong at rivai dot ai]

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

--- Comment #9 from JuzheZhong <juzhe.zhong at rivai dot ai> ---
(In reply to Richard Biener from comment #8)
> Still eventually for backporting.

Oh. I am sorry for closing it (I didn't notice it needs to be backport).

[Bug tree-optimization/112961] [13 Regression] middle-end Missed vectorization: failed to vectorize simple reduction max since GCC-13

[cvs-commit at gcc dot gnu.org]

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

--- Comment #10 from GCC 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:93db32a4146afd2a6d90410691351a56768167c9

commit r14-6483-g93db32a4146afd2a6d90410691351a56768167c9
Author: Richard Biener <rguenther@suse.de>
Date:   Wed Dec 13 08:45:58 2023 +0100

    tree-optimization/112991 - re-do PR112961 fix

    The following does away with the fake edge adding as in the original
    PR112961 fix and instead exposes handling of entry PHIs as additional
    parameter of the region VN run.

            PR tree-optimization/112991
            PR tree-optimization/112961
            * tree-ssa-sccvn.h (do_rpo_vn): Add skip_entry_phis argument.
            * tree-ssa-sccvn.cc (do_rpo_vn): Likewise.
            (do_rpo_vn_1): Likewise, merge with auto-processing.
            (run_rpo_vn): Adjust.
            (pass_fre::execute): Likewise.
            * tree-if-conv.cc (tree_if_conversion): Revert last change.
            Value-number latch block but disable value-numbering of
            entry PHIs.
            * tree-ssa-uninit.cc (execute_early_warn_uninitialized): Adjust.

            * gcc.dg/torture/pr112991.c: New testcase.

[Bug tree-optimization/112961] [13 Regression] middle-end Missed vectorization: failed to vectorize simple reduction max since GCC-13

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=112961
Bug 112961 depends on bug 112991, which changed state.

Bug 112991 Summary: [14 Regression] ICE during GIMPLE pass: ifcvt on p7zip-17.05 since r14-6457
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=112991

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

[Bug tree-optimization/112961] [13 Regression] middle-end Missed vectorization: failed to vectorize simple reduction max since GCC-13

[cvs-commit at gcc dot gnu.org]

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

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

https://gcc.gnu.org/g:25add4b65a3bac262685d290a4dc93884a022576

commit r13-8719-g25add4b65a3bac262685d290a4dc93884a022576
Author: Richard Biener <rguenther@suse.de>
Date:   Wed Dec 13 08:45:58 2023 +0100

    tree-optimization/112991 - re-do PR112961 fix

    The following does away with the fake edge adding as in the original
    PR112961 fix and instead exposes handling of entry PHIs as additional
    parameter of the region VN run.

            PR tree-optimization/112991
            PR tree-optimization/112961
            * tree-ssa-sccvn.h (do_rpo_vn): Add skip_entry_phis argument.
            * tree-ssa-sccvn.cc (do_rpo_vn): Likewise.
            (do_rpo_vn_1): Likewise, merge with auto-processing.
            (run_rpo_vn): Adjust.
            (pass_fre::execute): Likewise.
            * tree-if-conv.cc (tree_if_conversion): Revert last change.
            Value-number latch block but disable value-numbering of
            entry PHIs.
            * tree-ssa-uninit.cc (execute_early_warn_uninitialized): Adjust.

            * gcc.dg/torture/pr112991.c: New testcase.
            * g++.dg/vect/pr112961.cc: Likewise.

    (cherry picked from commit 93db32a4146afd2a6d90410691351a56768167c9)

[Bug tree-optimization/112961] [13 Regression] middle-end Missed vectorization: failed to vectorize simple reduction max since GCC-13

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to fail|                            |13.2.0
      Known to work|                            |13.2.1
         Resolution|---                         |FIXED
             Status|ASSIGNED                    |RESOLVED

--- Comment #12 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed.