Fix PR48648: Handle CLAST assignments.

The CLAST produced by CLooG-ISL contains an assignment and GCC chokes
on it.  The exact CLAST contains an assignment followed by an if:

scat_1 = max(0,ceild(T_4-7,8));
if (scat_1 <= min(1,floord(T_4-1,8))) {
  S7(scat_1);
}

This is equivalent to a loop that iterates only once, and so CLooG
generates an assignment followed by an if instead of a loop.  This is
an important optimization that was improved in ISL, that allows
if-conversion: imagine GCC having to figure out that a loop like the
following actually iterates only once, and can be converted to an if:

for (scat_1 = max(0,ceild(T_4-7,8)); scat_1 <= min(1,floord(T_4-1,8)); scat_1++)
  S7(scat_1);

This patch implements the translation of CLAST assignments.
Bootstrapped and tested on amd64-linux.

Sebastian

2011-07-22  Sebastian Pop  <sebastian.pop@amd.com>

	PR middle-end/48648
	* graphite-clast-to-gimple.c (clast_get_body_of_loop): Handle
	CLAST assignments.
	(translate_clast): Same.
	(translate_clast_assignment): New.

	* gcc.dg/graphite/id-pr48648.c: New.
---
 gcc/ChangeLog                              |    8 ++++
 gcc/graphite-clast-to-gimple.c             |   49 ++++++++++++++++++++++++++++
 gcc/testsuite/ChangeLog                    |    5 +++
 gcc/testsuite/gcc.dg/graphite/id-pr48648.c |   21 ++++++++++++
 4 files changed, 83 insertions(+), 0 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/graphite/id-pr48648.c

On Sat, Jul 23, 2011 at 1:01 AM, Sebastian Pop <sebpop@gmail.com> wrote:
> The CLAST produced by CLooG-ISL contains an assignment and GCC chokes
> on it.  The exact CLAST contains an assignment followed by an if:
>
> scat_1 = max(0,ceild(T_4-7,8));
> if (scat_1 <= min(1,floord(T_4-1,8))) {
>  S7(scat_1);
> }
>
> This is equivalent to a loop that iterates only once, and so CLooG
> generates an assignment followed by an if instead of a loop.  This is
> an important optimization that was improved in ISL, that allows
> if-conversion: imagine GCC having to figure out that a loop like the
> following actually iterates only once, and can be converted to an if:
>
> for (scat_1 = max(0,ceild(T_4-7,8)); scat_1 <= min(1,floord(T_4-1,8)); scat_1++)
>  S7(scat_1);
>
> This patch implements the translation of CLAST assignments.
> Bootstrapped and tested on amd64-linux.

Ok if Tobias is fine with it.

Thanks,
Richard.

