#GSoC Report I

Hi everyone!

As I told you before, my first task is to get more familiar with ISL AST generation. In this post, I'll describe a solution for it.

First of all, I added a new command line flag (fgraphite-isl-code-gen) to GCC. That was implemented with addition of the following code to gcc/common.opt:

fgraphite-isl-code-gen
Common Report Var(flag_graphite_isl_code_gen) Optimization
Enable isl code generator in Graphite

fgraphite-isl-code-gen will be used to generate new code in parallel, when it's necessary.

if (flag_graphite_isl_code_gen)
  {
    //generation of new code 
  }

Let's consider the following code: 

#include <stdio.h>
#define N 16
 
int
main1 (int n, int *a)
{
  int i, j;

  for (i = 0; i < n - 1; i++)
    for (j = 0; j < n; j++)
      a[j] = i + n;

  for (j = 0; j < n; j++)
    if (a[j] != i + n - 1)
      __builtin_abort ();

  return 0;
}

int
main ()
{
  int a[N];
  main1 (N, a);
  return 0;
} 

Graphite outlines the following SCoP from it: 

Schedule of the basic block: [n, P_37] -> { S_5[i0, i1] -> [0, i0, 0, i1, 0] }

Domain of the basic block: [n, P_37] -> { S_5[i0, i1] : exists (e0 = [(-2 + n)/4294967296], e1 = [(-1 + n)/4294967296]: i0 >= 0 and 4294967296e0 <= -2 + n and 4294967296e0 >= -4294967297 + n and 4294967296e0 <= -2 + n - i0 and i0 <= 2147483645 and i1 >= 0 and 4294967296e1 <= -1 + n and 4294967296e1 >= -4294967296 + n and 4294967296e1 <= -1 + n - i1 and i1 <= 2147483646 and n >= 1) }

After addition of a new flag I set up generation of isl_union_map, which specifies an order used to visit elements in a domain. 

static isl_union_map *
generate_isl_schedule (scop_p scop)
{
  int i;
  poly_bb_p pbb;
  isl_union_map *schedule_isl =
    isl_union_map_empty (isl_set_get_space (scop->context));

  FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb)
    {
      /* Dead code elimination: when the domain of a PBB is empty,
  don't generate code for the PBB.  */
      if (isl_set_is_empty (pbb->domain))
 continue;

      isl_map *bb_schedule = isl_map_copy (pbb->transformed);
      bb_schedule = isl_map_intersect_domain (bb_schedule,
           isl_set_copy (pbb->domain));
      schedule_isl =
        isl_union_map_union (schedule_isl,
        isl_union_map_from_map (bb_schedule));
    }
  return schedule_isl;
}

You can see that this function returns the union of all maps constructed by intersection of scattering functions' domains with corresponding domains of all basic blocks in the given SCoP.

In our case we get the following isl_union_map:

[n, P_37] -> { S_5[i0, i1] -> [0, i0, 0, i1, 0] : exists (e0 = [(-2 + n)/4294967296], e1 = [(-1 + n)/4294967296]: i0 >= 0 and 4294967296e0 <= -2 + n and 4294967296e0 >= -4294967297 + n and 4294967296e0 <= -2 + n - i0 and i0 <= 2147483645 and i1 >= 0 and 4294967296e1 <= -1 + n and 4294967296e1 >= -4294967296 + n and 4294967296e1 <= -1 + n - i1 and i1 <= 2147483646 and n >= 1) }

After this I set up generation of isl_ast_build, which specifies the constraints on the parameters.

static isl_ast_build *
generate_isl_context (scop_p scop)
{
  isl_set * context_isl = isl_set_params (isl_set_copy (scop->context));
  return isl_ast_build_from_context (context_isl);
}

Unfortunately, I haven't found any opportunity to dump isl_ast_build in ISL. That's why I'll provide a dump of universe set, which is used by isl_ast_build_from_context to generate isl_ast_build and generated from our SCoP.

[n, P_37] -> { : n <= 2147483647 and n >= 2 and P_37 <= 2147483647 and P_37 >= -2147483648 }

After this generation, I finally set up generation of a ISL AST.

static isl_ast_node *
scop_to_isl_ast (scop_p scop)
{
  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,
          schedule_isl);
  isl_ast_build_free (context_isl);
  return ast_isl;
}

Let's consider a dump of the ISL AST, which is generated in our case.

for (int c1 = 0; c1 < n - 1; c1 += 1)

  for (int c3 = 0; c3 < n; c3 += 1)

    S_5(c1, c3);

Now we can compare it with ClooG, which is also generated from our SCoP.

for (scat_1=0;scat_1<=n_7-2;scat_1++) {

  for (scat_3=0;scat_3<=n_7-1;scat_3++) {

    (scat_1,scat_3);

  }

}

You could see that they are generally similar.

After this generation, I traversed the ISL AST with the following code:

void
print_indent (int indent, isl_printer *prn)
{
  int i;
  for (i = 0; i < indent; i++)
    {
      prn = isl_printer_print_str (prn, " ");
    }
}

static void
translate_isl_ast (int indent, __isl_keep isl_ast_node *node, 
     isl_printer *prn);

/* Translates a isl_ast_node_for STMT to gimple.
   TODO: replace output to FILE with translation
   to GCC representation. */

