diff options
| -rw-r--r-- | polly/lib/External/isl/GIT_HEAD_ID | 2 | ||||
| -rw-r--r-- | polly/lib/External/isl/doc/user.pod | 30 | ||||
| -rw-r--r-- | polly/lib/External/isl/include/isl/list.h | 5 | ||||
| -rw-r--r-- | polly/lib/External/isl/include/isl/set.h | 2 | ||||
| -rw-r--r-- | polly/lib/External/isl/include/isl/union_map.h | 2 | ||||
| -rw-r--r-- | polly/lib/External/isl/include/isl/union_set.h | 4 | ||||
| -rw-r--r-- | polly/lib/External/isl/isl_farkas.c | 18 | ||||
| -rw-r--r-- | polly/lib/External/isl/isl_list_templ.c | 103 | ||||
| -rw-r--r-- | polly/lib/External/isl/isl_scheduler.c | 658 | ||||
| -rw-r--r-- | polly/lib/External/isl/isl_tab.h | 2 | ||||
| -rw-r--r-- | polly/lib/External/isl/isl_tab_pip.c | 14 | ||||
| -rw-r--r-- | polly/lib/External/isl/isl_union_map.c | 83 |
12 files changed, 771 insertions, 152 deletions
diff --git a/polly/lib/External/isl/GIT_HEAD_ID b/polly/lib/External/isl/GIT_HEAD_ID index 2854317db62..1d0ea449688 100644 --- a/polly/lib/External/isl/GIT_HEAD_ID +++ b/polly/lib/External/isl/GIT_HEAD_ID @@ -1 +1 @@ -isl-0.18-662-g17e172e +isl-0.18-679-g6e75a0d diff --git a/polly/lib/External/isl/doc/user.pod b/polly/lib/External/isl/doc/user.pod index b012ddf54ea..163438d8e7d 100644 --- a/polly/lib/External/isl/doc/user.pod +++ b/polly/lib/External/isl/doc/user.pod @@ -2116,15 +2116,26 @@ has a unique value when the values of the other variables are known. Alternatively, the existentially quantified variables can be removed using the following functions, which compute an overapproximation. + #include <isl/set.h> __isl_give isl_basic_set *isl_basic_set_remove_divs( __isl_take isl_basic_set *bset); - __isl_give isl_basic_map *isl_basic_map_remove_divs( - __isl_take isl_basic_map *bmap); __isl_give isl_set *isl_set_remove_divs( __isl_take isl_set *set); + + #include <isl/map.h> + __isl_give isl_basic_map *isl_basic_map_remove_divs( + __isl_take isl_basic_map *bmap); __isl_give isl_map *isl_map_remove_divs( __isl_take isl_map *map); + #include <isl/union_set.h> + __isl_give isl_union_set *isl_union_set_remove_divs( + __isl_take isl_union_set *bset); + + #include <isl/union_map.h> + __isl_give isl_union_map *isl_union_map_remove_divs( + __isl_take isl_union_map *bmap); + It is also possible to only remove those divs that are defined in terms of a given range of dimensions or only those for which no explicit representation is known. @@ -2221,11 +2232,17 @@ from int isl_map_n_basic_map(__isl_keep isl_map *map); It is also possible to obtain a list of basic sets from a set +or union set #include <isl/set.h> __isl_give isl_basic_set_list *isl_set_get_basic_set_list( __isl_keep isl_set *set); + #include <isl/union_set.h> + __isl_give isl_basic_set_list * + isl_union_set_get_basic_set_list( + __isl_keep isl_union_set *uset); + The returned list can be manipulated using the functions in L<"Lists">. To iterate over the constraints of a basic set or map, use @@ -5148,8 +5165,12 @@ Fourier-Motzkin elimination, but this may change or be made optional in future. In particular, future implementations may use different dualization algorithms or skip the elimination step. + #include <isl/set.h> __isl_give isl_basic_set *isl_basic_set_coefficients( __isl_take isl_basic_set *bset); + __isl_give isl_basic_set_list * + isl_basic_set_list_coefficients( + __isl_take isl_basic_set_list *list); __isl_give isl_basic_set *isl_set_coefficients( __isl_take isl_set *set); __isl_give isl_union_set *isl_union_set_coefficients( @@ -7460,6 +7481,11 @@ Lists can be created, copied, modified and freed using the following functions. __isl_give isl_set_list *isl_set_list_concat( __isl_take isl_set_list *list1, __isl_take isl_set_list *list2); + __isl_give isl_set_list *isl_set_list_map( + __isl_take isl_set_list *list, + __isl_give isl_set *(*fn)(__isl_take isl_set *el, + void *user), + void *user); __isl_give isl_set_list *isl_set_list_sort( __isl_take isl_set_list *list, int (*cmp)(__isl_keep isl_set *a, diff --git a/polly/lib/External/isl/include/isl/list.h b/polly/lib/External/isl/include/isl/list.h index 948e565427b..803fd3af205 100644 --- a/polly/lib/External/isl/include/isl/list.h +++ b/polly/lib/External/isl/include/isl/list.h @@ -50,6 +50,11 @@ __isl_give struct isl_##EL##_list *isl_##EL##_list_set_##EL( \ isl_stat isl_##EL##_list_foreach(__isl_keep isl_##EL##_list *list, \ isl_stat (*fn)(__isl_take struct isl_##EL *el, void *user), \ void *user); \ +__isl_give isl_##EL##_list *isl_##EL##_list_map( \ + __isl_take isl_##EL##_list *list, \ + __isl_give isl_##EL * (*fn)(__isl_take isl_##EL *el, \ + void *user), \ + void *user); \ __isl_give isl_##EL##_list *isl_##EL##_list_sort( \ __isl_take isl_##EL##_list *list, \ int (*cmp)(__isl_keep struct isl_##EL *a, \ diff --git a/polly/lib/External/isl/include/isl/set.h b/polly/lib/External/isl/include/isl/set.h index c4e6e9b0be0..0ef45ab0c9f 100644 --- a/polly/lib/External/isl/include/isl/set.h +++ b/polly/lib/External/isl/include/isl/set.h @@ -489,6 +489,8 @@ __isl_give isl_mat *isl_basic_set_reduced_basis(__isl_keep isl_basic_set *bset); __isl_give isl_basic_set *isl_basic_set_coefficients( __isl_take isl_basic_set *bset); +__isl_give isl_basic_set_list *isl_basic_set_list_coefficients( + __isl_take isl_basic_set_list *list); __isl_give isl_basic_set *isl_set_coefficients(__isl_take isl_set *set); __isl_give isl_basic_set *isl_basic_set_solutions( __isl_take isl_basic_set *bset); diff --git a/polly/lib/External/isl/include/isl/union_map.h b/polly/lib/External/isl/include/isl/union_map.h index 40dea4f8982..fa2310ec84c 100644 --- a/polly/lib/External/isl/include/isl/union_map.h +++ b/polly/lib/External/isl/include/isl/union_map.h @@ -194,6 +194,8 @@ __isl_give isl_union_map *isl_union_set_identity(__isl_take isl_union_set *uset) __isl_give isl_union_map *isl_union_map_project_out( __isl_take isl_union_map *umap, enum isl_dim_type type, unsigned first, unsigned n); +__isl_give isl_union_map *isl_union_map_remove_divs( + __isl_take isl_union_map *bmap); __isl_export isl_bool isl_union_map_is_empty(__isl_keep isl_union_map *umap); diff --git a/polly/lib/External/isl/include/isl/union_set.h b/polly/lib/External/isl/include/isl/union_set.h index 26858a40020..ca4090b8c7b 100644 --- a/polly/lib/External/isl/include/isl/union_set.h +++ b/polly/lib/External/isl/include/isl/union_set.h @@ -91,6 +91,8 @@ __isl_give isl_union_set *isl_union_set_preimage_union_pw_multi_aff( __isl_give isl_union_set *isl_union_set_project_out( __isl_take isl_union_set *uset, enum isl_dim_type type, unsigned first, unsigned n); +__isl_give isl_union_set *isl_union_set_remove_divs( + __isl_take isl_union_set *bset); isl_bool isl_union_set_is_params(__isl_keep isl_union_set *uset); __isl_export @@ -114,6 +116,8 @@ int isl_union_set_n_set(__isl_keep isl_union_set *uset); __isl_export isl_stat isl_union_set_foreach_set(__isl_keep isl_union_set *uset, isl_stat (*fn)(__isl_take isl_set *set, void *user), void *user); +__isl_give isl_basic_set_list *isl_union_set_get_basic_set_list( + __isl_keep isl_union_set *uset); isl_bool isl_union_set_contains(__isl_keep isl_union_set *uset, __isl_keep isl_space *space); __isl_give isl_set *isl_union_set_extract_set(__isl_keep isl_union_set *uset, diff --git a/polly/lib/External/isl/isl_farkas.c b/polly/lib/External/isl/isl_farkas.c index eff8608b280..cb45a633a1c 100644 --- a/polly/lib/External/isl/isl_farkas.c +++ b/polly/lib/External/isl/isl_farkas.c @@ -371,6 +371,24 @@ __isl_give isl_basic_set *isl_set_coefficients(__isl_take isl_set *set) return coeff; } +/* Wrapper around isl_basic_set_coefficients for use + * as a isl_basic_set_list_map callback. + */ +static __isl_give isl_basic_set *coefficients_wrap( + __isl_take isl_basic_set *bset, void *user) +{ + return isl_basic_set_coefficients(bset); +} + +/* Replace the elements of "list" by the result of applying + * isl_basic_set_coefficients to them. + */ +__isl_give isl_basic_set_list *isl_basic_set_list_coefficients( + __isl_take isl_basic_set_list *list) +{ + return isl_basic_set_list_map(list, &coefficients_wrap, NULL); +} + /* Construct a basic set containing the elements that satisfy all * affine constraints whose coefficient tuples are * contained in the given set. diff --git a/polly/lib/External/isl/isl_list_templ.c b/polly/lib/External/isl/isl_list_templ.c index ebfd6483c78..7d0c5446d20 100644 --- a/polly/lib/External/isl/isl_list_templ.c +++ b/polly/lib/External/isl/isl_list_templ.c @@ -2,6 +2,7 @@ * Copyright 2008-2009 Katholieke Universiteit Leuven * Copyright 2011 INRIA Saclay * Copyright 2012-2013 Ecole Normale Superieure + * Copyright 2017 Sven Verdoolaege * * Use of this software is governed by the MIT license * @@ -130,6 +131,18 @@ static __isl_give LIST(EL) *FN(LIST(EL),grow)(__isl_take LIST(EL) *list, int n) return res; } +/* Check that "index" is a valid position in "list". + */ +static isl_stat FN(LIST(EL),check_index)(__isl_keep LIST(EL) *list, int index) +{ + if (!list) + return isl_stat_error; + if (index < 0 || index >= list->n) + isl_die(FN(LIST(EL),get_ctx)(list), isl_error_invalid, + "index out of bounds", return isl_stat_error); + return isl_stat_ok; +} + __isl_give LIST(EL) *FN(LIST(EL),add)(__isl_take LIST(EL) *list, __isl_take struct EL *el) { @@ -239,11 +252,8 @@ int FN(FN(LIST(EL),n),BASE)(__isl_keep LIST(EL) *list) __isl_give EL *FN(FN(LIST(EL),get),BASE)(__isl_keep LIST(EL) *list, int index) { - if (!list) + if (FN(LIST(EL),check_index)(list, index) < 0) return NULL; - if (index < 0 || index >= list->n) - isl_die(list->ctx, isl_error_invalid, - "index out of bounds", return NULL); return FN(EL,copy)(list->p[index]); } @@ -254,9 +264,8 @@ __isl_give LIST(EL) *FN(FN(LIST(EL),set),BASE)(__isl_take LIST(EL) *list, { if (!list || !el) goto error; - if (index < 0 || index >= list->n) - isl_die(list->ctx, isl_error_invalid, - "index out of bounds", goto error); + if (FN(LIST(EL),check_index)(list, index) < 0) + goto error; if (list->p[index] == el) { FN(EL,free)(el); return list; @@ -273,6 +282,40 @@ error: return NULL; } +/* Return the element at position "index" of "list". + * This may be either a copy or the element itself + * if there is only one reference to "list". + * This allows the element to be modified inplace + * if both the list and the element have only a single reference. + * The caller is not allowed to modify "list" between + * this call to isl_list_*_take_* and a subsequent call + * to isl_list_*_restore_*. + * The only exception is that isl_list_*_free can be called instead. + */ +static __isl_give EL *FN(FN(LIST(EL),take),BASE)(__isl_keep LIST(EL) *list, + int index) +{ + EL *el; + + if (FN(LIST(EL),check_index)(list, index) < 0) + return NULL; + if (list->ref != 1) + return FN(FN(LIST(EL),get),BASE)(list, index); + el = list->p[index]; + list->p[index] = NULL; + return el; +} + +/* Set the element at position "index" of "list" to "el", + * where the position may be empty due to a previous call + * to isl_list_*_take_*. + */ +static __isl_give LIST(EL) *FN(FN(LIST(EL),restore),BASE)( + __isl_take LIST(EL) *list, int index, __isl_take EL *el) +{ + return FN(FN(LIST(EL),set),BASE)(list, index, el); +} + isl_stat FN(LIST(EL),foreach)(__isl_keep LIST(EL) *list, isl_stat (*fn)(__isl_take EL *el, void *user), void *user) { @@ -292,6 +335,29 @@ isl_stat FN(LIST(EL),foreach)(__isl_keep LIST(EL) *list, return isl_stat_ok; } +/* Replace each element in "list" by the result of calling "fn" + * on the element. + */ +__isl_give LIST(EL) *FN(LIST(EL),map)(__isl_keep LIST(EL) *list, + __isl_give EL *(*fn)(__isl_take EL *el, void *user), void *user) +{ + int i, n; + + if (!list) + return NULL; + + n = list->n; + for (i = 0; i < n; ++i) { + EL *el = FN(FN(LIST(EL),take),BASE)(list, i); + if (!el) + return FN(LIST(EL),free)(list); + el = fn(el, user); + list = FN(FN(LIST(EL),restore),BASE)(list, i, el); + } + + return list; +} + /* Internal data structure for isl_*_list_sort. * * "cmp" is the original comparison function. @@ -461,6 +527,26 @@ error: return NULL; } +/* Append the elements of "list2" to "list1", where "list1" is known + * to have only a single reference and enough room to hold + * the extra elements. + */ +static __isl_give LIST(EL) *FN(LIST(EL),concat_inplace)( + __isl_take LIST(EL) *list1, __isl_take LIST(EL) *list2) +{ + int i; + + for (i = 0; i < list2->n; ++i) + list1 = FN(LIST(EL),add)(list1, FN(EL,copy)(list2->p[i])); + FN(LIST(EL),free)(list2); + return list1; +} + +/* Concatenate "list1" and "list2". + * If "list1" has only one reference and has enough room + * for the elements of "list2", the add the elements to "list1" itself. + * Otherwise, create a new list to store the result. + */ __isl_give LIST(EL) *FN(LIST(EL),concat)(__isl_take LIST(EL) *list1, __isl_take LIST(EL) *list2) { @@ -471,6 +557,9 @@ __isl_give LIST(EL) *FN(LIST(EL),concat)(__isl_take LIST(EL) *list1, if (!list1 || !list2) goto error; + if (list1->ref == 1 && list1->n + list2->n <= list1->size) + return FN(LIST(EL),concat_inplace)(list1, list2); + ctx = FN(LIST(EL),get_ctx)(list1); res = FN(LIST(EL),alloc)(ctx, list1->n + list2->n); for (i = 0; i < list1->n; ++i) diff --git a/polly/lib/External/isl/isl_scheduler.c b/polly/lib/External/isl/isl_scheduler.c index 4b660abcce6..e65194a27d1 100644 --- a/polly/lib/External/isl/isl_scheduler.c +++ b/polly/lib/External/isl/isl_scheduler.c @@ -3,6 +3,7 @@ * Copyright 2012-2014 Ecole Normale Superieure * Copyright 2015-2016 Sven Verdoolaege * Copyright 2016 INRIA Paris + * Copyright 2017 Sven Verdoolaege * * Use of this software is governed by the MIT license * @@ -1586,6 +1587,9 @@ static __isl_give isl_dim_map *intra_dim_map(isl_ctx *ctx, unsigned total; isl_dim_map *dim_map; + if (!node) + return NULL; + total = isl_basic_set_total_dim(graph->lp); pos = node_var_coef_offset(node); dim_map = isl_dim_map_alloc(ctx, total); @@ -1621,6 +1625,9 @@ static __isl_give isl_dim_map *inter_dim_map(isl_ctx *ctx, unsigned total; isl_dim_map *dim_map; + if (!src || !dst) + return NULL; + total = isl_basic_set_total_dim(graph->lp); dim_map = isl_dim_map_alloc(ctx, total); @@ -2061,11 +2068,7 @@ static int is_any_validity(struct isl_sched_edge *edge) /* How many times should we count the constraints in "edge"? * - * If carry is set, then we are counting the number of - * (validity or conditional validity) constraints that will be added - * in setup_carry_lp and we count each edge exactly once. - * - * Otherwise, we count as follows + * We count as follows * validity -> 1 (>= 0) * validity+proximity -> 2 (>= 0 and upper bound) * proximity -> 2 (lower and upper bound) @@ -2077,11 +2080,8 @@ static int is_any_validity(struct isl_sched_edge *edge) * If "use_coincidence" is set, then we treat coincidence edges as local edges. * Otherwise, we ignore them. */ -static int edge_multiplicity(struct isl_sched_edge *edge, int carry, - int use_coincidence) +static int edge_multiplicity(struct isl_sched_edge *edge, int use_coincidence) { - if (carry) - return 1; if (is_proximity(edge) || is_local(edge)) return 2; if (use_coincidence && is_coincidence(edge)) @@ -2098,10 +2098,10 @@ static int edge_multiplicity(struct isl_sched_edge *edge, int carry, */ static isl_stat count_map_constraints(struct isl_sched_graph *graph, struct isl_sched_edge *edge, __isl_take isl_map *map, - int *n_eq, int *n_ineq, int carry, int use_coincidence) + int *n_eq, int *n_ineq, int use_coincidence) { isl_basic_set *coef; - int f = edge_multiplicity(edge, carry, use_coincidence); + int f = edge_multiplicity(edge, use_coincidence); if (f == 0) { isl_map_free(map); @@ -2143,7 +2143,7 @@ static int count_constraints(struct isl_sched_graph *graph, isl_map *map = isl_map_copy(edge->map); if (count_map_constraints(graph, edge, map, n_eq, n_ineq, - 0, use_coincidence) < 0) + use_coincidence) < 0) return -1; } @@ -3521,165 +3521,260 @@ static __isl_give isl_schedule_node *compute_next_band( return node; } -/* Add constraints to graph->lp that force the dependence "map" (which - * is part of the dependence relation of "edge") - * to be respected and attempt to carry it, where the edge is one from - * a node j to itself. "pos" is the sequence number of the given map. - * That is, add constraints that enforce +/* Add the constraints "coef" derived from an edge from "node" to itself + * to graph->lp in order to respect the dependences and to try and carry them. + * "pos" is the sequence number of the edge that needs to be carried. + * "coef" represents general constraints on coefficients (c_0, c_n, c_x) + * of valid constraints for (y - x) with x and y instances of the node. + * + * The constraints added to graph->lp need to enforce * * (c_j_0 + c_j_n n + c_j_x y) - (c_j_0 + c_j_n n + c_j_x x) * = c_j_x (y - x) >= e_i * - * for each (x,y) in R. - * We obtain general constraints on coefficients (c_0, c_n, c_x) - * of valid constraints for (y - x) and then plug in (-e_i, 0, c_j_x), - * with each coefficient in c_j_x represented as a pair of non-negative - * coefficients. + * for each (x,y) in the dependence relation of the edge. + * That is, (-e_i, 0, c_j_x) needs to be plugged in for (c_0, c_n, c_x), + * taking into account that each coefficient in c_j_x is represented + * as a pair of non-negative coefficients. */ -static int add_intra_constraints(struct isl_sched_graph *graph, - struct isl_sched_edge *edge, __isl_take isl_map *map, int pos) +static isl_stat add_intra_constraints(struct isl_sched_graph *graph, + struct isl_sched_node *node, __isl_take isl_basic_set *coef, int pos) { int offset; - isl_ctx *ctx = isl_map_get_ctx(map); + isl_ctx *ctx; isl_dim_map *dim_map; - isl_basic_set *coef; - struct isl_sched_node *node = edge->src; - coef = intra_coefficients(graph, node, map); if (!coef) - return -1; + return isl_stat_error; + ctx = isl_basic_set_get_ctx(coef); offset = coef_var_offset(coef); dim_map = intra_dim_map(ctx, graph, node, offset, 1); isl_dim_map_range(dim_map, 3 + pos, 0, 0, 0, 1, -1); graph->lp = add_constraints_dim_map(graph->lp, coef, dim_map); - return 0; + return isl_stat_ok; } -/* Add constraints to graph->lp that force the dependence "map" (which - * is part of the dependence relation of "edge") - * to be respected and attempt to carry it, where the edge is one from - * node j to node k. "pos" is the sequence number of the given map. - * That is, add constraints that enforce +/* Add the constraints "coef" derived from an edge from "src" to "dst" + * to graph->lp in order to respect the dependences and to try and carry them. + * "pos" is the sequence number of the edge that needs to be carried. + * "coef" represents general constraints on coefficients (c_0, c_n, c_x, c_y) + * of valid constraints for (x, y) with x and y instances of "src" and "dst". + * + * The constraints added to graph->lp need to enforce * * (c_k_0 + c_k_n n + c_k_x y) - (c_j_0 + c_j_n n + c_j_x x) >= e_i * - * for each (x,y) in R. - * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y) - * of valid constraints for R and then plug in + * for each (x,y) in the dependence relation of the edge. + * That is, * (-e_i + c_k_0 - c_j_0, c_k_n - c_j_n, -c_j_x, c_k_x) - * with each coefficient (except e_i, c_*_0 and c_*_n) - * represented as a pair of non-negative coefficients. + * needs to be plugged in for (c_0, c_n, c_x, c_y), + * taking into account that each coefficient in c_j_x and c_k_x is represented + * as a pair of non-negative coefficients. */ -static int add_inter_constraints(struct isl_sched_graph *graph, - struct isl_sched_edge *edge, __isl_take isl_map *map, int pos) +static isl_stat add_inter_constraints(struct isl_sched_graph *graph, + struct isl_sched_node *src, struct isl_sched_node *dst, + __isl_take isl_basic_set *coef, int pos) { int offset; - isl_ctx *ctx = isl_map_get_ctx(map); + isl_ctx *ctx; isl_dim_map *dim_map; - isl_basic_set *coef; - struct isl_sched_node *src = edge->src; - struct isl_sched_node *dst = edge->dst; - coef = inter_coefficients(graph, edge, map); if (!coef) - return -1; + return isl_stat_error; + ctx = isl_basic_set_get_ctx(coef); offset = coef_var_offset(coef); dim_map = inter_dim_map(ctx, graph, src, dst, offset, 1); isl_dim_map_range(dim_map, 3 + pos, 0, 0, 0, 1, -1); graph->lp = add_constraints_dim_map(graph->lp, coef, dim_map); - return 0; + return isl_stat_ok; } -/* Add constraints to graph->lp that force all (conditional) validity - * dependences to be respected and attempt to carry them. +/* Data structure collecting information used during the construction + * of an LP for carrying dependences. + * + * "intra" is a sequence of coefficient constraints for intra-node edges. + * "inter" is a sequence of coefficient constraints for inter-node edges. */ -static isl_stat add_all_constraints(struct isl_sched_graph *graph) +struct isl_carry { + isl_basic_set_list *intra; + isl_basic_set_list *inter; +}; + +/* Free all the data stored in "carry". + */ +static void isl_carry_clear(struct isl_carry *carry) { - int i, j; - int pos; + isl_basic_set_list_free(carry->intra); + isl_basic_set_list_free(carry->inter); +} - pos = 0; - for (i = 0; i < graph->n_edge; ++i) { - struct isl_sched_edge *edge = &graph->edge[i]; +/* Return a pointer to the node in "graph" that lives in "space". + * If the requested node has been compressed, then "space" + * corresponds to the compressed space. + * + * First try and see if "space" is the space of an uncompressed node. + * If so, return that node. + * Otherwise, "space" was constructed by construct_compressed_id and + * contains a user pointer pointing to the node in the tuple id. + */ +static struct isl_sched_node *graph_find_compressed_node(isl_ctx *ctx, + struct isl_sched_graph *graph, __isl_keep isl_space *space) +{ + isl_id *id; + struct isl_sched_node *node; - if (!is_any_validity(edge)) - continue; + if (!space) + return NULL; - for (j = 0; j < edge->map->n; ++j) { - isl_basic_map *bmap; - isl_map *map; + node = graph_find_node(ctx, graph, space); + if (node) + return node; - bmap = isl_basic_map_copy(edge->map->p[j]); - map = isl_map_from_basic_map(bmap); + id = isl_space_get_tuple_id(space, isl_dim_set); + node = isl_id_get_user(id); + isl_id_free(id); - if (edge->src == edge->dst && - add_intra_constraints(graph, edge, map, pos) < 0) - return isl_stat_error; - if (edge->src != edge->dst && - add_inter_constraints(graph, edge, map, pos) < 0) - return isl_stat_error; - ++pos; - } - } + if (!node) + return NULL; - return isl_stat_ok; + if (!(node >= &graph->node[0] && node < &graph->node[graph->n])) + isl_die(ctx, isl_error_internal, + "space points to invalid node", return NULL); + + return node; } -/* Count the number of equality and inequality constraints - * that will be added to the carry_lp problem. - * We count each edge exactly once. +/* Internal data structure for add_all_constraints. + * + * "graph" is the schedule constraint graph for which an LP problem + * is being constructed. + * "pos" is the position of the next edge that needs to be carried. + */ +struct isl_add_all_constraints_data { + isl_ctx *ctx; + struct isl_sched_graph *graph; + int pos; +}; + +/* Add the constraints "coef" derived from an edge from a node to itself + * to data->graph->lp in order to respect the dependences and + * to try and carry them. + * + * The space of "coef" is of the form + * + * coefficients[[c_cst, c_n] -> S[c_x]] + * + * with S[c_x] the (compressed) space of the node. + * Extract the node from the space and call add_intra_constraints. */ -static isl_stat count_all_constraints(struct isl_sched_graph *graph, - int *n_eq, int *n_ineq) +static isl_stat lp_add_intra(__isl_take isl_basic_set *coef, void *user) { - int i, j; + struct isl_add_all_constraints_data *data = user; + isl_space *space; + struct isl_sched_node *node; - *n_eq = *n_ineq = 0; - for (i = 0; i < graph->n_edge; ++i) { - struct isl_sched_edge *edge = &graph->edge[i]; + space = isl_basic_set_get_space(coef); + space = isl_space_range(isl_space_unwrap(space)); + node = graph_find_compressed_node(data->ctx, data->graph, space); + isl_space_free(space); + return add_intra_constraints(data->graph, node, coef, data->pos++); +} - if (!is_any_validity(edge)) - continue; +/* Add the constraints "coef" derived from an edge from a node j + * to a node k to data->graph->lp in order to respect the dependences and + * to try and carry them. + * + * The space of "coef" is of the form + * + * coefficients[[c_cst, c_n] -> [S_j[c_x] -> S_k[c_y]]] + * + * with S_j[c_x] and S_k[c_y] the (compressed) spaces of the nodes. + * Extract the nodes from the space and call add_inter_constraints. + */ +static isl_stat lp_add_inter(__isl_take isl_basic_set *coef, void *user) +{ + struct isl_add_all_constraints_data *data = user; + isl_space *space, *dom; + struct isl_sched_node *src, *dst; - for (j = 0; j < edge->map->n; ++j) { - isl_basic_map *bmap; - isl_map *map; + space = isl_basic_set_get_space(coef); + space = isl_space_unwrap(isl_space_range(isl_space_unwrap(space))); + dom = isl_space_domain(isl_space_copy(space)); + src = graph_find_compressed_node(data->ctx, data->graph, dom); + isl_space_free(dom); + space = isl_space_range(space); + dst = graph_find_compressed_node(data->ctx, data->graph, space); + isl_space_free(space); - bmap = isl_basic_map_copy(edge->map->p[j]); - map = isl_map_from_basic_map(bmap); + return add_inter_constraints(data->graph, src, dst, coef, data->pos++); +} - if (count_map_constraints(graph, edge, map, - n_eq, n_ineq, 1, 0) < 0) - return isl_stat_error; - } - } +/* Add constraints to graph->lp that force all (conditional) validity + * dependences to be respected and attempt to carry them. + * "intra" is the sequence of coefficient constraints for intra-node edges. + * "inter" is the sequence of coefficient constraints for inter-node edges. + */ +static isl_stat add_all_constraints(isl_ctx *ctx, struct isl_sched_graph *graph, + __isl_keep isl_basic_set_list *intra, + __isl_keep isl_basic_set_list *inter) +{ + struct isl_add_all_constraints_data data = { ctx, graph }; + data.pos = 0; + if (isl_basic_set_list_foreach(intra, &lp_add_intra, &data) < 0) + return isl_stat_error; + if (isl_basic_set_list_foreach(inter, &lp_add_inter, &data) < 0) + return isl_stat_error; return isl_stat_ok; } -/* Return the total number of (validity) edges that carry_dependences will - * attempt to carry. +/* Internal data structure for count_all_constraints + * for keeping track of the number of equality and inequality constraints. */ -static int count_carry_edges(struct isl_sched_graph *graph) +struct isl_sched_count { + int n_eq; + int n_ineq; +}; + +/* Add the number of equality and inequality constraints of "bset" + * to data->n_eq and data->n_ineq. + */ +static isl_stat bset_update_count(__isl_take isl_basic_set *bset, void *user) { - int i; - int n_edge; + struct isl_sched_count *data = user; - n_edge = 0; - for (i = 0; i < graph->n_edge; ++i) { - struct isl_sched_edge *edge = &graph->edge[i]; + data->n_eq += isl_basic_set_n_equality(bset); + data->n_ineq += isl_basic_set_n_inequality(bset); + isl_basic_set_free(bset); - if (!is_any_validity(edge)) - continue; + return isl_stat_ok; +} - n_edge += isl_map_n_basic_map(edge->map); - } +/* Count the number of equality and inequality constraints + * that will be added to the carry_lp problem. + * We count each edge exactly once. + * "intra" is the sequence of coefficient constraints for intra-node edges. + * "inter" is the sequence of coefficient constraints for inter-node edges. + */ +static isl_stat count_all_constraints(__isl_keep isl_basic_set_list *intra, + __isl_keep isl_basic_set_list *inter, int *n_eq, int *n_ineq) +{ + struct isl_sched_count data; - return n_edge; + data.n_eq = data.n_ineq = 0; + if (isl_basic_set_list_foreach(inter, &bset_update_count, &data) < 0) + return isl_stat_error; + if (isl_basic_set_list_foreach(intra, &bset_update_count, &data) < 0) + return isl_stat_error; + + *n_eq = data.n_eq; + *n_ineq = data.n_ineq; + + return isl_stat_ok; } /* Construct an LP problem for finding schedule coefficients @@ -3688,12 +3783,9 @@ static int count_carry_edges(struct isl_sched_graph *graph) * from below by e_i, with 0 <= e_i <= 1 and then maximize the sum * of all e_i's. Dependences with e_i = 0 in the solution are simply * respected, while those with e_i > 0 (in practice e_i = 1) are carried. - * Note that if the dependence relation is a union of basic maps, - * then we have to consider each basic map individually as it may only - * be possible to carry the dependences expressed by some of those - * basic maps and not all of them. - * Below, we consider each of those basic maps as a separate "edge". - * "n_edge" is the number of these edges. + * "intra" is the sequence of coefficient constraints for intra-node edges. + * "inter" is the sequence of coefficient constraints for inter-node edges. + * "n_edge" is the total number of edges. * * All variables of the LP are non-negative. The actual coefficients * may be negative, so each coefficient is represented as the difference @@ -3716,7 +3808,8 @@ static int count_carry_edges(struct isl_sched_graph *graph) * to express the sums and n_edge inequalities to express e_i <= 1. */ static isl_stat setup_carry_lp(isl_ctx *ctx, struct isl_sched_graph *graph, - int n_edge) + int n_edge, __isl_keep isl_basic_set_list *intra, + __isl_keep isl_basic_set_list *inter) { int i; int k; @@ -3731,7 +3824,7 @@ static isl_stat setup_carry_lp(isl_ctx *ctx, struct isl_sched_graph *graph, total += 1 + node->nparam + 2 * node->nvar; } - if (count_all_constraints(graph, &n_eq, &n_ineq) < 0) + if (count_all_constraints(intra, inter, &n_eq, &n_ineq) < 0) return isl_stat_error; dim = isl_space_set_alloc(ctx, 0, total); @@ -3764,7 +3857,7 @@ static isl_stat setup_carry_lp(isl_ctx *ctx, struct isl_sched_graph *graph, isl_int_set_si(graph->lp->ineq[k][0], 1); } - if (add_all_constraints(graph) < 0) + if (add_all_constraints(ctx, graph, intra, inter) < 0) return isl_stat_error; return isl_stat_ok; @@ -4092,10 +4185,12 @@ static int carries_dependences(__isl_keep isl_vec *sol, int n_edge) /* Return the lexicographically smallest rational point in "lp", * assuming that all variables are non-negative and performing some * additional sanity checks. + * If "want_integral" is set, then compute the lexicographically smallest + * integer point instead. * In particular, "lp" should not be empty by construction. * Double check that this is the case. - * Also, check that dependences are carried for at least one of - * the "n_edge" edges. + * If dependences are not carried for any of the "n_edge" edges, + * then return an empty vector. * * If the schedule_treat_coalescing option is set and * if the computed schedule performs loop coalescing on a given node, @@ -4107,11 +4202,22 @@ static int carries_dependences(__isl_keep isl_vec *sol, int n_edge) * to cut out this solution. Repeat this process until no more loop * coalescing occurs or until no more dependences can be carried. * In the latter case, revert to the previously computed solution. + * + * If the caller requests an integral solution and if coalescing should + * be treated, then perform the coalescing treatment first as + * an integral solution computed before coalescing treatment + * would carry the same number of edges and would therefore probably + * also be coalescing. + * + * To allow the coalescing treatment to be performed first, + * the initial solution is allowed to be rational and it is only + * cut out (if needed) in the next iteration, if no coalescing measures + * were taken. */ static __isl_give isl_vec *non_neg_lexmin(struct isl_sched_graph *graph, - __isl_take isl_basic_set *lp, int n_edge) + __isl_take isl_basic_set *lp, int n_edge, int want_integral) { - int i, pos; + int i, pos, cut; isl_ctx *ctx; isl_tab_lexmin *tl; isl_vec *sol, *prev = NULL; @@ -4123,23 +4229,30 @@ static __isl_give isl_vec *non_neg_lexmin(struct isl_sched_graph *graph, treat_coalescing = isl_options_get_schedule_treat_coalescing(ctx); tl = isl_tab_lexmin_from_basic_set(lp); + cut = 0; do { + int integral; + + if (cut) + tl = isl_tab_lexmin_cut_to_integer(tl); sol = non_empty_solution(tl); if (!sol) goto error; + integral = isl_int_is_one(sol->el[0]); if (!carries_dependences(sol, n_edge)) { if (!prev) - isl_die(ctx, isl_error_unknown, - "unable to carry dependences", - goto error); + prev = isl_vec_alloc(ctx, 0); isl_vec_free(sol); sol = prev; break; } prev = isl_vec_free(prev); + cut = want_integral && !integral; + if (cut) + prev = sol; if (!treat_coalescing) - break; + continue; for (i = 0; i < graph->n; ++i) { struct isl_sched_node *node = &graph->node[i]; @@ -4152,8 +4265,9 @@ static __isl_give isl_vec *non_neg_lexmin(struct isl_sched_graph *graph, if (i < graph->n) { prev = sol; tl = zero_out_node_coef(tl, &graph->node[i], pos); + cut = 0; } - } while (i < graph->n); + } while (prev); isl_tab_lexmin_free(tl); @@ -4165,14 +4279,228 @@ error: return NULL; } +/* If "edge" is an edge from a node to itself, then add the corresponding + * dependence relation to "umap". + * If "node" has been compressed, then the dependence relation + * is also compressed first. + */ +static __isl_give isl_union_map *add_intra(__isl_take isl_union_map *umap, + struct isl_sched_edge *edge) +{ + isl_map *map; + struct isl_sched_node *node = edge->src; + + if (edge->src != edge->dst) + return umap; + + map = isl_map_copy(edge->map); + if (node->compressed) { + map = isl_map_preimage_domain_multi_aff(map, + isl_multi_aff_copy(node->decompress)); + map = isl_map_preimage_range_multi_aff(map, + isl_multi_aff_copy(node->decompress)); + } + umap = isl_union_map_add_map(umap, map); + return umap; +} + +/* If "edge" is an edge from a node to another node, then add the corresponding + * dependence relation to "umap". + * If the source or destination nodes of "edge" have been compressed, + * then the dependence relation is also compressed first. + */ +static __isl_give isl_union_map *add_inter(__isl_take isl_union_map *umap, + struct isl_sched_edge *edge) +{ + isl_map *map; + + if (edge->src == edge->dst) + return umap; + + map = isl_map_copy(edge->map); + if (edge->src->compressed) + map = isl_map_preimage_domain_multi_aff(map, + isl_multi_aff_copy(edge->src->decompress)); + if (edge->dst->compressed) + map = isl_map_preimage_range_multi_aff(map, + isl_multi_aff_copy(edge->dst->decompress)); + umap = isl_union_map_add_map(umap, map); + return umap; +} + +/* For each (conditional) validity edge in "graph", + * add the corresponding dependence relation using "add" + * to a collection of dependence relations and return the result. + * If "coincidence" is set, then coincidence edges are considered as well. + */ +static __isl_give isl_union_map *collect_validity(struct isl_sched_graph *graph, + __isl_give isl_union_map *(*add)(__isl_take isl_union_map *umap, + struct isl_sched_edge *edge), int coincidence) +{ + int i; + isl_space *space; + isl_union_map *umap; + + space = isl_space_copy(graph->node[0].space); + umap = isl_union_map_empty(space); + + for (i = 0; i < graph->n_edge; ++i) { + struct isl_sched_edge *edge = &graph->edge[i]; + + if (!is_any_validity(edge) && + (!coincidence || !is_coincidence(edge))) + continue; + + umap = add(umap, edge); + } + + return umap; +} + +/* For each dependence relation on a (conditional) validity edge + * from a node to itself, + * construct the set of coefficients of valid constraints for elements + * in that dependence relation and collect the results. + * If "coincidence" is set, then coincidence edges are considered as well. + * + * In particular, for each dependence relation R, constraints + * on coefficients (c_0, c_n, c_x) are constructed such that + * + * c_0 + c_n n + c_x d >= 0 for each d in delta R = { y - x | (x,y) in R } + * + * This computation is essentially the same as that performed + * by intra_coefficients, except that it operates on multiple + * edges together. + * + * Note that if a dependence relation is a union of basic maps, + * then each basic map needs to be treated individually as it may only + * be possible to carry the dependences expressed by some of those + * basic maps and not all of them. + * The collected validity constraints are therefore not coalesced and + * it is assumed that they are not coalesced automatically. + * Duplicate basic maps can be removed, however. + * In particular, if the same basic map appears as a disjunct + * in multiple edges, then it only needs to be carried once. + */ +static __isl_give isl_basic_set_list *collect_intra_validity( + struct isl_sched_graph *graph, int coincidence) +{ + isl_union_map *intra; + isl_union_set *delta; + isl_basic_set_list *list; + + intra = collect_validity(graph, &add_intra, coincidence); + delta = isl_union_map_deltas(intra); + delta = isl_union_set_remove_divs(delta); + list = isl_union_set_get_basic_set_list(delta); + isl_union_set_free(delta); + + return isl_basic_set_list_coefficients(list); +} + +/* For each dependence relation on a (conditional) validity edge + * from a node to some other node, + * construct the set of coefficients of valid constraints for elements + * in that dependence relation and collect the results. + * If "coincidence" is set, then coincidence edges are considered as well. + * + * In particular, for each dependence relation R, constraints + * on coefficients (c_0, c_n, c_x, c_y) are constructed such that + * + * c_0 + c_n n + c_x x + c_y y >= 0 for each (x,y) in R + * + * This computation is essentially the same as that performed + * by inter_coefficients, except that it operates on multiple + * edges together. + * + * Note that if a dependence relation is a union of basic maps, + * then each basic map needs to be treated individually as it may only + * be possible to carry the dependences expressed by some of those + * basic maps and not all of them. + * The collected validity constraints are therefore not coalesced and + * it is assumed that they are not coalesced automatically. + * Duplicate basic maps can be removed, however. + * In particular, if the same basic map appears as a disjunct + * in multiple edges, then it only needs to be carried once. + */ +static __isl_give isl_basic_set_list *collect_inter_validity( + struct isl_sched_graph *graph, int coincidence) +{ + isl_union_map *inter; + isl_union_set *wrap; + isl_basic_set_list *list; + + inter = collect_validity(graph, &add_inter, coincidence); + inter = isl_union_map_remove_divs(inter); + wrap = isl_union_map_wrap(inter); + list = isl_union_set_get_basic_set_list(wrap); + isl_union_set_free(wrap); + return isl_basic_set_list_coefficients(list); +} + +/* Construct an LP problem for finding schedule coefficients + * such that the schedule carries as many of the validity dependences + * as possible and + * return the lexicographically smallest non-trivial solution. + * If "fallback" is set, then the carrying is performed as a fallback + * for the Pluto-like scheduler. + * If "coincidence" is set, then try and carry coincidence edges as well. + * + * The variable "n_edge" stores the number of groups that should be carried. + * If none of the "n_edge" groups can be carried + * then return an empty vector. + * If, moreover, "n_edge" is zero, then the LP problem does not even + * need to be constructed. + * + * If a fallback solution is being computed, then compute an integral solution + * for the coefficients rather than using the numerators + * of a rational solution. + */ +static __isl_give isl_vec *compute_carrying_sol(isl_ctx *ctx, + struct isl_sched_graph *graph, int fallback, int coincidence) +{ + int n_intra, n_inter; + int n_edge; + isl_basic_set *lp; + struct isl_carry carry = { 0 }; + + carry.intra = collect_intra_validity(graph, coincidence); + carry.inter = collect_inter_validity(graph, coincidence); + if (!carry.intra || !carry.inter) + goto error; + n_intra = isl_basic_set_list_n_basic_set(carry.intra); + n_inter = isl_basic_set_list_n_basic_set(carry.inter); + n_edge = n_intra + n_inter; + if (n_edge == 0) { + isl_carry_clear(&carry); + return isl_vec_alloc(ctx, 0); + } + + if (setup_carry_lp(ctx, graph, n_edge, carry.intra, carry.inter) < 0) + goto error; + + isl_carry_clear(&carry); + lp = isl_basic_set_copy(graph->lp); + return non_neg_lexmin(graph, lp, n_edge, fallback); +error: + isl_carry_clear(&carry); + return NULL; +} + /* Construct a schedule row for each node such that as many validity dependences * as possible are carried and then continue with the next band. + * If "fallback" is set, then the carrying is performed as a fallback + * for the Pluto-like scheduler. + * If "coincidence" is set, then try and carry coincidence edges as well. * * If there are no validity dependences, then no dependence can be carried and * the procedure is guaranteed to fail. If there is more than one component, * then try computing a schedule on each component separately * to prevent or at least postpone this failure. * + * If a schedule row is computed, then check that dependences are carried + * for at least one of the edges. + * * If the computed schedule row turns out to be trivial on one or * more nodes where it should not be trivial, then we throw it away * and try again on each component separately. @@ -4190,30 +4518,27 @@ error: * This insertion and the continued construction is performed by split_scaled * after optionally checking for non-trivial common divisors. */ -static __isl_give isl_schedule_node *carry_dependences( - __isl_take isl_schedule_node *node, struct isl_sched_graph *graph) +static __isl_give isl_schedule_node *carry(__isl_take isl_schedule_node *node, + struct isl_sched_graph *graph, int fallback, int coincidence) { - int n_edge; int trivial; isl_ctx *ctx; isl_vec *sol; - isl_basic_set *lp; if (!node) return NULL; - n_edge = count_carry_edges(graph); - if (n_edge == 0 && graph->scc > 1) - return compute_component_schedule(node, graph, 1); - ctx = isl_schedule_node_get_ctx(node); - if (setup_carry_lp(ctx, graph, n_edge) < 0) - return isl_schedule_node_free(node); - - lp = isl_basic_set_copy(graph->lp); - sol = non_neg_lexmin(graph, lp, n_edge); + sol = compute_carrying_sol(ctx, graph, fallback, coincidence); if (!sol) return isl_schedule_node_free(node); + if (sol->size == 0) { + isl_vec_free(sol); + if (graph->scc > 1) + return compute_component_schedule(node, graph, 1); + isl_die(ctx, isl_error_unknown, "unable to carry dependences", + return isl_schedule_node_free(node)); + } trivial = is_any_trivial(graph, sol); if (trivial < 0) { @@ -4231,6 +4556,50 @@ static __isl_give isl_schedule_node *carry_dependences( return split_scaled(node, graph); } +/* Construct a schedule row for each node such that as many validity dependences + * as possible are carried and then continue with the next band. + * Do so as a fallback for the Pluto-like scheduler. + * If "coincidence" is set, then try and carry coincidence edges as well. + */ +static __isl_give isl_schedule_node *carry_fallback( + __isl_take isl_schedule_node *node, struct isl_sched_graph *graph, + int coincidence) +{ + return carry(node, graph, 1, coincidence); +} + +/* Construct a schedule row for each node such that as many validity dependences + * as possible are carried and then continue with the next band. + * Do so for the case where the Feautrier scheduler was selected + * by the user. + */ +static __isl_give isl_schedule_node *carry_feautrier( + __isl_take isl_schedule_node *node, struct isl_sched_graph *graph) +{ + return carry(node, graph, 0, 0); +} + +/* Construct a schedule row for each node such that as many validity dependences + * as possible are carried and then continue with the next band. + * Do so as a fallback for the Pluto-like scheduler. + */ +static __isl_give isl_schedule_node *carry_dependences( + __isl_take isl_schedule_node *node, struct isl_sched_graph *graph) +{ + return carry_fallback(node, graph, 0); +} + +/* Construct a schedule row for each node such that as many validity or + * coincidence dependences as possible are carried and + * then continue with the next band. + * Do so as a fallback for the Pluto-like scheduler. + */ +static __isl_give isl_schedule_node *carry_coincidence( + __isl_take isl_schedule_node *node, struct isl_sched_graph *graph) +{ + return carry_fallback(node, graph, 1); +} + /* Topologically sort statements mapped to the same schedule iteration * and add insert a sequence node in front of "node" * corresponding to this order. @@ -4331,7 +4700,7 @@ static int need_feautrier_step(isl_ctx *ctx, struct isl_sched_graph *graph) static __isl_give isl_schedule_node *compute_schedule_wcc_feautrier( isl_schedule_node *node, struct isl_sched_graph *graph) { - return carry_dependences(node, graph); + return carry_feautrier(node, graph); } /* Turn off the "local" bit on all (condition) edges. @@ -4540,8 +4909,11 @@ error: * pair of SCCs between which to split) * - continue with the next band (assuming the current band has at least * one row) - * - try to carry as many dependences as possible and continue with the next - * band + * - if outer coincidence needs to be enforced, then try to carry as many + * validity or coincidence dependences as possible and + * continue with the next band + * - try to carry as many validity dependences as possible and + * continue with the next band * In each case, we first insert a band node in the schedule tree * if any rows have been computed. * @@ -4571,6 +4943,8 @@ static __isl_give isl_schedule_node *compute_schedule_finish_band( return compute_next_band(node, graph, 1); if (!initialized && compute_maxvar(graph) < 0) return isl_schedule_node_free(node); + if (isl_options_get_schedule_outer_coincidence(ctx)) + return carry_coincidence(node, graph); return carry_dependences(node, graph); } diff --git a/polly/lib/External/isl/isl_tab.h b/polly/lib/External/isl/isl_tab.h index a8bc77a0a69..c1ba670a2c9 100644 --- a/polly/lib/External/isl/isl_tab.h +++ b/polly/lib/External/isl/isl_tab.h @@ -281,6 +281,8 @@ __isl_give isl_tab_lexmin *isl_tab_lexmin_from_basic_set( int isl_tab_lexmin_dim(__isl_keep isl_tab_lexmin *tl); __isl_give isl_tab_lexmin *isl_tab_lexmin_add_eq(__isl_take isl_tab_lexmin *tl, isl_int *eq); +__isl_give isl_tab_lexmin *isl_tab_lexmin_cut_to_integer( + __isl_take isl_tab_lexmin *tl); __isl_give isl_vec *isl_tab_lexmin_get_solution(__isl_keep isl_tab_lexmin *tl); __isl_null isl_tab_lexmin *isl_tab_lexmin_free(__isl_take isl_tab_lexmin *tl); diff --git a/polly/lib/External/isl/isl_tab_pip.c b/polly/lib/External/isl/isl_tab_pip.c index f342a168f18..a488f33f797 100644 --- a/polly/lib/External/isl/isl_tab_pip.c +++ b/polly/lib/External/isl/isl_tab_pip.c @@ -5426,6 +5426,20 @@ __isl_give isl_tab_lexmin *isl_tab_lexmin_add_eq(__isl_take isl_tab_lexmin *tl, return tl; } +/* Add cuts to "tl" until the sample value reaches an integer value or + * until the result becomes empty. + */ +__isl_give isl_tab_lexmin *isl_tab_lexmin_cut_to_integer( + __isl_take isl_tab_lexmin *tl) +{ + if (!tl) + return NULL; + tl->tab = cut_to_integer_lexmin(tl->tab, CUT_ONE); + if (!tl->tab) + return isl_tab_lexmin_free(tl); + return tl; +} + /* Return the lexicographically smallest rational point in the basic set * from which "tl" was constructed. * If the original input was empty, then return a zero-length vector. diff --git a/polly/lib/External/isl/isl_union_map.c b/polly/lib/External/isl/isl_union_map.c index 5fc9ac5aa43..159ef6facf0 100644 --- a/polly/lib/External/isl/isl_union_map.c +++ b/polly/lib/External/isl/isl_union_map.c @@ -3463,6 +3463,24 @@ __isl_give isl_union_set *isl_union_set_reset_user( return isl_union_map_reset_user(uset); } +/* Remove all existentially quantified variables and integer divisions + * from "umap" using Fourier-Motzkin elimination. + */ +__isl_give isl_union_map *isl_union_map_remove_divs( + __isl_take isl_union_map *umap) +{ + return total(umap, &isl_map_remove_divs); +} + +/* Remove all existentially quantified variables and integer divisions + * from "uset" using Fourier-Motzkin elimination. + */ +__isl_give isl_union_set *isl_union_set_remove_divs( + __isl_take isl_union_set *uset) +{ + return isl_union_map_remove_divs(uset); +} + /* Internal data structure for isl_union_map_project_out. * "type", "first" and "n" are the arguments for the isl_map_project_out * call. @@ -3789,3 +3807,68 @@ uint32_t isl_union_set_get_hash(__isl_keep isl_union_set *uset) { return isl_union_map_get_hash(uset); } + +/* Add the number of basic sets in "set" to "n". + */ +static isl_stat add_n(__isl_take isl_set *set, void *user) +{ + int *n = user; + + *n += isl_set_n_basic_set(set); + isl_set_free(set); + + return isl_stat_ok; +} + +/* Return the total number of basic sets in "uset". + */ +int isl_union_set_n_basic_set(__isl_keep isl_union_set *uset) +{ + int n = 0; + + if (isl_union_set_foreach_set(uset, &add_n, &n) < 0) + return -1; + + return n; +} + +/* Add the basic sets in "set" to "list". + */ +static isl_stat add_list(__isl_take isl_set *set, void *user) +{ + isl_basic_set_list **list = user; + isl_basic_set_list *list_i; + + list_i = isl_set_get_basic_set_list(set); + *list = isl_basic_set_list_concat(*list, list_i); + isl_set_free(set); + + if (!*list) + return isl_stat_error; + return isl_stat_ok; +} + +/* Return a list containing all the basic sets in "uset". + * + * First construct a list of the appropriate size and + * then add all the elements. + */ +__isl_give isl_basic_set_list *isl_union_set_get_basic_set_list( + __isl_keep isl_union_set *uset) +{ + int n; + isl_ctx *ctx; + isl_basic_set_list *list; + + if (!uset) + return NULL; + ctx = isl_union_set_get_ctx(uset); + n = isl_union_set_n_basic_set(uset); + if (n < 0) + return NULL; + list = isl_basic_set_list_alloc(ctx, n); + if (isl_union_set_foreach_set(uset, &add_list, &list) < 0) + list = isl_basic_set_list_free(list); + + return list; +} |