> Sebastian
>
> 2011-07-22  Sebastian Pop  <sebastian.pop@amd.com>
>
>        PR middle-end/48648
>        * graphite-clast-to-gimple.c (clast_get_body_of_loop): Handle
>        CLAST assignments.
>        (translate_clast): Same.
>        (translate_clast_assignment): New.
>
>        * gcc.dg/graphite/id-pr48648.c: New.
> ---
>  gcc/ChangeLog                              |    8 ++++
>  gcc/graphite-clast-to-gimple.c             |   49 ++++++++++++++++++++++++++++
>  gcc/testsuite/ChangeLog                    |    5 +++
>  gcc/testsuite/gcc.dg/graphite/id-pr48648.c |   21 ++++++++++++
>  4 files changed, 83 insertions(+), 0 deletions(-)
>  create mode 100644 gcc/testsuite/gcc.dg/graphite/id-pr48648.c
>
> diff --git a/gcc/ChangeLog b/gcc/ChangeLog
> index 9cfa21b..303c9c9 100644
> --- a/gcc/ChangeLog
> +++ b/gcc/ChangeLog
> @@ -1,3 +1,11 @@
> +2011-07-22  Sebastian Pop  <sebastian.pop@amd.com>
> +
> +       PR middle-end/48648
> +       * graphite-clast-to-gimple.c (clast_get_body_of_loop): Handle
> +       CLAST assignments.
> +       (translate_clast): Same.
> +       (translate_clast_assignment): New.
> +
>  2011-07-21  Sebastian Pop  <sebastian.pop@amd.com>
>
>        PR middle-end/47654
> diff --git a/gcc/graphite-clast-to-gimple.c b/gcc/graphite-clast-to-gimple.c
> index ddf6d3d..a4668d3 100644
> --- a/gcc/graphite-clast-to-gimple.c
> +++ b/gcc/graphite-clast-to-gimple.c
> @@ -812,6 +812,9 @@ clast_get_body_of_loop (struct clast_stmt *stmt)
>   if (CLAST_STMT_IS_A (stmt, stmt_block))
>     return clast_get_body_of_loop (((struct clast_block *) stmt)->body);
>
> +  if (CLAST_STMT_IS_A (stmt, stmt_ass))
> +    return clast_get_body_of_loop (stmt->next);
> +
>   gcc_unreachable ();
>  }
>
> @@ -1121,6 +1124,48 @@ translate_clast_for (loop_p context_loop, struct clast_for *stmt, edge next_e,
>   return last_e;
>  }
>
> +/* Translates a clast assignment STMT to gimple.
> +
> +   - NEXT_E is the edge where new generated code should be attached.
> +   - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.  */
> +
> +static edge
> +translate_clast_assignment (struct clast_assignment *stmt, edge next_e,
> +                           int level, ivs_params_p ip)
> +{
> +  gimple_seq stmts;
> +  mpz_t v1, v2;
> +  tree type, new_name, var;
> +  edge res = single_succ_edge (split_edge (next_e));
> +  struct clast_expr *expr = (struct clast_expr *) stmt->RHS;
> +  struct clast_user_stmt *body
> +    = clast_get_body_of_loop ((struct clast_stmt *) stmt);
> +  poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (body->statement);
> +
> +  mpz_init (v1);
> +  mpz_init (v2);
> +  type = type_for_clast_expr (expr, ip, v1, v2);
> +  var = create_tmp_var (type, "graphite_var");
> +  new_name = force_gimple_operand (clast_to_gcc_expression (type, expr, ip),
> +                                  &stmts, true, var);
> +  add_referenced_var (var);
> +  if (stmts)
> +    {
> +      gsi_insert_seq_on_edge (next_e, stmts);
> +      gsi_commit_edge_inserts ();
> +    }
> +
> +  compute_bounds_for_level (pbb, level, v1, v2);
> +  save_clast_name_index (ip->newivs_index, stmt->LHS,
> +                        VEC_length (tree, *(ip->newivs)), level, v1, v2);
> +  VEC_safe_push (tree, heap, *(ip->newivs), new_name);
> +
> +  mpz_clear (v1);
> +  mpz_clear (v2);
> +
> +  return res;
> +}
> +
>  /* Translates a clast guard statement STMT to gimple.
>
>    - NEXT_E is the edge where new generated code should be attached.
> @@ -1171,6 +1216,10 @@ translate_clast (loop_p context_loop, struct clast_stmt *stmt, edge next_e,
>   else if (CLAST_STMT_IS_A (stmt, stmt_block))
>     next_e = translate_clast (context_loop, ((struct clast_block *) stmt)->body,
>                              next_e, bb_pbb_mapping, level, ip);
> +
> +  else if (CLAST_STMT_IS_A (stmt, stmt_ass))
> +    next_e = translate_clast_assignment ((struct clast_assignment *) stmt,
> +                                        next_e, level, ip);
>   else
>     gcc_unreachable();
>
> diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
> index a63b647..bfdbcfb 100644
> --- a/gcc/testsuite/ChangeLog
> +++ b/gcc/testsuite/ChangeLog
> @@ -1,3 +1,8 @@
> +2011-07-22  Sebastian Pop  <sebastian.pop@amd.com>
> +
> +       PR middle-end/48648
> +       * gcc.dg/graphite/id-pr48648.c: New.
> +
>  2011-07-21  Sebastian Pop  <sebastian.pop@amd.com>
>
>        PR middle-end/47654
> diff --git a/gcc/testsuite/gcc.dg/graphite/id-pr48648.c b/gcc/testsuite/gcc.dg/graphite/id-pr48648.c
> new file mode 100644
> index 0000000..ff58ec2
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/graphite/id-pr48648.c
> @@ -0,0 +1,21 @@
> +/* { dg-options "-O -fgraphite-identity" } */
> +
> +void *foo(const void *a);
> +
> +void bug48648()
> +{
> +  unsigned char a[2];
> +  long b;
> +  int i;
> +
> +  for(i = 0; i < 2; i++) {
> +    if (b <= 0)
> +      a[i] = 0;
> +    else if (b >= 8)
> +      a[i] = 0;
> +    else
> +      a[i] = 0;
> +    b -= 8;
> +  }
> +  foo(&a);
> +}
> --
> 1.7.4.1
>
>

