1625 lines · c
1/*2 * Copyright 2010 INRIA Saclay3 *4 * Use of this software is governed by the MIT license5 *6 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,7 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,8 * 91893 Orsay, France 9 */10 11#include <isl_map_private.h>12#include <isl_aff_private.h>13#include <isl/set.h>14#include <isl_seq.h>15#include <isl_tab.h>16#include <isl_space_private.h>17#include <isl_morph.h>18#include <isl_vertices_private.h>19#include <isl_mat_private.h>20#include <isl_vec_private.h>21 22#define SELECTED 123#define DESELECTED -124#define UNSELECTED 025 26static __isl_give isl_vertices *compute_chambers(__isl_take isl_basic_set *bset,27 __isl_take isl_vertices *vertices);28 29__isl_give isl_vertices *isl_vertices_copy(__isl_keep isl_vertices *vertices)30{31 if (!vertices)32 return NULL;33 34 vertices->ref++;35 return vertices;36}37 38__isl_null isl_vertices *isl_vertices_free(__isl_take isl_vertices *vertices)39{40 int i;41 42 if (!vertices)43 return NULL;44 45 if (--vertices->ref > 0)46 return NULL;47 48 for (i = 0; i < vertices->n_vertices; ++i) {49 isl_basic_set_free(vertices->v[i].vertex);50 isl_basic_set_free(vertices->v[i].dom);51 }52 free(vertices->v);53 54 for (i = 0; i < vertices->n_chambers; ++i) {55 free(vertices->c[i].vertices);56 isl_basic_set_free(vertices->c[i].dom);57 }58 free(vertices->c);59 60 isl_basic_set_free(vertices->bset);61 free(vertices);62 63 return NULL;64}65 66struct isl_vertex_list {67 struct isl_vertex v;68 struct isl_vertex_list *next;69};70 71static struct isl_vertex_list *free_vertex_list(struct isl_vertex_list *list)72{73 struct isl_vertex_list *next;74 75 for (; list; list = next) {76 next = list->next;77 isl_basic_set_free(list->v.vertex);78 isl_basic_set_free(list->v.dom);79 free(list);80 }81 82 return NULL;83}84 85static __isl_give isl_vertices *vertices_from_list(__isl_keep isl_basic_set *bset,86 int n_vertices, struct isl_vertex_list *list)87{88 int i;89 struct isl_vertex_list *next;90 isl_vertices *vertices;91 92 vertices = isl_calloc_type(bset->ctx, isl_vertices);93 if (!vertices)94 goto error;95 vertices->ref = 1;96 vertices->bset = isl_basic_set_copy(bset);97 vertices->v = isl_alloc_array(bset->ctx, struct isl_vertex, n_vertices);98 if (n_vertices && !vertices->v)99 goto error;100 vertices->n_vertices = n_vertices;101 102 for (i = 0; list; list = next, i++) {103 next = list->next;104 vertices->v[i] = list->v;105 free(list);106 }107 108 return vertices;109error:110 isl_vertices_free(vertices);111 free_vertex_list(list);112 return NULL;113}114 115/* Prepend a vertex to the linked list "list" based on the equalities in "tab".116 * Return isl_bool_true if the vertex was actually added and117 * isl_bool_false otherwise.118 * In particular, vertices with a lower-dimensional activity domain are119 * not added to the list because they would not be included in any chamber.120 * Return isl_bool_error on error.121 */122static isl_bool add_vertex(struct isl_vertex_list **list,123 __isl_keep isl_basic_set *bset, struct isl_tab *tab)124{125 isl_size nvar;126 struct isl_vertex_list *v = NULL;127 128 if (isl_tab_detect_implicit_equalities(tab) < 0)129 return isl_bool_error;130 131 nvar = isl_basic_set_dim(bset, isl_dim_set);132 if (nvar < 0)133 return isl_bool_error;134 135 v = isl_calloc_type(tab->mat->ctx, struct isl_vertex_list);136 if (!v)137 goto error;138 139 v->v.vertex = isl_basic_set_copy(bset);140 v->v.vertex = isl_basic_set_cow(v->v.vertex);141 v->v.vertex = isl_basic_set_update_from_tab(v->v.vertex, tab);142 v->v.vertex = isl_basic_set_simplify(v->v.vertex);143 v->v.vertex = isl_basic_set_finalize(v->v.vertex);144 if (!v->v.vertex)145 goto error;146 isl_assert(bset->ctx, v->v.vertex->n_eq >= nvar, goto error);147 v->v.dom = isl_basic_set_copy(v->v.vertex);148 v->v.dom = isl_basic_set_params(v->v.dom);149 if (!v->v.dom)150 goto error;151 152 if (v->v.dom->n_eq > 0) {153 free_vertex_list(v);154 return isl_bool_false;155 }156 157 v->next = *list;158 *list = v;159 160 return isl_bool_true;161error:162 free_vertex_list(v);163 return isl_bool_error;164}165 166/* Compute the parametric vertices and the chamber decomposition167 * of an empty parametric polytope.168 */169static __isl_give isl_vertices *vertices_empty(__isl_keep isl_basic_set *bset)170{171 isl_vertices *vertices;172 173 if (!bset)174 return NULL;175 176 vertices = isl_calloc_type(bset->ctx, isl_vertices);177 if (!vertices)178 return NULL;179 vertices->bset = isl_basic_set_copy(bset);180 vertices->ref = 1;181 182 vertices->n_vertices = 0;183 vertices->n_chambers = 0;184 185 return vertices;186}187 188/* Compute the parametric vertices and the chamber decomposition189 * of the parametric polytope defined using the same constraints190 * as "bset" in the 0D case.191 * There is exactly one 0D vertex and a single chamber containing192 * the vertex.193 */194static __isl_give isl_vertices *vertices_0D(__isl_keep isl_basic_set *bset)195{196 isl_vertices *vertices;197 198 if (!bset)199 return NULL;200 201 vertices = isl_calloc_type(bset->ctx, isl_vertices);202 if (!vertices)203 return NULL;204 vertices->ref = 1;205 vertices->bset = isl_basic_set_copy(bset);206 207 vertices->v = isl_calloc_array(bset->ctx, struct isl_vertex, 1);208 if (!vertices->v)209 goto error;210 vertices->n_vertices = 1;211 vertices->v[0].vertex = isl_basic_set_copy(bset);212 vertices->v[0].dom = isl_basic_set_params(isl_basic_set_copy(bset));213 if (!vertices->v[0].vertex || !vertices->v[0].dom)214 goto error;215 216 vertices->c = isl_calloc_array(bset->ctx, struct isl_chamber, 1);217 if (!vertices->c)218 goto error;219 vertices->n_chambers = 1;220 vertices->c[0].n_vertices = 1;221 vertices->c[0].vertices = isl_calloc_array(bset->ctx, int, 1);222 if (!vertices->c[0].vertices)223 goto error;224 vertices->c[0].dom = isl_basic_set_copy(vertices->v[0].dom);225 if (!vertices->c[0].dom)226 goto error;227 228 return vertices;229error:230 isl_vertices_free(vertices);231 return NULL;232}233 234/* Is the row pointed to by "f" linearly independent of the "n" first235 * rows in "facets"?236 */237static isl_bool is_independent(__isl_keep isl_mat *facets, int n, isl_int *f)238{239 isl_size rank;240 241 if (isl_seq_first_non_zero(f, facets->n_col) < 0)242 return isl_bool_false;243 244 isl_seq_cpy(facets->row[n], f, facets->n_col);245 facets->n_row = n + 1;246 rank = isl_mat_rank(facets);247 if (rank < 0)248 return isl_bool_error;249 250 return isl_bool_ok(rank == n + 1);251}252 253/* Check whether we can select constraint "level", given the current selection254 * reflected by facets in "tab", the rows of "facets" and the earlier255 * "selected" elements of "selection".256 *257 * If the constraint is (strictly) redundant in the tableau, selecting it would258 * result in an empty tableau, so it can't be selected.259 * If the set variable part of the constraint is not linearly independent260 * of the set variable parts of the already selected constraints,261 * the constraint cannot be selected.262 * If selecting the constraint results in an empty tableau, the constraint263 * cannot be selected.264 * Finally, if selecting the constraint results in some explicitly265 * deselected constraints turning into equalities, then the corresponding266 * vertices have already been generated, so the constraint cannot be selected.267 */268static isl_bool can_select(__isl_keep isl_basic_set *bset, int level,269 struct isl_tab *tab, __isl_keep isl_mat *facets, int selected,270 int *selection)271{272 int i;273 isl_bool indep;274 unsigned ovar;275 struct isl_tab_undo *snap;276 277 if (isl_tab_is_redundant(tab, level))278 return isl_bool_false;279 280 ovar = isl_space_offset(bset->dim, isl_dim_set);281 282 indep = is_independent(facets, selected, bset->ineq[level] + 1 + ovar);283 if (indep < 0 || !indep)284 return indep;285 286 snap = isl_tab_snap(tab);287 if (isl_tab_select_facet(tab, level) < 0)288 return isl_bool_error;289 290 if (tab->empty) {291 if (isl_tab_rollback(tab, snap) < 0)292 return isl_bool_error;293 return isl_bool_false;294 }295 296 for (i = 0; i < level; ++i) {297 int sgn;298 299 if (selection[i] != DESELECTED)300 continue;301 302 if (isl_tab_is_equality(tab, i))303 sgn = 0;304 else if (isl_tab_is_redundant(tab, i))305 sgn = 1;306 else307 sgn = isl_tab_sign_of_max(tab, i);308 if (sgn < -1)309 return isl_bool_error;310 if (sgn <= 0) {311 if (isl_tab_rollback(tab, snap) < 0)312 return isl_bool_error;313 return isl_bool_false;314 }315 }316 317 return isl_bool_true;318}319 320/* Compute the parametric vertices and the chamber decomposition321 * of a parametric polytope that is not full-dimensional.322 *323 * Simply map the parametric polytope to a lower dimensional space324 * and map the resulting vertices back.325 */326static __isl_give isl_vertices *lower_dim_vertices(327 __isl_take isl_basic_set *bset)328{329 isl_morph *morph;330 isl_vertices *vertices;331 332 morph = isl_basic_set_full_compression(bset);333 bset = isl_morph_basic_set(isl_morph_copy(morph), bset);334 335 vertices = isl_basic_set_compute_vertices(bset);336 isl_basic_set_free(bset);337 338 morph = isl_morph_inverse(morph);339 340 vertices = isl_morph_vertices(morph, vertices);341 342 return vertices;343}344 345/* Compute the parametric vertices and the chamber decomposition346 * of a parametric polytope "bset" that is not full-dimensional.347 * Additionally, free both "copy" and "tab".348 */349static __isl_give isl_vertices *lower_dim_vertices_free(350 __isl_take isl_basic_set *bset, __isl_take isl_basic_set *copy,351 struct isl_tab *tab)352{353 isl_basic_set_free(copy);354 isl_tab_free(tab);355 return lower_dim_vertices(bset);356}357 358/* Detect implicit equality constraints in "bset" using the tableau359 * representation "tab".360 * Return a copy of "bset" with the implicit equality constraints361 * made explicit, leaving the original "bset" unmodified.362 */363static __isl_give isl_basic_set *detect_implicit_equality_constraints(364 __isl_keep isl_basic_set *bset, struct isl_tab *tab)365{366 if (isl_tab_detect_implicit_equalities(tab) < 0)367 return NULL;368 369 bset = isl_basic_set_copy(bset);370 bset = isl_basic_set_cow(bset);371 bset = isl_basic_set_update_from_tab(bset, tab);372 373 return bset;374}375 376/* Compute the parametric vertices and the chamber decomposition377 * of the parametric polytope defined using the same constraints378 * as "bset". "bset" is assumed to have no existentially quantified379 * variables.380 *381 * The vertices themselves are computed in a fairly simplistic way.382 * We simply run through all combinations of d constraints,383 * with d the number of set variables, and check if those d constraints384 * define a vertex. To avoid the generation of duplicate vertices,385 * which may happen if a vertex is defined by more than d constraints,386 * we make sure we only generate the vertex for the d constraints with387 * smallest index.388 *389 * Only potential vertices with a full-dimensional activity domain390 * are considered. However, if the input has (implicit) equality391 * constraints among the parameters, then activity domain392 * should be considered full-dimensional if it does not satisfy393 * any extra equality constraints beyond those of the input.394 * The implicit equality constraints of the input are therefore first detected.395 * If there are any, then the input is mapped to a lower dimensional space396 * such that the check for full-dimensional activity domains397 * can be performed with respect to a full-dimensional space.398 * Note that it is important to leave "bset" unmodified while detecting399 * equality constraints since the inequality constraints of "bset"400 * are assumed to correspond to those of the tableau.401 *402 * We set up a tableau and keep track of which facets have been403 * selected. The tableau is marked strict_redundant so that we can be404 * sure that any constraint that is marked redundant (and that is not405 * also marked zero) is not an equality.406 * If a constraint is marked DESELECTED, it means the constraint was407 * SELECTED before (in combination with the same selection of earlier408 * constraints). If such a deselected constraint turns out to be an409 * equality, then any vertex that may still be found with the current410 * selection has already been generated when the constraint was selected.411 * A constraint is marked UNSELECTED when there is no way selecting412 * the constraint could lead to a vertex (in combination with the current413 * selection of earlier constraints).414 *415 * The set variable coefficients of the selected constraints are stored416 * in the facets matrix.417 */418__isl_give isl_vertices *isl_basic_set_compute_vertices(419 __isl_keep isl_basic_set *bset)420{421 struct isl_tab *tab;422 int level;423 int init;424 isl_size n_eq;425 isl_size nvar;426 int *selection = NULL;427 int selected;428 struct isl_tab_undo **snap = NULL;429 isl_mat *facets = NULL;430 struct isl_vertex_list *list = NULL;431 int n_vertices = 0;432 isl_vertices *vertices;433 isl_basic_set *copy;434 isl_basic_set *test;435 436 if (!bset)437 return NULL;438 439 if (isl_basic_set_plain_is_empty(bset))440 return vertices_empty(bset);441 442 if (bset->n_eq != 0)443 return lower_dim_vertices(isl_basic_set_copy(bset));444 445 if (isl_basic_set_check_no_locals(bset) < 0)446 return NULL;447 448 nvar = isl_basic_set_dim(bset, isl_dim_set);449 if (nvar < 0)450 return NULL;451 if (nvar == 0)452 return vertices_0D(bset);453 454 copy = isl_basic_set_copy(bset);455 copy = isl_basic_set_set_rational(copy);456 if (!copy)457 return NULL;458 459 tab = isl_tab_from_basic_set(copy, 0);460 if (!tab)461 goto error;462 tab->strict_redundant = 1;463 464 if (tab->empty) {465 vertices = vertices_empty(copy);466 isl_basic_set_free(copy);467 isl_tab_free(tab);468 return vertices;469 }470 471 test = detect_implicit_equality_constraints(bset, tab);472 n_eq = isl_basic_set_n_equality(test);473 if (n_eq < 0)474 test = isl_basic_set_free(test);475 if (n_eq < 0 || n_eq > 0)476 return lower_dim_vertices_free(test, copy, tab);477 isl_basic_set_free(test);478 479 selection = isl_alloc_array(copy->ctx, int, copy->n_ineq);480 snap = isl_alloc_array(copy->ctx, struct isl_tab_undo *, copy->n_ineq);481 facets = isl_mat_alloc(copy->ctx, nvar, nvar);482 if ((copy->n_ineq && (!selection || !snap)) || !facets)483 goto error;484 485 level = 0;486 init = 1;487 selected = 0;488 489 while (level >= 0) {490 if (level >= copy->n_ineq ||491 (!init && selection[level] != SELECTED)) {492 --level;493 init = 0;494 continue;495 }496 if (init) {497 isl_bool ok;498 snap[level] = isl_tab_snap(tab);499 ok = can_select(copy, level, tab, facets, selected,500 selection);501 if (ok < 0)502 goto error;503 if (ok) {504 selection[level] = SELECTED;505 selected++;506 } else507 selection[level] = UNSELECTED;508 } else {509 selection[level] = DESELECTED;510 selected--;511 if (isl_tab_rollback(tab, snap[level]) < 0)512 goto error;513 }514 if (selected == nvar) {515 if (tab->n_dead == nvar) {516 isl_bool added = add_vertex(&list, copy, tab);517 if (added < 0)518 goto error;519 if (added)520 n_vertices++;521 }522 init = 0;523 continue;524 }525 ++level;526 init = 1;527 }528 529 isl_mat_free(facets);530 free(selection);531 free(snap);532 533 isl_tab_free(tab);534 535 vertices = vertices_from_list(copy, n_vertices, list);536 537 vertices = compute_chambers(copy, vertices);538 539 return vertices;540error:541 free_vertex_list(list);542 isl_mat_free(facets);543 free(selection);544 free(snap);545 isl_tab_free(tab);546 isl_basic_set_free(copy);547 return NULL;548}549 550struct isl_chamber_list {551 struct isl_chamber c;552 struct isl_chamber_list *next;553};554 555static void free_chamber_list(struct isl_chamber_list *list)556{557 struct isl_chamber_list *next;558 559 for (; list; list = next) {560 next = list->next;561 isl_basic_set_free(list->c.dom);562 free(list->c.vertices);563 free(list);564 }565}566 567/* Check whether the basic set "bset" is a superset of the basic set described568 * by "tab", i.e., check whether all constraints of "bset" are redundant.569 */570static isl_bool bset_covers_tab(__isl_keep isl_basic_set *bset,571 struct isl_tab *tab)572{573 int i;574 575 if (!bset || !tab)576 return isl_bool_error;577 578 for (i = 0; i < bset->n_ineq; ++i) {579 enum isl_ineq_type type = isl_tab_ineq_type(tab, bset->ineq[i]);580 switch (type) {581 case isl_ineq_error: return isl_bool_error;582 case isl_ineq_redundant: continue;583 default: return isl_bool_false;584 }585 }586 587 return isl_bool_true;588}589 590static __isl_give isl_vertices *vertices_add_chambers(591 __isl_take isl_vertices *vertices, int n_chambers,592 struct isl_chamber_list *list)593{594 int i;595 isl_ctx *ctx;596 struct isl_chamber_list *next;597 598 ctx = isl_vertices_get_ctx(vertices);599 vertices->c = isl_alloc_array(ctx, struct isl_chamber, n_chambers);600 if (!vertices->c)601 goto error;602 vertices->n_chambers = n_chambers;603 604 for (i = 0; list; list = next, i++) {605 next = list->next;606 vertices->c[i] = list->c;607 free(list);608 }609 610 return vertices;611error:612 isl_vertices_free(vertices);613 free_chamber_list(list);614 return NULL;615}616 617/* Can "tab" be intersected with "bset" without resulting in618 * a lower-dimensional set.619 * "bset" itself is assumed to be full-dimensional.620 */621static isl_bool can_intersect(struct isl_tab *tab,622 __isl_keep isl_basic_set *bset)623{624 int i;625 struct isl_tab_undo *snap;626 627 if (bset->n_eq > 0)628 isl_die(isl_basic_set_get_ctx(bset), isl_error_internal,629 "expecting full-dimensional input",630 return isl_bool_error);631 632 if (isl_tab_extend_cons(tab, bset->n_ineq) < 0)633 return isl_bool_error;634 635 snap = isl_tab_snap(tab);636 637 for (i = 0; i < bset->n_ineq; ++i) {638 enum isl_ineq_type type;639 640 type = isl_tab_ineq_type(tab, bset->ineq[i]);641 if (type < 0)642 return isl_bool_error;643 if (type == isl_ineq_redundant)644 continue;645 if (isl_tab_add_ineq(tab, bset->ineq[i]) < 0)646 return isl_bool_error;647 }648 649 if (isl_tab_detect_implicit_equalities(tab) < 0)650 return isl_bool_error;651 if (tab->n_dead) {652 if (isl_tab_rollback(tab, snap) < 0)653 return isl_bool_error;654 return isl_bool_false;655 }656 657 return isl_bool_true;658}659 660static int add_chamber(struct isl_chamber_list **list,661 __isl_keep isl_vertices *vertices, struct isl_tab *tab, int *selection)662{663 int n_frozen;664 int i, j;665 int n_vertices = 0;666 struct isl_tab_undo *snap;667 struct isl_chamber_list *c = NULL;668 669 for (i = 0; i < vertices->n_vertices; ++i)670 if (selection[i])671 n_vertices++;672 673 snap = isl_tab_snap(tab);674 675 for (i = 0; i < tab->n_con && tab->con[i].frozen; ++i)676 tab->con[i].frozen = 0;677 n_frozen = i;678 679 if (isl_tab_detect_redundant(tab) < 0)680 return -1;681 682 c = isl_calloc_type(tab->mat->ctx, struct isl_chamber_list);683 if (!c)684 goto error;685 c->c.vertices = isl_alloc_array(tab->mat->ctx, int, n_vertices);686 if (n_vertices && !c->c.vertices)687 goto error;688 c->c.dom = isl_basic_set_copy(isl_tab_peek_bset(tab));689 c->c.dom = isl_basic_set_set_rational(c->c.dom);690 c->c.dom = isl_basic_set_cow(c->c.dom);691 c->c.dom = isl_basic_set_update_from_tab(c->c.dom, tab);692 c->c.dom = isl_basic_set_simplify(c->c.dom);693 c->c.dom = isl_basic_set_finalize(c->c.dom);694 if (!c->c.dom)695 goto error;696 697 c->c.n_vertices = n_vertices;698 699 for (i = 0, j = 0; i < vertices->n_vertices; ++i)700 if (selection[i]) {701 c->c.vertices[j] = i;702 j++;703 }704 705 c->next = *list;706 *list = c;707 708 for (i = 0; i < n_frozen; ++i)709 tab->con[i].frozen = 1;710 711 if (isl_tab_rollback(tab, snap) < 0)712 return -1;713 714 return 0;715error:716 free_chamber_list(c);717 return -1;718}719 720struct isl_facet_todo {721 struct isl_tab *tab; /* A tableau representation of the facet */722 isl_basic_set *bset; /* A normalized basic set representation */723 isl_vec *constraint; /* Constraint pointing to the other side */724 struct isl_facet_todo *next;725};726 727static void free_todo(struct isl_facet_todo *todo)728{729 while (todo) {730 struct isl_facet_todo *next = todo->next;731 732 isl_tab_free(todo->tab);733 isl_basic_set_free(todo->bset);734 isl_vec_free(todo->constraint);735 free(todo);736 737 todo = next;738 }739}740 741static struct isl_facet_todo *create_todo(struct isl_tab *tab, int con)742{743 int i;744 int n_frozen;745 struct isl_tab_undo *snap;746 struct isl_facet_todo *todo;747 748 snap = isl_tab_snap(tab);749 750 for (i = 0; i < tab->n_con && tab->con[i].frozen; ++i)751 tab->con[i].frozen = 0;752 n_frozen = i;753 754 if (isl_tab_detect_redundant(tab) < 0)755 return NULL;756 757 todo = isl_calloc_type(tab->mat->ctx, struct isl_facet_todo);758 if (!todo)759 return NULL;760 761 todo->constraint = isl_vec_alloc(tab->mat->ctx, 1 + tab->n_var);762 if (!todo->constraint)763 goto error;764 isl_seq_neg(todo->constraint->el, tab->bmap->ineq[con], 1 + tab->n_var);765 todo->bset = isl_basic_set_copy(isl_tab_peek_bset(tab));766 todo->bset = isl_basic_set_set_rational(todo->bset);767 todo->bset = isl_basic_set_cow(todo->bset);768 todo->bset = isl_basic_set_update_from_tab(todo->bset, tab);769 todo->bset = isl_basic_set_simplify(todo->bset);770 todo->bset = isl_basic_set_sort_constraints(todo->bset);771 if (!todo->bset)772 goto error;773 ISL_F_SET(todo->bset, ISL_BASIC_SET_NO_REDUNDANT);774 todo->tab = isl_tab_dup(tab);775 if (!todo->tab)776 goto error;777 778 for (i = 0; i < n_frozen; ++i)779 tab->con[i].frozen = 1;780 781 if (isl_tab_rollback(tab, snap) < 0)782 goto error;783 784 return todo;785error:786 free_todo(todo);787 return NULL;788}789 790/* Create todo items for all interior facets of the chamber represented791 * by "tab" and collect them in "next".792 */793static int init_todo(struct isl_facet_todo **next, struct isl_tab *tab)794{795 int i;796 struct isl_tab_undo *snap;797 struct isl_facet_todo *todo;798 799 snap = isl_tab_snap(tab);800 801 for (i = 0; i < tab->n_con; ++i) {802 if (tab->con[i].frozen)803 continue;804 if (tab->con[i].is_redundant)805 continue;806 807 if (isl_tab_select_facet(tab, i) < 0)808 return -1;809 810 todo = create_todo(tab, i);811 if (!todo)812 return -1;813 814 todo->next = *next;815 *next = todo;816 817 if (isl_tab_rollback(tab, snap) < 0)818 return -1;819 }820 821 return 0;822}823 824/* Does the linked list contain a todo item that is the opposite of "todo".825 * If so, return 1 and remove the opposite todo item.826 */827static int has_opposite(struct isl_facet_todo *todo,828 struct isl_facet_todo **list)829{830 for (; *list; list = &(*list)->next) {831 int eq;832 eq = isl_basic_set_plain_is_equal(todo->bset, (*list)->bset);833 if (eq < 0)834 return -1;835 if (!eq)836 continue;837 todo = *list;838 *list = todo->next;839 todo->next = NULL;840 free_todo(todo);841 return 1;842 }843 844 return 0;845}846 847/* Create todo items for all interior facets of the chamber represented848 * by "tab" and collect them in first->next, taking care to cancel849 * opposite todo items.850 */851static int update_todo(struct isl_facet_todo *first, struct isl_tab *tab)852{853 int i;854 struct isl_tab_undo *snap;855 struct isl_facet_todo *todo;856 857 snap = isl_tab_snap(tab);858 859 for (i = 0; i < tab->n_con; ++i) {860 int drop;861 862 if (tab->con[i].frozen)863 continue;864 if (tab->con[i].is_redundant)865 continue;866 867 if (isl_tab_select_facet(tab, i) < 0)868 return -1;869 870 todo = create_todo(tab, i);871 if (!todo)872 return -1;873 874 drop = has_opposite(todo, &first->next);875 if (drop < 0)876 return -1;877 878 if (drop)879 free_todo(todo);880 else {881 todo->next = first->next;882 first->next = todo;883 }884 885 if (isl_tab_rollback(tab, snap) < 0)886 return -1;887 }888 889 return 0;890}891 892/* Compute the chamber decomposition of the parametric polytope respresented893 * by "bset" given the parametric vertices and their activity domains.894 *895 * We are only interested in full-dimensional chambers.896 * Each of these chambers is the intersection of the activity domains of897 * one or more vertices and the union of all chambers is equal to the898 * projection of the entire parametric polytope onto the parameter space.899 *900 * We first create an initial chamber by intersecting as many activity901 * domains as possible without ending up with an empty or lower-dimensional902 * set. As a minor optimization, we only consider those activity domains903 * that contain some arbitrary point.904 *905 * For each of the interior facets of the chamber, we construct a todo item,906 * containing the facet and a constraint containing the other side of the facet,907 * for constructing the chamber on the other side.908 * While their are any todo items left, we pick a todo item and909 * create the required chamber by intersecting all activity domains910 * that contain the facet and have a full-dimensional intersection with911 * the other side of the facet. For each of the interior facets, we912 * again create todo items, taking care to cancel opposite todo items.913 */914static __isl_give isl_vertices *compute_chambers(__isl_take isl_basic_set *bset,915 __isl_take isl_vertices *vertices)916{917 int i;918 isl_ctx *ctx;919 isl_size n_eq;920 isl_vec *sample = NULL;921 struct isl_tab *tab = NULL;922 struct isl_tab_undo *snap;923 int *selection = NULL;924 int n_chambers = 0;925 struct isl_chamber_list *list = NULL;926 struct isl_facet_todo *todo = NULL;927 928 if (!bset || !vertices)929 goto error;930 931 ctx = isl_vertices_get_ctx(vertices);932 selection = isl_alloc_array(ctx, int, vertices->n_vertices);933 if (vertices->n_vertices && !selection)934 goto error;935 936 bset = isl_basic_set_params(bset);937 n_eq = isl_basic_set_n_equality(bset);938 if (n_eq < 0)939 goto error;940 if (n_eq > 0)941 isl_die(isl_basic_set_get_ctx(bset), isl_error_internal,942 "expecting full-dimensional input", goto error);943 944 tab = isl_tab_from_basic_set(bset, 1);945 if (!tab)946 goto error;947 for (i = 0; i < bset->n_ineq; ++i)948 if (isl_tab_freeze_constraint(tab, i) < 0)949 goto error;950 isl_basic_set_free(bset);951 952 snap = isl_tab_snap(tab);953 954 sample = isl_tab_get_sample_value(tab);955 956 for (i = 0; i < vertices->n_vertices; ++i) {957 selection[i] = isl_basic_set_contains(vertices->v[i].dom, sample);958 if (selection[i] < 0)959 goto error;960 if (!selection[i])961 continue;962 selection[i] = can_intersect(tab, vertices->v[i].dom);963 if (selection[i] < 0)964 goto error;965 }966 967 if (isl_tab_detect_redundant(tab) < 0)968 goto error;969 970 if (add_chamber(&list, vertices, tab, selection) < 0)971 goto error;972 n_chambers++;973 974 if (init_todo(&todo, tab) < 0)975 goto error;976 977 while (todo) {978 struct isl_facet_todo *next;979 980 if (isl_tab_rollback(tab, snap) < 0)981 goto error;982 983 if (isl_tab_add_ineq(tab, todo->constraint->el) < 0)984 goto error;985 if (isl_tab_freeze_constraint(tab, tab->n_con - 1) < 0)986 goto error;987 988 for (i = 0; i < vertices->n_vertices; ++i) {989 selection[i] = bset_covers_tab(vertices->v[i].dom,990 todo->tab);991 if (selection[i] < 0)992 goto error;993 if (!selection[i])994 continue;995 selection[i] = can_intersect(tab, vertices->v[i].dom);996 if (selection[i] < 0)997 goto error;998 }999 1000 if (isl_tab_detect_redundant(tab) < 0)1001 goto error;1002 1003 if (add_chamber(&list, vertices, tab, selection) < 0)1004 goto error;1005 n_chambers++;1006 1007 if (update_todo(todo, tab) < 0)1008 goto error;1009 1010 next = todo->next;1011 todo->next = NULL;1012 free_todo(todo);1013 todo = next;1014 }1015 1016 isl_vec_free(sample);1017 1018 isl_tab_free(tab);1019 free(selection);1020 1021 vertices = vertices_add_chambers(vertices, n_chambers, list);1022 1023 for (i = 0; vertices && i < vertices->n_vertices; ++i) {1024 isl_basic_set_free(vertices->v[i].dom);1025 vertices->v[i].dom = NULL;1026 }1027 1028 return vertices;1029error:1030 free_chamber_list(list);1031 free_todo(todo);1032 isl_vec_free(sample);1033 isl_tab_free(tab);1034 free(selection);1035 if (!tab)1036 isl_basic_set_free(bset);1037 isl_vertices_free(vertices);1038 return NULL;1039}1040 1041isl_ctx *isl_vertex_get_ctx(__isl_keep isl_vertex *vertex)1042{1043 return vertex ? isl_vertices_get_ctx(vertex->vertices) : NULL;1044}1045 1046isl_size isl_vertex_get_id(__isl_keep isl_vertex *vertex)1047{1048 return vertex ? vertex->id : isl_size_error;1049}1050 1051/* Return the activity domain of the vertex "vertex".1052 */1053__isl_give isl_basic_set *isl_vertex_get_domain(__isl_keep isl_vertex *vertex)1054{1055 struct isl_vertex *v;1056 1057 if (!vertex)1058 return NULL;1059 1060 v = &vertex->vertices->v[vertex->id];1061 if (!v->dom) {1062 v->dom = isl_basic_set_copy(v->vertex);1063 v->dom = isl_basic_set_params(v->dom);1064 v->dom = isl_basic_set_set_integral(v->dom);1065 }1066 1067 return isl_basic_set_copy(v->dom);1068}1069 1070/* Return a multiple quasi-affine expression describing the vertex "vertex"1071 * in terms of the parameters,1072 */1073__isl_give isl_multi_aff *isl_vertex_get_expr(__isl_keep isl_vertex *vertex)1074{1075 struct isl_vertex *v;1076 isl_basic_set *bset;1077 1078 if (!vertex)1079 return NULL;1080 1081 v = &vertex->vertices->v[vertex->id];1082 1083 bset = isl_basic_set_copy(v->vertex);1084 return isl_multi_aff_from_basic_set_equalities(bset);1085}1086 1087static __isl_give isl_vertex *isl_vertex_alloc(__isl_take isl_vertices *vertices,1088 int id)1089{1090 isl_ctx *ctx;1091 isl_vertex *vertex;1092 1093 if (!vertices)1094 return NULL;1095 1096 ctx = isl_vertices_get_ctx(vertices);1097 vertex = isl_alloc_type(ctx, isl_vertex);1098 if (!vertex)1099 goto error;1100 1101 vertex->vertices = vertices;1102 vertex->id = id;1103 1104 return vertex;1105error:1106 isl_vertices_free(vertices);1107 return NULL;1108}1109 1110__isl_null isl_vertex *isl_vertex_free(__isl_take isl_vertex *vertex)1111{1112 if (!vertex)1113 return NULL;1114 isl_vertices_free(vertex->vertices);1115 free(vertex);1116 1117 return NULL;1118}1119 1120isl_ctx *isl_cell_get_ctx(__isl_keep isl_cell *cell)1121{1122 return cell ? cell->dom->ctx : NULL;1123}1124 1125__isl_give isl_basic_set *isl_cell_get_domain(__isl_keep isl_cell *cell)1126{1127 return cell ? isl_basic_set_copy(cell->dom) : NULL;1128}1129 1130static __isl_give isl_cell *isl_cell_alloc(__isl_take isl_vertices *vertices,1131 __isl_take isl_basic_set *dom, int id)1132{1133 int i;1134 isl_cell *cell = NULL;1135 1136 if (!vertices || !dom)1137 goto error;1138 1139 cell = isl_calloc_type(dom->ctx, isl_cell);1140 if (!cell)1141 goto error;1142 1143 cell->n_vertices = vertices->c[id].n_vertices;1144 cell->ids = isl_alloc_array(dom->ctx, int, cell->n_vertices);1145 if (cell->n_vertices && !cell->ids)1146 goto error;1147 for (i = 0; i < cell->n_vertices; ++i)1148 cell->ids[i] = vertices->c[id].vertices[i];1149 cell->vertices = vertices;1150 cell->dom = dom;1151 1152 return cell;1153error:1154 isl_cell_free(cell);1155 isl_vertices_free(vertices);1156 isl_basic_set_free(dom);1157 return NULL;1158}1159 1160__isl_null isl_cell *isl_cell_free(__isl_take isl_cell *cell)1161{1162 if (!cell)1163 return NULL;1164 1165 isl_vertices_free(cell->vertices);1166 free(cell->ids);1167 isl_basic_set_free(cell->dom);1168 free(cell);1169 1170 return NULL;1171}1172 1173/* Create a tableau of the cone obtained by first homogenizing the given1174 * polytope and then making all inequalities strict by setting the1175 * constant term to -1.1176 */1177static struct isl_tab *tab_for_shifted_cone(__isl_keep isl_basic_set *bset)1178{1179 int i;1180 isl_vec *c = NULL;1181 struct isl_tab *tab;1182 isl_size total;1183 1184 total = isl_basic_set_dim(bset, isl_dim_all);1185 if (total < 0)1186 return NULL;1187 tab = isl_tab_alloc(bset->ctx, bset->n_eq + bset->n_ineq + 1,1188 1 + total, 0);1189 if (!tab)1190 return NULL;1191 tab->rational = ISL_F_ISSET(bset, ISL_BASIC_SET_RATIONAL);1192 if (ISL_F_ISSET(bset, ISL_BASIC_MAP_EMPTY)) {1193 if (isl_tab_mark_empty(tab) < 0)1194 goto error;1195 return tab;1196 }1197 1198 c = isl_vec_alloc(bset->ctx, 1 + 1 + total);1199 if (!c)1200 goto error;1201 1202 isl_int_set_si(c->el[0], 0);1203 for (i = 0; i < bset->n_eq; ++i) {1204 isl_seq_cpy(c->el + 1, bset->eq[i], c->size - 1);1205 if (isl_tab_add_eq(tab, c->el) < 0)1206 goto error;1207 }1208 1209 isl_int_set_si(c->el[0], -1);1210 for (i = 0; i < bset->n_ineq; ++i) {1211 isl_seq_cpy(c->el + 1, bset->ineq[i], c->size - 1);1212 if (isl_tab_add_ineq(tab, c->el) < 0)1213 goto error;1214 if (tab->empty) {1215 isl_vec_free(c);1216 return tab;1217 }1218 }1219 1220 isl_seq_clr(c->el + 1, c->size - 1);1221 isl_int_set_si(c->el[1], 1);1222 if (isl_tab_add_ineq(tab, c->el) < 0)1223 goto error;1224 1225 isl_vec_free(c);1226 return tab;1227error:1228 isl_vec_free(c);1229 isl_tab_free(tab);1230 return NULL;1231}1232 1233/* Compute an interior point of "bset" by selecting an interior1234 * point in homogeneous space and projecting the point back down.1235 */1236static __isl_give isl_vec *isl_basic_set_interior_point(1237 __isl_keep isl_basic_set *bset)1238{1239 isl_vec *vec;1240 struct isl_tab *tab;1241 1242 tab = tab_for_shifted_cone(bset);1243 vec = isl_tab_get_sample_value(tab);1244 isl_tab_free(tab);1245 if (!vec)1246 return NULL;1247 1248 isl_seq_cpy(vec->el, vec->el + 1, vec->size - 1);1249 vec->size--;1250 1251 return vec;1252}1253 1254/* Call "fn" on all chambers of the parametric polytope with the shared1255 * facets of neighboring chambers only appearing in one of the chambers.1256 *1257 * We pick an interior point from one of the chambers and then make1258 * all constraints that do not satisfy this point strict.1259 * For constraints that saturate the interior point, the sign1260 * of the first non-zero coefficient is used to determine which1261 * of the two (internal) constraints should be tightened.1262 */1263isl_stat isl_vertices_foreach_disjoint_cell(__isl_keep isl_vertices *vertices,1264 isl_stat (*fn)(__isl_take isl_cell *cell, void *user), void *user)1265{1266 int i;1267 isl_vec *vec;1268 isl_cell *cell;1269 1270 if (!vertices)1271 return isl_stat_error;1272 1273 if (vertices->n_chambers == 0)1274 return isl_stat_ok;1275 1276 if (vertices->n_chambers == 1) {1277 isl_basic_set *dom = isl_basic_set_copy(vertices->c[0].dom);1278 dom = isl_basic_set_set_integral(dom);1279 cell = isl_cell_alloc(isl_vertices_copy(vertices), dom, 0);1280 if (!cell)1281 return isl_stat_error;1282 return fn(cell, user);1283 }1284 1285 vec = isl_basic_set_interior_point(vertices->c[0].dom);1286 if (!vec)1287 return isl_stat_error;1288 1289 for (i = 0; i < vertices->n_chambers; ++i) {1290 int r;1291 isl_basic_set *dom = isl_basic_set_copy(vertices->c[i].dom);1292 if (i)1293 dom = isl_basic_set_tighten_outward(dom, vec);1294 dom = isl_basic_set_set_integral(dom);1295 cell = isl_cell_alloc(isl_vertices_copy(vertices), dom, i);1296 if (!cell)1297 goto error;1298 r = fn(cell, user);1299 if (r < 0)1300 goto error;1301 }1302 1303 isl_vec_free(vec);1304 1305 return isl_stat_ok;1306error:1307 isl_vec_free(vec);1308 return isl_stat_error;1309}1310 1311isl_stat isl_vertices_foreach_cell(__isl_keep isl_vertices *vertices,1312 isl_stat (*fn)(__isl_take isl_cell *cell, void *user), void *user)1313{1314 int i;1315 isl_cell *cell;1316 1317 if (!vertices)1318 return isl_stat_error;1319 1320 if (vertices->n_chambers == 0)1321 return isl_stat_ok;1322 1323 for (i = 0; i < vertices->n_chambers; ++i) {1324 isl_stat r;1325 isl_basic_set *dom = isl_basic_set_copy(vertices->c[i].dom);1326 1327 cell = isl_cell_alloc(isl_vertices_copy(vertices), dom, i);1328 if (!cell)1329 return isl_stat_error;1330 1331 r = fn(cell, user);1332 if (r < 0)1333 return isl_stat_error;1334 }1335 1336 return isl_stat_ok;1337}1338 1339isl_stat isl_vertices_foreach_vertex(__isl_keep isl_vertices *vertices,1340 isl_stat (*fn)(__isl_take isl_vertex *vertex, void *user), void *user)1341{1342 int i;1343 isl_vertex *vertex;1344 1345 if (!vertices)1346 return isl_stat_error;1347 1348 if (vertices->n_vertices == 0)1349 return isl_stat_ok;1350 1351 for (i = 0; i < vertices->n_vertices; ++i) {1352 isl_stat r;1353 1354 vertex = isl_vertex_alloc(isl_vertices_copy(vertices), i);1355 if (!vertex)1356 return isl_stat_error;1357 1358 r = fn(vertex, user);1359 if (r < 0)1360 return isl_stat_error;1361 }1362 1363 return isl_stat_ok;1364}1365 1366isl_stat isl_cell_foreach_vertex(__isl_keep isl_cell *cell,1367 isl_stat (*fn)(__isl_take isl_vertex *vertex, void *user), void *user)1368{1369 int i;1370 isl_vertex *vertex;1371 1372 if (!cell)1373 return isl_stat_error;1374 1375 if (cell->n_vertices == 0)1376 return isl_stat_ok;1377 1378 for (i = 0; i < cell->n_vertices; ++i) {1379 isl_stat r;1380 1381 vertex = isl_vertex_alloc(isl_vertices_copy(cell->vertices),1382 cell->ids[i]);1383 if (!vertex)1384 return isl_stat_error;1385 1386 r = fn(vertex, user);1387 if (r < 0)1388 return isl_stat_error;1389 }1390 1391 return isl_stat_ok;1392}1393 1394isl_ctx *isl_vertices_get_ctx(__isl_keep isl_vertices *vertices)1395{1396 return vertices ? vertices->bset->ctx : NULL;1397}1398 1399isl_size isl_vertices_get_n_vertices(__isl_keep isl_vertices *vertices)1400{1401 return vertices ? vertices->n_vertices : isl_size_error;1402}1403 1404__isl_give isl_vertices *isl_morph_vertices(__isl_take isl_morph *morph,1405 __isl_take isl_vertices *vertices)1406{1407 int i;1408 isl_morph *param_morph = NULL;1409 1410 if (!morph || !vertices)1411 goto error;1412 1413 isl_assert(vertices->bset->ctx, vertices->ref == 1, goto error);1414 1415 param_morph = isl_morph_copy(morph);1416 param_morph = isl_morph_dom_params(param_morph);1417 param_morph = isl_morph_ran_params(param_morph);1418 1419 for (i = 0; i < vertices->n_vertices; ++i) {1420 vertices->v[i].dom = isl_morph_basic_set(1421 isl_morph_copy(param_morph), vertices->v[i].dom);1422 vertices->v[i].vertex = isl_morph_basic_set(1423 isl_morph_copy(morph), vertices->v[i].vertex);1424 if (!vertices->v[i].vertex)1425 goto error;1426 }1427 1428 for (i = 0; i < vertices->n_chambers; ++i) {1429 vertices->c[i].dom = isl_morph_basic_set(1430 isl_morph_copy(param_morph), vertices->c[i].dom);1431 if (!vertices->c[i].dom)1432 goto error;1433 }1434 1435 isl_morph_free(param_morph);1436 isl_morph_free(morph);1437 return vertices;1438error:1439 isl_morph_free(param_morph);1440 isl_morph_free(morph);1441 isl_vertices_free(vertices);1442 return NULL;1443}1444 1445/* Construct a simplex isl_cell spanned by the vertices with indices in1446 * "simplex_ids" and "other_ids" and call "fn" on this isl_cell.1447 */1448static isl_stat call_on_simplex(__isl_keep isl_cell *cell,1449 int *simplex_ids, int n_simplex, int *other_ids, int n_other,1450 isl_stat (*fn)(__isl_take isl_cell *simplex, void *user), void *user)1451{1452 int i;1453 isl_ctx *ctx;1454 struct isl_cell *simplex;1455 1456 ctx = isl_cell_get_ctx(cell);1457 1458 simplex = isl_calloc_type(ctx, struct isl_cell);1459 if (!simplex)1460 return isl_stat_error;1461 simplex->vertices = isl_vertices_copy(cell->vertices);1462 if (!simplex->vertices)1463 goto error;1464 simplex->dom = isl_basic_set_copy(cell->dom);1465 if (!simplex->dom)1466 goto error;1467 simplex->n_vertices = n_simplex + n_other;1468 simplex->ids = isl_alloc_array(ctx, int, simplex->n_vertices);1469 if (!simplex->ids)1470 goto error;1471 1472 for (i = 0; i < n_simplex; ++i)1473 simplex->ids[i] = simplex_ids[i];1474 for (i = 0; i < n_other; ++i)1475 simplex->ids[n_simplex + i] = other_ids[i];1476 1477 return fn(simplex, user);1478error:1479 isl_cell_free(simplex);1480 return isl_stat_error;1481}1482 1483/* Check whether the parametric vertex described by "vertex"1484 * lies on the facet corresponding to constraint "facet" of "bset".1485 * The isl_vec "v" is a temporary vector than can be used by this function.1486 *1487 * We eliminate the variables from the facet constraint using the1488 * equalities defining the vertex and check if the result is identical1489 * to zero.1490 *1491 * It would probably be better to keep track of the constraints defining1492 * a vertex during the vertex construction so that we could simply look1493 * it up here.1494 */1495static int vertex_on_facet(__isl_keep isl_basic_set *vertex,1496 __isl_keep isl_basic_set *bset, int facet, __isl_keep isl_vec *v)1497{1498 int i;1499 isl_int m;1500 1501 isl_seq_cpy(v->el, bset->ineq[facet], v->size);1502 1503 isl_int_init(m);1504 for (i = 0; i < vertex->n_eq; ++i) {1505 int k = isl_seq_last_non_zero(vertex->eq[i], v->size);1506 isl_seq_elim(v->el, vertex->eq[i], k, v->size, &m);1507 }1508 isl_int_clear(m);1509 1510 return isl_seq_first_non_zero(v->el, v->size) == -1;1511}1512 1513/* Triangulate the polytope spanned by the vertices with ids1514 * in "simplex_ids" and "other_ids" and call "fn" on each of1515 * the resulting simplices.1516 * If the input polytope is already a simplex, we simply call "fn".1517 * Otherwise, we pick a point from "other_ids" and add it to "simplex_ids".1518 * Then we consider each facet of "bset" that does not contain the point1519 * we just picked, but does contain some of the other points in "other_ids"1520 * and call ourselves recursively on the polytope spanned by the new1521 * "simplex_ids" and those points in "other_ids" that lie on the facet.1522 */1523static isl_stat triangulate(__isl_keep isl_cell *cell, __isl_keep isl_vec *v,1524 int *simplex_ids, int n_simplex, int *other_ids, int n_other,1525 isl_stat (*fn)(__isl_take isl_cell *simplex, void *user), void *user)1526{1527 int i, j, k;1528 isl_size d, nparam;1529 int *ids;1530 isl_ctx *ctx;1531 isl_basic_set *vertex;1532 isl_basic_set *bset;1533 1534 ctx = isl_cell_get_ctx(cell);1535 d = isl_basic_set_dim(cell->vertices->bset, isl_dim_set);1536 nparam = isl_basic_set_dim(cell->vertices->bset, isl_dim_param);1537 if (d < 0 || nparam < 0)1538 return isl_stat_error;1539 1540 if (n_simplex + n_other == d + 1)1541 return call_on_simplex(cell, simplex_ids, n_simplex,1542 other_ids, n_other, fn, user);1543 1544 simplex_ids[n_simplex] = other_ids[0];1545 vertex = cell->vertices->v[other_ids[0]].vertex;1546 bset = cell->vertices->bset;1547 1548 ids = isl_alloc_array(ctx, int, n_other - 1);1549 if (!ids)1550 goto error;1551 for (i = 0; i < bset->n_ineq; ++i) {1552 if (isl_seq_first_non_zero(bset->ineq[i] + 1 + nparam, d) == -1)1553 continue;1554 if (vertex_on_facet(vertex, bset, i, v))1555 continue;1556 1557 for (j = 1, k = 0; j < n_other; ++j) {1558 isl_basic_set *ov;1559 ov = cell->vertices->v[other_ids[j]].vertex;1560 if (vertex_on_facet(ov, bset, i, v))1561 ids[k++] = other_ids[j];1562 }1563 if (k == 0)1564 continue;1565 1566 if (triangulate(cell, v, simplex_ids, n_simplex + 1,1567 ids, k, fn, user) < 0)1568 goto error;1569 }1570 free(ids);1571 1572 return isl_stat_ok;1573error:1574 free(ids);1575 return isl_stat_error;1576}1577 1578/* Triangulate the given cell and call "fn" on each of the resulting1579 * simplices.1580 */1581isl_stat isl_cell_foreach_simplex(__isl_take isl_cell *cell,1582 isl_stat (*fn)(__isl_take isl_cell *simplex, void *user), void *user)1583{1584 isl_size d, total;1585 isl_stat r;1586 isl_ctx *ctx;1587 isl_vec *v = NULL;1588 int *simplex_ids = NULL;1589 1590 if (!cell)1591 return isl_stat_error;1592 1593 d = isl_basic_set_dim(cell->vertices->bset, isl_dim_set);1594 total = isl_basic_set_dim(cell->vertices->bset, isl_dim_all);1595 if (d < 0 || total < 0)1596 return isl_stat_error;1597 1598 if (cell->n_vertices == d + 1)1599 return fn(cell, user);1600 1601 ctx = isl_cell_get_ctx(cell);1602 simplex_ids = isl_alloc_array(ctx, int, d + 1);1603 if (!simplex_ids)1604 goto error;1605 1606 v = isl_vec_alloc(ctx, 1 + total);1607 if (!v)1608 goto error;1609 1610 r = triangulate(cell, v, simplex_ids, 0,1611 cell->ids, cell->n_vertices, fn, user);1612 1613 isl_vec_free(v);1614 free(simplex_ids);1615 1616 isl_cell_free(cell);1617 1618 return r;1619error:1620 free(simplex_ids);1621 isl_vec_free(v);1622 isl_cell_free(cell);1623 return isl_stat_error;1624}1625