[Bug tree-optimization/107323] New: Problem with GCC optimizition

[Bug tree-optimization/107323] New: Problem with GCC optimizition

[fatemetmhr at gmail dot com]

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

            Bug ID: 107323
           Summary: Problem with GCC optimizition
           Product: gcc
           Version: 11.2.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: fatemetmhr at gmail dot com
  Target Milestone: ---

Created attachment 53732
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=53732&action=edit
The code

Hi! 

I faced a problem with GCC optimizitions on codeforces.com. I used GNU G++20
11.2.0 (64 bit, winlibs) for my code but the bug can be found in GCC 11.2.0
anywhere else (and even with some other versions of GCC).

Here's the compilation command used in Codeforces:
g++ -Wall -Wextra -Wconversion -static -DONLINE_JUDGE -Wl,--stack=268435456 -O2
-std=c++20 <source>

There's no error or warning while compiling the code. 
The code has different results while using GCC 11.2.0 and GCC 9.2.0. 

There's a problem with -ftree-loop-distribute-patterns. The flag made GCC
generate  a wrong code, including a memset after the `for` part ends, so the
variables will be set to 0 at the end of the process. 
This flag is obviously doing wrong while optimizing the code. And, somehow, it
can be fixed while using -ftree-vectorize. Which isn't turned on automatically
in -O2 with GCC 11.2.0 .
Anyway some other versions of GCC (like 12) seems to still have the problem
with -ftree-loop-distribute-patterns, but just because of using
-ftree-vectorize, they works correctly.

I posted many other codes here, using different optimizitions flags:
https://codeforces.com/blog/entry/108168

[Bug tree-optimization/107323] [10/11/12 Regression] Loop distribute issue

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|                            |10.1.0, 13.0
            Summary|Problem with GCC            |[10/11/12 Regression] Loop
                   |optimizition                |distribute issue
           Keywords|                            |needs-bisection, wrong-code
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2022-10-19
   Target Milestone|---                         |10.5
      Known to fail|                            |10.2.0, 10.4.0, 11.1.0,
                   |                            |12.2.0
             Status|UNCONFIRMED                 |NEW

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Looks to be fixed on the trunk; sometime after 20220708 .
Options tested: `-O2  -fno-tree-vectorize` which is able to reproduce the issue
on 12.1.0

[Bug tree-optimization/107323] [10/11/12 Regression] Loop distribute issue

