one-time loop

[albert]

Hello,

It looks like that turning off the one-time loop elimination (by using
-otl 0) doesn't make a difference, meaning that all one-time loops are
still gotten rid of.

Does anyone know how to enable the generation of one-time loops? For
example, instead of getting the following loop:

for t=0 to T-1
for j=t+1 to t+N-1
S1(t,0,-t+j)

I want to get the loop below that has a one-time loop i:

for t=0 to T-1
for i=t to t
for j=t+1 to t+N-1
S1(t,-t+i,-t+j)

Thanks in advance.!
-Albert

[Sven Verdoolaege]

On Sat, Dec 06, 2008 at 01:34:53AM -0800, albert wrote:
>
> Hello,
>
> It looks like that turning off the one-time loop elimination (by using
> -otl 0) doesn't make a difference, meaning that all one-time loops are
> still gotten rid of.
>
> Does anyone know how to enable the generation of one-time loops? For
> example, instead of getting the following loop:

Please send me an example input and I'll have a look.

skimo

[albert]

Hi,

Below is the CLooG input I was using.

Thanks!
-Albert


#-------------------------------------

# CLooG script generated automatically by PLUTO
# language: C
c

# Context
2 4
1 1 0 -1
1 0 1 -1

1
T N

# Number of statements
2

1 # of domains
6 7
1 0 0 1 0 0 -1
1 0 0 -1 0 1 -1
1 0 1 0 0 0 0
1 0 -1 0 0 1 -1
1 1 0 0 0 0 0
1 -1 0 0 1 0 -1
0 0 0

1 # of domains
6 7
1 0 0 1 0 0 0
1 0 0 -1 0 1 -1
1 0 1 0 0 0 -1
1 0 -1 0 0 1 -1
1 1 0 0 0 0 0
1 -1 0 0 1 0 -1
0 0 0

0

# of scattering functions
2

4 11
0 1 0 0 0 -1 0 0 0 0 0
0 0 1 0 0 -1 -1 0 0 0 0
0 0 0 1 0 -1 0 -1 0 0 0
0 0 0 0 1 0 0 0 0 0 0

4 11
0 1 0 0 0 -1 0 0 0 0 0
0 0 1 0 0 -1 -1 0 0 0 0
0 0 0 1 0 -1 0 -1 0 0 -1
0 0 0 0 1 0 0 0 0 0 -1

# we will set the scattering dimension names
4
t0 t1 t2 t3

[Sven Verdoolaege]

On Mon, Dec 08, 2008 at 10:13:36AM -0800, albert wrote:
>
> Hi,
>
> Below is the CLooG input I was using.

Hmm.... seems to be a bit different from the example
in your original message.
In any case, would expect you the following output:

if (N >= 2) {
for (t0=0;t0<=T-1;t0++) {
for (t1=t0;t1<=t0;t1++) {
for (t2=t0+1;t2<=t0+N-1;t2++) {
for (i=t0;i<=t0;i++) {
for (j=0;j<=0;j++) {
for (k=-t0+t2;k<=-t0+t2;k++) {
S1 ;
}
}
}
}
}
for (t1=t0+1;t1<=t0+N-1;t1++) {
for (t2=t0+1;t2<=t0+N-1;t2++) {
for (i=t0;i<=t0;i++) {
for (j=-t0+t1;j<=-t0+t1;j++) {
for (k=-t0+t2;k<=-t0+t2;k++) {
S1 ;
}
}
}
for (i=t0;i<=t0;i++) {
for (j=-t0+t1;j<=-t0+t1;j++) {
for (k=-t0+t2-1;k<=-t0+t2-1;k++) {
S2 ;
}
}
}
}
for (t2=t0+N;t2<=t0+N;t2++) {
for (i=t0;i<=t0;i++) {
for (j=-t0+t1;j<=-t0+t1;j++) {
for (k=N-1;k<=N-1;k++) {
S2 ;
}
}
}
}
}
}
}

or this one?

if (N >= 2) {
for (t0=0;t0<=T-1;t0++) {
for (t1=t0;t1<=t0;t1++) {
for (t2=t1+1;t2<=t1+N-1;t2++) {
k = -t0+t2 ;
S1(i = t0,j = 0) ;
}
}
for (t1=t0+1;t1<=t0+N-1;t1++) {
for (t2=t0+1;t2<=t0+N-1;t2++) {
j = -t0+t1 ;
k = -t0+t2 ;
S1(i = t0) ;
j = -t0+t1 ;
k = -t0+t2-1 ;
S2(i = t0) ;
}
for (t2=t0+N;t2<=t0+N;t2++) {
j = -t0+t1 ;
k = N-1 ;
S2(i = t0) ;
}
}
}
}