On Sat, Jul 23, 2011 at 04:59, Richard Guenther
<richard.guenther@gmail.com> wrote:
> On Sat, Jul 23, 2011 at 1:01 AM, Sebastian Pop <sebpop@gmail.com> wrote:
>> The CLAST produced by CLooG-ISL contains an assignment and GCC chokes
>> on it.  The exact CLAST contains an assignment followed by an if:
>>
>> scat_1 = max(0,ceild(T_4-7,8));
>> if (scat_1 <= min(1,floord(T_4-1,8))) {
>>  S7(scat_1);
>> }
>>
>> This is equivalent to a loop that iterates only once, and so CLooG
>> generates an assignment followed by an if instead of a loop.  This is
>> an important optimization that was improved in ISL, that allows
>> if-conversion: imagine GCC having to figure out that a loop like the
>> following actually iterates only once, and can be converted to an if:
>>
>> for (scat_1 = max(0,ceild(T_4-7,8)); scat_1 <= min(1,floord(T_4-1,8)); scat_1++)
>>  S7(scat_1);
>>
>> This patch implements the translation of CLAST assignments.
>> Bootstrapped and tested on amd64-linux.
>
> Ok if Tobias is fine with it.

Tobias, could you please have a look at this patch?

Thanks,
Sebastian

