Lines Matching full:info
209 * of the basic map represented by "info" that
212 static int any_eq(struct isl_coalesce_info *info, int status) in any_eq() argument
216 n_eq = isl_basic_map_n_equality(info->bmap); in any_eq()
217 return any(info->eq, 2 * n_eq, status); in any_eq()
221 * of the basic map represented by "info" that
224 static int any_ineq(struct isl_coalesce_info *info, int status) in any_ineq() argument
228 n_ineq = isl_basic_map_n_inequality(info->bmap); in any_ineq()
229 return any(info->ineq, n_ineq, status); in any_ineq()
233 * in the description of the basic map represented by "info" that
239 static int find_eq(struct isl_coalesce_info *info, int status) in find_eq() argument
243 n_eq = isl_basic_map_n_equality(info->bmap); in find_eq()
244 return find(info->eq, 2 * n_eq, status); in find_eq()
248 * of the basic map represented by "info" that
252 static int find_ineq(struct isl_coalesce_info *info, int status) in find_ineq() argument
256 n_ineq = isl_basic_map_n_inequality(info->bmap); in find_ineq()
257 return find(info->ineq, n_ineq, status); in find_ineq()
261 * of the basic map represented by "info" that
264 static int count_eq(struct isl_coalesce_info *info, int status) in count_eq() argument
268 n_eq = isl_basic_map_n_equality(info->bmap); in count_eq()
269 return count(info->eq, 2 * n_eq, status); in count_eq()
273 * of the basic map represented by "info" that
276 static int count_ineq(struct isl_coalesce_info *info, int status) in count_ineq() argument
280 n_ineq = isl_basic_map_n_inequality(info->bmap); in count_ineq()
281 return count(info->ineq, n_ineq, status); in count_ineq()
284 /* Are all non-redundant constraints of the basic map represented by "info"
287 static int all_valid_or_cut(struct isl_coalesce_info *info) in all_valid_or_cut() argument
291 for (i = 0; i < 2 * info->bmap->n_eq; ++i) { in all_valid_or_cut()
292 if (info->eq[i] == STATUS_REDUNDANT) in all_valid_or_cut()
294 if (info->eq[i] == STATUS_VALID) in all_valid_or_cut()
296 if (info->eq[i] == STATUS_CUT) in all_valid_or_cut()
301 for (i = 0; i < info->bmap->n_ineq; ++i) { in all_valid_or_cut()
302 if (info->ineq[i] == STATUS_REDUNDANT) in all_valid_or_cut()
304 if (info->ineq[i] == STATUS_VALID) in all_valid_or_cut()
306 if (info->ineq[i] == STATUS_CUT) in all_valid_or_cut()
314 /* Compute the hash of the (apparent) affine hull of info->bmap (with
316 * in info->hash.
318 static int coalesce_info_set_hull_hash(struct isl_coalesce_info *info) in coalesce_info_set_hull_hash() argument
323 hull = isl_basic_map_copy(info->bmap); in coalesce_info_set_hull_hash()
330 info->hull_hash = isl_basic_map_get_hash(hull); in coalesce_info_set_hull_hash()
339 static void clear_coalesce_info(int n, struct isl_coalesce_info *info) in clear_coalesce_info() argument
343 if (!info) in clear_coalesce_info()
347 isl_basic_map_free(info[i].bmap); in clear_coalesce_info()
348 isl_tab_free(info[i].tab); in clear_coalesce_info()
351 free(info); in clear_coalesce_info()
354 /* Clear the memory associated to "info".
356 static void clear(struct isl_coalesce_info *info) in clear() argument
358 info->bmap = isl_basic_map_free(info->bmap); in clear()
359 isl_tab_free(info->tab); in clear()
360 info->tab = NULL; in clear()
363 /* Drop the basic map represented by "info".
367 static void drop(struct isl_coalesce_info *info) in drop() argument
369 clear(info); in drop()
370 info->removed = 1; in drop()
378 struct isl_coalesce_info info; in exchange() local
380 info = *info1; in exchange()
382 *info2 = info; in exchange()
423 /* Add the valid constraints of the basic map represented by "info"
429 __isl_take isl_basic_map *bmap, struct isl_coalesce_info *info, in add_valid_constraints() argument
437 for (k = 0; k < info->bmap->n_eq; ++k) { in add_valid_constraints()
438 if (info->eq[2 * k] == STATUS_VALID && in add_valid_constraints()
439 info->eq[2 * k + 1] == STATUS_VALID) { in add_valid_constraints()
443 isl_seq_cpy(bmap->eq[l], info->bmap->eq[k], len); in add_valid_constraints()
444 } else if (info->eq[2 * k] == STATUS_VALID) { in add_valid_constraints()
448 isl_seq_neg(bmap->ineq[l], info->bmap->eq[k], len); in add_valid_constraints()
449 } else if (info->eq[2 * k + 1] == STATUS_VALID) { in add_valid_constraints()
453 isl_seq_cpy(bmap->ineq[l], info->bmap->eq[k], len); in add_valid_constraints()
457 for (k = 0; k < info->bmap->n_ineq; ++k) { in add_valid_constraints()
458 if (info->ineq[k] != STATUS_VALID) in add_valid_constraints()
463 isl_seq_cpy(bmap->ineq[l], info->bmap->ineq[k], len); in add_valid_constraints()
474 struct isl_coalesce_info *info, in number_of_constraints_increases() argument
479 n_old = 2 * info[i].bmap->n_eq + info[i].bmap->n_ineq; in number_of_constraints_increases()
480 n_old += 2 * info[j].bmap->n_eq + info[j].bmap->n_ineq; in number_of_constraints_increases()
511 static enum isl_change fuse(int i, int j, struct isl_coalesce_info *info, in fuse() argument
517 isl_size total = isl_basic_map_dim(info[i].bmap, isl_dim_all); in fuse()
525 return fuse(j, i, info, extra, detect_equalities, check_number); in fuse()
527 n_eq = info[i].bmap->n_eq + info[j].bmap->n_eq; in fuse()
528 n_ineq = info[i].bmap->n_ineq + info[j].bmap->n_ineq; in fuse()
529 fused = isl_basic_map_alloc_space(isl_space_copy(info[i].bmap->dim), in fuse()
530 info[i].bmap->n_div, n_eq, n_eq + n_ineq + extra_rows); in fuse()
531 fused = add_valid_constraints(fused, &info[i], 1 + total); in fuse()
532 fused = add_valid_constraints(fused, &info[j], 1 + total); in fuse()
535 if (ISL_F_ISSET(info[i].bmap, ISL_BASIC_MAP_RATIONAL) && in fuse()
536 ISL_F_ISSET(info[j].bmap, ISL_BASIC_MAP_RATIONAL)) in fuse()
539 for (k = 0; k < info[i].bmap->n_div; ++k) { in fuse()
543 if (isl_seq_eq(info[i].bmap->div[k], info[j].bmap->div[k], in fuse()
545 isl_seq_cpy(fused->div[l], info[i].bmap->div[k], in fuse()
563 if (simplify || info[j].simplify) { in fuse()
565 info[i].simplify = 0; in fuse()
576 number_of_constraints_increases(i, j, info, fused, fused_tab)) { in fuse()
582 clear(&info[i]); in fuse()
583 info[i].bmap = fused; in fuse()
584 info[i].tab = fused_tab; in fuse()
585 info[i].modified = 1; in fuse()
586 drop(&info[j]); in fuse()
625 struct isl_coalesce_info *info) in check_facets() argument
629 unsigned n_eq = info[i].bmap->n_eq; in check_facets()
631 snap = isl_tab_snap(info[i].tab); in check_facets()
632 if (isl_tab_mark_rational(info[i].tab) < 0) in check_facets()
634 snap2 = isl_tab_snap(info[i].tab); in check_facets()
636 for (k = 0; k < info[i].bmap->n_ineq; ++k) { in check_facets()
637 if (info[i].ineq[k] != STATUS_CUT) in check_facets()
639 if (isl_tab_select_facet(info[i].tab, n_eq + k) < 0) in check_facets()
641 for (l = 0; l < info[j].bmap->n_ineq; ++l) { in check_facets()
643 if (info[j].ineq[l] != STATUS_CUT) in check_facets()
645 stat = status_in(info[j].bmap->ineq[l], info[i].tab); in check_facets()
651 if (isl_tab_rollback(info[i].tab, snap2) < 0) in check_facets()
653 if (l < info[j].bmap->n_ineq) in check_facets()
657 if (k < info[i].bmap->n_ineq) { in check_facets()
658 if (isl_tab_rollback(info[i].tab, snap) < 0) in check_facets()
662 return fuse(i, j, info, NULL, 0, 0); in check_facets()
665 /* Check if info->bmap contains the basic map represented
671 static isl_bool contains(struct isl_coalesce_info *info, struct isl_tab *tab) in contains() argument
675 isl_basic_map *bmap = info->bmap; in contains()
698 if (info->ineq[k] == STATUS_REDUNDANT) in contains()
761 struct isl_coalesce_info *info, __isl_keep isl_mat *extra) in is_adj_ineq_extension_with_wraps() argument
765 isl_size total = isl_basic_map_dim(info[i].bmap, isl_dim_all); in is_adj_ineq_extension_with_wraps()
772 n_eq_i = isl_basic_map_n_equality(info[i].bmap); in is_adj_ineq_extension_with_wraps()
773 n_ineq_j = isl_basic_map_n_inequality(info[j].bmap); in is_adj_ineq_extension_with_wraps()
778 if (isl_tab_extend_cons(info[i].tab, 1 + n_ineq_j + n_extra) < 0) in is_adj_ineq_extension_with_wraps()
781 snap = isl_tab_snap(info[i].tab); in is_adj_ineq_extension_with_wraps()
783 if (isl_tab_unrestrict(info[i].tab, n_eq_i + k) < 0) in is_adj_ineq_extension_with_wraps()
786 isl_seq_neg(info[i].bmap->ineq[k], info[i].bmap->ineq[k], 1 + total); in is_adj_ineq_extension_with_wraps()
787 isl_int_sub_ui(info[i].bmap->ineq[k][0], info[i].bmap->ineq[k][0], 1); in is_adj_ineq_extension_with_wraps()
788 r = isl_tab_add_ineq(info[i].tab, info[i].bmap->ineq[k]); in is_adj_ineq_extension_with_wraps()
789 isl_seq_neg(info[i].bmap->ineq[k], info[i].bmap->ineq[k], 1 + total); in is_adj_ineq_extension_with_wraps()
790 isl_int_sub_ui(info[i].bmap->ineq[k][0], info[i].bmap->ineq[k][0], 1); in is_adj_ineq_extension_with_wraps()
795 if (info[j].ineq[k] != STATUS_VALID) in is_adj_ineq_extension_with_wraps()
797 if (isl_tab_add_ineq(info[i].tab, info[j].bmap->ineq[k]) < 0) in is_adj_ineq_extension_with_wraps()
801 if (isl_tab_add_ineq(info[i].tab, extra->row[k]) < 0) in is_adj_ineq_extension_with_wraps()
804 if (isl_tab_detect_constants(info[i].tab) < 0) in is_adj_ineq_extension_with_wraps()
807 super = contains(&info[j], info[i].tab); in is_adj_ineq_extension_with_wraps()
811 return fuse(i, j, info, extra, 0, 0); in is_adj_ineq_extension_with_wraps()
813 if (isl_tab_rollback(info[i].tab, snap) < 0) in is_adj_ineq_extension_with_wraps()
874 * of info->bmap in "v", check if the constraint can be tightened,
876 * for info->tab.
878 * to info->tab. "v" may be modified by this function.
890 * in info->tab. Add this tightened constraint as an extra row
891 * to info->tab to make this information explicitly available.
893 static __isl_give isl_vec *try_tightening(struct isl_coalesce_info *info, in try_tightening() argument
917 if (isl_tab_extend_cons(info->tab, 1) < 0) in try_tightening()
920 isl_int_sub(info->bmap->ineq[ineq][0], in try_tightening()
921 info->bmap->ineq[ineq][0], v->el[0]); in try_tightening()
922 r = isl_tab_add_ineq(info->tab, info->bmap->ineq[ineq]); in try_tightening()
923 isl_int_add(info->bmap->ineq[ineq][0], in try_tightening()
924 info->bmap->ineq[ineq][0], v->el[0]); in try_tightening()
933 * by info->tab.
934 * In particular, on input, info->tab represents the result
935 * of relaxing the "n" inequality constraints of info->bmap in "relaxed"
941 * and use it to tighten the other constraints of info->bmap
943 * updating info->tab (and leaving info->bmap untouched).
954 * The tightening is performed on the tableau info->tab by introducing
969 static isl_stat tighten_on_relaxed_facet(struct isl_coalesce_info *info, in tighten_on_relaxed_facet() argument
981 ctx = isl_basic_map_get_ctx(info->bmap); in tighten_on_relaxed_facet()
982 total = isl_basic_map_dim(info->bmap, isl_dim_all); in tighten_on_relaxed_facet()
985 isl_int_add_ui(info->bmap->ineq[k][0], info->bmap->ineq[k][0], 1); in tighten_on_relaxed_facet()
986 T = isl_mat_sub_alloc6(ctx, info->bmap->ineq, k, 1, 0, 1 + total); in tighten_on_relaxed_facet()
988 isl_int_sub_ui(info->bmap->ineq[k][0], info->bmap->ineq[k][0], 1); in tighten_on_relaxed_facet()
1003 for (i = 0; i < info->bmap->n_ineq; ++i) { in tighten_on_relaxed_facet()
1007 if (info->ineq[i] == STATUS_REDUNDANT) in tighten_on_relaxed_facet()
1009 handle = is_affected(info->bmap, i, affected, total); in tighten_on_relaxed_facet()
1017 isl_seq_cpy(v->el, info->bmap->ineq[i], 1 + total); in tighten_on_relaxed_facet()
1019 v = try_tightening(info, i, v); in tighten_on_relaxed_facet()
1036 * The tableau info[i].tab has already been extended.
1037 * Extend info[i].bmap accordingly by relaxing all constraints in "relax"
1046 struct isl_coalesce_info *info) in extend() argument
1051 info[i].bmap = isl_basic_map_cow(info[i].bmap); in extend()
1052 total = isl_basic_map_dim(info[i].bmap, isl_dim_all); in extend()
1055 for (l = 0; l < info[i].bmap->n_div; ++l) in extend()
1056 if (!isl_seq_eq(info[i].bmap->div[l], in extend()
1057 info[j].bmap->div[l], 1 + 1 + total)) { in extend()
1058 isl_int_set_si(info[i].bmap->div[l][0], 0); in extend()
1059 info[i].simplify = 1; in extend()
1062 isl_int_add_ui(info[i].bmap->ineq[relax[l]][0], in extend()
1063 info[i].bmap->ineq[relax[l]][0], 1); in extend()
1064 ISL_F_CLR(info[i].bmap, ISL_BASIC_MAP_NO_REDUNDANT); in extend()
1065 ISL_F_SET(info[i].bmap, ISL_BASIC_MAP_FINAL); in extend()
1066 drop(&info[j]); in extend()
1067 info[i].modified = 1; in extend()
1069 exchange(&info[i], &info[j]); in extend()
1118 struct isl_coalesce_info *info) in is_relaxed_extension() argument
1123 unsigned n_eq = info[i].bmap->n_eq; in is_relaxed_extension()
1126 if (isl_tab_is_equality(info[i].tab, n_eq + relax[l])) in is_relaxed_extension()
1129 snap = isl_tab_snap(info[i].tab); in is_relaxed_extension()
1131 if (isl_tab_relax(info[i].tab, n_eq + relax[l]) < 0) in is_relaxed_extension()
1134 if (!isl_tab_is_redundant(info[i].tab, n_eq + relax[l])) in is_relaxed_extension()
1136 if (isl_tab_rollback(info[i].tab, snap) < 0) in is_relaxed_extension()
1140 snap2 = isl_tab_snap(info[i].tab); in is_relaxed_extension()
1142 if (isl_tab_rollback(info[i].tab, snap2) < 0) in is_relaxed_extension()
1144 if (isl_tab_select_facet(info[i].tab, n_eq + relax[l]) < 0) in is_relaxed_extension()
1146 if (tighten_on_relaxed_facet(&info[i], n, relax, l) < 0) in is_relaxed_extension()
1148 super = contains(&info[j], info[i].tab); in is_relaxed_extension()
1153 if (isl_tab_rollback(info[i].tab, snap) < 0) in is_relaxed_extension()
1158 if (isl_tab_rollback(info[i].tab, snap2) < 0) in is_relaxed_extension()
1160 return extend(i, j, n, relax, info); in is_relaxed_extension()
1179 * in the equalities and inequalities of info->bmap that can be removed
1183 struct isl_coalesce_info *info) in wraps_update_max() argument
1187 isl_size total = isl_basic_map_dim(info->bmap, isl_dim_all); in wraps_update_max()
1193 for (k = 0; k < info->bmap->n_eq; ++k) { in wraps_update_max()
1194 if (info->eq[2 * k] == STATUS_VALID && in wraps_update_max()
1195 info->eq[2 * k + 1] == STATUS_VALID) in wraps_update_max()
1197 isl_seq_abs_max(info->bmap->eq[k] + 1, total, &max_k); in wraps_update_max()
1202 for (k = 0; k < info->bmap->n_ineq; ++k) { in wraps_update_max()
1203 if (info->ineq[k] == STATUS_VALID || in wraps_update_max()
1204 info->ineq[k] == STATUS_REDUNDANT) in wraps_update_max()
1206 isl_seq_abs_max(info->bmap->ineq[k] + 1, total, &max_k); in wraps_update_max()
1223 struct isl_coalesce_info *info, int i, int j) in wraps_init() argument
1239 if (wraps_update_max(wraps, &info[i]) < 0) in wraps_init()
1241 if (wraps_update_max(wraps, &info[j]) < 0) in wraps_init()
1310 * If "add_valid" is set, then all the constraints of info->bmap
1316 * If "add_valid" is not set, then some of the constraints of info->bmap
1327 * by info->tab) and that are valid or invalid depending on "add_valid".
1342 struct isl_coalesce_info *info, isl_int *bound, __isl_keep isl_set *set, in add_selected_wraps() argument
1348 isl_basic_map *bmap = info->bmap; in add_selected_wraps()
1358 int is_valid = info->ineq[l] == STATUS_VALID; in add_selected_wraps()
1360 info->ineq[l] == STATUS_REDUNDANT) in add_selected_wraps()
1366 if (isl_tab_is_redundant(info->tab, bmap->n_eq + l)) in add_selected_wraps()
1384 if (info->eq[2 * l + m] == STATUS_VALID) in add_selected_wraps()
1402 /* For each constraint in info->bmap that is not redundant (as determined
1403 * by info->tab) and that is not a valid constraint for the other basic map,
1423 struct isl_coalesce_info *info, isl_int *bound, __isl_keep isl_set *set) in add_wraps() argument
1425 return add_selected_wraps(wraps, info, bound, set, 0); in add_wraps()
1484 /* Does "info" have any cut constraints that are redundant?
1486 static isl_bool has_redundant_cuts(struct isl_coalesce_info *info) in has_redundant_cuts() argument
1491 n_eq = isl_basic_map_n_equality(info->bmap); in has_redundant_cuts()
1492 n_ineq = isl_basic_map_n_inequality(info->bmap); in has_redundant_cuts()
1498 if (info->ineq[l] != STATUS_CUT) in has_redundant_cuts()
1500 red = isl_tab_is_redundant(info->tab, n_eq + l); in has_redundant_cuts()
1510 /* Wrap some constraints of info->bmap that bound the facet defined
1523 * of info->bmap, we check them in check_wraps.
1532 * If any of the cut constraints of info->bmap turn out
1539 struct isl_coalesce_info *info, int k, isl_int *bound, in add_selected_wraps_around_facet() argument
1545 isl_size total = isl_basic_map_dim(info->bmap, isl_dim_all); in add_selected_wraps_around_facet()
1550 snap = isl_tab_snap(info->tab); in add_selected_wraps_around_facet()
1552 if (isl_tab_select_facet(info->tab, info->bmap->n_eq + k) < 0) in add_selected_wraps_around_facet()
1554 if (isl_tab_detect_redundant(info->tab) < 0) in add_selected_wraps_around_facet()
1556 if (info->tab->empty) { in add_selected_wraps_around_facet()
1557 if (isl_tab_rollback(info->tab, snap) < 0) in add_selected_wraps_around_facet()
1563 nowrap = has_redundant_cuts(info); in add_selected_wraps_around_facet()
1569 isl_seq_neg(bound, info->bmap->ineq[k], 1 + total); in add_selected_wraps_around_facet()
1571 if (add_selected_wraps(wraps, info, bound, set, add_valid) < 0) in add_selected_wraps_around_facet()
1575 if (isl_tab_rollback(info->tab, snap) < 0) in add_selected_wraps_around_facet()
1579 if (check_wraps(wraps, n, info->tab, add_valid) < 0) in add_selected_wraps_around_facet()
1585 /* Wrap the constraints of info->bmap that bound the facet defined
1588 * If any of the wrapped constraints turn out to be invalid for info->bmap
1592 struct isl_coalesce_info *info, int k, isl_int *bound, in add_wraps_around_facet() argument
1595 return add_selected_wraps_around_facet(wraps, info, k, bound, set, 0); in add_wraps_around_facet()
1598 /* Wrap the (valid) constraints of info->bmap that bound the facet defined
1603 * for info->bmap itself.
1606 struct isl_coalesce_info *info, int k, isl_int *bound, in add_valid_wraps_around_facet() argument
1609 return add_selected_wraps_around_facet(wraps, info, k, bound, set, 1); in add_valid_wraps_around_facet()
1628 struct isl_coalesce_info *info) in is_adj_ineq_extension() argument
1641 k = find_ineq(&info[i], STATUS_ADJ_INEQ); in is_adj_ineq_extension()
1643 isl_die(isl_basic_map_get_ctx(info[i].bmap), isl_error_internal, in is_adj_ineq_extension()
1644 "info[i].ineq should have exactly one STATUS_ADJ_INEQ", in is_adj_ineq_extension()
1647 total = isl_basic_map_dim(info[i].bmap, isl_dim_all); in is_adj_ineq_extension()
1648 n_eq_i = isl_basic_map_n_equality(info[i].bmap); in is_adj_ineq_extension()
1649 n_ineq_i = isl_basic_map_n_inequality(info[i].bmap); in is_adj_ineq_extension()
1653 set_j = set_from_updated_bmap(info[j].bmap, info[j].tab); in is_adj_ineq_extension()
1654 ctx = isl_basic_map_get_ctx(info[i].bmap); in is_adj_ineq_extension()
1657 if (wraps_init(&wraps, mat, info, i, j) < 0) in is_adj_ineq_extension()
1661 r = add_valid_wraps_around_facet(&wraps, &info[i], k, bound->el, set_j); in is_adj_ineq_extension()
1665 change = is_adj_ineq_extension_with_wraps(i, j, k, info, wraps.mat); in is_adj_ineq_extension()
1711 struct isl_coalesce_info *info) in check_adj_ineq() argument
1716 count_i = count_ineq(&info[i], STATUS_ADJ_INEQ); in check_adj_ineq()
1717 count_j = count_ineq(&info[j], STATUS_ADJ_INEQ); in check_adj_ineq()
1722 cut_i = any_eq(&info[i], STATUS_CUT) || any_ineq(&info[i], STATUS_CUT); in check_adj_ineq()
1723 cut_j = any_eq(&info[j], STATUS_CUT) || any_ineq(&info[j], STATUS_CUT); in check_adj_ineq()
1726 return fuse(i, j, info, NULL, 0, 0); in check_adj_ineq()
1729 return is_adj_ineq_extension(i, j, info); in check_adj_ineq()
1732 return is_adj_ineq_extension(j, i, info); in check_adj_ineq()
1759 struct isl_coalesce_info *info, int wrap_facet) in can_wrap_in_facet() argument
1768 isl_size total = isl_basic_map_dim(info[i].bmap, isl_dim_all); in can_wrap_in_facet()
1772 set_i = set_from_updated_bmap(info[i].bmap, info[i].tab); in can_wrap_in_facet()
1773 set_j = set_from_updated_bmap(info[j].bmap, info[j].tab); in can_wrap_in_facet()
1774 ctx = isl_basic_map_get_ctx(info[i].bmap); in can_wrap_in_facet()
1775 mat = isl_mat_alloc(ctx, 2 * (info[i].bmap->n_eq + info[j].bmap->n_eq) + in can_wrap_in_facet()
1776 info[i].bmap->n_ineq + info[j].bmap->n_ineq, in can_wrap_in_facet()
1778 if (wraps_init(&wraps, mat, info, i, j) < 0) in can_wrap_in_facet()
1784 isl_seq_cpy(bound->el, info[i].bmap->ineq[k], 1 + total); in can_wrap_in_facet()
1791 if (add_wraps(&wraps, &info[j], bound->el, set_i) < 0) in can_wrap_in_facet()
1797 if (add_wraps_around_facet(&wraps, &info[i], k, in can_wrap_in_facet()
1804 change = fuse(i, j, info, wraps.mat, 0, 0); in can_wrap_in_facet()
1883 struct isl_coalesce_info *info, struct isl_wraps *wraps, in try_wrap_in_facets() argument
1890 total = isl_basic_map_dim(info[i].bmap, isl_dim_all); in try_wrap_in_facets()
1894 snap = isl_tab_snap(info[j].tab); in try_wrap_in_facets()
1896 for (k = 0; k < info[i].bmap->n_eq; ++k) { in try_wrap_in_facets()
1898 if (info[i].eq[2 * k + l] != STATUS_CUT) in try_wrap_in_facets()
1903 info[i].bmap->eq[k], 1 + total); in try_wrap_in_facets()
1906 info[i].bmap->eq[k], 1 + total); in try_wrap_in_facets()
1907 if (wrap_in_facet(wraps, w, &info[j], set_i, snap) < 0) in try_wrap_in_facets()
1915 for (k = 0; k < info[i].bmap->n_ineq; ++k) { in try_wrap_in_facets()
1916 if (info[i].ineq[k] != STATUS_CUT) in try_wrap_in_facets()
1920 info[i].bmap->ineq[k], 1 + total); in try_wrap_in_facets()
1921 if (wrap_in_facet(wraps, w, &info[j], set_i, snap) < 0) in try_wrap_in_facets()
1928 return fuse(i, j, info, wraps->mat, 0, 1); in try_wrap_in_facets()
1943 struct isl_coalesce_info *info) in wrap_in_facets() argument
1950 isl_size total = isl_basic_map_dim(info[i].bmap, isl_dim_all); in wrap_in_facets()
1955 if (isl_tab_extend_cons(info[j].tab, 1) < 0) in wrap_in_facets()
1958 max_wrap = 1 + 2 * info[j].bmap->n_eq + info[j].bmap->n_ineq; in wrap_in_facets()
1961 set_i = set_from_updated_bmap(info[i].bmap, info[i].tab); in wrap_in_facets()
1962 ctx = isl_basic_map_get_ctx(info[i].bmap); in wrap_in_facets()
1964 if (wraps_init(&wraps, mat, info, i, j) < 0) in wrap_in_facets()
1969 change = try_wrap_in_facets(i, j, info, &wraps, set_i); in wrap_in_facets()
2055 struct isl_coalesce_info *info) in can_wrap_in_set() argument
2061 if (ISL_F_ISSET(info[i].bmap, ISL_BASIC_MAP_RATIONAL) || in can_wrap_in_set()
2062 ISL_F_ISSET(info[j].bmap, ISL_BASIC_MAP_RATIONAL)) in can_wrap_in_set()
2065 n = count_eq(&info[i], STATUS_CUT) + count_ineq(&info[i], STATUS_CUT); in can_wrap_in_set()
2069 total = isl_basic_map_dim(info[i].bmap, isl_dim_all); in can_wrap_in_set()
2072 for (k = 0; k < info[i].bmap->n_eq; ++k) { in can_wrap_in_set()
2076 if (info[i].eq[2 * k + l] != STATUS_CUT) in can_wrap_in_set()
2080 isl_seq_neg(info[i].bmap->eq[k], in can_wrap_in_set()
2081 info[i].bmap->eq[k], 1 + total); in can_wrap_in_set()
2082 type = type_of_relaxed(info[j].tab, in can_wrap_in_set()
2083 info[i].bmap->eq[k]); in can_wrap_in_set()
2085 isl_seq_neg(info[i].bmap->eq[k], in can_wrap_in_set()
2086 info[i].bmap->eq[k], 1 + total); in can_wrap_in_set()
2094 for (k = 0; k < info[i].bmap->n_ineq; ++k) { in can_wrap_in_set()
2097 if (info[i].ineq[k] != STATUS_CUT) in can_wrap_in_set()
2100 type = type_of_relaxed(info[j].tab, info[i].bmap->ineq[k]); in can_wrap_in_set()
2107 return wrap_in_facets(i, j, n, info); in can_wrap_in_set()
2114 static enum isl_change check_wrap(int i, int j, struct isl_coalesce_info *info) in check_wrap() argument
2118 change = can_wrap_in_set(i, j, info); in check_wrap()
2122 change = can_wrap_in_set(j, i, info); in check_wrap()
2131 static isl_bool all_cut_by_one(int i, int j, struct isl_coalesce_info *info, in all_cut_by_one() argument
2137 for (l = 0; l < info[i].bmap->n_ineq; ++l) { in all_cut_by_one()
2140 if (info[i].ineq[l] != STATUS_CUT) in all_cut_by_one()
2142 type = type_of_relaxed(info[j].tab, info[i].bmap->ineq[l]); in all_cut_by_one()
2170 struct isl_coalesce_info *info) in check_single_adj_eq() argument
2179 n_cut = count_ineq(&info[i], STATUS_CUT); in check_single_adj_eq()
2181 k = find_ineq(&info[i], STATUS_ADJ_EQ); in check_single_adj_eq()
2184 ctx = isl_basic_map_get_ctx(info[i].bmap); in check_single_adj_eq()
2189 try_relax = all_cut_by_one(i, j, info, relax + 1); in check_single_adj_eq()
2197 change = is_relaxed_extension(i, j, 1 + n_cut, relax, info); in check_single_adj_eq()
2203 change = can_wrap_in_facet(i, j, k, info, n_cut > 0); in check_single_adj_eq()
2219 struct isl_coalesce_info *info) in check_adj_eq() argument
2221 if (any_eq(&info[i], STATUS_ADJ_INEQ) && in check_adj_eq()
2222 any_eq(&info[j], STATUS_ADJ_INEQ)) in check_adj_eq()
2226 if (any_eq(&info[i], STATUS_ADJ_INEQ)) in check_adj_eq()
2227 return check_adj_eq(j, i, info); in check_adj_eq()
2231 if (count_ineq(&info[i], STATUS_ADJ_EQ) != 1) { in check_adj_eq()
2232 if (all_valid_or_cut(&info[i])) in check_adj_eq()
2233 return can_wrap_in_set(i, j, info); in check_adj_eq()
2236 if (any_eq(&info[i], STATUS_CUT)) in check_adj_eq()
2238 if (any_ineq(&info[j], STATUS_ADJ_EQ) || in check_adj_eq()
2239 any_ineq(&info[i], STATUS_ADJ_INEQ) || in check_adj_eq()
2240 any_ineq(&info[j], STATUS_ADJ_INEQ)) in check_adj_eq()
2244 return check_single_adj_eq(i, j, info); in check_adj_eq()
2260 struct isl_coalesce_info *info) in check_ineq_adj_eq() argument
2264 if (any_eq(&info[i], STATUS_CUT)) in check_ineq_adj_eq()
2266 if (any_ineq(&info[i], STATUS_CUT)) in check_ineq_adj_eq()
2268 if (any_ineq(&info[i], STATUS_ADJ_INEQ)) in check_ineq_adj_eq()
2270 if (count_ineq(&info[i], STATUS_ADJ_EQ) != 1) in check_ineq_adj_eq()
2273 k = find_ineq(&info[i], STATUS_ADJ_EQ); in check_ineq_adj_eq()
2275 return can_wrap_in_facet(i, j, k, info, 0); in check_ineq_adj_eq()
2297 struct isl_coalesce_info *info) in check_eq_adj_eq() argument
2308 isl_size total = isl_basic_map_dim(info[i].bmap, isl_dim_all); in check_eq_adj_eq()
2312 if (count_eq(&info[i], STATUS_ADJ_EQ) != 1) in check_eq_adj_eq()
2315 k = find_eq(&info[i], STATUS_ADJ_EQ); in check_eq_adj_eq()
2317 set_i = set_from_updated_bmap(info[i].bmap, info[i].tab); in check_eq_adj_eq()
2318 set_j = set_from_updated_bmap(info[j].bmap, info[j].tab); in check_eq_adj_eq()
2319 ctx = isl_basic_map_get_ctx(info[i].bmap); in check_eq_adj_eq()
2320 mat = isl_mat_alloc(ctx, 2 * (info[i].bmap->n_eq + info[j].bmap->n_eq) + in check_eq_adj_eq()
2321 info[i].bmap->n_ineq + info[j].bmap->n_ineq, in check_eq_adj_eq()
2323 if (wraps_init(&wraps, mat, info, i, j) < 0) in check_eq_adj_eq()
2330 isl_seq_neg(bound->el, info[i].bmap->eq[k / 2], 1 + total); in check_eq_adj_eq()
2332 isl_seq_cpy(bound->el, info[i].bmap->eq[k / 2], 1 + total); in check_eq_adj_eq()
2338 if (add_wraps(&wraps, &info[j], bound->el, set_i) < 0) in check_eq_adj_eq()
2349 if (add_wraps(&wraps, &info[i], bound->el, set_j) < 0) in check_eq_adj_eq()
2354 change = fuse(i, j, info, wraps.mat, detect_equalities, 0); in check_eq_adj_eq()
2369 /* Initialize the "eq" and "ineq" fields of "info".
2371 static void init_status(struct isl_coalesce_info *info) in init_status() argument
2373 info->eq = info->ineq = NULL; in init_status()
2376 /* Set info->eq to the positions of the equalities of info->bmap
2378 * If info->eq has already been computed, then do not compute it again.
2380 static void set_eq_status_in(struct isl_coalesce_info *info, in set_eq_status_in() argument
2383 if (info->eq) in set_eq_status_in()
2385 info->eq = eq_status_in(info->bmap, tab); in set_eq_status_in()
2388 /* Set info->ineq to the positions of the inequalities of info->bmap
2390 * If info->ineq has already been computed, then do not compute it again.
2392 static void set_ineq_status_in(struct isl_coalesce_info *info, in set_ineq_status_in() argument
2395 if (info->ineq) in set_ineq_status_in()
2397 info->ineq = ineq_status_in(info->bmap, info->tab, tab); in set_ineq_status_in()
2400 /* Free the memory allocated by the "eq" and "ineq" fields of "info".
2401 * This function assumes that init_status has been called on "info" first,
2405 static void clear_status(struct isl_coalesce_info *info) in clear_status() argument
2407 free(info->eq); in clear_status()
2408 free(info->ineq); in clear_status()
2411 /* Are all inequality constraints of the basic map represented by "info"
2415 static int all_ineq_valid_or_single_adj_ineq(struct isl_coalesce_info *info) in all_ineq_valid_or_single_adj_ineq() argument
2420 for (i = 0; i < info->bmap->n_ineq; ++i) { in all_ineq_valid_or_single_adj_ineq()
2421 if (info->ineq[i] == STATUS_REDUNDANT) in all_ineq_valid_or_single_adj_ineq()
2423 if (info->ineq[i] == STATUS_VALID) in all_ineq_valid_or_single_adj_ineq()
2425 if (info->ineq[i] != STATUS_ADJ_INEQ) in all_ineq_valid_or_single_adj_ineq()
2448 struct isl_coalesce_info *info) in separating_equality() argument
2452 if (all(info[j].eq, 2 * info[j].bmap->n_eq, STATUS_VALID) && in separating_equality()
2453 all_ineq_valid_or_single_adj_ineq(&info[j])) in separating_equality()
2454 change = is_adj_ineq_extension(j, i, info); in separating_equality()
2456 clear_status(&info[i]); in separating_equality()
2457 clear_status(&info[j]); in separating_equality()
2467 * The "eq" and "ineq" fields of info[i] and info[j] are assumed
2548 struct isl_coalesce_info *info) in coalesce_local_pair_reuse() argument
2552 set_ineq_status_in(&info[i], info[j].tab); in coalesce_local_pair_reuse()
2553 if (info[i].bmap->n_ineq && !info[i].ineq) in coalesce_local_pair_reuse()
2555 if (any_ineq(&info[i], STATUS_ERROR)) in coalesce_local_pair_reuse()
2557 if (any_ineq(&info[i], STATUS_SEPARATE)) in coalesce_local_pair_reuse()
2560 set_ineq_status_in(&info[j], info[i].tab); in coalesce_local_pair_reuse()
2561 if (info[j].bmap->n_ineq && !info[j].ineq) in coalesce_local_pair_reuse()
2563 if (any_ineq(&info[j], STATUS_ERROR)) in coalesce_local_pair_reuse()
2565 if (any_ineq(&info[j], STATUS_SEPARATE)) in coalesce_local_pair_reuse()
2568 set_eq_status_in(&info[i], info[j].tab); in coalesce_local_pair_reuse()
2569 if (info[i].bmap->n_eq && !info[i].eq) in coalesce_local_pair_reuse()
2571 if (any_eq(&info[i], STATUS_ERROR)) in coalesce_local_pair_reuse()
2574 set_eq_status_in(&info[j], info[i].tab); in coalesce_local_pair_reuse()
2575 if (info[j].bmap->n_eq && !info[j].eq) in coalesce_local_pair_reuse()
2577 if (any_eq(&info[j], STATUS_ERROR)) in coalesce_local_pair_reuse()
2580 if (any_eq(&info[i], STATUS_SEPARATE)) in coalesce_local_pair_reuse()
2581 return separating_equality(i, j, info); in coalesce_local_pair_reuse()
2582 if (any_eq(&info[j], STATUS_SEPARATE)) in coalesce_local_pair_reuse()
2583 return separating_equality(j, i, info); in coalesce_local_pair_reuse()
2585 if (all(info[i].eq, 2 * info[i].bmap->n_eq, STATUS_VALID) && in coalesce_local_pair_reuse()
2586 all(info[i].ineq, info[i].bmap->n_ineq, STATUS_VALID)) { in coalesce_local_pair_reuse()
2587 drop(&info[j]); in coalesce_local_pair_reuse()
2589 } else if (all(info[j].eq, 2 * info[j].bmap->n_eq, STATUS_VALID) && in coalesce_local_pair_reuse()
2590 all(info[j].ineq, info[j].bmap->n_ineq, STATUS_VALID)) { in coalesce_local_pair_reuse()
2591 drop(&info[i]); in coalesce_local_pair_reuse()
2593 } else if (any_eq(&info[i], STATUS_ADJ_EQ)) { in coalesce_local_pair_reuse()
2594 change = check_eq_adj_eq(i, j, info); in coalesce_local_pair_reuse()
2595 } else if (any_eq(&info[j], STATUS_ADJ_EQ)) { in coalesce_local_pair_reuse()
2596 change = check_eq_adj_eq(j, i, info); in coalesce_local_pair_reuse()
2597 } else if (any_eq(&info[i], STATUS_ADJ_INEQ) || in coalesce_local_pair_reuse()
2598 any_eq(&info[j], STATUS_ADJ_INEQ)) { in coalesce_local_pair_reuse()
2599 change = check_adj_eq(i, j, info); in coalesce_local_pair_reuse()
2600 } else if (any_ineq(&info[i], STATUS_ADJ_EQ)) { in coalesce_local_pair_reuse()
2601 change = check_ineq_adj_eq(i, j, info); in coalesce_local_pair_reuse()
2602 } else if (any_ineq(&info[j], STATUS_ADJ_EQ)) { in coalesce_local_pair_reuse()
2603 change = check_ineq_adj_eq(j, i, info); in coalesce_local_pair_reuse()
2604 } else if (any_ineq(&info[i], STATUS_ADJ_INEQ) || in coalesce_local_pair_reuse()
2605 any_ineq(&info[j], STATUS_ADJ_INEQ)) { in coalesce_local_pair_reuse()
2606 change = check_adj_ineq(i, j, info); in coalesce_local_pair_reuse()
2608 if (!any_eq(&info[i], STATUS_CUT) && in coalesce_local_pair_reuse()
2609 !any_eq(&info[j], STATUS_CUT)) in coalesce_local_pair_reuse()
2610 change = check_facets(i, j, info); in coalesce_local_pair_reuse()
2612 change = check_wrap(i, j, info); in coalesce_local_pair_reuse()
2616 clear_status(&info[i]); in coalesce_local_pair_reuse()
2617 clear_status(&info[j]); in coalesce_local_pair_reuse()
2620 clear_status(&info[i]); in coalesce_local_pair_reuse()
2621 clear_status(&info[j]); in coalesce_local_pair_reuse()
2633 struct isl_coalesce_info *info) in coalesce_local_pair() argument
2635 init_status(&info[i]); in coalesce_local_pair()
2636 init_status(&info[j]); in coalesce_local_pair()
2637 return coalesce_local_pair_reuse(i, j, info); in coalesce_local_pair()
2641 * represented by "info" by "shift".
2651 static isl_stat shift_div(struct isl_coalesce_info *info, int div, in shift_div() argument
2656 info->bmap = isl_basic_map_shift_div(info->bmap, div, 0, shift); in shift_div()
2657 if (!info->bmap) in shift_div()
2660 total = isl_basic_map_dim(info->bmap, isl_dim_all); in shift_div()
2661 n_div = isl_basic_map_dim(info->bmap, isl_dim_div); in shift_div()
2665 if (isl_tab_shift_var(info->tab, total + div, shift) < 0) in shift_div()
2700 static isl_stat normalize_stride_div(struct isl_coalesce_info *info, int div) in normalize_stride_div() argument
2707 defined = isl_basic_map_has_defining_equality(info->bmap, isl_dim_div, in normalize_stride_div()
2721 r = shift_div(info, div, shift); in normalize_stride_div()
2729 info->bmap = isl_basic_map_set_div_expr_constant_num_si_inplace( in normalize_stride_div()
2730 info->bmap, div, 0); in normalize_stride_div()
2731 if (!info->bmap) in normalize_stride_div()
2783 * at position "div" of the basic map represented by "info" by "shift".
2795 static isl_stat shift_if_cst_int(struct isl_coalesce_info *info, int div, in shift_if_cst_int() argument
2819 r = shift_div(info, div, d); in shift_if_cst_int()
3055 * The information in info->ineq is thrown away because it was
3059 static isl_stat fix_constant_divs(struct isl_coalesce_info *info, in fix_constant_divs() argument
3066 o_div = isl_basic_map_offset(info->bmap, isl_dim_div) - 1; in fix_constant_divs()
3067 ineq = isl_vec_alloc(isl_tab_get_ctx(info->tab), 1 + info->tab->n_var); in fix_constant_divs()
3070 isl_seq_clr(ineq->el + 1, info->tab->n_var); in fix_constant_divs()
3074 info->bmap = isl_basic_map_extend_constraints( in fix_constant_divs()
3075 info->bmap, 0, 2); in fix_constant_divs()
3076 info->bmap = isl_basic_map_add_div_constraints( in fix_constant_divs()
3077 info->bmap, expanded[i].pos - o_div); in fix_constant_divs()
3081 info->bmap = isl_basic_map_add_ineq(info->bmap, in fix_constant_divs()
3085 info->bmap = isl_basic_map_add_ineq(info->bmap, in fix_constant_divs()
3089 if (copy_ineq(info->tab, info->bmap) < 0) in fix_constant_divs()
3092 isl_tab_select_facet(info->tab, info->tab->n_con - 1) < 0) in fix_constant_divs()
3098 clear_status(info); in fix_constant_divs()
3099 init_status(info); in fix_constant_divs()
3105 * into info->tab and info->bmap and
3106 * update info->ineq with respect to the redundant constraints
3108 * "bmap" contains the result of this insertion in info->bmap,
3109 * while info->bmap is the original version
3111 * state of info->tab. The number of constraints in info->bmap
3113 * in info->tab. This is required to be able to detect
3118 * that were added to "bmap" after info->tab was created
3119 * from info->bmap.
3121 * to attain a fixed integer value in info->tab.
3125 * Replace info->bmap by "bmap" to match the changes to info->tab.
3126 * info->ineq was computed without a tableau and therefore
3132 * since info->ineq is completely thrown away in this case.
3134 static isl_stat tab_insert_divs(struct isl_coalesce_info *info, in tab_insert_divs() argument
3144 if (info->bmap->n_eq + info->bmap->n_ineq != info->tab->n_con) in tab_insert_divs()
3149 if (isl_tab_extend_vars(info->tab, n) < 0) in tab_insert_divs()
3151 if (isl_tab_extend_cons(info->tab, 2 * n) < 0) in tab_insert_divs()
3155 if (isl_tab_insert_var(info->tab, expanded[i].pos) < 0) in tab_insert_divs()
3159 snap = isl_tab_snap(info->tab); in tab_insert_divs()
3161 n_ineq = info->tab->n_con - info->tab->n_eq; in tab_insert_divs()
3162 if (copy_ineq(info->tab, bmap) < 0) in tab_insert_divs()
3165 isl_basic_map_free(info->bmap); in tab_insert_divs()
3166 info->bmap = bmap; in tab_insert_divs()
3170 expanded[i].cst = isl_tab_is_constant(info->tab, in tab_insert_divs()
3179 if (isl_tab_rollback(info->tab, snap) < 0) in tab_insert_divs()
3181 info->bmap = isl_basic_map_cow(info->bmap); in tab_insert_divs()
3182 info->bmap = isl_basic_map_free_inequality(info->bmap, 2 * n); in tab_insert_divs()
3183 if (!info->bmap) in tab_insert_divs()
3186 return fix_constant_divs(info, n, expanded); in tab_insert_divs()
3189 n_eq = info->bmap->n_eq; in tab_insert_divs()
3191 if (isl_tab_is_redundant(info->tab, n_eq + i)) in tab_insert_divs()
3192 info->ineq[i] = STATUS_REDUNDANT; in tab_insert_divs()
3201 /* Expand info->tab and info->bmap in the same way "bmap" was expanded
3203 * update info->ineq with respect to the redundant constraints
3204 * in the resulting tableau. info->bmap is the original version
3206 * state of info->tab. The number of constraints in info->bmap
3208 * in info->tab. This is required to be able to detect
3214 static isl_stat expand_tab(struct isl_coalesce_info *info, int *exp, in expand_tab() argument
3230 extra_var = total - info->tab->n_var; in expand_tab()
3251 r = tab_insert_divs(info, extra_var, expanded, bmap); in expand_tab()
3263 /* Check if the union of the basic maps represented by info[i] and info[j]
3265 * after expanding the divs of info[i] to match those of info[j].
3270 * The caller has already checked for info[j] being a subset of info[i].
3271 * If some of the divs of info[j] are unknown, then the expanded info[i]
3277 * info[i].bmap has already been expanded and the result is passed in
3279 * The "eq" and "ineq" fields of info[i] reflect the status of
3280 * the constraints of the expanded "bmap" with respect to info[j].tab.
3281 * However, inequality constraints that are redundant in info[i].tab
3284 * Replace info[i].bmap by "bmap" and expand info[i].tab as well,
3285 * updating info[i].ineq with respect to the redundant constraints.
3286 * Then try and coalesce the expanded info[i] with info[j],
3287 * reusing the information in info[i].eq and info[i].ineq.
3288 * If this does not result in any coalescing or if it results in info[j]
3290 * of info[j] being a subset of info[i] has already been checked by
3291 * the caller), then revert info[i] to its original state.
3294 int i, int j, struct isl_coalesce_info *info, __isl_keep isl_mat *div, in coalesce_expand_tab_divs() argument
3302 known = isl_basic_map_divs_known(info[j].bmap); in coalesce_expand_tab_divs()
3304 clear_status(&info[i]); in coalesce_expand_tab_divs()
3309 bmap_i = isl_basic_map_copy(info[i].bmap); in coalesce_expand_tab_divs()
3310 snap = isl_tab_snap(info[i].tab); in coalesce_expand_tab_divs()
3311 if (expand_tab(&info[i], exp, bmap) < 0) in coalesce_expand_tab_divs()
3314 init_status(&info[j]); in coalesce_expand_tab_divs()
3316 change = coalesce_local_pair_reuse(i, j, info); in coalesce_expand_tab_divs()
3318 clear_status(&info[i]); in coalesce_expand_tab_divs()
3322 isl_basic_map_free(info[i].bmap); in coalesce_expand_tab_divs()
3323 info[i].bmap = bmap_i; in coalesce_expand_tab_divs()
3325 if (isl_tab_rollback(info[i].tab, snap) < 0) in coalesce_expand_tab_divs()
3332 /* Check if the union of "bmap" and the basic map represented by info[j]
3334 * after expanding the divs of "bmap" to match those of info[j].
3340 * represented by the tableau info[j].tab.
3344 * info[j].tab.
3346 * If "i" is not equal to -1, then "bmap" is equal to info[i].bmap.
3347 * In this case, the positions of the constraints of info[i].bmap
3348 * with respect to the basic map represented by info[j] are stored
3349 * in info[i].
3352 * represented by the tableau info[j].tab and if "i" is not -1,
3353 * i.e., if the original "bmap" is info[i].bmap, then expand info[i].tab
3358 struct isl_coalesce_info *info, __isl_keep isl_mat *div, int *exp) in coalesce_with_expanded_divs() argument
3363 info_i = i >= 0 ? &info[i] : &info_local; in coalesce_with_expanded_divs()
3373 info_i->eq = eq_status_in(bmap, info[j].tab); in coalesce_with_expanded_divs()
3381 info_i->ineq = ineq_status_in(bmap, NULL, info[j].tab); in coalesce_with_expanded_divs()
3391 drop(&info[j]); in coalesce_with_expanded_divs()
3396 return coalesce_expand_tab_divs(bmap, i, j, info, div, exp); in coalesce_with_expanded_divs()
3408 /* Check if the union of "bmap_i" and the basic map represented by info[j]
3410 * after aligning the divs of "bmap_i" to match those of info[j].
3416 * info[j] after aligning the divs of "bmap_i" to those of info[j].
3418 * is smaller than (or equal to) the number of divs of info[j].
3421 * of those of info[j].bmap. If so, we pass control over to
3424 * If "i" is not equal to -1, then "bmap" is equal to info[i].bmap.
3428 struct isl_coalesce_info *info) in coalesce_after_aligning_divs() argument
3446 div_j = isl_basic_map_get_divs(info[j].bmap); in coalesce_after_aligning_divs()
3462 i, j, info, div, exp1); in coalesce_after_aligning_divs()
3501 struct isl_coalesce_info *info) in coalesce_subset_with_equalities() argument
3507 if (info[j].bmap->n_eq == 0) in coalesce_subset_with_equalities()
3509 if (info[i].bmap->n_div == 0) in coalesce_subset_with_equalities()
3512 hull_i = isl_basic_map_copy(info[i].bmap); in coalesce_subset_with_equalities()
3514 hull_j = isl_basic_map_copy(info[j].bmap); in coalesce_subset_with_equalities()
3529 bmap_i = isl_basic_map_copy(info[i].bmap); in coalesce_subset_with_equalities()
3534 if (bmap_i->n_div > info[j].bmap->n_div) { in coalesce_subset_with_equalities()
3539 change = coalesce_after_aligning_divs(bmap_i, -1, j, info); in coalesce_subset_with_equalities()
3546 /* Check if the union of the basic maps represented by info[i] and info[j]
3562 struct isl_coalesce_info *info) in coalesce_divs() argument
3566 if (info[i].bmap->n_div < info[j].bmap->n_div) in coalesce_divs()
3567 change = coalesce_after_aligning_divs(info[i].bmap, i, j, info); in coalesce_divs()
3571 if (info[j].bmap->n_div < info[i].bmap->n_div) in coalesce_divs()
3572 change = coalesce_after_aligning_divs(info[j].bmap, j, i, info); in coalesce_divs()
3576 change = coalesce_subset_with_equalities(i, j, info); in coalesce_divs()
3580 change = coalesce_subset_with_equalities(j, i, info); in coalesce_divs()
3693 /* Add variables to info->bmap and info->tab corresponding to the elements
3703 * do not appear in info->bmap. These constraints are not added
3704 * to info->bmap because for internal consistency, they would need to
3705 * be added to info->tab as well, where they could combine with the equality
3709 static isl_stat add_sub_vars(struct isl_coalesce_info *info, in add_sub_vars() argument
3715 info->bmap = isl_basic_map_cow(info->bmap); in add_sub_vars()
3716 info->bmap = isl_basic_map_extend(info->bmap, extra_var, 0, 0); in add_sub_vars()
3718 if (!info->bmap || n < 0) in add_sub_vars()
3732 if (isl_tab_insert_var(info->tab, dim + i) < 0) in add_sub_vars()
3734 d = isl_basic_map_alloc_div(info->bmap); in add_sub_vars()
3737 info->bmap = isl_basic_map_mark_div_unknown(info->bmap, d); in add_sub_vars()
3739 info->bmap = isl_basic_map_swap_div(info->bmap, in add_sub_vars()
3741 if (!info->bmap) in add_sub_vars()
3799 /* Add variables to info->tab and info->bmap corresponding to the elements
3801 * in info->tab is fixed to the purely affine expression defined by the element.
3802 * "dim" is the offset in the variables of info->tab where we should
3804 * When this function returns, the total number of variables in info->tab
3807 static isl_stat add_subs(struct isl_coalesce_info *info, in add_subs() argument
3817 extra_var = n - (info->tab->n_var - dim); in add_subs()
3819 if (isl_tab_extend_vars(info->tab, extra_var) < 0) in add_subs()
3821 if (isl_tab_extend_cons(info->tab, 2 * extra_var) < 0) in add_subs()
3823 if (add_sub_vars(info, list, dim, extra_var) < 0) in add_subs()
3826 return add_sub_equalities(info->tab, list, dim); in add_subs()
3843 struct isl_coalesce_info *info, __isl_keep isl_aff_list *list) in coalesce_with_subs() argument
3850 bmap_j = isl_basic_map_copy(info[j].bmap); in coalesce_with_subs()
3851 snap = isl_tab_snap(info[j].tab); in coalesce_with_subs()
3858 if (add_subs(&info[j], list, dim) < 0) in coalesce_with_subs()
3861 change = coalesce_local_pair(i, j, info); in coalesce_with_subs()
3865 isl_basic_map_free(info[j].bmap); in coalesce_with_subs()
3866 info[j].bmap = bmap_j; in coalesce_with_subs()
3868 if (isl_tab_rollback(info[j].tab, snap) < 0) in coalesce_with_subs()
3893 struct isl_coalesce_info *info) in check_coalesce_into_eq() argument
3901 n_div_i = isl_basic_map_dim(info[i].bmap, isl_dim_div); in check_coalesce_into_eq()
3902 n_div_j = isl_basic_map_dim(info[j].bmap, isl_dim_div); in check_coalesce_into_eq()
3907 if (info[j].bmap->n_eq == 0) in check_coalesce_into_eq()
3910 hull_i = isl_basic_map_copy(info[i].bmap); in check_coalesce_into_eq()
3912 hull_j = isl_basic_map_copy(info[j].bmap); in check_coalesce_into_eq()
3927 list = set_up_substitutions(info[i].bmap, info[j].bmap, hull_j); in check_coalesce_into_eq()
3936 change = coalesce_with_subs(i, j, info, list); in check_coalesce_into_eq()
3954 struct isl_coalesce_info *info) in check_coalesce_eq() argument
3959 known = isl_basic_map_divs_known(info[i].bmap); in check_coalesce_eq()
3962 known = isl_basic_map_divs_known(info[j].bmap); in check_coalesce_eq()
3965 nested = has_nested_div(info[i].bmap); in check_coalesce_eq()
3968 nested = has_nested_div(info[j].bmap); in check_coalesce_eq()
3972 change = check_coalesce_into_eq(i, j, info); in check_coalesce_eq()
3975 change = check_coalesce_into_eq(j, i, info); in check_coalesce_eq()
4003 struct isl_coalesce_info *info) in coalesce_pair() argument
4010 if (harmonize_divs(&info[i], &info[j]) < 0) in coalesce_pair()
4012 same = same_divs(info[i].bmap, info[j].bmap); in coalesce_pair()
4016 return coalesce_local_pair(i, j, info); in coalesce_pair()
4018 ctx = isl_basic_map_get_ctx(info[i].bmap); in coalesce_pair()
4020 if (!preserve && info[i].bmap->n_div == info[j].bmap->n_div) { in coalesce_pair()
4021 change = coalesce_local_pair(i, j, info); in coalesce_pair()
4026 change = coalesce_divs(i, j, info); in coalesce_pair()
4030 return check_coalesce_eq(i, j, info); in coalesce_pair()
4040 /* Pairwise coalesce the basic maps in the range [start1, end1[ of "info"
4054 static int coalesce_range(isl_ctx *ctx, struct isl_coalesce_info *info, in coalesce_range() argument
4060 if (info[i].removed) in coalesce_range()
4065 if (info[j].removed) in coalesce_range()
4067 if (info[i].removed) in coalesce_range()
4071 changed = coalesce_pair(i, j, info); in coalesce_range()
4091 /* Pairwise coalesce the basic maps described by the "n" elements of "info".
4099 static int coalesce(isl_ctx *ctx, int n, struct isl_coalesce_info *info) in coalesce() argument
4106 info[start - 1].hull_hash == info[start].hull_hash) in coalesce()
4108 if (coalesce_range(ctx, info, start, end, start, end) < 0) in coalesce()
4110 if (coalesce_range(ctx, info, start, end, end, n) < 0) in coalesce()
4117 /* Update the basic maps in "map" based on the information in "info".
4124 * If a basic map is still equal to the one from which the corresponding "info"
4130 int n, struct isl_coalesce_info *info) in update_basic_maps() argument
4138 if (info[i].removed) { in update_basic_maps()
4146 info[i].bmap = isl_basic_map_update_from_tab(info[i].bmap, in update_basic_maps()
4147 info[i].tab); in update_basic_maps()
4148 info[i].bmap = isl_basic_map_gauss(info[i].bmap, NULL); in update_basic_maps()
4149 if (info[i].simplify) in update_basic_maps()
4150 info[i].bmap = isl_basic_map_simplify(info[i].bmap); in update_basic_maps()
4151 info[i].bmap = isl_basic_map_finalize(info[i].bmap); in update_basic_maps()
4152 if (!info[i].bmap) in update_basic_maps()
4154 if (!info[i].modified) { in update_basic_maps()
4155 ISL_F_SET(info[i].bmap, ISL_BASIC_MAP_NO_IMPLICIT); in update_basic_maps()
4156 ISL_F_SET(info[i].bmap, ISL_BASIC_MAP_NO_REDUNDANT); in update_basic_maps()
4159 map->p[i] = info[i].bmap; in update_basic_maps()
4160 info[i].bmap = NULL; in update_basic_maps()
4196 struct isl_coalesce_info *info = NULL; in isl_map_coalesce() local
4214 info = isl_calloc_array(map->ctx, struct isl_coalesce_info, n); in isl_map_coalesce()
4215 if (!info) in isl_map_coalesce()
4222 info[i].bmap = isl_basic_map_copy(map->p[i]); in isl_map_coalesce()
4223 info[i].tab = isl_tab_from_basic_map(info[i].bmap, 0); in isl_map_coalesce()
4224 if (!info[i].tab) in isl_map_coalesce()
4226 if (!ISL_F_ISSET(info[i].bmap, ISL_BASIC_MAP_NO_IMPLICIT)) in isl_map_coalesce()
4227 if (isl_tab_detect_implicit_equalities(info[i].tab) < 0) in isl_map_coalesce()
4229 info[i].bmap = isl_tab_make_equalities_explicit(info[i].tab, in isl_map_coalesce()
4230 info[i].bmap); in isl_map_coalesce()
4231 if (!info[i].bmap) in isl_map_coalesce()
4233 if (!ISL_F_ISSET(info[i].bmap, ISL_BASIC_MAP_NO_REDUNDANT)) in isl_map_coalesce()
4234 if (isl_tab_detect_redundant(info[i].tab) < 0) in isl_map_coalesce()
4236 if (coalesce_info_set_hull_hash(&info[i]) < 0) in isl_map_coalesce()
4240 if (info[i].tab->empty) in isl_map_coalesce()
4241 drop(&info[i]); in isl_map_coalesce()
4243 if (coalesce(ctx, n, info) < 0) in isl_map_coalesce()
4246 map = update_basic_maps(map, n, info); in isl_map_coalesce()
4248 clear_coalesce_info(n, info); in isl_map_coalesce()
4252 clear_coalesce_info(n, info); in isl_map_coalesce()