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