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?

Reply via email to