X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=isl_ast_build.c;h=dd1aa7b65ed6fe263f10470bbe642ecc3c94c271;hb=19596bc4e5cd282b2e75d17077b1aaaeacbfd6f9;hp=a1941f8c3f621254c949cabac52299019b36ae54;hpb=90b03fd6d1ba37c9d3b0f1d78663aa8d35877547;p=platform%2Fupstream%2Fisl.git diff --git a/isl_ast_build.c b/isl_ast_build.c index a1941f8..dd1aa7b 100644 --- a/isl_ast_build.c +++ b/isl_ast_build.c @@ -49,7 +49,7 @@ static __isl_give isl_ast_build *isl_ast_build_init_derived( isl_vec *strides; build = isl_ast_build_cow(build); - if (!build) + if (!build || !build->domain) goto error; ctx = isl_ast_build_get_ctx(build); @@ -76,6 +76,24 @@ error: return isl_ast_build_free(build); } +/* Return an isl_id called "c%d", with "%d" set to "i". + * If an isl_id with such a name already appears among the parameters + * in build->domain, then adjust the name to "c%d_%d". + */ +static __isl_give isl_id *generate_name(isl_ctx *ctx, int i, + __isl_keep isl_ast_build *build) +{ + int j; + char name[16]; + isl_set *dom = build->domain; + + snprintf(name, sizeof(name), "c%d", i); + j = 0; + while (isl_set_find_dim_by_name(dom, isl_dim_param, name) >= 0) + snprintf(name, sizeof(name), "c%d_%d", i, j++); + return isl_id_alloc(ctx, name, NULL); +} + /* Create an isl_ast_build with "set" as domain. * * The input set is usually a parameter domain, but we currently allow it to @@ -108,7 +126,11 @@ __isl_give isl_ast_build *isl_ast_build_from_context(__isl_take isl_set *set) build->depth = n; build->iterators = isl_id_list_alloc(ctx, n); for (i = 0; i < n; ++i) { - isl_id *id = isl_set_get_dim_id(set, isl_dim_set, i); + isl_id *id; + if (isl_set_has_dim_id(set, isl_dim_set, i)) + id = isl_set_get_dim_id(set, isl_dim_set, i); + else + id = generate_name(ctx, i, build); build->iterators = isl_id_list_add(build->iterators, id); } space = isl_set_get_space(set); @@ -155,9 +177,14 @@ __isl_give isl_ast_build *isl_ast_build_dup(__isl_keep isl_ast_build *build) dup->strides = isl_vec_copy(build->strides); dup->offsets = isl_multi_aff_copy(build->offsets); dup->executed = isl_union_map_copy(build->executed); + dup->single_valued = build->single_valued; dup->options = isl_union_map_copy(build->options); dup->at_each_domain = build->at_each_domain; dup->at_each_domain_user = build->at_each_domain_user; + dup->before_each_for = build->before_each_for; + dup->before_each_for_user = build->before_each_for_user; + dup->after_each_for = build->after_each_for; + dup->after_each_for_user = build->after_each_for_user; dup->create_leaf = build->create_leaf; dup->create_leaf_user = build->create_leaf_user; @@ -316,6 +343,42 @@ __isl_give isl_ast_build *isl_ast_build_set_at_each_domain( return build; } +/* Set the "before_each_for" callback of "build" to "fn". + */ +__isl_give isl_ast_build *isl_ast_build_set_before_each_for( + __isl_take isl_ast_build *build, + __isl_give isl_id *(*fn)(__isl_keep isl_ast_build *build, + void *user), void *user) +{ + build = isl_ast_build_cow(build); + + if (!build) + return NULL; + + build->before_each_for = fn; + build->before_each_for_user = user; + + return build; +} + +/* Set the "after_each_for" callback of "build" to "fn". + */ +__isl_give isl_ast_build *isl_ast_build_set_after_each_for( + __isl_take isl_ast_build *build, + __isl_give isl_ast_node *(*fn)(__isl_take isl_ast_node *node, + __isl_keep isl_ast_build *build, void *user), void *user) +{ + build = isl_ast_build_cow(build); + + if (!build) + return NULL; + + build->after_each_for = fn; + build->after_each_for_user = user; + + return build; +} + /* Set the "create_leaf" callback of "build" to "fn". */ __isl_give isl_ast_build *isl_ast_build_set_create_leaf( @@ -352,6 +415,10 @@ __isl_give isl_ast_build *isl_ast_build_clear_local_info( build->at_each_domain = NULL; build->at_each_domain_user = NULL; + build->before_each_for = NULL; + build->before_each_for_user = NULL; + build->after_each_for = NULL; + build->after_each_for_user = NULL; build->create_leaf = NULL; build->create_leaf_user = NULL; @@ -666,9 +733,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; @@ -948,24 +1017,69 @@ __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) + __isl_take isl_val *stride, __isl_take isl_aff *offset) { int pos; build = isl_ast_build_cow(build); - if (!build || !offset) + if (!build || !stride || !offset) goto error; pos = build->depth; - build->strides = isl_vec_set_element(build->strides, pos, stride); + + if (isl_ast_build_has_stride(build, pos)) { + isl_val *stride2, *a, *b, *g; + isl_aff *offset2; + + stride2 = isl_vec_get_element_val(build->strides, pos); + g = isl_val_gcdext(isl_val_copy(stride), isl_val_copy(stride2), + &a, &b); + a = isl_val_mul(a, isl_val_copy(stride)); + a = isl_val_div(a, isl_val_copy(g)); + stride2 = isl_val_div(stride2, g); + b = isl_val_mul(b, isl_val_copy(stride2)); + stride = isl_val_mul(stride, stride2); + + offset2 = isl_multi_aff_get_aff(build->offsets, pos); + offset2 = isl_aff_scale_val(offset2, a); + offset = isl_aff_scale_val(offset, b); + offset = isl_aff_add(offset, offset2); + } + + build->strides = isl_vec_set_element_val(build->strides, pos, stride); build->offsets = isl_multi_aff_set_aff(build->offsets, pos, offset); if (!build->strides || !build->offsets) return isl_ast_build_free(build); return build; error: + isl_val_free(stride); isl_aff_free(offset); return isl_ast_build_free(build); } @@ -986,7 +1100,7 @@ __isl_give isl_set *isl_ast_build_get_stride_constraint( { isl_aff *aff; isl_set *set; - isl_int stride; + isl_val *stride; int pos; if (!build) @@ -997,16 +1111,12 @@ __isl_give isl_set *isl_ast_build_get_stride_constraint( if (!isl_ast_build_has_stride(build, pos)) return isl_set_universe(isl_ast_build_get_space(build, 1)); - isl_int_init(stride); - - isl_ast_build_get_stride(build, pos, &stride); + stride = isl_ast_build_get_stride(build, pos); aff = isl_ast_build_get_offset(build, pos); aff = isl_aff_add_coefficient_si(aff, isl_dim_in, pos, -1); - aff = isl_aff_mod(aff, stride); + aff = isl_aff_mod_val(aff, stride); set = isl_set_from_basic_set(isl_aff_zero_basic_set(aff)); - isl_int_clear(stride); - return set; } @@ -1028,7 +1138,7 @@ __isl_give isl_multi_aff *isl_ast_build_get_stride_expansion( isl_multi_aff *ma; int pos; isl_aff *aff, *offset; - isl_int stride; + isl_val *stride; if (!build) return NULL; @@ -1041,14 +1151,12 @@ __isl_give isl_multi_aff *isl_ast_build_get_stride_expansion( if (!isl_ast_build_has_stride(build, pos)) return ma; - isl_int_init(stride); offset = isl_ast_build_get_offset(build, pos); - isl_ast_build_get_stride(build, pos, &stride); + stride = isl_ast_build_get_stride(build, pos); aff = isl_multi_aff_get_aff(ma, pos); - aff = isl_aff_scale(aff, stride); + aff = isl_aff_scale_val(aff, stride); aff = isl_aff_add(aff, offset); ma = isl_multi_aff_set_aff(ma, pos, aff); - isl_int_clear(stride); return ma; } @@ -1079,51 +1187,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. @@ -1173,7 +1236,8 @@ static int detect_stride(__isl_take isl_constraint *c, void *user) { struct isl_detect_stride_data *data = user; int i, n_div; - isl_int v, gcd, stride, a, b, m; + isl_ctx *ctx; + isl_val *v, *stride, *m; if (!isl_constraint_is_equality(c) || !isl_constraint_involves_dims(c, isl_dim_set, data->pos, 1)) { @@ -1181,48 +1245,42 @@ static int detect_stride(__isl_take isl_constraint *c, void *user) return 0; } - isl_int_init(a); - isl_int_init(b); - isl_int_init(v); - isl_int_init(m); - isl_int_init(gcd); - isl_int_init(stride); - - isl_int_set_si(gcd, 0); + ctx = isl_constraint_get_ctx(c); + stride = isl_val_zero(ctx); n_div = isl_constraint_dim(c, isl_dim_div); for (i = 0; i < n_div; ++i) { - isl_constraint_get_coefficient(c, isl_dim_div, i, &v); - isl_int_gcd(gcd, gcd, v); + v = isl_constraint_get_coefficient_val(c, isl_dim_div, i); + v = isl_val_gcd(stride, v); } - isl_constraint_get_coefficient(c, isl_dim_set, data->pos, &v); - isl_int_gcd(m, v, gcd); - isl_int_divexact(stride, gcd, m); - isl_int_divexact(v, v, m); + v = isl_constraint_get_coefficient_val(c, isl_dim_set, data->pos); + m = isl_val_gcd(isl_val_copy(stride), isl_val_copy(v)); + stride = isl_val_div(stride, isl_val_copy(m)); + v = isl_val_div(v, isl_val_copy(m)); - if (!isl_int_is_zero(stride) && !isl_int_is_one(stride)) { + if (!isl_val_is_zero(stride) && !isl_val_is_one(stride)) { isl_aff *aff; + isl_val *gcd, *a, *b; - euclid(v, stride, &a, &b, &gcd); + gcd = isl_val_gcdext(v, isl_val_copy(stride), &a, &b); + isl_val_free(gcd); + isl_val_free(b); aff = isl_constraint_get_aff(c); for (i = 0; i < n_div; ++i) aff = isl_aff_set_coefficient_si(aff, isl_dim_div, i, 0); aff = isl_aff_set_coefficient_si(aff, isl_dim_in, data->pos, 0); - isl_int_neg(a, a); - aff = isl_aff_scale(aff, a); - aff = isl_aff_scale_down(aff, m); + a = isl_val_neg(a); + aff = isl_aff_scale_val(aff, a); + aff = isl_aff_scale_down_val(aff, m); data->build = set_stride(data->build, stride, aff); + } else { + isl_val_free(stride); + isl_val_free(m); + isl_val_free(v); } - isl_int_clear(stride); - isl_int_clear(gcd); - isl_int_clear(m); - isl_int_clear(v); - isl_int_clear(b); - isl_int_clear(a); - isl_constraint_free(c); return 0; } @@ -1462,28 +1520,25 @@ __isl_give isl_ast_build *isl_ast_build_insert_dim( * We therefore only need to update stride, offset and the options. */ __isl_give isl_ast_build *isl_ast_build_scale_down( - __isl_take isl_ast_build *build, isl_int m, + __isl_take isl_ast_build *build, __isl_take isl_val *m, __isl_take isl_union_map *umap) { isl_aff *aff; - isl_int v; + isl_val *v; int depth; build = isl_ast_build_cow(build); - if (!build || !umap) + if (!build || !umap || !m) goto error; depth = build->depth; - isl_int_init(v); - if (isl_vec_get_element(build->strides, depth, &v) < 0) - build->strides = isl_vec_free(build->strides); - isl_int_divexact(v, v, m); - build->strides = isl_vec_set_element(build->strides, depth, v); - isl_int_clear(v); + v = isl_vec_get_element_val(build->strides, depth); + v = isl_val_div(v, isl_val_copy(m)); + build->strides = isl_vec_set_element_val(build->strides, depth, v); aff = isl_multi_aff_get_aff(build->offsets, depth); - aff = isl_aff_scale_down(aff, m); + aff = isl_aff_scale_down_val(aff, m); build->offsets = isl_multi_aff_set_aff(build->offsets, depth, aff); build->options = isl_union_map_apply_domain(build->options, umap); if (!build->strides || !build->offsets || !build->options) @@ -1491,6 +1546,7 @@ __isl_give isl_ast_build *isl_ast_build_scale_down( return build; error: + isl_val_free(m); isl_union_map_free(umap); return isl_ast_build_free(build); } @@ -1502,20 +1558,14 @@ error: static __isl_give isl_id_list *generate_names(isl_ctx *ctx, int n, int first, __isl_keep isl_ast_build *build) { - int i, j; - char name[16]; + int i; isl_id_list *names; - isl_set *dom = build->domain; names = isl_id_list_alloc(ctx, n); for (i = 0; i < n; ++i) { isl_id *id; - snprintf(name, sizeof(name), "c%d", first + i); - j = 0; - while (isl_set_find_dim_by_name(dom, isl_dim_param, name) >= 0) - snprintf(name, sizeof(name), "c%d_%d", first + i, j++); - id = isl_id_alloc(ctx, name, NULL); + id = generate_name(ctx, first + i, build); names = isl_id_list_add(names, id); } @@ -1669,16 +1719,17 @@ int isl_ast_build_aff_is_nonneg(__isl_keep isl_ast_build *build, */ int isl_ast_build_has_stride(__isl_keep isl_ast_build *build, int pos) { - isl_int v; + isl_val *v; int has_stride; if (!build) return -1; - isl_int_init(v); - isl_vec_get_element(build->strides, pos, &v); - has_stride = !isl_int_is_one(v); - isl_int_clear(v); + v = isl_vec_get_element_val(build->strides, pos); + if (!v) + return -1; + has_stride = !isl_val_is_one(v); + isl_val_free(v); return has_stride; } @@ -1689,15 +1740,13 @@ int isl_ast_build_has_stride(__isl_keep isl_ast_build *build, int pos) * * with a an integer, return s through *stride. */ -int isl_ast_build_get_stride(__isl_keep isl_ast_build *build, int pos, - isl_int *stride) +__isl_give isl_val *isl_ast_build_get_stride(__isl_keep isl_ast_build *build, + int pos) { if (!build) - return -1; - - isl_vec_get_element(build->strides, pos, stride); + return NULL; - return 0; + return isl_vec_get_element_val(build->strides, pos); } /* Given that the dimension at position "pos" takes on values @@ -1743,6 +1792,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) @@ -2016,3 +2085,20 @@ __isl_give isl_set *isl_ast_build_eliminate( domain = isl_ast_build_eliminate_divs(build, domain); return domain; } + +/* Replace build->single_valued by "sv". + */ +__isl_give isl_ast_build *isl_ast_build_set_single_valued( + __isl_take isl_ast_build *build, int sv) +{ + if (!build) + return build; + if (build->single_valued == sv) + return build; + build = isl_ast_build_cow(build); + if (!build) + return build; + build->single_valued = sv; + + return build; +}