Saturday, May 31, 2014

#GSoC Report II

Hi everyone!

As I told you before, my second task is to get more familiar with CLooG generation. In this post, I'll consider an example of it.

If we give the following code as an input to Graphite
#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 will outline the following SCoP:

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) }

Let's generate a CLoogInput
static CloogInput *
generate_cloog_input (scop_p scop)
{
  CloogUnionDomain *union_domain;
  CloogInput *cloog_input;
  CloogDomain *context;

  union_domain = build_cloog_union_domain (scop);
  context = cloog_domain_from_isl_set (isl_set_copy (scop->context));
  cloog_input = cloog_input_alloc (context, union_domain);

  return cloog_input;
}

A CloogInput structure represents the input to CLooG. It is essentially a CloogUnionDomain along with a context CloogDomain. CloogDomain is an type representing a polyhedral domain (a union of polyhedra). “generate_cloog_input()” transforms type of scop's context to type, which is appropriate for CloogInput. “build_cloog_union_domain” is used for generation of CloogUnionDomain, which contains all CloogUnion corresponding to all basic blocks in the given scop. 

static CloogUnionDomain *
build_cloog_union_domain (scop_p scop)
{
  int i;
  poly_bb_p pbb;
  CloogUnionDomain *union_domain =
    cloog_union_domain_alloc (scop_nb_params (scop));

  FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb)
    {
      CloogDomain *domain;
      CloogScattering *scattering;

      /* 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;

      domain = cloog_domain_from_isl_set (isl_set_copy (pbb->domain));
      scattering = cloog_scattering_from_isl_map
 (isl_map_copy (pbb->transformed));

      union_domain = cloog_union_domain_add_domain (union_domain, "", domain,
          scattering, pbb);
    }

  return union_domain;
}

Let's pass the previously generated cloog_input to to the CLooG code generator
static struct clast_stmt *
scop_to_clast (scop_p scop)
{
  CloogInput *cloog_input;
  struct clast_stmt *clast;
  CloogOptions *options =  cloog_options_malloc (cloog_state);
  options->language = CLOOG_LANGUAGE_C;
  cloog_input = generate_cloog_input (scop);

  clast = cloog_clast_create_from_input (cloog_input, options);

  cloog_options_free (options);
  return clast;
}

We can produce the following dump now:

for (c2=0;c2<=M-2;c2++) {
  for (c4=0;c4<=M-1;c4++) {
    (c2,c4);
  }
}

In CLooG An AST constructed by cloog_clast_create_from_input has the type clast_stmt, which represents a linked list of statements”, which allows to traverse an AST tree. Let's do this
static void
translate_clast (CloogOptions *options, int indent,
    FILE *file, struct clast_stmt *);


static void
translate_clast_for (CloogOptions *options, int indent,
        FILE *file, struct clast_for *stmt)
{
  fprintf (file, "%*s", indent, "");
  fprintf(file, "for (");
  if (stmt->LB)
    {
      fprintf(file, "%s=LB", stmt->iterator);
    }
  fprintf(file,";");
  if (stmt->UB)
    {
      fprintf (file,"%s<=UB", stmt->iterator);
    }
  if (cloog_int_gt_si(stmt->stride, 1))
    {
      fprintf (file,";%s+=", stmt->iterator);
      cloog_int_print (file, stmt->stride);
      fprintf (file, ") \n");
    }
  else
    fprintf(file, ";%s++) \n", stmt->iterator);
  translate_clast (options, indent + 2, file, stmt->body);
}

static void
translate_clast_guard (CloogOptions *options, int indent,
   FILE *file, struct clast_guard *stmt)
{
  fprintf (file, "%*s", indent, "");
  fprintf(file,"if ");
  if (stmt->n > 1)
    fprintf(file, "(");
  int i;
  for (i = 0; i < stmt->n; i++)
  {
    if (i > 0)
    {
      fprintf(file, " && ");
    }
    fprintf(file, "(eq)");
  }
  if (stmt->n > 1)
    fprintf(file, ")");
  translate_clast (options, indent + 2, file, stmt->then);
}

static void
translate_clast_user (int indent, FILE *file,  struct clast_stmt *stmt)
{
  fprintf (file, "%*s", indent, "");
  print_clast_stmt (file, stmt);
}

static void
translate_clast_assignment (int indent, FILE *file,  struct clast_stmt *stmt)
{
  fprintf (file, "%*s", indent, "");
  print_clast_stmt (file, stmt);
}


static void
translate_clast (CloogOptions *options, int indent,
    FILE *file, struct clast_stmt *stmt)
{
  if (!stmt)
    return;

  if (CLAST_STMT_IS_A (stmt, stmt_root))
    ; /* Do nothing.  */

  else if (CLAST_STMT_IS_A (stmt, stmt_user))
    translate_clast_user (indent, file, stmt);

  else if (CLAST_STMT_IS_A (stmt, stmt_for))
    translate_clast_for (options, indent, file, (struct clast_for *) stmt);

  else if (CLAST_STMT_IS_A (stmt, stmt_guard))
    translate_clast_guard (options, indent, file, (struct clast_guard *) stmt);

  else if (CLAST_STMT_IS_A (stmt, stmt_block))
    translate_clast (options, indent, file, ((struct clast_block *) stmt)->body);

  else if (CLAST_STMT_IS_A (stmt, stmt_ass))
    translate_clast_assignment (indent, file, stmt);
  else
    gcc_unreachable ();

  translate_clast (options, indent, file, stmt->next);
}
Finally we get the following

