[GSoC] generation of Gimple code from isl_ast_node_if

[GSoC] generation of Gimple code from isl_ast_node_if

[Roman Gareev]

[-- Attachment #1: Type: text/plain, Size: 831 bytes --]

I've attached the patch, which contains generation of Gimple code from
isl_ast_node_if.

However, I've found out a problem. When I'm trying to generate Gimple
code from, for example, the following ISL AST:

{
  for (int c1 = 0; c1 <= 49; c1 += 1) {
    S_6(c1);
    if (c1 <= 48) {
      S_3(c1);
      if (c1 >= 24)
        S_4(c1);
      S_5(c1);
    }
  }
  S_7();
}

the pointer to Gimple basic block of S_3's poly basic block is NULL.

Could you please advise me possible reasons of this issue?

The source code of the example:

int
foo ()
{
  int i, res = 0;

  for (i = 0; i < 50; i++)
    {
      if (i >= 25)
        res += i;
    }

  return res;
}

extern void abort ();

int
main (void)
{
  int res = foo ();

  if (res != 1225)
    abort ();

  return 0;
}

--
                                   Cheers, Roman Gareev.

[-- Attachment #2: patch.txt --]
[-- Type: text/plain, Size: 1913 bytes --]

Index: gcc/graphite-isl-ast-to-gimple.c
===================================================================
--- gcc/graphite-isl-ast-to-gimple.c	(revision 212922)
+++ gcc/graphite-isl-ast-to-gimple.c	(working copy)
@@ -636,6 +636,42 @@
   return next_e;
 }
 
+/* Creates a new if region corresponding to ISL's cond.  */
+
+static edge
+graphite_create_new_guard (edge entry_edge, __isl_take isl_ast_expr *if_cond,
+			   ivs_params &ip)
+{
+  tree type =
+    build_nonstandard_integer_type (graphite_expression_type_precision, 0);
+  tree cond_expr = gcc_expression_from_isl_expression (type, if_cond, ip);
+  edge exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
+  return exit_edge;
+}
+
+/* Translates an isl_ast_node_if to Gimple.  */
+
+static edge
+translate_isl_ast_node_if (loop_p context_loop,
+			   __isl_keep isl_ast_node *node,
+			   edge next_e, ivs_params &ip)
+{
+  gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_if);
+  isl_ast_expr *if_cond = isl_ast_node_if_get_cond (node);
+  edge last_e = graphite_create_new_guard (next_e, if_cond, ip);
+
+  edge true_e = get_true_edge_from_guard_bb (next_e->dest);
+  isl_ast_node *then_node = isl_ast_node_if_get_then (node);
+  translate_isl_ast (context_loop, then_node, true_e, ip);
+  isl_ast_node_free (then_node);
+
+  edge false_e = get_false_edge_from_guard_bb (next_e->dest);
+  isl_ast_node *else_node = isl_ast_node_if_get_else (node);
+  translate_isl_ast (context_loop, else_node, false_e, ip);
+  isl_ast_node_free (else_node);
+  return last_e;
+}
+
 /* Translates an ISL AST node NODE to GCC representation in the
    context of a SESE.  */
 
@@ -653,7 +689,8 @@
 					 next_e, ip);
 
     case isl_ast_node_if:
-      return next_e;
+      return translate_isl_ast_node_if (context_loop, node,
+					next_e, ip);
 
     case isl_ast_node_user:
       return translate_isl_ast_node_user (node, next_e, ip);

Re: [GSoC] generation of Gimple code from isl_ast_node_if

[Tobias Grosser]

On 24/07/2014 12:09, Roman Gareev wrote:
> I've attached the patch, which contains generation of Gimple code from
> isl_ast_node_if.

Nice.

> However, I've found out a problem. When I'm trying to generate Gimple
> code from, for example, the following ISL AST:
>
> {
>    for (int c1 = 0; c1 <= 49; c1 += 1) {
>      S_6(c1);
>      if (c1 <= 48) {
>        S_3(c1);
>        if (c1 >= 24)
>          S_4(c1);
>        S_5(c1);
>      }
>    }
>    S_7();
> }
>
> the pointer to Gimple basic block of S_3's poly basic block is NULL.
>
> Could you please advise me possible reasons of this issue?

I have no idea. Is the Gimple basic block of S_3 never set, or is it set 
and deleted on the way? What code does S_3 correspond to?

The code itself looks good. Let's get back to this after we understood 
this bug.

Cheers,
Tobias

Re: [GSoC] generation of Gimple code from isl_ast_node_if

[Roman Gareev]

> I have no idea. Is the Gimple basic block of S_3 never set, or is it set and
> deleted on the way?

I think, that it is deleted on the way. I've found out, that the
Gimple basic block will be set, if we add the following code to the
generate_isl_schedule:

bb_schedule = isl_map_set_tuple_id (bb_schedule, isl_dim_in,
isl_id_for_pbb (scop, pbb));

where isl_id_for_pbb is

static isl_id *
isl_id_for_pbb (scop_p s, poly_bb_p pbb)
{
  char name[50];
  snprintf (name, sizeof (name), "S_%d", pbb_index (pbb));
  return isl_id_alloc (s->ctx, name, pbb);
}

> What code does S_3 correspond to?

If I'm not mistaken, it is corresponds to:

res_18 = Cross_BB_scalar_dependence.7[0];
phi_out_of_ssa.4[0] = res_18;

I used the following code from
https://gcc.gnu.org/onlinedocs/gccint/Basic-Blocks.html to dump basic
block of the Gimple basic block:

gimple_stmt_iterator si;

for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
  {
    gimple phi = gsi_stmt (si);
    print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
  }
for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
  {
    gimple stmt = gsi_stmt (si);
    print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
  }

Could you please advise me possible functions from
graphite-sese-to-poly.c, which can delete this?

P.S.: Only S_3 has this problem in the example.

--
                                   Cheers, Roman Gareev.

Re: [GSoC] generation of Gimple code from isl_ast_node_if

[Tobias Grosser]

On 25/07/2014 13:20, Roman Gareev wrote:
>> I have no idea. Is the Gimple basic block of S_3 never set, or is it set and
>> deleted on the way?
>
> I think, that it is deleted on the way. I've found out, that the
> Gimple basic block will be set, if we add the following code to the
> generate_isl_schedule:
>
> bb_schedule = isl_map_set_tuple_id (bb_schedule, isl_dim_in,
> isl_id_for_pbb (scop, pbb));

Is at this point the pbb of S_3 still valid? Does it point to valid data?

> where isl_id_for_pbb is
>
> static isl_id *
> isl_id_for_pbb (scop_p s, poly_bb_p pbb)
> {
>    char name[50];
>    snprintf (name, sizeof (name), "S_%d", pbb_index (pbb));
>    return isl_id_alloc (s->ctx, name, pbb);
> }

This is surprising. You previously said the pbb pointer is still valid, 
but only the pointer that within the pbb that points to the gimple bb is 
invalid. I don't really see why setting the isl_id again (pointing to 
the very same pbb) helps in preserving the data structures in pbb.

>> What code does S_3 correspond to?
>
> If I'm not mistaken, it is corresponds to:
>
> res_18 = Cross_BB_scalar_dependence.7[0];
> phi_out_of_ssa.4[0] = res_18;
>
> I used the following code from
> https://gcc.gnu.org/onlinedocs/gccint/Basic-Blocks.html to dump basic
> block of the Gimple basic block:
>
> gimple_stmt_iterator si;
>
> for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
>    {
>      gimple phi = gsi_stmt (si);
>      print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
>    }
> for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
>    {
>      gimple stmt = gsi_stmt (si);
>      print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
>    }
>
> Could you please advise me possible functions from
> graphite-sese-to-poly.c, which can delete this?

This is a hard guess. I would propose to debug this in gdb. Add a 
breakpoint at a location where pbb/isl_id are set, verify that they are 
correctly set and add a watchpoint on the pointer that is set to ZERO. 
This should make gdb stop exactly at the point where the information is 
lost.

Alternatively, you could also try to run this in valgrind.

Cheers,
Tobias

Re: [GSoC] generation of Gimple code from isl_ast_node_if

[Roman Gareev]

