[Bug c/99954] New: Copy loop over array of unions at -O3 generates memcpy instead of memmove, resulting in incorrect code

[Bug c/99954] New: Copy loop over array of unions at -O3 generates memcpy instead of memmove, resulting in incorrect code

[doublef.mobile at gmail dot com]

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

            Bug ID: 99954
           Summary: Copy loop over array of unions at -O3 generates memcpy
                    instead of memmove, resulting in incorrect code
           Product: gcc
           Version: 10.2.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c
          Assignee: unassigned at gcc dot gnu.org
          Reporter: doublef.mobile at gmail dot com
  Target Milestone: ---

Created attachment 50521
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=50521&action=edit
test case (should exit successfully but halts on assertion error)

The attached code is intended to generate an array of e.g. 1,1,2,3,4,5... (if
called without arguments) but instead generates e.g. 1,1,1,1,1 as the loop in
move() is incorrectly optimized to memcpy. The issue has been detected on x86,
amd64 and mips.

As checked on godbolt.org, issue applies to GCC 7+ (6 and below correctly
generate memmove); using -O2 "fixes" the issue on GCC 9 and below but not on
10.

If "#define CONTAINER_KIND struct" is used instead, the issue is not triggered.

[Bug tree-optimization/99954] [8/9/10/11 Regression] Copy loop over array of unions at -O3 generates memcpy instead of memmove, resulting in incorrect code

[redi at gcc dot gnu.org]

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

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2021-04-07
      Known to work|                            |6.5.0
            Summary|Copy loop over array of     |[8/9/10/11 Regression] Copy
                   |unions at -O3 generates     |loop over array of unions
                   |memcpy instead of memmove,  |at -O3 generates memcpy
                   |resulting in incorrect code |instead of memmove,
                   |                            |resulting in incorrect code
      Known to fail|                            |10.2.0, 11.0, 7.5.0, 8.4.0,
                   |                            |9.3.0
                 CC|                            |rguenther at suse dot de
     Ever confirmed|0                           |1

--- Comment #1 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Sergey Zakharchenko from comment #0)
> As checked on godbolt.org, issue applies to GCC 7+ (6 and below correctly
> generate memmove);

Started with r242470

re PR tree-optimization/78348 ([7 REGRESSION] 15% performance drop for
coremark-pro/nnet-test after r242038)

2016-11-16  Richard Biener

        PR tree-optimization/78348
        * tree-loop-distribution.c (enum partition_kind): Add PKIND_MEMMOVE.
        (generate_memcpy_builtin): Honor PKIND_MEMCPY on the partition.
        (classify_partition): Set PKIND_MEMCPY if dependence analysis
        revealed no dependency, PKIND_MEMMOVE otherwise.

        * gcc.dg/tree-ssa/ldist-24.c: New testcase.

[Bug tree-optimization/99954] [8/9/10/11 Regression] Copy loop over array of unions at -O3 generates memcpy instead of memmove, resulting in incorrect code

[redi at gcc dot gnu.org]

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

--- Comment #2 from Jonathan Wakely <redi at gcc dot gnu.org> ---
> using -O2 "fixes" the issue on GCC 9 and below but not on 10.

And that changed with r271553

        PR tree-optimization/88440
        * opts.c (default_options_table): Enable
-ftree-loop-distribute-patterns
        at -O[2s]+.
        * tree-loop-distribution.c (generate_memset_builtin): Fold the
        generated call.
        (generate_memcpy_builtin): Likewise.
        (distribute_loop): Pass in whether to only distribute patterns.
        (prepare_perfect_loop_nest): Also allow size optimization.
        (pass_loop_distribution::execute): When optimizing a loop
        nest for size allow pattern replacement.

[Bug tree-optimization/99954] [8/9/10/11 Regression] Copy loop over array of unions at -O3 generates memcpy instead of memmove, resulting in incorrect code

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P2
           Assignee|unassigned at gcc dot gnu.org      |rguenth at gcc dot gnu.org
   Target Milestone|---                         |8.5
             Status|NEW                         |ASSIGNED

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
I will have a look.

[Bug tree-optimization/99954] [8/9/10/11 Regression] Copy loop over array of unions at -O3 generates memcpy instead of memmove, resulting in incorrect code

[rguenth at gcc dot gnu.org]

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

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
OK, so

(compute_affine_dependence
  stmt_a: _1 = MEM[(union container *)p_11 + -4B].value;
  stmt_b: p_11->value = _1;
) -> no dependence

where there is indeed no depedence but it looks like this is the wrong
question to be asked.  So the cited rev. in question was "wrong" to
honor the assertion from classify_builtin_ldst based on dependence analysis.