skimo

[albert]

I expect to get the first code, where every statement inside the loop
nest has the same
number of surrounding loops (some loops may be one-time loops). I've
figured out a
quick solution for this, by explicitly inserting all one-time loops as
we generate CLAST
structure. It works well with what I need so far.

Anyway thanks a lot for your help, Sven.

-Albert


On Dec 16 2008, 6:33 pm, Sven Verdoolaege <skimo-cl...@kotnet.org>
wrote:

[Sven Verdoolaege]

On Sat, Feb 07, 2009 at 03:02:19PM -0800, albert wrote:
>
> I expect to get the first code, where every statement inside the loop
> nest has the same
> number of surrounding loops (some loops may be one-time loops). I've

This property holds for both versions of the code.

> figured out a
> quick solution for this, by explicitly inserting all one-time loops as
> we generate CLAST
> structure. It works well with what I need so far.

I have patches to generate both versions, I was just waiting
for a reaction from you.

skimo

[Sven Verdoolaege]

On Sun, Feb 08, 2009 at 12:35:46AM +0100, Sven Verdoolaege wrote:
> On Sat, Feb 07, 2009 at 03:02:19PM -0800, albert wrote:
> >
> > I expect to get the first code, where every statement inside the loop
> > nest has the same
> > number of surrounding loops (some loops may be one-time loops). I've
>
> This property holds for both versions of the code.

In other words, it would help if you could explain the real
reason why you prefer the first code.

skimo

[albert]

Hello Sven,

Sorry I mistakenly identified the code that I wanted to generate. It's
actually the second code (not the first).

So the code will be like this:

if (N >= 2) {
for (t0=0;t0<=T-1;t0++) {

for (t1=t0;t1<=t0;t1++) { //one-time loop

for (t2=t0+1;t2<=t0+N-1;t2++) {

S1(t0,0,-t0+t2) ;

}
}
for (t1=t0+1;t1<=t0+N-1;t1++) {
for (t2=t0+1;t2<=t0+N-1;t2++) {

S1(t0,-t0+t1,-t0+t2) ;
S2(t0,-t0+t1,-t0+t2-1) ;
}
for (t2=t0+N;t2<=t0+N;t2++) { //one-time loop
S2(t0,-t0+t1,N-1) ;
}
}
}
}

The explicitly inserted one-time loops are marked.

The reason I want to have such a code is because I want to preserve
the embedding information of the first S1 and the last S2 statements.
Without the one-time loops, the code would be like this:

if (N >= 2) {
for (t0=0;t0<=T-1;t0++) {

for (t2=t0+1;t2<=t0+N-1;t2++) {
S1(t0,0,-t0+t2) ;

}
for (t1=t0+1;t1<=t0+N-1;t1++) {
for (t2=t0+1;t2<=t0+N-1;t2++) {

S1(t0,-t0+t1,-t0+t2) ;
S2(t0,-t0+t1,-t0+t2-1) ;
}
S2(t0,-t0+t1,N-1) ;
}
}
}

With no one-time loops it's not clear how the first S1 and the last S2
statements are embedded in the 3-D iteration space. With the
equivalent value of the lower and upper bounds of the one-time loop
that is preserved by CLooG, we know precisely how the statement
instances (of the first S1 and the last S2) are located in the
iteration space.

Such information is essential for further post-process transformation.

Hope my explanation is clear. :-)

Thanks,
-Albert

[Sven Verdoolaege]

On Mon, Feb 09, 2009 at 06:13:01PM -0800, albert wrote:
> Hope my explanation is clear. :-)

I'm afraid not. You are still comparing between the current
situation and one of the proposed solutions. I want you to
compare between the two proposed solutions, the first
generating loops for all scattering dimensions and all
domain dimensions and the second only guaranteeing the
generation of loops for all scattering dimensions.

skimo

[albert]

> I'm afraid not.  You are still comparing between the current
> situation and one of the proposed solutions.  I want you to
> compare between the two proposed solutions, the first
> generating loops for all scattering dimensions and all
> domain dimensions and the second only guaranteeing the
> generation of loops for all scattering dimensions.