[-- Attachment #1: Type: text/plain, Size: 761 bytes --]

If I'm not mistaken, the reason of this bug is incorrect creation of a
poly_bb_p for basic_block from the existing pbb in new_pbb_from_pbb
(It is located in graphite-sese-to-poly.c). I think, that we should
set a new id of pbb1->domain (instead of using the id of the pbb),
which contains pointer to the pbb1.

I found out this after dumping of an index of pbb in the user
statement S_3. Its index is 9. It is created in
rewrite_reduction_out_of_ssa using new_pbb_from_pbb and the pbb with
index 3. After that the user statement S_3 is removed in
build_scop_drs, but the id of the  pbb->domain and the
pbb->transformed point to the old pbb with index 3.

I've attached the patch, which may fix this.

--
                                   Cheers, Roman Gareev.

[-- Attachment #2: patch.txt --]
[-- Type: text/plain, Size: 554 bytes --]

Index: gcc/graphite-sese-to-poly.c
===================================================================
--- gcc/graphite-sese-to-poly.c	(revision 212995)
+++ gcc/graphite-sese-to-poly.c	(working copy)
@@ -2044,6 +2044,10 @@
       break;
 
   pbb1->domain = isl_set_copy (pbb->domain);
+  char name[50];
+  snprintf (name, sizeof (name), "S_%d", pbb_index (pbb1));
+  pbb1->domain = isl_set_set_tuple_id (pbb1->domain,
+				       isl_id_alloc (scop->ctx, name, pbb1));
 
   GBB_PBB (gbb1) = pbb1;
   GBB_CONDITIONS (gbb1) = GBB_CONDITIONS (gbb).copy ();

Re: [GSoC] generation of Gimple code from isl_ast_node_if

[Tobias Grosser]

On 26/07/2014 10:59, Roman Gareev wrote:
> If I'm not mistaken, the reason of this bug is incorrect creation of a
> poly_bb_p for basic_block from the existing pbb in new_pbb_from_pbb
> (It is located in graphite-sese-to-poly.c). I think, that we should
> set a new id of pbb1->domain (instead of using the id of the pbb),
> which contains pointer to the pbb1.
 >
> I found out this after dumping of an index of pbb in the user
> statement S_3. Its index is 9. It is created in
> rewrite_reduction_out_of_ssa using new_pbb_from_pbb and the pbb with
> index 3. After that the user statement S_3 is removed in
> build_scop_drs, but the id of the  pbb->domain and the
> pbb->transformed point to the old pbb with index 3.

Interesting. I was not even aware that we did statement splitting for 
reductions. Very nice analysis.

> I've attached the patch, which may fix this.
>
> --
>                                     Cheers, Roman Gareev.
>
>
> patch.txt
>
>
> Index: gcc/graphite-sese-to-poly.c
> ===================================================================
> --- gcc/graphite-sese-to-poly.c	(revision 212995)
> +++ gcc/graphite-sese-to-poly.c	(working copy)
> @@ -2044,6 +2044,10 @@
>         break;
>
>     pbb1->domain = isl_set_copy (pbb->domain);
> +  char name[50];
> +  snprintf (name, sizeof (name), "S_%d", pbb_index (pbb1));
> +  pbb1->domain = isl_set_set_tuple_id (pbb1->domain,
> +				       isl_id_alloc (scop->ctx, name, pbb1));

Any reason you don't use isl_id_for_pbb() to create this isl_id?

Otherwise, the patch looks good to me. You can commit it if the graphite 
tests still pass and you add an appropriate ChangeLog entry.

Cheers,
Tobias

Re: [GSoC] generation of Gimple code from isl_ast_node_if

[Tobias Grosser]

On 24/07/2014 12:09, Roman Gareev wrote:
> I've attached the patch, which contains generation of Gimple code from
> isl_ast_node_if.
>
> However, I've found out a problem. When I'm trying to generate Gimple
> code from, for example, the following ISL AST:
>
> {
>    for (int c1 = 0; c1 <= 49; c1 += 1) {
>      S_6(c1);
>      if (c1 <= 48) {
>        S_3(c1);
>        if (c1 >= 24)
>          S_4(c1);
>        S_5(c1);
>      }
>    }
>    S_7();
> }
>
> the pointer to Gimple basic block of S_3's poly basic block is NULL.
>
> Could you please advise me possible reasons of this issue?
>
> The source code of the example:
>
> int
> foo ()
> {
>    int i, res = 0;
>
>    for (i = 0; i < 50; i++)
>      {
>        if (i >= 25)
>          res += i;
>      }
>
>    return res;
> }
>
> extern void abort ();
>
> int
> main (void)
> {
>    int res = foo ();
>
>    if (res != 1225)
>      abort ();
>
>    return 0;
> }

This patch looks also good. Can you quickly repost with the two test 
cases as well as the appropriate ChangeLog, before I give the final OK.

Cheers,
Tobias

Re: [GSoC] generation of Gimple code from isl_ast_node_if

[Roman Gareev]

[-- Attachment #1: Type: text/plain, Size: 639 bytes --]

> Any reason you don't use isl_id_for_pbb() to create this isl_id?

Yes, it is redundant. I've used isl_id_for_pbb() in the improved version.

> Otherwise, the patch looks good to me. You can commit it if the graphite tests still pass and you add an appropriate ChangeLog entry.

I haven't found out regression during testing with the graphite tests.

> This patch looks also good. Can you quickly repost with the two test cases as well as the appropriate ChangeLog, before I give the final OK.

If I'm not mistaken, I sent you only one test case. Should we create
another one?

--
                                   Cheers, Roman Gareev.

[-- Attachment #2: ChangeLog_entry1.txt --]
[-- Type: text/plain, Size: 212 bytes --]

2014-07-26  Roman Gareev  <gareevroman@gmail.com>

[gcc/]

	* graphite-sese-to-poly.c:
	(new_pbb_from_pbb): Set a new id of pbb1->domain (instead of using the
	id of the pbb), which contains pointer to the pbb1.

[-- Attachment #3: ChangeLog_entry2.txt --]
[-- Type: text/plain, Size: 316 bytes --]

2014-07-26  Roman Gareev  <gareevroman@gmail.com>

[gcc/]

	* graphite-isl-ast-to-gimple.c:
	(graphite_create_new_guard): New function.
	(translate_isl_ast_node_if): New function.
	(translate_isl_ast): Add calling of translate_isl_ast_node_if.
	
[gcc/testsuite]

	* gcc.dg/graphite/isl-ast-gen-if-1.c: New testcase.

[-- Attachment #4: patch1.txt --]
[-- Type: text/plain, Size: 532 bytes --]

Index: gcc/graphite-sese-to-poly.c
===================================================================
--- gcc/graphite-sese-to-poly.c	(revision 212995)
+++ gcc/graphite-sese-to-poly.c	(working copy)
@@ -2044,7 +2044,8 @@
       break;
 
   pbb1->domain = isl_set_copy (pbb->domain);
-
+  pbb1->domain = isl_set_set_tuple_id (pbb1->domain,
+				       isl_id_for_pbb (scop, pbb1));
   GBB_PBB (gbb1) = pbb1;
   GBB_CONDITIONS (gbb1) = GBB_CONDITIONS (gbb).copy ();
   GBB_CONDITION_CASES (gbb1) = GBB_CONDITION_CASES (gbb).copy ();

[-- Attachment #5: patch2.txt --]
[-- Type: text/plain, Size: 2650 bytes --]

Index: gcc/graphite-isl-ast-to-gimple.c
===================================================================
--- gcc/graphite-isl-ast-to-gimple.c	(revision 212995)
+++ gcc/graphite-isl-ast-to-gimple.c	(working copy)
@@ -646,6 +646,43 @@
   return next_e;
 }
 
+/* Creates a new if region corresponding to ISL's cond.  */
+
+static edge
+graphite_create_new_guard (edge entry_edge, __isl_take isl_ast_expr *if_cond,
+			   ivs_params &ip)
+{
+  tree type =
+    build_nonstandard_integer_type (graphite_expression_type_precision, 0);
+  tree cond_expr = gcc_expression_from_isl_expression (type, if_cond, ip);
+  edge exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
+  return exit_edge;
+}
+
+/* Translates an isl_ast_node_if to Gimple.  */
+
+static edge
+translate_isl_ast_node_if (loop_p context_loop,
+			   __isl_keep isl_ast_node *node,
+			   edge next_e, ivs_params &ip)
+{
+  gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_if);
+  isl_ast_expr *if_cond = isl_ast_node_if_get_cond (node);
+  edge last_e = graphite_create_new_guard (next_e, if_cond, ip);
+
+  edge true_e = get_true_edge_from_guard_bb (next_e->dest);
+  isl_ast_node *then_node = isl_ast_node_if_get_then (node);
+  translate_isl_ast (context_loop, then_node, true_e, ip);
+  isl_ast_node_free (then_node);
+
+  edge false_e = get_false_edge_from_guard_bb (next_e->dest);
+  isl_ast_node *else_node = isl_ast_node_if_get_else (node);
+  if (isl_ast_node_get_type (else_node) != isl_ast_node_error)
+    translate_isl_ast (context_loop, else_node, false_e, ip);
+  isl_ast_node_free (else_node);
+  return last_e;
+}
+
 /* Translates an ISL AST node NODE to GCC representation in the
    context of a SESE.  */
 
@@ -663,7 +700,8 @@
 					 next_e, ip);
 
     case isl_ast_node_if:
-      return next_e;
+      return translate_isl_ast_node_if (context_loop, node,
+					next_e, ip);
 
     case isl_ast_node_user:
       return translate_isl_ast_node_user (node, next_e, ip);
Index: gcc/testsuite/gcc.dg/graphite/isl-ast-gen-if-1.c
===================================================================
--- gcc/testsuite/gcc.dg/graphite/isl-ast-gen-if-1.c	(revision 0)
+++ gcc/testsuite/gcc.dg/graphite/isl-ast-gen-if-1.c	(working copy)
@@ -0,0 +1,29 @@
+/* { dg-do run } */
+/* { dg-options "-O2 -fgraphite-identity -fgraphite-code-generator=isl" } */
+
+static int __attribute__((noinline))
+foo ()
+{
+  int i, res = 0;
+
+  for (i = 0; i < 50; i++)
+    {
+      if (i >= 25)
+        res += i;
+    }
+
+  return res;
+}
+
+extern void abort ();
+
+int
+main (void)
+{ 
+  int res = foo ();
+
+  if (res != 925)
+    abort ();
+
+  return 0;
+}

Re: [GSoC] generation of Gimple code from isl_ast_node_if

[Tobias Grosser]

On 26/07/2014 11:53, Roman Gareev wrote:
>> Any reason you don't use isl_id_for_pbb() to create this isl_id?
>
> Yes, it is redundant. I've used isl_id_for_pbb() in the improved version.
>
>> Otherwise, the patch looks good to me. You can commit it if the graphite tests still pass and you add an appropriate ChangeLog entry.
>
> I haven't found out regression during testing with the graphite tests.
>
>> This patch looks also good. Can you quickly repost with the two test cases as well as the appropriate ChangeLog, before I give the final OK.
>
> If I'm not mistaken, I sent you only one test case. Should we create
> another one?

Right, I got confused.

I would still add a test case which does not contain a reduction (+=)
and where graphite is not duplicating pbbs.

If you make res of type float I assume graphite will not detect it as a 
reduction. On the other side, it may not even introduce if conditions. 
So you may need a little bit more complicated code e.g:


   for (i = 0; i < 50; i++)
     {
       res += i * 2.1;
       if (i >= 25)
         res += i * 3;
     }

This should in the best case yield an isl_ast which matches the input code.

Also, please add a comment to the other test case that notes what kind 
of issue this one is testing (reduction, where the pbbs are possibly 
duplicated).

Cheers,
Tobias

Re: [GSoC] generation of Gimple code from isl_ast_node_if

[Roman Gareev]

I've tried to compile your example and had the similar problem. It
generates the following ISL AST


{
  for (int c1 = 0; c1 <= 49; c1 += 1) {
    S_6(c1);
    if (c1 <= 48) {
      S_3(c1);
      S_9(c1);
      if (c1 >= 24)
        S_4(c1);
      S_5(c1);
    }
  }
  S_7();
}


where S_9 has pbb->domain and pbb->transformed of S_3. A pointer to a
Gimple basic block is not NULL now, but it leads to the wrong answer.

I've tried different examples, which generate ISL AST, but they have
same problems. Could you please advise me another one?

--
                                   Cheers, Roman Gareev.

Re: [GSoC] generation of Gimple code from isl_ast_node_if

[Tobias Grosser]

On 26/07/2014 14:59, Roman Gareev wrote:
> I've tried to compile your example and had the similar problem. It
> generates the following ISL AST
>
>
> {
>    for (int c1 = 0; c1 <= 49; c1 += 1) {
>      S_6(c1);
>      if (c1 <= 48) {
>        S_3(c1);
>        S_9(c1);
>        if (c1 >= 24)
>          S_4(c1);
>        S_5(c1);
>      }
>    }
>    S_7();
> }
>
>
> where S_9 has pbb->domain and pbb->transformed of S_3. A pointer to a
> Gimple basic block is not NULL now, but it leads to the wrong answer.

What do you mean by wrong answer? Is there still a bug in the code 
generation or the AST is just more complex as expected.

> I've tried different examples, which generate ISL AST, but they have
> same problems. Could you please advise me another one?

To my understanding bb copies are introduced in case reductions are 
seen. You could try to just initialize an array (maybe a little bit more 
complex, but without += statements):

for i:
   A[i] = ...

You could do the summation/verfication outside of the scop e.g. in the 
main function.

Cheers
Tobias

Re: [GSoC] generation of Gimple code from isl_ast_node_if

[Roman Gareev]

> What do you mean by wrong answer? Is there still a bug in the code
> generation or the AST is just more complex as expected.

I mean that the value of res is wrong. I think it is because of the
wrong id of pbb->domain and pbb->transformed inherited from S_3 by S_9
(It was correct for S_3, but it is incorrect for S_9).

> To my understanding bb copies are introduced in case reductions are seen.
> You could try to just initialize an array (maybe a little bit more complex,
> but without += statements):
>
> for i:
>   A[i] = ...
>
> You could do the summation/verfication outside of the scop e.g. in the main
> function.

It seems that it doesn't help (at least for now).

However, I've found out the following example:

static int __attribute__((noinline))
foo ()
{
  int i, res = 0;

  for (i = 0; i < 50; i++)
    {
      if (i < 5)
        res += 1;
    }

  return res;
}

extern void abort ();

int
main (void)
{
  int res = foo ();
  if (res != 5)
    abort ();

  return 0;
}

It gives the correct result, inspite of duplicating of pbbs and
generates the following ISL AST

{
  for (int c1 = 0; c1 <= 49; c1 += 1) {
    for (int c2 = 0; c2 <= 1; c2 += 1)
      S_3(c1);
    if (c1 <= 4)
      S_4(c1);
    S_5(c1);
  }
  S_7();
}

Maybe we could use it. What do you think about this?

--
                                   Cheers, Roman Gareev.

Re: [GSoC] generation of Gimple code from isl_ast_node_if

[Tobias Grosser]

On 26/07/2014 15:48, Roman Gareev wrote:
>> What do you mean by wrong answer? Is there still a bug in the code
>> generation or the AST is just more complex as expected.
>
> I mean that the value of res is wrong. I think it is because of the
> wrong id of pbb->domain and pbb->transformed inherited from S_3 by S_9
> (It was correct for S_3, but it is incorrect for S_9).

Sorry Roman. I am still confused. Are we looking for a test case or are 
we still trying to understand an issue. Specifically, do we still 
incorrectly transform the code even after your isl_id_for_pbb() patch?

>> To my understanding bb copies are introduced in case reductions are seen.
>> You could try to just initialize an array (maybe a little bit more complex,
>> but without += statements):
>>
>> for i:
>>    A[i] = ...
>>
>> You could do the summation/verfication outside of the scop e.g. in the main
>> function.
>
> It seems that it doesn't help (at least for now).

Help for what? I was looking to create a simple test case. Is there 
still an open bug?

I am looking for a simple test case that does _not_ contain a reduction 
in addition to the test case you already have.

> However, I've found out the following example:
>
> static int __attribute__((noinline))
> foo ()
> {
>    int i, res = 0;
>
>    for (i = 0; i < 50; i++)
>      {
>        if (i < 5)
>          res += 1;
>      }

This one still has a reduction.

> It gives the correct result, inspite of duplicating of pbbs and
> generates the following ISL AST
>
> {
>    for (int c1 = 0; c1 <= 49; c1 += 1) {
>      for (int c2 = 0; c2 <= 1; c2 += 1)
>        S_3(c1);
>      if (c1 <= 4)
>        S_4(c1);
>      S_5(c1);
>    }
>    S_7();

And this one still duplicates pbbs. So this is not the simple test case 
I am looking for. It introduces several new statements I do not 
understand, so it does not seem to be a trivial test case.

> Maybe we could use it. What do you think about this?

What do you want to use it for?

Cheers,
Tobias

Re: [GSoC] generation of Gimple code from isl_ast_node_if

[Roman Gareev]

> I would still add a test case which does not contain a reduction (+=)
> and where graphite is not duplicating pbbs.

> Help for what? I was looking to create a simple test case. Is there still an
> open bug?

Sorry, I thought, we should add this test case to be able to test
graphite without patch related to graphite-sese-to-poly.c (patch1).

> Sorry Roman. I am still confused. Are we looking for a test case or are we
> still trying to understand an issue. Specifically, do we still incorrectly
> transform the code even after your isl_id_for_pbb() patch?

I gives a wrong answer without patch1. The code is transformed
correctly with this patch.

--
                                   Cheers, Roman Gareev.

Re: [GSoC] generation of Gimple code from isl_ast_node_if

[Tobias Grosser]

On 26/07/2014 16:16, Roman Gareev wrote:
>> I would still add a test case which does not contain a reduction (+=)
>> and where graphite is not duplicating pbbs.
>
>> Help for what? I was looking to create a simple test case. Is there still an
>> open bug?
>
> Sorry, I thought, we should add this test case to be able to test
> graphite without patch related to graphite-sese-to-poly.c (patch1).

Right. I think we should have a simple test case that does not trigger 
basic block duplication, which is basically triggered for reductions.

The test case:

static int __attribute__((noinline))
foo ()
{
   int i, res = 0;

   for (i = 0; i < 50; i++)
     {
       if (i < 5)
         res += 1;
     }

   return res;
}

that you just proposed contains again a reduction and yields several bbs 
that cause problems.

{
   for (int c1 = 0; c1 <= 49; c1 += 1) {
     for (int c2 = 0; c2 <= 1; c2 += 1)
       S_3(c1);
     if (c1 <= 4)
       S_4(c1);
     S_5(c1);
   }
   S_7();
}

I proposed a test case without a reduction (possibly a little bit more 
complex):

 > > for i:
 > >   A[i] = ...
 > >
 > > You could do the summation/verfication outside of the scop e.g. in
 > > the main
 > > function.
 >
 > It seems that it doesn't help (at least for now).

Can you explain why you believe it is hard/impossible to generate a test 
case without reduction?

>> Sorry Roman. I am still confused. Are we looking for a test case or are we
>> still trying to understand an issue. Specifically, do we still incorrectly
>> transform the code even after your isl_id_for_pbb() patch?
>
> I gives a wrong answer without patch1. The code is transformed
> correctly with this patch.

OK. So we don't need to solve another bug. That is good.

Cheers,
Tobias

Re: [GSoC] generation of Gimple code from isl_ast_node_if

[Roman Gareev]

> Can you explain why you believe it is hard/impossible to generate a test
> case without reduction?

I don't believe this. I only know that all the test cases considered
by me have the same problem.

Could you please explain what is 'reduction'? I've found out that,
according to the comment of the rewrite_reductions_out_of_ssa (this
function duplicates pbbs), the rewrite_reductions_out_of_ssa  rewrite
out of SSA all the reduction phi nodes of SCOP. What are reduction phi
nodes? How are they related to 'reduction'?

--
                                   Cheers, Roman Gareev.

Re: [GSoC] generation of Gimple code from isl_ast_node_if

[Tobias Grosser]

On 27/07/2014 08:12, Roman Gareev wrote:
>> Can you explain why you believe it is hard/impossible to generate a test
>> case without reduction?
>
> I don't believe this. I only know that all the test cases considered
> by me have the same problem.
>
> Could you please explain what is 'reduction'? I've found out that,
> according to the comment of the rewrite_reductions_out_of_ssa (this
> function duplicates pbbs), the rewrite_reductions_out_of_ssa  rewrite
> out of SSA all the reduction phi nodes of SCOP. What are reduction phi
> nodes? How are they related to 'reduction'?

A reduction is an operation that combines a set of elements into a 
single element.

for (i = 0; i < 100; i++)
    sum += i;

combines the different elements 'i' into the single element 'sum'. 
Reductions where the combine operation *here '+') is associative and 
commutative can be reordered. This means you can e.g. write the loop as

for (i = 99; i >= 0; i--)
    sum += i;

and you get the same result. There are two ways to ensure something is 
not optimized as a reduction

1) Destroy associativity/commutativity

Floating point operations are generally not associative/commutative, 
except if -ffast-math is given to the compiler

2) Do not reduce into one element.

If we just assign to different elements of an array, there is no 
possibility we have a reduction.

Let's get back to the earlier test case:

for (i = 0; i < n; i++) {
    if (i <= m)
T:     A[i] = i;

S: A[i + p] = j;
}

What is the ast generated for this one? I just created this input file 
for isl_codegen:

[n,m] -> {S[i] -> [i]: 0<= i <= n;T[i] -> [i]: 0<= i <= m and i <= n}
[n,m] -> {:n,m > 1}
{}

$ isl_codegen < input.file

for (int c0 = 0; c0 <= n; c0 += 1) {
   if (m >= c0)
     T(c0);
   S(c0);
}

Is something in graphite preventing us to generate this simple loop with 
just one if-condition and no statement duplication?

Cheers,
Tobias

Re: [GSoC] generation of Gimple code from isl_ast_node_if

[Roman Gareev]

[-- Attachment #1: Type: text/plain, Size: 420 bytes --]

Thank you! I've attached patches with a test case (it is located in
patch1.txt), which generates the following ISL AST:

for (int c1 = 0; c1 <= 49; c1 += 1) {
  if (c1 <= 24)
    S_4(c1);
  S_5(c1);
}

I think that it doesn't contain reduction and doesn't yield several
bbs. I've also checked that pbbs correspond to pbbs of pbb->domain and
pbb->transformed.

--
                                   Cheers, Roman Gareev.

[-- Attachment #2: ChangeLog_entry1.txt --]
[-- Type: text/plain, Size: 316 bytes --]

2014-07-23  Roman Gareev  <gareevroman@gmail.com>

[gcc/]

	* graphite-isl-ast-to-gimple.c:
	(graphite_create_new_guard): New function.
	(translate_isl_ast_node_if): New function.
	(translate_isl_ast): Add calling of translate_isl_ast_node_if.
	
[gcc/testsuite]

	* gcc.dg/graphite/isl-ast-gen-if-1.c: New testcase.

[-- Attachment #3: ChangeLog_entry2.txt --]
[-- Type: text/plain, Size: 283 bytes --]

2014-07-23  Roman Gareev  <gareevroman@gmail.com>

[gcc/]

	* graphite-sese-to-poly.c:
	(new_pbb_from_pbb): Set a new id of pbb1->domain (instead of using the
	id of the pbb), which contains pointer to the pbb1.

[gcc/testsuite]

	* gcc.dg/graphite/isl-ast-gen-if-2.c: New testcase.

[-- Attachment #4: patch1.txt --]
[-- Type: text/plain, Size: 2850 bytes --]

Index: gcc/graphite-isl-ast-to-gimple.c
===================================================================
--- gcc/graphite-isl-ast-to-gimple.c	(revision 212995)
+++ gcc/graphite-isl-ast-to-gimple.c	(working copy)
@@ -646,6 +646,43 @@
   return next_e;
 }
 
+/* Creates a new if region corresponding to ISL's cond.  */
+
+static edge
+graphite_create_new_guard (edge entry_edge, __isl_take isl_ast_expr *if_cond,
+			   ivs_params &ip)
+{
+  tree type =
+    build_nonstandard_integer_type (graphite_expression_type_precision, 0);
+  tree cond_expr = gcc_expression_from_isl_expression (type, if_cond, ip);
+  edge exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
+  return exit_edge;
+}
+
+/* Translates an isl_ast_node_if to Gimple.  */
+
+static edge
+translate_isl_ast_node_if (loop_p context_loop,
+			   __isl_keep isl_ast_node *node,
+			   edge next_e, ivs_params &ip)
+{
+  gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_if);
+  isl_ast_expr *if_cond = isl_ast_node_if_get_cond (node);
+  edge last_e = graphite_create_new_guard (next_e, if_cond, ip);
+
+  edge true_e = get_true_edge_from_guard_bb (next_e->dest);
+  isl_ast_node *then_node = isl_ast_node_if_get_then (node);
+  translate_isl_ast (context_loop, then_node, true_e, ip);
+  isl_ast_node_free (then_node);
+
+  edge false_e = get_false_edge_from_guard_bb (next_e->dest);
+  isl_ast_node *else_node = isl_ast_node_if_get_else (node);
+  if (isl_ast_node_get_type (else_node) != isl_ast_node_error)
+    translate_isl_ast (context_loop, else_node, false_e, ip);
+  isl_ast_node_free (else_node);
+  return last_e;
+}
+
 /* Translates an ISL AST node NODE to GCC representation in the
    context of a SESE.  */
 
@@ -663,7 +700,8 @@
 					 next_e, ip);
 
     case isl_ast_node_if:
-      return next_e;
+      return translate_isl_ast_node_if (context_loop, node,
+					next_e, ip);
 
     case isl_ast_node_user:
       return translate_isl_ast_node_user (node, next_e, ip);
Index: gcc/testsuite/gcc.dg/graphite/isl-ast-gen-if-1.c
===================================================================
--- gcc/testsuite/gcc.dg/graphite/isl-ast-gen-if-1.c	(revision 0)
+++ gcc/testsuite/gcc.dg/graphite/isl-ast-gen-if-1.c	(working copy)
@@ -0,0 +1,37 @@
+/* { dg-do run } */
+/* { dg-options "-O2 -fgraphite-identity -fgraphite-code-generator=isl" } */
+
+int st = 1;
+static void __attribute__((noinline))
+foo (int a[], int n)
+{
+  int i;
+  for (i = 0; i < n; i++)
+    {
+      if (i < 25)
+        a[i] = i;
+      a[n - i] = 1;
+    }
+}
+
+static int __attribute__((noinline))
+array_sum (int a[])
+{
+  int i, res = 0;
+  for(i = 0; i < 50; i += st)
+    res += a[i];
+  return res;
+}
+
+extern void abort ();
+
+int
+main (void)
+{
+  int a[50];
+  foo (a, 50);
+  int res = array_sum (a);
+  if (res != 49)
+    abort ();
+  return 0;
+}

[-- Attachment #5: patch2.txt --]
[-- Type: text/plain, Size: 1276 bytes --]

Index: gcc/graphite-sese-to-poly.c
===================================================================
--- gcc/graphite-sese-to-poly.c	(revision 212995)
+++ gcc/graphite-sese-to-poly.c	(working copy)
@@ -2044,7 +2044,8 @@
       break;
 
   pbb1->domain = isl_set_copy (pbb->domain);
-
+  pbb1->domain = isl_set_set_tuple_id (pbb1->domain,
+				       isl_id_for_pbb (scop, pbb1));
   GBB_PBB (gbb1) = pbb1;
   GBB_CONDITIONS (gbb1) = GBB_CONDITIONS (gbb).copy ();
   GBB_CONDITION_CASES (gbb1) = GBB_CONDITION_CASES (gbb).copy ();
Index: gcc/testsuite/gcc.dg/graphite/isl-ast-gen-if-2.c
===================================================================
--- gcc/testsuite/gcc.dg/graphite/isl-ast-gen-if-2.c	(revision 0)
+++ gcc/testsuite/gcc.dg/graphite/isl-ast-gen-if-2.c	(working copy)
@@ -0,0 +1,31 @@
+/* { dg-do run } */
+/* { dg-options "-O2 -fgraphite-identity -fgraphite-code-generator=isl" } */
+
+/* This test case tests reduction, where the pbbs are duplicated.  */
+
+static int __attribute__((noinline))
+foo ()
+{
+  int i, res = 0;
+
+  for (i = 0; i < 50; i++)
+    {
+      if (i >= 25)
+        res += i;
+    }
+
+  return res;
+}
+
+extern void abort ();
+
+int
+main (void)
+{ 
+  int res = foo ();
+
+  if (res != 925)
+    abort ();
+
+  return 0;
+}

Re: [GSoC] generation of Gimple code from isl_ast_node_if

[Tobias Grosser]

On 27/07/2014 12:48, Roman Gareev wrote:
> Thank you! I've attached patches with a test case (it is located in
> patch1.txt), which generates the following ISL AST:
>
> for (int c1 = 0; c1 <= 49; c1 += 1) {
>    if (c1 <= 24)
>      S_4(c1);
>    S_5(c1);
> }
>
> I think that it doesn't contain reduction and doesn't yield several
> bbs. I've also checked that pbbs correspond to pbbs of pbb->domain and
> pbb->transformed.

OK. LGTM.

Tobias