X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=isl_ast_build.c;h=7bf8610299d099f12312e3074a54bf6103b21ca8;hb=63fb8a7f484648c3caa25351c8c94ac2395ec563;hp=ed6754518d0078f22cf338d06e2168de623632d2;hpb=076a978c4331b27eee3260851b3aaa27ea4e469a;p=platform%2Fupstream%2Fisl.git diff --git a/isl_ast_build.c b/isl_ast_build.c index ed67545..7bf8610 100644 --- a/isl_ast_build.c +++ b/isl_ast_build.c @@ -7,6 +7,7 @@ * Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France */ +#include #include #include #include @@ -733,9 +734,11 @@ __isl_give isl_ast_build *isl_ast_build_set_loop_bounds( set = isl_set_compute_divs(set); build->pending = isl_set_intersect(build->pending, isl_set_copy(set)); - if (isl_ast_build_has_stride(build, build->depth)) + if (isl_ast_build_has_stride(build, build->depth)) { build->domain = isl_set_eliminate(build->domain, isl_dim_set, build->depth, 1); + build->domain = isl_set_compute_divs(build->domain); + } } else { isl_basic_set *generated, *pending; @@ -1015,6 +1018,30 @@ __isl_give isl_id *isl_ast_build_get_iterator_id( /* Set the stride and offset of the current dimension to the given * value and expression. + * + * If we had already found a stride before, then the two strides + * are combined into a single stride. + * + * In particular, if the new stride information is of the form + * + * i = f + s (...) + * + * and the old stride information is of the form + * + * i = f2 + s2 (...) + * + * then we compute the extended gcd of s and s2 + * + * a s + b s2 = g, + * + * with g = gcd(s,s2), multiply the first equation with t1 = b s2/g + * and the second with t2 = a s1/g. + * This results in + * + * i = (b s2 + a s1)/g i = t1 f + t2 f2 + (s s2)/g (...) + * + * so that t1 f + t2 f2 is the combined offset and (s s2)/g = lcm(s,s2) + * is the combined stride. */ static __isl_give isl_ast_build *set_stride(__isl_take isl_ast_build *build, isl_int stride, __isl_take isl_aff *offset) @@ -1026,6 +1053,35 @@ static __isl_give isl_ast_build *set_stride(__isl_take isl_ast_build *build, goto error; pos = build->depth; + + if (isl_ast_build_has_stride(build, pos)) { + isl_int stride2, a, b, g; + isl_aff *offset2; + + isl_int_init(stride2); + isl_int_init(a); + isl_int_init(b); + isl_int_init(g); + + isl_vec_get_element(build->strides, pos, &stride2); + isl_int_gcdext(g, a, b, stride, stride2); + isl_int_mul(a, a, stride); + isl_int_divexact(a, a, g); + isl_int_divexact(stride2, stride2, g); + isl_int_mul(b, b, stride2); + isl_int_mul(stride, stride, stride2); + + offset2 = isl_multi_aff_get_aff(build->offsets, pos); + offset2 = isl_aff_scale(offset2, a); + offset = isl_aff_scale(offset, b); + offset = isl_aff_add(offset, offset2); + + isl_int_clear(stride2); + isl_int_clear(a); + isl_int_clear(b); + isl_int_clear(g); + } + build->strides = isl_vec_set_element(build->strides, pos, stride); build->offsets = isl_multi_aff_set_aff(build->offsets, pos, offset); if (!build->strides || !build->offsets) @@ -1146,51 +1202,6 @@ __isl_give isl_ast_build *isl_ast_build_include_stride( return build; } -/* Compute x, y and g such that g = gcd(a,b) and a*x+b*y = g */ -static void euclid(isl_int a, isl_int b, isl_int *x, isl_int *y, isl_int *g) -{ - isl_int c, d, e, f, tmp; - - isl_int_init(c); - isl_int_init(d); - isl_int_init(e); - isl_int_init(f); - isl_int_init(tmp); - isl_int_abs(c, a); - isl_int_abs(d, b); - isl_int_set_si(e, 1); - isl_int_set_si(f, 0); - while (isl_int_is_pos(d)) { - isl_int_tdiv_q(tmp, c, d); - isl_int_mul(tmp, tmp, f); - isl_int_sub(e, e, tmp); - isl_int_tdiv_q(tmp, c, d); - isl_int_mul(tmp, tmp, d); - isl_int_sub(c, c, tmp); - isl_int_swap(c, d); - isl_int_swap(e, f); - } - isl_int_set(*g, c); - if (isl_int_is_zero(a)) - isl_int_set_si(*x, 0); - else if (isl_int_is_pos(a)) - isl_int_set(*x, e); - else - isl_int_neg(*x, e); - if (isl_int_is_zero(b)) - isl_int_set_si(*y, 0); - else { - isl_int_mul(tmp, a, *x); - isl_int_sub(tmp, c, tmp); - isl_int_divexact(*y, tmp, b); - } - isl_int_clear(c); - isl_int_clear(d); - isl_int_clear(e); - isl_int_clear(f); - isl_int_clear(tmp); -} - /* Information used inside detect_stride. * * "build" may be updated by detect_stride to include stride information. @@ -1270,7 +1281,7 @@ static int detect_stride(__isl_take isl_constraint *c, void *user) if (!isl_int_is_zero(stride) && !isl_int_is_one(stride)) { isl_aff *aff; - euclid(v, stride, &a, &b, &gcd); + isl_int_gcdext(gcd, a, b, v, stride); aff = isl_constraint_get_aff(c); for (i = 0; i < n_div; ++i) @@ -1804,6 +1815,26 @@ int isl_ast_build_has_affine_value(__isl_keep isl_ast_build *build, return !involves; } +/* Plug in the known values (fixed affine expressions in terms of + * parameters and outer loop iterators) of all loop iterators + * in the domain of "umap". + * + * We simply precompose "umap" with build->values. + */ +__isl_give isl_union_map *isl_ast_build_substitute_values_union_map_domain( + __isl_keep isl_ast_build *build, __isl_take isl_union_map *umap) +{ + isl_multi_aff *values; + + if (!build) + return isl_union_map_free(umap); + + values = isl_multi_aff_copy(build->values); + umap = isl_union_map_preimage_domain_multi_aff(umap, values); + + return umap; +} + /* Is the current dimension known to attain only a single value? */ int isl_ast_build_has_value(__isl_keep isl_ast_build *build)