[marxin at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |marxin at gcc dot gnu.org

--- Comment #2 from Martin Liška <marxin at gcc dot gnu.org> ---
Simpler C test-case:

$ cat pr107323.c
int A[4];
int B[4];

static const char *__attribute__((noipa)) foo()
{
  return "1";
}

int main()
{
    const char *s = foo();

    A[0] = 1000;
    for(int i = 1; i < 4; ++i) {
        B[i] = 0;
        A[i] = 0;
        if(s[0])
            B[i] = 1;
        A[i] = A[i - 1];
    }

    __builtin_printf ("A[3] = %d\n", A[3]);
    if (A[3] != 1000)
      __builtin_abort ();
}

[Bug tree-optimization/107323] [10/11/12 Regression] Loop distribute issue

[marxin at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rguenth at gcc dot gnu.org
           Keywords|needs-bisection             |

--- Comment #3 from Martin Liška <marxin at gcc dot gnu.org> ---
Fixed on master with r13-1732-g87f46a16ec05beb5 and likely started with
r11-1565-g2c0069fafb53ccb7.

Richi: Can you consider backporting the revision?

[Bug tree-optimization/107323] [10/11/12 Regression] Loop distribute issue

[rguenth at gcc dot gnu.org]

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

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

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

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Martin Liška from comment #3)
> Fixed on master with r13-1732-g87f46a16ec05beb5 and likely started with
> r11-1565-g2c0069fafb53ccb7.
> 
> Richi: Can you consider backporting the revision?

The fix is just a cost modeling fix which makes a real issue latent.

I will have a look.

[Bug tree-optimization/107323] [10/11/12 Regression] Loop distribute issue

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |amker at gcc dot gnu.org

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
OK, so we seem to get unresolved dependences for which we insert an alias check
but then we end up somewhat randomly ordering partitions, first clearing B[],
then doing the non-clearing part of the loop and then afterwards the
clearing of A[] (which is the issue).

I think the issue is that in this case we have a WAW dependence and a
RAW dependence that can be resolved with an alias check.  Initially all
three partitions are in the same SCC and thus get "random" postorder.
But when resolving alias dependences that gets rectified - but for some
reason we restore the "corrupted" postorder from the random one before
sorting after it.

The comments in loop_distribution::break_alias_scc_partitions seem to
contradict themselves here:

      /* Collect data dependences for runtime alias checks to break SCCs.  */
      if (bitmap_count_bits (sccs_to_merge) != (unsigned) num_sccs)
        {
          /* Record the postorder information which will be corrupted by next
             graph SCC finding call.  */
          for (i = 0; i < pg->n_vertices; ++i)
            cbdata.vertices_post[i] = pg->vertices[i].post;

          /* Run SCC finding algorithm again, with alias dependence edges
             skipped.  This is to topologically sort partitions according to
             compilation time known dependence.  Note the topological order
             is stored in the form of pg's post order number.  */
          num_sccs_no_alias = graphds_scc (pg, NULL, pg_skip_alias_edge);

not "fixing" the postorder resolves this PR.

The restoring of postorder was done to fix PR95638 where previously a
fix for PR94125 tried to fix the case where we merge all partitions in
a SCC but the postorder of the prevailing partiton got it scheduled
wrongly (I don't see how that can happen though).  Unfortunately
the testcase no longer triggers the late partition merging.

But clearly simply restoring the original postorder is wrong here.

I need to go back and revisit PR94125 when it was reproducible, it
was fixed with r10-7184-ge4e9a59105a81c

[Bug tree-optimization/107323] [10/11/12 Regression] Loop distribute issue

[rguenth at gcc dot gnu.org]

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

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
Ah - we are merging _original_ SCCs here, so vertices that might not be in the
same component after the second graphds_scc.  So it seems

      /* If all partitions in a SCC have the same type, we can simply merge the
         SCC.  This loop finds out such SCCS and record them in bitmap.  */
      bitmap_set_range (sccs_to_merge, 0, (unsigned) num_sccs);
      for (i = 0; i < num_sccs; ++i)
        {
...

should better be reflected to the graph _before_ the alias ordering
graphds_scc.

[Bug tree-optimization/107323] [10/11/12 Regression] Loop distribute issue

[rguenth at gcc dot gnu.org]

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

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> ---
Created attachment 53740
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=53740&action=edit
tentative patch

When implementing that I noticed that the set of DRs we use for versioning are
_not_ enough to break the SCC.  Basically I swapped

         /* Run SCC finding algorithm again, with alias dependence edges
            skipped.  This is to topologically sort partitions according to
            compilation time known dependence.  Note the topological order
            is stored in the form of pg's post order number.  */
         num_sccs_no_alias = graphds_scc (pg, NULL, pg_skip_alias_edge);
         gcc_assert (partitions->length () == (unsigned) num_sccs_no_alias);
         /* With topological order, we can construct two subgraphs L and R.
            L contains edge <x, y> where x < y in terms of post order, while
            R contains edge <x, y> where x > y.  Edges for compilation time
            known dependence all fall in R, so we break SCCs by removing all
            (alias) edges of in subgraph L.  */
         for_each_edge (pg, pg_collect_alias_ddrs, &cbdata);

doing pg_collect_alias_ddrs first and clearing all not collected ->alias_ddrs
so we end up only ignoring those edges we version.  For the testcase
at hand the patch then ICEs at the assert

         gcc_assert (partitions->length () == (unsigned) num_sccs_no_alias);

which means that not all SCCs were broken by this.  I think the issue is
that we do

  /* Vertices are topologically sorted according to compilation time
     known dependences, so we can break strong connected components
     by removing edges of the opposite direction, i.e, edges pointing
     from vertice with smaller post number to vertice with bigger post
     number.  */
  if (g->vertices[i].post < g->vertices[j].post

originally we are comparing SCCs of the graph with all edges and the
postorder numbers of the graph with all alias_ddr edges removed (and
thus no SCCs).  That seems unreliable at best.  I notice that with
the proposed change we change that so the postorder numbers are also
for the graph with all edges which means the comment no longer holds.
Maybe it also really tries to check i < j and not the postorder numbers.

I need to look closer.

[Bug tree-optimization/107323] [10/11/12 Regression] Loop distribute issue

[rguenth at gcc dot gnu.org]

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

--- Comment #8 from Richard Biener <rguenth at gcc dot gnu.org> ---
OK, so I think I found an alternate fix for PR94125 that makes more sense. 
When 
deciding to merge SCCs rather than breaking them we have to make sure to _not_
ignore the alias edges in those SCCs when doing the final SCC discovery so
postorder info correctly reflects this merging.

That allows us to remove the save/restore of the wrong postorder (just removing
that reproduces PR94125 on the gcc 10 branch again), fixing this bug.

[Bug tree-optimization/107323] [10/11/12 Regression] Loop distribute issue

[cvs-commit at gcc dot gnu.org]

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

--- Comment #9 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:09f9814dc02c161ed78604c6df70b19b596f7524

commit r13-3432-g09f9814dc02c161ed78604c6df70b19b596f7524
Author: Richard Biener <rguenther@suse.de>
Date:   Fri Oct 21 09:45:44 2022 +0200

    tree-optimization/107323 - loop distribution partition ordering issue

    The following reverts part of the PR94125 fix which causes us to
    use a bogus partition ordering after applying versioning for
    alias to the testcase in PR107323.  Instead PR94125 is fixed by
    appropriately considering to be merged SCCs when skipping edges
    we want to ignore because of the alias versioning.

            PR tree-optimization/107323
            * tree-loop-distribution.cc (pg_unmark_merged_alias_ddrs):
            New function.
            (loop_distribution::break_alias_scc_partitions): Revert
            postorder save/restore from the PR94125 fix.  Instead
            make sure to not ignore edges from SCCs we are going to
            merge.

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

[Bug tree-optimization/107323] [10/11/12 Regression] Loop distribute issue

[cvs-commit at gcc dot gnu.org]

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

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

https://gcc.gnu.org/g:19a9b5e587e87f524425864dba989eeef8bfffbb

commit r12-8855-g19a9b5e587e87f524425864dba989eeef8bfffbb
Author: Richard Biener <rguenther@suse.de>
Date:   Fri Oct 21 09:45:44 2022 +0200

    tree-optimization/107323 - loop distribution partition ordering issue

    The following reverts part of the PR94125 fix which causes us to
    use a bogus partition ordering after applying versioning for
    alias to the testcase in PR107323.  Instead PR94125 is fixed by
    appropriately considering to be merged SCCs when skipping edges
    we want to ignore because of the alias versioning.

            PR tree-optimization/107323
            * tree-loop-distribution.cc (pg_unmark_merged_alias_ddrs):
            New function.
            (loop_distribution::break_alias_scc_partitions): Revert
            postorder save/restore from the PR94125 fix.  Instead
            make sure to not ignore edges from SCCs we are going to
            merge.

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

    (cherry picked from commit 09f9814dc02c161ed78604c6df70b19b596f7524)

[Bug tree-optimization/107323] [10/11 Regression] Loop distribute issue

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|                            |12.2.1
            Summary|[10/11/12 Regression] Loop  |[10/11 Regression] Loop
                   |distribute issue            |distribute issue

--- Comment #11 from Richard Biener <rguenth at gcc dot gnu.org> ---
Truly fixed on trunk now and also the GCC 12 branch.  I'll wait a bit before
backporting further, the patch cherry-picks to all older branches just fine in
case you want to try on your full code with GCC 11.

[Bug tree-optimization/107323] [10/11 Regression] Loop distribute issue

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |hahnjo at hahnjo dot de

--- Comment #12 from Richard Biener <rguenth at gcc dot gnu.org> ---
*** Bug 108008 has been marked as a duplicate of this bug. ***

[Bug tree-optimization/107323] [10/11 Regression] Loop distribute issue

[cvs-commit at gcc dot gnu.org]

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

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

https://gcc.gnu.org/g:28fe903730d2c6e424732184ab2d8b1e7d46db6c

commit r11-10482-g28fe903730d2c6e424732184ab2d8b1e7d46db6c
Author: Richard Biener <rguenther@suse.de>
Date:   Fri Oct 21 09:45:44 2022 +0200

    tree-optimization/107323 - loop distribution partition ordering issue

    The following reverts part of the PR94125 fix which causes us to
    use a bogus partition ordering after applying versioning for
    alias to the testcase in PR107323.  Instead PR94125 is fixed by
    appropriately considering to be merged SCCs when skipping edges
    we want to ignore because of the alias versioning.

            PR tree-optimization/107323
            * tree-loop-distribution.c (pg_unmark_merged_alias_ddrs):
            New function.
            (loop_distribution::break_alias_scc_partitions): Revert
            postorder save/restore from the PR94125 fix.  Instead
            make sure to not ignore edges from SCCs we are going to
            merge.

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

    (cherry picked from commit 09f9814dc02c161ed78604c6df70b19b596f7524)

[Bug tree-optimization/107323] [10 Regression] Loop distribute issue

[cvs-commit at gcc dot gnu.org]

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

--- Comment #14 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:95e5c07aa216fe2863ea02e8508a51b5f7528839

commit r10-11178-g95e5c07aa216fe2863ea02e8508a51b5f7528839
Author: Richard Biener <rguenther@suse.de>
Date:   Fri Oct 21 09:45:44 2022 +0200

    tree-optimization/107323 - loop distribution partition ordering issue

    The following reverts part of the PR94125 fix which causes us to
    use a bogus partition ordering after applying versioning for
    alias to the testcase in PR107323.  Instead PR94125 is fixed by
    appropriately considering to be merged SCCs when skipping edges
    we want to ignore because of the alias versioning.

            PR tree-optimization/107323
            * tree-loop-distribution.c (pg_unmark_merged_alias_ddrs):
            New function.
            (loop_distribution::break_alias_scc_partitions): Revert
            postorder save/restore from the PR94125 fix.  Instead
            make sure to not ignore edges from SCCs we are going to
            merge.

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

    (cherry picked from commit 09f9814dc02c161ed78604c6df70b19b596f7524)

[Bug tree-optimization/107323] [10 Regression] Loop distribute issue

[rguenth at gcc dot gnu.org]

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

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

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

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