[GSoC] generation of Gimple code from isl_ast_node_if

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

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;
+}

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

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.

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

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

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

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

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

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

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