2 * Copyright 2010-2011 INRIA Saclay
3 * Copyright 2014 Ecole Normale Superieure
5 * Use of this software is governed by the MIT license
7 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
8 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
10 * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
13 #include <isl_map_private.h>
14 #include <isl_aff_private.h>
15 #include <isl_morph.h>
17 #include <isl_mat_private.h>
18 #include <isl_space_private.h>
19 #include <isl_equalities.h>
20 #include <isl_id_private.h>
21 #include <isl_aff_private.h>
22 #include <isl_vec_private.h>
24 isl_ctx
*isl_morph_get_ctx(__isl_keep isl_morph
*morph
)
28 return isl_basic_set_get_ctx(morph
->dom
);
31 __isl_give isl_morph
*isl_morph_alloc(
32 __isl_take isl_basic_set
*dom
, __isl_take isl_basic_set
*ran
,
33 __isl_take isl_mat
*map
, __isl_take isl_mat
*inv
)
37 if (!dom
|| !ran
|| !map
|| !inv
)
40 morph
= isl_alloc_type(dom
->ctx
, struct isl_morph
);
52 isl_basic_set_free(dom
);
53 isl_basic_set_free(ran
);
59 __isl_give isl_morph
*isl_morph_copy(__isl_keep isl_morph
*morph
)
68 __isl_give isl_morph
*isl_morph_dup(__isl_keep isl_morph
*morph
)
73 return isl_morph_alloc(isl_basic_set_copy(morph
->dom
),
74 isl_basic_set_copy(morph
->ran
),
75 isl_mat_copy(morph
->map
), isl_mat_copy(morph
->inv
));
78 __isl_give isl_morph
*isl_morph_cow(__isl_take isl_morph
*morph
)
86 return isl_morph_dup(morph
);
89 __isl_null isl_morph
*isl_morph_free(__isl_take isl_morph
*morph
)
97 isl_basic_set_free(morph
->dom
);
98 isl_basic_set_free(morph
->ran
);
99 isl_mat_free(morph
->map
);
100 isl_mat_free(morph
->inv
);
106 /* Is "morph" an identity on the parameters?
108 static isl_bool
identity_on_parameters(__isl_keep isl_morph
*morph
)
110 isl_bool is_identity
;
111 isl_size nparam
, nparam_ran
;
114 nparam
= isl_morph_dom_dim(morph
, isl_dim_param
);
115 nparam_ran
= isl_morph_ran_dim(morph
, isl_dim_param
);
116 if (nparam
< 0 || nparam_ran
< 0)
117 return isl_bool_error
;
118 if (nparam
!= nparam_ran
)
119 return isl_bool_false
;
121 return isl_bool_true
;
122 sub
= isl_mat_sub_alloc(morph
->map
, 0, 1 + nparam
, 0, 1 + nparam
);
123 is_identity
= isl_mat_is_scaled_identity(sub
);
129 /* Return an affine expression of the variables of the range of "morph"
130 * in terms of the parameters and the variables of the domain on "morph".
132 * In order for the space manipulations to make sense, we require
133 * that the parameters are not modified by "morph".
135 __isl_give isl_multi_aff
*isl_morph_get_var_multi_aff(
136 __isl_keep isl_morph
*morph
)
138 isl_space
*dom
, *ran
, *space
;
141 isl_size nparam
, nvar
;
143 isl_bool is_identity
;
148 is_identity
= identity_on_parameters(morph
);
152 isl_die(isl_morph_get_ctx(morph
), isl_error_invalid
,
153 "cannot handle parameter compression", return NULL
);
155 dom
= isl_morph_get_dom_space(morph
);
156 ls
= isl_local_space_from_space(isl_space_copy(dom
));
157 ran
= isl_morph_get_ran_space(morph
);
158 space
= isl_space_map_from_domain_and_range(dom
, ran
);
159 ma
= isl_multi_aff_zero(space
);
161 nparam
= isl_multi_aff_dim(ma
, isl_dim_param
);
162 nvar
= isl_multi_aff_dim(ma
, isl_dim_out
);
163 if (nparam
< 0 || nvar
< 0)
164 ma
= isl_multi_aff_free(ma
);
165 for (i
= 0; i
< nvar
; ++i
) {
170 v
= isl_mat_get_row(morph
->map
, 1 + nparam
+ i
);
171 v
= isl_vec_insert_els(v
, 0, 1);
172 val
= isl_mat_get_element_val(morph
->map
, 0, 0);
173 v
= isl_vec_set_element_val(v
, 0, val
);
174 aff
= isl_aff_alloc_vec(isl_local_space_copy(ls
), v
);
175 ma
= isl_multi_aff_set_aff(ma
, i
, aff
);
178 isl_local_space_free(ls
);
182 /* Return the domain space of "morph".
184 __isl_give isl_space
*isl_morph_get_dom_space(__isl_keep isl_morph
*morph
)
189 return isl_basic_set_get_space(morph
->dom
);
192 __isl_give isl_space
*isl_morph_get_ran_space(__isl_keep isl_morph
*morph
)
197 return isl_space_copy(morph
->ran
->dim
);
200 isl_size
isl_morph_dom_dim(__isl_keep isl_morph
*morph
, enum isl_dim_type type
)
203 return isl_size_error
;
205 return isl_basic_set_dim(morph
->dom
, type
);
208 isl_size
isl_morph_ran_dim(__isl_keep isl_morph
*morph
, enum isl_dim_type type
)
211 return isl_size_error
;
213 return isl_basic_set_dim(morph
->ran
, type
);
216 __isl_give isl_morph
*isl_morph_remove_dom_dims(__isl_take isl_morph
*morph
,
217 enum isl_dim_type type
, unsigned first
, unsigned n
)
224 morph
= isl_morph_cow(morph
);
228 dom_offset
= 1 + isl_space_offset(morph
->dom
->dim
, type
);
230 morph
->dom
= isl_basic_set_remove_dims(morph
->dom
, type
, first
, n
);
232 morph
->map
= isl_mat_drop_cols(morph
->map
, dom_offset
+ first
, n
);
234 morph
->inv
= isl_mat_drop_rows(morph
->inv
, dom_offset
+ first
, n
);
236 if (morph
->dom
&& morph
->ran
&& morph
->map
&& morph
->inv
)
239 isl_morph_free(morph
);
243 __isl_give isl_morph
*isl_morph_remove_ran_dims(__isl_take isl_morph
*morph
,
244 enum isl_dim_type type
, unsigned first
, unsigned n
)
251 morph
= isl_morph_cow(morph
);
255 ran_offset
= 1 + isl_space_offset(morph
->ran
->dim
, type
);
257 morph
->ran
= isl_basic_set_remove_dims(morph
->ran
, type
, first
, n
);
259 morph
->map
= isl_mat_drop_rows(morph
->map
, ran_offset
+ first
, n
);
261 morph
->inv
= isl_mat_drop_cols(morph
->inv
, ran_offset
+ first
, n
);
263 if (morph
->dom
&& morph
->ran
&& morph
->map
&& morph
->inv
)
266 isl_morph_free(morph
);
270 /* Project domain of morph onto its parameter domain.
272 __isl_give isl_morph
*isl_morph_dom_params(__isl_take isl_morph
*morph
)
276 morph
= isl_morph_cow(morph
);
279 n
= isl_basic_set_dim(morph
->dom
, isl_dim_set
);
281 return isl_morph_free(morph
);
282 morph
= isl_morph_remove_dom_dims(morph
, isl_dim_set
, 0, n
);
285 morph
->dom
= isl_basic_set_params(morph
->dom
);
289 isl_morph_free(morph
);
293 /* Project range of morph onto its parameter domain.
295 __isl_give isl_morph
*isl_morph_ran_params(__isl_take isl_morph
*morph
)
299 morph
= isl_morph_cow(morph
);
302 n
= isl_basic_set_dim(morph
->ran
, isl_dim_set
);
304 return isl_morph_free(morph
);
305 morph
= isl_morph_remove_ran_dims(morph
, isl_dim_set
, 0, n
);
308 morph
->ran
= isl_basic_set_params(morph
->ran
);
312 isl_morph_free(morph
);
316 /* Replace the identifier of the tuple of the range of the morph by "id".
318 static __isl_give isl_morph
*isl_morph_set_ran_tuple_id(
319 __isl_take isl_morph
*morph
, __isl_keep isl_id
*id
)
321 morph
= isl_morph_cow(morph
);
324 morph
->ran
= isl_basic_set_set_tuple_id(morph
->ran
, isl_id_copy(id
));
326 return isl_morph_free(morph
);
330 void isl_morph_print_internal(__isl_take isl_morph
*morph
, FILE *out
)
335 isl_basic_set_dump(morph
->dom
);
336 isl_basic_set_dump(morph
->ran
);
337 isl_mat_print_internal(morph
->map
, out
, 4);
338 isl_mat_print_internal(morph
->inv
, out
, 4);
341 void isl_morph_dump(__isl_take isl_morph
*morph
)
343 isl_morph_print_internal(morph
, stderr
);
346 __isl_give isl_morph
*isl_morph_identity(__isl_keep isl_basic_set
*bset
)
349 isl_basic_set
*universe
;
352 total
= isl_basic_set_dim(bset
, isl_dim_all
);
356 id
= isl_mat_identity(bset
->ctx
, 1 + total
);
357 universe
= isl_basic_set_universe(isl_space_copy(bset
->dim
));
359 return isl_morph_alloc(universe
, isl_basic_set_copy(universe
),
360 id
, isl_mat_copy(id
));
363 /* Create a(n identity) morphism between empty sets of the same dimension
366 __isl_give isl_morph
*isl_morph_empty(__isl_keep isl_basic_set
*bset
)
369 isl_basic_set
*empty
;
372 total
= isl_basic_set_dim(bset
, isl_dim_all
);
376 id
= isl_mat_identity(bset
->ctx
, 1 + total
);
377 empty
= isl_basic_set_empty(isl_space_copy(bset
->dim
));
379 return isl_morph_alloc(empty
, isl_basic_set_copy(empty
),
380 id
, isl_mat_copy(id
));
383 /* Construct a basic set described by the "n" equalities of "bset" starting
386 static __isl_give isl_basic_set
*copy_equalities(__isl_keep isl_basic_set
*bset
,
387 unsigned first
, unsigned n
)
393 total
= isl_basic_set_dim(bset
, isl_dim_all
);
394 if (total
< 0 || isl_basic_set_check_no_locals(bset
) < 0)
397 eq
= isl_basic_set_alloc_space(isl_basic_set_get_space(bset
), 0, n
, 0);
400 for (i
= 0; i
< n
; ++i
) {
401 k
= isl_basic_set_alloc_equality(eq
);
404 isl_seq_cpy(eq
->eq
[k
], bset
->eq
[first
+ i
], 1 + total
);
409 isl_basic_set_free(eq
);
413 /* Given a basic set, exploit the equalities in the basic set to construct
414 * a morphism that maps the basic set to a lower-dimensional space.
415 * Specifically, the morphism reduces the number of dimensions of type "type".
417 * We first select the equalities of interest, that is those that involve
418 * variables of type "type" and no later variables.
419 * Denote those equalities as
423 * where C(p) depends on the parameters if type == isl_dim_set and
424 * is a constant if type == isl_dim_param.
426 * Use isl_mat_final_variable_compression to construct a compression
432 * If T is a zero-column matrix, then the set of equality constraints
433 * do not admit a solution. In this case, an empty morphism is returned.
435 * Both matrices are extended to map the full original space to the full
438 __isl_give isl_morph
*isl_basic_set_variable_compression(
439 __isl_keep isl_basic_set
*bset
, enum isl_dim_type type
)
449 isl_basic_set
*dom
, *ran
;
454 if (isl_basic_set_plain_is_empty(bset
))
455 return isl_morph_empty(bset
);
457 if (isl_basic_set_check_no_locals(bset
) < 0)
460 ntype
= isl_basic_set_dim(bset
, type
);
461 total
= isl_basic_set_dim(bset
, isl_dim_all
);
462 if (ntype
< 0 || total
< 0)
464 otype
= isl_basic_set_offset(bset
, type
);
465 orest
= otype
+ ntype
;
466 nrest
= total
- (orest
- 1);
468 for (f_eq
= 0; f_eq
< bset
->n_eq
; ++f_eq
)
469 if (isl_seq_first_non_zero(bset
->eq
[f_eq
] + orest
, nrest
) == -1)
471 for (n_eq
= 0; f_eq
+ n_eq
< bset
->n_eq
; ++n_eq
)
472 if (isl_seq_first_non_zero(bset
->eq
[f_eq
+ n_eq
] + otype
, ntype
) == -1)
475 return isl_morph_identity(bset
);
477 E
= isl_mat_sub_alloc6(bset
->ctx
, bset
->eq
, f_eq
, n_eq
, 0, orest
);
478 C
= isl_mat_final_variable_compression(E
, otype
- 1, &Q
);
481 if (C
&& C
->n_col
== 0) {
484 return isl_morph_empty(bset
);
487 Q
= isl_mat_diagonal(Q
, isl_mat_identity(bset
->ctx
, nrest
));
488 C
= isl_mat_diagonal(C
, isl_mat_identity(bset
->ctx
, nrest
));
490 space
= isl_space_copy(bset
->dim
);
491 space
= isl_space_drop_dims(space
, type
, 0, ntype
);
492 space
= isl_space_add_dims(space
, type
, ntype
- n_eq
);
493 ran
= isl_basic_set_universe(space
);
494 dom
= copy_equalities(bset
, f_eq
, n_eq
);
496 return isl_morph_alloc(dom
, ran
, Q
, C
);
499 /* Given a basic set, exploit the equalities in the basic set to construct
500 * a morphism that maps the basic set to a lower-dimensional space
501 * with identifier "id".
502 * Specifically, the morphism reduces the number of set dimensions.
504 __isl_give isl_morph
*isl_basic_set_variable_compression_with_id(
505 __isl_keep isl_basic_set
*bset
, __isl_keep isl_id
*id
)
509 morph
= isl_basic_set_variable_compression(bset
, isl_dim_set
);
510 morph
= isl_morph_set_ran_tuple_id(morph
, id
);
514 /* Construct a parameter compression for "bset".
515 * We basically just call isl_mat_parameter_compression with the right input
516 * and then extend the resulting matrix to include the variables.
518 * The implementation assumes that "bset" does not have any equalities
519 * that only involve the parameters and that isl_basic_set_gauss has
520 * been applied to "bset".
522 * Let the equalities be given as
526 * We use isl_mat_parameter_compression_ext to compute the compression
530 __isl_give isl_morph
*isl_basic_set_parameter_compression(
531 __isl_keep isl_basic_set
*bset
)
539 isl_basic_set
*dom
, *ran
;
544 if (isl_basic_set_plain_is_empty(bset
))
545 return isl_morph_empty(bset
);
547 return isl_morph_identity(bset
);
550 nparam
= isl_basic_set_dim(bset
, isl_dim_param
);
551 nvar
= isl_basic_set_dim(bset
, isl_dim_set
);
552 n_div
= isl_basic_set_dim(bset
, isl_dim_div
);
553 if (nparam
< 0 || nvar
< 0 || n_div
< 0)
556 if (isl_seq_first_non_zero(bset
->eq
[bset
->n_eq
- 1] + 1 + nparam
,
558 isl_die(isl_basic_set_get_ctx(bset
), isl_error_invalid
,
559 "input not allowed to have parameter equalities",
561 if (n_eq
> nvar
+ n_div
)
562 isl_die(isl_basic_set_get_ctx(bset
), isl_error_invalid
,
563 "input not gaussed", return NULL
);
565 B
= isl_mat_sub_alloc6(bset
->ctx
, bset
->eq
, 0, n_eq
, 0, 1 + nparam
);
566 H
= isl_mat_sub_alloc6(bset
->ctx
, bset
->eq
,
567 0, n_eq
, 1 + nparam
, nvar
+ n_div
);
568 inv
= isl_mat_parameter_compression_ext(B
, H
);
569 inv
= isl_mat_diagonal(inv
, isl_mat_identity(bset
->ctx
, nvar
));
570 map
= isl_mat_right_inverse(isl_mat_copy(inv
));
572 dom
= isl_basic_set_universe(isl_space_copy(bset
->dim
));
573 ran
= isl_basic_set_universe(isl_space_copy(bset
->dim
));
575 return isl_morph_alloc(dom
, ran
, map
, inv
);
578 /* Construct an isl_multi_aff that corresponds
579 * to the affine transformation matrix "mat" and
580 * that lives in an anonymous space.
582 static __isl_give isl_multi_aff
*isl_multi_aff_from_aff_mat_anonymous(
583 __isl_take isl_mat
*mat
)
585 isl_size n_row
, n_col
;
589 ctx
= isl_mat_get_ctx(mat
);
590 n_row
= isl_mat_rows(mat
);
591 n_col
= isl_mat_cols(mat
);
592 if (n_row
< 0 || n_col
< 0)
595 space
= isl_space_alloc(ctx
, 0, n_col
- 1, n_row
- 1);
597 return isl_multi_aff_from_aff_mat(space
, mat
);
600 /* Apply the morphism to the basic set.
601 * In particular, compute the preimage of "bset" under the inverse mapping
602 * in morph and intersect with the range of the morphism.
603 * Note that the mapping in morph applies to both parameters and set dimensions,
604 * so the parameters need to be treated as set dimensions during the call
605 * to isl_basic_set_preimage_multi_aff.
607 __isl_give isl_basic_set
*isl_morph_basic_set(__isl_take isl_morph
*morph
,
608 __isl_take isl_basic_set
*bset
)
614 if (!morph
|| isl_basic_set_check_equal_space(bset
, morph
->dom
) < 0)
616 n_param
= isl_basic_set_dim(morph
->dom
, isl_dim_param
);
620 ma
= isl_multi_aff_from_aff_mat_anonymous(isl_mat_copy(morph
->inv
));
622 bset
= isl_basic_set_move_dims(bset
, isl_dim_set
, 0,
623 isl_dim_param
, 0, n_param
);
624 bset
= isl_basic_set_preimage_multi_aff(bset
, ma
);
625 space
= isl_basic_set_get_space(morph
->ran
);
626 bset
= isl_basic_set_reset_space(bset
, space
);
627 bset
= isl_basic_set_intersect(bset
, isl_basic_set_copy(morph
->ran
));
629 isl_morph_free(morph
);
632 isl_morph_free(morph
);
633 isl_basic_set_free(bset
);
637 /* Apply the morphism to the set.
638 * In particular, compute the preimage of "set" under the inverse mapping
639 * in morph and intersect with the range of the morphism.
640 * Note that the mapping in morph applies to both parameters and set dimensions,
641 * so the parameters need to be treated as set dimensions during the call
642 * to isl_set_preimage_multi_aff.
644 __isl_give isl_set
*isl_morph_set(__isl_take isl_morph
*morph
,
645 __isl_take isl_set
*set
)
652 if (!morph
|| isl_set_basic_set_check_equal_space(set
, morph
->dom
) < 0)
654 n_param
= isl_basic_set_dim(morph
->dom
, isl_dim_param
);
658 ma
= isl_multi_aff_from_aff_mat_anonymous(isl_mat_copy(morph
->inv
));
660 set
= isl_set_move_dims(set
, isl_dim_set
, 0, isl_dim_param
, 0, n_param
);
661 set
= isl_set_preimage_multi_aff(set
, ma
);
662 space
= isl_basic_set_get_space(morph
->ran
);
663 set
= isl_set_reset_space(set
, space
);
664 ran
= isl_basic_set_copy(morph
->ran
);
665 set
= isl_set_intersect(set
, isl_set_from_basic_set(ran
));
667 isl_morph_free(morph
);
671 isl_morph_free(morph
);
675 /* Construct a morphism that first does morph2 and then morph1.
677 __isl_give isl_morph
*isl_morph_compose(__isl_take isl_morph
*morph1
,
678 __isl_take isl_morph
*morph2
)
681 isl_basic_set
*dom
, *ran
;
683 if (!morph1
|| !morph2
)
686 map
= isl_mat_product(isl_mat_copy(morph1
->map
), isl_mat_copy(morph2
->map
));
687 inv
= isl_mat_product(isl_mat_copy(morph2
->inv
), isl_mat_copy(morph1
->inv
));
688 dom
= isl_morph_basic_set(isl_morph_inverse(isl_morph_copy(morph2
)),
689 isl_basic_set_copy(morph1
->dom
));
690 dom
= isl_basic_set_intersect(dom
, isl_basic_set_copy(morph2
->dom
));
691 ran
= isl_morph_basic_set(isl_morph_copy(morph1
),
692 isl_basic_set_copy(morph2
->ran
));
693 ran
= isl_basic_set_intersect(ran
, isl_basic_set_copy(morph1
->ran
));
695 isl_morph_free(morph1
);
696 isl_morph_free(morph2
);
698 return isl_morph_alloc(dom
, ran
, map
, inv
);
700 isl_morph_free(morph1
);
701 isl_morph_free(morph2
);
705 __isl_give isl_morph
*isl_morph_inverse(__isl_take isl_morph
*morph
)
710 morph
= isl_morph_cow(morph
);
715 morph
->dom
= morph
->ran
;
719 morph
->map
= morph
->inv
;
725 /* We detect all the equalities first to avoid implicit equalities
726 * being discovered during the computations. In particular,
727 * the compression on the variables could expose additional stride
728 * constraints on the parameters. This would result in existentially
729 * quantified variables after applying the resulting morph, which
730 * in turn could break invariants of the calling functions.
732 __isl_give isl_morph
*isl_basic_set_full_compression(
733 __isl_keep isl_basic_set
*bset
)
735 isl_morph
*morph
, *morph2
;
737 bset
= isl_basic_set_copy(bset
);
738 bset
= isl_basic_set_detect_equalities(bset
);
740 morph
= isl_basic_set_variable_compression(bset
, isl_dim_param
);
741 bset
= isl_morph_basic_set(isl_morph_copy(morph
), bset
);
743 morph2
= isl_basic_set_parameter_compression(bset
);
744 bset
= isl_morph_basic_set(isl_morph_copy(morph2
), bset
);
746 morph
= isl_morph_compose(morph2
, morph
);
748 morph2
= isl_basic_set_variable_compression(bset
, isl_dim_set
);
749 isl_basic_set_free(bset
);
751 morph
= isl_morph_compose(morph2
, morph
);
756 __isl_give isl_vec
*isl_morph_vec(__isl_take isl_morph
*morph
,
757 __isl_take isl_vec
*vec
)
762 vec
= isl_mat_vec_product(isl_mat_copy(morph
->map
), vec
);
764 isl_morph_free(morph
);
767 isl_morph_free(morph
);