2 * Copyright 2008-2009 Katholieke Universiteit Leuven
4 * Use of this software is governed by the GNU LGPLv2.1 license
6 * Written by Sven Verdoolaege, K.U.Leuven, Departement
7 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
10 #include <isl_ctx_private.h>
11 #include <isl_map_private.h>
16 #include "isl_equalities.h"
17 #include "isl_sample.h"
19 #include <isl_mat_private.h>
21 struct isl_basic_map
*isl_basic_map_implicit_equalities(
22 struct isl_basic_map
*bmap
)
29 bmap
= isl_basic_map_gauss(bmap
, NULL
);
30 if (ISL_F_ISSET(bmap
, ISL_BASIC_MAP_EMPTY
))
32 if (ISL_F_ISSET(bmap
, ISL_BASIC_MAP_NO_IMPLICIT
))
34 if (bmap
->n_ineq
<= 1)
37 tab
= isl_tab_from_basic_map(bmap
, 0);
38 if (isl_tab_detect_implicit_equalities(tab
) < 0)
40 bmap
= isl_basic_map_update_from_tab(bmap
, tab
);
42 bmap
= isl_basic_map_gauss(bmap
, NULL
);
43 ISL_F_SET(bmap
, ISL_BASIC_MAP_NO_IMPLICIT
);
47 isl_basic_map_free(bmap
);
51 struct isl_basic_set
*isl_basic_set_implicit_equalities(
52 struct isl_basic_set
*bset
)
54 return (struct isl_basic_set
*)
55 isl_basic_map_implicit_equalities((struct isl_basic_map
*)bset
);
58 struct isl_map
*isl_map_implicit_equalities(struct isl_map
*map
)
65 for (i
= 0; i
< map
->n
; ++i
) {
66 map
->p
[i
] = isl_basic_map_implicit_equalities(map
->p
[i
]);
77 /* Make eq[row][col] of both bmaps equal so we can add the row
78 * add the column to the common matrix.
79 * Note that because of the echelon form, the columns of row row
80 * after column col are zero.
82 static void set_common_multiple(
83 struct isl_basic_set
*bset1
, struct isl_basic_set
*bset2
,
84 unsigned row
, unsigned col
)
88 if (isl_int_eq(bset1
->eq
[row
][col
], bset2
->eq
[row
][col
]))
93 isl_int_lcm(m
, bset1
->eq
[row
][col
], bset2
->eq
[row
][col
]);
94 isl_int_divexact(c
, m
, bset1
->eq
[row
][col
]);
95 isl_seq_scale(bset1
->eq
[row
], bset1
->eq
[row
], c
, col
+1);
96 isl_int_divexact(c
, m
, bset2
->eq
[row
][col
]);
97 isl_seq_scale(bset2
->eq
[row
], bset2
->eq
[row
], c
, col
+1);
102 /* Delete a given equality, moving all the following equalities one up.
104 static void delete_row(struct isl_basic_set
*bset
, unsigned row
)
111 for (r
= row
; r
< bset
->n_eq
; ++r
)
112 bset
->eq
[r
] = bset
->eq
[r
+1];
113 bset
->eq
[bset
->n_eq
] = t
;
116 /* Make first row entries in column col of bset1 identical to
117 * those of bset2, using the fact that entry bset1->eq[row][col]=a
118 * is non-zero. Initially, these elements of bset1 are all zero.
119 * For each row i < row, we set
120 * A[i] = a * A[i] + B[i][col] * A[row]
123 * A[i][col] = B[i][col] = a * old(B[i][col])
125 static void construct_column(
126 struct isl_basic_set
*bset1
, struct isl_basic_set
*bset2
,
127 unsigned row
, unsigned col
)
136 total
= 1 + isl_basic_set_n_dim(bset1
);
137 for (r
= 0; r
< row
; ++r
) {
138 if (isl_int_is_zero(bset2
->eq
[r
][col
]))
140 isl_int_gcd(b
, bset2
->eq
[r
][col
], bset1
->eq
[row
][col
]);
141 isl_int_divexact(a
, bset1
->eq
[row
][col
], b
);
142 isl_int_divexact(b
, bset2
->eq
[r
][col
], b
);
143 isl_seq_combine(bset1
->eq
[r
], a
, bset1
->eq
[r
],
144 b
, bset1
->eq
[row
], total
);
145 isl_seq_scale(bset2
->eq
[r
], bset2
->eq
[r
], a
, total
);
149 delete_row(bset1
, row
);
152 /* Make first row entries in column col of bset1 identical to
153 * those of bset2, using only these entries of the two matrices.
154 * Let t be the last row with different entries.
155 * For each row i < t, we set
156 * A[i] = (A[t][col]-B[t][col]) * A[i] + (B[i][col]-A[i][col) * A[t]
157 * B[i] = (A[t][col]-B[t][col]) * B[i] + (B[i][col]-A[i][col) * B[t]
159 * A[i][col] = B[i][col] = old(A[t][col]*B[i][col]-A[i][col]*B[t][col])
161 static int transform_column(
162 struct isl_basic_set
*bset1
, struct isl_basic_set
*bset2
,
163 unsigned row
, unsigned col
)
169 for (t
= row
-1; t
>= 0; --t
)
170 if (isl_int_ne(bset1
->eq
[t
][col
], bset2
->eq
[t
][col
]))
175 total
= 1 + isl_basic_set_n_dim(bset1
);
179 isl_int_sub(b
, bset1
->eq
[t
][col
], bset2
->eq
[t
][col
]);
180 for (i
= 0; i
< t
; ++i
) {
181 isl_int_sub(a
, bset2
->eq
[i
][col
], bset1
->eq
[i
][col
]);
182 isl_int_gcd(g
, a
, b
);
183 isl_int_divexact(a
, a
, g
);
184 isl_int_divexact(g
, b
, g
);
185 isl_seq_combine(bset1
->eq
[i
], g
, bset1
->eq
[i
], a
, bset1
->eq
[t
],
187 isl_seq_combine(bset2
->eq
[i
], g
, bset2
->eq
[i
], a
, bset2
->eq
[t
],
193 delete_row(bset1
, t
);
194 delete_row(bset2
, t
);
198 /* The implementation is based on Section 5.2 of Michael Karr,
199 * "Affine Relationships Among Variables of a Program",
200 * except that the echelon form we use starts from the last column
201 * and that we are dealing with integer coefficients.
203 static struct isl_basic_set
*affine_hull(
204 struct isl_basic_set
*bset1
, struct isl_basic_set
*bset2
)
210 if (!bset1
|| !bset2
)
213 total
= 1 + isl_basic_set_n_dim(bset1
);
216 for (col
= total
-1; col
>= 0; --col
) {
217 int is_zero1
= row
>= bset1
->n_eq
||
218 isl_int_is_zero(bset1
->eq
[row
][col
]);
219 int is_zero2
= row
>= bset2
->n_eq
||
220 isl_int_is_zero(bset2
->eq
[row
][col
]);
221 if (!is_zero1
&& !is_zero2
) {
222 set_common_multiple(bset1
, bset2
, row
, col
);
224 } else if (!is_zero1
&& is_zero2
) {
225 construct_column(bset1
, bset2
, row
, col
);
226 } else if (is_zero1
&& !is_zero2
) {
227 construct_column(bset2
, bset1
, row
, col
);
229 if (transform_column(bset1
, bset2
, row
, col
))
233 isl_assert(bset1
->ctx
, row
== bset1
->n_eq
, goto error
);
234 isl_basic_set_free(bset2
);
235 bset1
= isl_basic_set_normalize_constraints(bset1
);
238 isl_basic_set_free(bset1
);
239 isl_basic_set_free(bset2
);
243 /* Find an integer point in the set represented by "tab"
244 * that lies outside of the equality "eq" e(x) = 0.
245 * If "up" is true, look for a point satisfying e(x) - 1 >= 0.
246 * Otherwise, look for a point satisfying -e(x) - 1 >= 0 (i.e., e(x) <= -1).
247 * The point, if found, is returned.
248 * If no point can be found, a zero-length vector is returned.
250 * Before solving an ILP problem, we first check if simply
251 * adding the normal of the constraint to one of the known
252 * integer points in the basic set represented by "tab"
253 * yields another point inside the basic set.
255 * The caller of this function ensures that the tableau is bounded or
256 * that tab->basis and tab->n_unbounded have been set appropriately.
258 static struct isl_vec
*outside_point(struct isl_tab
*tab
, isl_int
*eq
, int up
)
261 struct isl_vec
*sample
= NULL
;
262 struct isl_tab_undo
*snap
;
270 sample
= isl_vec_alloc(ctx
, 1 + dim
);
273 isl_int_set_si(sample
->el
[0], 1);
274 isl_seq_combine(sample
->el
+ 1,
275 ctx
->one
, tab
->bmap
->sample
->el
+ 1,
276 up
? ctx
->one
: ctx
->negone
, eq
+ 1, dim
);
277 if (isl_basic_map_contains(tab
->bmap
, sample
))
279 isl_vec_free(sample
);
282 snap
= isl_tab_snap(tab
);
285 isl_seq_neg(eq
, eq
, 1 + dim
);
286 isl_int_sub_ui(eq
[0], eq
[0], 1);
288 if (isl_tab_extend_cons(tab
, 1) < 0)
290 if (isl_tab_add_ineq(tab
, eq
) < 0)
293 sample
= isl_tab_sample(tab
);
295 isl_int_add_ui(eq
[0], eq
[0], 1);
297 isl_seq_neg(eq
, eq
, 1 + dim
);
299 if (sample
&& isl_tab_rollback(tab
, snap
) < 0)
304 isl_vec_free(sample
);
308 struct isl_basic_set
*isl_basic_set_recession_cone(struct isl_basic_set
*bset
)
312 bset
= isl_basic_set_cow(bset
);
315 isl_assert(bset
->ctx
, bset
->n_div
== 0, goto error
);
317 for (i
= 0; i
< bset
->n_eq
; ++i
)
318 isl_int_set_si(bset
->eq
[i
][0], 0);
320 for (i
= 0; i
< bset
->n_ineq
; ++i
)
321 isl_int_set_si(bset
->ineq
[i
][0], 0);
323 ISL_F_CLR(bset
, ISL_BASIC_SET_NO_IMPLICIT
);
324 return isl_basic_set_implicit_equalities(bset
);
326 isl_basic_set_free(bset
);
330 __isl_give isl_set
*isl_set_recession_cone(__isl_take isl_set
*set
)
339 set
= isl_set_remove_divs(set
);
340 set
= isl_set_cow(set
);
344 for (i
= 0; i
< set
->n
; ++i
) {
345 set
->p
[i
] = isl_basic_set_recession_cone(set
->p
[i
]);
356 /* Extend an initial (under-)approximation of the affine hull of basic
357 * set represented by the tableau "tab"
358 * by looking for points that do not satisfy one of the equalities
359 * in the current approximation and adding them to that approximation
360 * until no such points can be found any more.
362 * The caller of this function ensures that "tab" is bounded or
363 * that tab->basis and tab->n_unbounded have been set appropriately.
365 static struct isl_basic_set
*extend_affine_hull(struct isl_tab
*tab
,
366 struct isl_basic_set
*hull
)
376 if (isl_tab_extend_cons(tab
, 2 * dim
+ 1) < 0)
379 for (i
= 0; i
< dim
; ++i
) {
380 struct isl_vec
*sample
;
381 struct isl_basic_set
*point
;
382 for (j
= 0; j
< hull
->n_eq
; ++j
) {
383 sample
= outside_point(tab
, hull
->eq
[j
], 1);
386 if (sample
->size
> 0)
388 isl_vec_free(sample
);
389 sample
= outside_point(tab
, hull
->eq
[j
], 0);
392 if (sample
->size
> 0)
394 isl_vec_free(sample
);
396 if (isl_tab_add_eq(tab
, hull
->eq
[j
]) < 0)
402 tab
= isl_tab_add_sample(tab
, isl_vec_copy(sample
));
405 point
= isl_basic_set_from_vec(sample
);
406 hull
= affine_hull(hull
, point
);
413 isl_basic_set_free(hull
);
417 /* Drop all constraints in bset that involve any of the dimensions
418 * first to first+n-1.
420 __isl_give isl_basic_set
*isl_basic_set_drop_constraints_involving(
421 __isl_take isl_basic_set
*bset
, unsigned first
, unsigned n
)
428 bset
= isl_basic_set_cow(bset
);
433 for (i
= bset
->n_eq
- 1; i
>= 0; --i
) {
434 if (isl_seq_first_non_zero(bset
->eq
[i
] + 1 + first
, n
) == -1)
436 isl_basic_set_drop_equality(bset
, i
);
439 for (i
= bset
->n_ineq
- 1; i
>= 0; --i
) {
440 if (isl_seq_first_non_zero(bset
->ineq
[i
] + 1 + first
, n
) == -1)
442 isl_basic_set_drop_inequality(bset
, i
);
448 /* Look for all equalities satisfied by the integer points in bset,
449 * which is assumed to be bounded.
451 * The equalities are obtained by successively looking for
452 * a point that is affinely independent of the points found so far.
453 * In particular, for each equality satisfied by the points so far,
454 * we check if there is any point on a hyperplane parallel to the
455 * corresponding hyperplane shifted by at least one (in either direction).
457 static struct isl_basic_set
*uset_affine_hull_bounded(struct isl_basic_set
*bset
)
459 struct isl_vec
*sample
= NULL
;
460 struct isl_basic_set
*hull
;
461 struct isl_tab
*tab
= NULL
;
464 if (isl_basic_set_plain_is_empty(bset
))
467 dim
= isl_basic_set_n_dim(bset
);
469 if (bset
->sample
&& bset
->sample
->size
== 1 + dim
) {
470 int contains
= isl_basic_set_contains(bset
, bset
->sample
);
476 sample
= isl_vec_copy(bset
->sample
);
478 isl_vec_free(bset
->sample
);
483 tab
= isl_tab_from_basic_set(bset
, 1);
488 isl_vec_free(sample
);
489 return isl_basic_set_set_to_empty(bset
);
493 struct isl_tab_undo
*snap
;
494 snap
= isl_tab_snap(tab
);
495 sample
= isl_tab_sample(tab
);
496 if (isl_tab_rollback(tab
, snap
) < 0)
498 isl_vec_free(tab
->bmap
->sample
);
499 tab
->bmap
->sample
= isl_vec_copy(sample
);
504 if (sample
->size
== 0) {
506 isl_vec_free(sample
);
507 return isl_basic_set_set_to_empty(bset
);
510 hull
= isl_basic_set_from_vec(sample
);
512 isl_basic_set_free(bset
);
513 hull
= extend_affine_hull(tab
, hull
);
518 isl_vec_free(sample
);
520 isl_basic_set_free(bset
);
524 /* Given an unbounded tableau and an integer point satisfying the tableau,
525 * construct an initial affine hull containing the recession cone
526 * shifted to the given point.
528 * The unbounded directions are taken from the last rows of the basis,
529 * which is assumed to have been initialized appropriately.
531 static __isl_give isl_basic_set
*initial_hull(struct isl_tab
*tab
,
532 __isl_take isl_vec
*vec
)
536 struct isl_basic_set
*bset
= NULL
;
543 isl_assert(ctx
, vec
->size
!= 0, goto error
);
545 bset
= isl_basic_set_alloc(ctx
, 0, vec
->size
- 1, 0, vec
->size
- 1, 0);
548 dim
= isl_basic_set_n_dim(bset
) - tab
->n_unbounded
;
549 for (i
= 0; i
< dim
; ++i
) {
550 k
= isl_basic_set_alloc_equality(bset
);
553 isl_seq_cpy(bset
->eq
[k
] + 1, tab
->basis
->row
[1 + i
] + 1,
555 isl_seq_inner_product(bset
->eq
[k
] + 1, vec
->el
+1,
556 vec
->size
- 1, &bset
->eq
[k
][0]);
557 isl_int_neg(bset
->eq
[k
][0], bset
->eq
[k
][0]);
560 bset
= isl_basic_set_gauss(bset
, NULL
);
564 isl_basic_set_free(bset
);
569 /* Given a tableau of a set and a tableau of the corresponding
570 * recession cone, detect and add all equalities to the tableau.
571 * If the tableau is bounded, then we can simply keep the
572 * tableau in its state after the return from extend_affine_hull.
573 * However, if the tableau is unbounded, then
574 * isl_tab_set_initial_basis_with_cone will add some additional
575 * constraints to the tableau that have to be removed again.
576 * In this case, we therefore rollback to the state before
577 * any constraints were added and then add the equalities back in.
579 struct isl_tab
*isl_tab_detect_equalities(struct isl_tab
*tab
,
580 struct isl_tab
*tab_cone
)
583 struct isl_vec
*sample
;
584 struct isl_basic_set
*hull
;
585 struct isl_tab_undo
*snap
;
587 if (!tab
|| !tab_cone
)
590 snap
= isl_tab_snap(tab
);
592 isl_mat_free(tab
->basis
);
595 isl_assert(tab
->mat
->ctx
, tab
->bmap
, goto error
);
596 isl_assert(tab
->mat
->ctx
, tab
->samples
, goto error
);
597 isl_assert(tab
->mat
->ctx
, tab
->samples
->n_col
== 1 + tab
->n_var
, goto error
);
598 isl_assert(tab
->mat
->ctx
, tab
->n_sample
> tab
->n_outside
, goto error
);
600 if (isl_tab_set_initial_basis_with_cone(tab
, tab_cone
) < 0)
603 sample
= isl_vec_alloc(tab
->mat
->ctx
, 1 + tab
->n_var
);
607 isl_seq_cpy(sample
->el
, tab
->samples
->row
[tab
->n_outside
], sample
->size
);
609 isl_vec_free(tab
->bmap
->sample
);
610 tab
->bmap
->sample
= isl_vec_copy(sample
);
612 if (tab
->n_unbounded
== 0)
613 hull
= isl_basic_set_from_vec(isl_vec_copy(sample
));
615 hull
= initial_hull(tab
, isl_vec_copy(sample
));
617 for (j
= tab
->n_outside
+ 1; j
< tab
->n_sample
; ++j
) {
618 isl_seq_cpy(sample
->el
, tab
->samples
->row
[j
], sample
->size
);
619 hull
= affine_hull(hull
,
620 isl_basic_set_from_vec(isl_vec_copy(sample
)));
623 isl_vec_free(sample
);
625 hull
= extend_affine_hull(tab
, hull
);
629 if (tab
->n_unbounded
== 0) {
630 isl_basic_set_free(hull
);
634 if (isl_tab_rollback(tab
, snap
) < 0)
637 if (hull
->n_eq
> tab
->n_zero
) {
638 for (j
= 0; j
< hull
->n_eq
; ++j
) {
639 isl_seq_normalize(tab
->mat
->ctx
, hull
->eq
[j
], 1 + tab
->n_var
);
640 if (isl_tab_add_eq(tab
, hull
->eq
[j
]) < 0)
645 isl_basic_set_free(hull
);
653 /* Compute the affine hull of "bset", where "cone" is the recession cone
656 * We first compute a unimodular transformation that puts the unbounded
657 * directions in the last dimensions. In particular, we take a transformation
658 * that maps all equalities to equalities (in HNF) on the first dimensions.
659 * Let x be the original dimensions and y the transformed, with y_1 bounded
662 * [ y_1 ] [ y_1 ] [ Q_1 ]
663 * x = U [ y_2 ] [ y_2 ] = [ Q_2 ] x
665 * Let's call the input basic set S. We compute S' = preimage(S, U)
666 * and drop the final dimensions including any constraints involving them.
667 * This results in set S''.
668 * Then we compute the affine hull A'' of S''.
669 * Let F y_1 >= g be the constraint system of A''. In the transformed
670 * space the y_2 are unbounded, so we can add them back without any constraints,
674 * [ F 0 ] [ y_2 ] >= g
677 * [ F 0 ] [ Q_2 ] x >= g
681 * The affine hull in the original space is then obtained as
682 * A = preimage(A'', Q_1).
684 static struct isl_basic_set
*affine_hull_with_cone(struct isl_basic_set
*bset
,
685 struct isl_basic_set
*cone
)
689 struct isl_basic_set
*hull
;
690 struct isl_mat
*M
, *U
, *Q
;
695 total
= isl_basic_set_total_dim(cone
);
696 cone_dim
= total
- cone
->n_eq
;
698 M
= isl_mat_sub_alloc6(bset
->ctx
, cone
->eq
, 0, cone
->n_eq
, 1, total
);
699 M
= isl_mat_left_hermite(M
, 0, &U
, &Q
);
704 U
= isl_mat_lin_to_aff(U
);
705 bset
= isl_basic_set_preimage(bset
, isl_mat_copy(U
));
707 bset
= isl_basic_set_drop_constraints_involving(bset
, total
- cone_dim
,
709 bset
= isl_basic_set_drop_dims(bset
, total
- cone_dim
, cone_dim
);
711 Q
= isl_mat_lin_to_aff(Q
);
712 Q
= isl_mat_drop_rows(Q
, 1 + total
- cone_dim
, cone_dim
);
714 if (bset
&& bset
->sample
&& bset
->sample
->size
== 1 + total
)
715 bset
->sample
= isl_mat_vec_product(isl_mat_copy(Q
), bset
->sample
);
717 hull
= uset_affine_hull_bounded(bset
);
722 struct isl_vec
*sample
= isl_vec_copy(hull
->sample
);
723 U
= isl_mat_drop_cols(U
, 1 + total
- cone_dim
, cone_dim
);
724 if (sample
&& sample
->size
> 0)
725 sample
= isl_mat_vec_product(U
, sample
);
728 hull
= isl_basic_set_preimage(hull
, Q
);
730 isl_vec_free(hull
->sample
);
731 hull
->sample
= sample
;
733 isl_vec_free(sample
);
736 isl_basic_set_free(cone
);
740 isl_basic_set_free(bset
);
741 isl_basic_set_free(cone
);
745 /* Look for all equalities satisfied by the integer points in bset,
746 * which is assumed not to have any explicit equalities.
748 * The equalities are obtained by successively looking for
749 * a point that is affinely independent of the points found so far.
750 * In particular, for each equality satisfied by the points so far,
751 * we check if there is any point on a hyperplane parallel to the
752 * corresponding hyperplane shifted by at least one (in either direction).
754 * Before looking for any outside points, we first compute the recession
755 * cone. The directions of this recession cone will always be part
756 * of the affine hull, so there is no need for looking for any points
757 * in these directions.
758 * In particular, if the recession cone is full-dimensional, then
759 * the affine hull is simply the whole universe.
761 static struct isl_basic_set
*uset_affine_hull(struct isl_basic_set
*bset
)
763 struct isl_basic_set
*cone
;
765 if (isl_basic_set_plain_is_empty(bset
))
768 cone
= isl_basic_set_recession_cone(isl_basic_set_copy(bset
));
771 if (cone
->n_eq
== 0) {
772 struct isl_basic_set
*hull
;
773 isl_basic_set_free(cone
);
774 hull
= isl_basic_set_universe_like(bset
);
775 isl_basic_set_free(bset
);
779 if (cone
->n_eq
< isl_basic_set_total_dim(cone
))
780 return affine_hull_with_cone(bset
, cone
);
782 isl_basic_set_free(cone
);
783 return uset_affine_hull_bounded(bset
);
785 isl_basic_set_free(bset
);
789 /* Look for all equalities satisfied by the integer points in bmap
790 * that are independent of the equalities already explicitly available
793 * We first remove all equalities already explicitly available,
794 * then look for additional equalities in the reduced space
795 * and then transform the result to the original space.
796 * The original equalities are _not_ added to this set. This is
797 * the responsibility of the calling function.
798 * The resulting basic set has all meaning about the dimensions removed.
799 * In particular, dimensions that correspond to existential variables
800 * in bmap and that are found to be fixed are not removed.
802 static struct isl_basic_set
*equalities_in_underlying_set(
803 struct isl_basic_map
*bmap
)
805 struct isl_mat
*T1
= NULL
;
806 struct isl_mat
*T2
= NULL
;
807 struct isl_basic_set
*bset
= NULL
;
808 struct isl_basic_set
*hull
= NULL
;
810 bset
= isl_basic_map_underlying_set(bmap
);
814 bset
= isl_basic_set_remove_equalities(bset
, &T1
, &T2
);
818 hull
= uset_affine_hull(bset
);
826 struct isl_vec
*sample
= isl_vec_copy(hull
->sample
);
827 if (sample
&& sample
->size
> 0)
828 sample
= isl_mat_vec_product(T1
, sample
);
831 hull
= isl_basic_set_preimage(hull
, T2
);
833 isl_vec_free(hull
->sample
);
834 hull
->sample
= sample
;
836 isl_vec_free(sample
);
842 isl_basic_set_free(bset
);
843 isl_basic_set_free(hull
);
847 /* Detect and make explicit all equalities satisfied by the (integer)
850 struct isl_basic_map
*isl_basic_map_detect_equalities(
851 struct isl_basic_map
*bmap
)
854 struct isl_basic_set
*hull
= NULL
;
858 if (bmap
->n_ineq
== 0)
860 if (ISL_F_ISSET(bmap
, ISL_BASIC_MAP_EMPTY
))
862 if (ISL_F_ISSET(bmap
, ISL_BASIC_MAP_ALL_EQUALITIES
))
864 if (ISL_F_ISSET(bmap
, ISL_BASIC_MAP_RATIONAL
))
865 return isl_basic_map_implicit_equalities(bmap
);
867 hull
= equalities_in_underlying_set(isl_basic_map_copy(bmap
));
870 if (ISL_F_ISSET(hull
, ISL_BASIC_SET_EMPTY
)) {
871 isl_basic_set_free(hull
);
872 return isl_basic_map_set_to_empty(bmap
);
874 bmap
= isl_basic_map_extend_space(bmap
, isl_space_copy(bmap
->dim
), 0,
876 for (i
= 0; i
< hull
->n_eq
; ++i
) {
877 j
= isl_basic_map_alloc_equality(bmap
);
880 isl_seq_cpy(bmap
->eq
[j
], hull
->eq
[i
],
881 1 + isl_basic_set_total_dim(hull
));
883 isl_vec_free(bmap
->sample
);
884 bmap
->sample
= isl_vec_copy(hull
->sample
);
885 isl_basic_set_free(hull
);
886 ISL_F_SET(bmap
, ISL_BASIC_MAP_NO_IMPLICIT
| ISL_BASIC_MAP_ALL_EQUALITIES
);
887 bmap
= isl_basic_map_simplify(bmap
);
888 return isl_basic_map_finalize(bmap
);
890 isl_basic_set_free(hull
);
891 isl_basic_map_free(bmap
);
895 __isl_give isl_basic_set
*isl_basic_set_detect_equalities(
896 __isl_take isl_basic_set
*bset
)
898 return (isl_basic_set
*)
899 isl_basic_map_detect_equalities((isl_basic_map
*)bset
);
902 __isl_give isl_map
*isl_map_inline_foreach_basic_map(__isl_take isl_map
*map
,
903 __isl_give isl_basic_map
*(*fn
)(__isl_take isl_basic_map
*bmap
))
905 struct isl_basic_map
*bmap
;
911 for (i
= 0; i
< map
->n
; ++i
) {
912 bmap
= isl_basic_map_copy(map
->p
[i
]);
916 isl_basic_map_free(map
->p
[i
]);
926 __isl_give isl_map
*isl_map_detect_equalities(__isl_take isl_map
*map
)
928 return isl_map_inline_foreach_basic_map(map
,
929 &isl_basic_map_detect_equalities
);
932 __isl_give isl_set
*isl_set_detect_equalities(__isl_take isl_set
*set
)
934 return (isl_set
*)isl_map_detect_equalities((isl_map
*)set
);
937 /* After computing the rational affine hull (by detecting the implicit
938 * equalities), we compute the additional equalities satisfied by
939 * the integer points (if any) and add the original equalities back in.
941 struct isl_basic_map
*isl_basic_map_affine_hull(struct isl_basic_map
*bmap
)
943 bmap
= isl_basic_map_detect_equalities(bmap
);
944 bmap
= isl_basic_map_cow(bmap
);
946 isl_basic_map_free_inequality(bmap
, bmap
->n_ineq
);
947 bmap
= isl_basic_map_finalize(bmap
);
951 struct isl_basic_set
*isl_basic_set_affine_hull(struct isl_basic_set
*bset
)
953 return (struct isl_basic_set
*)
954 isl_basic_map_affine_hull((struct isl_basic_map
*)bset
);
957 struct isl_basic_map
*isl_map_affine_hull(struct isl_map
*map
)
960 struct isl_basic_map
*model
= NULL
;
961 struct isl_basic_map
*hull
= NULL
;
964 map
= isl_map_detect_equalities(map
);
965 map
= isl_map_align_divs(map
);
971 hull
= isl_basic_map_empty_like_map(map
);
976 model
= isl_basic_map_copy(map
->p
[0]);
977 set
= isl_map_underlying_set(map
);
978 set
= isl_set_cow(set
);
982 for (i
= 0; i
< set
->n
; ++i
) {
983 set
->p
[i
] = isl_basic_set_cow(set
->p
[i
]);
984 set
->p
[i
] = isl_basic_set_affine_hull(set
->p
[i
]);
985 set
->p
[i
] = isl_basic_set_gauss(set
->p
[i
], NULL
);
989 set
= isl_set_remove_empty_parts(set
);
991 hull
= isl_basic_map_empty_like(model
);
992 isl_basic_map_free(model
);
994 struct isl_basic_set
*bset
;
996 set
->p
[0] = affine_hull(set
->p
[0], set
->p
[--set
->n
]);
1000 bset
= isl_basic_set_copy(set
->p
[0]);
1001 hull
= isl_basic_map_overlying_set(bset
, model
);
1004 hull
= isl_basic_map_simplify(hull
);
1005 return isl_basic_map_finalize(hull
);
1007 isl_basic_map_free(model
);
1012 struct isl_basic_set
*isl_set_affine_hull(struct isl_set
*set
)
1014 return (struct isl_basic_set
*)
1015 isl_map_affine_hull((struct isl_map
*)set
);