Confirmed on x86_64.

For two more testcases: PR68756 comment 3

GCC 6.1 has been released.

GCC 6.2 is being released, adjusting target milestone.

GCC 6.2 is being released, adjusting target milestone.

GCC 6.3 is being released, adjusting target milestone.

Reconfirmed on trunk.

removing the assert doesn't fix it (ISL complains).  This is all ISL stuff I don't understand, somebody else needs to look at this - the SCOP is quite regular.
Confirmed with ISL 0.18.

GCC 6.4 is being released, adjusting target milestone.

*** Bug 80069 has been marked as a duplicate of this bug. ***

*** Bug 81226 has been marked as a duplicate of this bug. ***

*** Bug 82057 has been marked as a duplicate of this bug. ***

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?

static isl_pw_aff *
extract_affine (scop_p s, tree e, __isl_take isl_space *space)
{
..
    case NEGATE_EXPR:
    case BIT_NOT_EXPR:
      lhs = extract_affine (s, TREE_OPERAND (e, 0), isl_space_copy (space));
      rhs = extract_affine (s, integer_minus_one_node, space);
      res = isl_pw_aff_mul (lhs, rhs);
      break;

so we do x * -1 for negate -- that looks ok.  At least bogus for
BIT_NOT_EXPR which is really -1 - x, not x * -1.

Doesn't seem to handle any conversion to signed correctly either as it
misses an appropriate 'wrap' operation (the existing one only works
for unsigned).  The offset argument in POINTER_PLUS_EXPR handling needs
to be interpreted as signed.

So for the ICE I now have the hackish

Index: gcc/graphite-sese-to-poly.c
===================================================================
--- gcc/graphite-sese-to-poly.c (revision 252920)
+++ gcc/graphite-sese-to-poly.c (working copy)
@@ -1030,6 +1035,8 @@ outer_projection_mupa (__isl_take isl_un
   return isl_multi_union_pw_aff_from_union_pw_multi_aff (data.res);
 }
 
+static bool schedule_error;
+
 /* Embed SCHEDULE in the constraints of the LOOP domain.  */
 
 static isl_schedule *
@@ -1043,6 +1050,14 @@ 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))
+    {
+      schedule_error = true;
+      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;
 
@@ -1169,6 +1183,8 @@ build_schedule_loop_nest (scop_p scop, i
 static bool
 build_original_schedule (scop_p scop)
 {
+  schedule_error = false;
+
   int i = 0;
   int n = scop->pbbs.length ();
   while (i < n)
@@ -1183,6 +1199,14 @@ build_original_schedule (scop_p scop)
       scop->original_schedule = add_in_sequence (scop->original_schedule, s);
     }
 
+  if (schedule_error)
+    {
+      if (dump_file)
+       fprintf (dump_file, "[sese-to-poly] failed to build "
+                "original schedule\n");
+      return false;
+    }
+
   if (dump_file)
     {
       fprintf (dump_file, "[sese-to-poly] original schedule:\n");

*** Bug 80105 has been marked as a duplicate of this bug. ***

It makes sense to early fail when the schedule builder gets confused and built an empty domain.  Could you please also add a comment around the if that sets schedule_error?  The change looks good.  Thanks.

(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).

Fixed.

Author: rguenth
Date: Tue Sep 19 08:25:17 2017
New Revision: 252968

URL: https://gcc.gnu.org/viewcvs?rev=252968&root=gcc&view=rev
Log:
2017-09-19  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/69728
	* graphite-sese-to-poly.c (schedule_error): New global.
	(add_loop_schedule): Handle empty domain by failing the
	schedule.
	(build_original_schedule): Handle schedule_error.

	* gfortran.dg/graphite/pr69728.f90: New testcase.
	* gcc.dg/graphite/pr69728.c: Likewise.

Added:
    trunk/gcc/testsuite/gcc.dg/graphite/pr69728.c
    trunk/gcc/testsuite/gfortran.dg/graphite/pr69728.f90
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/graphite-sese-to-poly.c
    trunk/gcc/testsuite/ChangeLog

> So how'd we properly handle a valid empty domain?

DCE the statement.

If the domain for a statement is empty, it means that the statement does not execute: it is dead code.

I think we are better enforcing the elimination of the statement as this wrong analysis (or translation) of the number of iterations could produce wrong code.

> I assume P_21 is c.7_12

the number after P_ is the ssa variable number, so P_21 is c.7_21.

> we have 0 <= i1 <= 2147483637, whereever that comes from.

you can think about i1 as a canonical induction variable: 0 <= i1
and i1 is indexing all iterations in that loop: i.e., i1 is incremented by 1.

> Probably from the i1 <= 2147483637 constraint

this constraint is added based on the type of the induction variable that gives an upper bound for the iteration domain.

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

Yes, this constraint seems to be wrong.

On Tue, 19 Sep 2017, spop at gcc dot gnu.org wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=69728
> 
> --- Comment #19 from Sebastian Pop <spop at gcc dot gnu.org> ---
> > So how'd we properly handle a valid empty domain?
> 
> DCE the statement.
> 
> If the domain for a statement is empty, it means that the statement does not
> execute: it is dead code.
> 
> I think we are better enforcing the elimination of the statement as this wrong
> analysis (or translation) of the number of iterations could produce wrong code.

That was my thinking, I put it on my TODO to figure out how to "DCE"
a stmt (or in this case it's rather the whole "loop body", right?).
I've not fully found my way through initial schedule building yet
(otherwise I would have tried refactoring to not operate in pbb
vector order but more naturally follow the SESE in a CFG walk with
maintaining a BB -> pbb mapping).

> > I assume P_21 is c.7_12
> 
> the number after P_ is the ssa variable number, so P_21 is c.7_21.
> 
> > we have 0 <= i1 <= 2147483637, whereever that comes from.
> 
> you can think about i1 as a canonical induction variable: 0 <= i1
> and i1 is indexing all iterations in that loop: i.e., i1 is incremented by 1.
> 
> > Probably from the i1 <= 2147483637 constraint
> 
> this constraint is added based on the type of the induction variable that gives
> an upper bound for the iteration domain.
> 
> > 4294967296*floor((-1 - P_21)/4294967296) < -P_21 - i1
> 
> Yes, this constraint seems to be wrong.

It indeed looks like so though I wasn't able to nail down what goes wrong.
Unfortunately the extract_affine fixes didn't affect this one in a 
positive way.

Oh, fixed on trunk only.

> I put it on my TODO to figure out how to "DCE" a stmt
> (or in this case it's rather the whole "loop body", right?).

The code generator would not even see a statement to be generated: it would just disappear in the new code, so there is nothing to do to DCE statements with empty domains.

> I've not fully found my way through initial schedule building yet
> (otherwise I would have tried refactoring to not operate in pbb
> vector order but more naturally follow the SESE in a CFG walk with
> maintaining a BB -> pbb mapping).

Yes, DOM-walk could be used to detect the sequential order in which basic blocks are executed.

There are some difficulties in giving an execution sequence number for if-then and if-else clauses, and for switch cases: for the moment we represent them as executing in sequence.  For example,

if (c)
  a;
else
  b;

we would number the stmts a and b as if the code looked like this:

if (c)
  a;
if (!c)
  b;

which is correct.
The fact that the constraint "c" is added to the iteration domain of "a", and "!c" added to the iter domain of "b" allows the scheduler to know that there are no sequential dependences between stmts "a" and "b" as they are executed in different iterations.

Author: rguenth
Date: Thu Oct 12 14:09:21 2017
New Revision: 253677

URL: https://gcc.gnu.org/viewcvs?rev=253677&root=gcc&view=rev
Log:
2017-10-12  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/69728
	Revert
	2017-09-19  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/69728
	* graphite-sese-to-poly.c (schedule_error): New global.
	(add_loop_schedule): Handle empty domain by failing the
	schedule.
	(build_original_schedule): Handle schedule_error.

	* graphite-sese-to-poly.c (add_loop_schedule): Handle empty
	domain by returning an unchanged schedule.

	* gcc.dg/graphite/pr69728.c: Adjust to reflect we can handle
	the loop now.  Remove unrelated undefined behavior.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/graphite-sese-to-poly.c
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/testsuite/gcc.dg/graphite/pr69728.c

GCC 6 branch is being closed

Fixed in GCC 8.

This this PR be closed now?

(In reply to Arseny Solokha from comment #26)
> This this PR be closed now?

Yeah I think that's what Richard meant to do