for (c2=LB;c2<=UB;c2++) 
  for (c4=LB;c4<=UB;c4++) 
    (c2,c4);

Sunday, May 25, 2014

#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

Thursday, May 1, 2014

My GSOC 2014 Proposal: Integration of ISL code generator into Graphite

Hi everyone! To start this blog I’m posting my accepted proposal on Google Summer of Code.  From this day forward I will post the updates of the project after reaching my mile stones. Maybe It would be useful for everyone who wants to know about the code generation of Graphite through CLooG and the Integer Set Library.

Short description: For a long period of time Graphite was relying on CLooG to produce GIMPLE code. The Integer Set Library (ISL) recently became available in this project to be used as a back end of CLooG. ISL is nowadays mature enough to replace CLooG with own code generation that sometimes is better. This project aims to integrate ISL code generation into Graphite and avoid necessity of CLooG in GCC.

Student: Roman Gareev
Email Address: gareevroman at gmail dot com

1 Summary


ISL is nowadays mature enough to replace CLooG with own code generation that sometimes is better. Our project aims to integrate ISL code generation into Graphite and avoid necessity of CLooG in GCC.


2 The project


For a long period of time Graphite was relying on CLooG [1] to produce GIMPLE code. The Integer Set Library (ISL) [2] recently became available in this project to be used as a back end of CLooG. ISL is nowadays mature enough to replace CLooG with own code generation that sometimes is better. Our proposal aims to integrate ISL code generation into Graphite and avoid necessity of CLooG in GCC.


Graphite uses the polyhedral model as a basic model for loop optimization and parallelization. Subsequently, it uses CLooG to perform code generation for loops represented in the polyhedral model. Graphite is now able to use ISL back end of CLooG for generating code out of polyhedral program representation.


The goal of our project is to totally replace CLooG with ISL to perform code generation. ISL will generate ISL AST, which is a simple abstract-syntax tree containing only loops, conditions, and statements. GIMPLE code corresponding to transformed polyhedral model will be then regenerated from this representation.

3 Benefits for Graphite

• This project could help to eliminate CLooG library installation dependency from GCC,

• ISL code generator has already shown compile-time performance improvements [3] in Polly project [4]. There is a possibility of the performance improvement in Graphite,

• ISL code generator supports unrolling, full/partial tile separation, fine-grained code size adjustments. It allows to improve quality of generated code.

4 Details about the project

In source-to-source polyhedral compilers, the code generation pass is the last one, generating the new loop structures to scan statement instances in the order defined by the modified schedule. CLooG is used in graphite as the major component of code generation.

In Graphite it is not the syntactical source code that is the final result of the pass: graphite should be able to regenerate the GIMPLE code. Furthermore, the generated GIMPLE code has to be reinserted back into the CFG, respecting the SSA form invariants and passed to the further passes after Graphite.

Graphite uses CLooG as the major component of this code generation. CLooG generates an internal representation called CLAST which is a simple abstract-syntax tree containing only loops, conditions, and statements. In our case statements are replaced with basic blocks.

CLooG is fed by the polyhedral representation (GPOLY) and is asked to generate a CLAST through GLooG (GIMPLE Loop Generator) “scop_to_clast()”. The nodes of the abstract-syntax tree are pointers to original basic blocks. Depending on the loop transformations, the basic blocks might be rescheduled, moved to other loops, or even replicated (when performing a transformation). The final effect is represented in the CLAST. The CLAST tree is traversed through GLooG “translate_clast()” and the basic blocks are put into the their new positions in the GIMPLE CFG, loop structures are regenerated and some basic blocks are replicated.

Even in the case of the identity transformation (no schedule modification), the newly generated loops according to the CLAST tree have the new induction variables. All the basic blocks belonging to a SCoP have to be scanned, and the old induction variables have to be replaced with new induction variables.

ISL will generate ISL AST, which is a simple abstract-syntax tree containing only loops, conditions, and statements. Its statements also will be pointers to original basic blocks. After this it will be traversed and transformed into the GIMPLE CFG.

An API introduced by ISL for code generation is generally similar to the API introduced by CLooG, but has differences. In this section, we present a list of some differences between them:

• An AST generation:
In CLooG an AST can be constructed using “cloog_clast_create_from_input()”. “cloog_clast_create_from_input()” must be called with two arguments. The first of them influences on constructed AST and has type of pointer to CloogInput. A CloogInput structure represents the input to CLooG. It is essentially a CloogUnionDomain along with a context CloogDomain. CloogDomain is an type representing a polyhedral domain (a union of polyhedra).
Graphite uses “cloog_clast_create_from_input()” to generate CLAST representation and “generate_cloog_input()” to create its first argument mentioned previously. “generate_cloog_input()” transforms type of scop's context to type, which is appropriate for CloogInput. “build_cloog_union_domain” is used for generation of CloogUnionDomain, which contains all CloogUnion corresponding to all basic blocks in the given scop.

