From d5c69a92b8c15fb5daa255a094bac37904f525ad Mon Sep 17 00:00:00 2001 From: Tobias Grosser Date: Mon, 17 Oct 2011 18:11:20 +0100 Subject: [PATCH] select "best" lower bound for unrolling When support for unrolling was added in 7f6868b (add support for unrolling, Thu May 12 16:22:49 2011 +0200), it was restricted to loops with only a single lower bound. This was relaxed in a0c4004 (allow unrolling of loops with multiple lower bounds, Fri Jun 3 15:04:07 2011 +0200), but the new code would simply pick the first appropriate lower bound it could find. Since the iteration domain is sliced in parallel to the lower bound, different lower bounds may lead to different numbers of iterations. In some cases this difference can be quite dramatic. We now pick the lower bound that results in the smallest number of slices. Note however that some of those slices may be empty, so this choice does not always guarantee that the smallest code will be generated. As an example, for the newly added test case, we now generate if ((M >= -1) && (M <= 9)) { if (M >= 0) { S1(M); } S1(M+1); } whereas before we would generate if ((M >= -1) && (M <= 9)) { if (M <= 0) { S1(0); } if ((M >= 0) && (M <= 1)) { S1(1); } if ((M >= 1) && (M <= 2)) { S1(2); } if ((M >= 2) && (M <= 3)) { S1(3); } if ((M >= 3) && (M <= 4)) { S1(4); } if ((M >= 4) && (M <= 5)) { S1(5); } if ((M >= 5) && (M <= 6)) { S1(6); } if ((M >= 6) && (M <= 7)) { S1(7); } if ((M >= 7) && (M <= 8)) { S1(8); } if (M >= 8) { S1(9); } if (M == 9) { S1(10); } } Reported-by: Carlos Juega Reimundez Signed-off-by: Sven Verdoolaege Signed-off-by: Tobias Grosser --- source/isl/domain.c | 21 ++++++++++++++------- test/Makefile.am | 2 ++ test/isl/unroll2.c | 7 +++++++ test/isl/unroll2.cloog | 14 ++++++++++++++ test/isl/unroll2.good.c | 21 +++++++++++++++++++++ 5 files changed, 58 insertions(+), 7 deletions(-) create mode 100644 test/isl/unroll2.c create mode 100644 test/isl/unroll2.cloog create mode 100644 test/isl/unroll2.good.c diff --git a/source/isl/domain.c b/source/isl/domain.c index 4a60dbf..67f0458 100644 --- a/source/isl/domain.c +++ b/source/isl/domain.c @@ -1702,14 +1702,15 @@ struct cloog_can_unroll { /* - * Check if the given lower bound can be used for unrolling. + * Check if the given lower bound can be used for unrolling + * and, if so, return the unrolling factor/trip count in *v. * If the lower bound involves any existentially quantified * variables, we currently punt. * Otherwise we compute the maximal value of (i - ceil(l) + 1), * with l the given lower bound and i the iterator identified by level. */ static int is_valid_unrolling_lower_bound(struct cloog_can_unroll *ccu, - __isl_keep isl_constraint *c) + __isl_keep isl_constraint *c, isl_int *v) { unsigned n_div; isl_aff *aff; @@ -1723,7 +1724,7 @@ static int is_valid_unrolling_lower_bound(struct cloog_can_unroll *ccu, aff = isl_aff_ceil(aff); aff = isl_aff_neg(aff); aff = isl_aff_add_coefficient_si(aff, isl_dim_in, ccu->level - 1, 1); - res = isl_set_max(ccu->set, aff, ccu->n); + res = isl_set_max(ccu->set, aff, v); isl_aff_free(aff); if (res == isl_lp_unbounded) @@ -1731,7 +1732,7 @@ static int is_valid_unrolling_lower_bound(struct cloog_can_unroll *ccu, assert(res == isl_lp_ok); - cloog_int_add_ui(*ccu->n, *ccu->n, 1); + cloog_int_add_ui(*v, *v, 1); return 1; } @@ -1746,13 +1747,19 @@ static int constraint_can_unroll(__isl_take isl_constraint *c, void *user) { struct cloog_can_unroll *ccu = (struct cloog_can_unroll *)user; isl_int v; + isl_int count; isl_int_init(v); + isl_int_init(count); isl_constraint_get_coefficient(c, isl_dim_set, ccu->level - 1, &v); - if (isl_int_is_pos(v)) { - if (!ccu->c && is_valid_unrolling_lower_bound(ccu, c)) - ccu->c = isl_constraint_copy(c); + if (isl_int_is_pos(v) && + is_valid_unrolling_lower_bound(ccu, c, &count) && + (!ccu->c || isl_int_lt(count, *ccu->n))) { + isl_constraint_free(ccu->c); + ccu->c = isl_constraint_copy(c); + isl_int_set(*ccu->n, count); } + isl_int_clear(count); isl_int_clear(v); isl_constraint_free(c); diff --git a/test/Makefile.am b/test/Makefile.am index 8ad5038..68b073d 100644 --- a/test/Makefile.am +++ b/test/Makefile.am @@ -210,6 +210,7 @@ CLOOGTEST_STRIDED = \ SPECIAL_TESTS = \ isl/unroll \ isl/jacobi-shared \ + isl/unroll2 \ backtrack \ vasilache \ merge \ @@ -224,6 +225,7 @@ SPECIAL_TESTS = \ SPECIAL_OPTIONS = \ 'isl/unroll -first-unroll 1' \ 'isl/jacobi-shared -f 4 -l -1 -override -strides 1 -sh 1' \ + 'isl/unroll2 -first-unroll 1' \ 'backtrack -f 1 -backtrack' \ 'vasilache -f 8 -l 9' \ 'merge -f -1' \ diff --git a/test/isl/unroll2.c b/test/isl/unroll2.c new file mode 100644 index 0000000..7ec66bd --- /dev/null +++ b/test/isl/unroll2.c @@ -0,0 +1,7 @@ +/* Generated from ../../../git/cloog/test/isl/unroll2.cloog by CLooG 0.16.3-13-g27516e4 gmp bits in 0.00s. */ +if ((M >= -1) && (M <= 9)) { + if (M >= 0) { + S1(M); + } + S1(M+1); +} diff --git a/test/isl/unroll2.cloog b/test/isl/unroll2.cloog new file mode 100644 index 0000000..d725478 --- /dev/null +++ b/test/isl/unroll2.cloog @@ -0,0 +1,14 @@ +C + +[n] -> { : } + +0 + +1 + +[n] -> { [i] : 0 <= i and n <= i <= n + 1 <= 10 } +0 0 0 + +0 + +0 diff --git a/test/isl/unroll2.good.c b/test/isl/unroll2.good.c new file mode 100644 index 0000000..537b3b1 --- /dev/null +++ b/test/isl/unroll2.good.c @@ -0,0 +1,21 @@ +/* Generated from ../../../git/cloog/test/isl/unroll2.cloog by CLooG 0.16.3-13-g27516e4 gmp bits in 0.00s. */ +extern void hash(int); + +/* Useful macros. */ +#define floord(n,d) (((n)<0) ? -((-(n)+(d)-1)/(d)) : (n)/(d)) +#define ceild(n,d) (((n)<0) ? -((-(n))/(d)) : ((n)+(d)-1)/(d)) +#define max(x,y) ((x) > (y) ? (x) : (y)) +#define min(x,y) ((x) < (y) ? (x) : (y)) + +#define S1(i) { hash(1); hash(i); } + +void test(int M) +{ + /* Original iterators. */ + int i; + if ((M >= -1) && (M <= 9)) { + for (i=max(0,M);i<=M+1;i++) { + S1(i); + } + } +} -- 2.11.4.GIT