[Bug tree-optimization/101173] New: wrong code at -O3 on x86_64-linux-gnu

[Bug tree-optimization/101173] New: wrong code at -O3 on x86_64-linux-gnu

[qrzhang at gatech dot edu]

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

            Bug ID: 101173
           Summary: wrong code at -O3 on x86_64-linux-gnu
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: qrzhang at gatech dot edu
  Target Milestone: ---

It affects gcc-8 to the trunk. Gcc-7.5.0 works.

$ gcc-trunk -v
Supported LTO compression algorithms: zlib
gcc version 12.0.0 20210622 (experimental) [master revision
f0e40ea0640:393ac5ed7d8:7822285515cd4dab86f722a9f4969b6952904a37] (GCC)



$ gcc-trunk abc.c ; ./a.out > 1.txt
$ gcc-trunk -O3 abc.c ; ./a.out > 2.txt

$ diff 1.txt 2.txt
11c11
< 0
---
> 8

$ cat abc.c
int a[6][9];
char b, c;
short d;
int e, f;
int main() {
  a[1][3] = 8;
  b = 1;
  for (; b <= 5; b++) {
    d = 0;
    for (; d <= 5; d++) {
      c = 0;
      for (; c <= 5; c++)
        a[b][c] = a[b][c + 2] & 216;
    }
  }
  for (; e < 6; e++) {
    f = 0;
    for (; f < 9; f++)
      printf("%d\n", a[e][f]);
  }
}

[Bug tree-optimization/101173] wrong code at -O3 on x86_64-linux-gnu

[qrzhang at gatech dot edu]

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

--- Comment #1 from Qirun Zhang <qrzhang at gatech dot edu> ---
My bisection points to g:fbdec14e80e9399cd301ed3

[Bug tree-optimization/101173] [9/10/11/12 Regression] wrong code at -O3 on x86_64-linux-gnu

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |9.5
           Keywords|                            |wrong-code
                 CC|                            |amker at gcc dot gnu.org
            Summary|wrong code at -O3 on        |[9/10/11/12 Regression]
                   |x86_64-linux-gnu            |wrong code at -O3 on
                   |                            |x86_64-linux-gnu
     Ever confirmed|0                           |1
            Version|unknown                     |12.0
      Known to work|                            |7.5.0
           Priority|P3                          |P2
   Last reconfirmed|                            |2021-06-23
             Status|UNCONFIRMED                 |NEW
      Known to fail|                            |8.5.0

--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
Confirmed.

int a[6][9];
int c;
int main()
{
  a[1][3] = 8;
  for (int b = 1; b <= 5; b++)
    for (int d = 0; d <= 5; d++)
      for (c = 0; c <= 5; c++)
        a[b][c] = a[b][c + 2] & 216;
  for (int e = 0; e < 6; e++)
    for (int f = 0; f < 9; f++)
      if (a[e][f] != 0)
        __builtin_abort ();
  return 0;
}

Fails with -O -floop-interchange already.

[Bug tree-optimization/101173] [9/10/11/12 Regression] wrong code at -O3 on x86_64-linux-gnu

[rguenth at gcc dot gnu.org]

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

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
So we're exchanging the inner two loops

  a[1][3] = 8;
  for (int b = 1; b <= 5; b++)
    for (int d = 0; d <= 5; d++)
      for (c = 0; c <= 5; c++)
        a[b][c] = a[b][c + 2] & 216;

to

  a[1][3] = 8;
  for (int b = 1; b <= 5; b++)
    for (c = 0; c <= 5; c++)
      for (int d = 0; d <= 5; d++)
        a[b][c] = a[b][c + 2] & 216;

but that looks wrong from a dependence analysis perspective.  We have

