https://gcc.gnu.org/bugzilla/show_bug.cgi?id=128654
Bug ID: 128654
Summary: Data dependence analysis misses dependences when an
equal subscript varies in two loops
Product: gcc
Version: 17.0
Status: UNCONFIRMED
Keywords: wrong-code
Severity: normal
Priority: P3
Component: tree-optimization
Assignee: unassigned at gcc dot gnu.org
Reporter: konstantinos.eleftheriou at vrull dot eu
Target Milestone: ---
Target: aarch64-linux-gnu
Created attachment 66133
--> https://gcc.gnu.org/bugzilla/attachment.cgi?id=66133&action=edit
testcase
The attached testcase aborts at -O3:
$ gcc -O3 testcase.c && ./a.out
Aborted
It also fails at -O2 -ftree-loop-distribution and passes at
-O3 -fno-tree-loop-distribution. Reproduced on aarch64-linux-gnu with
trunk (2104f1a937eb) and GCC 15.2.1.
In a nest of two loops over i and k, the body stores a[i + k][k + 1] and loads
a[i + k][k]. The load at (i, k) and the store at (i + 1, k - 1) access the
same element, so there is a dependence with distance (1, -1). ldist finds
none and runs all the stores to a before the loads from a:
(compute_affine_dependence
ref_a: a[_1][_2], stmt_a: a[_1][_2] = 1;
ref_b: a[_1][k_18], stmt_b: _3 = a[_1][k_18];
(analyze_overlapping_iterations
(chrec_a = {1, +, 1}_2)
(chrec_b = {0, +, 1}_2)
(analyze_siv_subscript
(analyze_subscript_affine_affine
(overlaps_a = [0 + 1 * x_1])
(overlaps_b = [1 + 1 * x_1]))
)
(overlap_iterations_a = [0 + 1 * x_1])
(overlap_iterations_b = [1 + 1 * x_1]))
(analyze_overlapping_iterations
(chrec_a = {{0, +, 1}<nw>_1, +, 1}_2)
(chrec_b = {{0, +, 1}<nw>_1, +, 1}_2)
(overlap_iterations_a = [0])
(overlap_iterations_b = [0]))
) -> no dependence
Both references have the same row subscript, i + k. For equal chrecs,
analyze_overlapping_iterations returns the conflict [0] for both references,
so the subscript gets a distance of 0, that is the same iteration only. That
is wrong here, because i + k takes the same value in different iterations.
build_classic_dist_vector_1 uses this distance for the loop over k, as if the
subscript only varied with k. The column subscripts, k + 1 and k, give a
distance of -1 for the same loop. The two distances differ, so the subscript
coupling test concludes that there is no dependence.
Without that shortcut, such a subscript would go to analyze_miv_subscript,
which also returns [0] for equal chrecs.
