[Bug tree-optimization/69728] [6/7/8 Regression] internal compiler error: in outer_projection_mupa, at graphite-sese-to-poly.c:1175

[rguenth at gcc dot gnu.org]

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

--- Comment #16 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #13)
> A "simple" patch like the following seems to "work".
> 
> Index: gcc/graphite-sese-to-poly.c
> ===================================================================
> --- gcc/graphite-sese-to-poly.c (revision 252920)
> +++ gcc/graphite-sese-to-poly.c (working copy)
> @@ -1043,6 +1043,13 @@ add_loop_schedule (__isl_take isl_schedu
>    if (empty < 0 || empty)
>      return empty < 0 ? isl_schedule_free (schedule) : schedule;
>  
> +  isl_union_set *domain = isl_schedule_get_domain (schedule);
> +  if (isl_union_set_is_empty (domain))
> +    {
> +      isl_union_set_free (domain);
> +      return schedule;
> +    }
> +
>    isl_space *space = isl_set_get_space (iterators);
>    int loop_index = isl_space_dim (space, isl_dim_set) - 1;
>  
> @@ -1063,7 +1070,6 @@ add_loop_schedule (__isl_take isl_schedu
>    prefix = isl_multi_aff_set_tuple_id (prefix, isl_dim_out, label);
>  
>    int n = isl_multi_aff_dim (prefix, isl_dim_in);
> -  isl_union_set *domain = isl_schedule_get_domain (schedule);
>    isl_multi_union_pw_aff *mupa = outer_projection_mupa (domain, n);
>    mupa = isl_multi_union_pw_aff_apply_multi_aff (mupa, prefix);
>    return isl_schedule_insert_partial_schedule (schedule, mupa);
> 
> 
> but it results in a bougs initial schedule:
> 
> [scheduler] original ast:
> {
>   for (int c0 = 0; c0 < -P_21; c0 += 1) {
>     S_9(c0);
>     if (P_21 + c0 <= -2)
>       S_8(c0);
>   }
>   S_10();
> }
> 
> so the conditional loop ended up not being a loop.  I believe in this
> case we are somehow confused by 'c' wrapping?  niter is computed
> as -(unsigned int) (c.7_21 + 1).  Can we really "handle" negating
> an unsigned value?

The real issue is that we probably mishandle the constraint generation for
-(unsigned int) (c.7_21 + 1) (niter of the loop) or that ISL mis-handles
them.  I can't fully decipher the details in the dump but I see

[sese-to-poly] adding constraint to the domain: [P_21] -> { [i1] : i1 <=
2147483637 }
[sese-to-poly] set pbb_9->domain: [P_21] -> { [i1] : -2147483648 <= P_21 <=
2147483647 and 0 <= i1 <= 2147483637 and 4294967296*floor((-1 -
P_21)/4294967296) < -P_21 - i1 }
[sese-to-poly] set pbb_8->domain: [P_21] -> { [i1] : -2147483648 <= P_21 <=
2147483647 and 0 <= i1 <= 2147483637 and 4294967296*floor((-1 -
P_21)/4294967296) < -P_21 - i1 }
[sese-to-poly] adding one extra dimension to the domain for loop_2.
[sese-to-poly] adding constraint to the domain: [P_21] -> { [i1, i2] : i2 >= 0
}
[sese-to-poly] set pbb_6->domain: [P_21] -> { [i1, i2] : -2147483648 <= P_21 <=
2147483647 and 0 <= i1 <= 2147483637 and 0 <= i2 <= 7 and 4294967296*floor((-1
- P_21)/4294967296) < -P_21 - i1 }
[sese-to-poly] set pbb_10->domain: [P_21] -> { [] : -2147483648 <= P_21 <=
2147483647 and 4294967296*floor((-1 - P_21)/4294967296) >= -2147483638 - P_21 }

where I believe the pbb_6 domain is the issue.  The constraint on P_21

4294967296*floor((-1 - P_21)/4294967296) < -P_21 - i1

where I assume P_21 is c.7_12, is supposed to capture th case
where c initially is negative and increasing until it is zero,
the case where it is initially positive would invoke undefined behavior.
But we have 0 <= i1 <= 2147483637, whereever that comes from.  Probably
from the i1 <= 2147483637 constraint?

That said, this testcase is somewhat confusing....

Still, if ISL can get "confused" does it reliably return an empty domain?

That is, aren't we papering over possible wrong-code issues in GRAPHITE
or ISL with handling this as error?  Couldn't it be GCC simply didn't
optimize the code properly and the domain can really be empty in which
case we should not schedule any stmts of the loop?  W/o setting the
error in the patch we end up scheduling the stmt anyway which would
be wrong.  So how'd we properly handle a valid empty domain?  The
initial schedule generation is somewhat of a mess to me...

Anyway, I added

  /* We cannot apply an empty domain to pbbs in this loop so fail.
     ???  Somehow drop pbbs in the loop instead.  */

and committed the patch (we clearly cannot properly handle an empty
domain during initial schedule generation even if the empty domain
is correct).