Re: [GSoC] generation of GCC expression trees from isl ast expressions

[Tobias Grosser <tobias at grosser dot es>]

On 23/06/2014 08:34, Roman Gareev wrote:
> Hi Tobias,
>
> I'm currently working on generation of GCC expression trees from isl
> ast expressions . Could you please answer a few questions about it?
>
> 1. How is it better to generate tree from isl_ast_expr_int? In the
> temporary variant I call isl_ast_expr_get_int to get isl_int from
> isl_ast_expr. After this, gmp_cst_to_tree (it was used in
> graphite-clast-to-gimple.c) is called to generate tree frome isl_int.
> It is possible now, because isl_int is mpz_t. However, it can be
> changed in the future, according to comments from its source code.

I think a better approach is to use isl_ast_expr_get_val() and to then
use isl_val_get_num_gmp() (see val_gmp.h). isl_int will be removed in
newer versions of isl and the above functions are the new interface to
get gmp values.

> 2. As you said in previous messages, we can always use signed 64/128,
> until isl is able to give information about types. I haven't found
> them in types of Generic
> (https://gcc.gnu.org/onlinedocs/gccint/Types.html#Types). Could they
> be declared using build_nonstandard_integer_type (128, 1)?

I assume so. However, we always want signed types, so the second
argument should be zero, no?

> 3. If I am not mistaken, the structure ivs_params from
> graphite-clast-to-gimple.c is used to store induction variables and
> parameters, rename them according to SSA form. Could it be used in
> graphite-isl-ast-to-gimple.c, too?

May be. Feel free to reuse it if you feel you need it, but don't worry
if you need different data structures. I will review its use in case you
add it.

> 4. Should we transform all isl_ast_expr_op types of isl ast
> expressions to GCC expression tree?
> For example, the following types
> are not transformed at all in Polly project: isl_ast_op_cond,
> isl_ast_op_and_then, isl_ast_op_or_else, isl_ast_op_call,
> isl_ast_op_member, isl_ast_op_access, isl_ast_op_pdiv_q,
> isl_ast_op_pdiv_r, isl_ast_op_div, isl_ast_op_fdiv_q.

We should support all that can occur. isl_ast_op_access won't ever be
built for the input we provide, similarly isl_ast_op_call, and possibly
isl_ast_op_member. The others may just be missing in Polly or may not be
needed for certain options.

For now, let's start with a basic set that we can test and extend later.

> The first draft of generation of GCC expression trees from isl ast
> expressions can be found below:

Comments inline.

> +/* 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);
> +}

OK.

> +static tree
> +gcc_expression_from_isl_expression (tree type, __isl_keep isl_ast_expr *);
> +
> +/* 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);
> +}

As discussed above avoid the use of isl_int.

> +/* 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)
> +{
> +  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);
> +  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);
> +  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);

How did you verify that the semantics of the GCC and isl expressions are
identical?

> +    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 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)
> +{
> +  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);
> +  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);
> +  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);
> +  isl_ast_expr_free (arg_expr);
> +  return fold_build3 (COND_EXPR, type, tree_first_expr,
> +		      tree_second_expr, tree_third_expr);
> +}
> +
> +/* 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)
> +{
> +  gcc_assert (isl_ast_expr_get_op_type (expr) == isl_ast_op_cond);
> +  isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
> +  tree tree_expr = gcc_expression_from_isl_expression (type, arg_expr);
> +  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)
> +{
> +  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);
> +  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);
> +      res = fold_build2 (op_code, type, res, t);
> +      isl_ast_expr_free (arg_expr);
> +    }
> +  return res;
> +}
> +/* Converts a 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)
> +{
> +  gcc_assert (isl_ast_expr_get_type (expr) == isl_ast_expr_op);
> +  switch (isl_ast_expr_get_op_type (expr))
> +    {
> +    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 ();

Can you add a message to identify and explain this unreachable?

> +    case isl_ast_op_max:
> +    case isl_ast_op_min:
> +      return nary_op_to_tree (type, expr);
> +
> +    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);
> +
> +    case isl_ast_op_minus:
> +      return unary_op_to_tree (type, expr);
> +
> +    case isl_ast_op_cond:
> +      return ternary_op_to_tree (type, expr);
> +
> +    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)
> +{
> +  switch (isl_ast_expr_get_type (expr))
> +    {
> +    case isl_ast_expr_id:
> +      gcc_unreachable ();
> +
> +    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);
> +
> +    default:
> +      gcc_unreachable ();
> +    }
> +
> +  return NULL_TREE;
> +}
> +
>  /* Prints NODE to FILE.  */
>
>  void

The kind of code you write looks very good. Now, the only question is
how can we commit it as quickly as possible. This means we need to add
just enough functionality such that we create a working subset that is
testable. Testing in gcc is a little difficult, as we commonly work
from C output to a testable executable. Maybe we should have a look at
the existing graphite test cases for -fgraphite-identify and identify
the simplest ones. Or we can even create simpler ones.

I assume the easiest one is a single loop:

for (i = 0; i < 100; i++)
  A[i] = i;

Alternatively, we could try create unit tests for the expressions.
However, I am not sure if there exists a unit-test infrastructure in
gcc.

Cheers,
Tobias