[Bug tree-optimization/94969] New: Invalid loop distribution

[Bug tree-optimization/94969] New: Invalid loop distribution

[krebbel at gcc dot gnu.org]

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

            Bug ID: 94969
           Summary: Invalid loop distribution
           Product: gcc
           Version: 11.0
            Status: UNCONFIRMED
          Severity: critical
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: krebbel at gcc dot gnu.org
  Target Milestone: ---

Created attachment 48461
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=48461&action=edit
Testcase

The attached testcase aborts on x86 when compiled with -O3. It succeeds with
-O2 or -O3 -fno-loop-distribution.

The loop is distributed separating the two statements. This affects the result
of the testcase.

 for (; c <= 1; c++) {
    f[b] = g;
    f[b].e ^= 1;
  }

[Bug tree-optimization/94969] Invalid loop distribution

[krebbel at gcc dot gnu.org]

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

--- Comment #1 from Andreas Krebbel <krebbel at gcc dot gnu.org> ---
The problem arises from dr_analyze_innermost not being able to analyze the
bitfield access. However, the returned error is ignored in
find_data_references_in_stmt and execution continues with bogus values in the
data reference object.

[Bug tree-optimization/94969] Invalid loop distribution

[krebbel at gcc dot gnu.org]

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

--- Comment #2 from Andreas Krebbel <krebbel at gcc dot gnu.org> ---
Created attachment 48462
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=48462&action=edit
Experimental patch

With this patch the returned error is propagated. Unfortunately this prevents
some vectorizations e.g. in gcc.dg/vect/vect-simd-5.c. The reason appears to be
the "evolution of base is not affine" failure in dr_analyze_innermost which now
also gets propagated.

[Bug tree-optimization/94969] Invalid loop distribution

[krebbel at gcc dot gnu.org]

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

Andreas Krebbel <krebbel at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P2
               Host|                            |x86_64-gnu-linux

[Bug tree-optimization/94969] [8/9/10/11 Regression] Invalid loop distribution

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |8.5
           Keywords|                            |wrong-code
   Last reconfirmed|                            |2020-05-06
             Status|UNCONFIRMED                 |NEW
            Summary|Invalid loop distribution   |[8/9/10/11 Regression]
                   |                            |Invalid loop distribution
      Known to work|                            |7.5.0
     Ever confirmed|0                           |1

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
Confirmed.  Works fine in GCC 7 which also says

Creating dr for f[pretmp_5].e
analyze_innermost: Applying pattern match.pd:84, generic-match.c:11461
failed: bit offset alignment.
        base_address:
        offset from base address:
        constant offset from base address:
        step:
        aligned to:
        base_object: f
        Access function 0: 7
        Access function 1: pretmp_5

but

(compute_affine_dependence
  stmt_a: f[pretmp_5] = g;
  stmt_b: _2 = f[pretmp_5].e;
) -> dependence analysis failed

instead of

(compute_affine_dependence
  stmt_a: f[pretmp_5] = g;
  stmt_b: _2 = f[pretmp_5].e;
(analyze_overlapping_iterations
  (chrec_a = pretmp_5)
  (chrec_b = pretmp_5)
  (overlap_iterations_a = [0])
  (overlap_iterations_b = [0]))
)

[Bug tree-optimization/94969] [8/9/10/11 Regression] Invalid loop distribution since r8-2390-gdfbddbeb1ca912c9

[marxin at gcc dot gnu.org]

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

Martin Liška <marxin at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[8/9/10/11 Regression]      |[8/9/10/11 Regression]
                   |Invalid loop distribution   |Invalid loop distribution
                   |                            |since
                   |                            |r8-2390-gdfbddbeb1ca912c9
                 CC|                            |marxin at gcc dot gnu.org,
                   |                            |rsandifo at gcc dot gnu.org

--- Comment #4 from Martin Liška <marxin at gcc dot gnu.org> ---
Confirmed, started with -O3 -ftree-loop-distribution since
r8-2390-gdfbddbeb1ca912c9

[Bug tree-optimization/94969] [8/9/10/11 Regression] Invalid loop distribution since r8-2390-gdfbddbeb1ca912c9

[rguenth at gcc dot gnu.org]

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

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
So I think the issue is not dependence testing but loop distribution accepting
a
zero dependence distance as OK.  Of course dependence analysis is quite useless
here since the accesses are to the same location in every iteration.

Bin, maybe you can share your thoughts on this issue?

The testcase doesn't need bitfields - those just disable the cost model
which otherwise prevents the distribution.

