#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);