Re: [GSoC] generation of Gimple loops with empty bodies

Re: [GSoC] generation of Gimple loops with empty bodies

[Dominique Dhumieres]

On x86_64-apple-darwin13, the test gcc.dg/graphite/isl-codegen-loop-dumping.c
gives an ICE with -m32 after r212455. The backtrace is

* thread #1: tid = 0xdac306, 0x0000000100523c52 cc1`fold_binary_loc(loc=0, code=MINUS_EXPR, type=0x0000000000000000, op0=0x0000000142c09bd0, op1=0x0000000142c1b048) + 6402 at fold-const.c:10813, queue = 'com.apple.main-thread', stop reason = EXC_BAD_ACCESS (code=1, address=0x0)
    frame #0: 0x0000000100523c52 cc1`fold_binary_loc(loc=0, code=MINUS_EXPR, type=0x0000000000000000, op0=0x0000000142c09bd0, op1=0x0000000142c1b048) + 6402 at fold-const.c:10813
   10810	      if (TREE_CODE (type) != COMPLEX_TYPE
   10811		  && TREE_CODE (arg0) == NEGATE_EXPR
   10812		  && integer_onep (arg1)
-> 10813		  && !TYPE_OVERFLOW_TRAPS (type))
   10814		return fold_build1_loc (loc, BIT_NOT_EXPR, type,
   10815				    fold_convert_loc (loc, type,
   10816						      TREE_OPERAND (arg0, 0)));
(lldb) bt
* thread #1: tid = 0xdac306, 0x0000000100523c52 cc1`fold_binary_loc(loc=0, code=MINUS_EXPR, type=0x0000000000000000, op0=0x0000000142c09bd0, op1=0x0000000142c1b048) + 6402 at fold-const.c:10813, queue = 'com.apple.main-thread', stop reason = EXC_BAD_ACCESS (code=1, address=0x0)
  * frame #0: 0x0000000100523c52 cc1`fold_binary_loc(loc=0, code=MINUS_EXPR, type=0x0000000000000000, op0=0x0000000142c09bd0, op1=0x0000000142c1b048) + 6402 at fold-const.c:10813
    frame #1: 0x0000000100549c2b cc1`fold_build2_stat_loc(loc=0, code=MINUS_EXPR, type=0x0000000000000000, op0=0x0000000142c09bd0, op1=0x0000000142c1b048) + 27 at fold-const.c:14985
    frame #2: 0x00000001005ff9a1 cc1`gcc_expression_from_isl_expression + 417 at graphite-isl-ast-to-gimple.c:175
    frame #3: 0x00000001005ff800 cc1`gcc_expression_from_isl_expression + 928
    frame #4: 0x00000001005ff818 cc1`gcc_expression_from_isl_expression + 24 at graphite-isl-ast-to-gimple.c:164
    frame #5: 0x00000001005ff800 cc1`gcc_expression_from_isl_expression + 928
    frame #6: 0x00000001005ffd26 cc1`translate_isl_ast + 229 at graphite-isl-ast-to-gimple.c:501
    frame #7: 0x00000001005ffc41 cc1`translate_isl_ast + 17
    frame #8: 0x00000001005ffc30 cc1`translate_isl_ast(context_loop=0x0000000142c031a0, node=0x0000000141f1acd0, next_e=0x0000000142d36f50, ip=0x00007fff5fbfeff0) + 128
    frame #9: 0x000000010060047c cc1`graphite_regenerate_ast_isl(scop=<unavailable>) + 844 at graphite-isl-ast-to-gimple.c:699
    frame #10: 0x00000001005f8a28 cc1`graphite_transform_loops() + 2280 at graphite.c:304
    frame #11: 0x00000001005f8ab1 cc1`execute(this=<unavailable>, fun=<unavailable>) + 33 at graphite.c:333
    frame #12: 0x0000000100783097 cc1`execute_one_pass(pass=0x0000000141e10f40) + 407 at passes.c:2149
    frame #13: 0x000000010078368e cc1`execute_pass_list_1(pass=0x0000000141e10f40) + 30 at passes.c:2201
    frame #14: 0x00000001007836a0 cc1`execute_pass_list_1(pass=0x0000000141e10ee0) + 48 at passes.c:2202
    frame #15: 0x00000001007836a0 cc1`execute_pass_list_1(pass=0x0000000141e10ac0) + 48 at passes.c:2202
    frame #16: 0x00000001007836a0 cc1`execute_pass_list_1(pass=0x0000000141e0fa40) + 48 at passes.c:2202
    frame #17: 0x00000001007836e9 cc1`execute_pass_list(fn=0x0000000142d1c738, pass=0x0000000141e0f980) + 25 at passes.c:2212
    frame #18: 0x00000001003ee215 cc1`expand_function(node=0x0000000142d3b000) + 245 at cgraphunit.c:1786
    frame #19: 0x00000001003f0847 cc1`compile() + 230 at cgraphunit.c:1920
    frame #20: 0x00000001003f0761 cc1`compile() + 2209
    frame #21: 0x00000001003f1026 cc1`finalize_compilation_unit() + 102 at cgraphunit.c:2341
    frame #22: 0x0000000100020d55 cc1`c_write_global_declarations() + 613 at c-decl.c:10463
    frame #23: 0x000000010085cc97 cc1`compile_file + 167 at toplev.c:562
    frame #24: 0x000000010085f43f cc1`toplev_main(argc=7, argv=0x00007fff5fbff390) + 3327 at toplev.c:1946

TIA

Dominique

Re: [GSoC] generation of Gimple loops with empty bodies

[Roman Gareev]

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

Hi Dominique,

thank you for the message! I've attached a patch, that may fix the issue.

Please report back if it fixes the problem.

--
                                   Cheers, Roman Gareev.

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

Index: gcc/graphite-isl-ast-to-gimple.c
===================================================================
--- gcc/graphite-isl-ast-to-gimple.c	(revision 212491)
+++ gcc/graphite-isl-ast-to-gimple.c	(working copy)
@@ -65,7 +65,9 @@
 /* We always use signed 128, until isl is able to give information about
 types  */
 
-static tree *graphite_expression_size_type = &int128_integer_type_node;
+static tree *graphite_expression_size_type = int128_integer_type_node ?
+					     &int128_integer_type_node :
+					     &long_long_integer_type_node;
 
 /* Converts a GMP constant VAL to a tree and returns it.  */
 

Re: [GSoC] generation of Gimple loops with empty bodies

[Dominique Dhumieres]

Hi Roman,

Thanks for the quick answer.

> Please report back if it fixes the problem.

I have not yet done a full regtest, but a manual testing suggest that
the patch fixes the problem.

Dominique

Re: [GSoC] generation of Gimple loops with empty bodies

[Dominique Dhumieres]

I have regtested graphite.exp for gcc/g++/gfortran/libgomp without
regression. So your patch seems a safe fix.

Dominique

Re: [GSoC] generation of Gimple loops with empty bodies

[Tobias Grosser]

On 13/07/2014 12:34, Roman Gareev wrote:
> Hi Dominique,
>
> thank you for the message! I've attached a patch, that may fix the issue.
>
> Please report back if it fixes the problem.

Roman, this patch is OK to commit, but please include a correct 
changelog file.

Tobias

Re: [GSoC] generation of Gimple loops with empty bodies

[Roman Gareev]

I've found out that int128_integer_type_node and
long_long_integer_type_node are NULL at the moment of definition of
the graphite_expression_size_type. Maybe we should use
long_long_integer_type_node, because, as you said before, using of
signed 64 has also been proved to be very robust. What do you think
about this?

--
                                   Cheers, Roman Gareev.

Re: [GSoC] generation of Gimple loops with empty bodies

[Roman Gareev]

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

> I suggest you use the largest available integer mode via
> mode = mode_for_size (MAX_FIXED_MODE_SIZE, MODE_INT, 0);
> type = build_nonstandard_integer_type (GET_MODE_PRECISION (mode), [01]);

Thank you for the suggestion!

> Roman, can you give this a shot?

Maybe, we could use the following code:

static int max_mode_int_precision =
  GET_MODE_PRECISION (mode_for_size (MAX_FIXED_MODE_SIZE, MODE_INT, 0));
static int graphite_expression_type_precision = 128 <= max_mode_int_precision ?

128 : max_mode_int_precision;

This allows us to change the size during debugging and avoid using
unacceptable mode size. Tobias, what do you think about this?

--
                                   Cheers, Roman Gareev

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

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

	gcc/
	* graphite-isl-ast-to-gimple.c:
	Add using of build_nonstandard_integer_type instead of
	int128_integer_type_node.

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

Index: gcc/graphite-isl-ast-to-gimple.c
===================================================================
--- gcc/graphite-isl-ast-to-gimple.c	(revision 212804)
+++ gcc/graphite-isl-ast-to-gimple.c	(working copy)
@@ -62,10 +62,13 @@
 
 static bool graphite_regenerate_error;
 
-/* We always use signed 128, until isl is able to give information about
-types  */
+/* We always use signed 128, until it is not accpeted or isl is able to give
+   information about types.  */
 
-static tree *graphite_expression_size_type = &int128_integer_type_node;
+static int max_mode_int_precision =
+  GET_MODE_PRECISION (mode_for_size (MAX_FIXED_MODE_SIZE, MODE_INT, 0));
+static int graphite_expression_type_precision = 128 <= max_mode_int_precision ?
+						128 : max_mode_int_precision;
 
 /* Converts a GMP constant VAL to a tree and returns it.  */
 
@@ -494,7 +497,8 @@
   tree cond_expr;
   edge exit_edge;
 
-  *type = *graphite_expression_size_type;
+  *type =
+    build_nonstandard_integer_type (graphite_expression_type_precision, 0);
   isl_ast_expr *for_init = isl_ast_node_for_get_init (node_for);
   *lb = gcc_expression_from_isl_expression (*type, for_init, ip);
   isl_ast_expr *upper_bound = get_upper_bound (node_for);

Re: [GSoC] generation of Gimple loops with empty bodies

[Tobias Grosser]

On 18/07/2014 12:34, Roman Gareev wrote:
>> I suggest you use the largest available integer mode via
>> >mode = mode_for_size (MAX_FIXED_MODE_SIZE, MODE_INT, 0);
>> >type = build_nonstandard_integer_type (GET_MODE_PRECISION (mode), [01]);
> Thank you for the suggestion!
>
>> >Roman, can you give this a shot?
> Maybe, we could use the following code:
>
> static int max_mode_int_precision =
>    GET_MODE_PRECISION (mode_for_size (MAX_FIXED_MODE_SIZE, MODE_INT, 0));
> static int graphite_expression_type_precision = 128 <= max_mode_int_precision ?
>
> 128 : max_mode_int_precision;
>
> This allows us to change the size during debugging and avoid using
> unacceptable mode size. Tobias, what do you think about this?

One comment is unclear. Otherwise it is good.

If my proposed comment is OK, please update, commit and close the bug 
report.

Tobias

> --
>                                     Cheers, Roman Gareev
>
>
> ChangeLog_entry.txt
>
>
> 2014-07-08  Roman Gareev<gareevroman@gmail.com>
>
> 	gcc/
> 	* graphite-isl-ast-to-gimple.c:
> 	Add using of build_nonstandard_integer_type instead of
> 	int128_integer_type_node.
>
>
> patch.txt
>
>
> Index: gcc/graphite-isl-ast-to-gimple.c
> ===================================================================
> --- gcc/graphite-isl-ast-to-gimple.c	(revision 212804)
> +++ gcc/graphite-isl-ast-to-gimple.c	(working copy)
> @@ -62,10 +62,13 @@
>
>   static bool graphite_regenerate_error;
>
> -/* We always use signed 128, until isl is able to give information about
> -types  */
> +/* We always use signed 128, until it is not accpeted or isl is able to give
> +   information about types.  */

This is not understandable.

What about;

/* We always try to use signed 128 bit types, but fall back to smaller 
types in case a platform does not provide types of this sizes. In the
future we should use isl to derive the optimal type for each 
subexpression. */

> -static tree *graphite_expression_size_type = &int128_integer_type_node;
> +static int max_mode_int_precision =
> +  GET_MODE_PRECISION (mode_for_size (MAX_FIXED_MODE_SIZE, MODE_INT, 0));
> +static int graphite_expression_type_precision = 128 <= max_mode_int_precision ?
> +						128 : max_mode_int_precision;
>
>   /* Converts a GMP constant VAL to a tree and returns it.  */
>
> @@ -494,7 +497,8 @@
>     tree cond_expr;
>     edge exit_edge;
>
> -  *type = *graphite_expression_size_type;
> +  *type =
> +    build_nonstandard_integer_type (graphite_expression_type_precision, 0);
>     isl_ast_expr *for_init = isl_ast_node_for_get_init (node_for);
>     *lb = gcc_expression_from_isl_expression (*type, for_init, ip);
>     isl_ast_expr *upper_bound = get_upper_bound (node_for);

Re: [GSoC] generation of Gimple loops with empty bodies

[Tobias Grosser]

On 11/07/2014 15:41, Roman Gareev wrote:
> I've attached an improved version of the patch and the ChangeLog
> entry. Are they fine for trunk?

LGTM.

Thank you!
Tobias

Re: [GSoC] generation of Gimple loops with empty bodies

[Roman Gareev]

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

I've attached an improved version of the patch and the ChangeLog
entry. Are they fine for trunk?

--
                                   Cheers, Roman Gareev.

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

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

	gcc/
	* graphite-isl-ast-to-gimple.c (gmp_cst_to_tree):
	New function.
	(graphite_verify): New function.
	(ivs_params_clear): New function.
	(gcc_expression_from_isl_ast_expr_id): New function.
	(gcc_expression_from_isl_expr_int): New function.
	(binary_op_to_tree): New function.
	(ternary_op_to_tree): New function.
	(unary_op_to_tree): New function.
	(nary_op_to_tree): New function.
	(gcc_expression_from_isl_expr_op): New function.
	(gcc_expression_from_isl_expression): New function.
	(graphite_create_new_loop): New function.
	(translate_isl_ast_for_loop): New function.
	(get_upper_bound): New function.
	(graphite_create_new_loop_guard): New function.
	(translate_isl_ast_node_for): New function.
	(translate_isl_ast): New function.
	(add_parameters_to_ivs_params): New function.
	(scop_to_isl_ast): New parameter ip.
	(graphite_regenerate_ast_isl): Add generation of GIMPLE code.

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

Index: gcc/graphite-isl-ast-to-gimple.c
===================================================================
--- gcc/graphite-isl-ast-to-gimple.c	(revision 212450)
+++ gcc/graphite-isl-ast-to-gimple.c	(working copy)
@@ -25,7 +25,14 @@
 #include <isl/map.h>
 #include <isl/union_map.h>
 #include <isl/ast_build.h>
+#if defined(__cplusplus)
+extern "C" {
 #endif
+#include <isl/val_gmp.h>
+#if defined(__cplusplus)
+}
+#endif
+#endif
 
 #include "system.h"
 #include "coretypes.h"
@@ -42,6 +49,9 @@
 #include "cfgloop.h"
 #include "tree-data-ref.h"
 #include "sese.h"
+#include "tree-ssa-loop-manip.h"
+#include "tree-scalar-evolution.h"
+#include <map>
 
 #ifdef HAVE_cloog
 #include "graphite-poly.h"
@@ -52,6 +62,515 @@
 
 static bool graphite_regenerate_error;
 