diff --git a/gcc/tree-loop-distribution.c b/gcc/tree-loop-distribution.c
index 44423215332..ac272d63c3d 100644
--- a/gcc/tree-loop-distribution.c
+++ b/gcc/tree-loop-distribution.c
@@ -2852,6 +2852,7 @@ loop_distribution::finalize_partitions (class loop *loop,
   /* Don't distribute current loop into too many loops given we don't have
      memory stream cost model.  Be even more conservative in case of loop
      nest distribution.  */
+#if 0
   if ((same_type_p && num_builtin == 0
        && (loop->inner == NULL || num_normal != 2 || num_partial_memset != 1))
       || (loop->inner != NULL
@@ -2867,6 +2868,7 @@ loop_distribution::finalize_partitions (class loop *loop,
        }
       partitions->truncate (1);
     }
+#endif

   /* Fuse memset builtins if possible.  */
   if (partitions->length () > 1)


makes the testcase miscompiled even with the : 7 and : 2 commented, so plain

struct S {
  signed m;
  signed e;
};

[Bug tree-optimization/94969] [8/9/10/11 Regression] Invalid loop distribution since r8-2390-gdfbddbeb1ca912c9

[rguenth at gcc dot gnu.org]

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

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
Before Richards change we likely gave up on the mismatch in access function
dimensionality for f[b] vs. f[b].e but now we compute a dependence distance
of zero.

[Bug tree-optimization/94969] [8/9/10/11 Regression] Invalid loop distribution since r8-2390-gdfbddbeb1ca912c9

[amker at gcc dot gnu.org]

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

--- Comment #7 from bin cheng <amker at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #5)
> So I think the issue is not dependence testing but loop distribution
> accepting a
> zero dependence distance as OK.  Of course dependence analysis is quite
> useless
> here since the accesses are to the same location in every iteration.
> 
> Bin, maybe you can share your thoughts on this issue?
> 
> The testcase doesn't need bitfields - those just disable the cost model
> which otherwise prevents the distribution.
> 
> diff --git a/gcc/tree-loop-distribution.c b/gcc/tree-loop-distribution.c
> index 44423215332..ac272d63c3d 100644
> --- a/gcc/tree-loop-distribution.c
> +++ b/gcc/tree-loop-distribution.c
> @@ -2852,6 +2852,7 @@ loop_distribution::finalize_partitions (class loop
> *loop,
>    /* Don't distribute current loop into too many loops given we don't have
>       memory stream cost model.  Be even more conservative in case of loop
>       nest distribution.  */
> +#if 0
>    if ((same_type_p && num_builtin == 0
>         && (loop->inner == NULL || num_normal != 2 || num_partial_memset !=
> 1))
>        || (loop->inner != NULL
> @@ -2867,6 +2868,7 @@ loop_distribution::finalize_partitions (class loop
> *loop,
>         }
>        partitions->truncate (1);
>      }
> +#endif
>  
>    /* Fuse memset builtins if possible.  */
>    if (partitions->length () > 1)
> 
> 
> makes the testcase miscompiled even with the : 7 and : 2 commented, so plain
> 
> struct S {
>   signed m;
>   signed e;
> };

I think there is something wrong in data dependence analysis, however,
Richard's change just exposed it.  
Given below loop and data refs:

for (...) {
  array[loop_invariant] = x;  // ref1
  array[loop_invariant] ^= 1; // ref2
}
There are both output dependence for ref2(iteration i) -> ref1 (iteration i +
1), and for ref1(iteration i) -> ref2(iteration i).

It seems to me now the first one is missing.  Will dig deeper.

[Bug tree-optimization/94969] [8/9/10/11 Regression] Invalid loop distribution since r8-2390-gdfbddbeb1ca912c9

[amker at gcc dot gnu.org]

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

--- Comment #8 from bin cheng <amker at gcc dot gnu.org> ---
Root cause is in build_classic_dist_vector -> constant_access_functions which
adds unit distance vector only in case of constant access function.  It should
cover invariant cases.  Testing a patch.  Thanks

[Bug tree-optimization/94969] [8/9/10/11 Regression] Invalid loop distribution since r8-2390-gdfbddbeb1ca912c9

[cvs-commit at gcc dot gnu.org]

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

--- Comment #9 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Bin Cheng <amker@gcc.gnu.org>:

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

commit r11-345-gf6e1a4cd83190746b6544917f7526fa480ca5f18
Author: Bin Cheng <bin.cheng@linux.alibaba.com>
Date:   Wed May 13 11:37:47 2020 +0800

    Add missing unit dependence vector in data dependence analysis

    Current data dependence analysis misses unit distant vector if DRs in
    DDR have the same invariant access functions.  This adds the vector as
    the constant access function case.

    2020-05-13  Bin Cheng  <bin.cheng@linux.alibaba.com>
    PR tree-optimization/94969

    gcc/
        * tree-data-dependence.c (constant_access_functions): Rename to...
        (invariant_access_functions): ...this.  Add parameter.  Check for
        invariant access function, rather than constant.
        (build_classic_dist_vector): Call above function.
        * tree-loop-distribution.c (pg_add_dependence_edges): Add comment.

    gcc/testsuite/
        * gcc.dg/tree-ssa/pr94969.c: New test.

[Bug tree-optimization/94969] [8/9/10/11 Regression] Invalid loop distribution since r8-2390-gdfbddbeb1ca912c9

[amker at gcc dot gnu.org]

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

--- Comment #10 from bin cheng <amker at gcc dot gnu.org> ---
Hi，should I backport this and PR95110 to branches?  Thanks

[Bug tree-optimization/94969] [8/9/10/11 Regression] Invalid loop distribution since r8-2390-gdfbddbeb1ca912c9

[rguenther at suse dot de]

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

--- Comment #11 from rguenther at suse dot de <rguenther at suse dot de> ---
On Mon, 18 May 2020, amker at gcc dot gnu.org wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=94969
> 
> --- Comment #10 from bin cheng <amker at gcc dot gnu.org> ---
> Hi，should I backport this and PR95110 to branches?  Thanks

Yes.  Thanks.

[Bug tree-optimization/94969] [8/9/10/11 Regression] Invalid loop distribution since r8-2390-gdfbddbeb1ca912c9

[cvs-commit at gcc dot gnu.org]

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

--- Comment #12 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-9 branch has been updated by Bin Cheng <amker@gcc.gnu.org>:

https://gcc.gnu.org/g:466ad887c9e1cd5a6762e7ec620eef2c8175b50d

commit r9-8614-g466ad887c9e1cd5a6762e7ec620eef2c8175b50d
Author: Bin Cheng <bin.cheng@linux.alibaba.com>
Date:   Fri May 22 11:42:11 2020 +0800

    Add missing unit dependence vector in data dependence analysis

    Current data dependence analysis misses unit distant vector if DRs in
    DDR have the same invariant access functions.  This adds the vector as
    the constant access function case.

    Also fix typo in testcase.

    Backport from master.

    2020-05-13  Bin Cheng  <bin.cheng@linux.alibaba.com>

    gcc/
            PR tree-optimization/94969
            * tree-data-ref.c (constant_access_functions): Rename to...
            (invariant_access_functions): ...this.  Add parameter.  Check for
            invariant access function, rather than constant.
            (build_classic_dist_vector): Call above function.
            * tree-loop-distribution.c (pg_add_dependence_edges): Add comment.

    gcc/testsuite/
            PR tree-optimization/94969
            * gcc.dg/tree-ssa/pr94969.c: New test.

    2020-05-13  Jakub Jelinek  <jakub@redhat.com>

    gcc/testsuite/
            PR tree-optimization/95110
            * gcc.dg/tree-ssa/pr94969.c: Swap scan-tree-dump-not arguments.

[Bug tree-optimization/94969] [8/9/10/11 Regression] Invalid loop distribution since r8-2390-gdfbddbeb1ca912c9

[krebbel at gcc dot gnu.org]

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

Andreas Krebbel <krebbel at gcc dot gnu.org> changed:

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

--- Comment #13 from Andreas Krebbel <krebbel at gcc dot gnu.org> ---
Fixed by Bin Cheng. Thanks!

[Bug tree-optimization/94969] [8/9/10/11 Regression] Invalid loop distribution since r8-2390-gdfbddbeb1ca912c9

[krebbel at gcc dot gnu.org]

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

Andreas Krebbel <krebbel at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|RESOLVED                    |CLOSED

--- Comment #14 from Andreas Krebbel <krebbel at gcc dot gnu.org> ---
Closing

[Bug tree-optimization/94969] [8/10 Regression] Invalid loop distribution since r8-2390-gdfbddbeb1ca912c9

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|FIXED                       |---
      Known to work|                            |9.3.1
             Status|CLOSED                      |ASSIGNED
      Known to fail|                            |10.1.0
            Summary|[8/9/10/11 Regression]      |[8/10 Regression] Invalid
                   |Invalid loop distribution   |loop distribution since
                   |since                       |r8-2390-gdfbddbeb1ca912c9
                   |r8-2390-gdfbddbeb1ca912c9   |

--- Comment #15 from Richard Biener <rguenth at gcc dot gnu.org> ---
I don't see the commit on the GCC 10 branch nor the GCC 8 branch.  Master and
GCC 9 are fixed though.

[Bug tree-optimization/94969] [8/10 Regression] Invalid loop distribution since r8-2390-gdfbddbeb1ca912c9

[amker at gcc dot gnu.org]

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

--- Comment #16 from bin cheng <amker at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #15)
> I don't see the commit on the GCC 10 branch nor the GCC 8 branch.  Master
> and GCC 9 are fixed though.

Will backport the 10 and 8, thanks for reminding.

[Bug tree-optimization/94969] [8/10 Regression] Invalid loop distribution since r8-2390-gdfbddbeb1ca912c9

[cvs-commit at gcc dot gnu.org]

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

--- Comment #17 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-10 branch has been updated by Bin Cheng <amker@gcc.gnu.org>:

https://gcc.gnu.org/g:63c00a0c6543ce6d55e0ebc97ddbc1d36fb1289c

commit r10-8332-g63c00a0c6543ce6d55e0ebc97ddbc1d36fb1289c
Author: Bin Cheng <bin.cheng@linux.alibaba.com>
Date:   Sat Jun 20 14:24:31 2020 +0800

    Add missing unit dependence vector in data dependence analysis

    Current data dependence analysis misses unit distant vector if DRs in
    DDR have the same invariant access functions.  This adds the vector as
    the constant access function case.

    Also fix typo in testcase.

    Backport from master.

    2020-06-20  Bin Cheng  <bin.cheng@linux.alibaba.com>

    gcc/
            PR tree-optimization/94969
            * tree-data-ref.c (constant_access_functions): Rename to...
            (invariant_access_functions): ...this.  Add parameter.  Check for
            invariant access function, rather than constant.
            (build_classic_dist_vector): Call above function.
            * tree-loop-distribution.c (pg_add_dependence_edges): Add comment.

    gcc/testsuite/
            PR tree-optimization/94969
            * gcc.dg/tree-ssa/pr94969.c: New test.

    2020-06-20  Jakub Jelinek  <jakub@redhat.com>

    gcc/testsuite/
            PR tree-optimization/95110
            * gcc.dg/tree-ssa/pr94969.c: Swap scan-tree-dump-not arguments.

[Bug tree-optimization/94969] [8/10 Regression] Invalid loop distribution since r8-2390-gdfbddbeb1ca912c9

[cvs-commit at gcc dot gnu.org]

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

--- Comment #18 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-8 branch has been updated by Bin Cheng <amker@gcc.gnu.org>:

https://gcc.gnu.org/g:0a7a2b7c64a77218e504e8390af29cfa5f79a242

commit r8-10320-g0a7a2b7c64a77218e504e8390af29cfa5f79a242
Author: Bin Cheng <bin.cheng@linux.alibaba.com>
Date:   Sat Jun 20 16:56:21 2020 +0800

    Add missing unit dependence vector in data dependence analysis

    Current data dependence analysis misses unit distant vector if DRs in
    DDR have the same invariant access functions.  This adds the vector as
    the constant access function case.

    Also fix typo in testcase.

    Backport from master commit: 287552950d56be47adb6b6bf2eae2d612233eaec
    and f6e1a4cd83190746b6544917f7526fa480ca5f18

    2020-06-20  Bin Cheng  <bin.cheng@linux.alibaba.com>

    gcc/
            PR tree-optimization/94969
            * tree-data-ref.c (constant_access_functions): Rename to...
            (invariant_access_functions): ...this.  Add parameter.  Check for
            invariant access function, rather than constant.
            (build_classic_dist_vector): Call above function.
            * tree-loop-distribution.c (pg_add_dependence_edges): Add comment.

    gcc/testsuite/
            PR tree-optimization/94969
            * gcc.dg/tree-ssa/pr94969.c: New test.

    2020-06-20  Jakub Jelinek  <jakub@redhat.com>

    gcc/testsuite/
            PR tree-optimization/95110
            * gcc.dg/tree-ssa/pr94969.c: Swap scan-tree-dump-not arguments.

[Bug tree-optimization/94969] [8/10 Regression] Invalid loop distribution since r8-2390-gdfbddbeb1ca912c9

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to fail|                            |8.4.0
             Status|ASSIGNED                    |RESOLVED
      Known to work|                            |10.1.1, 8.4.1
         Resolution|---                         |FIXED

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