Skip to content

Commit

Permalink
detect all one-time loops and convert them to an assignment followed …
Browse files Browse the repository at this point in the history 
…by a guard

If the lower and upper bound of a loop are exactly the same, then
CLooG would already convert the loop to an assignment to the loop
iterator.  However, even if the bounds are different, the loop
may still be executed at most once and then it is better
to generate an assignment of the lower bound to the iterator
followed by a comparison with the upper bound.
One advantage is that the result can be handled by if-conversion.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
  • Loading branch information
Sven Verdoolaege committed Jul 15, 2010
1 parent 4171187 commit 7a10c39
Show file tree
Hide file tree
Showing 8 changed files with 136 additions and 39 deletions.
1 change: 1 addition & 0 deletions include/cloog/domain.h
View file
Original file line number Diff line number Diff line change
Expand Up @@ -119,6 +119,7 @@ CloogDomain * cloog_domain_extend(CloogDomain *, int);
int cloog_domain_never_integral(CloogDomain *) ;
void cloog_domain_stride(CloogDomain *, int, cloog_int_t *, cloog_int_t *);
int cloog_domain_can_stride(CloogDomain *domain, int level);
int cloog_domain_is_otl(CloogDomain *domain, int level);
CloogDomain * cloog_domain_stride_lower_bound(CloogDomain *domain, int level,
cloog_int_t stride, cloog_int_t offset);
int cloog_domain_lazy_disjoint(CloogDomain *, CloogDomain *) ;
Expand Down
1 change: 1 addition & 0 deletions include/cloog/loop.h
View file
Original file line number Diff line number Diff line change
Expand Up @@ -63,6 +63,7 @@ struct cloogloop
{
CloogState *state; /**< State. */
CloogDomain * domain ; /**< The iteration domain. */
int otl; /**< Loop is executed at most once. */
cloog_int_t stride; /**< The stride for the corresponding iterator
* (filled only after loop generation).
*/
Expand Down
55 changes: 52 additions & 3 deletions source/clast.c
View file
Original file line number Diff line number Diff line change
Expand Up @@ -53,7 +53,7 @@ static int insert_modulo_guard(CloogConstraint *upper,
struct clast_stmt ***next, CloogInfos *infos);
static int insert_equation(CloogConstraint *upper, CloogConstraint *lower,
int level, struct clast_stmt ***next, CloogInfos *infos);
static int insert_for(CloogConstraintSet *constraints, int level,
static int insert_for(CloogConstraintSet *constraints, int level, int otl,
struct clast_stmt ***next, CloogInfos *infos);
static void insert_block(CloogBlock *block, int level,
struct clast_stmt ***next, CloogInfos *infos);
Expand Down Expand Up @@ -1454,6 +1454,52 @@ static void insert_otl_for(CloogConstraintSet *constraints, int level,
}


/**
* Insert a loop that is executed at most once as an assignment followed
* by a guard. In particular, the loop
*
* for (i = e1; i <= e2; ++i) {
* S;
* }
*
* is generated as
*
* i = e1;
* if (i <= e2) {
* S;
* }
*
*/
static void insert_guarded_otl_for(CloogConstraintSet *constraints, int level,
struct clast_expr *e1, struct clast_expr *e2,
struct clast_stmt ***next, CloogInfos *infos)
{
const char *iterator;
struct clast_assignment *ass;
struct clast_guard *guard;

iterator = cloog_names_name_at_level(infos->names, level);

if (infos->options->block) {
struct clast_block *b = new_clast_block();
**next = &b->stmt;
*next = &b->body;
}
ass = new_clast_assignment(iterator, e1);
**next = &ass->stmt;
*next = &(**next)->next;

guard = new_clast_guard(1);
guard->eq[0].sign = -1;
guard->eq[0].LHS = &new_clast_term(infos->state->one,
&new_clast_name(iterator)->expr)->expr;
guard->eq[0].RHS = e2;

**next = &guard->stmt;
*next = &guard->then;
}


/**
* insert_for function:
* This function inserts a for loop in the clast.
Expand All @@ -1475,11 +1521,12 @@ static void insert_otl_for(CloogConstraintSet *constraints, int level,
* and then reattach the guard inside the loop.
* - constraints contains all constraints,
* - level is the column number of the element in matrix we want to use,
* - otl is set if the loop is executed at most once,
* - the infos structure gives the user some options about code printing,
* the number of parameters in matrix (nb_par), and the arrays of iterator
* names and parameters (iters and params).
*/
static int insert_for(CloogConstraintSet *constraints, int level,
static int insert_for(CloogConstraintSet *constraints, int level, int otl,
struct clast_stmt ***next, CloogInfos *infos)
{
const char *iterator;
Expand All @@ -1502,6 +1549,8 @@ static int insert_for(CloogConstraintSet *constraints, int level,
if (e1 && e2 && infos->options->otl && clast_expr_equal(e1, e2)) {
free_clast_expr(e2);
insert_otl_for(constraints, level, e1, next, infos);
} else if (otl) {
insert_guarded_otl_for(constraints, level, e1, e2, next, infos);
} else {
struct clast_for *f;
iterator = cloog_names_name_at_level(infos->names, level);
Expand Down Expand Up @@ -1630,7 +1679,7 @@ static void insert_loop(CloogLoop * loop, int level,
level, &j, infos->names->nb_parameters))) {
empty_loop = !insert_equation(i, j, level, next, infos);
} else
empty_loop = !insert_for(constraints, level, next, infos);
empty_loop = !insert_for(constraints, level, loop->otl, next, infos);
}

if (!empty_loop) {
Expand Down
25 changes: 25 additions & 0 deletions source/isl/domain.c
View file
Original file line number Diff line number Diff line change
Expand Up @@ -616,6 +616,31 @@ int cloog_domain_never_integral(CloogDomain * domain)
}


/**
* Check whether the loop at "level" is executed at most once.
* We construct a map that maps all remaining variables to this iterator
* and check whether this map is single valued.
*
* Alternatively, we could have mapped the domain through a mapping
* [p] -> { [..., i] -> [..., i'] : i' > i }
* and then taken the intersection of the original domain and the transformed
* domain. If this intersection is empty, then the corresponding
* loop is executed at most once.
*/
int cloog_domain_is_otl(CloogDomain *domain, int level)
{
int otl;
isl_map *map;

map = isl_map_from_domain(isl_set_copy(&domain->set));
map = isl_map_move_dims(map, isl_dim_out, 0, isl_dim_in, level - 1, 1);
otl = isl_map_is_single_valued(map);
isl_map_free(map);

return otl;
}


/**
* cloog_domain_stride function:
* This function finds the stride imposed to unknown with the column number
Expand Down
60 changes: 36 additions & 24 deletions source/loop.c
View file
Original file line number Diff line number Diff line change
Expand Up @@ -293,6 +293,7 @@ CloogLoop *cloog_loop_read(CloogState *state,
nb_iterators = cloog_domain_dimension(loop->domain);
else
nb_iterators = 0 ;
loop->otl = 0;
/* stride is initialized to 1. */
cloog_int_init(loop->stride);
cloog_int_set_si(loop->stride, 1);
Expand Down Expand Up @@ -345,6 +346,7 @@ CloogLoop *cloog_loop_malloc(CloogState *state)
loop->usr = NULL;
loop->inner = NULL ;
loop->next = NULL ;
loop->otl = 0;
cloog_int_init(loop->stride);
cloog_int_set_si(loop->stride, 1);
cloog_int_init(loop->offset);
Expand All @@ -364,7 +366,7 @@ CloogLoop *cloog_loop_malloc(CloogState *state)
* - November 21th 2005: use of cloog_loop_malloc.
*/
CloogLoop *cloog_loop_alloc(CloogState *state,
CloogDomain *domain, cloog_int_t stride, cloog_int_t offset,
CloogDomain *domain, int otl, cloog_int_t stride, cloog_int_t offset,
CloogBlock *block, CloogLoop *inner, CloogLoop *next)
{ CloogLoop * loop ;

Expand All @@ -374,6 +376,7 @@ CloogLoop *cloog_loop_alloc(CloogState *state,
loop->block = block ;
loop->inner = inner ;
loop->next = next ;
loop->otl = otl;
cloog_int_set(loop->stride, stride);
cloog_int_set(loop->offset, offset);

Expand Down Expand Up @@ -442,8 +445,8 @@ CloogLoop * cloog_loop_copy(CloogLoop * source)
if (source != NULL)
{ domain = cloog_domain_copy(source->domain) ;
block = cloog_block_copy(source->block) ;
loop = cloog_loop_alloc(source->state, domain, source->stride,
source->offset, block, NULL, NULL);
loop = cloog_loop_alloc(source->state, domain, source->otl,
source->stride, source->offset, block, NULL, NULL);
loop->usr = source->usr;
loop->inner = cloog_loop_copy(source->inner) ;
loop->next = cloog_loop_copy(source->next) ;
Expand Down Expand Up @@ -487,7 +490,7 @@ CloogLoop ** start, ** now, * loop ;
domain = cloog_domain_cut_first(domain, &rest);

/* This first element is the first of the list of disjoint polyhedra. */
sep = cloog_loop_alloc(loop->state, domain, loop->state->one,
sep = cloog_loop_alloc(loop->state, domain, 0, loop->state->one,
loop->state->zero, loop->block, loop->inner, NULL);
cloog_loop_add(start,now,sep) ;

Expand All @@ -510,7 +513,7 @@ CloogLoop ** start, ** now, * loop ;
block = cloog_block_copy(loop->block) ;

sep = cloog_loop_alloc(loop->state, cloog_domain_copy(domain),
loop->state->one, loop->state->zero,
0, loop->state->one, loop->state->zero,
block, inner, NULL);
/* domain can be an union too. If so: recursion. */
if (cloog_domain_isconvex(domain))
Expand Down Expand Up @@ -591,7 +594,7 @@ CloogLoop *cloog_loop_restrict(CloogLoop *loop, CloogDomain *context)
}
else {
new_loop = cloog_loop_alloc(loop->state, new_domain,
loop->state->one, loop->state->zero,
0, loop->state->one, loop->state->zero,
loop->block, loop->inner, NULL);
return(new_loop) ;
}
Expand Down Expand Up @@ -649,15 +652,15 @@ CloogLoop * cloog_loop_project(CloogLoop * loop, int level)
CloogDomain * new_domain ;
CloogLoop * new_loop, * copy ;

copy = cloog_loop_alloc(loop->state, loop->domain, loop->stride, loop->offset,
loop->block, loop->inner, NULL);
copy = cloog_loop_alloc(loop->state, loop->domain, loop->otl, loop->stride,
loop->offset, loop->block, loop->inner, NULL);

if (cloog_domain_dimension(loop->domain) == level)
new_domain = cloog_domain_copy(loop->domain) ;
else
new_domain = cloog_domain_project(loop->domain, level);

new_loop = cloog_loop_alloc(loop->state, new_domain, loop->state->one,
new_loop = cloog_loop_alloc(loop->state, new_domain, 0, loop->state->one,
loop->state->zero, NULL, copy, NULL);

return(new_loop) ;
Expand Down Expand Up @@ -820,7 +823,7 @@ CloogLoop * cloog_loop_separate(CloogLoop * loop)

UQ = cloog_domain_copy(loop->domain) ;
domain = cloog_domain_copy(loop->domain) ;
res = cloog_loop_alloc(loop->state, domain, loop->state->one,
res = cloog_loop_alloc(loop->state, domain, 0, loop->state->one,
loop->state->zero, loop->block, loop->inner, NULL);

old = loop ;
Expand All @@ -843,7 +846,7 @@ CloogLoop * cloog_loop_separate(CloogLoop * loop)
if (!cloog_domain_isempty(domain))
{ new_inner = cloog_loop_concat(cloog_loop_copy(Q->inner),
cloog_loop_copy(loop->inner)) ;
new_loop = cloog_loop_alloc(loop->state, domain, loop->state->one,
new_loop = cloog_loop_alloc(loop->state, domain, 0, loop->state->one,
loop->state->zero, NULL, new_inner, NULL);
cloog_loop_add_disjoint(&temp,&now,new_loop) ;
}
Expand All @@ -864,7 +867,7 @@ CloogLoop * cloog_loop_separate(CloogLoop * loop)
}

if (!cloog_domain_isempty(domain)) {
new_loop = cloog_loop_alloc(loop->state, domain, loop->state->one,
new_loop = cloog_loop_alloc(loop->state, domain, 0, loop->state->one,
loop->state->zero, NULL, Q->inner, NULL);
cloog_loop_add_disjoint(&temp,&now,new_loop) ;
}
Expand All @@ -888,7 +891,7 @@ CloogLoop * cloog_loop_separate(CloogLoop * loop)
}

if (!cloog_domain_isempty(domain)) {
new_loop = cloog_loop_alloc(loop->state, domain, loop->state->one,
new_loop = cloog_loop_alloc(loop->state, domain, 0, loop->state->one,
loop->state->zero, NULL, loop->inner, NULL);
cloog_loop_add_disjoint(&temp,&now,new_loop) ;
}
Expand Down Expand Up @@ -979,7 +982,7 @@ CloogLoop *cloog_loop_merge(CloogLoop *loop, int level, CloogOptions *options)
cloog_domain_free(new_domain);
continue;
}
res = cloog_loop_alloc(old->state, new_domain, old->state->one,
res = cloog_loop_alloc(old->state, new_domain, 0, old->state->one,
old->state->zero, NULL,
cloog_loop_copy(new_inner), res);
}
Expand All @@ -994,10 +997,10 @@ CloogLoop *cloog_loop_merge(CloogLoop *loop, int level, CloogOptions *options)
cloog_domain_free(new_domain);
cloog_loop_free(new_inner);
} else
res = cloog_loop_alloc(old->state, new_domain, old->state->one,
res = cloog_loop_alloc(old->state, new_domain, 0, old->state->one,
old->state->zero, NULL, new_inner, res);
} else {
res = cloog_loop_alloc(old->state, new_domain, old->state->one,
res = cloog_loop_alloc(old->state, new_domain, 0, old->state->one,
old->state->zero, NULL, new_inner, NULL);
}
cloog_domain_free(temp);
Expand Down Expand Up @@ -1103,7 +1106,7 @@ CloogLoop *cloog_loop_nest(CloogLoop *loop, CloogDomain *context, int level)
if (p != NULL)
{ cloog_loop_free_parts(loop,1,0,0,0) ;

temp = cloog_loop_alloc(p->state, p->domain, p->state->one,
temp = cloog_loop_alloc(p->state, p->domain, 0, p->state->one,
p->state->zero, p->block, p->inner, NULL);

/* If the intersection dimension is too big, we make projections smaller
Expand All @@ -1113,7 +1116,7 @@ CloogLoop *cloog_loop_nest(CloogLoop *loop, CloogDomain *context, int level)
if (cloog_domain_dimension(p->domain) >= level)
for (l = cloog_domain_dimension(p->domain); l >= level; l--) {
new_domain = cloog_domain_project(p->domain, l);
temp = cloog_loop_alloc(p->state, new_domain, p->state->one,
temp = cloog_loop_alloc(p->state, new_domain, 0, p->state->one,
p->state->zero, NULL, temp, NULL);
}

Expand Down Expand Up @@ -1219,6 +1222,13 @@ void cloog_loop_stride(CloogLoop * loop, int level)
}


void cloog_loop_otl(CloogLoop *loop, int level)
{
if (cloog_domain_is_otl(loop->domain, level))
loop->otl = 1;
}


/**
* cloog_loop_stop function:
* This function implements the 'stop' option : each domain of each loop
Expand Down Expand Up @@ -1402,10 +1412,10 @@ CloogLoop *cloog_loop_generate_backtrack(CloogLoop *loop,
{ next = inner->next ;
/* This 'if' and its first part is the debug of july 31th 2002. */
if (inner->block != NULL) {
end = cloog_loop_alloc(temp->state, inner->domain, temp->state->one,
end = cloog_loop_alloc(temp->state, inner->domain, 0, temp->state->one,
temp->state->zero, inner->block, NULL, NULL);
domain = cloog_domain_copy(temp->domain) ;
new_loop = cloog_loop_alloc(temp->state, domain, temp->state->one,
new_loop = cloog_loop_alloc(temp->state, domain, 0, temp->state->one,
temp->state->zero, NULL, end, NULL);
}
else
Expand Down Expand Up @@ -1506,6 +1516,8 @@ CloogLoop *cloog_loop_generate_general(CloogLoop *loop,
while(temp != NULL)
{ if (level && options->strides)
cloog_loop_stride(temp, level);
if (level && options->otl)
cloog_loop_otl(temp, level);
inner = temp->inner ;
domain = temp->domain ;
into = NULL ;
Expand Down Expand Up @@ -1543,7 +1555,7 @@ CloogLoop *cloog_loop_generate_general(CloogLoop *loop,
while (temp != NULL)
{ next = temp->next ;
l = cloog_loop_nest(temp->inner, temp->domain, level+1);
new_loop = cloog_loop_alloc(temp->state, temp->domain, temp->state->one,
new_loop = cloog_loop_alloc(temp->state, temp->domain, 0, temp->state->one,
temp->state->zero, NULL, l, NULL);
temp->inner = NULL ;
temp->next = NULL ;
Expand Down Expand Up @@ -2126,7 +2138,7 @@ CloogLoop *cloog_loop_decompose_inner(CloogLoop *loop,
n_loops -= n;
i += n + 1;
tmp = cloog_loop_alloc(l->state, cloog_domain_copy(l->domain),
l->stride, l->offset, l->block, inner, l->next);
l->otl, l->stride, l->offset, l->block, inner, l->next);
l->next = tmp;
l = tmp;
}
Expand Down Expand Up @@ -2258,8 +2270,8 @@ static CloogLoop *loop_simplify(CloogLoop *loop, CloogDomain *context,

new_block = cloog_block_copy(loop->block) ;

simplified = cloog_loop_alloc(loop->state, simp, loop->stride, loop->offset,
new_block, inner, NULL);
simplified = cloog_loop_alloc(loop->state, simp, loop->otl, loop->stride,
loop->offset, new_block, inner, NULL);

return(simplified) ;
}
Expand Down
5 changes: 3 additions & 2 deletions test/thomasset.c
View file
Original file line number Diff line number Diff line change
@@ -1,4 +1,4 @@
/* Generated from /home/skimo/git/cloog/test/thomasset.cloog by CLooG 0.14.0-284-ga90f184 gmp bits in 0.04s. */
/* Generated from /home/skimo/git/cloog/test/thomasset.cloog by CLooG 0.14.0-292-g2bfd6ac gmp bits in 0.04s. */
if (n >= 1) {
for (c1=0;c1<=floord(n-4,3);c1++) {
for (i=3*c1+1;i<=3*c1+3;i++) {
Expand Down Expand Up @@ -39,7 +39,8 @@ if (n >= 1) {
for (c1=ceild(n,3);c1<=floord(2*n,3);c1++) {
for (c2=0;c2<=n-1;c2++) {
for (j=max(1,3*c1-n);j<=min(n,3*c1-n+4);j++) {
for (p=max(ceild(3*c1-j,3),ceild(n-2,3));p<=min(floord(n,3),floord(3*c1-j+2,3));p++) {
p = max(ceild(3*c1-j,3),ceild(n-2,3));
if (p <= min(floord(n,3),floord(3*c1-j+2,3))) {
S2(c2+1,j,0,p,c1-p);
}
}
Expand Down
Loading

0 comments on commit 7a10c39

Please sign in to comment.