diff --git a/gcc/tree-loop-distribution.c b/gcc/tree-loop-distribution.c
index 583bb062b76..2ec7d999e21 100644
--- a/gcc/tree-loop-distribution.c
+++ b/gcc/tree-loop-distribution.c
@@ -1759,11 +1759,11 @@ loop_distribution::classify_builtin_ldst (loop_p loop,
struct graph *rdg,
   /* Now check that if there is a dependence.  */
   ddr_p ddr = get_data_dependence (rdg, src_dr, dst_dr);

-  /* Classify as memcpy if no dependence between load and store.  */
+  /* Classify as memmove if no dependence between load and store.  */
   if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
     {
       partition->builtin = alloc_builtin (dst_dr, src_dr, base, src_base,
size);
-      partition->kind = PKIND_MEMCPY;
+      partition->kind = PKIND_MEMMOVE;
       return;
     }


is the correct thing to do here.  That leaves classifciation involving
(constant) sizes on the plate we could check the dependence distance
against or adjust the later alias check by creating ao_refs with size.
In particular this FAILs the added testcase by said ref.

Adjusting the alias check for the testcase isn't easy, the dest/src
pointers look like

(gdb) p debug_generic_expr (src)
(double *) par.0_1 + ((sizetype) i_19 * 320 + 4160)
$5 = void
(gdb) p debug_generic_expr (dest)
(double *) par.0_1 + ((sizetype) i_19 * 320 + 1600)
$6 = void

and there's no nice API do use here.  We can use tree-affine to subtract
the pointers and compare the difference with the computed size though.

[Bug tree-optimization/99954] [8/9/10/11 Regression] Copy loop over array of unions at -O3 generates memcpy instead of memmove, resulting in incorrect code

[cvs-commit at gcc dot gnu.org]

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

--- Comment #5 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:c01ae2ab6b227e21835d128c90e974dce4604be9

commit r11-8027-gc01ae2ab6b227e21835d128c90e974dce4604be9
Author: Richard Biener <rguenther@suse.de>
Date:   Wed Apr 7 13:17:05 2021 +0200

    tree-optimization/99954 - fix loop distribution memcpy classification

    This fixes bogus classification of a copy as memcpy.  We cannot use
    plain dependence analysis to decide between memcpy and memmove when
    it computes no dependence.  Instead we have to try harder later which
    the patch does for the gcc.dg/tree-ssa/ldist-24.c testcase by resorting
    to tree-affine to compute the difference between src and dest and
    compare against the copy size.

    2021-04-07  Richard Biener  <rguenther@suse.de>

            PR tree-optimization/99954
            * tree-loop-distribution.c: Include tree-affine.h.
            (generate_memcpy_builtin): Try using tree-affine to prove
            non-overlap.
            (loop_distribution::classify_builtin_ldst): Always classify
            as PKIND_MEMMOVE.

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

[Bug tree-optimization/99954] [8/9/10 Regression] Copy loop over array of unions at -O3 generates memcpy instead of memmove, resulting in incorrect code

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|                            |11.0
            Summary|[8/9/10/11 Regression] Copy |[8/9/10 Regression] Copy
                   |loop over array of unions   |loop over array of unions
                   |at -O3 generates memcpy     |at -O3 generates memcpy
                   |instead of memmove,         |instead of memmove,
                   |resulting in incorrect code |resulting in incorrect code

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

[Bug tree-optimization/99954] [8/9/10 Regression] Copy loop over array of unions at -O3 generates memcpy instead of memmove, resulting in incorrect code

[cvs-commit at gcc dot gnu.org]

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

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

https://gcc.gnu.org/g:ee16f803357725df96e8c232b8066d9db3ec16a8

commit r10-9768-gee16f803357725df96e8c232b8066d9db3ec16a8
Author: Richard Biener <rguenther@suse.de>
Date:   Wed Apr 7 13:17:05 2021 +0200

    tree-optimization/99954 - fix loop distribution memcpy classification

    This fixes bogus classification of a copy as memcpy.  We cannot use
    plain dependence analysis to decide between memcpy and memmove when
    it computes no dependence.  Instead we have to try harder later which
    the patch does for the gcc.dg/tree-ssa/ldist-24.c testcase by resorting
    to tree-affine to compute the difference between src and dest and
    compare against the copy size.

    2021-04-07  Richard Biener  <rguenther@suse.de>

            PR tree-optimization/99954
            * tree-loop-distribution.c: Include tree-affine.h.
            (generate_memcpy_builtin): Try using tree-affine to prove
            non-overlap.
            (loop_distribution::classify_builtin_ldst): Always classify
            as PKIND_MEMMOVE.

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

    (cherry picked from commit c01ae2ab6b227e21835d128c90e974dce4604be9)

[Bug tree-optimization/99954] [8/9 Regression] Copy loop over array of unions at -O3 generates memcpy instead of memmove, resulting in incorrect code

[cvs-commit at gcc dot gnu.org]

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

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

https://gcc.gnu.org/g:b091cb1efa1881e93fb2e264daaab8876acf6800

commit r9-9471-gb091cb1efa1881e93fb2e264daaab8876acf6800
Author: Richard Biener <rguenther@suse.de>
Date:   Wed Apr 7 13:17:05 2021 +0200

    tree-optimization/99954 - fix loop distribution memcpy classification

    This fixes bogus classification of a copy as memcpy.  We cannot use
    plain dependence analysis to decide between memcpy and memmove when
    it computes no dependence.  Instead we have to try harder later which
    the patch does for the gcc.dg/tree-ssa/ldist-24.c testcase by resorting
    to tree-affine to compute the difference between src and dest and
    compare against the copy size.

    2021-04-07  Richard Biener  <rguenther@suse.de>

            PR tree-optimization/99954
            * tree-loop-distribution.c: Include tree-affine.h.
            (generate_memcpy_builtin): Try using tree-affine to prove
            non-overlap.
            (loop_distribution::classify_builtin_ldst): Always classify
            as PKIND_MEMMOVE.

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

[Bug tree-optimization/99954] [8 Regression] Copy loop over array of unions at -O3 generates memcpy instead of memmove, resulting in incorrect code

[cvs-commit at gcc dot gnu.org]

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

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

https://gcc.gnu.org/g:ab620c241b61733c92a7596620b73af4f380b5e0

commit r8-10928-gab620c241b61733c92a7596620b73af4f380b5e0
Author: Richard Biener <rguenther@suse.de>
Date:   Wed Apr 7 13:17:05 2021 +0200

    tree-optimization/99954 - fix loop distribution memcpy classification

    This fixes bogus classification of a copy as memcpy.  We cannot use
    plain dependence analysis to decide between memcpy and memmove when
    it computes no dependence.  Instead we have to try harder later which
    the patch does for the gcc.dg/tree-ssa/ldist-24.c testcase by resorting
    to tree-affine to compute the difference between src and dest and
    compare against the copy size.

    2021-04-07  Richard Biener  <rguenther@suse.de>

            PR tree-optimization/99954
            * tree-loop-distribution.c: Include tree-affine.h.
            (generate_memcpy_builtin): Try using tree-affine to prove
            non-overlap.
            (loop_distribution::classify_builtin_ldst): Always classify
            as PKIND_MEMMOVE.

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

    (cherry picked from commit b091cb1efa1881e93fb2e264daaab8876acf6800)

[Bug tree-optimization/99954] [8 Regression] Copy loop over array of unions at -O3 generates memcpy instead of memmove, resulting in incorrect code

[rguenth at gcc dot gnu.org]

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

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

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

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

[Bug tree-optimization/99954] [8 Regression] Copy loop over array of unions at -O3 generates memcpy instead of memmove, resulting in incorrect code

[cvs-commit at gcc dot gnu.org]

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

--- Comment #11 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:c290e6a0b7a9de5692963affc6627a4af7dc2411

commit r15-491-gc290e6a0b7a9de5692963affc6627a4af7dc2411
Author: Richard Biener <rguenther@suse.de>
Date:   Tue May 14 11:13:51 2024 +0200

    tree-optimization/99954 - redo loop distribution memcpy recognition fix

    The following revisits the fix for PR99954 which was observed as
    causing missed memcpy recognition and instead using memmove for
    non-aliasing copies.  While the original fix mitigated bogus
    recognition of memcpy the root cause was not properly identified.
    The root cause is dr_analyze_indices "failing" to handle union
    references and leaving the DRs indices in a state that's not correctly
    handled by dr_may_alias.  The following mitigates this there
    appropriately, restoring memcpy recognition for non-aliasing copies.

    This makes us run into a latent issue in ptr_deref_may_alias_decl_p
    when the pointer is something like &MEM[0].a in which case we fail
    to handle non-SSA name pointers.  Add code similar to what we have
    in ptr_derefs_may_alias_p.

            PR tree-optimization/99954
            * tree-data-ref.cc (dr_may_alias_p): For bases that are
            not completely analyzed fall back to TBAA and points-to.
            * tree-loop-distribution.cc
            (loop_distribution::classify_builtin_ldst): When there
            is no dependence again classify as memcpy.
            * tree-ssa-alias.cc (ptr_deref_may_alias_decl_p): Verify
            the pointer is an SSA name.

            * gcc.dg/tree-ssa/ldist-40.c: New testcase.