In ISL an AST can be constructed using “isl_ast_build_ast_from_schedule”. “isl_ast_build_ast_from_schedule” also must be called with two arguments. The first of them must have isl_ast_build type, which speciļ¬es the context and can be created using isl_ast_build_from_context. The second argument of “isl_ast_build_ast_from_schedule” must have isl_union_map type. In particular, given a isl_union_map, an AST is generated that visits all the elements in the domain of the isl_union_map according to the lexicographic order of the corresponding image element(s).

In our case the second argument can be the union of all maps constructed by intersection of scattering functions' domains with corresponding domains of all basic blocks in the given scop.

• The AST format:
In CLooG An AST constructed by cloog_clast_create_from_input has the type clast_stmt, which represents a linked list of “statements”, which allows to traverse an AST tree.
The following statement types are defined by CLooG: clast_root, clast_assignment, clast_block, clast_user_stmt, clast_for, clast_guard.
The clast_stmt returned by cloog_clast_create is a clast_root. It contains a placeholder for all the variable names that appear in the AST and a (list of) nested statement(s).

A clast_assignment assigns the value given by the clast_expr RHS to a variable named LHS. 
A clast_block groups a list of statements into one statement. 
A clast_user_stmt represents a call to a statement specified by the user. 
A clast_for represents a for loop. 

A clast_guard represents the guarded execution of the then (list of) statement(s).

ISL has similar representation of an AST and own mechanism to traverse it.
In ISL the type of an AST node is one of isl_ast_node_for, isl_ast_node_if, isl_ast_node_block or isl_ast_node_user.
An isl_ast_node_for represents a for node. 
An isl_ast_node_if represents an if node. 
An isl_ast_node_block represents a compound node. 
An isl_ast_node_user represents an expression statement. An expression statement typically corresponds to a domain element, i.e., one of the elements that is visited by the AST.
ISL uses the following functions to get child nodes of AST tree: “isl_ast_node_for_get_body()”, “isl_ast_node_if_get_then()”, “isl_ast_node_if_get_else()”, “isl_ast_node_block_get_children()”.

• Timeline

◦ 19 May – 25 May: Get more familiar with ISL AST generation: generate an isl_ast_build and an isl_union_map, pass them to the ISL code generator, traverse the resulting AST and dump it to a file.
◦ 26 May – 31 May: Get more familiar with CLooG generation: generate a CloogInput, pass it to the CLooG code generator, traverse the resulting AST and dump it to a file.
 ◦ 1 June – 15 June: Vacation (I have some university exams).
◦ 16 June – 22 June: Add ISL AST generation to Graphite and dumps generated ISL AST to a file.
◦ 23 June – 29 June: Testing and fixing bugs.
◦ 30 June – 6 July: Begin generation of Gimple from ISL AST: remove CLAST generation, generate loops without any basic blocks, extend to generation of loops with a single basic block.
◦ 7 July – 13 July: Testing and fixing bugs.
◦ 14 July – 20 July: Extension to generation of loops with nested loops and if expressions.
◦ 21 July – 27 July: Testing and fixing bugs.
◦ 28 July – 3 August: Adding new tests, removing CLooG library installation dependency from GCC.
◦ 4 August – 17 August: Testing and fixing bugs, writing documentation.

5 Required deliverables

• Graphite must become fully independent of CLooG library,
• GCC should be able to bootstrap,
• Pass regression tests,
• Add new tests to testsuite.

6 Nice to have

According to advancement in work on the integration and results, we want to :
• Make execution-time and compile-time performance comparisons between CLooG and ISL code generation in Graphite.
• Use the full/partial tile separation for the tiles generated by the isl scheduler.

Experience

• Experience in fixing PR59586 of Graphite project [10], [7], [8], [9].
• Experience in replacement of GCC code. I switched the resolution strategy of a hash table used in the symbol table of identifiers from open addressing to separate chaining with linked list [5], [6].
• Academic experience in writing compilers using ANTLR [11], Flex [12], Bison [13].

Ref:

[1] http://www.cloog.org/
[2] http://isl.gforge.inria.fr/
[3] http://www.marshut.com/whwvq/performance-comparison-between-cloog-and-isl-code-generation.html
[4] http://polly.llvm.org/index.html
[5] http://gcc.gnu.org/ml/gcc-patches/2013-10/msg01653.html
[6] http://gcc.gnu.org/ml/gcc-patches/2013-11/msg00265.html
[7] http://gcc.gnu.org/ml/gcc-patches/2014-03/msg00475.html
[8] http://gcc.gnu.org/ml/gcc-patches/2014-03/msg00462.html
[9] http://gcc.gnu.org/ml/gcc-patches/2014-03/msg00463.html
[10] http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59586
[11] http://www.antlr.org/
[12] http://flex.sourceforge.net/
[13] http://www.gnu.org/software/bison/