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

--- Comment #2 from Jinhong Wang <wangjinhong at hygon dot cn> ---
I independently reproduced the same missing write self-dependence
reported in PR128648. I am adding a fixed-bound reproducer, a required
positive control for bounded-domain interchange, and a draft candidate
fix for discussion. The draft is based on GCC 12.3 and has not yet been
adapted to or tested as a fix on upstream trunk.

The following testcase prints D[4] = 10 instead of the expected 400 when
compiled with -O3, or with -O2 -floop-interchange. Disabling loop
interchange restores the expected result.

#include <stdio.h>

int main (void)
{
  int D[636] = {0};
  for (int i = 0; i < 128; ++i)
    for (int j = 0; j < 128; ++j)
      D[i + 4*j] = 100*i + 10*j;

  printf ("D[4] = %d (expected 400)\n", D[4]);
  return D[4] != 400;
}

Reproduction commands (gcc denotes the tested installation):

  gcc -O3 -Wall -Wextra -save-temps -fdump-tree-linterchange-details
self-store.c -o repro
  ./repro

Actual output:
  D[4] = 10 (expected 400)
Exit status: 1

Expected output:
  D[4] = 400 (expected 400)
Exit status: 0

Option comparison, with the same compiler and input:
  -O0                       D[4] = 400; exit 0
  -O2 -floop-interchange     D[4] = 10;  exit 1
  -O3                       D[4] = 10;  exit 1
  -O3 -fno-loop-interchange  D[4] = 400; exit 0

All four compilations completed without warnings using -Wall -Wextra.
The attached self-store.i also reproduces with gcc -O3 self-store.i.
The linterchange dump contains:
  Loop_pair<outer:1, inner:2> is interchanged

Correctness argument:
The maximum array index is 127 + 4*127 = 635, within D[636], and the
maximum stored value is 13970. Iteration (i,j) = (0,1) writes 10 to D[4],
then (4,0) writes 400 in the original order. Interchanging the loops
reverses these writes. The dependence distance (4,-1), defined as the
later iteration minus the earlier one in the original execution order,
becomes (-1,4) after interchange.

Analysis:
In the inspected loop-interchange implementation, the data-reference
pair enumeration starts at j = i + 1. A loop containing only this one
static store therefore does not get a write-reference self-dependence
checked by this enumeration. The observed dump creates a single data
reference and then interchanges the loop pair.

A draft candidate fix is attached for discussion. It was developed and
tested on a GCC 12.3-based source tree; it is not yet an upstream
trunk patch. See draft-patch-notes.txt for its exact base and validation
scope. The separate upstream reproduction above establishes the bug;
it does not establish that the attached patch has been validated on
upstream trunk.

Required positive control: preserve the legal bounded-domain interchange

The fix should retain the interchange of the following kernel when it
is profitable under the same options used for the regression tests:

  int D[128 * 128];
  for (int i = 0; i < 128; ++i)
    for (int j = 0; j < 128; ++j)
      D[i + 128*j] = 100*i + 10*j;

This is a positive control, not an additional wrong-code reproducer.
The attached bounded-safe-128.c is a complete runnable testcase. It
checks all output elements and untouched guard elements against a
reference loop compiled with loop interchange disabled. The code above
shows the relevant access pattern; the attachment retains the full
runtime oracle and testsuite directives.

For two accesses to collide, their iteration differences must satisfy
  delta_i + 128 * delta_j = 0.
Since abs(delta_i) <= 127, the only feasible solution is delta_i = 0 and
delta_j = 0. Thus distinct iterations cannot access the same element.
A nonzero algebraic self-dependence such as (128,-1) lies outside this
iteration domain and must not cause an otherwise profitable interchange
to be rejected. Simply enabling self-dependence checks without accounting
for the loop bounds can therefore introduce an optimization regression.

Acceptance requires BOTH correct runtime output and actual interchange
of kernel in the linterchange dump at -O2 -floop-interchange and -O3.
A successful runtime result alone is insufficient, because keeping the
original loop order would also produce the correct values. The relevant
dump check is scoped to kernel so that another loop cannot satisfy it.

The paired bounded-conflict-129.c increases only the outer trip count to
129, with enough array storage for the maximum index 16384. Iterations
(0,1) and (128,0) now collide at element 128: the original final value is
12800, while an interchange would leave 10. This case must run correctly
and must NOT interchange kernel.

The current draft patch already includes these two regression tests as
loop-interchange-19.c (128 iterations, interchange required) and
loop-interchange-20.c (129 iterations, interchange forbidden). The
standalone attachments are byte-identical copies of those tests.

Example validation commands:
  gcc -O2 -floop-interchange -fdump-tree-linterchange-details
bounded-safe-128.c -o safe
  ./safe
  gcc -O3 -fdump-tree-linterchange-details bounded-safe-128.c -o safe-o3
  ./safe-o3

Both programs must exit with status 0. Inspect the dump for an actual
Loop_pair<outer:..., inner:...> is interchanged entry in function kernel.
Repeat with bounded-conflict-129.c: exit status 0, no interchange in kernel.


Validation of the attached boundary controls with the patched GCC 12.3-based
checking bootstrap compiler:
  bounded-safe-128.c:     O2 PASS, one kernel interchange;
                         O3 PASS, one kernel interchange.
  bounded-conflict-129.c: O2 PASS, no kernel interchange;
                         O3 PASS, no kernel interchange.
All four programs exited with status 0, all compilations were warning-free,
and the input and compiler fingerprints remained unchanged during testing.
These results validate the draft on its GCC 12.3 base; they are not results
of applying the patch to GCC 17 trunk.

The regression range is documented in the original report. This comment
adds an independently tested reproducer, bounded-domain controls, and a
GCC 12.3-based draft candidate fix; it does not add an independent bisect.

Full compiler configuration and version:

Using built-in specs.
COLLECT_GCC=/home/wangjinhong/gcc-public/trunk-public-project-install-release/bin/gcc
COLLECT_LTO_WRAPPER=/home/wangjinhong/gcc-public/trunk-public-project-install-release/bin/../libexec/gcc/x86_64-linux-gnu/17.0.0/lto-wrapper
Target: x86_64-linux-gnu
Configured with:
/home/wangjinhong/gcc-public/gcc-public-project/build-script/../../gcc-public-project/gcc-project/configure
--prefix=/home/wangjinhong/gcc-public/gcc-public-project/build-script/../../trunk-public-project-install-release
--enable-shared --enable-threads=posix --enable-checking=release
--enable-__cxa_atexit --enable-gnu-unique-object --enable-linker-build-id
--with-linker-hash-style=gnu --enable-languages=c,c++,fortran,lto
--enable-initfini-array --enable-gnu-indirect-function --enable-default-pie
--with-gnu-as --with-gnu-ld --enable-libquadmath --with-pkgversion='gcc
public:trunk Build:20261106' --disable-bootstrap --build=x86_64-linux-gnu
--host=x86_64-linux-gnu --target=x86_64-linux-gnu
Thread model: posix
Supported LTO compression algorithms: zlib zstd
gcc version 17.0.0 20261106 (experimental) (gcc public:trunk Build:20261106)

Reply via email to