[Bug tree-optimization/87917] ICE in initialize_matrix_A at gcc/tree-data-ref.c:3150

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
           Assignee|unassigned at gcc dot gnu.org      |rguenth at gcc dot gnu.org

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Sebastian Pop from comment #3)
> > Sebastian - can you say if
> > evolution_function_is_affine_multivariate_p ({0, +, {0, +, 4}_1}_2, 1)
> > should really return true?
> 
> You are right, {0, +, {0, +, 4}_1}_2 is not a valid affine multivariate
> function: only the base (not the step) should vary in an outer loop.
> 
> For example, this would be an affine multivariate: {{0, +, 4}_1, +, 42}_2.

Hmm, but evolution_function_is_affine_multivariate_p currently says:

  switch (TREE_CODE (chrec))
    {
    case POLYNOMIAL_CHREC:
      if (evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec), loopnum))
        {
          if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec),
loopnum))
            return true;

so for {0, +, {0, +, 1}_1 }_2 and asking for loopnum == 2 where loop 2 is
nested inside loop 1 this would already return true because {0, +, 1}_1
is invariant in 2.  Now for the testcase we are asking for loopnum == 1
where the above doesn't hold but we then fall through to

          else
            {
              if (TREE_CODE (CHREC_RIGHT (chrec)) == POLYNOMIAL_CHREC
                  && CHREC_VARIABLE (CHREC_RIGHT (chrec))
                     != CHREC_VARIABLE (chrec)
                  && evolution_function_is_affine_multivariate_p
                  (CHREC_RIGHT (chrec), loopnum))
                return true;

which surely looks bogus (the != should probably be a flow_loop_nested_p
in some way).  A SCEV like {0, +, {0, +, 1}_1 }_1 isn't valid anyways.

If trying to make sense of evolution_function_is_affine_multivariate_p
by looking at evolution_function_is_affine_p and
evolution_function_is_univariate_p I would come up with sth like

    if (evolution_function_is_invariant_p (CHREC_RIGHT (chrec),
                                           CHREC_VARIABLE (chrec))
        && (TREE_CODE (CHREC_RIGHT (chrec)) != POLYNOMIAL_CHREC
            || evolution_function_is_affine_multivariate_p (CHREC_RIGHT
(chrec)))
      return true;
    else
      return false;

That is, why's the evolution of CHREC_LEFT restricted at all here?

That said - this would also make the loopnum argument to
evolution_function_is_affine_multivariate_p moot.  So like the following
together with removing the arg everywhere.  It doesn't fix the ICE
though since we then implicitely ask for loopnum == 2.

Index: tree-chrec.c
===================================================================
--- tree-chrec.c        (revision 266145)
+++ tree-chrec.c        (working copy)
@@ -1063,7 +1063,7 @@ evolution_function_is_invariant_p (tree
    evolution.  */

 bool
-evolution_function_is_affine_multivariate_p (const_tree chrec, int loopnum)
+evolution_function_is_affine_multivariate_p (const_tree chrec)
 {
   if (chrec == NULL_TREE)
     return false;
@@ -1071,33 +1071,11 @@ evolution_function_is_affine_multivariat
   switch (TREE_CODE (chrec))
     {
     case POLYNOMIAL_CHREC:
-      if (evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec), loopnum))
-       {
-         if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec),
loopnum))
-           return true;
-         else
-           {
-             if (TREE_CODE (CHREC_RIGHT (chrec)) == POLYNOMIAL_CHREC
-                 && CHREC_VARIABLE (CHREC_RIGHT (chrec))
-                    != CHREC_VARIABLE (chrec)
-                 && evolution_function_is_affine_multivariate_p
-                 (CHREC_RIGHT (chrec), loopnum))
-               return true;
-             else
-               return false;
-           }
-       }
-      else
-       {
-         if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec),
loopnum)
-             && TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC
-             && CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec)
-             && evolution_function_is_affine_multivariate_p
-             (CHREC_LEFT (chrec), loopnum))
-           return true;
-         else
-           return false;
-       }
+      return (evolution_function_is_invariant_p (CHREC_RIGHT (chrec),
+                                                CHREC_VARIABLE (chrec))
+             && (TREE_CODE (CHREC_RIGHT (chrec)) != POLYNOMIAL_CHREC
+                 || evolution_function_is_affine_multivariate_p
+                       (CHREC_RIGHT (chrec))));

     default:
       return false;


Hmm, maybe what is missing is a check at the top whether the CHREC itself
varies in loopnum?  Anyway, the current code doesn't make much sense to me.

And what dependence analysis does - asking for dependence of two DRs
in loop 2 (the inner one) with respect to evolution in the outer loop
doesn't make much sense?

In any case analyze_subscript_affine_affine doesn't seem to handle
the case of an tree_contains_chrecs (CHREC_RIGHT (..)) because
initialize_matrix_A expects it to be an INTEGER_CST (even!  not just
invariant, but that is checked for).

The other caller of analyze_subscript_affine_affine (analyze_siv_subscript)
seems to use evolution_function_is_affine_in_loop and help themselves
with can_use_analyze_subscript_affine_affine to handle some cases of
chrec_contains_symbols.

So I am now testing the simple

Index: gcc/tree-data-ref.c
===================================================================
--- gcc/tree-data-ref.c (revision 266145)
+++ gcc/tree-data-ref.c (working copy)
@@ -3994,9 +3993,9 @@ analyze_miv_subscript (tree chrec_a,
       dependence_stats.num_miv_independent++;
     }

-  else if (evolution_function_is_affine_multivariate_p (chrec_a,
loop_nest->num)
+  else if (evolution_function_is_affine_in_loop (chrec_a, loop_nest->num)
           && !chrec_contains_symbols (chrec_a)
-          && evolution_function_is_affine_multivariate_p (chrec_b,
loop_nest->num)
+          && evolution_function_is_affine_in_loop (chrec_b, loop_nest->num)
           && !chrec_contains_symbols (chrec_b))
     {
       /* testsuite/.../ssa-chrec-35.c


but still somehow is_affine_multivariate returns true for something
that is_affine_in_loop does not ... (so the predicates look inconsistent).

Any help appreciated.