2 * Copyright 2010 INRIA Saclay
4 * Use of this software is governed by the GNU LGPLv2.1 license
6 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
7 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
14 #include <isl_map_private.h>
15 #include <isl_dim_private.h>
16 #include <isl_morph.h>
17 #include <isl_vertices_private.h>
18 #include <isl_mat_private.h>
24 static __isl_give isl_vertices
*compute_chambers(__isl_take isl_basic_set
*bset
,
25 __isl_take isl_vertices
*vertices
);
27 __isl_give isl_vertices
*isl_vertices_copy(__isl_keep isl_vertices
*vertices
)
36 void isl_vertices_free(__isl_take isl_vertices
*vertices
)
43 if (--vertices
->ref
> 0)
46 for (i
= 0; i
< vertices
->n_vertices
; ++i
) {
47 isl_basic_set_free(vertices
->v
[i
].vertex
);
48 isl_basic_set_free(vertices
->v
[i
].dom
);
52 for (i
= 0; i
< vertices
->n_chambers
; ++i
) {
53 free(vertices
->c
[i
].vertices
);
54 isl_basic_set_free(vertices
->c
[i
].dom
);
58 isl_ctx_deref(vertices
->ctx
);
62 struct isl_vertex_list
{
64 struct isl_vertex_list
*next
;
67 static void free_vertex_list(struct isl_vertex_list
*list
)
69 struct isl_vertex_list
*next
;
71 for (; list
; list
= next
) {
73 isl_basic_set_free(list
->v
.vertex
);
74 isl_basic_set_free(list
->v
.dom
);
79 static __isl_give isl_vertices
*vertices_from_list(__isl_keep isl_basic_set
*bset
,
80 int n_vertices
, struct isl_vertex_list
*list
)
83 struct isl_vertex_list
*next
;
84 isl_vertices
*vertices
;
86 vertices
= isl_calloc_type(bset
->ctx
, isl_vertices
);
89 vertices
->ctx
= bset
->ctx
;
90 isl_ctx_ref(bset
->ctx
);
92 vertices
->v
= isl_alloc_array(bset
->ctx
, struct isl_vertex
, n_vertices
);
95 vertices
->n_vertices
= n_vertices
;
97 for (i
= 0; list
; list
= next
, i
++) {
99 vertices
->v
[i
] = list
->v
;
106 free_vertex_list(list
);
110 /* Prepend a vertex to the linked list "list" based on the equalities in "tab".
112 static int add_vertex(struct isl_vertex_list
**list
,
113 __isl_keep isl_basic_set
*bset
, struct isl_tab
*tab
)
117 struct isl_vertex_list
*v
= NULL
;
119 if (isl_tab_detect_implicit_equalities(tab
) < 0)
122 nvar
= isl_basic_set_dim(bset
, isl_dim_set
);
123 nparam
= isl_basic_set_dim(bset
, isl_dim_param
);
125 v
= isl_calloc_type(tab
->mat
->ctx
, struct isl_vertex_list
);
129 v
->v
.vertex
= isl_basic_set_copy(bset
);
130 v
->v
.vertex
= isl_basic_set_cow(v
->v
.vertex
);
131 v
->v
.vertex
= isl_basic_set_update_from_tab(v
->v
.vertex
, tab
);
132 v
->v
.vertex
= isl_basic_set_simplify(v
->v
.vertex
);
133 v
->v
.vertex
= isl_basic_set_finalize(v
->v
.vertex
);
136 isl_assert(bset
->ctx
, v
->v
.vertex
->n_eq
>= nvar
, goto error
);
137 v
->v
.dom
= isl_basic_set_copy(v
->v
.vertex
);
138 v
->v
.dom
= isl_basic_set_project_out(v
->v
.dom
, isl_dim_set
, 0, nvar
);
151 /* Compute the parametric vertices and the chamber decomposition
152 * of an empty parametric polytope.
154 static __isl_give isl_vertices
*vertices_empty(__isl_keep isl_basic_set
*bset
)
156 isl_vertices
*vertices
;
162 nparam
= isl_basic_set_dim(bset
, isl_dim_param
);
164 vertices
= isl_calloc_type(bset
->ctx
, isl_vertices
);
167 vertices
->ctx
= bset
->ctx
;
168 isl_ctx_ref(bset
->ctx
);
171 vertices
->n_vertices
= 0;
172 vertices
->n_chambers
= 0;
177 /* Compute the parametric vertices and the chamber decomposition
178 * of the parametric polytope defined using the same constraints
179 * as "bset" in the 0D case.
180 * There is exactly one 0D vertex and a single chamber containing
183 static __isl_give isl_vertices
*vertices_0D(__isl_keep isl_basic_set
*bset
)
185 isl_vertices
*vertices
;
191 nparam
= isl_basic_set_dim(bset
, isl_dim_param
);
193 vertices
= isl_calloc_type(bset
->ctx
, isl_vertices
);
196 vertices
->ctx
= bset
->ctx
;
197 isl_ctx_ref(bset
->ctx
);
200 vertices
->v
= isl_calloc_array(bset
->ctx
, struct isl_vertex
, 1);
203 vertices
->n_vertices
= 1;
204 vertices
->v
[0].vertex
= isl_basic_set_copy(bset
);
205 if (!vertices
->v
[0].vertex
)
208 vertices
->c
= isl_calloc_array(bset
->ctx
, struct isl_chamber
, 1);
211 vertices
->n_chambers
= 1;
212 vertices
->c
[0].n_vertices
= 1;
213 vertices
->c
[0].vertices
= isl_calloc_array(bset
->ctx
, int, 1);
214 if (!vertices
->c
[0].vertices
)
216 vertices
->c
[0].dom
= isl_basic_set_copy(bset
);
217 if (!vertices
->c
[0].dom
)
222 isl_vertices_free(vertices
);
226 static int isl_mat_rank(__isl_keep isl_mat
*mat
)
231 H
= isl_mat_left_hermite(isl_mat_copy(mat
), 0, NULL
, NULL
);
235 for (col
= 0; col
< H
->n_col
; ++col
) {
236 for (row
= 0; row
< H
->n_row
; ++row
)
237 if (!isl_int_is_zero(H
->row
[row
][col
]))
248 /* Is the row pointed to by "f" linearly independent of the "n" first
251 static int is_independent(__isl_keep isl_mat
*facets
, int n
, isl_int
*f
)
255 if (isl_seq_first_non_zero(f
, facets
->n_col
) < 0)
258 isl_seq_cpy(facets
->row
[n
], f
, facets
->n_col
);
259 facets
->n_row
= n
+ 1;
260 rank
= isl_mat_rank(facets
);
264 return rank
== n
+ 1;
267 /* Check whether we can select constraint "level", given the current selection
268 * reflected by facets in "tab", the rows of "facets" and the earlier
269 * "selected" elements of "selection".
271 * If the constraint is (strictly) redundant in the tableau, selecting it would
272 * result in an empty tableau, so it can't be selected.
273 * If the set variable part of the constraint is not linearly indepedent
274 * of the set variable parts of the already selected constraints,
275 * the constraint cannot be selected.
276 * If selecting the constraint results in an empty tableau, the constraint
277 * cannot be selected.
278 * Finally, if selecting the constraint results in some explicitly
279 * deselected constraints turning into equalities, then the corresponding
280 * vertices have already been generated, so the constraint cannot be selected.
282 static int can_select(__isl_keep isl_basic_set
*bset
, int level
,
283 struct isl_tab
*tab
, __isl_keep isl_mat
*facets
, int selected
,
289 struct isl_tab_undo
*snap
;
291 if (isl_tab_is_redundant(tab
, level
))
294 ovar
= isl_dim_offset(bset
->dim
, isl_dim_set
);
296 indep
= is_independent(facets
, selected
, bset
->ineq
[level
] + 1 + ovar
);
302 snap
= isl_tab_snap(tab
);
303 if (isl_tab_select_facet(tab
, level
) < 0)
307 if (isl_tab_rollback(tab
, snap
) < 0)
312 for (i
= 0; i
< level
; ++i
) {
315 if (selection
[i
] != DESELECTED
)
318 if (isl_tab_is_equality(tab
, i
))
320 else if (isl_tab_is_redundant(tab
, i
))
323 sgn
= isl_tab_sign_of_max(tab
, i
);
327 if (isl_tab_rollback(tab
, snap
) < 0)
336 /* Compute the parametric vertices and the chamber decomposition
337 * of a parametric polytope that is not full-dimensional.
339 * Simply map the parametric polytope to a lower dimensional space
340 * and map the resulting vertices back.
342 static __isl_give isl_vertices
*lower_dim_vertices(
343 __isl_keep isl_basic_set
*bset
)
346 isl_vertices
*vertices
;
348 bset
= isl_basic_set_copy(bset
);
349 morph
= isl_basic_set_full_compression(bset
);
350 bset
= isl_morph_basic_set(isl_morph_copy(morph
), bset
);
352 vertices
= isl_basic_set_compute_vertices(bset
);
353 isl_basic_set_free(bset
);
355 morph
= isl_morph_inverse(morph
);
357 vertices
= isl_morph_vertices(morph
, vertices
);
362 /* Compute the parametric vertices and the chamber decomposition
363 * of the parametric polytope defined using the same constraints
364 * as "bset". "bset" is assumed to have no existentially quantified
367 * The vertices themselves are computed in a fairly simplistic way.
368 * We simply run through all combinations of d constraints,
369 * with d the number of set variables, and check if those d constraints
370 * define a vertex. To avoid the generation of duplicate vertices,
371 * which we may happen if a vertex is defined by more that d constraints,
372 * we make sure we only generate the vertex for the d constraints with
375 * We set up a tableau and keep track of which facets have been
376 * selected. The tableau is marked strict_redundant so that we can be
377 * sure that any constraint that is marked redundant (and that is not
378 * also marked zero) is not an equality.
379 * If a constraint is marked DESELECTED, it means the constraint was
380 * SELECTED before (in combination with the same selection of earlier
381 * constraints). If such a deselected constraint turns out to be an
382 * equality, then any vertex that may still be found with the current
383 * selection has already been generated when the constraint was selected.
384 * A constraint is marked UNSELECTED when there is no way selecting
385 * the constraint could lead to a vertex (in combination with the current
386 * selection of earlier constraints).
388 * The set variable coefficients of the selected constraints are stored
389 * in the facets matrix.
391 __isl_give isl_vertices
*isl_basic_set_compute_vertices(
392 __isl_keep isl_basic_set
*bset
)
400 struct isl_tab_undo
**snap
;
402 struct isl_vertex_list
*list
= NULL
;
404 isl_vertices
*vertices
;
409 if (isl_basic_set_fast_is_empty(bset
))
410 return vertices_empty(bset
);
413 return lower_dim_vertices(bset
);
415 isl_assert(bset
->ctx
, isl_basic_set_dim(bset
, isl_dim_div
) == 0,
418 if (isl_basic_set_dim(bset
, isl_dim_set
) == 0)
419 return vertices_0D(bset
);
421 nvar
= isl_basic_set_dim(bset
, isl_dim_set
);
423 bset
= isl_basic_set_copy(bset
);
424 bset
= isl_basic_set_set_rational(bset
);
428 tab
= isl_tab_from_basic_set(bset
);
431 tab
->strict_redundant
= 1;
434 vertices
= vertices_empty(bset
);
435 isl_basic_set_free(bset
);
440 selection
= isl_alloc_array(bset
->ctx
, int, bset
->n_ineq
);
441 snap
= isl_alloc_array(bset
->ctx
, struct isl_tab_undo
*, bset
->n_ineq
);
442 facets
= isl_mat_alloc(bset
->ctx
, nvar
, nvar
);
443 if (!selection
|| !snap
|| !facets
)
451 if (level
>= bset
->n_ineq
||
452 (!init
&& selection
[level
] != SELECTED
)) {
459 snap
[level
] = isl_tab_snap(tab
);
460 ok
= can_select(bset
, level
, tab
, facets
, selected
,
465 selection
[level
] = SELECTED
;
468 selection
[level
] = UNSELECTED
;
470 selection
[level
] = DESELECTED
;
472 if (isl_tab_rollback(tab
, snap
[level
]) < 0)
475 if (selected
== nvar
) {
476 if (tab
->n_dead
== nvar
) {
477 if (add_vertex(&list
, bset
, tab
) < 0)
488 isl_mat_free(facets
);
494 vertices
= vertices_from_list(bset
, n_vertices
, list
);
496 vertices
= compute_chambers(bset
, vertices
);
500 isl_mat_free(facets
);
504 isl_basic_set_free(bset
);
508 struct isl_chamber_list
{
509 struct isl_chamber c
;
510 struct isl_chamber_list
*next
;
513 static void free_chamber_list(struct isl_chamber_list
*list
)
515 struct isl_chamber_list
*next
;
517 for (; list
; list
= next
) {
519 isl_basic_set_free(list
->c
.dom
);
520 free(list
->c
.vertices
);
525 /* Check whether the basic set "bset" is a superset of the basic set described
526 * by "tab", i.e., check whether all constraints of "bset" are redundant.
528 static int bset_covers_tab(__isl_keep isl_basic_set
*bset
, struct isl_tab
*tab
)
535 for (i
= 0; i
< bset
->n_ineq
; ++i
) {
536 enum isl_ineq_type type
= isl_tab_ineq_type(tab
, bset
->ineq
[i
]);
538 case isl_ineq_error
: return -1;
539 case isl_ineq_redundant
: continue;
547 static __isl_give isl_vertices
*vertices_add_chambers(
548 __isl_take isl_vertices
*vertices
, int n_chambers
,
549 struct isl_chamber_list
*list
)
552 struct isl_chamber_list
*next
;
554 vertices
->c
= isl_alloc_array(vertices
->ctx
, struct isl_chamber
, n_chambers
);
557 vertices
->n_chambers
= n_chambers
;
559 for (i
= 0; list
; list
= next
, i
++) {
561 vertices
->c
[i
] = list
->c
;
567 isl_vertices_free(vertices
);
568 free_chamber_list(list
);
572 /* Can "tab" be intersected with "bset" without resulting in
573 * a lower-dimensional set.
575 static int can_intersect(struct isl_tab
*tab
, __isl_keep isl_basic_set
*bset
)
578 struct isl_tab_undo
*snap
;
580 if (isl_tab_extend_cons(tab
, bset
->n_ineq
) < 0)
583 snap
= isl_tab_snap(tab
);
585 for (i
= 0; i
< bset
->n_ineq
; ++i
) {
586 if (isl_tab_ineq_type(tab
, bset
->ineq
[i
]) == isl_ineq_redundant
)
588 if (isl_tab_add_ineq(tab
, bset
->ineq
[i
]) < 0)
592 if (isl_tab_detect_implicit_equalities(tab
) < 0)
595 if (isl_tab_rollback(tab
, snap
) < 0)
603 static int add_chamber(struct isl_chamber_list
**list
,
604 __isl_keep isl_vertices
*vertices
, struct isl_tab
*tab
, int *selection
)
609 struct isl_tab_undo
*snap
;
610 struct isl_chamber_list
*c
= NULL
;
612 for (i
= 0; i
< vertices
->n_vertices
; ++i
)
616 snap
= isl_tab_snap(tab
);
618 for (i
= 0; i
< tab
->n_con
&& tab
->con
[i
].frozen
; ++i
)
619 tab
->con
[i
].frozen
= 0;
622 if (isl_tab_detect_redundant(tab
) < 0)
625 c
= isl_calloc_type(tab
->mat
->ctx
, struct isl_chamber_list
);
628 c
->c
.vertices
= isl_alloc_array(tab
->mat
->ctx
, int, n_vertices
);
631 c
->c
.dom
= isl_basic_set_from_basic_map(isl_basic_map_copy(tab
->bmap
));
632 c
->c
.dom
= isl_basic_set_set_rational(c
->c
.dom
);
633 c
->c
.dom
= isl_basic_set_cow(c
->c
.dom
);
634 c
->c
.dom
= isl_basic_set_update_from_tab(c
->c
.dom
, tab
);
635 c
->c
.dom
= isl_basic_set_simplify(c
->c
.dom
);
636 c
->c
.dom
= isl_basic_set_finalize(c
->c
.dom
);
640 c
->c
.n_vertices
= n_vertices
;
642 for (i
= 0, j
= 0; i
< vertices
->n_vertices
; ++i
)
644 c
->c
.vertices
[j
] = i
;
651 for (i
= 0; i
< n_frozen
; ++i
)
652 tab
->con
[i
].frozen
= 1;
654 if (isl_tab_rollback(tab
, snap
) < 0)
659 free_chamber_list(c
);
663 struct isl_facet_todo
{
664 struct isl_tab
*tab
; /* A tableau representation of the facet */
665 isl_basic_set
*bset
; /* A normalized basic set representation */
666 isl_vec
*constraint
; /* Constraint pointing to the other side */
667 struct isl_facet_todo
*next
;
670 static void free_todo(struct isl_facet_todo
*todo
)
673 struct isl_facet_todo
*next
= todo
->next
;
675 isl_tab_free(todo
->tab
);
676 isl_basic_set_free(todo
->bset
);
677 isl_vec_free(todo
->constraint
);
684 static struct isl_facet_todo
*create_todo(struct isl_tab
*tab
, int con
)
688 struct isl_tab_undo
*snap
;
689 struct isl_facet_todo
*todo
;
691 snap
= isl_tab_snap(tab
);
693 for (i
= 0; i
< tab
->n_con
&& tab
->con
[i
].frozen
; ++i
)
694 tab
->con
[i
].frozen
= 0;
697 if (isl_tab_detect_redundant(tab
) < 0)
700 todo
= isl_calloc_type(tab
->mat
->ctx
, struct isl_facet_todo
);
704 todo
->constraint
= isl_vec_alloc(tab
->mat
->ctx
, 1 + tab
->n_var
);
705 if (!todo
->constraint
)
707 isl_seq_neg(todo
->constraint
->el
, tab
->bmap
->ineq
[con
], 1 + tab
->n_var
);
708 todo
->bset
= isl_basic_set_from_basic_map(isl_basic_map_copy(tab
->bmap
));
709 todo
->bset
= isl_basic_set_set_rational(todo
->bset
);
710 todo
->bset
= isl_basic_set_cow(todo
->bset
);
711 todo
->bset
= isl_basic_set_update_from_tab(todo
->bset
, tab
);
712 todo
->bset
= isl_basic_set_simplify(todo
->bset
);
713 todo
->bset
= isl_basic_set_sort_constraints(todo
->bset
);
716 ISL_F_SET(todo
->bset
, ISL_BASIC_SET_NORMALIZED
);
717 todo
->tab
= isl_tab_dup(tab
);
721 for (i
= 0; i
< n_frozen
; ++i
)
722 tab
->con
[i
].frozen
= 1;
724 if (isl_tab_rollback(tab
, snap
) < 0)
733 /* Create todo items for all interior facets of the chamber represented
734 * by "tab" and collect them in "next".
736 static int init_todo(struct isl_facet_todo
**next
, struct isl_tab
*tab
)
739 struct isl_tab_undo
*snap
;
740 struct isl_facet_todo
*todo
;
742 snap
= isl_tab_snap(tab
);
744 for (i
= 0; i
< tab
->n_con
; ++i
) {
745 if (tab
->con
[i
].frozen
)
747 if (tab
->con
[i
].is_redundant
)
750 if (isl_tab_select_facet(tab
, i
) < 0)
753 todo
= create_todo(tab
, i
);
760 if (isl_tab_rollback(tab
, snap
) < 0)
767 /* Does the linked list contain a todo item that is the opposite of "todo".
768 * If so, return 1 and remove the opposite todo item.
770 static int has_opposite(struct isl_facet_todo
*todo
,
771 struct isl_facet_todo
**list
)
773 for (; *list
; list
= &(*list
)->next
) {
775 eq
= isl_basic_set_fast_is_equal(todo
->bset
, (*list
)->bset
);
790 /* Create todo items for all interior facets of the chamber represented
791 * by "tab" and collect them in first->next, taking care to cancel
792 * opposite todo items.
794 static int update_todo(struct isl_facet_todo
*first
, struct isl_tab
*tab
)
797 struct isl_tab_undo
*snap
;
798 struct isl_facet_todo
*todo
;
800 snap
= isl_tab_snap(tab
);
802 for (i
= 0; i
< tab
->n_con
; ++i
) {
805 if (tab
->con
[i
].frozen
)
807 if (tab
->con
[i
].is_redundant
)
810 if (isl_tab_select_facet(tab
, i
) < 0)
813 todo
= create_todo(tab
, i
);
817 drop
= has_opposite(todo
, &first
->next
);
824 todo
->next
= first
->next
;
828 if (isl_tab_rollback(tab
, snap
) < 0)
835 /* Compute the chamber decomposition of the parametric polytope respresented
836 * by "bset" given the parametric vertices and their activity domains.
838 * We are only interested in full-dimensional chambers.
839 * Each of these chambers is the intersection of the activity domains of
840 * one or more vertices and the union of all chambers is equal to the
841 * projection of the entire parametric polytope onto the parameter space.
843 * We first create an initial chamber by intersecting as many activity
844 * domains as possible without ending up with an empty or lower-dimensional
845 * set. As a minor optimization, we only consider those activity domains
846 * that contain some arbitrary point.
848 * For each of interior facets of the chamber, we construct a todo item,
849 * containing the facet and a constraint containing the other side of the facet,
850 * for constructing the chamber on the other side.
851 * While their are any todo items left, we pick a todo item and
852 * create the required chamber by intersecting all activity domains
853 * that contain the facet and have a full-dimensional intersection with
854 * the other side of the facet. For each of the interior facets, we
855 * again create todo items, taking care to cancel opposite todo items.
857 static __isl_give isl_vertices
*compute_chambers(__isl_take isl_basic_set
*bset
,
858 __isl_take isl_vertices
*vertices
)
861 isl_vec
*sample
= NULL
;
862 struct isl_tab
*tab
= NULL
;
863 struct isl_tab_undo
*snap
;
865 int *selection
= NULL
;
867 struct isl_chamber_list
*list
= NULL
;
868 struct isl_facet_todo
*todo
= NULL
;
870 if (!bset
|| !vertices
)
873 selection
= isl_alloc_array(vertices
->ctx
, int, vertices
->n_vertices
);
877 nvar
= isl_basic_set_dim(bset
, isl_dim_set
);
878 bset
= isl_basic_set_project_out(bset
, isl_dim_set
, 0, nvar
);
880 tab
= isl_tab_from_basic_set(bset
);
881 for (i
= 0; i
< bset
->n_ineq
; ++i
)
882 if (isl_tab_freeze_constraint(tab
, i
) < 0)
884 if (isl_tab_track_bset(tab
, bset
) < 0)
887 snap
= isl_tab_snap(tab
);
889 sample
= isl_tab_get_sample_value(tab
);
891 for (i
= 0; i
< vertices
->n_vertices
; ++i
) {
892 selection
[i
] = isl_basic_set_contains(vertices
->v
[i
].dom
, sample
);
893 if (selection
[i
] < 0)
897 selection
[i
] = can_intersect(tab
, vertices
->v
[i
].dom
);
898 if (selection
[i
] < 0)
902 if (isl_tab_detect_redundant(tab
) < 0)
905 if (add_chamber(&list
, vertices
, tab
, selection
) < 0)
909 if (init_todo(&todo
, tab
) < 0)
913 struct isl_facet_todo
*next
;
915 if (isl_tab_rollback(tab
, snap
) < 0)
918 if (isl_tab_add_ineq(tab
, todo
->constraint
->el
) < 0)
920 if (isl_tab_freeze_constraint(tab
, tab
->n_con
- 1) < 0)
923 for (i
= 0; i
< vertices
->n_vertices
; ++i
) {
924 selection
[i
] = bset_covers_tab(vertices
->v
[i
].dom
,
926 if (selection
[i
] < 0)
930 selection
[i
] = can_intersect(tab
, vertices
->v
[i
].dom
);
931 if (selection
[i
] < 0)
935 if (isl_tab_detect_redundant(tab
) < 0)
938 if (add_chamber(&list
, vertices
, tab
, selection
) < 0)
942 if (update_todo(todo
, tab
) < 0)
951 isl_vec_free(sample
);
956 vertices
= vertices_add_chambers(vertices
, n_chambers
, list
);
958 for (i
= 0; vertices
&& i
< vertices
->n_vertices
; ++i
) {
959 isl_basic_set_free(vertices
->v
[i
].dom
);
960 vertices
->v
[i
].dom
= NULL
;
965 free_chamber_list(list
);
967 isl_vec_free(sample
);
971 isl_basic_set_free(bset
);
972 isl_vertices_free(vertices
);
976 isl_ctx
*isl_vertex_get_ctx(__isl_keep isl_vertex
*vertex
)
978 return vertex
? vertex
->vertices
->ctx
: NULL
;
981 int isl_vertex_get_id(__isl_keep isl_vertex
*vertex
)
983 return vertex
? vertex
->id
: -1;
986 __isl_give isl_basic_set
*isl_vertex_get_domain(__isl_keep isl_vertex
*vertex
)
988 struct isl_vertex
*v
;
993 v
= &vertex
->vertices
->v
[vertex
->id
];
996 nvar
= isl_basic_set_dim(v
->vertex
, isl_dim_set
);
997 v
->dom
= isl_basic_set_copy(v
->vertex
);
998 v
->dom
= isl_basic_set_project_out(v
->dom
, isl_dim_set
, 0, nvar
);
1001 return isl_basic_set_copy(v
->dom
);
1004 __isl_give isl_basic_set
*isl_vertex_get_expr(__isl_keep isl_vertex
*vertex
)
1006 struct isl_vertex
*v
;
1011 v
= &vertex
->vertices
->v
[vertex
->id
];
1013 return isl_basic_set_copy(v
->vertex
);
1016 static __isl_give isl_vertex
*isl_vertex_alloc(__isl_take isl_vertices
*vertices
,
1024 vertex
= isl_alloc_type(vertices
->ctx
, isl_vertex
);
1028 vertex
->vertices
= vertices
;
1033 isl_vertices_free(vertices
);
1037 void isl_vertex_free(__isl_take isl_vertex
*vertex
)
1041 isl_vertices_free(vertex
->vertices
);
1045 __isl_give isl_basic_set
*isl_basic_set_set_integral(__isl_take isl_basic_set
*bset
)
1050 if (!ISL_F_ISSET(bset
, ISL_BASIC_MAP_RATIONAL
))
1053 bset
= isl_basic_set_cow(bset
);
1057 ISL_F_CLR(bset
, ISL_BASIC_MAP_RATIONAL
);
1059 return isl_basic_set_finalize(bset
);
1062 isl_ctx
*isl_cell_get_ctx(__isl_keep isl_cell
*cell
)
1064 return cell
? cell
->vertices
->ctx
: NULL
;
1067 __isl_give isl_basic_set
*isl_cell_get_domain(__isl_keep isl_cell
*cell
)
1069 struct isl_chamber
*c
;
1074 c
= &cell
->vertices
->c
[cell
->id
];
1076 return isl_basic_set_copy(c
->dom
);
1079 static __isl_give isl_cell
*isl_cell_alloc(__isl_take isl_vertices
*vertices
,
1080 __isl_take isl_basic_set
*dom
, int id
)
1084 if (!vertices
|| !dom
)
1087 cell
= isl_alloc_type(dom
->ctx
, isl_cell
);
1091 cell
->vertices
= vertices
;
1097 isl_vertices_free(vertices
);
1098 isl_basic_set_free(dom
);
1102 void isl_cell_free(__isl_take isl_cell
*cell
)
1107 isl_vertices_free(cell
->vertices
);
1108 isl_basic_set_free(cell
->dom
);
1112 /* Create a tableau of the cone obtained by first homogenizing the given
1113 * polytope and then making all inequalities strict by setting the
1114 * constant term to -1.
1116 static struct isl_tab
*tab_for_shifted_cone(__isl_keep isl_basic_set
*bset
)
1120 struct isl_tab
*tab
;
1124 tab
= isl_tab_alloc(bset
->ctx
, bset
->n_ineq
+ 1,
1125 1 + isl_basic_set_total_dim(bset
), 0);
1128 tab
->rational
= ISL_F_ISSET(bset
, ISL_BASIC_SET_RATIONAL
);
1129 if (ISL_F_ISSET(bset
, ISL_BASIC_MAP_EMPTY
)) {
1130 if (isl_tab_mark_empty(tab
) < 0)
1135 c
= isl_vec_alloc(bset
->ctx
, 1 + 1 + isl_basic_set_total_dim(bset
));
1139 isl_int_set_si(c
->el
[0], 0);
1140 for (i
= 0; i
< bset
->n_eq
; ++i
) {
1141 isl_seq_cpy(c
->el
+ 1, bset
->eq
[i
], c
->size
- 1);
1142 if (isl_tab_add_eq(tab
, c
->el
) < 0)
1146 isl_int_set_si(c
->el
[0], -1);
1147 for (i
= 0; i
< bset
->n_ineq
; ++i
) {
1148 isl_seq_cpy(c
->el
+ 1, bset
->ineq
[i
], c
->size
- 1);
1149 if (isl_tab_add_ineq(tab
, c
->el
) < 0)
1157 isl_seq_clr(c
->el
+ 1, c
->size
- 1);
1158 isl_int_set_si(c
->el
[1], 1);
1159 if (isl_tab_add_ineq(tab
, c
->el
) < 0)
1170 /* Compute an interior point of "bset" by selecting an interior
1171 * point in homogeneous space and projecting the point back down.
1173 static __isl_give isl_vec
*isl_basic_set_interior_point(
1174 __isl_keep isl_basic_set
*bset
)
1177 struct isl_tab
*tab
;
1179 tab
= tab_for_shifted_cone(bset
);
1180 vec
= isl_tab_get_sample_value(tab
);
1185 isl_seq_cpy(vec
->el
, vec
->el
+ 1, vec
->size
- 1);
1191 /* Call "fn" on all chambers of the parametric polytope with the shared
1192 * facets of neighboring chambers only appearing in one of the chambers.
1194 * We pick an interior point from one of the chambers and then make
1195 * all constraints that do not satisfy this point strict.
1197 int isl_vertices_foreach_disjoint_cell(__isl_keep isl_vertices
*vertices
,
1198 int (*fn
)(__isl_take isl_cell
*cell
, void *user
), void *user
)
1208 if (vertices
->n_chambers
== 0)
1211 if (vertices
->n_chambers
== 1) {
1212 isl_basic_set
*dom
= isl_basic_set_copy(vertices
->c
[0].dom
);
1213 dom
= isl_basic_set_set_integral(dom
);
1214 cell
= isl_cell_alloc(isl_vertices_copy(vertices
), dom
, 0);
1217 return fn(cell
, user
);
1220 vec
= isl_basic_set_interior_point(vertices
->c
[0].dom
);
1226 for (i
= 0; i
< vertices
->n_chambers
; ++i
) {
1228 isl_basic_set
*dom
= isl_basic_set_copy(vertices
->c
[i
].dom
);
1229 dom
= isl_basic_set_cow(dom
);
1232 for (j
= 0; i
&& j
< dom
->n_ineq
; ++j
) {
1233 isl_seq_inner_product(vec
->el
, dom
->ineq
[j
], vec
->size
,
1235 if (!isl_int_is_neg(v
))
1237 isl_int_sub_ui(dom
->ineq
[j
][0], dom
->ineq
[j
][0], 1);
1239 dom
= isl_basic_set_set_integral(dom
);
1240 cell
= isl_cell_alloc(isl_vertices_copy(vertices
), dom
, i
);
1258 int isl_vertices_foreach_cell(__isl_keep isl_vertices
*vertices
,
1259 int (*fn
)(__isl_take isl_cell
*cell
, void *user
), void *user
)
1267 if (vertices
->n_chambers
== 0)
1270 for (i
= 0; i
< vertices
->n_chambers
; ++i
) {
1272 isl_basic_set
*dom
= isl_basic_set_copy(vertices
->c
[i
].dom
);
1274 cell
= isl_cell_alloc(isl_vertices_copy(vertices
), dom
, i
);
1286 int isl_vertices_foreach_vertex(__isl_keep isl_vertices
*vertices
,
1287 int (*fn
)(__isl_take isl_vertex
*vertex
, void *user
), void *user
)
1295 if (vertices
->n_vertices
== 0)
1298 for (i
= 0; i
< vertices
->n_vertices
; ++i
) {
1301 vertex
= isl_vertex_alloc(isl_vertices_copy(vertices
), i
);
1305 r
= fn(vertex
, user
);
1313 int isl_cell_foreach_vertex(__isl_keep isl_cell
*cell
,
1314 int (*fn
)(__isl_take isl_vertex
*vertex
, void *user
), void *user
)
1318 struct isl_chamber
*c
;
1323 c
= &cell
->vertices
->c
[cell
->id
];
1325 if (c
->n_vertices
== 0)
1328 for (i
= 0; i
< c
->n_vertices
; ++i
) {
1331 vertex
= isl_vertex_alloc(isl_vertices_copy(cell
->vertices
),
1336 r
= fn(vertex
, user
);
1344 isl_ctx
*isl_vertices_get_ctx(__isl_keep isl_vertices
*vertices
)
1346 return vertices
? vertices
->ctx
: NULL
;
1349 int isl_vertices_get_n_vertices(__isl_keep isl_vertices
*vertices
)
1351 return vertices
? vertices
->n_vertices
: -1;
1354 __isl_give isl_vertices
*isl_morph_vertices(__isl_take isl_morph
*morph
,
1355 __isl_take isl_vertices
*vertices
)
1358 isl_morph
*param_morph
= NULL
;
1360 if (!morph
|| !vertices
)
1363 isl_assert(vertices
->ctx
, vertices
->ref
== 1, goto error
);
1365 param_morph
= isl_morph_copy(morph
);
1366 param_morph
= isl_morph_remove_dom_dims(param_morph
, isl_dim_set
,
1367 0, isl_morph_dom_dim(morph
, isl_dim_set
));
1368 param_morph
= isl_morph_remove_ran_dims(param_morph
, isl_dim_set
,
1369 0, isl_morph_ran_dim(morph
, isl_dim_set
));
1371 for (i
= 0; i
< vertices
->n_vertices
; ++i
) {
1372 vertices
->v
[i
].dom
= isl_morph_basic_set(
1373 isl_morph_copy(param_morph
), vertices
->v
[i
].dom
);
1374 vertices
->v
[i
].vertex
= isl_morph_basic_set(
1375 isl_morph_copy(morph
), vertices
->v
[i
].vertex
);
1376 if (!vertices
->v
[i
].vertex
)
1380 for (i
= 0; i
< vertices
->n_chambers
; ++i
) {
1381 vertices
->c
[i
].dom
= isl_morph_basic_set(
1382 isl_morph_copy(param_morph
), vertices
->c
[i
].dom
);
1383 if (!vertices
->c
[i
].dom
)
1387 isl_morph_free(param_morph
);
1388 isl_morph_free(morph
);
1391 isl_morph_free(param_morph
);
1392 isl_morph_free(morph
);
1393 isl_vertices_free(vertices
);