(compute_affine_dependence
  ref_a: a[b_33][_1], stmt_a: _2 = a[b_33][_1];
  ref_b: a[b_33][c.3_32], stmt_b: a[b_33][c.3_32] = _3;
(analyze_overlapping_iterations
  (chrec_a = {2, +, 1}_5)
  (chrec_b = {0, +, 1}_5)
(analyze_siv_subscript
(analyze_subscript_affine_affine
  (overlaps_a = [0 + 1 * x_1])
  (overlaps_b = [2 + 1 * x_1]))
)
  (overlap_iterations_a = [0 + 1 * x_1])
  (overlap_iterations_b = [2 + 1 * x_1]))
(analyze_overlapping_iterations
  (chrec_a = {1, +, 1}_1)
  (chrec_b = {1, +, 1}_1)
  (overlap_iterations_a = [0])
  (overlap_iterations_b = [0]))
(analyze_overlapping_iterations
  (chrec_a = {0, +, 1}_5)
  (chrec_b = {2, +, 1}_5)
(analyze_siv_subscript
(analyze_subscript_affine_affine
  (overlaps_a = [2 + 1 * x_1])
  (overlaps_b = [0 + 1 * x_1]))
)
  (overlap_iterations_a = [2 + 1 * x_1])
  (overlap_iterations_b = [0 + 1 * x_1]))
(analyze_overlapping_iterations
  (chrec_a = {1, +, 1}_1)
  (chrec_b = {1, +, 1}_1)
  (overlap_iterations_a = [0])
  (overlap_iterations_b = [0]))
(build_classic_dist_vector
  dist_vector = (  0   0   2
  )
)
)

I don't see anything wrong with that at a first glance so the bug must be in
tree_loop_interchange::valid_data_dependences it checks

          /* Be conservative, skip case if either direction at i_idx/o_idx
             levels is not '=' or '<'.  */
          if (dist_vect[i_idx] < 0 || dist_vect[o_idx] < 0)
            return false;

dist_vect is [0 0 2], i_idx 2 and o_idx 1 but I think that dist_vect[o_idx]
should exclude zero, thus

diff --git a/gcc/gimple-loop-interchange.cc b/gcc/gimple-loop-interchange.cc
index f45b9364644..265e36c48d4 100644
--- a/gcc/gimple-loop-interchange.cc
+++ b/gcc/gimple-loop-interchange.cc
@@ -1043,8 +1043,8 @@ tree_loop_interchange::valid_data_dependences (unsigned
i_idx, unsigned o_idx,
            continue;

          /* Be conservative, skip case if either direction at i_idx/o_idx
-            levels is not '=' or '<'.  */
-         if (dist_vect[i_idx] < 0 || dist_vect[o_idx] < 0)
+            levels is not '=' (for the inner loop) or '<'.  */
+         if (dist_vect[i_idx] < 0 || dist_vect[o_idx] <= 0)
            return false;
        }
     }

Bin - does this analysis look sound?

[Bug tree-optimization/101173] [9/10/11/12 Regression] wrong code at -O3 on x86_64-linux-gnu

[rguenth at gcc dot gnu.org]

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

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

For reference this is the patch that completed bootstrap & regtest on
x86_64-unknown-linux-gnu.

[Bug tree-optimization/101173] [9/10/11/12 Regression] wrong code at -O3 on x86_64-linux-gnu

[amker at gcc dot gnu.org]

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

