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

[Tobias Grosser <tobias at grosser dot es>]

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