+/* We always use signed 128, until isl is able to give information about
+types  */
+
+static tree *graphite_expression_size_type = &int128_integer_type_node;
+
+/* Converts a GMP constant VAL to a tree and returns it.  */
+
+static tree
+gmp_cst_to_tree (tree type, mpz_t val)
+{
+  tree t = type ? type : integer_type_node;
+  mpz_t tmp;
+
+  mpz_init (tmp);
+  mpz_set (tmp, val);
+  wide_int wi = wi::from_mpz (t, tmp, true);
+  mpz_clear (tmp);
+
+  return wide_int_to_tree (t, wi);
+}
+
+/* Verifies properties that GRAPHITE should maintain during translation.  */
+
+static inline void
+graphite_verify (void)
+{
+#ifdef ENABLE_CHECKING
+  verify_loop_structure ();
+  verify_loop_closed_ssa (true);
+#endif
+}
+
+/* IVS_PARAMS maps ISL's scattering and parameter identifiers
+   to corresponding trees.  */
+
+typedef std::map<isl_id *, tree> ivs_params;
+
+/* Free all memory allocated for ISL's identifiers.  */
+
+void ivs_params_clear (ivs_params &ip)
+{
+  std::map<isl_id *, tree>::iterator it;
+  for (it = ip.begin ();
+       it != ip.end (); it++)
+    {
+      isl_id_free (it->first);
+    }
+}
+
+static tree
+gcc_expression_from_isl_expression (tree type, __isl_take isl_ast_expr *,
+				    ivs_params &ip);
+
+/* Return the tree variable that corresponds to the given isl ast identifier
+ expression (an isl_ast_expr of type isl_ast_expr_id).  */
+
+static tree
+gcc_expression_from_isl_ast_expr_id (__isl_keep isl_ast_expr *expr_id,
+				     ivs_params &ip)
+{
+  gcc_assert (isl_ast_expr_get_type (expr_id) == isl_ast_expr_id);
+  isl_id *tmp_isl_id = isl_ast_expr_get_id (expr_id);
+  std::map<isl_id *, tree>::iterator res;
+  res = ip.find (tmp_isl_id);
+  isl_id_free (tmp_isl_id);
+  gcc_assert (res != ip.end () &&
+              "Could not map isl_id to tree expression");
+  isl_ast_expr_free (expr_id);
+  return res->second;
+}
+
+/* Converts an isl_ast_expr_int expression E to a GCC expression tree of
+   type TYPE.  */
+
+static tree
+gcc_expression_from_isl_expr_int (tree type, __isl_take isl_ast_expr *expr)
+{
+  gcc_assert (isl_ast_expr_get_type (expr) == isl_ast_expr_int);
+  isl_val *val = isl_ast_expr_get_val (expr);
+  mpz_t val_mpz_t;
+  mpz_init (val_mpz_t);
+  tree res;
+  if (isl_val_get_num_gmp (val, val_mpz_t) == -1)
+    res = NULL_TREE;
+  else
+    res = gmp_cst_to_tree (type, val_mpz_t);
+  isl_val_free (val);
+  isl_ast_expr_free (expr);
+  mpz_clear (val_mpz_t);
+  return res;
+}
+
+/* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of
+   type TYPE.  */
+
+static tree
+binary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params &ip)
+{
+  isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
+  tree tree_lhs_expr = gcc_expression_from_isl_expression (type, arg_expr, ip);
+  arg_expr = isl_ast_expr_get_op_arg (expr, 1);
+  tree tree_rhs_expr = gcc_expression_from_isl_expression (type, arg_expr, ip);
+  enum isl_ast_op_type expr_type = isl_ast_expr_get_op_type (expr);
+  isl_ast_expr_free (expr);
+  switch (expr_type)
+    {
+    case isl_ast_op_add:
+      return fold_build2 (PLUS_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+    case isl_ast_op_sub:
+      return fold_build2 (MINUS_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+    case isl_ast_op_mul:
+      return fold_build2 (MULT_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+    case isl_ast_op_div:
+      return fold_build2 (EXACT_DIV_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+    case isl_ast_op_fdiv_q:
+      return fold_build2 (FLOOR_DIV_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+    case isl_ast_op_and:
+      return fold_build2 (TRUTH_ANDIF_EXPR, type,
+			  tree_lhs_expr, tree_rhs_expr);
+
+    case isl_ast_op_or:
+      return fold_build2 (TRUTH_ORIF_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+    case isl_ast_op_eq:
+      return fold_build2 (EQ_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+    case isl_ast_op_le:
+      return fold_build2 (LE_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+    case isl_ast_op_lt:
+      return fold_build2 (LT_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+    case isl_ast_op_ge:
+      return fold_build2 (GE_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+    case isl_ast_op_gt:
+      return fold_build2 (GT_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+    default:
+      gcc_unreachable ();
+    }
+}
+
+/* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of
+   type TYPE.  */
+
+static tree
+ternary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params &ip)
+{
+  gcc_assert (isl_ast_expr_get_op_type (expr) == isl_ast_op_minus);
+  isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
+  tree tree_first_expr
+    = gcc_expression_from_isl_expression (type, arg_expr, ip);
+  arg_expr = isl_ast_expr_get_op_arg (expr, 1);
+  tree tree_second_expr
+    = gcc_expression_from_isl_expression (type, arg_expr, ip);
+  arg_expr = isl_ast_expr_get_op_arg (expr, 2);
+  tree tree_third_expr
+    = gcc_expression_from_isl_expression (type, arg_expr, ip);
+  isl_ast_expr_free (expr);
+  return fold_build3 (COND_EXPR, type, tree_first_expr,
+		      tree_second_expr, tree_third_expr);
+}
+
+/* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
+   type TYPE.  */
+
+static tree
+unary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params &ip)
+{
+  gcc_assert (isl_ast_expr_get_op_type (expr) == isl_ast_op_minus);
+  isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
+  tree tree_expr = gcc_expression_from_isl_expression (type, arg_expr, ip);
+  isl_ast_expr_free (expr);
+  return fold_build1 (NEGATE_EXPR, type, tree_expr);
+}
+
+/* Converts an isl_ast_expr_op expression E with unknown number of arguments
+   to a GCC expression tree of type TYPE.  */
+
+static tree
+nary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params &ip)
+{
+  enum tree_code op_code;
+  switch (isl_ast_expr_get_op_type (expr))
+    {
+    case isl_ast_op_max:
+      op_code = MAX_EXPR;
+      break;
+
+    case isl_ast_op_min:
+      op_code = MIN_EXPR;
+      break;
+
+    default:
+      gcc_unreachable ();    
+    }
+  isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
+  tree res = gcc_expression_from_isl_expression (type, arg_expr, ip);
+  int i;
+  for (i = 1; i < isl_ast_expr_get_op_n_arg (expr); i++)
+    {
+      arg_expr = isl_ast_expr_get_op_arg (expr, i);
+      tree t = gcc_expression_from_isl_expression (type, arg_expr, ip);
+      res = fold_build2 (op_code, type, res, t);
+    }
+  isl_ast_expr_free (expr);
+  return res;
+}
+
+
+/* Converts an isl_ast_expr_op expression E to a GCC expression tree of
+   type TYPE.  */
+
+static tree
+gcc_expression_from_isl_expr_op (tree type, __isl_take isl_ast_expr *expr,
+				 ivs_params &ip)
+{
+  gcc_assert (isl_ast_expr_get_type (expr) == isl_ast_expr_op);
+  switch (isl_ast_expr_get_op_type (expr))
+    {
+    /* These isl ast expressions are not supported yet.  */
+    case isl_ast_op_error:
+    case isl_ast_op_call:
+    case isl_ast_op_and_then:
+    case isl_ast_op_or_else:
+    case isl_ast_op_pdiv_q:
+    case isl_ast_op_pdiv_r:
+    case isl_ast_op_select:
+      gcc_unreachable ();
+
+    case isl_ast_op_max:
+    case isl_ast_op_min:
+      return nary_op_to_tree (type, expr, ip);
+
+    case isl_ast_op_add:
+    case isl_ast_op_sub:
+    case isl_ast_op_mul:
+    case isl_ast_op_div:
+    case isl_ast_op_fdiv_q:
+    case isl_ast_op_and:
+    case isl_ast_op_or:
+    case isl_ast_op_eq:
+    case isl_ast_op_le:
+    case isl_ast_op_lt:
+    case isl_ast_op_ge:
+    case isl_ast_op_gt:
+      return binary_op_to_tree (type, expr, ip);
+
+    case isl_ast_op_minus:
+      return unary_op_to_tree (type, expr, ip);
+
+    case isl_ast_op_cond:
+      return ternary_op_to_tree (type, expr, ip);
+
+    default:
+      gcc_unreachable ();
+    }
+
+  return NULL_TREE;
+}
+
+/* Converts an ISL AST expression E back to a GCC expression tree of
+   type TYPE.  */
+
+static tree
+gcc_expression_from_isl_expression (tree type, __isl_take isl_ast_expr *expr,
+				    ivs_params &ip)
+{
+  switch (isl_ast_expr_get_type (expr))
+    {
+    case isl_ast_expr_id:
+      return gcc_expression_from_isl_ast_expr_id (expr, ip);
+
+    case isl_ast_expr_int:
+      return gcc_expression_from_isl_expr_int (type, expr);
+
+    case isl_ast_expr_op:
+      return gcc_expression_from_isl_expr_op (type, expr, ip);
+
+    default:
+      gcc_unreachable ();
+    }
+
+  return NULL_TREE;
+}
+
+/* Creates a new LOOP corresponding to isl_ast_node_for.  Inserts an
+   induction variable for the new LOOP.  New LOOP is attached to CFG
+   starting at ENTRY_EDGE.  LOOP is inserted into the loop tree and
+   becomes the child loop of the OUTER_LOOP.  NEWIVS_INDEX binds
+   ISL's scattering name to the induction variable created for the
+   loop of STMT.  The new induction variable is inserted in the NEWIVS
+   vector and is of type TYPE.  */
+
+static struct loop *
+graphite_create_new_loop (edge entry_edge, __isl_keep isl_ast_node *node_for,
+			  loop_p outer, tree type, tree lb, tree ub,
+			  ivs_params &ip)
+{
+  isl_ast_expr *for_inc = isl_ast_node_for_get_inc (node_for);
+  tree stride = gcc_expression_from_isl_expression (type, for_inc, ip);
+  tree ivvar = create_tmp_var (type, "graphite_IV");
+  tree iv, iv_after_increment;
+  loop_p loop = create_empty_loop_on_edge
+    (entry_edge, lb, stride, ub, ivvar, &iv, &iv_after_increment,
+     outer ? outer : entry_edge->src->loop_father);
+
+  isl_ast_expr *for_iterator = isl_ast_node_for_get_iterator (node_for);
+  isl_id *id = isl_ast_expr_get_id (for_iterator);
+  ip[id] = iv;
+  isl_ast_expr_free (for_iterator);
+  return loop;
+}
+
+static edge
+translate_isl_ast (loop_p context_loop, __isl_keep isl_ast_node *node,
+		   edge next_e, ivs_params &ip);
+
+/* Create the loop for a isl_ast_node_for.
+
+   - NEXT_E is the edge where new generated code should be attached.  */
+
+static edge
+translate_isl_ast_for_loop (loop_p context_loop,
+			    __isl_keep isl_ast_node *node_for, edge next_e,
+			    tree type, tree lb, tree ub,
+			    ivs_params &ip)
+{
+  gcc_assert (isl_ast_node_get_type (node_for) == isl_ast_node_for);
+  struct loop *loop = graphite_create_new_loop (next_e, node_for, context_loop,
+						type, lb, ub, ip);
+  edge last_e = single_exit (loop);
+  edge to_body = single_succ_edge (loop->header);
+  basic_block after = to_body->dest;
+
+  /* Create a basic block for loop close phi nodes.  */
+  last_e = single_succ_edge (split_edge (last_e));
+
+  /* Translate the body of the loop.  */
+  isl_ast_node *for_body = isl_ast_node_for_get_body (node_for);
+  next_e = translate_isl_ast (loop, for_body, to_body, ip);
+  isl_ast_node_free (for_body);
+  redirect_edge_succ_nodup (next_e, after);
+  set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src);
+
+  /* TODO: Add checking for the loop parallelism.  */
+
+  return last_e;
+}
+
+/* We use this function to get the upper bound because of the form,
+   which is used by isl to represent loops:
+
+   for (iterator = init; cond; iterator += inc)
+
+   {
+
+     ...
+
+   }
+
+   The loop condition is an arbitrary expression, which contains the
+   current loop iterator.
+
+   (e.g. iterator + 3 < B && C > iterator + A)
+
+   We have to know the upper bound of the iterator to generate a loop
+   in Gimple form. It can be obtained from the special representation
+   of the loop condition, which is generated by isl,
+   if the ast_build_atomic_upper_bound option is set. In this case,
+   isl generates a loop condition that consists of the current loop
+   iterator, + an operator (< or <=) and an expression not involving
+   the iterator, which is processed and returned by this function.
+
+   (e.g iterator <= upper-bound-expression-without-iterator)  */
+
+static __isl_give isl_ast_expr *
+get_upper_bound (__isl_keep isl_ast_node *node_for)
+{
+  gcc_assert (isl_ast_node_get_type (node_for) == isl_ast_node_for);
+  isl_ast_expr *for_cond = isl_ast_node_for_get_cond (node_for);
+  gcc_assert (isl_ast_expr_get_type (for_cond) == isl_ast_expr_op);
+  isl_ast_expr *res;
+  switch (isl_ast_expr_get_op_type (for_cond))
+    {
+    case isl_ast_op_le:
+      res = isl_ast_expr_get_op_arg (for_cond, 1);
+      break;
+
+    case isl_ast_op_lt:
+      {
+        // (iterator < ub) => (iterator <= ub - 1)
+        isl_val *one = isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond), 1);
+        isl_ast_expr *ub = isl_ast_expr_get_op_arg (for_cond, 1);
+        res = isl_ast_expr_sub (ub, isl_ast_expr_from_val (one));
+        break;
+      }
+
+    default:
+      gcc_unreachable ();
+    }
+  isl_ast_expr_free (for_cond);
+  return res;
+}
+
+/* All loops generated by create_empty_loop_on_edge have the form of
+   a post-test loop:
+
+   do
+
+   {
+     body of the loop;
+   } while (lower bound < upper bound);
+
+   We create a new if region protecting the loop to be executed, if
+   the execution count is zero (lower bound > upper bound).  */
+
+static edge
+graphite_create_new_loop_guard (edge entry_edge,
+				__isl_keep isl_ast_node *node_for, tree *type,
+				tree *lb, tree *ub, ivs_params &ip)
+{
+  gcc_assert (isl_ast_node_get_type (node_for) == isl_ast_node_for);
+  tree cond_expr;
+  edge exit_edge;
+
+  *type = *graphite_expression_size_type;
+  isl_ast_expr *for_init = isl_ast_node_for_get_init (node_for);
+  *lb = gcc_expression_from_isl_expression (*type, for_init, ip);
+  isl_ast_expr *upper_bound = get_upper_bound (node_for);
+  *ub = gcc_expression_from_isl_expression (*type, upper_bound, ip);
+  
+  /* When ub is simply a constant or a parameter, use lb <= ub.  */
+  if (TREE_CODE (*ub) == INTEGER_CST || TREE_CODE (*ub) == SSA_NAME)
+    cond_expr = fold_build2 (LE_EXPR, boolean_type_node, *lb, *ub);
+  else
+    {
+      tree one = (POINTER_TYPE_P (*type)
+		  ? convert_to_ptrofftype (integer_one_node)
+		  : fold_convert (*type, integer_one_node));
+      /* Adding +1 and using LT_EXPR helps with loop latches that have a
+	 loop iteration count of "PARAMETER - 1".  For PARAMETER == 0 this
+	 becomes 2^k-1 due to integer overflow, and the condition lb <= ub
+	 is true, even if we do not want this.  However lb < ub + 1 is false,
+	 as expected.  */
+      tree ub_one = fold_build2 (POINTER_TYPE_P (*type) ? POINTER_PLUS_EXPR
+				 : PLUS_EXPR, *type, *ub, one);
+
+      cond_expr = fold_build2 (LT_EXPR, boolean_type_node, *lb, ub_one);
+    }
+
+  exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
+
+  return exit_edge;
+}
+
+/* Translates an isl_ast_node_for to Gimple. */
+
+static edge
+translate_isl_ast_node_for (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_for);
+  tree type, lb, ub;
+  edge last_e = graphite_create_new_loop_guard (next_e, node, &type,
+						&lb, &ub, ip);
+  edge true_e = get_true_edge_from_guard_bb (next_e->dest);
+
+  translate_isl_ast_for_loop (context_loop, node, true_e,
+			      type, lb, ub, ip);
+  return last_e;
+}
+
+/* Translates an ISL AST node NODE to GCC representation in the
+   context of a SESE.  */
+
+static edge
+translate_isl_ast (loop_p context_loop, __isl_keep isl_ast_node *node,
+		   edge next_e, ivs_params &ip)
+{
+  switch (isl_ast_node_get_type (node))
+    {
+    case isl_ast_node_error:
+      gcc_unreachable ();
+
+    case isl_ast_node_for:
+      return translate_isl_ast_node_for (context_loop, node,
+					 next_e, ip);
+
+    case isl_ast_node_if:
+      return next_e;
+
+    case isl_ast_node_user:
+      return next_e;
+
+    case isl_ast_node_block:
+      return next_e;
+
+    default:
+      gcc_unreachable ();
+    }
+}
+
 /* Prints NODE to FILE.  */
 
 void
@@ -65,6 +584,23 @@
   isl_printer_free (prn);
 }
 
+/* Add ISL's parameter identifiers and corresponding.trees to ivs_params  */
+
+static void
+add_parameters_to_ivs_params (scop_p scop, ivs_params &ip)
+{
+  sese region = SCOP_REGION (scop);
+  unsigned nb_parameters = isl_set_dim (scop->context, isl_dim_param);
+  gcc_assert (nb_parameters == SESE_PARAMS (region).length ());
+  unsigned i;
+  for (i = 0; i < nb_parameters; i++)
+    {
+      isl_id *tmp_id = isl_set_get_dim_id (scop->context, isl_dim_param, i);
+      ip[tmp_id] = SESE_PARAMS (region)[i];
+    }
+}
+
+
 /* Generates a build, which specifies the constraints on the parameters.  */
 
 static __isl_give isl_ast_build *
@@ -103,8 +639,15 @@
 }
 
 static __isl_give isl_ast_node *
-scop_to_isl_ast (scop_p scop)
+scop_to_isl_ast (scop_p scop, ivs_params &ip)
 {
+  /* Generate loop upper bounds that consist of the current loop iterator,
+  an operator (< or <=) and an expression not involving the iterator.
+  If this option is not set, then the current loop iterator may appear several
+  times in the upper bound. See the isl manual for more details.  */
+  isl_options_set_ast_build_atomic_upper_bound (scop->ctx, true);
+
+  add_parameters_to_ivs_params (scop, ip);
   isl_union_map *schedule_isl = generate_isl_schedule (scop);
   isl_ast_build *context_isl = generate_isl_context (scop);
   isl_ast_node *ast_isl = isl_ast_build_ast_from_schedule (context_isl,
@@ -117,21 +660,59 @@
    the given SCOP.  Return true if code generation succeeded.
 
    FIXME: This is not yet a full implementation of the code generator
-          with ISL ASTs. Generation of GIMPLE code is have to be added.  */
+          with ISL ASTs. Generation of GIMPLE code has to be completed.  */
 
 bool
 graphite_regenerate_ast_isl (scop_p scop)
 {
+  loop_p context_loop;
+  sese region = SCOP_REGION (scop);
+  ifsese if_region = NULL;
+  isl_ast_node *root_node;
+  ivs_params ip;
+
   timevar_push (TV_GRAPHITE_CODE_GEN);
   graphite_regenerate_error = false;
-  isl_ast_node *root_node = scop_to_isl_ast (scop);
+  root_node = scop_to_isl_ast (scop, ip);
+
   if (dump_file && (dump_flags & TDF_DETAILS))
     {
       fprintf (dump_file, "\nISL AST generated by ISL: \n");
       print_isl_ast_node (dump_file, root_node, scop->ctx);
+      fprintf (dump_file, "\n");
     }
+
+  recompute_all_dominators ();
+  graphite_verify ();
+
+  if_region = move_sese_in_condition (region);
+  sese_insert_phis_for_liveouts (region,
+				 if_region->region->exit->src,
+				 if_region->false_region->exit,
+				 if_region->true_region->exit);
+  recompute_all_dominators ();
+  graphite_verify ();
+
+  context_loop = SESE_ENTRY (region)->src->loop_father;
+
+  translate_isl_ast (context_loop, root_node, if_region->true_region->entry,
+		     ip);
+  graphite_verify ();
+  scev_reset ();
+  recompute_all_dominators ();
+  graphite_verify ();
+
+  if (graphite_regenerate_error)
+    set_ifsese_condition (if_region, integer_zero_node);
+
+  free (if_region->true_region);
+  free (if_region->region);
+  free (if_region);
+
+  ivs_params_clear (ip);
   isl_ast_node_free (root_node);
   timevar_pop (TV_GRAPHITE_CODE_GEN);
+  /* TODO: Add dump  */
   return !graphite_regenerate_error;
 }
 #endif

Re: [GSoC] generation of Gimple loops with empty bodies

[Tobias Grosser]

On 11/07/2014 13:11, Roman Gareev wrote:
>> The struct now contains only a single element such that there seems to be no
>> need for it anymore. Should we remove it? (We could still use a typedef if
>> you believe the datatype is too long).
>
> I don't mind removing it. However I think that we should choose the
> way of transferring of sese region, which is used for translation of
> an isl_ast_node_user to Gimple code. Should we transfer it separately
> or restore ivs_params later? What do you think?

Sorry, I currently don't see why sese region is needed later. In case it
is, we may keep it, but this would require to pull more code in the 
review. I personally would just remove it to finish this review.

Feel free to commit after applying this change.

Cheers,
Tobias

Re: [GSoC] generation of Gimple loops with empty bodies

[Roman Gareev]

> The struct now contains only a single element such that there seems to be no
> need for it anymore. Should we remove it? (We could still use a typedef if
> you believe the datatype is too long).

I don't mind removing it. However I think that we should choose the
way of transferring of sese region, which is used for translation of
an isl_ast_node_user to Gimple code. Should we transfer it separately
or restore ivs_params later? What do you think?

--
                                   Cheers, Roman Gareev.

Re: [GSoC] generation of Gimple loops with empty bodies

[Tobias Grosser]

> I tried to incorporate all your comments in the attached patch.

Nice. It looks now very good to me. One final and last detail:


+/* TREE_FROM_ISL_ID maps ISL's scattering and parameter identifiers
+   to corresponding trees.  */
+
+typedef struct ivs_params {
+  std::map<isl_id *, tree> tree_from_isl_id;
+} *ivs_params_p;

The struct now contains only a single element such that there seems to 
be no need for it anymore. Should we remove it? (We could still use a 
typedef if you believe the datatype is too long).

Cheers,
Tobias

Re: [GSoC] generation of Gimple loops with empty bodies

[Roman Gareev]

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

> I would use -x to see the headers. This should tell you if it is defined
> or only used there.

It gives the following output:

roman@roman-System-Product-Name:~/isl-0.12.2/lib$ objdump -x
libisl.so.10.2.2 | grep isl_ast_expr_get_val
0000000000060380 g     F .text 0000000000000053
isl_ast_expr_get_val

> Sorry, but this still needs to be debugged. :-( I am too busy to do it
> myself, so i am afraid you may just need to dig into it yourself. :-(

I've found the reason of this error. Somehow cc1 used an older version
of isl provided by the package from the standard repository in spite
of manually selected paths to isl 0.12.2. I think it is better to move
on and not to concentrate on this.

>> +#include "graphite-htab.h"
>
> Is this still needed?

No, this is redundant.

>> +/* IVS_PARAMS_MAP maps ISL's scattering and parameter identifiers
>> +   to corresponding trees.  */
>> +typedef struct ivs_params {
>> +  std::map<isl_id *, tree, id_comp> ivs_params_map;
>
> What about calling it isl_id_to_tree?

Maybe it would be better to call it tree_from_isl_id (because it would
help to avoid confusion with definitions from isl)?

>> +  sese region;
>
> Is this region needed?

No, this is redundant.

>> +   We create a new if region protecting the loop to be executed, if
>> +   the execution count is zero (lower bound > upper bound). In this case,
>> +   it is subsequently removed by dead code elimination.  */
>
>
> The last sentence is unclear. Are you saying the loop will be removed or
> that the condition will be removed in case it is always true. Also, what
> about cases where the condition remains?

I wanted to say that the loop will be removed. Maybe it would be
better to remove the last sentence at all (because the previous
sentence already explains the motivation)?

> Those changes are unrelated and are part of the other patch, right?

Yes, these changes were made in the revision under No. 212361.

>> +  ip.region = region;
>
> Is this needed? ip.region seems unused.

Yes, this is redundant.


I tried to incorporate all your comments in the attached patch.

--
                                   Cheers, Roman Gareev.

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

Index: gcc/graphite-isl-ast-to-gimple.c
===================================================================
--- gcc/graphite-isl-ast-to-gimple.c	(revision 212361)
+++ gcc/graphite-isl-ast-to-gimple.c	(working copy)
@@ -25,7 +25,14 @@
 #include <isl/map.h>
 #include <isl/union_map.h>
 #include <isl/ast_build.h>
+#if defined(__cplusplus)
+extern "C" {
 #endif
+#include <isl/val_gmp.h>
+#if defined(__cplusplus)
+}
+#endif
+#endif
 
 #include "system.h"
 #include "coretypes.h"
@@ -42,6 +49,9 @@
 #include "cfgloop.h"
 #include "tree-data-ref.h"
 #include "sese.h"
+#include "tree-ssa-loop-manip.h"
+#include "tree-scalar-evolution.h"
+#include <map>
 
 #ifdef HAVE_cloog
 #include "graphite-poly.h"
@@ -52,6 +62,517 @@
 
 static bool graphite_regenerate_error;
 
+/* We always use signed 128, until isl is able to give information about
+types  */
+
+static tree *graphite_expression_size_type = &int128_integer_type_node;
+
+/* Converts a GMP constant VAL to a tree and returns it.  */
+
+static tree
+gmp_cst_to_tree (tree type, mpz_t val)
+{
+  tree t = type ? type : integer_type_node;
+  mpz_t tmp;
+
+  mpz_init (tmp);
+  mpz_set (tmp, val);
+  wide_int wi = wi::from_mpz (t, tmp, true);
+  mpz_clear (tmp);
+
+  return wide_int_to_tree (t, wi);
+}
+
+/* Verifies properties that GRAPHITE should maintain during translation.  */
+
+static inline void
+graphite_verify (void)
+{
+#ifdef ENABLE_CHECKING
+  verify_loop_structure ();
+  verify_loop_closed_ssa (true);
+#endif
+}
+
+/* TREE_FROM_ISL_ID maps ISL's scattering and parameter identifiers
+   to corresponding trees.  */
+
+typedef struct ivs_params {
+  std::map<isl_id *, tree> tree_from_isl_id;
+} *ivs_params_p;
+
+/* Free all memory allocated for ISL's identifiers.  */
+
+void ivs_params_clear (ivs_params_p ip)
+{
+  std::map<isl_id *, tree>::iterator it;
+  for (it = ip->tree_from_isl_id.begin ();
+       it != ip->tree_from_isl_id.end (); it++)
+    {
+      isl_id_free (it->first);
+    }
+}
+
+static tree
+gcc_expression_from_isl_expression (tree type, __isl_take isl_ast_expr *,
+				    ivs_params_p ip);
+
+/* Return the tree variable that corresponds to the given isl ast identifier
+ expression (an isl_ast_expr of type isl_ast_expr_id).  */
+
+static tree
+gcc_expression_from_isl_ast_expr_id (__isl_keep isl_ast_expr *expr_id,
+				     ivs_params_p ip)
+{
+  gcc_assert (isl_ast_expr_get_type (expr_id) == isl_ast_expr_id);
+  isl_id *tmp_isl_id = isl_ast_expr_get_id (expr_id);
+  std::map<isl_id *, tree>::iterator res;
+  res = ip->tree_from_isl_id.find (tmp_isl_id);
+  isl_id_free (tmp_isl_id);
+  gcc_assert (res != ip->tree_from_isl_id.end () &&
+              "Could not map isl_id to tree expression");
+  isl_ast_expr_free (expr_id);
+  return res->second;
+}
+
+/* Converts an isl_ast_expr_int expression E to a GCC expression tree of
+   type TYPE.  */
+
+static tree
+gcc_expression_from_isl_expr_int (tree type, __isl_take isl_ast_expr *expr)
+{
+  gcc_assert (isl_ast_expr_get_type (expr) == isl_ast_expr_int);
+  isl_val *val = isl_ast_expr_get_val (expr);
+  mpz_t val_mpz_t;
+  mpz_init (val_mpz_t);
+  tree res;
+  if (isl_val_get_num_gmp (val, val_mpz_t) == -1)
+    res = NULL_TREE;
+  else
+    res = gmp_cst_to_tree (type, val_mpz_t);
+  isl_val_free (val);
+  isl_ast_expr_free (expr);
+  mpz_clear (val_mpz_t);
+  return res;
+}
+
+/* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of
+   type TYPE.  */
+
+static tree
+binary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params_p ip)
+{
+  isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
+  tree tree_lhs_expr = gcc_expression_from_isl_expression (type, arg_expr, ip);
+  arg_expr = isl_ast_expr_get_op_arg (expr, 1);
+  tree tree_rhs_expr = gcc_expression_from_isl_expression (type, arg_expr, ip);
+  enum isl_ast_op_type expr_type = isl_ast_expr_get_op_type (expr);
+  isl_ast_expr_free (expr);
+  switch (expr_type)
+    {
+    case isl_ast_op_add:
+      return fold_build2 (PLUS_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+    case isl_ast_op_sub:
+      return fold_build2 (MINUS_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+    case isl_ast_op_mul:
+      return fold_build2 (MULT_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+    case isl_ast_op_div:
+      return fold_build2 (EXACT_DIV_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+    case isl_ast_op_fdiv_q:
+      return fold_build2 (FLOOR_DIV_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+    case isl_ast_op_and:
+      return fold_build2 (TRUTH_ANDIF_EXPR, type,
+			  tree_lhs_expr, tree_rhs_expr);
+
+    case isl_ast_op_or:
+      return fold_build2 (TRUTH_ORIF_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+    case isl_ast_op_eq:
+      return fold_build2 (EQ_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+    case isl_ast_op_le:
+      return fold_build2 (LE_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+    case isl_ast_op_lt:
+      return fold_build2 (LT_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+    case isl_ast_op_ge:
+      return fold_build2 (GE_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+    case isl_ast_op_gt:
+      return fold_build2 (GT_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+    default:
+      gcc_unreachable ();
+    }
+}
+
+/* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of
+   type TYPE.  */
+
+static tree
+ternary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params_p ip)
+{
+  gcc_assert (isl_ast_expr_get_op_type (expr) == isl_ast_op_minus);
+  isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
+  tree tree_first_expr
+    = gcc_expression_from_isl_expression (type, arg_expr, ip);
+  arg_expr = isl_ast_expr_get_op_arg (expr, 1);
+  tree tree_second_expr
+    = gcc_expression_from_isl_expression (type, arg_expr, ip);
+  arg_expr = isl_ast_expr_get_op_arg (expr, 2);
+  tree tree_third_expr
+    = gcc_expression_from_isl_expression (type, arg_expr, ip);
+  isl_ast_expr_free (expr);
+  return fold_build3 (COND_EXPR, type, tree_first_expr,
+		      tree_second_expr, tree_third_expr);
+}
+
+/* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
+   type TYPE.  */
+
+static tree
+unary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params_p ip)
+{
+  gcc_assert (isl_ast_expr_get_op_type (expr) == isl_ast_op_minus);
+  isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
+  tree tree_expr = gcc_expression_from_isl_expression (type, arg_expr, ip);
+  isl_ast_expr_free (expr);
+  return fold_build1 (NEGATE_EXPR, type, tree_expr);
+}
+
+/* Converts an isl_ast_expr_op expression E with unknown number of arguments
+   to a GCC expression tree of type TYPE.  */
+
+static tree
+nary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params_p ip)
+{
+  enum tree_code op_code;
+  switch (isl_ast_expr_get_op_type (expr))
+    {
+    case isl_ast_op_max:
+      op_code = MAX_EXPR;
+      break;
+
+    case isl_ast_op_min:
+      op_code = MIN_EXPR;
+      break;
+
+    default:
+      gcc_unreachable ();    
+    }
+  isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
+  tree res = gcc_expression_from_isl_expression (type, arg_expr, ip);
+  int i;
+  for (i = 1; i < isl_ast_expr_get_op_n_arg (expr); i++)
+    {
+      arg_expr = isl_ast_expr_get_op_arg (expr, i);
+      tree t = gcc_expression_from_isl_expression (type, arg_expr, ip);
+      res = fold_build2 (op_code, type, res, t);
+    }
+  isl_ast_expr_free (expr);
+  return res;
+}
+
+
+/* Converts an isl_ast_expr_op expression E to a GCC expression tree of
+   type TYPE.  */
+
+static tree
+gcc_expression_from_isl_expr_op (tree type, __isl_take isl_ast_expr *expr,
+				 ivs_params_p ip)
+{
+  gcc_assert (isl_ast_expr_get_type (expr) == isl_ast_expr_op);
+  switch (isl_ast_expr_get_op_type (expr))
+    {
+    /* These isl ast expressions are not supported yet.  */
+    case isl_ast_op_error:
+    case isl_ast_op_call:
+    case isl_ast_op_and_then:
+    case isl_ast_op_or_else:
+    case isl_ast_op_pdiv_q:
+    case isl_ast_op_pdiv_r:
+    case isl_ast_op_select:
+      gcc_unreachable ();
+
+    case isl_ast_op_max:
+    case isl_ast_op_min:
+      return nary_op_to_tree (type, expr, ip);
+
+    case isl_ast_op_add:
+    case isl_ast_op_sub:
+    case isl_ast_op_mul:
+    case isl_ast_op_div:
+    case isl_ast_op_fdiv_q:
+    case isl_ast_op_and:
+    case isl_ast_op_or:
+    case isl_ast_op_eq:
+    case isl_ast_op_le:
+    case isl_ast_op_lt:
+    case isl_ast_op_ge:
+    case isl_ast_op_gt:
+      return binary_op_to_tree (type, expr, ip);
+
+    case isl_ast_op_minus:
+      return unary_op_to_tree (type, expr, ip);
+
+    case isl_ast_op_cond:
+      return ternary_op_to_tree (type, expr, ip);
+
+    default:
+      gcc_unreachable ();
+    }
+
+  return NULL_TREE;
+}
+
+/* Converts an ISL AST expression E back to a GCC expression tree of
+   type TYPE.  */
+
+static tree
+gcc_expression_from_isl_expression (tree type, __isl_take isl_ast_expr *expr,
+				    ivs_params_p ip)
+{
+  switch (isl_ast_expr_get_type (expr))
+    {
+    case isl_ast_expr_id:
+      return gcc_expression_from_isl_ast_expr_id (expr, ip);
+
+    case isl_ast_expr_int:
+      return gcc_expression_from_isl_expr_int (type, expr);
+
+    case isl_ast_expr_op:
+      return gcc_expression_from_isl_expr_op (type, expr, ip);
+
+    default:
+      gcc_unreachable ();
+    }
+
+  return NULL_TREE;
+}
+
+/* Creates a new LOOP corresponding to isl_ast_node_for.  Inserts an
+   induction variable for the new LOOP.  New LOOP is attached to CFG
+   starting at ENTRY_EDGE.  LOOP is inserted into the loop tree and
+   becomes the child loop of the OUTER_LOOP.  NEWIVS_INDEX binds
+   ISL's scattering name to the induction variable created for the
+   loop of STMT.  The new induction variable is inserted in the NEWIVS
+   vector and is of type TYPE.  */
+
+static struct loop *
+graphite_create_new_loop (edge entry_edge, __isl_keep isl_ast_node *node_for,
+			  loop_p outer, tree type, tree lb, tree ub,
+			  ivs_params_p ip)
+{
+  isl_ast_expr *for_inc = isl_ast_node_for_get_inc (node_for);
+  tree stride = gcc_expression_from_isl_expression (type, for_inc, ip);
+  tree ivvar = create_tmp_var (type, "graphite_IV");
+  tree iv, iv_after_increment;
+  loop_p loop = create_empty_loop_on_edge
+    (entry_edge, lb, stride, ub, ivvar, &iv, &iv_after_increment,
+     outer ? outer : entry_edge->src->loop_father);
+
+  isl_ast_expr *for_iterator = isl_ast_node_for_get_iterator (node_for);
+  isl_id *id = isl_ast_expr_get_id (for_iterator);
+  ip->tree_from_isl_id[id] = iv;
+  isl_ast_expr_free (for_iterator);
+  return loop;
+}
+
+static edge
+translate_isl_ast (loop_p context_loop, __isl_keep isl_ast_node *node,
+		   edge next_e, ivs_params_p ip);
+
+/* Create the loop for a isl_ast_node_for.
+
+   - NEXT_E is the edge where new generated code should be attached.  */
+
+static edge
+translate_isl_ast_for_loop (loop_p context_loop,
+			    __isl_keep isl_ast_node *node_for, edge next_e,
+			    tree type, tree lb, tree ub,
+			    ivs_params_p ip)
+{
+  gcc_assert (isl_ast_node_get_type (node_for) == isl_ast_node_for);
+  struct loop *loop = graphite_create_new_loop (next_e, node_for, context_loop,
+						type, lb, ub, ip);
+  edge last_e = single_exit (loop);
+  edge to_body = single_succ_edge (loop->header);
+  basic_block after = to_body->dest;
+
+  /* Create a basic block for loop close phi nodes.  */
+  last_e = single_succ_edge (split_edge (last_e));
+
+  /* Translate the body of the loop.  */
+  isl_ast_node *for_body = isl_ast_node_for_get_body (node_for);
+  next_e = translate_isl_ast (loop, for_body, to_body, ip);
+  isl_ast_node_free (for_body);
+  redirect_edge_succ_nodup (next_e, after);
+  set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src);
+
+  /* TODO: Add checking for the loop parallelism.  */
+
+  return last_e;
+}
+
+/* We use this function to get the upper bound because of the form,
+   which is used by isl to represent loops:
+
+   for (iterator = init; cond; iterator += inc)
+
+   {
+
+     ...
+
+   }
+
+   The loop condition is an arbitrary expression, which contains the
+   current loop iterator.
+
+   (e.g. iterator + 3 < B && C > iterator + A)
+
+   We have to know the upper bound of the iterator to generate a loop
+   in Gimple form. It can be obtained from the special representation
+   of the loop condition, which is generated by isl,
+   if the ast_build_atomic_upper_bound option is set. In this case,
+   isl generates a loop condition that consists of the current loop
+   iterator, + an operator (< or <=) and an expression not involving
+   the iterator, which is processed and returned by this function.
+
+   (e.g iterator <= upper-bound-expression-without-iterator)  */
+
+static __isl_give isl_ast_expr *
+get_upper_bound (__isl_keep isl_ast_node *node_for)
+{
+  gcc_assert (isl_ast_node_get_type (node_for) == isl_ast_node_for);
+  isl_ast_expr *for_cond = isl_ast_node_for_get_cond (node_for);
+  gcc_assert (isl_ast_expr_get_type (for_cond) == isl_ast_expr_op);
+  isl_ast_expr *res;
+  switch (isl_ast_expr_get_op_type (for_cond))
+    {
+    case isl_ast_op_le:
+      res = isl_ast_expr_get_op_arg (for_cond, 1);
+      break;
+
+    case isl_ast_op_lt:
+      {
+        // (iterator < ub) => (iterator <= ub - 1)
+        isl_val *one = isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond), 1);
+        isl_ast_expr *ub = isl_ast_expr_get_op_arg (for_cond, 1);
+        res = isl_ast_expr_sub (ub, isl_ast_expr_from_val (one));
+        break;
+      }
+
+    default:
+      gcc_unreachable ();
+    }
+  isl_ast_expr_free (for_cond);
+  return res;
+}
+
+/* All loops generated by create_empty_loop_on_edge have the form of
+   a post-test loop:
+
+   do
+
+   {
+     body of the loop;
+   } while (lower bound < upper bound);
+
+   We create a new if region protecting the loop to be executed, if
+   the execution count is zero (lower bound > upper bound).  */
+
+static edge
+graphite_create_new_loop_guard (edge entry_edge,
+				__isl_keep isl_ast_node *node_for, tree *type,
+				tree *lb, tree *ub, ivs_params_p ip)
+{
+  gcc_assert (isl_ast_node_get_type (node_for) == isl_ast_node_for);
+  tree cond_expr;
+  edge exit_edge;
+
+  *type = *graphite_expression_size_type;
+  isl_ast_expr *for_init = isl_ast_node_for_get_init (node_for);
+  *lb = gcc_expression_from_isl_expression (*type, for_init, ip);
+  isl_ast_expr *upper_bound = get_upper_bound (node_for);
+  *ub = gcc_expression_from_isl_expression (*type, upper_bound, ip);
+  
+  /* When ub is simply a constant or a parameter, use lb <= ub.  */
+  if (TREE_CODE (*ub) == INTEGER_CST || TREE_CODE (*ub) == SSA_NAME)
+    cond_expr = fold_build2 (LE_EXPR, boolean_type_node, *lb, *ub);
+  else
+    {
+      tree one = (POINTER_TYPE_P (*type)
+		  ? convert_to_ptrofftype (integer_one_node)
+		  : fold_convert (*type, integer_one_node));
+      /* Adding +1 and using LT_EXPR helps with loop latches that have a
+	 loop iteration count of "PARAMETER - 1".  For PARAMETER == 0 this
+	 becomes 2^k-1 due to integer overflow, and the condition lb <= ub
+	 is true, even if we do not want this.  However lb < ub + 1 is false,
+	 as expected.  */
+      tree ub_one = fold_build2 (POINTER_TYPE_P (*type) ? POINTER_PLUS_EXPR
+				 : PLUS_EXPR, *type, *ub, one);
+
+      cond_expr = fold_build2 (LT_EXPR, boolean_type_node, *lb, ub_one);
+    }
+
+  exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
+
+  return exit_edge;
+}
+
+/* Translates an isl_ast_node_for to Gimple. */
+
+static edge
+translate_isl_ast_node_for (loop_p context_loop, __isl_keep isl_ast_node *node,
+			    edge next_e, ivs_params_p ip)
+{
+  gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_for);
+  tree type, lb, ub;
+  edge last_e = graphite_create_new_loop_guard (next_e, node, &type,
+						&lb, &ub, ip);
+  edge true_e = get_true_edge_from_guard_bb (next_e->dest);
+
+  translate_isl_ast_for_loop (context_loop, node, true_e,
+			      type, lb, ub, ip);
+  return last_e;
+}
+
+/* Translates an ISL AST node NODE to GCC representation in the
+   context of a SESE.  */
+
+static edge
+translate_isl_ast (loop_p context_loop, __isl_keep isl_ast_node *node,
+		   edge next_e, ivs_params_p ip)
+{
+  switch (isl_ast_node_get_type (node))
+    {
+    case isl_ast_node_error:
+      gcc_unreachable ();
+
+    case isl_ast_node_for:
+      return translate_isl_ast_node_for (context_loop, node,
+					 next_e, ip);
+
+    case isl_ast_node_if:
+      return next_e;
+
+    case isl_ast_node_user:
+      return next_e;
+
+    case isl_ast_node_block:
+      return next_e;
+
+    default:
+      gcc_unreachable ();
+    }
+}
+
 /* Prints NODE to FILE.  */
 
 void
@@ -65,6 +586,23 @@
   isl_printer_free (prn);
 }
 
+/* Add ISL's parameter identifiers and corresponding.trees to ivs_params  */
+
+static void
+add_parameters_to_ivs_params (scop_p scop, ivs_params_p ip)
+{
+  sese region = SCOP_REGION (scop);
+  unsigned nb_parameters = isl_set_dim (scop->context, isl_dim_param);
+  gcc_assert (nb_parameters == SESE_PARAMS (region).length ());
+  unsigned i;
+  for (i = 0; i < nb_parameters; i++)
+    {
+      isl_id *tmp_id = isl_set_get_dim_id (scop->context, isl_dim_param, i);
+      ip->tree_from_isl_id[tmp_id] = SESE_PARAMS (region)[i];
+    }
+}
+
+
 /* Generates a build, which specifies the constraints on the parameters.  */
 
 static __isl_give isl_ast_build *
@@ -103,8 +641,15 @@
 }
 
 static __isl_give isl_ast_node *
-scop_to_isl_ast (scop_p scop)
+scop_to_isl_ast (scop_p scop, ivs_params_p ip)
 {
+  /* Generate loop upper bounds that consist of the current loop iterator,
+  an operator (< or <=) and an expression not involving the iterator.
+  If this option is not set, then the current loop iterator may appear several
+  times in the upper bound. See the isl manual for more details.  */
+  isl_options_set_ast_build_atomic_upper_bound (scop->ctx, true);
+
+  add_parameters_to_ivs_params (scop, ip);
   isl_union_map *schedule_isl = generate_isl_schedule (scop);
   isl_ast_build *context_isl = generate_isl_context (scop);
   isl_ast_node *ast_isl = isl_ast_build_ast_from_schedule (context_isl,
@@ -117,21 +662,59 @@
    the given SCOP.  Return true if code generation succeeded.
 
    FIXME: This is not yet a full implementation of the code generator
-          with ISL ASTs. Generation of GIMPLE code is have to be added.  */
+          with ISL ASTs. Generation of GIMPLE code has to be completed.  */
 
 bool
 graphite_regenerate_ast_isl (scop_p scop)
 {
+  loop_p context_loop;
+  sese region = SCOP_REGION (scop);
+  ifsese if_region = NULL;
+  isl_ast_node *root_node;
+  struct ivs_params ip;
+
   timevar_push (TV_GRAPHITE_CODE_GEN);
   graphite_regenerate_error = false;
-  isl_ast_node *root_node = scop_to_isl_ast (scop);
+  root_node = scop_to_isl_ast (scop, &ip);
+
   if (dump_file && (dump_flags & TDF_DETAILS))
     {
       fprintf (dump_file, "\nISL AST generated by ISL: \n");
       print_isl_ast_node (dump_file, root_node, scop->ctx);
+      fprintf (dump_file, "\n");
     }
+
+  recompute_all_dominators ();
+  graphite_verify ();
+
+  if_region = move_sese_in_condition (region);
+  sese_insert_phis_for_liveouts (region,
+				 if_region->region->exit->src,
+				 if_region->false_region->exit,
+				 if_region->true_region->exit);
+  recompute_all_dominators ();
+  graphite_verify ();
+
+  context_loop = SESE_ENTRY (region)->src->loop_father;
+
+  translate_isl_ast (context_loop, root_node, if_region->true_region->entry,
+		     &ip);
+  graphite_verify ();
+  scev_reset ();
+  recompute_all_dominators ();
+  graphite_verify ();
+
+  if (graphite_regenerate_error)
+    set_ifsese_condition (if_region, integer_zero_node);
+
+  free (if_region->true_region);
+  free (if_region->region);
+  free (if_region);
+
+  ivs_params_clear (&ip);
   isl_ast_node_free (root_node);
   timevar_pop (TV_GRAPHITE_CODE_GEN);
+  /* TODO: Add dump  */
   return !graphite_regenerate_error;
 }
 #endif

Re: [GSoC] generation of Gimple loops with empty bodies

[Tobias Grosser]

On 08/07/2014 14:47, Roman Gareev wrote:
>> Surprising. Is the symbol defined in libisl.so? You could use objdump to
>> >check?
> If I am not mistaken, objdump shows that libisl.so contains it.
>
> objdump -d libisl.so.10.2.2 | grep isl_ast_expr_get_val
> 0000000000060380 <isl_ast_expr_get_val>:
>     60383: 74 4b                 je     603d0 <isl_ast_expr_get_val+0x50>
>     60389: 75 0d                 jne    60398 <isl_ast_expr_get_val+0x18

I would use -x to see the headers. This should tell you if it is defined
or only used there.

> +#include "graphite-htab.h"

Is this still needed?

(Just a question, no need to act on it if it is still needed)

> +struct id_comp
> +{
> +  bool operator()(isl_id *id1, isl_id *id2) const
> +  {
> +    const char *name1 = isl_id_get_name (id1);
> +    const char *name2 = isl_id_get_name (id2);
> +    return strcmp (name1, name2) == 0;
> +  }
> +};
No need to provide this. Comparing by pointer should be fine.

> +
> +/* IVS_PARAMS_MAP maps ISL's scattering and parameter identifiers
> +   to corresponding trees.  */
> +typedef struct ivs_params {
> +  std::map<isl_id *, tree, id_comp> ivs_params_map;

What about calling it isl_id_to_tree?

> +  sese region;

Is this region needed?

> +static tree
> +gcc_expression_from_isl_expression (tree type, __isl_keep isl_ast_expr *,
> +				    ivs_params_p ip);

I would make those functions __isl_take the expression.

> +
> +/* Returns the tree variable from the name of isl_id, which is stored
> +   in the isl_ast_expr EXPR_ID that was given in ISL representation.  */

This takes a couple of turns. What about:

"Return the tree variable that corresponds to the given isl ast identifier
  expression (an isl_ast_expr of type isl_ast_expr_id)."

> +
> +static tree
> +gcc_expression_from_isl_ast_expr_id (__isl_keep isl_ast_expr *expr_id,
> +				     ivs_params_p ip)
> +{
> +  gcc_assert (isl_ast_expr_get_type (expr_id) == isl_ast_expr_id);
> +  isl_id *tmp_isl_id = isl_ast_expr_get_id (expr_id);
> +  std::map<isl_id *, tree, id_comp>::iterator res;
> +  res = ip->ivs_params_map.find (tmp_isl_id);
> +  isl_id_free (tmp_isl_id);
> +  gcc_assert (res != ip->ivs_params_map.end ());

Maybe add an assert message ala "Could not map isl_id to tree expression"?

> +  return res->second;
> +}
> +
> +/* Converts a isl_ast_expr_int expression E to a GCC expression tree of

Converts _aN_ isl_ast_expr_int ...
          ^^^^

> +   type TYPE.  */
> +
> +static tree
> +gcc_expression_from_isl_expr_int (tree type, __isl_keep isl_ast_expr *expr)
> +{
> +  gcc_assert (isl_ast_expr_get_type (expr) == isl_ast_expr_int);
> +  isl_int val;
> +  isl_int_init (val);
> +  if (isl_ast_expr_get_int (expr, &val) == -1)
> +    {
> +      isl_int_clear (val);

Sorry, but this still needs to be debugged. :-( I am too busy to do it
myself, so i am afraid you may just need to dig into it yourself. :-(

> +/* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of
> +   type TYPE.  */
> +
> +static tree
> +binary_op_to_tree (tree type, __isl_keep isl_ast_expr *expr, ivs_params_p ip)
> +{
> +  isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
> +  tree tree_lhs_expr = gcc_expression_from_isl_expression (type, arg_expr, ip);
> +  isl_ast_expr_free (arg_expr);

If the from_isl_expression functions become __isl_take this free becomes
unnecessary.

> +/* Converts a isl_ast_expr_op expression E with unknown number of arguments

Converts _an_ isl

> +/* Converts an isl_ast_expr_op expression E to a GCC expression tree of
> +   type TYPE.  */
> +
> +static tree
> +gcc_expression_from_isl_expr_op (tree type, __isl_keep isl_ast_expr *expr,
> +				 ivs_params_p ip)
> +{
> +  gcc_assert (isl_ast_expr_get_type (expr) == isl_ast_expr_op);
> +  switch (isl_ast_expr_get_op_type (expr))
> +    {
> +    /* These isl ast expressions are not supported yet.  */
> +    case isl_ast_op_error:
> +    case isl_ast_op_call:
> +    case isl_ast_op_and_then:
> +    case isl_ast_op_or_else:
> +    case isl_ast_op_pdiv_q:
> +    case isl_ast_op_pdiv_r:
> +    case isl_ast_op_select:
> +      gcc_unreachable ();
> +
> +    case isl_ast_op_max:
> +    case isl_ast_op_min:
> +      return nary_op_to_tree (type, expr, ip);
> +
> +    case isl_ast_op_add:
> +    case isl_ast_op_sub:
> +    case isl_ast_op_mul:
> +    case isl_ast_op_div:
> +    case isl_ast_op_fdiv_q:
> +    case isl_ast_op_and:
> +    case isl_ast_op_or:
> +    case isl_ast_op_eq:
> +    case isl_ast_op_le:
> +    case isl_ast_op_lt:
> +    case isl_ast_op_ge:
> +    case isl_ast_op_gt:
> +      return binary_op_to_tree (type, expr, ip);
> +
> +    case isl_ast_op_minus:
> +      return unary_op_to_tree (type, expr, ip);
> +
> +    case isl_ast_op_cond:
> +      return ternary_op_to_tree (type, expr, ip);
> +
> +    default:
> +      gcc_unreachable ();
> +    }
> +
> +  return NULL_TREE;
> +}
> +
> +/* Converts a ISL AST expression E back to a GCC expression tree of

_an_

> +/* We use this function to get the upper bound because of the form,
> +   which is used by isl to represent loops:
> +
> +   for (iterator = init; cond; iterator += inc)
> +
> +   {
> +
> +     ...
> +
> +   }
> +
> +   The loop condition is an arbitrary expression, which contains the
> +   current loop iterator.

(e.g. iterator + 3 < B && C > iterator + A)

> +
> +   We have to know the upper bound of the iterator to generate a loop
> +   in Gimple form. It can be obtained from the special representation
> +   of the loop condition, which is generated by isl,
> +   if the ast_build_atomic_upper_bound option is set. In this case,
> +   isl generates a loop condition that consists of the current loop
> +   iterator, + an operator (< or <=) and an expression not involving
> +   the iterator, which is processed and returned by this function.  */

e.g (iterator <= upper-bound-expression-without-iterator)

> +static __isl_give isl_ast_expr *
> +get_upper_bound (__isl_keep isl_ast_node *node_for)
> +{
> +  gcc_assert (isl_ast_node_get_type (node_for) == isl_ast_node_for);
> +  isl_ast_expr *for_cond = isl_ast_node_for_get_cond (node_for);
> +  gcc_assert (isl_ast_expr_get_type (for_cond) == isl_ast_expr_op);
> +  isl_ast_expr *res;
> +  switch (isl_ast_expr_get_op_type (for_cond))
> +    {
> +    case isl_ast_op_le:
> +      res = isl_ast_expr_get_op_arg (for_cond, 1);
> +      break;
> +
> +    case isl_ast_op_lt:
> +      {
> +        // (iteraotr < ub) => (iterator <= ub - 1)

iterator

> +        isl_val *one = isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond), 1);
> +        isl_ast_expr *ub = isl_ast_expr_get_op_arg (for_cond, 1);
> +        res = isl_ast_expr_sub (ub, isl_ast_expr_from_val (one));
> +        break;
> +      }
> +
> +    default:
> +      gcc_unreachable ();
> +    }
> +  isl_ast_expr_free (for_cond);
> +  return res;
> +}
> +
> +/* All loops generated by create_empty_loop_on_edge have the form of
> +   a post-test loop:
> +
> +   do
> +
> +   {
> +     body of the loop;
> +   } while (lower bound < upper bound);
> +
> +   We create a new if region protecting the loop to be executed, if
> +   the execution count is zero (lower bound > upper bound). In this case,
> +   it is subsequently removed by dead code elimination.  */

The last sentence is unclear. Are you saying the loop will be removed or
that the condition will be removed in case it is always true. Also, what
about cases where the condition remains?

> +/* Add tree representations and names of parameters to ivs_params  */
> +
> +static void
> +add_parameters_to_ivs_params (scop_p scop, ivs_params_p ip)
> +{
> +  sese region = SCOP_REGION (scop);
> +  int i;
> +  int nb_parameters = SESE_PARAMS (region).length ();
> +  gcc_assert (nb_parameters == (short) isl_set_dim (scop->context,
> +						    isl_dim_param));
> +
> +  for (i = 0; i < nb_parameters; i++)
> +    {
> +      tree param = SESE_PARAMS (region)[i];
> +      const char *name = get_name (param);
> +      int len;
> +      char *parameter;
> +
> +      if (!name)
> +	name = "T";
> +      len = strlen (name);
> +      parameter = XCNEWVEC (char, len + 1);
> +      snprintf (parameter, len, "%s", name);
> +      isl_id *tmp_id = isl_id_alloc (scop->ctx, parameter, NULL);
> +      ip->ivs_params_map[tmp_id] = param;
> +      free (parameter);
> +    }
> +}

I see now possibly why you compared the isl_id's by name above. At this
point, all parameters should already have ids assigned. We should use 
those very id's to add the param locations into this map.

>   /* Generates a build, which specifies the constraints on the parameters.  */
>
> -static isl_ast_build *
> +static __isl_give isl_ast_build *
>   generate_isl_context (scop_p scop)
>   {
>     isl_set *context_isl = isl_set_params (isl_set_copy (scop->context));
> @@ -77,7 +640,7 @@
>   /* Generates a schedule, which specifies an order used to
>      visit elements in a domain.  */
>
> -static isl_union_map *
> +static __isl_give isl_union_map *
>   generate_isl_schedule (scop_p scop)
>   {
>     int i;
> @@ -102,9 +665,16 @@
>     return schedule_isl;
>   }
>
> -static isl_ast_node *
> -scop_to_isl_ast (scop_p scop)
> +static __isl_give isl_ast_node *
> +scop_to_isl_ast (scop_p scop, ivs_params_p ip)

Those changes are unrelated and are part of the other patch, right?

>   {
> +  /* Generate loop upper bounds that consist of the current loop iterator,
> +  an operator (< or <=) and an expression not involving the iterator.
> +  If this option is not set, then the current loop iterator may appear several
> +  times in the upper bound. See the isl manual for more details.  */
> +  isl_options_set_ast_build_atomic_upper_bound (scop->ctx, true);
> +
> +  add_parameters_to_ivs_params (scop, ip);
>     isl_union_map *schedule_isl = generate_isl_schedule (scop);
>     isl_ast_build *context_isl = generate_isl_context (scop);
>     isl_ast_node *ast_isl = isl_ast_build_ast_from_schedule (context_isl,
> @@ -117,21 +687,62 @@
>      the given SCOP.  Return true if code generation succeeded.
>
>      FIXME: This is not yet a full implementation of the code generator
> -          with ISL ASTs. Generation of GIMPLE code is have to be added.  */
> +          with ISL ASTs. Generation of GIMPLE code has to be completed.  */
>
>   bool
>   graphite_regenerate_ast_isl (scop_p scop)
>   {
> +  loop_p context_loop;
> +  sese region = SCOP_REGION (scop);
> +  ifsese if_region = NULL;
> +  isl_ast_node *root_node;
> +  struct ivs_params ip;
> +
>     timevar_push (TV_GRAPHITE_CODE_GEN);
>     graphite_regenerate_error = false;
> -  isl_ast_node *root_node = scop_to_isl_ast (scop);
> +
> +  ip.region = region;

Is this needed? ip.region seems unused.

Cheers,
Tobias

Re: [GSoC] generation of Gimple loops with empty bodies

[Roman Gareev]

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

> Surprising. Is the symbol defined in libisl.so? You could use objdump to
> check?

If I am not mistaken, objdump shows that libisl.so contains it.

objdump -d libisl.so.10.2.2 | grep isl_ast_expr_get_val
0000000000060380 <isl_ast_expr_get_val>:
   60383: 74 4b                 je     603d0 <isl_ast_expr_get_val+0x50>
   60389: 75 0d                 jne    60398 <isl_ast_expr_get_val+0x18




I've attached the version, which uses map instead of hash table.

--
                                   Cheers, Roman Gareev

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

Index: gcc/graphite-isl-ast-to-gimple.c
===================================================================
--- gcc/graphite-isl-ast-to-gimple.c	(revision 212294)
+++ gcc/graphite-isl-ast-to-gimple.c	(working copy)
@@ -42,16 +42,549 @@
 #include "cfgloop.h"
 #include "tree-data-ref.h"
 #include "sese.h"
+#include "tree-ssa-loop-manip.h"
+#include "tree-scalar-evolution.h"
+#include <map>
 
 #ifdef HAVE_cloog
 #include "graphite-poly.h"
 #include "graphite-isl-ast-to-gimple.h"
+#include "graphite-htab.h"
 
 /* This flag is set when an error occurred during the translation of
    ISL AST to Gimple.  */
 
 static bool graphite_regenerate_error;
 
+/* We always use signed 128, until isl is able to give information about
+types  */
+
+static tree *graphite_expression_size_type = &int128_integer_type_node;
+
+/* Converts a GMP constant VAL to a tree and returns it.  */
+
+static tree
+gmp_cst_to_tree (tree type, mpz_t val)
+{
+  tree t = type ? type : integer_type_node;
+  mpz_t tmp;
+
+  mpz_init (tmp);
+  mpz_set (tmp, val);
+  wide_int wi = wi::from_mpz (t, tmp, true);
+  mpz_clear (tmp);
+
+  return wide_int_to_tree (t, wi);
+}
+
+/* Verifies properties that GRAPHITE should maintain during translation.  */
+
+static inline void
+graphite_verify (void)
+{
+#ifdef ENABLE_CHECKING
+  verify_loop_structure ();
+  verify_loop_closed_ssa (true);
+#endif
+}
+
+/* The comparison function for ivs_params_map  */
+
+struct id_comp
+{
+  bool operator()(isl_id *id1, isl_id *id2) const
+  {
+    const char *name1 = isl_id_get_name (id1);
+    const char *name2 = isl_id_get_name (id2);
+    return strcmp (name1, name2) == 0;
+  }
+};
+
+/* IVS_PARAMS_MAP maps ISL's scattering and parameter identifiers
+   to corresponding trees.  */
+
+typedef struct ivs_params {
+  std::map<isl_id *, tree, id_comp> ivs_params_map;
+  sese region;
+} *ivs_params_p;
+
+/* Free all memory allocated for ISL's identifiers.  */
+
+void ivs_params_clear (ivs_params_p ip)
+{
+  std::map<isl_id *, tree, id_comp>::iterator it;
+  for (it = ip->ivs_params_map.begin (); it != ip->ivs_params_map.end (); it++)
+    {
+      isl_id_free (it->first);
+    }
+}
+
+static tree
+gcc_expression_from_isl_expression (tree type, __isl_keep isl_ast_expr *,
+				    ivs_params_p ip);
+
+/* Returns the tree variable from the name of isl_id, which is stored
+   in the isl_ast_expr EXPR_ID that was given in ISL representation.  */
+
+static tree
+gcc_expression_from_isl_ast_expr_id (__isl_keep isl_ast_expr *expr_id,
+				     ivs_params_p ip)
+{
+  gcc_assert (isl_ast_expr_get_type (expr_id) == isl_ast_expr_id);
+  isl_id *tmp_isl_id = isl_ast_expr_get_id (expr_id);
+  std::map<isl_id *, tree, id_comp>::iterator res;
+  res = ip->ivs_params_map.find (tmp_isl_id);
+  isl_id_free (tmp_isl_id);
+  gcc_assert (res != ip->ivs_params_map.end ());
+  return res->second;
+}
+
+/* Converts a isl_ast_expr_int expression E to a GCC expression tree of
+   type TYPE.  */
+
+static tree
+gcc_expression_from_isl_expr_int (tree type, __isl_keep isl_ast_expr *expr)
+{
+  gcc_assert (isl_ast_expr_get_type (expr) == isl_ast_expr_int);
+  isl_int val;
+  isl_int_init (val);
+  if (isl_ast_expr_get_int (expr, &val) == -1)
+    {
+      isl_int_clear (val);
+      return NULL_TREE;
+    }
+  else
+    return gmp_cst_to_tree (type, val);
+}
+
+/* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of
+   type TYPE.  */
+
+static tree
+binary_op_to_tree (tree type, __isl_keep isl_ast_expr *expr, ivs_params_p ip)
+{
+  isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
+  tree tree_lhs_expr = gcc_expression_from_isl_expression (type, arg_expr, ip);
+  isl_ast_expr_free (arg_expr);
+  arg_expr = isl_ast_expr_get_op_arg (expr, 1);
+  tree tree_rhs_expr = gcc_expression_from_isl_expression (type, arg_expr, ip);
+  isl_ast_expr_free (arg_expr);
+  switch (isl_ast_expr_get_op_type (expr))
+    {
+    case isl_ast_op_add:
+      return fold_build2 (PLUS_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+    case isl_ast_op_sub:
+      return fold_build2 (MINUS_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+    case isl_ast_op_mul:
+      return fold_build2 (MULT_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+    case isl_ast_op_div:
+      return fold_build2 (EXACT_DIV_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+    case isl_ast_op_fdiv_q:
+      return fold_build2 (FLOOR_DIV_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+    case isl_ast_op_and:
+      return fold_build2 (TRUTH_ANDIF_EXPR, type,
+			  tree_lhs_expr, tree_rhs_expr);
+
+    case isl_ast_op_or:
+      return fold_build2 (TRUTH_ORIF_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+    case isl_ast_op_eq:
+      return fold_build2 (EQ_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+    case isl_ast_op_le:
+      return fold_build2 (LE_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+    case isl_ast_op_lt:
+      return fold_build2 (LT_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+    case isl_ast_op_ge:
+      return fold_build2 (GE_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+    case isl_ast_op_gt:
+      return fold_build2 (GT_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+    default:
+      gcc_unreachable ();
+    }
+}
+
+/* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of
+   type TYPE.  */
+
+static tree
+ternary_op_to_tree (tree type, __isl_keep isl_ast_expr *expr, ivs_params_p ip)
+{
+  gcc_assert (isl_ast_expr_get_op_type (expr) == isl_ast_op_minus);
+  isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
+  tree tree_first_expr
+    = gcc_expression_from_isl_expression (type, arg_expr, ip);
+  isl_ast_expr_free (arg_expr);
+  arg_expr = isl_ast_expr_get_op_arg (expr, 1);
+  tree tree_second_expr
+    = gcc_expression_from_isl_expression (type, arg_expr, ip);
+  isl_ast_expr_free (arg_expr);
+  arg_expr = isl_ast_expr_get_op_arg (expr, 2);
+  tree tree_third_expr
+    = gcc_expression_from_isl_expression (type, arg_expr, ip);
+  isl_ast_expr_free (arg_expr);
+  return fold_build3 (COND_EXPR, type, tree_first_expr,
+		      tree_second_expr, tree_third_expr);
+}
+
+/* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
+   type TYPE.  */
+
+static tree
+unary_op_to_tree (tree type, __isl_keep isl_ast_expr *expr, ivs_params_p ip)
+{
+  gcc_assert (isl_ast_expr_get_op_type (expr) == isl_ast_op_minus);
+  isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
+  tree tree_expr = gcc_expression_from_isl_expression (type, arg_expr, ip);
+  isl_ast_expr_free (arg_expr);
+  return fold_build1 (NEGATE_EXPR, type, tree_expr);
+}
+
+/* Converts a isl_ast_expr_op expression E with unknown number of arguments
+   to a GCC expression tree of type TYPE.  */
+
+static tree
+nary_op_to_tree (tree type, __isl_keep isl_ast_expr *expr, ivs_params_p ip)
+{
+  enum tree_code op_code;
+  switch (isl_ast_expr_get_op_type (expr))
+    {
+    case isl_ast_op_max:
+      op_code = MAX_EXPR;
+      break;
+
+    case isl_ast_op_min:
+      op_code = MIN_EXPR;
+      break;
+
+    default:
+      gcc_unreachable ();    
+    }
+  isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
+  tree res = gcc_expression_from_isl_expression (type, arg_expr, ip);
+  isl_ast_expr_free (arg_expr);
+  int i;
+  for (i = 1; i < isl_ast_expr_get_op_n_arg (expr); i++)
+    {
+      arg_expr = isl_ast_expr_get_op_arg (expr, i);
+      tree t = gcc_expression_from_isl_expression (type, arg_expr, ip);
+      res = fold_build2 (op_code, type, res, t);
+      isl_ast_expr_free (arg_expr);
+    }
+  return res;
+}
+
+
+/* Converts an isl_ast_expr_op expression E to a GCC expression tree of
+   type TYPE.  */
+
+static tree
+gcc_expression_from_isl_expr_op (tree type, __isl_keep isl_ast_expr *expr,
+				 ivs_params_p ip)
+{
+  gcc_assert (isl_ast_expr_get_type (expr) == isl_ast_expr_op);
+  switch (isl_ast_expr_get_op_type (expr))
+    {
+    /* These isl ast expressions are not supported yet.  */
+    case isl_ast_op_error:
+    case isl_ast_op_call:
+    case isl_ast_op_and_then:
+    case isl_ast_op_or_else:
+    case isl_ast_op_pdiv_q:
+    case isl_ast_op_pdiv_r:
+    case isl_ast_op_select:
+      gcc_unreachable ();
+
+    case isl_ast_op_max:
+    case isl_ast_op_min:
+      return nary_op_to_tree (type, expr, ip);
+
+    case isl_ast_op_add:
+    case isl_ast_op_sub:
+    case isl_ast_op_mul:
+    case isl_ast_op_div:
+    case isl_ast_op_fdiv_q:
+    case isl_ast_op_and:
+    case isl_ast_op_or:
+    case isl_ast_op_eq:
+    case isl_ast_op_le:
+    case isl_ast_op_lt:
+    case isl_ast_op_ge:
+    case isl_ast_op_gt:
+      return binary_op_to_tree (type, expr, ip);
+
+    case isl_ast_op_minus:
+      return unary_op_to_tree (type, expr, ip);
+
+    case isl_ast_op_cond:
+      return ternary_op_to_tree (type, expr, ip);
+
+    default:
+      gcc_unreachable ();
+    }
+
+  return NULL_TREE;
+}
+
+/* Converts a ISL AST expression E back to a GCC expression tree of
+   type TYPE.  */
+
+static tree
+gcc_expression_from_isl_expression (tree type, __isl_keep isl_ast_expr *expr,
+				    ivs_params_p ip)
+{
+  switch (isl_ast_expr_get_type (expr))
+    {
+    case isl_ast_expr_id:
+      return gcc_expression_from_isl_ast_expr_id (expr, ip);
+
+    case isl_ast_expr_int:
+      return gcc_expression_from_isl_expr_int (type, expr);
+
+    case isl_ast_expr_op:
+      return gcc_expression_from_isl_expr_op (type, expr, ip);
+
+    default:
+      gcc_unreachable ();
+    }
+
+  return NULL_TREE;
+}
+
+/* Creates a new LOOP corresponding to isl_ast_node_for.  Inserts an
+   induction variable for the new LOOP.  New LOOP is attached to CFG
+   starting at ENTRY_EDGE.  LOOP is inserted into the loop tree and
+   becomes the child loop of the OUTER_LOOP.  NEWIVS_INDEX binds
+   ISL's scattering name to the induction variable created for the
+   loop of STMT.  The new induction variable is inserted in the NEWIVS
+   vector and is of type TYPE.  */
+
+static struct loop *
+graphite_create_new_loop (edge entry_edge, __isl_keep isl_ast_node *node_for,
+			  loop_p outer, tree type, tree lb, tree ub,
+			  ivs_params_p ip)
+{
+  isl_ast_expr *for_inc = isl_ast_node_for_get_inc (node_for);
+  tree stride = gcc_expression_from_isl_expression (type, for_inc, ip);
+  isl_ast_expr_free (for_inc);
+  tree ivvar = create_tmp_var (type, "graphite_IV");
+  tree iv, iv_after_increment;
+  loop_p loop = create_empty_loop_on_edge
+    (entry_edge, lb, stride, ub, ivvar, &iv, &iv_after_increment,
+     outer ? outer : entry_edge->src->loop_father);
+
+  isl_ast_expr *for_iterator = isl_ast_node_for_get_iterator (node_for);
+  isl_id *id = isl_ast_expr_get_id (for_iterator);
+  std::map<isl_id *, tree, id_comp>::iterator it;
+  it = ip->ivs_params_map.find (id);
+  if (it == ip->ivs_params_map.end ())
+    ip->ivs_params_map[id] = iv;
+  else
+    {
+      it->second = iv;
+      isl_id_free (id);
+    }
+  isl_ast_expr_free (for_iterator);
+  return loop;
+}
+
+static edge
+translate_isl_ast (loop_p context_loop, __isl_keep isl_ast_node *node,
+		   edge next_e, ivs_params_p ip);
+
+/* Create the loop for a isl_ast_node_for.
+
+   - NEXT_E is the edge where new generated code should be attached.  */
+
+static edge
+translate_isl_ast_for_loop (loop_p context_loop,
+			    __isl_keep isl_ast_node *node_for, edge next_e,
+			    tree type, tree lb, tree ub,
+			    ivs_params_p ip)
+{
+  gcc_assert (isl_ast_node_get_type (node_for) == isl_ast_node_for);
+  struct loop *loop = graphite_create_new_loop (next_e, node_for, context_loop,
+						type, lb, ub, ip);
+  edge last_e = single_exit (loop);
+  edge to_body = single_succ_edge (loop->header);
+  basic_block after = to_body->dest;
+
+  /* Create a basic block for loop close phi nodes.  */
+  last_e = single_succ_edge (split_edge (last_e));
+
+  /* Translate the body of the loop.  */
+  isl_ast_node *for_body = isl_ast_node_for_get_body (node_for);
+  next_e = translate_isl_ast (loop, for_body, to_body, ip);
+  isl_ast_node_free (for_body);
+  redirect_edge_succ_nodup (next_e, after);
+  set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src);
+
+  /* TODO: Add checking for the loop parallelism.  */
+
+  return last_e;
+}
+
+/* We use this function to get the upper bound because of the form,
+   which is used by isl to represent loops:
+
+   for (iterator = init; cond; iterator += inc)
+
+   {
+
+     ...
+
+   }
+
+   The loop condition is an arbitrary expression, which contains the
+   current loop iterator.
+
+   We have to know the upper bound of the iterator to generate a loop
+   in Gimple form. It can be obtained from the special representation
+   of the loop condition, which is generated by isl,
+   if the ast_build_atomic_upper_bound option is set. In this case,
+   isl generates a loop condition that consists of the current loop
+   iterator, + an operator (< or <=) and an expression not involving
+   the iterator, which is processed and returned by this function.  */
+
+static __isl_give isl_ast_expr *
+get_upper_bound (__isl_keep isl_ast_node *node_for)
+{
+  gcc_assert (isl_ast_node_get_type (node_for) == isl_ast_node_for);
+  isl_ast_expr *for_cond = isl_ast_node_for_get_cond (node_for);
+  gcc_assert (isl_ast_expr_get_type (for_cond) == isl_ast_expr_op);
+  isl_ast_expr *res;
+  switch (isl_ast_expr_get_op_type (for_cond))
+    {
+    case isl_ast_op_le:
+      res = isl_ast_expr_get_op_arg (for_cond, 1);
+      break;
+
+    case isl_ast_op_lt:
+      {
+        // (iteraotr < ub) => (iterator <= ub - 1)
+        isl_val *one = isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond), 1);
+        isl_ast_expr *ub = isl_ast_expr_get_op_arg (for_cond, 1);
+        res = isl_ast_expr_sub (ub, isl_ast_expr_from_val (one));
+        break;
+      }
+
+    default:
+      gcc_unreachable ();
+    }
+  isl_ast_expr_free (for_cond);
+  return res;
+}
+
+/* All loops generated by create_empty_loop_on_edge have the form of
+   a post-test loop:
+
+   do
+
+   {
+     body of the loop;
+   } while (lower bound < upper bound);
+
+   We create a new if region protecting the loop to be executed, if
+   the execution count is zero (lower bound > upper bound). In this case,
+   it is subsequently removed by dead code elimination.  */
+
+static edge
+graphite_create_new_loop_guard (edge entry_edge,
+				__isl_keep isl_ast_node *node_for, tree *type,
+				tree *lb, tree *ub, ivs_params_p ip)
+{
+  gcc_assert (isl_ast_node_get_type (node_for) == isl_ast_node_for);
+  tree cond_expr;
+  edge exit_edge;
+
+  *type = *graphite_expression_size_type;
+  isl_ast_expr *for_init = isl_ast_node_for_get_init (node_for);
+  *lb = gcc_expression_from_isl_expression (*type, for_init, ip);
+  isl_ast_expr_free (for_init);
+  isl_ast_expr *upper_bound = get_upper_bound (node_for);
+  *ub = gcc_expression_from_isl_expression (*type, upper_bound, ip);
+  isl_ast_expr_free (upper_bound);
+  
+  /* When ub is simply a constant or a parameter, use lb <= ub.  */
+  if (TREE_CODE (*ub) == INTEGER_CST || TREE_CODE (*ub) == SSA_NAME)
+    cond_expr = fold_build2 (LE_EXPR, boolean_type_node, *lb, *ub);
+  else
+    {
+      tree one = (POINTER_TYPE_P (*type)
+		  ? convert_to_ptrofftype (integer_one_node)
+		  : fold_convert (*type, integer_one_node));
+      /* Adding +1 and using LT_EXPR helps with loop latches that have a
+	 loop iteration count of "PARAMETER - 1".  For PARAMETER == 0 this
+	 becomes 2^k-1 due to integer overflow, and the condition lb <= ub
+	 is true, even if we do not want this.  However lb < ub + 1 is false,
+	 as expected.  */
+      tree ub_one = fold_build2 (POINTER_TYPE_P (*type) ? POINTER_PLUS_EXPR
+				 : PLUS_EXPR, *type, *ub, one);
+
+      cond_expr = fold_build2 (LT_EXPR, boolean_type_node, *lb, ub_one);
+    }
+
+  exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
+
+  return exit_edge;
+}
+
+/* Translates an isl_ast_node_for to Gimple. */
+
+static edge
+translate_isl_ast_node_for (loop_p context_loop, __isl_keep isl_ast_node *node,
+			    edge next_e, ivs_params_p ip)
+{
+  gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_for);
+  tree type, lb, ub;
+  edge last_e = graphite_create_new_loop_guard (next_e, node, &type,
+						&lb, &ub, ip);
+  edge true_e = get_true_edge_from_guard_bb (next_e->dest);
+
+  translate_isl_ast_for_loop (context_loop, node, true_e,
+			      type, lb, ub, ip);
+  return last_e;
+}
+
+/* Translates an ISL AST node NODE to GCC representation in the
+   context of a SESE.  */
+
+static edge
+translate_isl_ast (loop_p context_loop, __isl_keep isl_ast_node *node,
+		   edge next_e, ivs_params_p ip)
+{
+  switch (isl_ast_node_get_type (node))
+    {
+    case isl_ast_node_error:
+      gcc_unreachable ();
+
+    case isl_ast_node_for:
+      return translate_isl_ast_node_for (context_loop, node,
+					 next_e, ip);
+
+    case isl_ast_node_if:
+      return next_e;
+
+    case isl_ast_node_user:
+      return next_e;
+
+    case isl_ast_node_block:
+      return next_e;
+
+    default:
+      gcc_unreachable ();
+    }
+}
+
 /* Prints NODE to FILE.  */
 
 void
@@ -65,9 +598,39 @@
   isl_printer_free (prn);
 }
 
+/* Add tree representations and names of parameters to ivs_params  */
+
+static void
+add_parameters_to_ivs_params (scop_p scop, ivs_params_p ip)
+{
+  sese region = SCOP_REGION (scop);
+  int i;
+  int nb_parameters = SESE_PARAMS (region).length ();
+  gcc_assert (nb_parameters == (short) isl_set_dim (scop->context,
+						    isl_dim_param));
+
+  for (i = 0; i < nb_parameters; i++)
+    {
+      tree param = SESE_PARAMS (region)[i];
+      const char *name = get_name (param);
+      int len;
+      char *parameter;
+
+      if (!name)
+	name = "T";
+      len = strlen (name);
+      parameter = XCNEWVEC (char, len + 1);
+      snprintf (parameter, len, "%s", name);
+      isl_id *tmp_id = isl_id_alloc (scop->ctx, parameter, NULL);
+      ip->ivs_params_map[tmp_id] = param;
+      free (parameter);
+    }
+}
+
+
 /* Generates a build, which specifies the constraints on the parameters.  */
 
-static isl_ast_build *
+static __isl_give isl_ast_build *
 generate_isl_context (scop_p scop)
 {
   isl_set *context_isl = isl_set_params (isl_set_copy (scop->context));
@@ -77,7 +640,7 @@
 /* Generates a schedule, which specifies an order used to
    visit elements in a domain.  */
 
-static isl_union_map *
+static __isl_give isl_union_map *
 generate_isl_schedule (scop_p scop)
 {
   int i;
@@ -102,9 +665,16 @@
   return schedule_isl;
 }
 
-static isl_ast_node *
-scop_to_isl_ast (scop_p scop)
+static __isl_give isl_ast_node *
+scop_to_isl_ast (scop_p scop, ivs_params_p ip)
 {
+  /* Generate loop upper bounds that consist of the current loop iterator,
+  an operator (< or <=) and an expression not involving the iterator.
+  If this option is not set, then the current loop iterator may appear several
+  times in the upper bound. See the isl manual for more details.  */
+  isl_options_set_ast_build_atomic_upper_bound (scop->ctx, true);
+
+  add_parameters_to_ivs_params (scop, ip);
   isl_union_map *schedule_isl = generate_isl_schedule (scop);
   isl_ast_build *context_isl = generate_isl_context (scop);
   isl_ast_node *ast_isl = isl_ast_build_ast_from_schedule (context_isl,
@@ -117,21 +687,62 @@
    the given SCOP.  Return true if code generation succeeded.
 
    FIXME: This is not yet a full implementation of the code generator
-          with ISL ASTs. Generation of GIMPLE code is have to be added.  */
+          with ISL ASTs. Generation of GIMPLE code has to be completed.  */
 
 bool
 graphite_regenerate_ast_isl (scop_p scop)
 {
+  loop_p context_loop;
+  sese region = SCOP_REGION (scop);
+  ifsese if_region = NULL;
+  isl_ast_node *root_node;
+  struct ivs_params ip;
+
   timevar_push (TV_GRAPHITE_CODE_GEN);
   graphite_regenerate_error = false;
-  isl_ast_node *root_node = scop_to_isl_ast (scop);
+
+  ip.region = region;
+
+  root_node = scop_to_isl_ast (scop, &ip);
+
   if (dump_file && (dump_flags & TDF_DETAILS))
     {
       fprintf (dump_file, "\nISL AST generated by ISL: \n");
       print_isl_ast_node (dump_file, root_node, scop->ctx);
+      fprintf (dump_file, "\n");
     }
+
+  recompute_all_dominators ();
+  graphite_verify ();
+
+  if_region = move_sese_in_condition (region);
+  sese_insert_phis_for_liveouts (region,
+				 if_region->region->exit->src,
+				 if_region->false_region->exit,
+				 if_region->true_region->exit);
+  recompute_all_dominators ();
+  graphite_verify ();
+
+  context_loop = SESE_ENTRY (region)->src->loop_father;
+
+  translate_isl_ast (context_loop, root_node, if_region->true_region->entry,
+		     &ip);
+  graphite_verify ();
+  scev_reset ();
+  recompute_all_dominators ();
+  graphite_verify ();
+
+  if (graphite_regenerate_error)
+    set_ifsese_condition (if_region, integer_zero_node);
+
+  free (if_region->true_region);
+  free (if_region->region);
+  free (if_region);
+
+  ivs_params_clear (&ip);
   isl_ast_node_free (root_node);
   timevar_pop (TV_GRAPHITE_CODE_GEN);
+  /* TODO: Add dump  */
   return !graphite_regenerate_error;
 }
 #endif

Re: [GSoC] generation of Gimple loops with empty bodies

[Tobias Grosser]

On 05/07/2014 09:06, Roman Gareev wrote:
>> Sorry, I may have missed it. What kind of error was arising?
>
> Symbol lookup error. The full error message:
>
> /home/roman/compiled/build/graphite_sec/libexec/gcc/x86_64-unknown-linux-gnu/4.10.0/cc1:
> symbol lookup error:
> /home/roman/compiled/build/graphite_sec/libexec/gcc/x86_64-unknown-linux-gnu/4.10.0/cc1:
> undefined symbol: isl_ast_expr_get_val
>
> I've attached the version, which uses isl_val instead of isl_int.

Surprising. Is the symbol defined in libisl.so? You could use objdump to 
check?

>> I see. The way you generate loops seems to be exactly right (at least for
>> now). I only was asking you to add comments explaining why this was done
>> this way. It seems you just went the way of least resistance, but maybe you
>> can use my previous comments to motivate this a little bit more in the
>> source code (I will then go through the comments and add the missing pieces
>> of motivation).
>
> Possible motivation was added to comments of
> graphite_create_new_loop_guard and get_upper_bound. I am ready to add
> something or totally rewrite them.

Sorry, I did not yet find the time to go through this. I will try to do 
this later today.

Tobias

[GSoC] generation of Gimple loops with empty bodies

[Roman Gareev]

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

> Sorry, I may have missed it. What kind of error was arising?

Symbol lookup error. The full error message:

/home/roman/compiled/build/graphite_sec/libexec/gcc/x86_64-unknown-linux-gnu/4.10.0/cc1:
symbol lookup error:
/home/roman/compiled/build/graphite_sec/libexec/gcc/x86_64-unknown-linux-gnu/4.10.0/cc1:
undefined symbol: isl_ast_expr_get_val

I've attached the version, which uses isl_val instead of isl_int.

> I see. The way you generate loops seems to be exactly right (at least for
> now). I only was asking you to add comments explaining why this was done
> this way. It seems you just went the way of least resistance, but maybe you
> can use my previous comments to motivate this a little bit more in the
> source code (I will then go through the comments and add the missing pieces
> of motivation).

Possible motivation was added to comments of
graphite_create_new_loop_guard and get_upper_bound. I am ready to add
something or totally rewrite them.

--
                                   Cheers, Roman Gareev

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

Index: gcc/graphite-isl-ast-to-gimple.c
===================================================================
--- gcc/graphite-isl-ast-to-gimple.c	(revision 212294)
+++ gcc/graphite-isl-ast-to-gimple.c	(working copy)
@@ -42,16 +42,640 @@
 #include "cfgloop.h"
 #include "tree-data-ref.h"
 #include "sese.h"
+#include "tree-ssa-loop-manip.h"
+#include "tree-scalar-evolution.h"
 
 #ifdef HAVE_cloog
 #include "graphite-poly.h"
 #include "graphite-isl-ast-to-gimple.h"
+#include "graphite-htab.h"
 
 /* This flag is set when an error occurred during the translation of
    ISL AST to Gimple.  */
 
 static bool graphite_regenerate_error;
 
+/* We always use signed 128, until isl is able to give information about
+types  */
+
+static tree *graphite_expression_size_type = &int128_integer_type_node;
+
+/* Converts a GMP constant VAL to a tree and returns it.  */
+
+static tree
+gmp_cst_to_tree (tree type, mpz_t val)
+{
+  tree t = type ? type : integer_type_node;
+  mpz_t tmp;
+
+  mpz_init (tmp);
+  mpz_set (tmp, val);
+  wide_int wi = wi::from_mpz (t, tmp, true);
+  mpz_clear (tmp);
+
+  return wide_int_to_tree (t, wi);
+}
+
+/* Verifies properties that GRAPHITE should maintain during translation.  */
+
+static inline void
+graphite_verify (void)
+{
+#ifdef ENABLE_CHECKING
+  verify_loop_structure ();
+  verify_loop_closed_ssa (true);
+#endif
+}
+
+/* Stores the INDEX in a vector for a given isl_id NAME.  */
+
+typedef struct ast_isl_name_index {
+  int index;
+  const char *name;
+  /* If free_name is set, the content of name was allocated by us and needs
+     to be freed.  */
+  char *free_name;
+} *ast_isl_name_index_p;
+
+/* Helper for hashing ast_isl_name_index.  */
+
+struct ast_isl_index_hasher
+{
+  typedef ast_isl_name_index value_type;
+  typedef ast_isl_name_index compare_type;
+  static inline hashval_t hash (const value_type *);
+  static inline bool equal (const value_type *, const compare_type *);
+  static inline void remove (value_type *);
+};
+
+/* Computes a hash function for database element E.  */
+
+inline hashval_t
+ast_isl_index_hasher::hash (const value_type *e)
+{
+  hashval_t hash = 0;
+
+  int length = strlen (e->name);
+  int i;
+
+  for (i = 0; i < length; ++i)
+    hash = hash | (e->name[i] << (i % 4));
+
+  return hash;
+}
+
+/* Compares database elements ELT1 and ELT2.  */
+
+inline bool
+ast_isl_index_hasher::equal (const value_type *elt1, const compare_type *elt2)
+{
+  return strcmp (elt1->name, elt2->name) == 0;
+}
+
+/* Free the memory taken by a ast_isl_name_index struct.  */
+
+inline void
+ast_isl_index_hasher::remove (value_type *c)
+{
+  if (c->free_name)
+    free (c->free_name);
+  free (c);
+}
+
+typedef hash_table<ast_isl_index_hasher> ast_isl_index_htab_type;
+
+/* Returns a pointer to a new element of type ast_isl_name_index_p built
+   from NAME, INDEX.  */
+
+static inline ast_isl_name_index_p
+new_ast_isl_name_index (const char *name, int index)
+{
+  ast_isl_name_index_p res = XNEW (struct ast_isl_name_index);
+  char *new_name = XNEWVEC (char, strlen (name) + 1);
+  strcpy (new_name, name);
+
+  res->name = new_name;
+  res->free_name = new_name;
+  res->index = index;
+  return res;
+}
+
+/* For a given name of the isl_id, which is stored in the isl_ast_expr EXPR_ID,
+   returns -1 if it does not correspond to any parameter, or otherwise, returns
+   the index in the PARAMS or SCATTERING_DIMENSIONS vector.  */
+
+static inline int
+ast_expr_id_to_index (__isl_keep isl_ast_expr *expr_id,
+		      ast_isl_index_htab_type *index_table)
+{
+  struct ast_isl_name_index tmp;
+  ast_isl_name_index **slot;
+
+  isl_id *tmp_isl_id = isl_ast_expr_get_id (expr_id);
+  tmp.name = isl_id_get_name (tmp_isl_id);
+  tmp.free_name = NULL;
+
+  slot = index_table->find_slot (&tmp, NO_INSERT);
+
+  isl_id_free (tmp_isl_id);
+  if (slot && *slot)
+    return (*slot)->index;
+
+  return -1;
+}
+
+/* Records in INDEX_TABLE the INDEX and for NAME.  */
+
+static inline void
+save_isl_id_name_index (ast_isl_index_htab_type *index_table,
+			const char *name, int index)
+{
+  struct ast_isl_name_index tmp;
+  ast_isl_name_index **slot;
+
+  tmp.name = name;
+  tmp.free_name = NULL;
+  slot = index_table->find_slot (&tmp, INSERT);
+
+  if (slot)
+    {
+      free (*slot);
+      *slot = new_ast_isl_name_index (name, index);
+    }
+}
+
+/* INDEX binds ISL's scattering and parameter name to the index of the tree
+   induction variable and paramatere in IVS_PARAMS_VEC.
+
+   PARAMS_INDEX binds ISL's parameter name to the index of the tree
+   parameter in PARAMS.  */
+
+typedef struct ivs_params {
+  vec<tree> ivs_params_vec;
+  ast_isl_index_htab_type *ivs_params_index;
+  sese region;
+} *ivs_params_p;
+
+static tree
+gcc_expression_from_isl_expression (tree type, __isl_keep isl_ast_expr *,
+				    ivs_params_p ip);
+
+/* Returns the tree variable from the name of isl_id, which is stored
+   in the isl_ast_expr EXPR_ID that was given in ISL representation.  */
+
+static tree
+gcc_expression_from_isl_ast_expr_id (__isl_keep isl_ast_expr *expr_id,
+				     ivs_params_p ip)
+{
+  gcc_assert (isl_ast_expr_get_type (expr_id) == isl_ast_expr_id);
+  int index;
+  gcc_assert (ip->ivs_params_vec.exists () && ip->ivs_params_index);
+  index = ast_expr_id_to_index (expr_id, ip->ivs_params_index);
+  gcc_assert (index >= 0);
+  return (ip->ivs_params_vec)[index];
+}
+
+/* Converts a isl_ast_expr_int expression E to a GCC expression tree of
+   type TYPE.  */
+
+static tree
+gcc_expression_from_isl_expr_int (tree type, __isl_keep isl_ast_expr *expr)
+{
+  gcc_assert (isl_ast_expr_get_type (expr) == isl_ast_expr_int);
+  isl_int val;
+  isl_int_init (val);
+  if (isl_ast_expr_get_int (expr, &val) == -1)
+    {
+      isl_int_clear (val);
+      return NULL_TREE;
+    }
+  else
+    return gmp_cst_to_tree (type, val);
+}
+
+/* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of
+   type TYPE.  */
+
+static tree
+binary_op_to_tree (tree type, __isl_keep isl_ast_expr *expr, ivs_params_p ip)
+{
+  isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
+  tree tree_lhs_expr = gcc_expression_from_isl_expression (type, arg_expr, ip);
+  isl_ast_expr_free (arg_expr);
+  arg_expr = isl_ast_expr_get_op_arg (expr, 1);
+  tree tree_rhs_expr = gcc_expression_from_isl_expression (type, arg_expr, ip);
+  isl_ast_expr_free (arg_expr);
+  switch (isl_ast_expr_get_op_type (expr))
+    {
+    case isl_ast_op_add:
+      return fold_build2 (PLUS_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+    case isl_ast_op_sub:
+      return fold_build2 (MINUS_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+    case isl_ast_op_mul:
+      return fold_build2 (MULT_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+    case isl_ast_op_div:
+      return fold_build2 (EXACT_DIV_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+    case isl_ast_op_fdiv_q:
+      return fold_build2 (FLOOR_DIV_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+    case isl_ast_op_and:
+      return fold_build2 (TRUTH_ANDIF_EXPR, type,
+			  tree_lhs_expr, tree_rhs_expr);
+
+    case isl_ast_op_or:
+      return fold_build2 (TRUTH_ORIF_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+    case isl_ast_op_eq:
+      return fold_build2 (EQ_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+    case isl_ast_op_le:
+      return fold_build2 (LE_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+    case isl_ast_op_lt:
+      return fold_build2 (LT_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+    case isl_ast_op_ge:
+      return fold_build2 (GE_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+    case isl_ast_op_gt:
+      return fold_build2 (GT_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+    default:
+      gcc_unreachable ();
+    }
+}
+
+/* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of
+   type TYPE.  */
+
+static tree
+ternary_op_to_tree (tree type, __isl_keep isl_ast_expr *expr, ivs_params_p ip)
+{
+  gcc_assert (isl_ast_expr_get_op_type (expr) == isl_ast_op_minus);
+  isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
+  tree tree_first_expr
+    = gcc_expression_from_isl_expression (type, arg_expr, ip);
+  isl_ast_expr_free (arg_expr);
+  arg_expr = isl_ast_expr_get_op_arg (expr, 1);
+  tree tree_second_expr
+    = gcc_expression_from_isl_expression (type, arg_expr, ip);
+  isl_ast_expr_free (arg_expr);
+  arg_expr = isl_ast_expr_get_op_arg (expr, 2);
+  tree tree_third_expr
+    = gcc_expression_from_isl_expression (type, arg_expr, ip);
+  isl_ast_expr_free (arg_expr);
+  return fold_build3 (COND_EXPR, type, tree_first_expr,
+		      tree_second_expr, tree_third_expr);
+}
+
+/* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
+   type TYPE.  */
+
+static tree
+unary_op_to_tree (tree type, __isl_keep isl_ast_expr *expr, ivs_params_p ip)
+{
+  gcc_assert (isl_ast_expr_get_op_type (expr) == isl_ast_op_minus);
+  isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
+  tree tree_expr = gcc_expression_from_isl_expression (type, arg_expr, ip);
+  isl_ast_expr_free (arg_expr);
+  return fold_build1 (NEGATE_EXPR, type, tree_expr);
+}
+
+/* Converts a isl_ast_expr_op expression E with unknown number of arguments
+   to a GCC expression tree of type TYPE.  */
+
+static tree
+nary_op_to_tree (tree type, __isl_keep isl_ast_expr *expr, ivs_params_p ip)
+{
+  enum tree_code op_code;
+  switch (isl_ast_expr_get_op_type (expr))
+    {
+    case isl_ast_op_max:
+      op_code = MAX_EXPR;
+      break;
+
+    case isl_ast_op_min:
+      op_code = MIN_EXPR;
+      break;
+
+    default:
+      gcc_unreachable ();    
+    }
+  isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
+  tree res = gcc_expression_from_isl_expression (type, arg_expr, ip);
+  isl_ast_expr_free (arg_expr);
+  int i;
+  for (i = 1; i < isl_ast_expr_get_op_n_arg (expr); i++)
+    {
+      arg_expr = isl_ast_expr_get_op_arg (expr, i);
+      tree t = gcc_expression_from_isl_expression (type, arg_expr, ip);
+      res = fold_build2 (op_code, type, res, t);
+      isl_ast_expr_free (arg_expr);
+    }
+  return res;
+}
+
+
+/* Converts an isl_ast_expr_op expression E to a GCC expression tree of
+   type TYPE.  */
+
+static tree
+gcc_expression_from_isl_expr_op (tree type, __isl_keep isl_ast_expr *expr,
+				 ivs_params_p ip)
+{
+  gcc_assert (isl_ast_expr_get_type (expr) == isl_ast_expr_op);
+  switch (isl_ast_expr_get_op_type (expr))
+    {
+    /* These isl ast expressions are not supported yet.  */
+    case isl_ast_op_error:
+    case isl_ast_op_call:
+    case isl_ast_op_and_then:
+    case isl_ast_op_or_else:
+    case isl_ast_op_pdiv_q:
+    case isl_ast_op_pdiv_r:
+    case isl_ast_op_select:
+      gcc_unreachable ();
+
+    case isl_ast_op_max:
+    case isl_ast_op_min:
+      return nary_op_to_tree (type, expr, ip);
+
+    case isl_ast_op_add:
+    case isl_ast_op_sub:
+    case isl_ast_op_mul:
+    case isl_ast_op_div:
+    case isl_ast_op_fdiv_q:
+    case isl_ast_op_and:
+    case isl_ast_op_or:
+    case isl_ast_op_eq:
+    case isl_ast_op_le:
+    case isl_ast_op_lt:
+    case isl_ast_op_ge:
+    case isl_ast_op_gt:
+      return binary_op_to_tree (type, expr, ip);
+
+    case isl_ast_op_minus:
+      return unary_op_to_tree (type, expr, ip);
+
+    case isl_ast_op_cond:
+      return ternary_op_to_tree (type, expr, ip);
+
+    default:
+      gcc_unreachable ();
+    }
+
+  return NULL_TREE;
+}
+
+/* Converts a ISL AST expression E back to a GCC expression tree of
+   type TYPE.  */
+
+static tree
+gcc_expression_from_isl_expression (tree type, __isl_keep isl_ast_expr *expr,
+				    ivs_params_p ip)
+{
+  switch (isl_ast_expr_get_type (expr))
+    {
+    case isl_ast_expr_id:
+      return gcc_expression_from_isl_ast_expr_id (expr, ip);
+
+    case isl_ast_expr_int:
+      return gcc_expression_from_isl_expr_int (type, expr);
+
+    case isl_ast_expr_op:
+      return gcc_expression_from_isl_expr_op (type, expr, ip);
+
+    default:
+      gcc_unreachable ();
+    }
+
+  return NULL_TREE;
+}
+
+/* Creates a new LOOP corresponding to isl_ast_node_for.  Inserts an
+   induction variable for the new LOOP.  New LOOP is attached to CFG
+   starting at ENTRY_EDGE.  LOOP is inserted into the loop tree and
+   becomes the child loop of the OUTER_LOOP.  NEWIVS_INDEX binds
+   ISL's scattering name to the induction variable created for the
+   loop of STMT.  The new induction variable is inserted in the NEWIVS
+   vector and is of type TYPE.  */
+
+static struct loop *
+graphite_create_new_loop (edge entry_edge, __isl_keep isl_ast_node *node_for,
+			  loop_p outer, tree type, tree lb, tree ub,
+			  ivs_params_p ip)
+{
+  isl_ast_expr *for_inc = isl_ast_node_for_get_inc (node_for);
+  tree stride = gcc_expression_from_isl_expression (type, for_inc, ip);
+  isl_ast_expr_free (for_inc);
+  tree ivvar = create_tmp_var (type, "graphite_IV");
+  tree iv, iv_after_increment;
+  loop_p loop = create_empty_loop_on_edge
+    (entry_edge, lb, stride, ub, ivvar, &iv, &iv_after_increment,
+     outer ? outer : entry_edge->src->loop_father);
+
+  isl_ast_expr *for_iterator = isl_ast_node_for_get_iterator (node_for);
+  isl_id *id = isl_ast_expr_get_id (for_iterator);
+  save_isl_id_name_index (ip->ivs_params_index, isl_id_get_name (id),
+			  (ip->ivs_params_vec).length ());
+  isl_id_free (id);
+  isl_ast_expr_free (for_iterator);
+  (ip->ivs_params_vec).safe_push (iv);
+  return loop;
+}
+
+static edge
+translate_isl_ast (loop_p context_loop, __isl_keep isl_ast_node *node,
+		   edge next_e, ivs_params_p ip);
+
+/* Create the loop for a isl_ast_node_for.
+
+   - NEXT_E is the edge where new generated code should be attached.  */
+
+static edge
+translate_isl_ast_for_loop (loop_p context_loop,
+			    __isl_keep isl_ast_node *node_for, edge next_e,
+			    tree type, tree lb, tree ub,
+			    ivs_params_p ip)
+{
+  gcc_assert (isl_ast_node_get_type (node_for) == isl_ast_node_for);
+  struct loop *loop = graphite_create_new_loop (next_e, node_for, context_loop,
+						type, lb, ub, ip);
+  edge last_e = single_exit (loop);
+  edge to_body = single_succ_edge (loop->header);
+  basic_block after = to_body->dest;
+
+  /* Create a basic block for loop close phi nodes.  */
+  last_e = single_succ_edge (split_edge (last_e));
+
+  /* Translate the body of the loop.  */
+  isl_ast_node *for_body = isl_ast_node_for_get_body (node_for);
+  next_e = translate_isl_ast (loop, for_body, to_body, ip);
+  isl_ast_node_free (for_body);
+  redirect_edge_succ_nodup (next_e, after);
+  set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src);
+
+  /* TODO: Add checking for the loop parallelism.  */
+
+  return last_e;
+}
+
+/* We use this function to get the upper bound because of the form,
+   which is used by isl to represent loops:
+
+   for (iterator = init; cond; iterator += inc)
+
+   {
+
+     ...
+
+   }
+
+   The loop condition is an arbitrary expression, which contains the
+   current loop iterator.
+
+   We have to know the upper bound of the iterator to generate a loop
+   in Gimple form. It can be obtained from the special representation
+   of the loop condition, which is generated by isl,
+   if the ast_build_atomic_upper_bound option is set. In this case,
+   isl generates a loop condition that consists of the current loop
+   iterator, + an operator (< or <=) and an expression not involving
+   the iterator, which is processed and returned by this function.  */
+
+static __isl_give isl_ast_expr *
+get_upper_bound (__isl_keep isl_ast_node *node_for)
+{
+  gcc_assert (isl_ast_node_get_type (node_for) == isl_ast_node_for);
+  isl_ast_expr *for_cond = isl_ast_node_for_get_cond (node_for);
+  gcc_assert (isl_ast_expr_get_type (for_cond) == isl_ast_expr_op);
+  isl_ast_expr *res;
+  switch (isl_ast_expr_get_op_type (for_cond))
+    {
+    case isl_ast_op_le:
+      res = isl_ast_expr_get_op_arg (for_cond, 1);
+      break;
+
+    case isl_ast_op_lt:
+      {
+        // (iteraotr < ub) => (iterator <= ub - 1)
+        isl_val *one = isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond), 1);
+        isl_ast_expr *ub = isl_ast_expr_get_op_arg (for_cond, 1);
+        res = isl_ast_expr_sub (ub, isl_ast_expr_from_val (one));
+        break;
+      }
+
+    default:
+      gcc_unreachable ();
+    }
+  isl_ast_expr_free (for_cond);
+  return res;
+}
+
+/* All loops generated by create_empty_loop_on_edge have the form of
+   a post-test loop:
+
+   do
+
+   {
+     body of the loop;
+   } while (lower bound < upper bound);
+
+   We create a new if region protecting the loop to be executed, if
+   the execution count is zero (lower bound > upper bound). In this case,
+   it is subsequently removed by dead code elimination.  */
+
+static edge
+graphite_create_new_loop_guard (edge entry_edge,
+				__isl_keep isl_ast_node *node_for, tree *type,
+				tree *lb, tree *ub, ivs_params_p ip)
+{
+  gcc_assert (isl_ast_node_get_type (node_for) == isl_ast_node_for);
+  tree cond_expr;
+  edge exit_edge;
+
+  *type = *graphite_expression_size_type;
+  isl_ast_expr *for_init = isl_ast_node_for_get_init (node_for);
+  *lb = gcc_expression_from_isl_expression (*type, for_init, ip);
+  isl_ast_expr_free (for_init);
+  isl_ast_expr *upper_bound = get_upper_bound (node_for);
+  *ub = gcc_expression_from_isl_expression (*type, upper_bound, ip);
+  isl_ast_expr_free (upper_bound);
+  
+  /* When ub is simply a constant or a parameter, use lb <= ub.  */
+  if (TREE_CODE (*ub) == INTEGER_CST || TREE_CODE (*ub) == SSA_NAME)
+    cond_expr = fold_build2 (LE_EXPR, boolean_type_node, *lb, *ub);
+  else
+    {
+      tree one = (POINTER_TYPE_P (*type)
+		  ? convert_to_ptrofftype (integer_one_node)
+		  : fold_convert (*type, integer_one_node));
+      /* Adding +1 and using LT_EXPR helps with loop latches that have a
+	 loop iteration count of "PARAMETER - 1".  For PARAMETER == 0 this
+	 becomes 2^k-1 due to integer overflow, and the condition lb <= ub
+	 is true, even if we do not want this.  However lb < ub + 1 is false,
+	 as expected.  */
+      tree ub_one = fold_build2 (POINTER_TYPE_P (*type) ? POINTER_PLUS_EXPR
+				 : PLUS_EXPR, *type, *ub, one);
+
+      cond_expr = fold_build2 (LT_EXPR, boolean_type_node, *lb, ub_one);
+    }
+
+  exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
+
+  return exit_edge;
+}
+
+/* Translates an isl_ast_node_for to Gimple. */
+
+static edge
+translate_isl_ast_node_for (loop_p context_loop, __isl_keep isl_ast_node *node,
+			    edge next_e, ivs_params_p ip)
+{
+  gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_for);
+  tree type, lb, ub;
+  edge last_e = graphite_create_new_loop_guard (next_e, node, &type,
+						&lb, &ub, ip);
+  edge true_e = get_true_edge_from_guard_bb (next_e->dest);
+
+  translate_isl_ast_for_loop (context_loop, node, true_e,
+			      type, lb, ub, ip);
+  return last_e;
+}
+
+/* Translates an ISL AST node NODE to GCC representation in the
+   context of a SESE.  */
+
+static edge
+translate_isl_ast (loop_p context_loop, __isl_keep isl_ast_node *node,
+		   edge next_e, ivs_params_p ip)
+{
+  switch (isl_ast_node_get_type (node))
+    {
+    case isl_ast_node_error:
+      gcc_unreachable ();
+
+    case isl_ast_node_for:
+      return translate_isl_ast_node_for (context_loop, node,
+					 next_e, ip);
+
+    case isl_ast_node_if:
+      return next_e;
+
+    case isl_ast_node_user:
+      return next_e;
+
+    case isl_ast_node_block:
+      return next_e;
+
+    default:
+      gcc_unreachable ();
+    }
+}
+
 /* Prints NODE to FILE.  */
 
 void
@@ -65,9 +689,33 @@
   isl_printer_free (prn);
 }
 
+/* Add tree representations and names of parameters to ivs_params  */
+
+static void
+add_parameters_to_ivs_params (scop_p scop, ivs_params_p ip)
+{
+  sese region = SCOP_REGION (scop);
+  int i;
+  int nb_parameters = SESE_PARAMS (region).length ();
+  gcc_assert (nb_parameters == (short) isl_set_dim (scop->context,
+						    isl_dim_param));
+
+  for (i = 0; i < nb_parameters; i++)
+    {
+      tree param = SESE_PARAMS (region)[i];
+      const char *name = get_name (param);
+
+      if (!name)
+	name = "T";
+      save_isl_id_name_index (ip->ivs_params_index, name, i);
+      (ip->ivs_params_vec).safe_push (param);
+    }
+}
+
+
 /* Generates a build, which specifies the constraints on the parameters.  */
 
-static isl_ast_build *
+static __isl_give isl_ast_build *
 generate_isl_context (scop_p scop)
 {
   isl_set *context_isl = isl_set_params (isl_set_copy (scop->context));
@@ -77,7 +725,7 @@
 /* Generates a schedule, which specifies an order used to
    visit elements in a domain.  */
 
-static isl_union_map *
+static __isl_give isl_union_map *
 generate_isl_schedule (scop_p scop)
 {
   int i;
@@ -102,9 +750,16 @@
   return schedule_isl;
 }
 
-static isl_ast_node *
-scop_to_isl_ast (scop_p scop)
+static __isl_give isl_ast_node *
+scop_to_isl_ast (scop_p scop, ivs_params_p ip)
 {
+  /* Generate loop upper bounds that consist of the current loop iterator,
+  an operator (< or <=) and an expression not involving the iterator.
+  If this option is not set, then the current loop iterator may appear several
+  times in the upper bound. See the isl manual for more details.  */
+  isl_options_set_ast_build_atomic_upper_bound (scop->ctx, true);
+
+  add_parameters_to_ivs_params (scop, ip);
   isl_union_map *schedule_isl = generate_isl_schedule (scop);
   isl_ast_build *context_isl = generate_isl_context (scop);
   isl_ast_node *ast_isl = isl_ast_build_ast_from_schedule (context_isl,
@@ -117,21 +772,68 @@
    the given SCOP.  Return true if code generation succeeded.
 
    FIXME: This is not yet a full implementation of the code generator
-          with ISL ASTs. Generation of GIMPLE code is have to be added.  */
+          with ISL ASTs. Generation of GIMPLE code has to be completed.  */
 
 bool
 graphite_regenerate_ast_isl (scop_p scop)
 {
+  loop_p context_loop;
+  sese region = SCOP_REGION (scop);
+  ifsese if_region = NULL;
+  ast_isl_index_htab_type *ivs_params_index;
+  isl_ast_node *root_node;
+  struct ivs_params ip;
+
   timevar_push (TV_GRAPHITE_CODE_GEN);
   graphite_regenerate_error = false;
-  isl_ast_node *root_node = scop_to_isl_ast (scop);
+
+  auto_vec<tree, 10> ivs_params_vec;
+  ivs_params_index = new ast_isl_index_htab_type (10);
+  ip.ivs_params_vec = ivs_params_vec;
+  ip.ivs_params_index = ivs_params_index;
+  ip.region = region;
+
+  root_node = scop_to_isl_ast (scop, &ip);
+
   if (dump_file && (dump_flags & TDF_DETAILS))
     {
       fprintf (dump_file, "\nISL AST generated by ISL: \n");
       print_isl_ast_node (dump_file, root_node, scop->ctx);
+      fprintf (dump_file, "\n");
     }
+
+  recompute_all_dominators ();
+  graphite_verify ();
+
+  if_region = move_sese_in_condition (region);
+  sese_insert_phis_for_liveouts (region,
+				 if_region->region->exit->src,
+				 if_region->false_region->exit,
+				 if_region->true_region->exit);
+  recompute_all_dominators ();
+  graphite_verify ();
+
+  context_loop = SESE_ENTRY (region)->src->loop_father;
+
+  translate_isl_ast (context_loop, root_node, if_region->true_region->entry,
+		     &ip);
+  graphite_verify ();
+  scev_reset ();
+  recompute_all_dominators ();
+  graphite_verify ();
+
+  if (graphite_regenerate_error)
+    set_ifsese_condition (if_region, integer_zero_node);
+
+  free (if_region->true_region);
+  free (if_region->region);
+  free (if_region);
+
+  delete ivs_params_index;
+  ivs_params_index = NULL;
   isl_ast_node_free (root_node);
   timevar_pop (TV_GRAPHITE_CODE_GEN);
+  /* TODO: Add dump  */
   return !graphite_regenerate_error;
 }
 #endif

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

Index: gcc/graphite-isl-ast-to-gimple.c
===================================================================
--- gcc/graphite-isl-ast-to-gimple.c	(revision 212294)
+++ gcc/graphite-isl-ast-to-gimple.c	(working copy)
@@ -25,7 +25,14 @@
 #include <isl/map.h>
 #include <isl/union_map.h>
 #include <isl/ast_build.h>
+#if defined(__cplusplus)
+extern "C" {
 #endif
+#include <isl/val_gmp.h>
+#if defined(__cplusplus)
+}
+#endif
+#endif
 
 #include "system.h"
 #include "coretypes.h"
@@ -42,16 +49,642 @@
 #include "cfgloop.h"
 #include "tree-data-ref.h"
 #include "sese.h"
+#include "tree-ssa-loop-manip.h"
+#include "tree-scalar-evolution.h"
 
 #ifdef HAVE_cloog
 #include "graphite-poly.h"
 #include "graphite-isl-ast-to-gimple.h"
+#include "graphite-htab.h"
 
 /* This flag is set when an error occurred during the translation of
    ISL AST to Gimple.  */
 
 static bool graphite_regenerate_error;
 
+/* We always use signed 128, until isl is able to give information about
+types  */
+
+static tree *graphite_expression_size_type = &int128_integer_type_node;
+
+/* Converts a GMP constant VAL to a tree and returns it.  */
+
+static tree
+gmp_cst_to_tree (tree type, mpz_t val)
+{
+  tree t = type ? type : integer_type_node;
+  mpz_t tmp;
+
+  mpz_init (tmp);
+  mpz_set (tmp, val);
+  wide_int wi = wi::from_mpz (t, tmp, true);
+  mpz_clear (tmp);
+
+  return wide_int_to_tree (t, wi);
+}
+
+/* Verifies properties that GRAPHITE should maintain during translation.  */
+
+static inline void
+graphite_verify (void)
+{
+#ifdef ENABLE_CHECKING
+  verify_loop_structure ();
+  verify_loop_closed_ssa (true);
+#endif
+}
+
+/* Stores the INDEX in a vector for a given isl_id NAME.  */
+
+typedef struct ast_isl_name_index {
+  int index;
+  const char *name;
+  /* If free_name is set, the content of name was allocated by us and needs
+     to be freed.  */
+  char *free_name;
+} *ast_isl_name_index_p;
+
+/* Helper for hashing ast_isl_name_index.  */
+
+struct ast_isl_index_hasher
+{
+  typedef ast_isl_name_index value_type;
+  typedef ast_isl_name_index compare_type;
+  static inline hashval_t hash (const value_type *);
+  static inline bool equal (const value_type *, const compare_type *);
+  static inline void remove (value_type *);
+};
+
+/* Computes a hash function for database element E.  */
+
+inline hashval_t
+ast_isl_index_hasher::hash (const value_type *e)
+{
+  hashval_t hash = 0;
+
+  int length = strlen (e->name);
+  int i;
+
+  for (i = 0; i < length; ++i)
+    hash = hash | (e->name[i] << (i % 4));
+
+  return hash;
+}
+
+/* Compares database elements ELT1 and ELT2.  */
+
+inline bool
+ast_isl_index_hasher::equal (const value_type *elt1, const compare_type *elt2)
+{
+  return strcmp (elt1->name, elt2->name) == 0;
+}
+
+/* Free the memory taken by a ast_isl_name_index struct.  */
+
+inline void
+ast_isl_index_hasher::remove (value_type *c)
+{
+  if (c->free_name)
+    free (c->free_name);
+  free (c);
+}
+
+typedef hash_table<ast_isl_index_hasher> ast_isl_index_htab_type;
+
+/* Returns a pointer to a new element of type ast_isl_name_index_p built
+   from NAME, INDEX.  */
+
+static inline ast_isl_name_index_p
+new_ast_isl_name_index (const char *name, int index)
+{
+  ast_isl_name_index_p res = XNEW (struct ast_isl_name_index);
+  char *new_name = XNEWVEC (char, strlen (name) + 1);
+  strcpy (new_name, name);
+
+  res->name = new_name;
+  res->free_name = new_name;
+  res->index = index;
+  return res;
+}
+
+/* For a given name of the isl_id, which is stored in the isl_ast_expr EXPR_ID,
+   returns -1 if it does not correspond to any parameter, or otherwise, returns
+   the index in the PARAMS or SCATTERING_DIMENSIONS vector.  */
+
+static inline int
+ast_expr_id_to_index (__isl_keep isl_ast_expr *expr_id,
+		      ast_isl_index_htab_type *index_table)
+{
+  struct ast_isl_name_index tmp;
+  ast_isl_name_index **slot;
+
+  isl_id *tmp_isl_id = isl_ast_expr_get_id (expr_id);
+  tmp.name = isl_id_get_name (tmp_isl_id);
+  tmp.free_name = NULL;
+
+  slot = index_table->find_slot (&tmp, NO_INSERT);
+
+  isl_id_free (tmp_isl_id);
+  if (slot && *slot)
+    return (*slot)->index;
+
+  return -1;
+}
+
+/* Records in INDEX_TABLE the INDEX and for NAME.  */
+
+static inline void
+save_isl_id_name_index (ast_isl_index_htab_type *index_table,
+			const char *name, int index)
+{
+  struct ast_isl_name_index tmp;
+  ast_isl_name_index **slot;
+
+  tmp.name = name;
+  tmp.free_name = NULL;
+  slot = index_table->find_slot (&tmp, INSERT);
+
+  if (slot)
+    {
+      free (*slot);
+      *slot = new_ast_isl_name_index (name, index);
+    }
+}
+
+/* INDEX binds ISL's scattering and parameter name to the index of the tree
+   induction variable and paramatere in IVS_PARAMS_VEC.
+
+   PARAMS_INDEX binds ISL's parameter name to the index of the tree
+   parameter in PARAMS.  */
+
+typedef struct ivs_params {
+  vec<tree> ivs_params_vec;
+  ast_isl_index_htab_type *ivs_params_index;
+  sese region;
+} *ivs_params_p;
+
+static tree
+gcc_expression_from_isl_expression (tree type, __isl_keep isl_ast_expr *,
+				    ivs_params_p ip);
+
+/* Returns the tree variable from the name of isl_id, which is stored
+   in the isl_ast_expr EXPR_ID that was given in ISL representation.  */
+
+static tree
+gcc_expression_from_isl_ast_expr_id (__isl_keep isl_ast_expr *expr_id,
+				     ivs_params_p ip)
+{
+  gcc_assert (isl_ast_expr_get_type (expr_id) == isl_ast_expr_id);
+  int index;
+  gcc_assert (ip->ivs_params_vec.exists () && ip->ivs_params_index);
+  index = ast_expr_id_to_index (expr_id, ip->ivs_params_index);
+  gcc_assert (index >= 0);
+  return (ip->ivs_params_vec)[index];
+}
+
+/* Converts a isl_ast_expr_int expression E to a GCC expression tree of
+   type TYPE.  */
+
+static tree
+gcc_expression_from_isl_expr_int (tree type, __isl_keep isl_ast_expr *expr)
+{
+  gcc_assert (isl_ast_expr_get_type (expr) == isl_ast_expr_int);
+  isl_val *val = isl_ast_expr_get_val (expr);
+  mpz_t val_mpz_t;
+  mpz_init (val_mpz_t);
+  tree res;
+  if (isl_val_get_num_gmp (val, val_mpz_t) == -1)
+    res = NULL_TREE;
+  else
+    res = gmp_cst_to_tree (type, val_mpz_t);
+  isl_val_free (val);
+  mpz_clear (val_mpz_t);
+  return res;
+}
+
+/* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of
+   type TYPE.  */
+
+static tree
+binary_op_to_tree (tree type, __isl_keep isl_ast_expr *expr, ivs_params_p ip)
+{
+  isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
+  tree tree_lhs_expr = gcc_expression_from_isl_expression (type, arg_expr, ip);
+  isl_ast_expr_free (arg_expr);
+  arg_expr = isl_ast_expr_get_op_arg (expr, 1);
+  tree tree_rhs_expr = gcc_expression_from_isl_expression (type, arg_expr, ip);
+  isl_ast_expr_free (arg_expr);
+  switch (isl_ast_expr_get_op_type (expr))
+    {
+    case isl_ast_op_add:
+      return fold_build2 (PLUS_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+    case isl_ast_op_sub:
+      return fold_build2 (MINUS_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+    case isl_ast_op_mul:
+      return fold_build2 (MULT_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+    case isl_ast_op_div:
+      return fold_build2 (EXACT_DIV_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+    case isl_ast_op_fdiv_q:
+      return fold_build2 (FLOOR_DIV_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+    case isl_ast_op_and:
+      return fold_build2 (TRUTH_ANDIF_EXPR, type,
+			  tree_lhs_expr, tree_rhs_expr);
+
+    case isl_ast_op_or:
+      return fold_build2 (TRUTH_ORIF_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+    case isl_ast_op_eq:
+      return fold_build2 (EQ_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+    case isl_ast_op_le:
+      return fold_build2 (LE_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+    case isl_ast_op_lt:
+      return fold_build2 (LT_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+    case isl_ast_op_ge:
+      return fold_build2 (GE_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+    case isl_ast_op_gt:
+      return fold_build2 (GT_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+    default:
+      gcc_unreachable ();
+    }
+}
+
+/* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of
+   type TYPE.  */
+
+static tree
+ternary_op_to_tree (tree type, __isl_keep isl_ast_expr *expr, ivs_params_p ip)
+{
+  gcc_assert (isl_ast_expr_get_op_type (expr) == isl_ast_op_minus);
+  isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
+  tree tree_first_expr
+    = gcc_expression_from_isl_expression (type, arg_expr, ip);
+  isl_ast_expr_free (arg_expr);
+  arg_expr = isl_ast_expr_get_op_arg (expr, 1);
+  tree tree_second_expr
+    = gcc_expression_from_isl_expression (type, arg_expr, ip);
+  isl_ast_expr_free (arg_expr);
+  arg_expr = isl_ast_expr_get_op_arg (expr, 2);
+  tree tree_third_expr
+    = gcc_expression_from_isl_expression (type, arg_expr, ip);
+  isl_ast_expr_free (arg_expr);
+  return fold_build3 (COND_EXPR, type, tree_first_expr,
+		      tree_second_expr, tree_third_expr);
+}
+
+/* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
+   type TYPE.  */
+
+static tree
+unary_op_to_tree (tree type, __isl_keep isl_ast_expr *expr, ivs_params_p ip)
+{
+  gcc_assert (isl_ast_expr_get_op_type (expr) == isl_ast_op_minus);
+  isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
+  tree tree_expr = gcc_expression_from_isl_expression (type, arg_expr, ip);
+  isl_ast_expr_free (arg_expr);
+  return fold_build1 (NEGATE_EXPR, type, tree_expr);
+}
+
+/* Converts a isl_ast_expr_op expression E with unknown number of arguments
+   to a GCC expression tree of type TYPE.  */
+
+static tree
+nary_op_to_tree (tree type, __isl_keep isl_ast_expr *expr, ivs_params_p ip)
+{
+  enum tree_code op_code;
+  switch (isl_ast_expr_get_op_type (expr))
+    {
+    case isl_ast_op_max:
+      op_code = MAX_EXPR;
+      break;
+
+    case isl_ast_op_min:
+      op_code = MIN_EXPR;
+      break;
+
+    default:
+      gcc_unreachable ();    
+    }
+  isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
+  tree res = gcc_expression_from_isl_expression (type, arg_expr, ip);
+  isl_ast_expr_free (arg_expr);
+  int i;
+  for (i = 1; i < isl_ast_expr_get_op_n_arg (expr); i++)
+    {
+      arg_expr = isl_ast_expr_get_op_arg (expr, i);
+      tree t = gcc_expression_from_isl_expression (type, arg_expr, ip);
+      res = fold_build2 (op_code, type, res, t);
+      isl_ast_expr_free (arg_expr);
+    }
+  return res;
+}
+
+
+/* Converts an isl_ast_expr_op expression E to a GCC expression tree of
+   type TYPE.  */
+
+static tree
+gcc_expression_from_isl_expr_op (tree type, __isl_keep isl_ast_expr *expr,
+				 ivs_params_p ip)
+{
+  gcc_assert (isl_ast_expr_get_type (expr) == isl_ast_expr_op);
+  switch (isl_ast_expr_get_op_type (expr))
+    {
+    /* These isl ast expressions are not supported yet.  */
+    case isl_ast_op_error:
+    case isl_ast_op_call:
+    case isl_ast_op_and_then:
+    case isl_ast_op_or_else:
+    case isl_ast_op_pdiv_q:
+    case isl_ast_op_pdiv_r:
+    case isl_ast_op_select:
+      gcc_unreachable ();
+
+    case isl_ast_op_max:
+    case isl_ast_op_min:
+      return nary_op_to_tree (type, expr, ip);
+
+    case isl_ast_op_add:
+    case isl_ast_op_sub:
+    case isl_ast_op_mul:
+    case isl_ast_op_div:
+    case isl_ast_op_fdiv_q:
+    case isl_ast_op_and:
+    case isl_ast_op_or:
+    case isl_ast_op_eq:
+    case isl_ast_op_le:
+    case isl_ast_op_lt:
+    case isl_ast_op_ge:
+    case isl_ast_op_gt:
+      return binary_op_to_tree (type, expr, ip);
+
+    case isl_ast_op_minus:
+      return unary_op_to_tree (type, expr, ip);
+
+    case isl_ast_op_cond:
+      return ternary_op_to_tree (type, expr, ip);
+
+    default:
+      gcc_unreachable ();
+    }
+
+  return NULL_TREE;
+}
+
+/* Converts a ISL AST expression E back to a GCC expression tree of
+   type TYPE.  */
+
+static tree
+gcc_expression_from_isl_expression (tree type, __isl_keep isl_ast_expr *expr,
+				    ivs_params_p ip)
+{
+  switch (isl_ast_expr_get_type (expr))
+    {
+    case isl_ast_expr_id:
+      return gcc_expression_from_isl_ast_expr_id (expr, ip);
+
+    case isl_ast_expr_int:
+      return gcc_expression_from_isl_expr_int (type, expr);
+
+    case isl_ast_expr_op:
+      return gcc_expression_from_isl_expr_op (type, expr, ip);
+
+    default:
+      gcc_unreachable ();
+    }
+
+  return NULL_TREE;
+}
+
+/* Creates a new LOOP corresponding to isl_ast_node_for.  Inserts an
+   induction variable for the new LOOP.  New LOOP is attached to CFG
+   starting at ENTRY_EDGE.  LOOP is inserted into the loop tree and
+   becomes the child loop of the OUTER_LOOP.  NEWIVS_INDEX binds
+   ISL's scattering name to the induction variable created for the
+   loop of STMT.  The new induction variable is inserted in the NEWIVS
+   vector and is of type TYPE.  */
+
+static struct loop *
+graphite_create_new_loop (edge entry_edge, __isl_keep isl_ast_node *node_for,
+			  loop_p outer, tree type, tree lb, tree ub,
+			  ivs_params_p ip)
+{
+  isl_ast_expr *for_inc = isl_ast_node_for_get_inc (node_for);
+  tree stride = gcc_expression_from_isl_expression (type, for_inc, ip);
+  isl_ast_expr_free (for_inc);
+  tree ivvar = create_tmp_var (type, "graphite_IV");
+  tree iv, iv_after_increment;
+  loop_p loop = create_empty_loop_on_edge
+    (entry_edge, lb, stride, ub, ivvar, &iv, &iv_after_increment,
+     outer ? outer : entry_edge->src->loop_father);
+
+  isl_ast_expr *for_iterator = isl_ast_node_for_get_iterator (node_for);
+  isl_id *id = isl_ast_expr_get_id (for_iterator);
+  save_isl_id_name_index (ip->ivs_params_index, isl_id_get_name (id),
+			  (ip->ivs_params_vec).length ());
+  isl_id_free (id);
+  isl_ast_expr_free (for_iterator);
+  (ip->ivs_params_vec).safe_push (iv);
+  return loop;
+}
+
+static edge
+translate_isl_ast (loop_p context_loop, __isl_keep isl_ast_node *node,
+		   edge next_e, ivs_params_p ip);
+
+/* Create the loop for a isl_ast_node_for.
+
+   - NEXT_E is the edge where new generated code should be attached.  */
+
+static edge
+translate_isl_ast_for_loop (loop_p context_loop,
+			    __isl_keep isl_ast_node *node_for, edge next_e,
+			    tree type, tree lb, tree ub,
+			    ivs_params_p ip)
+{
+  gcc_assert (isl_ast_node_get_type (node_for) == isl_ast_node_for);
+  struct loop *loop = graphite_create_new_loop (next_e, node_for, context_loop,
+						type, lb, ub, ip);
+  edge last_e = single_exit (loop);
+  edge to_body = single_succ_edge (loop->header);
+  basic_block after = to_body->dest;
+
+  /* Create a basic block for loop close phi nodes.  */
+  last_e = single_succ_edge (split_edge (last_e));
+
+  /* Translate the body of the loop.  */
+  isl_ast_node *for_body = isl_ast_node_for_get_body (node_for);
+  next_e = translate_isl_ast (loop, for_body, to_body, ip);
+  isl_ast_node_free (for_body);
+  redirect_edge_succ_nodup (next_e, after);
+  set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src);
+
+  /* TODO: Add checking for the loop parallelism.  */
+
+  return last_e;
+}
+
+/* We use this function to get the upper bound because of the form,
+   which is used by isl to represent loops:
+
+   for (iterator = init; cond; iterator += inc)
+
+   {
+
+     ...
+
+   }
+
+   The loop condition is an arbitrary expression, which contains the
+   current loop iterator.
+
+   We have to know the upper bound of the iterator to generate a loop
+   in Gimple form. It can be obtained from the special representation
+   of the loop condition, which is generated by isl,
+   if the ast_build_atomic_upper_bound option is set. In this case,
+   isl generates a loop condition that consists of the current loop
+   iterator, + an operator (< or <=) and an expression not involving
+   the iterator, which is processed and returned by this function.  */
+
+static __isl_give isl_ast_expr *
+get_upper_bound (__isl_keep isl_ast_node *node_for)
+{
+  gcc_assert (isl_ast_node_get_type (node_for) == isl_ast_node_for);
+  isl_ast_expr *for_cond = isl_ast_node_for_get_cond (node_for);
+  gcc_assert (isl_ast_expr_get_type (for_cond) == isl_ast_expr_op);
+  isl_ast_expr *res;
+  switch (isl_ast_expr_get_op_type (for_cond))
+    {
+    case isl_ast_op_le:
+      res = isl_ast_expr_get_op_arg (for_cond, 1);
+      break;
+
+    case isl_ast_op_lt:
+      {
+        // (iteraotr < ub) => (iterator <= ub - 1)
+        isl_val *one = isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond), 1);
+        isl_ast_expr *ub = isl_ast_expr_get_op_arg (for_cond, 1);
+        res = isl_ast_expr_sub (ub, isl_ast_expr_from_val (one));
+        break;
+      }
+
+    default:
+      gcc_unreachable ();
+    }
+  isl_ast_expr_free (for_cond);
+  return res;
+}
+
+/* All loops generated by create_empty_loop_on_edge have the form of
+   a post-test loop:
+
+   do
+
+   {
+     body of the loop;
+   } while (lower bound < upper bound);
+
+   We create a new if region protecting the loop to be executed, if
+   the execution count is zero (lower bound > upper bound). In this case,
+   it is subsequently removed by dead code elimination.  */
+
+static edge
+graphite_create_new_loop_guard (edge entry_edge,
+				__isl_keep isl_ast_node *node_for, tree *type,
+				tree *lb, tree *ub, ivs_params_p ip)
+{
+  gcc_assert (isl_ast_node_get_type (node_for) == isl_ast_node_for);
+  tree cond_expr;
+  edge exit_edge;
+
+  *type = *graphite_expression_size_type;
+  isl_ast_expr *for_init = isl_ast_node_for_get_init (node_for);
+  *lb = gcc_expression_from_isl_expression (*type, for_init, ip);
+  isl_ast_expr_free (for_init);
+  isl_ast_expr *upper_bound = get_upper_bound (node_for);
+  *ub = gcc_expression_from_isl_expression (*type, upper_bound, ip);
+  isl_ast_expr_free (upper_bound);
+  
+  /* When ub is simply a constant or a parameter, use lb <= ub.  */
+  if (TREE_CODE (*ub) == INTEGER_CST || TREE_CODE (*ub) == SSA_NAME)
+    cond_expr = fold_build2 (LE_EXPR, boolean_type_node, *lb, *ub);
+  else
+    {
+      tree one = (POINTER_TYPE_P (*type)
+		  ? convert_to_ptrofftype (integer_one_node)
+		  : fold_convert (*type, integer_one_node));
+      /* Adding +1 and using LT_EXPR helps with loop latches that have a
+	 loop iteration count of "PARAMETER - 1".  For PARAMETER == 0 this
+	 becomes 2^k-1 due to integer overflow, and the condition lb <= ub
+	 is true, even if we do not want this.  However lb < ub + 1 is false,
+	 as expected.  */
+      tree ub_one = fold_build2 (POINTER_TYPE_P (*type) ? POINTER_PLUS_EXPR
+				 : PLUS_EXPR, *type, *ub, one);
+
+      cond_expr = fold_build2 (LT_EXPR, boolean_type_node, *lb, ub_one);
+    }
+
+  exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
+
+  return exit_edge;
+}
+
+/* Translates an isl_ast_node_for to Gimple. */
+
+static edge
+translate_isl_ast_node_for (loop_p context_loop, __isl_keep isl_ast_node *node,
+			    edge next_e, ivs_params_p ip)
+{
+  gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_for);
+  tree type, lb, ub;
+  edge last_e = graphite_create_new_loop_guard (next_e, node, &type,
+						&lb, &ub, ip);
+  edge true_e = get_true_edge_from_guard_bb (next_e->dest);
+
+  translate_isl_ast_for_loop (context_loop, node, true_e,
+			      type, lb, ub, ip);
+  return last_e;
+}
+
+/* Translates an ISL AST node NODE to GCC representation in the
+   context of a SESE.  */
+
+static edge
+translate_isl_ast (loop_p context_loop, __isl_keep isl_ast_node *node,
+		   edge next_e, ivs_params_p ip)
+{
+  switch (isl_ast_node_get_type (node))
+    {
+    case isl_ast_node_error:
+      gcc_unreachable ();
+
+    case isl_ast_node_for:
+      return translate_isl_ast_node_for (context_loop, node,
+					 next_e, ip);
+
+    case isl_ast_node_if:
+      return next_e;
+
+    case isl_ast_node_user:
+      return next_e;
+
+    case isl_ast_node_block:
+      return next_e;
+
+    default:
+      gcc_unreachable ();
+    }
+}
+
 /* Prints NODE to FILE.  */
 
 void
@@ -65,9 +698,33 @@
   isl_printer_free (prn);
 }
 
+/* Add tree representations and names of parameters to ivs_params  */
+
+static void
+add_parameters_to_ivs_params (scop_p scop, ivs_params_p ip)
+{
+  sese region = SCOP_REGION (scop);
+  int i;
+  int nb_parameters = SESE_PARAMS (region).length ();
+  gcc_assert (nb_parameters == (short) isl_set_dim (scop->context,
+						    isl_dim_param));
+
+  for (i = 0; i < nb_parameters; i++)
+    {
+      tree param = SESE_PARAMS (region)[i];
+      const char *name = get_name (param);
+
+      if (!name)
+	name = "T";
+      save_isl_id_name_index (ip->ivs_params_index, name, i);
+      (ip->ivs_params_vec).safe_push (param);
+    }
+}
+
+
 /* Generates a build, which specifies the constraints on the parameters.  */
 
-static isl_ast_build *
+static __isl_give isl_ast_build *
 generate_isl_context (scop_p scop)
 {
   isl_set *context_isl = isl_set_params (isl_set_copy (scop->context));
@@ -77,7 +734,7 @@
 /* Generates a schedule, which specifies an order used to
    visit elements in a domain.  */
 
-static isl_union_map *
+static __isl_give isl_union_map *
 generate_isl_schedule (scop_p scop)
 {
   int i;
@@ -102,9 +759,16 @@
   return schedule_isl;
 }
 
-static isl_ast_node *
-scop_to_isl_ast (scop_p scop)
+static __isl_give isl_ast_node *
+scop_to_isl_ast (scop_p scop, ivs_params_p ip)
 {
+  /* Generate loop upper bounds that consist of the current loop iterator,
+  an operator (< or <=) and an expression not involving the iterator.
+  If this option is not set, then the current loop iterator may appear several
+  times in the upper bound. See the isl manual for more details.  */
+  isl_options_set_ast_build_atomic_upper_bound (scop->ctx, true);
+
+  add_parameters_to_ivs_params (scop, ip);
   isl_union_map *schedule_isl = generate_isl_schedule (scop);
   isl_ast_build *context_isl = generate_isl_context (scop);
   isl_ast_node *ast_isl = isl_ast_build_ast_from_schedule (context_isl,
@@ -117,21 +781,68 @@
    the given SCOP.  Return true if code generation succeeded.
 
    FIXME: This is not yet a full implementation of the code generator
-          with ISL ASTs. Generation of GIMPLE code is have to be added.  */
+          with ISL ASTs. Generation of GIMPLE code has to be completed.  */
 
 bool
 graphite_regenerate_ast_isl (scop_p scop)
 {
+  loop_p context_loop;
+  sese region = SCOP_REGION (scop);
+  ifsese if_region = NULL;
+  ast_isl_index_htab_type *ivs_params_index;
+  isl_ast_node *root_node;
+  struct ivs_params ip;
+
   timevar_push (TV_GRAPHITE_CODE_GEN);
   graphite_regenerate_error = false;
-  isl_ast_node *root_node = scop_to_isl_ast (scop);
+
+  auto_vec<tree, 10> ivs_params_vec;
+  ivs_params_index = new ast_isl_index_htab_type (10);
+  ip.ivs_params_vec = ivs_params_vec;
+  ip.ivs_params_index = ivs_params_index;
+  ip.region = region;
+
+  root_node = scop_to_isl_ast (scop, &ip);
+
   if (dump_file && (dump_flags & TDF_DETAILS))
     {
       fprintf (dump_file, "\nISL AST generated by ISL: \n");
       print_isl_ast_node (dump_file, root_node, scop->ctx);
+      fprintf (dump_file, "\n");
     }
+
+  recompute_all_dominators ();
+  graphite_verify ();
+
+  if_region = move_sese_in_condition (region);
+  sese_insert_phis_for_liveouts (region,
+				 if_region->region->exit->src,
+				 if_region->false_region->exit,
+				 if_region->true_region->exit);
+  recompute_all_dominators ();
+  graphite_verify ();
+
+  context_loop = SESE_ENTRY (region)->src->loop_father;
+
+  translate_isl_ast (context_loop, root_node, if_region->true_region->entry,
+		     &ip);
+  graphite_verify ();
+  scev_reset ();
+  recompute_all_dominators ();
+  graphite_verify ();
+
+  if (graphite_regenerate_error)
+    set_ifsese_condition (if_region, integer_zero_node);
+
+  free (if_region->true_region);
+  free (if_region->region);
+  free (if_region);
+
+  delete ivs_params_index;
+  ivs_params_index = NULL;
   isl_ast_node_free (root_node);
   timevar_pop (TV_GRAPHITE_CODE_GEN);
+  /* TODO: Add dump  */
   return !graphite_regenerate_error;
 }
 #endif