From 23b40efbbbfced149584994d03c85dabbc20a258 Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Mon, 25 May 2009 14:01:02 +0200 Subject: [PATCH] add isl_map_coalesce --- include/isl_map.h | 2 + isl_coalesce.c | 445 ++++++++++++++++++++++++++++-------------------------- 2 files changed, 229 insertions(+), 218 deletions(-) diff --git a/include/isl_map.h b/include/isl_map.h index d027f1a..000e417 100644 --- a/include/isl_map.h +++ b/include/isl_map.h @@ -265,6 +265,8 @@ void isl_map_dump(struct isl_map *map, FILE *out, int indent); int isl_map_fast_input_is_fixed(struct isl_map *map, unsigned in, isl_int *val); +struct isl_map *isl_map_coalesce(struct isl_map *map); + int isl_map_fast_is_equal(struct isl_map *map1, struct isl_map *map2); #if defined(__cplusplus) diff --git a/isl_coalesce.c b/isl_coalesce.c index 0d5da2f..3bb18b8 100644 --- a/isl_coalesce.c +++ b/isl_coalesce.c @@ -22,24 +22,24 @@ static int status_in(struct isl_ctx *ctx, isl_int *ineq, struct isl_tab *tab) } } -/* Compute the position of the equalities of basic set "i" - * with respect to basic set "j". +/* Compute the position of the equalities of basic map "i" + * with respect to basic map "j". * The resulting array has twice as many entries as the number * of equalities corresponding to the two inequalties to which * each equality corresponds. */ -static int *eq_status_in(struct isl_set *set, int i, int j, +static int *eq_status_in(struct isl_map *map, int i, int j, struct isl_tab **tabs) { int k, l; - int *eq = isl_calloc_array(set->ctx, int, 2 * set->p[i]->n_eq); + int *eq = isl_calloc_array(map->ctx, int, 2 * map->p[i]->n_eq); unsigned dim; - dim = isl_basic_set_total_dim(set->p[i]); - for (k = 0; k < set->p[i]->n_eq; ++k) { + dim = isl_basic_map_total_dim(map->p[i]); + for (k = 0; k < map->p[i]->n_eq; ++k) { for (l = 0; l < 2; ++l) { - isl_seq_neg(set->p[i]->eq[k], set->p[i]->eq[k], 1+dim); - eq[2 * k + l] = status_in(set->ctx, set->p[i]->eq[k], + isl_seq_neg(map->p[i]->eq[k], map->p[i]->eq[k], 1+dim); + eq[2 * k + l] = status_in(map->ctx, map->p[i]->eq[k], tabs[j]); if (eq[2 * k + l] == STATUS_ERROR) goto error; @@ -55,22 +55,22 @@ error: return NULL; } -/* Compute the position of the inequalities of basic set "i" - * with respect to basic set "j". +/* Compute the position of the inequalities of basic map "i" + * with respect to basic map "j". */ -static int *ineq_status_in(struct isl_set *set, int i, int j, +static int *ineq_status_in(struct isl_map *map, int i, int j, struct isl_tab **tabs) { int k; - unsigned n_eq = set->p[i]->n_eq; - int *ineq = isl_calloc_array(set->ctx, int, set->p[i]->n_ineq); + unsigned n_eq = map->p[i]->n_eq; + int *ineq = isl_calloc_array(map->ctx, int, map->p[i]->n_ineq); - for (k = 0; k < set->p[i]->n_ineq; ++k) { - if (isl_tab_is_redundant(set->ctx, tabs[i], n_eq + k)) { + for (k = 0; k < map->p[i]->n_ineq; ++k) { + if (isl_tab_is_redundant(map->ctx, tabs[i], n_eq + k)) { ineq[k] = STATUS_REDUNDANT; continue; } - ineq[k] = status_in(set->ctx, set->p[i]->ineq[k], tabs[j]); + ineq[k] = status_in(map->ctx, map->p[i]->ineq[k], tabs[j]); if (ineq[k] == STATUS_ERROR) goto error; if (ineq[k] == STATUS_SEPARATE) @@ -117,94 +117,94 @@ static int all(int *con, unsigned len, int status) return 1; } -static void drop(struct isl_set *set, int i, struct isl_tab **tabs) +static void drop(struct isl_map *map, int i, struct isl_tab **tabs) { - isl_basic_set_free(set->p[i]); - isl_tab_free(set->ctx, tabs[i]); + isl_basic_map_free(map->p[i]); + isl_tab_free(map->ctx, tabs[i]); - if (i != set->n - 1) { - set->p[i] = set->p[set->n - 1]; - tabs[i] = tabs[set->n - 1]; + if (i != map->n - 1) { + map->p[i] = map->p[map->n - 1]; + tabs[i] = tabs[map->n - 1]; } - tabs[set->n - 1] = NULL; - set->n--; + tabs[map->n - 1] = NULL; + map->n--; } -/* Replace the pair of basic sets i and j but the basic set bounded - * by the valid constraints in both basic sets. +/* Replace the pair of basic maps i and j but the basic map bounded + * by the valid constraints in both basic maps. */ -static int fuse(struct isl_set *set, int i, int j, struct isl_tab **tabs, +static int fuse(struct isl_map *map, int i, int j, struct isl_tab **tabs, int *ineq_i, int *ineq_j) { int k, l; - struct isl_basic_set *fused = NULL; + struct isl_basic_map *fused = NULL; struct isl_tab *fused_tab = NULL; - unsigned total = isl_basic_set_total_dim(set->p[i]); + unsigned total = isl_basic_map_total_dim(map->p[i]); - fused = isl_basic_set_alloc_dim(isl_dim_copy(set->p[i]->dim), - set->p[i]->n_div, - set->p[i]->n_eq + set->p[j]->n_eq, - set->p[i]->n_ineq + set->p[j]->n_ineq); + fused = isl_basic_map_alloc_dim(isl_dim_copy(map->p[i]->dim), + map->p[i]->n_div, + map->p[i]->n_eq + map->p[j]->n_eq, + map->p[i]->n_ineq + map->p[j]->n_ineq); if (!fused) goto error; - for (k = 0; k < set->p[i]->n_eq; ++k) { - int l = isl_basic_set_alloc_equality(fused); - isl_seq_cpy(fused->eq[l], set->p[i]->eq[k], 1 + total); + for (k = 0; k < map->p[i]->n_eq; ++k) { + int l = isl_basic_map_alloc_equality(fused); + isl_seq_cpy(fused->eq[l], map->p[i]->eq[k], 1 + total); } - for (k = 0; k < set->p[j]->n_eq; ++k) { - int l = isl_basic_set_alloc_equality(fused); - isl_seq_cpy(fused->eq[l], set->p[j]->eq[k], 1 + total); + for (k = 0; k < map->p[j]->n_eq; ++k) { + int l = isl_basic_map_alloc_equality(fused); + isl_seq_cpy(fused->eq[l], map->p[j]->eq[k], 1 + total); } - for (k = 0; k < set->p[i]->n_ineq; ++k) { + for (k = 0; k < map->p[i]->n_ineq; ++k) { if (ineq_i[k] != STATUS_VALID) continue; - l = isl_basic_set_alloc_inequality(fused); - isl_seq_cpy(fused->ineq[l], set->p[i]->ineq[k], 1 + total); + l = isl_basic_map_alloc_inequality(fused); + isl_seq_cpy(fused->ineq[l], map->p[i]->ineq[k], 1 + total); } - for (k = 0; k < set->p[j]->n_ineq; ++k) { + for (k = 0; k < map->p[j]->n_ineq; ++k) { if (ineq_j[k] != STATUS_VALID) continue; - l = isl_basic_set_alloc_inequality(fused); - isl_seq_cpy(fused->ineq[l], set->p[j]->ineq[k], 1 + total); + l = isl_basic_map_alloc_inequality(fused); + isl_seq_cpy(fused->ineq[l], map->p[j]->ineq[k], 1 + total); } - for (k = 0; k < set->p[i]->n_div; ++k) { - int l = isl_basic_set_alloc_div(fused); - isl_seq_cpy(fused->div[l], set->p[i]->div[k], 1 + 1 + total); + for (k = 0; k < map->p[i]->n_div; ++k) { + int l = isl_basic_map_alloc_div(fused); + isl_seq_cpy(fused->div[l], map->p[i]->div[k], 1 + 1 + total); } - fused = isl_basic_set_gauss(fused, NULL); - ISL_F_SET(fused, ISL_BASIC_SET_FINAL); + fused = isl_basic_map_gauss(fused, NULL); + ISL_F_SET(fused, ISL_BASIC_MAP_FINAL); - fused_tab = isl_tab_from_basic_set(fused); - fused_tab = isl_tab_detect_redundant(set->ctx, fused_tab); + fused_tab = isl_tab_from_basic_map(fused); + fused_tab = isl_tab_detect_redundant(map->ctx, fused_tab); if (!fused_tab) goto error; - isl_basic_set_free(set->p[i]); - set->p[i] = fused; - isl_tab_free(set->ctx, tabs[i]); + isl_basic_map_free(map->p[i]); + map->p[i] = fused; + isl_tab_free(map->ctx, tabs[i]); tabs[i] = fused_tab; - drop(set, j, tabs); + drop(map, j, tabs); return 1; error: - isl_basic_set_free(fused); + isl_basic_map_free(fused); return -1; } -/* Given a pair of basic sets i and j such that all constraints are either +/* Given a pair of basic maps i and j such that all constraints are either * "valid" or "cut", check if the facets corresponding to the "cut" - * constraints of i lie entirely within basic set j. - * If so, replace the pair by the basic set consisting of the valid - * constraints in both basic sets. + * constraints of i lie entirely within basic map j. + * If so, replace the pair by the basic map consisting of the valid + * constraints in both basic maps. * * To see that we are not introducing any extra points, call the - * two basic sets A and B and the resulting set U and let x + * two basic maps A and B and the resulting map U and let x * be an element of U \setminus ( A \cup B ). * Then there is a pair of cut constraints c_1 and c_2 in A and B such that x * violates them. Let X be the intersection of U with the opposites @@ -216,43 +216,43 @@ error: * c_2 must be opposites of each other, but then x could not violate * both of them. */ -static int check_facets(struct isl_set *set, int i, int j, +static int check_facets(struct isl_map *map, int i, int j, struct isl_tab **tabs, int *ineq_i, int *ineq_j) { int k, l; struct isl_tab_undo *snap; - unsigned n_eq = set->p[i]->n_eq; + unsigned n_eq = map->p[i]->n_eq; - snap = isl_tab_snap(set->ctx, tabs[i]); + snap = isl_tab_snap(map->ctx, tabs[i]); - for (k = 0; k < set->p[i]->n_ineq; ++k) { + for (k = 0; k < map->p[i]->n_ineq; ++k) { if (ineq_i[k] != STATUS_CUT) continue; - tabs[i] = isl_tab_select_facet(set->ctx, tabs[i], n_eq + k); - for (l = 0; l < set->p[j]->n_ineq; ++l) { + tabs[i] = isl_tab_select_facet(map->ctx, tabs[i], n_eq + k); + for (l = 0; l < map->p[j]->n_ineq; ++l) { int stat; if (ineq_j[l] != STATUS_CUT) continue; - stat = status_in(set->ctx, set->p[j]->ineq[l], tabs[i]); + stat = status_in(map->ctx, map->p[j]->ineq[l], tabs[i]); if (stat != STATUS_VALID) break; } - isl_tab_rollback(set->ctx, tabs[i], snap); - if (l < set->p[j]->n_ineq) + isl_tab_rollback(map->ctx, tabs[i], snap); + if (l < map->p[j]->n_ineq) break; } - if (k < set->p[i]->n_ineq) + if (k < map->p[i]->n_ineq) /* BAD CUT PAIR */ return 0; - return fuse(set, i, j, tabs, ineq_i, ineq_j); + return fuse(map, i, j, tabs, ineq_i, ineq_j); } -/* Both basic sets have at least one inequality with and adjacent - * (but opposite) inequality in the other basic set. +/* Both basic maps have at least one inequality with and adjacent + * (but opposite) inequality in the other basic map. * Check that there are no cut constraints and that there is only * a single pair of adjacent inequalities. - * If so, we can replace the pair by a single basic set described + * If so, we can replace the pair by a single basic map described * by all but the pair of adjacent inequalities. * Any additional points introduced lie strictly between the two * adjacent hyperplanes and can therefore be integral. @@ -265,7 +265,7 @@ static int check_facets(struct isl_set *set, int i, int j, * \___||_/ \_____/ * * The test for a single pair of adjancent inequalities is important - * for avoiding the combination of two basic sets like the following + * for avoiding the combination of two basic maps like the following * * /| * / | @@ -275,70 +275,70 @@ static int check_facets(struct isl_set *set, int i, int j, * | | * |___| */ -static int check_adj_ineq(struct isl_set *set, int i, int j, +static int check_adj_ineq(struct isl_map *map, int i, int j, struct isl_tab **tabs, int *ineq_i, int *ineq_j) { int changed = 0; - if (any(ineq_i, set->p[i]->n_ineq, STATUS_CUT) || - any(ineq_j, set->p[j]->n_ineq, STATUS_CUT)) + if (any(ineq_i, map->p[i]->n_ineq, STATUS_CUT) || + any(ineq_j, map->p[j]->n_ineq, STATUS_CUT)) /* ADJ INEQ CUT */ ; - else if (count(ineq_i, set->p[i]->n_ineq, STATUS_ADJ_INEQ) == 1 && - count(ineq_j, set->p[j]->n_ineq, STATUS_ADJ_INEQ) == 1) - changed = fuse(set, i, j, tabs, ineq_i, ineq_j); + else if (count(ineq_i, map->p[i]->n_ineq, STATUS_ADJ_INEQ) == 1 && + count(ineq_j, map->p[j]->n_ineq, STATUS_ADJ_INEQ) == 1) + changed = fuse(map, i, j, tabs, ineq_i, ineq_j); /* else ADJ INEQ TOO MANY */ return changed; } -/* Check if basic set "i" contains the basic set represented +/* Check if basic map "i" contains the basic map represented * by the tableau "tab". */ -static int contains(struct isl_set *set, int i, int *ineq_i, +static int contains(struct isl_map *map, int i, int *ineq_i, struct isl_tab *tab) { int k, l; unsigned dim; - dim = isl_basic_set_total_dim(set->p[i]); - for (k = 0; k < set->p[i]->n_eq; ++k) { + dim = isl_basic_map_total_dim(map->p[i]); + for (k = 0; k < map->p[i]->n_eq; ++k) { for (l = 0; l < 2; ++l) { int stat; - isl_seq_neg(set->p[i]->eq[k], set->p[i]->eq[k], 1+dim); - stat = status_in(set->ctx, set->p[i]->eq[k], tab); + isl_seq_neg(map->p[i]->eq[k], map->p[i]->eq[k], 1+dim); + stat = status_in(map->ctx, map->p[i]->eq[k], tab); if (stat != STATUS_VALID) return 0; } } - for (k = 0; k < set->p[i]->n_ineq; ++k) { + for (k = 0; k < map->p[i]->n_ineq; ++k) { int stat; if (ineq_i[l] == STATUS_REDUNDANT) continue; - stat = status_in(set->ctx, set->p[i]->ineq[k], tab); + stat = status_in(map->ctx, map->p[i]->ineq[k], tab); if (stat != STATUS_VALID) return 0; } return 1; } -/* At least one of the basic sets has an equality that is adjacent - * to inequality. Make sure that only one of the basic sets has - * such an equality and that the other basic set has exactly one +/* At least one of the basic maps has an equality that is adjacent + * to inequality. Make sure that only one of the basic maps has + * such an equality and that the other basic map has exactly one * inequality adjacent to an equality. - * We call the basic set that has the inequality "i" and the basic - * set that has the equality "j". + * We call the basic map that has the inequality "i" and the basic + * map that has the equality "j". * If "i" has any "cut" inequality, then relaxing the inequality - * by one would not result in a basic set that contains the other - * basic set. + * by one would not result in a basic map that contains the other + * basic map. * Otherwise, we relax the constraint, compute the corresponding - * facet and check whether it is included in the other basic set. + * facet and check whether it is included in the other basic map. * If so, we know that relaxing the constraint extend the basic - * set with exactly the other basic set (we already know that this - * other basic set is included in the extension, because there + * map with exactly the other basic map (we already know that this + * other basic map is included in the extension, because there * were no "cut" inequalities in "i") and we can replace the - * two basic sets by thie extension. + * two basic maps by thie extension. * ____ _____ * / || / | * / || / | @@ -346,113 +346,113 @@ static int contains(struct isl_set *set, int i, int *ineq_i, * \ || \ | * \___|| \____| */ -static int check_adj_eq(struct isl_set *set, int i, int j, +static int check_adj_eq(struct isl_map *map, int i, int j, struct isl_tab **tabs, int *eq_i, int *ineq_i, int *eq_j, int *ineq_j) { int changed = 0; int super; int k; struct isl_tab_undo *snap, *snap2; - unsigned n_eq = set->p[i]->n_eq; + unsigned n_eq = map->p[i]->n_eq; - if (any(eq_i, 2 * set->p[i]->n_eq, STATUS_ADJ_INEQ) && - any(eq_j, 2 * set->p[j]->n_eq, STATUS_ADJ_INEQ)) + if (any(eq_i, 2 * map->p[i]->n_eq, STATUS_ADJ_INEQ) && + any(eq_j, 2 * map->p[j]->n_eq, STATUS_ADJ_INEQ)) /* ADJ EQ TOO MANY */ return 0; - if (any(eq_i, 2 * set->p[i]->n_eq, STATUS_ADJ_INEQ)) - return check_adj_eq(set, j, i, tabs, + if (any(eq_i, 2 * map->p[i]->n_eq, STATUS_ADJ_INEQ)) + return check_adj_eq(map, j, i, tabs, eq_j, ineq_j, eq_i, ineq_i); /* j has an equality adjacent to an inequality in i */ - if (any(ineq_i, set->p[i]->n_ineq, STATUS_CUT)) + if (any(ineq_i, map->p[i]->n_ineq, STATUS_CUT)) /* ADJ EQ CUT */ return 0; - if (count(eq_j, 2 * set->p[j]->n_eq, STATUS_ADJ_INEQ) != 1 || - count(ineq_i, set->p[i]->n_ineq, STATUS_ADJ_EQ) != 1 || - any(ineq_j, set->p[j]->n_ineq, STATUS_ADJ_EQ) || - any(ineq_i, set->p[i]->n_ineq, STATUS_ADJ_INEQ) || - any(ineq_j, set->p[j]->n_ineq, STATUS_ADJ_INEQ)) + if (count(eq_j, 2 * map->p[j]->n_eq, STATUS_ADJ_INEQ) != 1 || + count(ineq_i, map->p[i]->n_ineq, STATUS_ADJ_EQ) != 1 || + any(ineq_j, map->p[j]->n_ineq, STATUS_ADJ_EQ) || + any(ineq_i, map->p[i]->n_ineq, STATUS_ADJ_INEQ) || + any(ineq_j, map->p[j]->n_ineq, STATUS_ADJ_INEQ)) /* ADJ EQ TOO MANY */ return 0; - for (k = 0; k < set->p[i]->n_ineq ; ++k) + for (k = 0; k < map->p[i]->n_ineq ; ++k) if (ineq_i[k] == STATUS_ADJ_EQ) break; - snap = isl_tab_snap(set->ctx, tabs[i]); - tabs[i] = isl_tab_relax(set->ctx, tabs[i], n_eq + k); - snap2 = isl_tab_snap(set->ctx, tabs[i]); - tabs[i] = isl_tab_select_facet(set->ctx, tabs[i], n_eq + k); - super = contains(set, j, ineq_j, tabs[i]); + snap = isl_tab_snap(map->ctx, tabs[i]); + tabs[i] = isl_tab_relax(map->ctx, tabs[i], n_eq + k); + snap2 = isl_tab_snap(map->ctx, tabs[i]); + tabs[i] = isl_tab_select_facet(map->ctx, tabs[i], n_eq + k); + super = contains(map, j, ineq_j, tabs[i]); if (super) { - isl_tab_rollback(set->ctx, tabs[i], snap2); - set->p[i] = isl_basic_set_cow(set->p[i]); - if (!set->p[i]) + isl_tab_rollback(map->ctx, tabs[i], snap2); + map->p[i] = isl_basic_map_cow(map->p[i]); + if (!map->p[i]) return -1; - isl_int_add_ui(set->p[i]->ineq[k][0], set->p[i]->ineq[k][0], 1); - ISL_F_SET(set->p[i], ISL_BASIC_SET_FINAL); - drop(set, j, tabs); + isl_int_add_ui(map->p[i]->ineq[k][0], map->p[i]->ineq[k][0], 1); + ISL_F_SET(map->p[i], ISL_BASIC_MAP_FINAL); + drop(map, j, tabs); changed = 1; } else - isl_tab_rollback(set->ctx, tabs[i], snap); + isl_tab_rollback(map->ctx, tabs[i], snap); return changed; } -/* Check if the union of the given pair of basic sets - * can be represented by a single basic set. - * If so, replace the pair by the single basic set and return 1. +/* Check if the union of the given pair of basic maps + * can be represented by a single basic map. + * If so, replace the pair by the single basic map and return 1. * Otherwise, return 0; * - * We first check the effect of each constraint of one basic set - * on the other basic set. + * We first check the effect of each constraint of one basic map + * on the other basic map. * The constraint may be * redundant the constraint is redundant in its own - * basic set and should be ignore and removed + * basic map and should be ignore and removed * in the end - * valid all (integer) points of the other basic set + * valid all (integer) points of the other basic map * satisfy the constraint - * separate no (integer) point of the other basic set + * separate no (integer) point of the other basic map * satisfies the constraint - * cut some but not all points of the other basic set + * cut some but not all points of the other basic map * satisfy the constraint * adj_eq the given constraint is adjacent (on the outside) - * to an equality of the other basic set + * to an equality of the other basic map * adj_ineq the given constraint is adjacent (on the outside) - * to an inequality of the other basic set + * to an inequality of the other basic map * * We consider four cases in which we can replace the pair by a single - * basic set. We ignore all "redundant" constraints. + * basic map. We ignore all "redundant" constraints. * - * 1. all constraints of one basic set are valid - * => the other basic set is a subset and can be removed + * 1. all constraints of one basic map are valid + * => the other basic map is a subset and can be removed * - * 2. all constraints of both basic sets are either "valid" or "cut" + * 2. all constraints of both basic maps are either "valid" or "cut" * and the facets corresponding to the "cut" constraints - * of one of the basic sets lies entirely inside the other basic set - * => the pair can be replaced by a basic set consisting - * of the valid constraints in both basic sets + * of one of the basic maps lies entirely inside the other basic map + * => the pair can be replaced by a basic map consisting + * of the valid constraints in both basic maps * * 3. there is a single pair of adjacent inequalities * (all other constraints are "valid") - * => the pair can be replaced by a basic set consisting - * of the valid constraints in both basic sets + * => the pair can be replaced by a basic map consisting + * of the valid constraints in both basic maps * * 4. there is a single adjacent pair of an inequality and an equality, - * the other constraints of the basic set containing the inequality are - * "valid". Moreover, if the inequality the basic set is relaxed + * the other constraints of the basic map containing the inequality are + * "valid". Moreover, if the inequality the basic map is relaxed * and then turned into an equality, then resulting facet lies - * entirely inside the other basic set - * => the pair can be replaced by the basic set containing + * entirely inside the other basic map + * => the pair can be replaced by the basic map containing * the inequality, with the inequality relaxed. * * Throughout the computation, we maintain a collection of tableaus - * corresponding to the basic sets. When the basic sets are dropped + * corresponding to the basic maps. When the basic maps are dropped * or combined, the tableaus are modified accordingly. */ -static int coalesce_pair(struct isl_set *set, int i, int j, +static int coalesce_pair(struct isl_map *map, int i, int j, struct isl_tab **tabs) { int changed = 0; @@ -461,57 +461,57 @@ static int coalesce_pair(struct isl_set *set, int i, int j, int *ineq_i = NULL; int *ineq_j = NULL; - eq_i = eq_status_in(set, i, j, tabs); - if (any(eq_i, 2 * set->p[i]->n_eq, STATUS_ERROR)) + eq_i = eq_status_in(map, i, j, tabs); + if (any(eq_i, 2 * map->p[i]->n_eq, STATUS_ERROR)) goto error; - if (any(eq_i, 2 * set->p[i]->n_eq, STATUS_SEPARATE)) + if (any(eq_i, 2 * map->p[i]->n_eq, STATUS_SEPARATE)) goto done; - eq_j = eq_status_in(set, j, i, tabs); - if (any(eq_j, 2 * set->p[j]->n_eq, STATUS_ERROR)) + eq_j = eq_status_in(map, j, i, tabs); + if (any(eq_j, 2 * map->p[j]->n_eq, STATUS_ERROR)) goto error; - if (any(eq_j, 2 * set->p[j]->n_eq, STATUS_SEPARATE)) + if (any(eq_j, 2 * map->p[j]->n_eq, STATUS_SEPARATE)) goto done; - ineq_i = ineq_status_in(set, i, j, tabs); - if (any(ineq_i, set->p[i]->n_ineq, STATUS_ERROR)) + ineq_i = ineq_status_in(map, i, j, tabs); + if (any(ineq_i, map->p[i]->n_ineq, STATUS_ERROR)) goto error; - if (any(ineq_i, set->p[i]->n_ineq, STATUS_SEPARATE)) + if (any(ineq_i, map->p[i]->n_ineq, STATUS_SEPARATE)) goto done; - ineq_j = ineq_status_in(set, j, i, tabs); - if (any(ineq_j, set->p[j]->n_ineq, STATUS_ERROR)) + ineq_j = ineq_status_in(map, j, i, tabs); + if (any(ineq_j, map->p[j]->n_ineq, STATUS_ERROR)) goto error; - if (any(ineq_j, set->p[j]->n_ineq, STATUS_SEPARATE)) + if (any(ineq_j, map->p[j]->n_ineq, STATUS_SEPARATE)) goto done; - if (all(eq_i, 2 * set->p[i]->n_eq, STATUS_VALID) && - all(ineq_i, set->p[i]->n_ineq, STATUS_VALID)) { - drop(set, j, tabs); + if (all(eq_i, 2 * map->p[i]->n_eq, STATUS_VALID) && + all(ineq_i, map->p[i]->n_ineq, STATUS_VALID)) { + drop(map, j, tabs); changed = 1; - } else if (all(eq_j, 2 * set->p[j]->n_eq, STATUS_VALID) && - all(ineq_j, set->p[j]->n_ineq, STATUS_VALID)) { - drop(set, i, tabs); + } else if (all(eq_j, 2 * map->p[j]->n_eq, STATUS_VALID) && + all(ineq_j, map->p[j]->n_ineq, STATUS_VALID)) { + drop(map, i, tabs); changed = 1; - } else if (any(eq_i, 2 * set->p[i]->n_eq, STATUS_CUT) || - any(eq_j, 2 * set->p[j]->n_eq, STATUS_CUT)) { + } else if (any(eq_i, 2 * map->p[i]->n_eq, STATUS_CUT) || + any(eq_j, 2 * map->p[j]->n_eq, STATUS_CUT)) { /* BAD CUT */ - } else if (any(eq_i, 2 * set->p[i]->n_eq, STATUS_ADJ_EQ) || - any(eq_j, 2 * set->p[j]->n_eq, STATUS_ADJ_EQ)) { + } else if (any(eq_i, 2 * map->p[i]->n_eq, STATUS_ADJ_EQ) || + any(eq_j, 2 * map->p[j]->n_eq, STATUS_ADJ_EQ)) { /* ADJ EQ PAIR */ - } else if (any(eq_i, 2 * set->p[i]->n_eq, STATUS_ADJ_INEQ) || - any(eq_j, 2 * set->p[j]->n_eq, STATUS_ADJ_INEQ)) { - changed = check_adj_eq(set, i, j, tabs, + } else if (any(eq_i, 2 * map->p[i]->n_eq, STATUS_ADJ_INEQ) || + any(eq_j, 2 * map->p[j]->n_eq, STATUS_ADJ_INEQ)) { + changed = check_adj_eq(map, i, j, tabs, eq_i, ineq_i, eq_j, ineq_j); - } else if (any(ineq_i, set->p[i]->n_ineq, STATUS_ADJ_EQ) || - any(ineq_j, set->p[j]->n_ineq, STATUS_ADJ_EQ)) { + } else if (any(ineq_i, map->p[i]->n_ineq, STATUS_ADJ_EQ) || + any(ineq_j, map->p[j]->n_ineq, STATUS_ADJ_EQ)) { /* Can't happen */ /* BAD ADJ INEQ */ - } else if (any(ineq_i, set->p[i]->n_ineq, STATUS_ADJ_INEQ) || - any(ineq_j, set->p[j]->n_ineq, STATUS_ADJ_INEQ)) { - changed = check_adj_ineq(set, i, j, tabs, ineq_i, ineq_j); + } else if (any(ineq_i, map->p[i]->n_ineq, STATUS_ADJ_INEQ) || + any(ineq_j, map->p[j]->n_ineq, STATUS_ADJ_INEQ)) { + changed = check_adj_ineq(map, i, j, tabs, ineq_i, ineq_j); } else - changed = check_facets(set, i, j, tabs, ineq_i, ineq_j); + changed = check_facets(map, i, j, tabs, ineq_i, ineq_j); done: free(eq_i); @@ -527,73 +527,73 @@ error: return -1; } -static struct isl_set *coalesce(struct isl_set *set, struct isl_tab **tabs) +static struct isl_map *coalesce(struct isl_map *map, struct isl_tab **tabs) { int i, j; - for (i = 0; i < set->n - 1; ++i) - for (j = i + 1; j < set->n; ++j) { + for (i = 0; i < map->n - 1; ++i) + for (j = i + 1; j < map->n; ++j) { int changed; - changed = coalesce_pair(set, i, j, tabs); + changed = coalesce_pair(map, i, j, tabs); if (changed < 0) goto error; if (changed) - return coalesce(set, tabs); + return coalesce(map, tabs); } - return set; + return map; error: - isl_set_free(set); + isl_map_free(map); return NULL; } -/* For each pair of basic sets in the set, check if the union of the two - * can be represented by a single basic set. - * If so, replace the pair by the single basic set and start over. +/* For each pair of basic maps in the map, check if the union of the two + * can be represented by a single basic map. + * If so, replace the pair by the single basic map and start over. */ -struct isl_set *isl_set_coalesce(struct isl_set *set) +struct isl_map *isl_map_coalesce(struct isl_map *map) { int i; unsigned n; struct isl_ctx *ctx; struct isl_tab **tabs = NULL; - if (!set) + if (!map) return NULL; - if (set->n <= 1) - return set; + if (map->n <= 1) + return map; - set = isl_set_align_divs(set); + map = isl_map_align_divs(map); - tabs = isl_calloc_array(set->ctx, struct isl_tab *, set->n); + tabs = isl_calloc_array(map->ctx, struct isl_tab *, map->n); if (!tabs) goto error; - n = set->n; - ctx = set->ctx; - for (i = 0; i < set->n; ++i) { - tabs[i] = isl_tab_from_basic_set(set->p[i]); + n = map->n; + ctx = map->ctx; + for (i = 0; i < map->n; ++i) { + tabs[i] = isl_tab_from_basic_map(map->p[i]); if (!tabs[i]) goto error; - if (!ISL_F_ISSET(set->p[i], ISL_BASIC_SET_NO_IMPLICIT)) - tabs[i] = isl_tab_detect_equalities(set->ctx, tabs[i]); - if (!ISL_F_ISSET(set->p[i], ISL_BASIC_SET_NO_REDUNDANT)) - tabs[i] = isl_tab_detect_redundant(set->ctx, tabs[i]); + if (!ISL_F_ISSET(map->p[i], ISL_BASIC_MAP_NO_IMPLICIT)) + tabs[i] = isl_tab_detect_equalities(map->ctx, tabs[i]); + if (!ISL_F_ISSET(map->p[i], ISL_BASIC_MAP_NO_REDUNDANT)) + tabs[i] = isl_tab_detect_redundant(map->ctx, tabs[i]); } - for (i = set->n - 1; i >= 0; --i) + for (i = map->n - 1; i >= 0; --i) if (tabs[i]->empty) - drop(set, i, tabs); + drop(map, i, tabs); - set = coalesce(set, tabs); + map = coalesce(map, tabs); - if (set) - for (i = 0; i < set->n; ++i) { - set->p[i] = isl_basic_set_update_from_tab(set->p[i], + if (map) + for (i = 0; i < map->n; ++i) { + map->p[i] = isl_basic_map_update_from_tab(map->p[i], tabs[i]); - if (!set->p[i]) + if (!map->p[i]) goto error; - ISL_F_SET(set->p[i], ISL_BASIC_SET_NO_IMPLICIT); - ISL_F_SET(set->p[i], ISL_BASIC_SET_NO_REDUNDANT); + ISL_F_SET(map->p[i], ISL_BASIC_MAP_NO_IMPLICIT); + ISL_F_SET(map->p[i], ISL_BASIC_MAP_NO_REDUNDANT); } for (i = 0; i < n; ++i) @@ -601,7 +601,7 @@ struct isl_set *isl_set_coalesce(struct isl_set *set) free(tabs); - return set; + return map; error: if (tabs) for (i = 0; i < n; ++i) @@ -609,3 +609,12 @@ error: free(tabs); return NULL; } + +/* For each pair of basic sets in the set, check if the union of the two + * can be represented by a single basic set. + * If so, replace the pair by the single basic set and start over. + */ +struct isl_set *isl_set_coalesce(struct isl_set *set) +{ + (struct isl_set *)isl_map_coalesce((struct isl_map *)set); +} -- 2.7.4