static void
translate_isl_ast_node_for (int indent, __isl_keep isl_ast_node *node_for,
       isl_printer *prn)
{
  isl_id *id;
  const char *name;
  const char *type;
  type = isl_options_get_ast_iterator_type (isl_printer_get_ctx (prn));
  isl_ast_expr *for_iterator = isl_ast_node_for_get_iterator (node_for);
  isl_ast_expr_free (for_iterator);
  id = isl_ast_expr_get_id (for_iterator);
  name = isl_id_get_name (id);
  isl_id_free (id);
  prn = isl_printer_print_str (prn, "\n");
  print_indent (indent, prn);
  prn = isl_printer_print_str (prn, "for (");
  prn = isl_printer_print_str (prn, type);
  prn = isl_printer_print_str (prn, " ");
  prn = isl_printer_print_str (prn, name);
  prn = isl_printer_print_str (prn, " = ");
  isl_ast_expr *for_init = isl_ast_node_for_get_init (node_for);
  prn = isl_printer_print_ast_expr (prn, for_init);
  isl_ast_expr_free (for_init);
  prn = isl_printer_print_str (prn, "; ");
  isl_ast_expr *for_cond = isl_ast_node_for_get_cond (node_for);
  prn = isl_printer_print_ast_expr (prn, for_cond);
  isl_ast_expr_free (for_cond);
  prn = isl_printer_print_str (prn, "; ");
  prn = isl_printer_print_str (prn, name);
  prn = isl_printer_print_str (prn, " += ");
  isl_ast_expr *for_inc = isl_ast_node_for_get_inc (node_for);
  prn = isl_printer_print_ast_expr (prn, for_inc);
  isl_ast_expr_free (for_inc);
  prn = isl_printer_print_str (prn, ")");
  isl_ast_node *for_body = isl_ast_node_for_get_body (node_for);
  translate_isl_ast (indent + 2, for_body, prn);
  isl_ast_node_free (for_body);
}

/* Translates a clast guard statement STMT to gimple.
   TODO: replace output to FILE with translation
   to GCC representation. */

static void
translate_isl_ast_node_if (int indent, __isl_keep isl_ast_node *node_if,
      isl_printer *prn)
{
  prn = isl_printer_print_str (prn, "\n");
  print_indent (indent, prn);
  prn = isl_printer_print_str (prn, "if (");
  isl_ast_expr *if_cond = isl_ast_node_if_get_cond (node_if);
  prn = isl_printer_print_ast_expr (prn, if_cond);
  isl_ast_expr_free (if_cond);
  prn = isl_printer_print_str (prn, ")");
  isl_ast_node *if_then = isl_ast_node_if_get_then (node_if);
  translate_isl_ast (indent + 2, if_then, prn);
  isl_ast_node_free (if_then);
  if (isl_ast_node_if_has_else (node_if))
    {
      prn = isl_printer_print_str (prn, "else");
      isl_ast_node *if_else = isl_ast_node_if_get_else(node_if);
      translate_isl_ast (indent + 2, if_else, prn);
      isl_ast_node_free (if_else);
    }
}

/* Translates a clast guard statement STMT to gimple.
   TODO: replace output to FILE with translation
   to GCC representation. */

static void
translate_isl_ast_node_user (int indent, __isl_keep isl_ast_node *node_user,
        isl_printer *prn)
{
  prn = isl_printer_print_str (prn, "\n");
  prn = isl_printer_set_indent (prn, indent);
  prn = isl_printer_print_ast_node (prn, node_user);
}

/* Translates a clast guard statement STMT to gimple.
   TODO: replace output to FILE with translation
   to GCC representation. */

static void
translate_isl_ast_node_block (int indent, __isl_keep isl_ast_node *node_block,
         isl_printer *prn)
{
  isl_ast_node_list *node_list = isl_ast_node_block_get_children (node_block);
  int i;
  for (i = 0; i < isl_ast_node_list_n_ast_node (node_list); i++)
    {
      translate_isl_ast (indent + 2, 
    isl_ast_node_list_get_ast_node (node_list, i), prn);
    }
  isl_ast_node_list_free (node_list);
}

/* Translates a ISL AST node NODE to GCC representation in the
   context of a SESE.
   TODO: replace output to FILE with translation
   to GCC representation. */

static void
translate_isl_ast (int indent, __isl_keep isl_ast_node *node, isl_printer *prn)
{
  switch (isl_ast_node_get_type (node))
    {
    case isl_ast_node_error:
      gcc_unreachable ();

    case isl_ast_node_for:
      translate_isl_ast_node_for (indent, node, prn);
      return;

    case isl_ast_node_if:
      translate_isl_ast_node_if (indent, node, prn);
      return;

    case isl_ast_node_user:
      translate_isl_ast_node_user (indent, node, prn);
      return;

    case isl_ast_node_block:
      translate_isl_ast_node_block (indent, node, prn);
      return;

    default:
      gcc_unreachable ();
    }
}

/* Prints NODE to FILE.  */

void
print_isl_ast_node (FILE *file, __isl_keep isl_ast_node *node, 
      __isl_keep isl_ctx *ctx)
{
  isl_printer *prn = isl_printer_to_file (ctx, file);
  prn = isl_printer_set_output_format (prn, ISL_FORMAT_C);
  prn = isl_printer_print_ast_node (prn, node);
  isl_printer_free (prn);
}

You could make sure, that traversing is correct by comparing it with the dump of the ISL AST.

for (int c1 = 0; c1 < n - 1; c1 += 1)

  for (int c3 = 0; c3 < n; c3 += 1)

    S_5(c1, c3);

You can find all the mentioned changes in the following patch, wich can be found at the following link http://gcc.1065356.n5.nabble.com/attachment/1037729/0/patch