From 9802965061171115824e7127771c2d12ea37c75a Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Sat, 4 Dec 2010 17:57:26 +0100 Subject: [PATCH] cloog_loop_generate_general: add special treatment for loops with constant value When the -noscalars option is used, the generated code could be different from code generated without this option. The reason is that during separation at a constant level, the domains of the different loops could differ in values of earlier dimensions or of parameters. The result is that separation would then be applied to these earlier dimensions and parameters. This patch avoids separation if all loops under consideration can be seen to have a fixed value at the current level. The check does not depend on not using the -noscalars option. Since the check is applied locally, it can also avoid some separations that are not avoided by not using the -noscalars option. In principle, the same optimization could be applied whenever all constraints involving the current level are the same for the domains of all loops, and the only differences are in constraints not involving the current level. Reported-by: Tobias Grosser Signed-off-by: Sven Verdoolaege --- source/loop.c | 57 ++++++++++++++++++++- test/Makefile.am | 1 + test/cholesky2.c | 17 +++--- test/constant.c | 17 ++++++ test/constant.cloog | 128 ++++++++++++++++++++++++++++++++++++++++++++++ test/constant.good.c | 39 ++++++++++++++ test/reservoir/lim-lam3.c | 8 ++- 7 files changed, 250 insertions(+), 17 deletions(-) create mode 100644 test/constant.c create mode 100644 test/constant.cloog create mode 100644 test/constant.good.c diff --git a/source/loop.c b/source/loop.c index ec5200a..c76071e 100644 --- a/source/loop.c +++ b/source/loop.c @@ -1502,6 +1502,59 @@ int cloog_loop_more(CloogLoop *loop, int level, int scalar, int nb_scattdims) return level + scalar <= nb_scattdims || cloog_domain_dimension(loop->domain) >= level; } + +/** + * Return 1 if the domains of all loops in the given linked list + * have a fixed value at the given level. + * Note that there is no need to check that the fixed value is + * the same for each of these loops because this function is only + * called on a component. If the loops were to have fixed, but + * different values, the loops with different fixed values would + * have been split over distinct components. + */ +int cloog_loop_is_constant(CloogLoop *loop, int level) +{ + for (; loop; loop = loop->next) + if (!cloog_domain_lazy_isconstant(loop->domain, level - 1)) + return 0; + return 1; +} + +/** + * Assuming all domains in the given linked list of loop + * have a fixed values at level, return a single loop with + * a domain corresponding to this fixed value and with as + * list of inner loops the concatenation of all inner loops + * in the original list. + */ +CloogLoop *cloog_loop_constant(CloogLoop *loop, int level) +{ + CloogLoop *res, *inner, *tmp; + CloogDomain *domain, *context, *t; + + if (!loop) + return loop; + + inner = loop->inner; + for (tmp = loop->next; tmp; tmp = tmp->next) + inner = cloog_loop_concat(inner, tmp->inner); + + domain = cloog_domain_copy(loop->domain); + domain = cloog_domain_simple_convex(t = domain); + cloog_domain_free(t); + context = cloog_domain_project(domain, level - 1); + context = cloog_domain_extend(t = context, level); + cloog_domain_free(t); + domain = cloog_domain_simplify(t = domain, context); + cloog_domain_free(t); + cloog_domain_free(context); + + res = cloog_loop_alloc(loop->state, domain, 0, NULL, NULL, inner, NULL); + + cloog_loop_free_parts(loop, 1, 0, 0, 1); + + return res; +} CloogLoop *cloog_loop_generate_restricted_or_stop(CloogLoop *loop, CloogDomain *context, @@ -1541,7 +1594,9 @@ CloogLoop *cloog_loop_generate_general(CloogLoop *loop, int separate = 0; /* 3. Separate all projections into disjoint polyhedra. */ - if ((options->f > level+scalar) || (options->f < 0)) + if (level > 0 && cloog_loop_is_constant(loop, level)) + res = cloog_loop_constant(loop, level); + else if ((options->f > level+scalar) || (options->f < 0)) res = cloog_loop_merge(loop, level, options); else { res = cloog_loop_separate(loop); diff --git a/test/Makefile.am b/test/Makefile.am index cc2650c..72e98db 100644 --- a/test/Makefile.am +++ b/test/Makefile.am @@ -73,6 +73,7 @@ FINITE_CLOOGTEST_C = \ cholesky2 \ classen \ classen2 \ + constant \ constbound \ darte \ dealII \ diff --git a/test/cholesky2.c b/test/cholesky2.c index cbc05e3..a093a6e 100644 --- a/test/cholesky2.c +++ b/test/cholesky2.c @@ -1,17 +1,12 @@ -/* Generated from ../../../git/cloog/test/cholesky2.cloog by CLooG 0.14.0-313-g0d7f67f gmp bits in 0.04s. */ +/* Generated from ../../../git/cloog/test/cholesky2.cloog by CLooG 0.14.0-333-g4442dac gmp bits in 0.04s. */ if (M >= 1) { - if (M >= 2) { - for (c2=1;c2<=M-1;c2++) { - S1(c2); - for (c3=c2+1;c3<=M;c3++) { - S4(c2,c3); - } + for (c2=1;c2<=M-1;c2++) { + S1(c2); + for (c3=c2+1;c3<=M;c3++) { + S4(c2,c3); } - S1(M); - } - if (M == 1) { - S1(1); } + S1(M); if (M >= 3) { S3(1); } diff --git a/test/constant.c b/test/constant.c new file mode 100644 index 0000000..3a6378e --- /dev/null +++ b/test/constant.c @@ -0,0 +1,17 @@ +/* Generated from ../../../git/cloog/test/constant.cloog by CLooG 0.14.0-333-g4442dac gmp bits in 0.01s. */ +for (c2=0;c2<=min(1023,M+1024);c2++) { + S1(c2); + S3(c2); +} +for (c2=max(0,M+1025);c2<=1023;c2++) { + S2(c2); + S3(c2); +} +for (c1=0;c1<=min(1023,M+1024);c1++) { + S4(c1); + S6(c1); +} +for (c1=max(0,M+1025);c1<=1023;c1++) { + S5(c1); + S6(c1); +} diff --git a/test/constant.cloog b/test/constant.cloog new file mode 100644 index 0000000..d251b1b --- /dev/null +++ b/test/constant.cloog @@ -0,0 +1,128 @@ +# CLooG -> CLooG +# This is an automatic dump of a CLooG input file from a CloogInput data +# structure. + +# Language: C +c + +# Context: +0 3 + +0 # Parameter name(s) + +# Statement number: +6 + +# Iteration domain of statement 1 (Stmt_if.then). +1 + +3 4 1 0 0 1 +1 1 0 0 +1 -1 0 1023 +1 -1 1 1024 + +0 0 0 # For future options. + +# Iteration domain of statement 2 (Stmt_if.else). +1 + +3 4 1 0 0 1 +1 1 0 0 +1 -1 0 1023 +1 1 -1 -1025 + +0 0 0 # For future options. + +# Iteration domain of statement 3 (Stmt_if.end). +1 + +2 4 1 0 0 1 +1 1 0 0 +1 -1 0 1023 + +0 0 0 # For future options. + +# Iteration domain of statement 1 (Stmt_if.then). +1 + +3 4 1 0 0 1 +1 1 0 0 +1 -1 0 1023 +1 -1 1 1024 + +0 0 0 # For future options. + +# Iteration domain of statement 2 (Stmt_if.else). +1 + +3 4 1 0 0 1 +1 1 0 0 +1 -1 0 1023 +1 1 -1 -1025 + +0 0 0 # For future options. + +# Iteration domain of statement 3 (Stmt_if.end). +1 + +2 4 1 0 0 1 +1 1 0 0 +1 -1 0 1023 + +0 0 0 # For future options. + + +0 # Iterator name(s) + +# --------------------- SCATTERING -------------------- +6 # Scattering functions + +# Scattering of statement 1 (Stmt_if.then). +1 + +3 7 3 1 0 1 +0 0 0 1 0 0 0 +0 0 1 0 -1 0 0 +0 1 0 0 0 0 1 + +# Scattering of statement 2 (Stmt_if.else). +1 + +3 7 3 1 0 1 +0 0 0 1 0 0 -1 +0 0 1 0 -1 0 0 +0 1 0 0 0 0 1 + +# Scattering of statement 3 (Stmt_if.end). +1 + +3 7 3 1 0 1 +0 0 0 1 0 0 -2 +0 0 1 0 -1 0 0 +0 1 0 0 0 0 1 + +# Scattering of statement 1 (Stmt_if.then). +1 + +3 7 3 1 0 1 +0 0 0 1 0 0 0 +0 1 0 0 -1 0 0 +0 0 1 0 0 0 0 + +# Scattering of statement 2 (Stmt_if.else). +1 + +3 7 3 1 0 1 +0 0 0 1 0 0 -1 +0 1 0 0 -1 0 0 +0 0 1 0 0 0 0 + +# Scattering of statement 3 (Stmt_if.end). +1 + +3 7 3 1 0 1 +0 0 0 1 0 0 -2 +0 1 0 0 -1 0 0 +0 0 1 0 0 0 0 + +0 # Scattering dimension name(s) diff --git a/test/constant.good.c b/test/constant.good.c new file mode 100644 index 0000000..c94fc44 --- /dev/null +++ b/test/constant.good.c @@ -0,0 +1,39 @@ +/* Generated from ../../../git/cloog/test/constant.cloog by CLooG 0.14.0-333-g4442dac gmp bits in 0.01s. */ +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); } +#define S2(i) { hash(2); hash(i); } +#define S3(i) { hash(3); hash(i); } +#define S4(i) { hash(4); hash(i); } +#define S5(i) { hash(5); hash(i); } +#define S6(i) { hash(6); hash(i); } + +void test(int M) +{ + /* Scattering iterators. */ + int c1, c2; + /* Original iterators. */ + int i; + for (c2=0;c2<=min(1023,M+1024);c2++) { + S1(c2); + S3(c2); + } + for (c2=max(0,M+1025);c2<=1023;c2++) { + S2(c2); + S3(c2); + } + for (c1=0;c1<=min(1023,M+1024);c1++) { + S4(c1); + S6(c1); + } + for (c1=max(0,M+1025);c1<=1023;c1++) { + S5(c1); + S6(c1); + } +} diff --git a/test/reservoir/lim-lam3.c b/test/reservoir/lim-lam3.c index 0e3b002..e2026d9 100644 --- a/test/reservoir/lim-lam3.c +++ b/test/reservoir/lim-lam3.c @@ -1,4 +1,4 @@ -/* Generated from /home/skimo/git/cloog/test/./reservoir/lim-lam3.cloog by CLooG 0.14.0-284-ga90f184 gmp bits in 0.02s. */ +/* Generated from ../../../git/cloog/test/reservoir/lim-lam3.cloog by CLooG 0.14.0-333-g4442dac gmp bits in 0.03s. */ S4(1); for (c2=9;c2<=min(13,5*M-1);c2++) { if (c2 <= M+7) { @@ -7,10 +7,8 @@ for (c2=9;c2<=min(13,5*M-1);c2++) { if (c2 == 10) { S4(2); } - if (c2 <= 3*M+3) { - if (c2%3 == 0) { - S3((c2-3)/3,1); - } + if (c2%3 == 0) { + S3((c2-3)/3,1); } } if (M == 2) { -- 2.11.4.GIT