[Bug tree-optimization/98736] New: Wrong partition order generated in loop distribution pass

[Bug tree-optimization/98736] New: Wrong partition order generated in loop distribution pass

[krebbel at gcc dot gnu.org]

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

            Bug ID: 98736
           Summary: Wrong partition order generated in loop distribution
                    pass
           Product: gcc
           Version: 11.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: krebbel at gcc dot gnu.org
  Target Milestone: ---

int a[6];
char b, c;
int main() {
  int d[4] = {0, 0, 0, 0};
  for (c = 0; c <= 5; c++) {
    for (b = 2; b != 0; b++)
      a[c] = 8;
    a[c] = d[3];
  }
  if (a[0] != 0)
    __builtin_abort();
}

Aborts when compiled with:
gcc -Os -march=z13 t.c -o t

Succeeds with:
gcc -O3 -march=z13 t.c -o t

The outer loop is recognized as clearmem. Unfortunately it is generated before
the inner loop body.

[Bug tree-optimization/98736] Wrong partition order generated in loop distribution pass

[krebbel at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |wrong-code
           Priority|P3                          |P2
             Target|                            |s390x

[Bug tree-optimization/98736] [10/11 Regression] Wrong partition order generated in loop distribution pass

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to fail|                            |10.2.1, 11.0
      Known to work|                            |9.3.1
             Status|UNCONFIRMED                 |ASSIGNED
   Target Milestone|---                         |10.3
            Summary|Wrong partition order       |[10/11 Regression] Wrong
                   |generated in loop           |partition order generated
                   |distribution pass           |in loop distribution pass
             Target|s390x                       |s390x, x86_64-*-*
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2021-01-19
                 CC|                            |rguenth at gcc dot gnu.org

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
Confirmed on x86_64 as well, also fails with GCC 10, GCC 9 is fine.

[Bug tree-optimization/98736] [10/11 Regression] Wrong partition order generated in loop distribution pass since r10-619-g5879ab5fafedc8f6

[marxin at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[10/11 Regression] Wrong    |[10/11 Regression] Wrong
                   |partition order generated   |partition order generated
                   |in loop distribution pass   |in loop distribution pass
                   |                            |since
                   |                            |r10-619-g5879ab5fafedc8f6
                 CC|                            |marxin at gcc dot gnu.org

--- Comment #2 from Martin Liška <marxin at gcc dot gnu.org> ---
Started with r10-619-g5879ab5fafedc8f6 when -ftree-loop-distribute-patterns was
enabled for -O2. However, adding -ftree-loop-distribute-patterns to -Os does
not point to an older revision.

[Bug tree-optimization/98736] [10/11 Regression] Wrong partition order generated in loop distribution pass since r10-619-g5879ab5fafedc8f6

[amker at gcc dot gnu.org]

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

--- Comment #3 from bin cheng <amker at gcc dot gnu.org> ---
hmm, seems topological order isn't enough for distributing a loop nest, we need
topological order plus inner loop depth-first.

[Bug tree-optimization/98736] [10/11 Regression] Wrong partition order generated in loop distribution pass since r10-619-g5879ab5fafedc8f6

[amker at gcc dot gnu.org]

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

--- Comment #4 from bin cheng <amker at gcc dot gnu.org> ---
(In reply to bin cheng from comment #3)
> hmm, seems topological order isn't enough for distributing a loop nest, we
> need topological order plus inner loop depth-first.

Well, not really.  In this case, problem is that rev-post order algorithm puts
"a[c] = d[3];" before the inner loop which violates the original program order. 

Seems that it can be fixed by inner loop depth-first order wrto how we
distribute inner loop, but I am not sure if this always preserves programming
order because loop has been reformed by various optimizers.

[Bug tree-optimization/98736] [10/11 Regression] Wrong partition order generated in loop distribution pass since r10-619-g5879ab5fafedc8f6

[cvs-commit at gcc dot gnu.org]

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

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

commit r11-8023-ge0bdccac582c01c928a05f26edcd8f5ac24669eb
Author: Bin Cheng <bin.cheng@linux.alibaba.com>
Date:   Wed Apr 7 10:24:32 2021 +0800

    tree-optimization/98736 - use programing order preserved RPO in ldist

    Tree loop distribution uses RPO to build reduced dependence graph,
    it's important that RPO preserves the original programing order.
    Though it usually does so, when distributing loop nest, exit BB can
    be placed before some loop BBs while after loop header.  This patch
    fixes the issue by calling rev_post_order_and_mark_dfs_back_seme.

    gcc/ChangeLog:

            PR tree-optimization/98736
            * tree-loop-distribution.c
            * (loop_distribution::bb_top_order_init):
            Compute RPO with programing order preserved by calling function
            rev_post_order_and_mark_dfs_back_seme.

    gcc/testsuite/ChangeLog:

            PR tree-optimization/98736
            * gcc.c-torture/execute/pr98736.c: New test.

[Bug tree-optimization/98736] [10/11 Regression] Wrong partition order generated in loop distribution pass since r10-619-g5879ab5fafedc8f6

[amker at gcc dot gnu.org]

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

--- Comment #6 from bin cheng <amker at gcc dot gnu.org> ---
Shall this be backported to 10/11 later? Thanks.

[Bug tree-optimization/98736] [10/11 Regression] Wrong partition order generated in loop distribution pass since r10-619-g5879ab5fafedc8f6

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |zhendong.su at inf dot ethz.ch

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

[Bug tree-optimization/98736] [10 Regression] Wrong partition order generated in loop distribution pass since r10-619-g5879ab5fafedc8f6

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Assignee|amker at gcc dot gnu.org           |rguenth at gcc dot gnu.org
      Known to fail|11.0                        |
            Summary|[10/11 Regression] Wrong    |[10 Regression] Wrong
                   |partition order generated   |partition order generated
                   |in loop distribution pass   |in loop distribution pass
                   |since                       |since
                   |r10-619-g5879ab5fafedc8f6   |r10-619-g5879ab5fafedc8f6
      Known to work|                            |11.0

--- Comment #8 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed on trunk sofar.  I'll see how to arrange backporting (the
rev_post_order_and_mark_dfs_back_seme function on the branch does not provide
the program order constraint we need).

[Bug tree-optimization/98736] [10 Regression] Wrong partition order generated in loop distribution pass since r10-619-g5879ab5fafedc8f6

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|10.3                        |10.4

--- Comment #9 from Richard Biener <rguenth at gcc dot gnu.org> ---
GCC 10.3 is being released, retargeting bugs to GCC 10.4.

[Bug tree-optimization/98736] [10 Regression] Wrong partition order generated in loop distribution pass since r10-619-g5879ab5fafedc8f6

[cvs-commit at gcc dot gnu.org]

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

--- Comment #10 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:6c6a1173cccfd9c466e43bafa7ef7940b93d1495

commit r10-9758-g6c6a1173cccfd9c466e43bafa7ef7940b93d1495
Author: Bin Cheng <bin.cheng@linux.alibaba.com>
Date:   Wed Apr 7 10:24:32 2021 +0800

    tree-optimization/98736 - use programing order preserved RPO in ldist

    Tree loop distribution uses RPO to build reduced dependence graph,
    it's important that RPO preserves the original programing order.
    Though it usually does so, when distributing loop nest, exit BB can
    be placed before some loop BBs while after loop header.  This patch
    fixes the issue by calling rev_post_order_and_mark_dfs_back_seme.

    gcc/ChangeLog:

            PR tree-optimization/98736
            * tree-loop-distribution.c
            * (loop_distribution::bb_top_order_init):
            Compute RPO with programing order preserved by calling function
            rev_post_order_and_mark_dfs_back_seme.

    gcc/testsuite/ChangeLog:

            PR tree-optimization/98736
            * gcc.c-torture/execute/pr98736.c: New test.

    (cherry picked from commit e0bdccac582c01c928a05f26edcd8f5ac24669eb)

[Bug tree-optimization/98736] [10 Regression] Wrong partition order generated in loop distribution pass since r10-619-g5879ab5fafedc8f6

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |FIXED
      Known to fail|                            |10.3.0
      Known to work|                            |10.3.1

--- Comment #11 from Richard Biener <rguenth at gcc dot gnu.org> ---
I've convinced myself that simply picking those changes is safe.  Thus fixed.