>
> Thanks,
> Richard.
>
>> Sebastian
>>
>> 2011-07-22  Sebastian Pop  <sebastian.pop@amd.com>
>>
>>        PR middle-end/48648
>>        * graphite-clast-to-gimple.c (clast_get_body_of_loop): Handle
>>        CLAST assignments.
>>        (translate_clast): Same.
>>        (translate_clast_assignment): New.
>>
>>        * gcc.dg/graphite/id-pr48648.c: New.
>> ---
>>  gcc/ChangeLog                              |    8 ++++
>>  gcc/graphite-clast-to-gimple.c             |   49 ++++++++++++++++++++++++++++
>>  gcc/testsuite/ChangeLog                    |    5 +++
>>  gcc/testsuite/gcc.dg/graphite/id-pr48648.c |   21 ++++++++++++
>>  4 files changed, 83 insertions(+), 0 deletions(-)
>>  create mode 100644 gcc/testsuite/gcc.dg/graphite/id-pr48648.c
>>
>> diff --git a/gcc/ChangeLog b/gcc/ChangeLog
>> index 9cfa21b..303c9c9 100644
>> --- a/gcc/ChangeLog
>> +++ b/gcc/ChangeLog
>> @@ -1,3 +1,11 @@
>> +2011-07-22  Sebastian Pop  <sebastian.pop@amd.com>
>> +
>> +       PR middle-end/48648
>> +       * graphite-clast-to-gimple.c (clast_get_body_of_loop): Handle
>> +       CLAST assignments.
>> +       (translate_clast): Same.
>> +       (translate_clast_assignment): New.
>> +
>>  2011-07-21  Sebastian Pop  <sebastian.pop@amd.com>
>>
>>        PR middle-end/47654
>> diff --git a/gcc/graphite-clast-to-gimple.c b/gcc/graphite-clast-to-gimple.c
>> index ddf6d3d..a4668d3 100644
>> --- a/gcc/graphite-clast-to-gimple.c
>> +++ b/gcc/graphite-clast-to-gimple.c
>> @@ -812,6 +812,9 @@ clast_get_body_of_loop (struct clast_stmt *stmt)
>>   if (CLAST_STMT_IS_A (stmt, stmt_block))
>>     return clast_get_body_of_loop (((struct clast_block *) stmt)->body);
>>
>> +  if (CLAST_STMT_IS_A (stmt, stmt_ass))
>> +    return clast_get_body_of_loop (stmt->next);
>> +
>>   gcc_unreachable ();
>>  }
>>
>> @@ -1121,6 +1124,48 @@ translate_clast_for (loop_p context_loop, struct clast_for *stmt, edge next_e,
>>   return last_e;
>>  }
>>
>> +/* Translates a clast assignment STMT to gimple.
>> +
>> +   - NEXT_E is the edge where new generated code should be attached.
>> +   - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.  */
>> +
>> +static edge
>> +translate_clast_assignment (struct clast_assignment *stmt, edge next_e,
>> +                           int level, ivs_params_p ip)
>> +{
>> +  gimple_seq stmts;
>> +  mpz_t v1, v2;
>> +  tree type, new_name, var;
>> +  edge res = single_succ_edge (split_edge (next_e));
>> +  struct clast_expr *expr = (struct clast_expr *) stmt->RHS;
>> +  struct clast_user_stmt *body
>> +    = clast_get_body_of_loop ((struct clast_stmt *) stmt);
>> +  poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (body->statement);
>> +
>> +  mpz_init (v1);
>> +  mpz_init (v2);
>> +  type = type_for_clast_expr (expr, ip, v1, v2);
>> +  var = create_tmp_var (type, "graphite_var");
>> +  new_name = force_gimple_operand (clast_to_gcc_expression (type, expr, ip),
>> +                                  &stmts, true, var);
>> +  add_referenced_var (var);
>> +  if (stmts)
>> +    {
>> +      gsi_insert_seq_on_edge (next_e, stmts);
>> +      gsi_commit_edge_inserts ();
>> +    }
>> +
>> +  compute_bounds_for_level (pbb, level, v1, v2);
>> +  save_clast_name_index (ip->newivs_index, stmt->LHS,
>> +                        VEC_length (tree, *(ip->newivs)), level, v1, v2);
>> +  VEC_safe_push (tree, heap, *(ip->newivs), new_name);
>> +
>> +  mpz_clear (v1);
>> +  mpz_clear (v2);
>> +
>> +  return res;
>> +}
>> +
>>  /* Translates a clast guard statement STMT to gimple.
>>
>>    - NEXT_E is the edge where new generated code should be attached.
>> @@ -1171,6 +1216,10 @@ translate_clast (loop_p context_loop, struct clast_stmt *stmt, edge next_e,
>>   else if (CLAST_STMT_IS_A (stmt, stmt_block))
>>     next_e = translate_clast (context_loop, ((struct clast_block *) stmt)->body,
>>                              next_e, bb_pbb_mapping, level, ip);
>> +
>> +  else if (CLAST_STMT_IS_A (stmt, stmt_ass))
>> +    next_e = translate_clast_assignment ((struct clast_assignment *) stmt,
>> +                                        next_e, level, ip);
>>   else
>>     gcc_unreachable();
>>
>> diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
>> index a63b647..bfdbcfb 100644
>> --- a/gcc/testsuite/ChangeLog
>> +++ b/gcc/testsuite/ChangeLog
>> @@ -1,3 +1,8 @@
>> +2011-07-22  Sebastian Pop  <sebastian.pop@amd.com>
>> +
>> +       PR middle-end/48648
>> +       * gcc.dg/graphite/id-pr48648.c: New.
>> +
>>  2011-07-21  Sebastian Pop  <sebastian.pop@amd.com>
>>
>>        PR middle-end/47654
>> diff --git a/gcc/testsuite/gcc.dg/graphite/id-pr48648.c b/gcc/testsuite/gcc.dg/graphite/id-pr48648.c
>> new file mode 100644
>> index 0000000..ff58ec2
>> --- /dev/null
>> +++ b/gcc/testsuite/gcc.dg/graphite/id-pr48648.c
>> @@ -0,0 +1,21 @@
>> +/* { dg-options "-O -fgraphite-identity" } */
>> +
>> +void *foo(const void *a);
>> +
>> +void bug48648()
>> +{
>> +  unsigned char a[2];
>> +  long b;
>> +  int i;
>> +
>> +  for(i = 0; i < 2; i++) {
>> +    if (b <= 0)
>> +      a[i] = 0;
>> +    else if (b >= 8)
>> +      a[i] = 0;
>> +    else
>> +      a[i] = 0;
>> +    b -= 8;
>> +  }
>> +  foo(&a);
>> +}
>> --
>> 1.7.4.1
>>
>>
>

On 07/23/2011 12:01 AM, Sebastian Pop wrote:
> The CLAST produced by CLooG-ISL contains an assignment and GCC chokes
> on it.  The exact CLAST contains an assignment followed by an if:
>
> scat_1 = max(0,ceild(T_4-7,8));
> if (scat_1<= min(1,floord(T_4-1,8))) {
>    S7(scat_1);
> }
>
> This is equivalent to a loop that iterates only once, and so CLooG
> generates an assignment followed by an if instead of a loop.  This is
> an important optimization that was improved in ISL, that allows
> if-conversion: imagine GCC having to figure out that a loop like the
> following actually iterates only once, and can be converted to an if:
>
> for (scat_1 = max(0,ceild(T_4-7,8)); scat_1<= min(1,floord(T_4-1,8)); scat_1++)
>    S7(scat_1);
>
> This patch implements the translation of CLAST assignments.
> Bootstrapped and tested on amd64-linux.