--- Comment #5 from bin cheng <amker at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #3)
> So we're exchanging the inner two loops
> 
>   a[1][3] = 8;
>   for (int b = 1; b <= 5; b++)
>     for (int d = 0; d <= 5; d++)
>       for (c = 0; c <= 5; c++)
>         a[b][c] = a[b][c + 2] & 216;
> 
> to
> 
>   a[1][3] = 8;
>   for (int b = 1; b <= 5; b++)
>     for (c = 0; c <= 5; c++)
>       for (int d = 0; d <= 5; d++)
>         a[b][c] = a[b][c + 2] & 216;
> 
> but that looks wrong from a dependence analysis perspective.  We have
> 
> (compute_affine_dependence
>   ref_a: a[b_33][_1], stmt_a: _2 = a[b_33][_1];
>   ref_b: a[b_33][c.3_32], stmt_b: a[b_33][c.3_32] = _3;
> (analyze_overlapping_iterations
>   (chrec_a = {2, +, 1}_5)
>   (chrec_b = {0, +, 1}_5)
> (analyze_siv_subscript
> (analyze_subscript_affine_affine
>   (overlaps_a = [0 + 1 * x_1])
>   (overlaps_b = [2 + 1 * x_1]))
> )
>   (overlap_iterations_a = [0 + 1 * x_1])
>   (overlap_iterations_b = [2 + 1 * x_1]))
> (analyze_overlapping_iterations
>   (chrec_a = {1, +, 1}_1)
>   (chrec_b = {1, +, 1}_1)
>   (overlap_iterations_a = [0])
>   (overlap_iterations_b = [0]))
> (analyze_overlapping_iterations
>   (chrec_a = {0, +, 1}_5)
>   (chrec_b = {2, +, 1}_5)
> (analyze_siv_subscript
> (analyze_subscript_affine_affine
>   (overlaps_a = [2 + 1 * x_1])
>   (overlaps_b = [0 + 1 * x_1]))
> )
>   (overlap_iterations_a = [2 + 1 * x_1])
>   (overlap_iterations_b = [0 + 1 * x_1]))
> (analyze_overlapping_iterations
>   (chrec_a = {1, +, 1}_1)
>   (chrec_b = {1, +, 1}_1)
>   (overlap_iterations_a = [0])
>   (overlap_iterations_b = [0]))
> (build_classic_dist_vector
>   dist_vector = (  0   0   2
>   )
> )
> )
> 
> I don't see anything wrong with that at a first glance so the bug must be in
> tree_loop_interchange::valid_data_dependences it checks
> 
>           /* Be conservative, skip case if either direction at i_idx/o_idx
>              levels is not '=' or '<'.  */
>           if (dist_vect[i_idx] < 0 || dist_vect[o_idx] < 0)
>             return false;
> 
> dist_vect is [0 0 2], i_idx 2 and o_idx 1 but I think that dist_vect[o_idx]
> should exclude zero, thus
> 
> diff --git a/gcc/gimple-loop-interchange.cc b/gcc/gimple-loop-interchange.cc
> index f45b9364644..265e36c48d4 100644
> --- a/gcc/gimple-loop-interchange.cc
> +++ b/gcc/gimple-loop-interchange.cc
> @@ -1043,8 +1043,8 @@ tree_loop_interchange::valid_data_dependences
> (unsigned i_idx, unsigned o_idx,
>             continue;
>  
>           /* Be conservative, skip case if either direction at i_idx/o_idx
> -            levels is not '=' or '<'.  */
> -         if (dist_vect[i_idx] < 0 || dist_vect[o_idx] < 0)
> +            levels is not '=' (for the inner loop) or '<'.  */
> +         if (dist_vect[i_idx] < 0 || dist_vect[o_idx] <= 0)
>             return false;
>         }
>      }
> 
> Bin - does this analysis look sound?

Hi Richard,
Thanks very much for helping on this.  Sorry I would need a bit more time to
answer this question.  Thanks again.

[Bug tree-optimization/101173] [9/10/11/12 Regression] wrong code at -O3 on x86_64-linux-gnu

[rguenth at gcc dot gnu.org]

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

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
             Status|NEW                         |ASSIGNED

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
No problem, I'll hold on the patch for a bit longer to give you a chance to
look.

[Bug tree-optimization/101173] [9/10/11/12 Regression] wrong code at -O3 on x86_64-linux-gnu

[cvs-commit at gcc dot gnu.org]

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

--- Comment #7 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:0ad9d88a3d7170b3d864693c9eb512f89a5096ff

