2 * Copyright 2010 INRIA Saclay
4 * Use of this software is governed by the MIT license
6 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
7 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
11 #include <isl_map_private.h>
12 #include <isl_aff_private.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>
26 static __isl_give isl_vertices
*compute_chambers(__isl_take isl_basic_set
*bset
,
27 __isl_take isl_vertices
*vertices
);
29 __isl_give isl_vertices
*isl_vertices_copy(__isl_keep isl_vertices
*vertices
)
38 __isl_null isl_vertices
*isl_vertices_free(__isl_take isl_vertices
*vertices
)
45 if (--vertices
->ref
> 0)
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
);
54 for (i
= 0; i
< vertices
->n_chambers
; ++i
) {
55 free(vertices
->c
[i
].vertices
);
56 isl_basic_set_free(vertices
->c
[i
].dom
);
60 isl_basic_set_free(vertices
->bset
);
66 struct isl_vertex_list
{
68 struct isl_vertex_list
*next
;
71 static struct isl_vertex_list
*free_vertex_list(struct isl_vertex_list
*list
)
73 struct isl_vertex_list
*next
;
75 for (; list
; list
= next
) {
77 isl_basic_set_free(list
->v
.vertex
);
78 isl_basic_set_free(list
->v
.dom
);
85 static __isl_give isl_vertices
*vertices_from_list(__isl_keep isl_basic_set
*bset
,
86 int n_vertices
, struct isl_vertex_list
*list
)
89 struct isl_vertex_list
*next
;
90 isl_vertices
*vertices
;
92 vertices
= isl_calloc_type(bset
->ctx
, isl_vertices
);
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
)
100 vertices
->n_vertices
= n_vertices
;
102 for (i
= 0; list
; list
= next
, i
++) {
104 vertices
->v
[i
] = list
->v
;
110 isl_vertices_free(vertices
);
111 free_vertex_list(list
);
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 and
117 * isl_bool_false otherwise.
118 * In particular, vertices with a lower-dimensional activity domain are
119 * not added to the list because they would not be included in any chamber.
120 * Return isl_bool_error on error.
122 static isl_bool
add_vertex(struct isl_vertex_list
**list
,
123 __isl_keep isl_basic_set
*bset
, struct isl_tab
*tab
)
126 struct isl_vertex_list
*v
= NULL
;
128 if (isl_tab_detect_implicit_equalities(tab
) < 0)
129 return isl_bool_error
;
131 nvar
= isl_basic_set_dim(bset
, isl_dim_set
);
133 return isl_bool_error
;
135 v
= isl_calloc_type(tab
->mat
->ctx
, struct isl_vertex_list
);
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
);
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
);
152 if (v
->v
.dom
->n_eq
> 0) {
154 return isl_bool_false
;
160 return isl_bool_true
;
163 return isl_bool_error
;
166 /* Compute the parametric vertices and the chamber decomposition
167 * of an empty parametric polytope.
169 static __isl_give isl_vertices
*vertices_empty(__isl_keep isl_basic_set
*bset
)
171 isl_vertices
*vertices
;
176 vertices
= isl_calloc_type(bset
->ctx
, isl_vertices
);
179 vertices
->bset
= isl_basic_set_copy(bset
);
182 vertices
->n_vertices
= 0;
183 vertices
->n_chambers
= 0;
188 /* Compute the parametric vertices and the chamber decomposition
189 * of the parametric polytope defined using the same constraints
190 * as "bset" in the 0D case.
191 * There is exactly one 0D vertex and a single chamber containing
194 static __isl_give isl_vertices
*vertices_0D(__isl_keep isl_basic_set
*bset
)
196 isl_vertices
*vertices
;
201 vertices
= isl_calloc_type(bset
->ctx
, isl_vertices
);
205 vertices
->bset
= isl_basic_set_copy(bset
);
207 vertices
->v
= isl_calloc_array(bset
->ctx
, struct isl_vertex
, 1);
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
)
216 vertices
->c
= isl_calloc_array(bset
->ctx
, struct isl_chamber
, 1);
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
)
224 vertices
->c
[0].dom
= isl_basic_set_copy(vertices
->v
[0].dom
);
225 if (!vertices
->c
[0].dom
)
230 isl_vertices_free(vertices
);
234 /* Is the row pointed to by "f" linearly independent of the "n" first
237 static isl_bool
is_independent(__isl_keep isl_mat
*facets
, int n
, isl_int
*f
)
241 if (isl_seq_first_non_zero(f
, facets
->n_col
) < 0)
242 return isl_bool_false
;
244 isl_seq_cpy(facets
->row
[n
], f
, facets
->n_col
);
245 facets
->n_row
= n
+ 1;
246 rank
= isl_mat_rank(facets
);
248 return isl_bool_error
;
250 return isl_bool_ok(rank
== n
+ 1);
253 /* Check whether we can select constraint "level", given the current selection
254 * reflected by facets in "tab", the rows of "facets" and the earlier
255 * "selected" elements of "selection".
257 * If the constraint is (strictly) redundant in the tableau, selecting it would
258 * result in an empty tableau, so it can't be selected.
259 * If the set variable part of the constraint is not linearly independent
260 * 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 constraint
263 * cannot be selected.
264 * Finally, if selecting the constraint results in some explicitly
265 * deselected constraints turning into equalities, then the corresponding
266 * vertices have already been generated, so the constraint cannot be selected.
268 static isl_bool
can_select(__isl_keep isl_basic_set
*bset
, int level
,
269 struct isl_tab
*tab
, __isl_keep isl_mat
*facets
, int selected
,
275 struct isl_tab_undo
*snap
;
277 if (isl_tab_is_redundant(tab
, level
))
278 return isl_bool_false
;
280 ovar
= isl_space_offset(bset
->dim
, isl_dim_set
);
282 indep
= is_independent(facets
, selected
, bset
->ineq
[level
] + 1 + ovar
);
283 if (indep
< 0 || !indep
)
286 snap
= isl_tab_snap(tab
);
287 if (isl_tab_select_facet(tab
, level
) < 0)
288 return isl_bool_error
;
291 if (isl_tab_rollback(tab
, snap
) < 0)
292 return isl_bool_error
;
293 return isl_bool_false
;
296 for (i
= 0; i
< level
; ++i
) {
299 if (selection
[i
] != DESELECTED
)
302 if (isl_tab_is_equality(tab
, i
))
304 else if (isl_tab_is_redundant(tab
, i
))
307 sgn
= isl_tab_sign_of_max(tab
, i
);
309 return isl_bool_error
;
311 if (isl_tab_rollback(tab
, snap
) < 0)
312 return isl_bool_error
;
313 return isl_bool_false
;
317 return isl_bool_true
;
320 /* Compute the parametric vertices and the chamber decomposition
321 * of a parametric polytope that is not full-dimensional.
323 * Simply map the parametric polytope to a lower dimensional space
324 * and map the resulting vertices back.
326 static __isl_give isl_vertices
*lower_dim_vertices(
327 __isl_keep isl_basic_set
*bset
)
330 isl_vertices
*vertices
;
332 bset
= isl_basic_set_copy(bset
);
333 morph
= isl_basic_set_full_compression(bset
);
334 bset
= isl_morph_basic_set(isl_morph_copy(morph
), bset
);
336 vertices
= isl_basic_set_compute_vertices(bset
);
337 isl_basic_set_free(bset
);
339 morph
= isl_morph_inverse(morph
);
341 vertices
= isl_morph_vertices(morph
, vertices
);
346 /* Compute the parametric vertices and the chamber decomposition
347 * of the parametric polytope defined using the same constraints
348 * as "bset". "bset" is assumed to have no existentially quantified
351 * The vertices themselves are computed in a fairly simplistic way.
352 * We simply run through all combinations of d constraints,
353 * with d the number of set variables, and check if those d constraints
354 * define a vertex. To avoid the generation of duplicate vertices,
355 * which we may happen if a vertex is defined by more that d constraints,
356 * we make sure we only generate the vertex for the d constraints with
359 * We set up a tableau and keep track of which facets have been
360 * selected. The tableau is marked strict_redundant so that we can be
361 * sure that any constraint that is marked redundant (and that is not
362 * also marked zero) is not an equality.
363 * If a constraint is marked DESELECTED, it means the constraint was
364 * SELECTED before (in combination with the same selection of earlier
365 * constraints). If such a deselected constraint turns out to be an
366 * equality, then any vertex that may still be found with the current
367 * selection has already been generated when the constraint was selected.
368 * A constraint is marked UNSELECTED when there is no way selecting
369 * the constraint could lead to a vertex (in combination with the current
370 * selection of earlier constraints).
372 * The set variable coefficients of the selected constraints are stored
373 * in the facets matrix.
375 __isl_give isl_vertices
*isl_basic_set_compute_vertices(
376 __isl_keep isl_basic_set
*bset
)
382 int *selection
= NULL
;
384 struct isl_tab_undo
**snap
= NULL
;
385 isl_mat
*facets
= NULL
;
386 struct isl_vertex_list
*list
= NULL
;
388 isl_vertices
*vertices
;
393 if (isl_basic_set_plain_is_empty(bset
))
394 return vertices_empty(bset
);
397 return lower_dim_vertices(bset
);
399 if (isl_basic_set_check_no_locals(bset
) < 0)
402 nvar
= isl_basic_set_dim(bset
, isl_dim_set
);
406 return vertices_0D(bset
);
408 bset
= isl_basic_set_copy(bset
);
409 bset
= isl_basic_set_set_rational(bset
);
413 tab
= isl_tab_from_basic_set(bset
, 0);
416 tab
->strict_redundant
= 1;
419 vertices
= vertices_empty(bset
);
420 isl_basic_set_free(bset
);
425 selection
= isl_alloc_array(bset
->ctx
, int, bset
->n_ineq
);
426 snap
= isl_alloc_array(bset
->ctx
, struct isl_tab_undo
*, bset
->n_ineq
);
427 facets
= isl_mat_alloc(bset
->ctx
, nvar
, nvar
);
428 if ((bset
->n_ineq
&& (!selection
|| !snap
)) || !facets
)
436 if (level
>= bset
->n_ineq
||
437 (!init
&& selection
[level
] != SELECTED
)) {
444 snap
[level
] = isl_tab_snap(tab
);
445 ok
= can_select(bset
, level
, tab
, facets
, selected
,
450 selection
[level
] = SELECTED
;
453 selection
[level
] = UNSELECTED
;
455 selection
[level
] = DESELECTED
;
457 if (isl_tab_rollback(tab
, snap
[level
]) < 0)
460 if (selected
== nvar
) {
461 if (tab
->n_dead
== nvar
) {
462 isl_bool added
= add_vertex(&list
, bset
, tab
);
475 isl_mat_free(facets
);
481 vertices
= vertices_from_list(bset
, n_vertices
, list
);
483 vertices
= compute_chambers(bset
, vertices
);
487 free_vertex_list(list
);
488 isl_mat_free(facets
);
492 isl_basic_set_free(bset
);
496 struct isl_chamber_list
{
497 struct isl_chamber c
;
498 struct isl_chamber_list
*next
;
501 static void free_chamber_list(struct isl_chamber_list
*list
)
503 struct isl_chamber_list
*next
;
505 for (; list
; list
= next
) {
507 isl_basic_set_free(list
->c
.dom
);
508 free(list
->c
.vertices
);
513 /* Check whether the basic set "bset" is a superset of the basic set described
514 * by "tab", i.e., check whether all constraints of "bset" are redundant.
516 static isl_bool
bset_covers_tab(__isl_keep isl_basic_set
*bset
,
522 return isl_bool_error
;
524 for (i
= 0; i
< bset
->n_ineq
; ++i
) {
525 enum isl_ineq_type type
= isl_tab_ineq_type(tab
, bset
->ineq
[i
]);
527 case isl_ineq_error
: return isl_bool_error
;
528 case isl_ineq_redundant
: continue;
529 default: return isl_bool_false
;
533 return isl_bool_true
;
536 static __isl_give isl_vertices
*vertices_add_chambers(
537 __isl_take isl_vertices
*vertices
, int n_chambers
,
538 struct isl_chamber_list
*list
)
542 struct isl_chamber_list
*next
;
544 ctx
= isl_vertices_get_ctx(vertices
);
545 vertices
->c
= isl_alloc_array(ctx
, struct isl_chamber
, n_chambers
);
548 vertices
->n_chambers
= n_chambers
;
550 for (i
= 0; list
; list
= next
, i
++) {
552 vertices
->c
[i
] = list
->c
;
558 isl_vertices_free(vertices
);
559 free_chamber_list(list
);
563 /* Can "tab" be intersected with "bset" without resulting in
564 * a lower-dimensional set.
565 * "bset" itself is assumed to be full-dimensional.
567 static isl_bool
can_intersect(struct isl_tab
*tab
,
568 __isl_keep isl_basic_set
*bset
)
571 struct isl_tab_undo
*snap
;
574 isl_die(isl_basic_set_get_ctx(bset
), isl_error_internal
,
575 "expecting full-dimensional input",
576 return isl_bool_error
);
578 if (isl_tab_extend_cons(tab
, bset
->n_ineq
) < 0)
579 return isl_bool_error
;
581 snap
= isl_tab_snap(tab
);
583 for (i
= 0; i
< bset
->n_ineq
; ++i
) {
584 enum isl_ineq_type type
;
586 type
= isl_tab_ineq_type(tab
, bset
->ineq
[i
]);
588 return isl_bool_error
;
589 if (type
== isl_ineq_redundant
)
591 if (isl_tab_add_ineq(tab
, bset
->ineq
[i
]) < 0)
592 return isl_bool_error
;
595 if (isl_tab_detect_implicit_equalities(tab
) < 0)
596 return isl_bool_error
;
598 if (isl_tab_rollback(tab
, snap
) < 0)
599 return isl_bool_error
;
600 return isl_bool_false
;
603 return isl_bool_true
;
606 static int add_chamber(struct isl_chamber_list
**list
,
607 __isl_keep isl_vertices
*vertices
, struct isl_tab
*tab
, int *selection
)
612 struct isl_tab_undo
*snap
;
613 struct isl_chamber_list
*c
= NULL
;
615 for (i
= 0; i
< vertices
->n_vertices
; ++i
)
619 snap
= isl_tab_snap(tab
);
621 for (i
= 0; i
< tab
->n_con
&& tab
->con
[i
].frozen
; ++i
)
622 tab
->con
[i
].frozen
= 0;
625 if (isl_tab_detect_redundant(tab
) < 0)
628 c
= isl_calloc_type(tab
->mat
->ctx
, struct isl_chamber_list
);
631 c
->c
.vertices
= isl_alloc_array(tab
->mat
->ctx
, int, n_vertices
);
632 if (n_vertices
&& !c
->c
.vertices
)
634 c
->c
.dom
= isl_basic_set_copy(isl_tab_peek_bset(tab
));
635 c
->c
.dom
= isl_basic_set_set_rational(c
->c
.dom
);
636 c
->c
.dom
= isl_basic_set_cow(c
->c
.dom
);
637 c
->c
.dom
= isl_basic_set_update_from_tab(c
->c
.dom
, tab
);
638 c
->c
.dom
= isl_basic_set_simplify(c
->c
.dom
);
639 c
->c
.dom
= isl_basic_set_finalize(c
->c
.dom
);
643 c
->c
.n_vertices
= n_vertices
;
645 for (i
= 0, j
= 0; i
< vertices
->n_vertices
; ++i
)
647 c
->c
.vertices
[j
] = i
;
654 for (i
= 0; i
< n_frozen
; ++i
)
655 tab
->con
[i
].frozen
= 1;
657 if (isl_tab_rollback(tab
, snap
) < 0)
662 free_chamber_list(c
);
666 struct isl_facet_todo
{
667 struct isl_tab
*tab
; /* A tableau representation of the facet */
668 isl_basic_set
*bset
; /* A normalized basic set representation */
669 isl_vec
*constraint
; /* Constraint pointing to the other side */
670 struct isl_facet_todo
*next
;
673 static void free_todo(struct isl_facet_todo
*todo
)
676 struct isl_facet_todo
*next
= todo
->next
;
678 isl_tab_free(todo
->tab
);
679 isl_basic_set_free(todo
->bset
);
680 isl_vec_free(todo
->constraint
);
687 static struct isl_facet_todo
*create_todo(struct isl_tab
*tab
, int con
)
691 struct isl_tab_undo
*snap
;
692 struct isl_facet_todo
*todo
;
694 snap
= isl_tab_snap(tab
);
696 for (i
= 0; i
< tab
->n_con
&& tab
->con
[i
].frozen
; ++i
)
697 tab
->con
[i
].frozen
= 0;
700 if (isl_tab_detect_redundant(tab
) < 0)
703 todo
= isl_calloc_type(tab
->mat
->ctx
, struct isl_facet_todo
);
707 todo
->constraint
= isl_vec_alloc(tab
->mat
->ctx
, 1 + tab
->n_var
);
708 if (!todo
->constraint
)
710 isl_seq_neg(todo
->constraint
->el
, tab
->bmap
->ineq
[con
], 1 + tab
->n_var
);
711 todo
->bset
= isl_basic_set_copy(isl_tab_peek_bset(tab
));
712 todo
->bset
= isl_basic_set_set_rational(todo
->bset
);
713 todo
->bset
= isl_basic_set_cow(todo
->bset
);
714 todo
->bset
= isl_basic_set_update_from_tab(todo
->bset
, tab
);
715 todo
->bset
= isl_basic_set_simplify(todo
->bset
);
716 todo
->bset
= isl_basic_set_sort_constraints(todo
->bset
);
719 ISL_F_SET(todo
->bset
, ISL_BASIC_SET_NO_REDUNDANT
);
720 todo
->tab
= isl_tab_dup(tab
);
724 for (i
= 0; i
< n_frozen
; ++i
)
725 tab
->con
[i
].frozen
= 1;
727 if (isl_tab_rollback(tab
, snap
) < 0)
736 /* Create todo items for all interior facets of the chamber represented
737 * by "tab" and collect them in "next".
739 static int init_todo(struct isl_facet_todo
**next
, struct isl_tab
*tab
)
742 struct isl_tab_undo
*snap
;
743 struct isl_facet_todo
*todo
;
745 snap
= isl_tab_snap(tab
);
747 for (i
= 0; i
< tab
->n_con
; ++i
) {
748 if (tab
->con
[i
].frozen
)
750 if (tab
->con
[i
].is_redundant
)
753 if (isl_tab_select_facet(tab
, i
) < 0)
756 todo
= create_todo(tab
, i
);
763 if (isl_tab_rollback(tab
, snap
) < 0)
770 /* Does the linked list contain a todo item that is the opposite of "todo".
771 * If so, return 1 and remove the opposite todo item.
773 static int has_opposite(struct isl_facet_todo
*todo
,
774 struct isl_facet_todo
**list
)
776 for (; *list
; list
= &(*list
)->next
) {
778 eq
= isl_basic_set_plain_is_equal(todo
->bset
, (*list
)->bset
);
793 /* Create todo items for all interior facets of the chamber represented
794 * by "tab" and collect them in first->next, taking care to cancel
795 * opposite todo items.
797 static int update_todo(struct isl_facet_todo
*first
, struct isl_tab
*tab
)
800 struct isl_tab_undo
*snap
;
801 struct isl_facet_todo
*todo
;
803 snap
= isl_tab_snap(tab
);
805 for (i
= 0; i
< tab
->n_con
; ++i
) {
808 if (tab
->con
[i
].frozen
)
810 if (tab
->con
[i
].is_redundant
)
813 if (isl_tab_select_facet(tab
, i
) < 0)
816 todo
= create_todo(tab
, i
);
820 drop
= has_opposite(todo
, &first
->next
);
827 todo
->next
= first
->next
;
831 if (isl_tab_rollback(tab
, snap
) < 0)
838 /* Compute the chamber decomposition of the parametric polytope respresented
839 * by "bset" given the parametric vertices and their activity domains.
841 * We are only interested in full-dimensional chambers.
842 * Each of these chambers is the intersection of the activity domains of
843 * one or more vertices and the union of all chambers is equal to the
844 * projection of the entire parametric polytope onto the parameter space.
846 * We first create an initial chamber by intersecting as many activity
847 * domains as possible without ending up with an empty or lower-dimensional
848 * set. As a minor optimization, we only consider those activity domains
849 * that contain some arbitrary point.
851 * For each of the interior facets of the chamber, we construct a todo item,
852 * containing the facet and a constraint containing the other side of the facet,
853 * for constructing the chamber on the other side.
854 * While their are any todo items left, we pick a todo item and
855 * create the required chamber by intersecting all activity domains
856 * that contain the facet and have a full-dimensional intersection with
857 * the other side of the facet. For each of the interior facets, we
858 * again create todo items, taking care to cancel opposite todo items.
860 static __isl_give isl_vertices
*compute_chambers(__isl_take isl_basic_set
*bset
,
861 __isl_take isl_vertices
*vertices
)
865 isl_vec
*sample
= NULL
;
866 struct isl_tab
*tab
= NULL
;
867 struct isl_tab_undo
*snap
;
868 int *selection
= NULL
;
870 struct isl_chamber_list
*list
= NULL
;
871 struct isl_facet_todo
*todo
= NULL
;
873 if (!bset
|| !vertices
)
876 ctx
= isl_vertices_get_ctx(vertices
);
877 selection
= isl_alloc_array(ctx
, int, vertices
->n_vertices
);
878 if (vertices
->n_vertices
&& !selection
)
881 bset
= isl_basic_set_params(bset
);
883 tab
= isl_tab_from_basic_set(bset
, 1);
886 for (i
= 0; i
< bset
->n_ineq
; ++i
)
887 if (isl_tab_freeze_constraint(tab
, i
) < 0)
889 isl_basic_set_free(bset
);
891 snap
= isl_tab_snap(tab
);
893 sample
= isl_tab_get_sample_value(tab
);
895 for (i
= 0; i
< vertices
->n_vertices
; ++i
) {
896 selection
[i
] = isl_basic_set_contains(vertices
->v
[i
].dom
, sample
);
897 if (selection
[i
] < 0)
901 selection
[i
] = can_intersect(tab
, vertices
->v
[i
].dom
);
902 if (selection
[i
] < 0)
906 if (isl_tab_detect_redundant(tab
) < 0)
909 if (add_chamber(&list
, vertices
, tab
, selection
) < 0)
913 if (init_todo(&todo
, tab
) < 0)
917 struct isl_facet_todo
*next
;
919 if (isl_tab_rollback(tab
, snap
) < 0)
922 if (isl_tab_add_ineq(tab
, todo
->constraint
->el
) < 0)
924 if (isl_tab_freeze_constraint(tab
, tab
->n_con
- 1) < 0)
927 for (i
= 0; i
< vertices
->n_vertices
; ++i
) {
928 selection
[i
] = bset_covers_tab(vertices
->v
[i
].dom
,
930 if (selection
[i
] < 0)
934 selection
[i
] = can_intersect(tab
, vertices
->v
[i
].dom
);
935 if (selection
[i
] < 0)
939 if (isl_tab_detect_redundant(tab
) < 0)
942 if (add_chamber(&list
, vertices
, tab
, selection
) < 0)
946 if (update_todo(todo
, tab
) < 0)
955 isl_vec_free(sample
);
960 vertices
= vertices_add_chambers(vertices
, n_chambers
, list
);
962 for (i
= 0; vertices
&& i
< vertices
->n_vertices
; ++i
) {
963 isl_basic_set_free(vertices
->v
[i
].dom
);
964 vertices
->v
[i
].dom
= NULL
;
969 free_chamber_list(list
);
971 isl_vec_free(sample
);
975 isl_basic_set_free(bset
);
976 isl_vertices_free(vertices
);
980 isl_ctx
*isl_vertex_get_ctx(__isl_keep isl_vertex
*vertex
)
982 return vertex
? isl_vertices_get_ctx(vertex
->vertices
) : NULL
;
985 isl_size
isl_vertex_get_id(__isl_keep isl_vertex
*vertex
)
987 return vertex
? vertex
->id
: isl_size_error
;
990 /* Return the activity domain of the vertex "vertex".
992 __isl_give isl_basic_set
*isl_vertex_get_domain(__isl_keep isl_vertex
*vertex
)
994 struct isl_vertex
*v
;
999 v
= &vertex
->vertices
->v
[vertex
->id
];
1001 v
->dom
= isl_basic_set_copy(v
->vertex
);
1002 v
->dom
= isl_basic_set_params(v
->dom
);
1003 v
->dom
= isl_basic_set_set_integral(v
->dom
);
1006 return isl_basic_set_copy(v
->dom
);
1009 /* Return a multiple quasi-affine expression describing the vertex "vertex"
1010 * in terms of the parameters,
1012 __isl_give isl_multi_aff
*isl_vertex_get_expr(__isl_keep isl_vertex
*vertex
)
1014 struct isl_vertex
*v
;
1015 isl_basic_set
*bset
;
1020 v
= &vertex
->vertices
->v
[vertex
->id
];
1022 bset
= isl_basic_set_copy(v
->vertex
);
1023 return isl_multi_aff_from_basic_set_equalities(bset
);
1026 static __isl_give isl_vertex
*isl_vertex_alloc(__isl_take isl_vertices
*vertices
,
1035 ctx
= isl_vertices_get_ctx(vertices
);
1036 vertex
= isl_alloc_type(ctx
, isl_vertex
);
1040 vertex
->vertices
= vertices
;
1045 isl_vertices_free(vertices
);
1049 __isl_null isl_vertex
*isl_vertex_free(__isl_take isl_vertex
*vertex
)
1053 isl_vertices_free(vertex
->vertices
);
1059 isl_ctx
*isl_cell_get_ctx(__isl_keep isl_cell
*cell
)
1061 return cell
? cell
->dom
->ctx
: NULL
;
1064 __isl_give isl_basic_set
*isl_cell_get_domain(__isl_keep isl_cell
*cell
)
1066 return cell
? isl_basic_set_copy(cell
->dom
) : NULL
;
1069 static __isl_give isl_cell
*isl_cell_alloc(__isl_take isl_vertices
*vertices
,
1070 __isl_take isl_basic_set
*dom
, int id
)
1073 isl_cell
*cell
= NULL
;
1075 if (!vertices
|| !dom
)
1078 cell
= isl_calloc_type(dom
->ctx
, isl_cell
);
1082 cell
->n_vertices
= vertices
->c
[id
].n_vertices
;
1083 cell
->ids
= isl_alloc_array(dom
->ctx
, int, cell
->n_vertices
);
1084 if (cell
->n_vertices
&& !cell
->ids
)
1086 for (i
= 0; i
< cell
->n_vertices
; ++i
)
1087 cell
->ids
[i
] = vertices
->c
[id
].vertices
[i
];
1088 cell
->vertices
= vertices
;
1093 isl_cell_free(cell
);
1094 isl_vertices_free(vertices
);
1095 isl_basic_set_free(dom
);
1099 __isl_null isl_cell
*isl_cell_free(__isl_take isl_cell
*cell
)
1104 isl_vertices_free(cell
->vertices
);
1106 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
;
1123 total
= isl_basic_set_dim(bset
, isl_dim_all
);
1126 tab
= isl_tab_alloc(bset
->ctx
, bset
->n_eq
+ bset
->n_ineq
+ 1,
1130 tab
->rational
= ISL_F_ISSET(bset
, ISL_BASIC_SET_RATIONAL
);
1131 if (ISL_F_ISSET(bset
, ISL_BASIC_MAP_EMPTY
)) {
1132 if (isl_tab_mark_empty(tab
) < 0)
1137 c
= isl_vec_alloc(bset
->ctx
, 1 + 1 + total
);
1141 isl_int_set_si(c
->el
[0], 0);
1142 for (i
= 0; i
< bset
->n_eq
; ++i
) {
1143 isl_seq_cpy(c
->el
+ 1, bset
->eq
[i
], c
->size
- 1);
1144 if (isl_tab_add_eq(tab
, c
->el
) < 0)
1148 isl_int_set_si(c
->el
[0], -1);
1149 for (i
= 0; i
< bset
->n_ineq
; ++i
) {
1150 isl_seq_cpy(c
->el
+ 1, bset
->ineq
[i
], c
->size
- 1);
1151 if (isl_tab_add_ineq(tab
, c
->el
) < 0)
1159 isl_seq_clr(c
->el
+ 1, c
->size
- 1);
1160 isl_int_set_si(c
->el
[1], 1);
1161 if (isl_tab_add_ineq(tab
, c
->el
) < 0)
1172 /* Compute an interior point of "bset" by selecting an interior
1173 * point in homogeneous space and projecting the point back down.
1175 static __isl_give isl_vec
*isl_basic_set_interior_point(
1176 __isl_keep isl_basic_set
*bset
)
1179 struct isl_tab
*tab
;
1181 tab
= tab_for_shifted_cone(bset
);
1182 vec
= isl_tab_get_sample_value(tab
);
1187 isl_seq_cpy(vec
->el
, vec
->el
+ 1, vec
->size
- 1);
1193 /* Call "fn" on all chambers of the parametric polytope with the shared
1194 * facets of neighboring chambers only appearing in one of the chambers.
1196 * We pick an interior point from one of the chambers and then make
1197 * all constraints that do not satisfy this point strict.
1198 * For constraints that saturate the interior point, the sign
1199 * of the first non-zero coefficient is used to determine which
1200 * of the two (internal) constraints should be tightened.
1202 isl_stat
isl_vertices_foreach_disjoint_cell(__isl_keep isl_vertices
*vertices
,
1203 isl_stat (*fn
)(__isl_take isl_cell
*cell
, void *user
), void *user
)
1210 return isl_stat_error
;
1212 if (vertices
->n_chambers
== 0)
1215 if (vertices
->n_chambers
== 1) {
1216 isl_basic_set
*dom
= isl_basic_set_copy(vertices
->c
[0].dom
);
1217 dom
= isl_basic_set_set_integral(dom
);
1218 cell
= isl_cell_alloc(isl_vertices_copy(vertices
), dom
, 0);
1220 return isl_stat_error
;
1221 return fn(cell
, user
);
1224 vec
= isl_basic_set_interior_point(vertices
->c
[0].dom
);
1226 return isl_stat_error
;
1228 for (i
= 0; i
< vertices
->n_chambers
; ++i
) {
1230 isl_basic_set
*dom
= isl_basic_set_copy(vertices
->c
[i
].dom
);
1232 dom
= isl_basic_set_tighten_outward(dom
, vec
);
1233 dom
= isl_basic_set_set_integral(dom
);
1234 cell
= isl_cell_alloc(isl_vertices_copy(vertices
), dom
, i
);
1247 return isl_stat_error
;
1250 isl_stat
isl_vertices_foreach_cell(__isl_keep isl_vertices
*vertices
,
1251 isl_stat (*fn
)(__isl_take isl_cell
*cell
, void *user
), void *user
)
1257 return isl_stat_error
;
1259 if (vertices
->n_chambers
== 0)
1262 for (i
= 0; i
< vertices
->n_chambers
; ++i
) {
1264 isl_basic_set
*dom
= isl_basic_set_copy(vertices
->c
[i
].dom
);
1266 cell
= isl_cell_alloc(isl_vertices_copy(vertices
), dom
, i
);
1268 return isl_stat_error
;
1272 return isl_stat_error
;
1278 isl_stat
isl_vertices_foreach_vertex(__isl_keep isl_vertices
*vertices
,
1279 isl_stat (*fn
)(__isl_take isl_vertex
*vertex
, void *user
), void *user
)
1285 return isl_stat_error
;
1287 if (vertices
->n_vertices
== 0)
1290 for (i
= 0; i
< vertices
->n_vertices
; ++i
) {
1293 vertex
= isl_vertex_alloc(isl_vertices_copy(vertices
), i
);
1295 return isl_stat_error
;
1297 r
= fn(vertex
, user
);
1299 return isl_stat_error
;
1305 isl_stat
isl_cell_foreach_vertex(__isl_keep isl_cell
*cell
,
1306 isl_stat (*fn
)(__isl_take isl_vertex
*vertex
, void *user
), void *user
)
1312 return isl_stat_error
;
1314 if (cell
->n_vertices
== 0)
1317 for (i
= 0; i
< cell
->n_vertices
; ++i
) {
1320 vertex
= isl_vertex_alloc(isl_vertices_copy(cell
->vertices
),
1323 return isl_stat_error
;
1325 r
= fn(vertex
, user
);
1327 return isl_stat_error
;
1333 isl_ctx
*isl_vertices_get_ctx(__isl_keep isl_vertices
*vertices
)
1335 return vertices
? vertices
->bset
->ctx
: NULL
;
1338 isl_size
isl_vertices_get_n_vertices(__isl_keep isl_vertices
*vertices
)
1340 return vertices
? vertices
->n_vertices
: isl_size_error
;
1343 __isl_give isl_vertices
*isl_morph_vertices(__isl_take isl_morph
*morph
,
1344 __isl_take isl_vertices
*vertices
)
1347 isl_morph
*param_morph
= NULL
;
1349 if (!morph
|| !vertices
)
1352 isl_assert(vertices
->bset
->ctx
, vertices
->ref
== 1, goto error
);
1354 param_morph
= isl_morph_copy(morph
);
1355 param_morph
= isl_morph_dom_params(param_morph
);
1356 param_morph
= isl_morph_ran_params(param_morph
);
1358 for (i
= 0; i
< vertices
->n_vertices
; ++i
) {
1359 vertices
->v
[i
].dom
= isl_morph_basic_set(
1360 isl_morph_copy(param_morph
), vertices
->v
[i
].dom
);
1361 vertices
->v
[i
].vertex
= isl_morph_basic_set(
1362 isl_morph_copy(morph
), vertices
->v
[i
].vertex
);
1363 if (!vertices
->v
[i
].vertex
)
1367 for (i
= 0; i
< vertices
->n_chambers
; ++i
) {
1368 vertices
->c
[i
].dom
= isl_morph_basic_set(
1369 isl_morph_copy(param_morph
), vertices
->c
[i
].dom
);
1370 if (!vertices
->c
[i
].dom
)
1374 isl_morph_free(param_morph
);
1375 isl_morph_free(morph
);
1378 isl_morph_free(param_morph
);
1379 isl_morph_free(morph
);
1380 isl_vertices_free(vertices
);
1384 /* Construct a simplex isl_cell spanned by the vertices with indices in
1385 * "simplex_ids" and "other_ids" and call "fn" on this isl_cell.
1387 static isl_stat
call_on_simplex(__isl_keep isl_cell
*cell
,
1388 int *simplex_ids
, int n_simplex
, int *other_ids
, int n_other
,
1389 isl_stat (*fn
)(__isl_take isl_cell
*simplex
, void *user
), void *user
)
1393 struct isl_cell
*simplex
;
1395 ctx
= isl_cell_get_ctx(cell
);
1397 simplex
= isl_calloc_type(ctx
, struct isl_cell
);
1399 return isl_stat_error
;
1400 simplex
->vertices
= isl_vertices_copy(cell
->vertices
);
1401 if (!simplex
->vertices
)
1403 simplex
->dom
= isl_basic_set_copy(cell
->dom
);
1406 simplex
->n_vertices
= n_simplex
+ n_other
;
1407 simplex
->ids
= isl_alloc_array(ctx
, int, simplex
->n_vertices
);
1411 for (i
= 0; i
< n_simplex
; ++i
)
1412 simplex
->ids
[i
] = simplex_ids
[i
];
1413 for (i
= 0; i
< n_other
; ++i
)
1414 simplex
->ids
[n_simplex
+ i
] = other_ids
[i
];
1416 return fn(simplex
, user
);
1418 isl_cell_free(simplex
);
1419 return isl_stat_error
;
1422 /* Check whether the parametric vertex described by "vertex"
1423 * lies on the facet corresponding to constraint "facet" of "bset".
1424 * The isl_vec "v" is a temporary vector than can be used by this function.
1426 * We eliminate the variables from the facet constraint using the
1427 * equalities defining the vertex and check if the result is identical
1430 * It would probably be better to keep track of the constraints defining
1431 * a vertex during the vertex construction so that we could simply look
1434 static int vertex_on_facet(__isl_keep isl_basic_set
*vertex
,
1435 __isl_keep isl_basic_set
*bset
, int facet
, __isl_keep isl_vec
*v
)
1440 isl_seq_cpy(v
->el
, bset
->ineq
[facet
], v
->size
);
1443 for (i
= 0; i
< vertex
->n_eq
; ++i
) {
1444 int k
= isl_seq_last_non_zero(vertex
->eq
[i
], v
->size
);
1445 isl_seq_elim(v
->el
, vertex
->eq
[i
], k
, v
->size
, &m
);
1449 return isl_seq_first_non_zero(v
->el
, v
->size
) == -1;
1452 /* Triangulate the polytope spanned by the vertices with ids
1453 * in "simplex_ids" and "other_ids" and call "fn" on each of
1454 * the resulting simplices.
1455 * If the input polytope is already a simplex, we simply call "fn".
1456 * Otherwise, we pick a point from "other_ids" and add it to "simplex_ids".
1457 * Then we consider each facet of "bset" that does not contain the point
1458 * we just picked, but does contain some of the other points in "other_ids"
1459 * and call ourselves recursively on the polytope spanned by the new
1460 * "simplex_ids" and those points in "other_ids" that lie on the facet.
1462 static isl_stat
triangulate(__isl_keep isl_cell
*cell
, __isl_keep isl_vec
*v
,
1463 int *simplex_ids
, int n_simplex
, int *other_ids
, int n_other
,
1464 isl_stat (*fn
)(__isl_take isl_cell
*simplex
, void *user
), void *user
)
1470 isl_basic_set
*vertex
;
1471 isl_basic_set
*bset
;
1473 ctx
= isl_cell_get_ctx(cell
);
1474 d
= isl_basic_set_dim(cell
->vertices
->bset
, isl_dim_set
);
1475 nparam
= isl_basic_set_dim(cell
->vertices
->bset
, isl_dim_param
);
1476 if (d
< 0 || nparam
< 0)
1477 return isl_stat_error
;
1479 if (n_simplex
+ n_other
== d
+ 1)
1480 return call_on_simplex(cell
, simplex_ids
, n_simplex
,
1481 other_ids
, n_other
, fn
, user
);
1483 simplex_ids
[n_simplex
] = other_ids
[0];
1484 vertex
= cell
->vertices
->v
[other_ids
[0]].vertex
;
1485 bset
= cell
->vertices
->bset
;
1487 ids
= isl_alloc_array(ctx
, int, n_other
- 1);
1490 for (i
= 0; i
< bset
->n_ineq
; ++i
) {
1491 if (isl_seq_first_non_zero(bset
->ineq
[i
] + 1 + nparam
, d
) == -1)
1493 if (vertex_on_facet(vertex
, bset
, i
, v
))
1496 for (j
= 1, k
= 0; j
< n_other
; ++j
) {
1498 ov
= cell
->vertices
->v
[other_ids
[j
]].vertex
;
1499 if (vertex_on_facet(ov
, bset
, i
, v
))
1500 ids
[k
++] = other_ids
[j
];
1505 if (triangulate(cell
, v
, simplex_ids
, n_simplex
+ 1,
1506 ids
, k
, fn
, user
) < 0)
1514 return isl_stat_error
;
1517 /* Triangulate the given cell and call "fn" on each of the resulting
1520 isl_stat
isl_cell_foreach_simplex(__isl_take isl_cell
*cell
,
1521 isl_stat (*fn
)(__isl_take isl_cell
*simplex
, void *user
), void *user
)
1527 int *simplex_ids
= NULL
;
1530 return isl_stat_error
;
1532 d
= isl_basic_set_dim(cell
->vertices
->bset
, isl_dim_set
);
1533 total
= isl_basic_set_dim(cell
->vertices
->bset
, isl_dim_all
);
1534 if (d
< 0 || total
< 0)
1535 return isl_stat_error
;
1537 if (cell
->n_vertices
== d
+ 1)
1538 return fn(cell
, user
);
1540 ctx
= isl_cell_get_ctx(cell
);
1541 simplex_ids
= isl_alloc_array(ctx
, int, d
+ 1);
1545 v
= isl_vec_alloc(ctx
, 1 + total
);
1549 r
= triangulate(cell
, v
, simplex_ids
, 0,
1550 cell
->ids
, cell
->n_vertices
, fn
, user
);
1555 isl_cell_free(cell
);
1561 isl_cell_free(cell
);
1562 return isl_stat_error
;