Hi Sebastian,

thanks for adding this to graphite. One comment inline.

>
> Sebastian
>
> 2011-07-22  Sebastian Pop<sebastian.pop@amd.com>
>
> 	PR middle-end/48648
> 	* graphite-clast-to-gimple.c (clast_get_body_of_loop): Handle
> 	CLAST assignments.
> 	(translate_clast): Same.
> 	(translate_clast_assignment): New.
>
> 	* gcc.dg/graphite/id-pr48648.c: New.
> ---
>   gcc/ChangeLog                              |    8 ++++
>   gcc/graphite-clast-to-gimple.c             |   49 ++++++++++++++++++++++++++++
>   gcc/testsuite/ChangeLog                    |    5 +++
>   gcc/testsuite/gcc.dg/graphite/id-pr48648.c |   21 ++++++++++++
>   4 files changed, 83 insertions(+), 0 deletions(-)
>   create mode 100644 gcc/testsuite/gcc.dg/graphite/id-pr48648.c
>
> diff --git a/gcc/ChangeLog b/gcc/ChangeLog
> index 9cfa21b..303c9c9 100644
> +/* Translates a clast assignment STMT to gimple.
> +
> +   - NEXT_E is the edge where new generated code should be attached.
> +   - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.  */
> +
> +static edge
> +translate_clast_assignment (struct clast_assignment *stmt, edge next_e,
> +			    int level, ivs_params_p ip)
> +{
> +  gimple_seq stmts;
> +  mpz_t v1, v2;
> +  tree type, new_name, var;
> +  edge res = single_succ_edge (split_edge (next_e));
> +  struct clast_expr *expr = (struct clast_expr *) stmt->RHS;
> +  struct clast_user_stmt *body
> +    = clast_get_body_of_loop ((struct clast_stmt *) stmt);

I am not a big fan of using clast_get_body_of_loop as it is buggy. 
Introducing new uses of it, is nothing what I would support. Do we 
really need this?

> +  poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (body->statement);
> +
> +  mpz_init (v1);
> +  mpz_init (v2);

What about some more meaningful names like bound_one, bound_two?

> +  type = type_for_clast_expr (expr, ip, v1, v2);
> +  var = create_tmp_var (type, "graphite_var");
> +  new_name = force_gimple_operand (clast_to_gcc_expression (type, expr, ip),
> +				&stmts, true, var);
> +  add_referenced_var (var);
> +  if (stmts)
> +    {
> +      gsi_insert_seq_on_edge (next_e, stmts);
> +      gsi_commit_edge_inserts ();
> +    }
> +
> +  compute_bounds_for_level (pbb, level, v1, v2);

Mh. I do not completely understand all the code. But can't we get v1 and 
v2 set without the need for the compute_bounds_for_level function. Is 
the type_for_clast_expression not setting them.

Cheers
Tobi

On 07/28/2011 06:56 PM, Sebastian Pop wrote:
> Hi Tobi,
>
> On Thu, Jul 28, 2011 at 12:13, Tobias Grosser<tobias@grosser.es>  wrote:
>>> +  struct clast_user_stmt *body
>>> +    = clast_get_body_of_loop ((struct clast_stmt *) stmt);
>>
>> I am not a big fan of using clast_get_body_of_loop as it is buggy.
>> Introducing new uses of it, is nothing what I would support. Do we really
>> need this?
>
> No, because of ...
>
>>
>>> +  poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (body->statement);
>>
>> What about some more meaningful names like bound_one, bound_two?
>
> Ok, see the second patch attached.
>
>>> +
>>> +  compute_bounds_for_level (pbb, level, v1, v2);
>>
>> Mh. I do not completely understand all the code. But can't we get v1 and v2
>> set without the need for the compute_bounds_for_level function. Is the
>> type_for_clast_expression not setting them.
>>
>
> ... this.
> You are right.  type_for_clast_expr would provide the bounds for the
> RHS of the assign and so we don't need to compute the bounds on
> the loop level, as we would have done on a real loop.  Attached the
> amended patch.  I'm regstrapping these patches on amd64-linux.
> Ok for trunk after?

Looks good to me. Please commit if it passes regstrapping.

Cheers
Tobi