commit r12-1836-g0ad9d88a3d7170b3d864693c9eb512f89a5096ff
Author: Richard Biener <rguenther@suse.de>
Date:   Wed Jun 23 09:59:28 2021 +0200

    tree-optimization/101173 - fix interchange dependence checking

    This adjusts the loop interchange dependence checking to disallow
    an outer loop dependence distance of zero.

    2021-06-23  Richard Biener  <rguenther@suse.de>

            PR tree-optimization/101173
            * gimple-loop-interchange.cc
            (tree_loop_interchange::valid_data_dependences): Disallow outer
            loop dependence distance of zero.

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

[Bug tree-optimization/101173] [9/10/11 Regression] wrong code at -O3 on x86_64-linux-gnu

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[9/10/11/12 Regression]     |[9/10/11 Regression] wrong
                   |wrong code at -O3 on        |code at -O3 on
                   |x86_64-linux-gnu            |x86_64-linux-gnu
      Known to work|                            |12.0

--- Comment #8 from Richard Biener <rguenth at gcc dot gnu.org> ---
I've now pushed it to trunk - comments are still appreciated.

[Bug tree-optimization/101173] [9/10/11 Regression] wrong code at -O3 on x86_64-linux-gnu

[rguenth at gcc dot gnu.org]

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

--- Comment #9 from Richard Biener <rguenth at gcc dot gnu.org> ---
In the light of PR101280 I am now testing the following alternate fix for the
original problem, avoiding this regression:

diff --git a/gcc/gimple-loop-interchange.cc b/gcc/gimple-loop-interchange.cc
index 43045c5455e..43ef112a2d0 100644
--- a/gcc/gimple-loop-interchange.cc
+++ b/gcc/gimple-loop-interchange.cc
@@ -1043,8 +1043,11 @@ tree_loop_interchange::valid_data_dependences (unsigned
i_idx, unsigned o_idx,
            continue;

          /* Be conservative, skip case if either direction at i_idx/o_idx
-            levels is not '=' (for the inner loop) or '<'.  */
-         if (dist_vect[i_idx] < 0 || dist_vect[o_idx] <= 0)
+            levels is not '=' or '<'.  */
+         if (dist_vect[i_idx] < 0
+             || (DDR_REVERSED_P (ddr) && dist_vect[i_idx] > 0)
+             || dist_vect[o_idx] < 0
+             || (DDR_REVERSED_P (ddr) && dist_vect[o_idx] > 0))
            return false;
        }
     }

[Bug tree-optimization/101173] [9/10/11 Regression] wrong code at -O3 on x86_64-linux-gnu

[cvs-commit at gcc dot gnu.org]

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

--- Comment #10 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:0a77c07b9b3fe83679358c3ef57721e09e2ad5fb

commit r12-1954-g0a77c07b9b3fe83679358c3ef57721e09e2ad5fb
Author: Richard Biener <rguenther@suse.de>
Date:   Thu Jul 1 12:49:45 2021 +0200

    tree-optimization/101280 - revise interchange fix for PR101173

    The following revises the original fix for PR101173 to correctly
    check for a reversed dependence rather than disallowing a zero
    distance.  It also adds a check from TSVC which asks for this
    kind of interchange (but with a valid dependence).

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

            PR tree-optimization/101280
            PR tree-optimization/101173
            * gimple-loop-interchange.cc
            (tree_loop_interchange::valid_data_dependences): Revert
            previous change and instead correctly handle DDR_REVERSED_P
            dependence.

            * gcc.dg/tree-ssa/loop-interchange-16.c: New testcase.

[Bug tree-optimization/101173] [9/10/11 Regression] wrong code at -O3 on x86_64-linux-gnu

[rguenth at gcc dot gnu.org]

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

Bug 101280 Summary: [12 Regression] TSVC s231 slower with -Ofast -march=znver1 since r12-1836-g0ad9d88a3d7170b3
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101280

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