Yes, what I need is the second solution that you propose (i.e., to
generate loops only for all scattering dimensions). Generating loops
for all domain dimensions (in the first solution that you propose) is
not necessary.

Thanks,
-Albert

[Sven Verdoolaege]

It sounds like both forms would be acceptable to you, but that
the second form would be sufficient (apparently assuming that
generating the second form is easier). Is that correct?

skimo

[albert]

> It sounds like both forms would be acceptable to you, but that
> the second form would be sufficient (apparently assuming that
> generating the second form is easier).  Is that correct?

O yes, exactly. Both forms will work fine with me. The second form
precisely fits with what I need, but I could also use the first form
too (with an extra simple pre-process that eliminates loops that
correspond to the domain dimensions).

Thanks,
--Albert

[Sven Verdoolaege]

So, Cedric, which one do you prefer?
Patch below. Remove the "1 ||" to get the second version.

skimo

diff --git a/source/clast.c b/source/clast.c
index 91aff67..6ec0ec3 100644
--- a/source/clast.c
+++ b/source/clast.c
@@ -33,6 +33,8 @@ static int clast_binary_cmp(struct clast_binary *b1, struct clast_binary *b2);
static int clast_reduction_cmp(struct clast_reduction *r1,
struct clast_reduction *r2);

+static struct clast_expr *clast_expr_copy(struct clast_expr *e);
+
static int clast_equal_add(CloogEqualities *equal,
CloogConstraintSet *constraints,
int level, CloogConstraint constraint,
@@ -410,6 +412,36 @@ static void clast_guard_sort(struct clast_guard *g)
}


+/**
+ * Construct a (deep) copy of an expression clast.
+ */
+static struct clast_expr *clast_expr_copy(struct clast_expr *e)
+{
+ if (!e)
+ return NULL;
+ switch (e->type) {
+ case expr_term: {
+ struct clast_term* t = (struct clast_term*) e;
+ return &new_clast_term(t->val, t->var)->expr;
+ }
+ case expr_red: {
+ int i;
+ struct clast_reduction *r = (struct clast_reduction*) e;
+ struct clast_reduction *r2 = new_clast_reduction(r->type, r->n);
+ for (i = 0; i < r->n; ++i)
+ r2->elts[i] = clast_expr_copy(r->elts[i]);
+ return &r2->expr;
+ }
+ case expr_bin: {
+ struct clast_binary *b = (struct clast_binary*) e;
+ return &new_clast_binary(b->type, clast_expr_copy(b->LHS), b->RHS)->expr;
+ }
+ default:
+ assert(0);
+ }
+}
+
+
/******************************************************************************
* Equalities spreading functions *
******************************************************************************/
@@ -1145,6 +1177,30 @@ static void insert_modulo_guard(CloogConstraint upper,


/**
+ * We found an equality or a pair of inequalities identifying
+ * a loop with a single iteration, but the user wants us to generate
+ * a loop anyway, so we do it here.
+ */
+static void insert_equation_as_loop(CloogConstraint upper,
+ CloogConstraint lower, int level, struct clast_stmt ***next,
+ CloogInfos *infos)
+{
+ const char *iterator = cloog_names_name_at_level(infos->names, level);
+ struct clast_expr *e1, *e2;
+ struct clast_for *f;
+
+ e2 = clast_bound_from_constraint(upper, level, infos->names);
+ if (!cloog_constraint_is_valid(lower))
+ e1 = clast_expr_copy(e2);
+ else
+ e1 = clast_bound_from_constraint(lower, level, infos->names);
+ f = new_clast_for(iterator, e1, e2, infos->stride[level-1]);
+ **next = &f->stmt;
+ *next = &f->body;
+}
+
+
+/**
* insert_equation function:
* This function inserts an equality
* constraint according to an element in the clast.
@@ -1172,6 +1228,12 @@ static void insert_equation(CloogConstraint upper, CloogConstraint lower,
struct clast_expr *e;
struct clast_assignment *ass;

+ if (!infos->options->otl && (1 || infos->names->nb_scattering == 0 ||
+ level <= infos->names->nb_scattering)) {
+ insert_equation_as_loop(upper, lower, level, next, infos);
+ return;
+ }
+
insert_modulo_guard(upper, lower, level, next, infos);

if (cloog_constraint_is_valid(lower) ||