[Bug tree-optimization/101173] [9/10/11 Regression] wrong code at -O3 on x86_64-linux-gnu

[cvs-commit at gcc dot gnu.org]

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

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

commit r12-1973-gc4804ff24401733e3b470a49b8a6c9306e6cfcfa
Author: Richard Biener <rguenther@suse.de>
Date:   Fri Jul 2 08:51:43 2021 +0200

    tree-optimization/101280 - re-revise interchange fix for PR101173

    The following fixes up the revision of the original fix for PR101173
    to properly guard all dependence checks with DDR_REVERSED_P or its
    inverse.

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

            PR tree-optimization/101280
            PR tree-optimization/101173
            * gimple-loop-interchange.cc
            (tree_loop_interchange::valid_data_dependences): Properly
            guard all dependence checks with DDR_REVERSED_P or its
            inverse.

[Bug tree-optimization/101173] [9/10/11 Regression] wrong code at -O3 on x86_64-linux-gnu

[cvs-commit at gcc dot gnu.org]

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

--- Comment #12 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:e46ec6e243c704f0858d16af380a7d9c36fc4244

commit r11-8699-ge46ec6e243c704f0858d16af380a7d9c36fc4244
Author: Richard Biener <rguenther@suse.de>
Date:   Wed Jun 23 09:59:28 2021 +0200

    tree-optimization/101173 - fix interchange dependence checking

    This adjusts the loop interchange dependence checking to properly
    guard all dependence checks with DDR_REVERSED_P or its inverse.

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

            PR tree-optimization/101173
            PR tree-optimization/101280
            * gimple-loop-interchange.cc
            (tree_loop_interchange::valid_data_dependences): Properly
            guard all dependence checks with DDR_REVERSED_P or its
            inverse.

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

[Bug tree-optimization/101173] [9/10 Regression] wrong code at -O3 on x86_64-linux-gnu

[cvs-commit at gcc dot gnu.org]

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

--- Comment #13 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:ac6efdd70779a3be748d11c3b03c08df9ce15dd7

commit r10-10097-gac6efdd70779a3be748d11c3b03c08df9ce15dd7
Author: Richard Biener <rguenther@suse.de>
Date:   Wed Jun 23 09:59:28 2021 +0200

    tree-optimization/101173 - fix interchange dependence checking

    This adjusts the loop interchange dependence checking to properly
    guard all dependence checks with DDR_REVERSED_P or its inverse.

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

            PR tree-optimization/101173
            PR tree-optimization/101280
            * gimple-loop-interchange.cc
            (tree_loop_interchange::valid_data_dependences): Properly
            guard all dependence checks with DDR_REVERSED_P or its
            inverse.

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

    (cherry picked from commit e46ec6e243c704f0858d16af380a7d9c36fc4244)

[Bug tree-optimization/101173] [9 Regression] wrong code at -O3 on x86_64-linux-gnu

[cvs-commit at gcc dot gnu.org]

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

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

commit r9-9772-g5d2771db571323bc7ea25c61b5ed9e5309950f18
Author: Richard Biener <rguenther@suse.de>
Date:   Wed Jun 23 09:59:28 2021 +0200

    tree-optimization/101173 - fix interchange dependence checking

    This adjusts the loop interchange dependence checking to properly
    guard all dependence checks with DDR_REVERSED_P or its inverse.

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

            PR tree-optimization/101173
            PR tree-optimization/101280
            * gimple-loop-interchange.cc
            (tree_loop_interchange::valid_data_dependences): Properly
            guard all dependence checks with DDR_REVERSED_P or its
            inverse.

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

    (cherry picked from commit e46ec6e243c704f0858d16af380a7d9c36fc4244)

[Bug tree-optimization/101173] [9 Regression] wrong code at -O3 on x86_64-linux-gnu

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|---                         |FIXED
             Status|ASSIGNED                    |RESOLVED
      Known to fail|                            |9.4.0

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