1/*
2 * Copyright 2010-2011 INRIA Saclay
3 * Copyright 2014 Ecole Normale Superieure
4 *
5 * Use of this software is governed by the MIT license
6 *
7 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
8 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
9 * 91893 Orsay, France
10 * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
11 */
12
13#include <isl_map_private.h>
14#include <isl_aff_private.h>
15#include <isl_morph.h>
16#include <isl_seq.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>
23
24isl_ctx *isl_morph_get_ctx(__isl_keep isl_morph *morph)
25{
26 if (!morph)
27 return NULL;
28 return isl_basic_set_get_ctx(bset: morph->dom);
29}
30
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)
34{
35 isl_morph *morph;
36
37 if (!dom || !ran || !map || !inv)
38 goto error;
39
40 morph = isl_alloc_type(dom->ctx, struct isl_morph);
41 if (!morph)
42 goto error;
43
44 morph->ref = 1;
45 morph->dom = dom;
46 morph->ran = ran;
47 morph->map = map;
48 morph->inv = inv;
49
50 return morph;
51error:
52 isl_basic_set_free(bset: dom);
53 isl_basic_set_free(bset: ran);
54 isl_mat_free(mat: map);
55 isl_mat_free(mat: inv);
56 return NULL;
57}
58
59__isl_give isl_morph *isl_morph_copy(__isl_keep isl_morph *morph)
60{
61 if (!morph)
62 return NULL;
63
64 morph->ref++;
65 return morph;
66}
67
68__isl_give isl_morph *isl_morph_dup(__isl_keep isl_morph *morph)
69{
70 if (!morph)
71 return NULL;
72
73 return isl_morph_alloc(dom: isl_basic_set_copy(bset: morph->dom),
74 ran: isl_basic_set_copy(bset: morph->ran),
75 map: isl_mat_copy(mat: morph->map), inv: isl_mat_copy(mat: morph->inv));
76}
77
78__isl_give isl_morph *isl_morph_cow(__isl_take isl_morph *morph)
79{
80 if (!morph)
81 return NULL;
82
83 if (morph->ref == 1)
84 return morph;
85 morph->ref--;
86 return isl_morph_dup(morph);
87}
88
89__isl_null isl_morph *isl_morph_free(__isl_take isl_morph *morph)
90{
91 if (!morph)
92 return NULL;
93
94 if (--morph->ref > 0)
95 return NULL;
96
97 isl_basic_set_free(bset: morph->dom);
98 isl_basic_set_free(bset: morph->ran);
99 isl_mat_free(mat: morph->map);
100 isl_mat_free(mat: morph->inv);
101 free(ptr: morph);
102
103 return NULL;
104}
105
106/* Is "morph" an identity on the parameters?
107 */
108static isl_bool identity_on_parameters(__isl_keep isl_morph *morph)
109{
110 isl_bool is_identity;
111 isl_size nparam, nparam_ran;
112 isl_mat *sub;
113
114 nparam = isl_morph_dom_dim(morph, type: isl_dim_param);
115 nparam_ran = isl_morph_ran_dim(morph, type: 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;
120 if (nparam == 0)
121 return isl_bool_true;
122 sub = isl_mat_sub_alloc(mat: morph->map, first_row: 0, n_row: 1 + nparam, first_col: 0, n_col: 1 + nparam);
123 is_identity = isl_mat_is_scaled_identity(mat: sub);
124 isl_mat_free(mat: sub);
125
126 return is_identity;
127}
128
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".
131 *
132 * In order for the space manipulations to make sense, we require
133 * that the parameters are not modified by "morph".
134 */
135__isl_give isl_multi_aff *isl_morph_get_var_multi_aff(
136 __isl_keep isl_morph *morph)
137{
138 isl_space *dom, *ran, *space;
139 isl_local_space *ls;
140 isl_multi_aff *ma;
141 isl_size nparam, nvar;
142 int i;
143 isl_bool is_identity;
144
145 if (!morph)
146 return NULL;
147
148 is_identity = identity_on_parameters(morph);
149 if (is_identity < 0)
150 return NULL;
151 if (!is_identity)
152 isl_die(isl_morph_get_ctx(morph), isl_error_invalid,
153 "cannot handle parameter compression", return NULL);
154
155 dom = isl_morph_get_dom_space(morph);
156 ls = isl_local_space_from_space(space: isl_space_copy(space: dom));
157 ran = isl_morph_get_ran_space(morph);
158 space = isl_space_map_from_domain_and_range(domain: dom, range: ran);
159 ma = isl_multi_aff_zero(space);
160
161 nparam = isl_multi_aff_dim(multi: ma, type: isl_dim_param);
162 nvar = isl_multi_aff_dim(multi: ma, type: isl_dim_out);
163 if (nparam < 0 || nvar < 0)
164 ma = isl_multi_aff_free(multi: ma);
165 for (i = 0; i < nvar; ++i) {
166 isl_val *val;
167 isl_vec *v;
168 isl_aff *aff;
169
170 v = isl_mat_get_row(mat: morph->map, row: 1 + nparam + i);
171 v = isl_vec_insert_els(vec: v, pos: 0, n: 1);
172 val = isl_mat_get_element_val(mat: morph->map, row: 0, col: 0);
173 v = isl_vec_set_element_val(vec: v, pos: 0, v: val);
174 aff = isl_aff_alloc_vec(ls: isl_local_space_copy(ls), v);
175 ma = isl_multi_aff_set_aff(multi: ma, pos: i, el: aff);
176 }
177
178 isl_local_space_free(ls);
179 return ma;
180}
181
182/* Return the domain space of "morph".
183 */
184static __isl_keep isl_space *isl_morph_peek_dom_space(
185 __isl_keep isl_morph *morph)
186{
187 if (!morph)
188 return NULL;
189
190 return isl_basic_set_peek_space(bset: morph->dom);
191}
192
193/* Return a copy of the domain space of "morph".
194 */
195__isl_give isl_space *isl_morph_get_dom_space(__isl_keep isl_morph *morph)
196{
197 return isl_space_copy(space: isl_morph_peek_dom_space(morph));
198}
199
200/* Check that the match against "space" with result "match" was successful.
201 */
202static isl_stat check_space_match(__isl_keep isl_space *space, isl_bool match)
203{
204 if (match < 0)
205 return isl_stat_error;
206 if (!match)
207 isl_die(isl_space_get_ctx(space), isl_error_invalid,
208 "spaces don't match", return isl_stat_error);
209
210 return isl_stat_ok;
211}
212
213/* Check that "morph" can be applied to the "space".
214 */
215isl_stat isl_morph_check_applies(__isl_keep isl_morph *morph,
216 __isl_keep isl_space *space)
217{
218 isl_space *dom_space;
219 isl_bool applies;
220
221 dom_space = isl_morph_peek_dom_space(morph);
222 applies = isl_space_is_equal(space1: dom_space, space2: space);
223 return check_space_match(space, match: applies);
224}
225
226__isl_give isl_space *isl_morph_get_ran_space(__isl_keep isl_morph *morph)
227{
228 if (!morph)
229 return NULL;
230
231 return isl_space_copy(space: morph->ran->dim);
232}
233
234isl_size isl_morph_dom_dim(__isl_keep isl_morph *morph, enum isl_dim_type type)
235{
236 if (!morph)
237 return isl_size_error;
238
239 return isl_basic_set_dim(bset: morph->dom, type);
240}
241
242isl_size isl_morph_ran_dim(__isl_keep isl_morph *morph, enum isl_dim_type type)
243{
244 if (!morph)
245 return isl_size_error;
246
247 return isl_basic_set_dim(bset: morph->ran, type);
248}
249
250__isl_give isl_morph *isl_morph_remove_dom_dims(__isl_take isl_morph *morph,
251 enum isl_dim_type type, unsigned first, unsigned n)
252{
253 unsigned dom_offset;
254
255 if (n == 0)
256 return morph;
257
258 morph = isl_morph_cow(morph);
259 if (!morph)
260 return NULL;
261
262 dom_offset = 1 + isl_space_offset(space: morph->dom->dim, type);
263
264 morph->dom = isl_basic_set_remove_dims(bset: morph->dom, type, first, n);
265
266 morph->map = isl_mat_drop_cols(mat: morph->map, col: dom_offset + first, n);
267
268 morph->inv = isl_mat_drop_rows(mat: morph->inv, row: dom_offset + first, n);
269
270 if (morph->dom && morph->ran && morph->map && morph->inv)
271 return morph;
272
273 isl_morph_free(morph);
274 return NULL;
275}
276
277__isl_give isl_morph *isl_morph_remove_ran_dims(__isl_take isl_morph *morph,
278 enum isl_dim_type type, unsigned first, unsigned n)
279{
280 unsigned ran_offset;
281
282 if (n == 0)
283 return morph;
284
285 morph = isl_morph_cow(morph);
286 if (!morph)
287 return NULL;
288
289 ran_offset = 1 + isl_space_offset(space: morph->ran->dim, type);
290
291 morph->ran = isl_basic_set_remove_dims(bset: morph->ran, type, first, n);
292
293 morph->map = isl_mat_drop_rows(mat: morph->map, row: ran_offset + first, n);
294
295 morph->inv = isl_mat_drop_cols(mat: morph->inv, col: ran_offset + first, n);
296
297 if (morph->dom && morph->ran && morph->map && morph->inv)
298 return morph;
299
300 isl_morph_free(morph);
301 return NULL;
302}
303
304/* Project domain of morph onto its parameter domain.
305 */
306__isl_give isl_morph *isl_morph_dom_params(__isl_take isl_morph *morph)
307{
308 isl_size n;
309
310 morph = isl_morph_cow(morph);
311 if (!morph)
312 return NULL;
313 n = isl_basic_set_dim(bset: morph->dom, type: isl_dim_set);
314 if (n < 0)
315 return isl_morph_free(morph);
316 morph = isl_morph_remove_dom_dims(morph, type: isl_dim_set, first: 0, n);
317 if (!morph)
318 return NULL;
319 morph->dom = isl_basic_set_params(bset: morph->dom);
320 if (morph->dom)
321 return morph;
322
323 isl_morph_free(morph);
324 return NULL;
325}
326
327/* Project range of morph onto its parameter domain.
328 */
329__isl_give isl_morph *isl_morph_ran_params(__isl_take isl_morph *morph)
330{
331 isl_size n;
332
333 morph = isl_morph_cow(morph);
334 if (!morph)
335 return NULL;
336 n = isl_basic_set_dim(bset: morph->ran, type: isl_dim_set);
337 if (n < 0)
338 return isl_morph_free(morph);
339 morph = isl_morph_remove_ran_dims(morph, type: isl_dim_set, first: 0, n);
340 if (!morph)
341 return NULL;
342 morph->ran = isl_basic_set_params(bset: morph->ran);
343 if (morph->ran)
344 return morph;
345
346 isl_morph_free(morph);
347 return NULL;
348}
349
350/* Replace the identifier of the tuple of the range of the morph by "id".
351 */
352static __isl_give isl_morph *isl_morph_set_ran_tuple_id(
353 __isl_take isl_morph *morph, __isl_keep isl_id *id)
354{
355 morph = isl_morph_cow(morph);
356 if (!morph)
357 return NULL;
358 morph->ran = isl_basic_set_set_tuple_id(bset: morph->ran, id: isl_id_copy(id));
359 if (!morph->ran)
360 return isl_morph_free(morph);
361 return morph;
362}
363
364void isl_morph_print_internal(__isl_take isl_morph *morph, FILE *out)
365{
366 if (!morph)
367 return;
368
369 isl_basic_set_dump(bset: morph->dom);
370 isl_basic_set_dump(bset: morph->ran);
371 isl_mat_print_internal(mat: morph->map, out, indent: 4);
372 isl_mat_print_internal(mat: morph->inv, out, indent: 4);
373}
374
375void isl_morph_dump(__isl_take isl_morph *morph)
376{
377 isl_morph_print_internal(morph, stderr);
378}
379
380__isl_give isl_morph *isl_morph_identity(__isl_keep isl_basic_set *bset)
381{
382 isl_mat *id;
383 isl_basic_set *universe;
384 isl_size total;
385
386 total = isl_basic_set_dim(bset, type: isl_dim_all);
387 if (total < 0)
388 return NULL;
389
390 id = isl_mat_identity(ctx: bset->ctx, n_row: 1 + total);
391 universe = isl_basic_set_universe(space: isl_space_copy(space: bset->dim));
392
393 return isl_morph_alloc(dom: universe, ran: isl_basic_set_copy(bset: universe),
394 map: id, inv: isl_mat_copy(mat: id));
395}
396
397/* Create a(n identity) morphism between empty sets of the same dimension
398 * a "bset".
399 */
400__isl_give isl_morph *isl_morph_empty(__isl_keep isl_basic_set *bset)
401{
402 isl_mat *id;
403 isl_basic_set *empty;
404 isl_size total;
405
406 total = isl_basic_set_dim(bset, type: isl_dim_all);
407 if (total < 0)
408 return NULL;
409
410 id = isl_mat_identity(ctx: bset->ctx, n_row: 1 + total);
411 empty = isl_basic_set_empty(space: isl_space_copy(space: bset->dim));
412
413 return isl_morph_alloc(dom: empty, ran: isl_basic_set_copy(bset: empty),
414 map: id, inv: isl_mat_copy(mat: id));
415}
416
417/* Construct a basic set described by the "n" equalities of "bset" starting
418 * at "first".
419 */
420static __isl_give isl_basic_set *copy_equalities(__isl_keep isl_basic_set *bset,
421 unsigned first, unsigned n)
422{
423 int i, k;
424 isl_basic_set *eq;
425 isl_size total;
426
427 total = isl_basic_set_dim(bset, type: isl_dim_all);
428 if (total < 0 || isl_basic_set_check_no_locals(bset) < 0)
429 return NULL;
430
431 eq = isl_basic_set_alloc_space(space: isl_basic_set_get_space(bset), extra: 0, n_eq: n, n_ineq: 0);
432 if (!eq)
433 return NULL;
434 for (i = 0; i < n; ++i) {
435 k = isl_basic_set_alloc_equality(bset: eq);
436 if (k < 0)
437 goto error;
438 isl_seq_cpy(dst: eq->eq[k], src: bset->eq[first + i], len: 1 + total);
439 }
440
441 return eq;
442error:
443 isl_basic_set_free(bset: eq);
444 return NULL;
445}
446
447/* Given a basic set, exploit the equalities in the basic set to construct
448 * a morphism that maps the basic set to a lower-dimensional space.
449 * Specifically, the morphism reduces the number of dimensions of type "type".
450 *
451 * We first select the equalities of interest, that is those that involve
452 * variables of type "type" and no later variables.
453 * Denote those equalities as
454 *
455 * -C(p) + M x = 0
456 *
457 * where C(p) depends on the parameters if type == isl_dim_set and
458 * is a constant if type == isl_dim_param.
459 *
460 * Use isl_mat_final_variable_compression to construct a compression
461 *
462 * x = T x'
463 *
464 * x' = Q x
465 *
466 * If T is a zero-column matrix, then the set of equality constraints
467 * do not admit a solution. In this case, an empty morphism is returned.
468 *
469 * Both matrices are extended to map the full original space to the full
470 * compressed space.
471 */
472__isl_give isl_morph *isl_basic_set_variable_compression(
473 __isl_keep isl_basic_set *bset, enum isl_dim_type type)
474{
475 unsigned otype;
476 isl_size ntype;
477 unsigned orest;
478 unsigned nrest;
479 isl_size total;
480 int f_eq, n_eq;
481 isl_space *space;
482 isl_mat *E, *Q, *C;
483 isl_basic_set *dom, *ran;
484
485 if (!bset)
486 return NULL;
487
488 if (isl_basic_set_plain_is_empty(bset))
489 return isl_morph_empty(bset);
490
491 if (isl_basic_set_check_no_locals(bset) < 0)
492 return NULL;
493
494 ntype = isl_basic_set_dim(bset, type);
495 total = isl_basic_set_dim(bset, type: isl_dim_all);
496 if (ntype < 0 || total < 0)
497 return NULL;
498 otype = isl_basic_set_offset(bset, type);
499 orest = otype + ntype;
500 nrest = total - (orest - 1);
501
502 for (f_eq = 0; f_eq < bset->n_eq; ++f_eq)
503 if (isl_seq_first_non_zero(p: bset->eq[f_eq] + orest, len: nrest) == -1)
504 break;
505 for (n_eq = 0; f_eq + n_eq < bset->n_eq; ++n_eq)
506 if (isl_seq_first_non_zero(p: bset->eq[f_eq + n_eq] + otype, len: ntype) == -1)
507 break;
508 if (n_eq == 0)
509 return isl_morph_identity(bset);
510
511 E = isl_mat_sub_alloc6(ctx: bset->ctx, row: bset->eq, first_row: f_eq, n_row: n_eq, first_col: 0, n_col: orest);
512 C = isl_mat_final_variable_compression(B: E, first: otype - 1, T2: &Q);
513 if (!Q)
514 C = isl_mat_free(mat: C);
515 if (C && C->n_col == 0) {
516 isl_mat_free(mat: C);
517 isl_mat_free(mat: Q);
518 return isl_morph_empty(bset);
519 }
520
521 Q = isl_mat_diagonal(mat1: Q, mat2: isl_mat_identity(ctx: bset->ctx, n_row: nrest));
522 C = isl_mat_diagonal(mat1: C, mat2: isl_mat_identity(ctx: bset->ctx, n_row: nrest));
523
524 space = isl_space_copy(space: bset->dim);
525 space = isl_space_drop_dims(space, type, first: 0, num: ntype);
526 space = isl_space_add_dims(space, type, n: ntype - n_eq);
527 ran = isl_basic_set_universe(space);
528 dom = copy_equalities(bset, first: f_eq, n: n_eq);
529
530 return isl_morph_alloc(dom, ran, map: Q, inv: C);
531}
532
533/* Given a basic set, exploit the equalities in the basic set to construct
534 * a morphism that maps the basic set to a lower-dimensional space
535 * with identifier "id".
536 * Specifically, the morphism reduces the number of set dimensions.
537 */
538__isl_give isl_morph *isl_basic_set_variable_compression_with_id(
539 __isl_keep isl_basic_set *bset, __isl_keep isl_id *id)
540{
541 isl_morph *morph;
542
543 morph = isl_basic_set_variable_compression(bset, type: isl_dim_set);
544 morph = isl_morph_set_ran_tuple_id(morph, id);
545 return morph;
546}
547
548/* Construct a parameter compression for "bset".
549 * We basically just call isl_mat_parameter_compression with the right input
550 * and then extend the resulting matrix to include the variables.
551 *
552 * The implementation assumes that "bset" does not have any equalities
553 * that only involve the parameters and that isl_basic_set_gauss has
554 * been applied to "bset".
555 *
556 * Let the equalities be given as
557 *
558 * B(p) + A x = 0.
559 *
560 * We use isl_mat_parameter_compression_ext to compute the compression
561 *
562 * p = T p'.
563 */
564__isl_give isl_morph *isl_basic_set_parameter_compression(
565 __isl_keep isl_basic_set *bset)
566{
567 isl_size nparam;
568 isl_size nvar;
569 isl_size n_div;
570 int n_eq;
571 isl_mat *H, *B;
572 isl_mat *map, *inv;
573 isl_basic_set *dom, *ran;
574
575 if (!bset)
576 return NULL;
577
578 if (isl_basic_set_plain_is_empty(bset))
579 return isl_morph_empty(bset);
580 if (bset->n_eq == 0)
581 return isl_morph_identity(bset);
582
583 n_eq = bset->n_eq;
584 nparam = isl_basic_set_dim(bset, type: isl_dim_param);
585 nvar = isl_basic_set_dim(bset, type: isl_dim_set);
586 n_div = isl_basic_set_dim(bset, type: isl_dim_div);
587 if (nparam < 0 || nvar < 0 || n_div < 0)
588 return NULL;
589
590 if (isl_seq_first_non_zero(p: bset->eq[bset->n_eq - 1] + 1 + nparam,
591 len: nvar + n_div) == -1)
592 isl_die(isl_basic_set_get_ctx(bset), isl_error_invalid,
593 "input not allowed to have parameter equalities",
594 return NULL);
595 if (n_eq > nvar + n_div)
596 isl_die(isl_basic_set_get_ctx(bset), isl_error_invalid,
597 "input not gaussed", return NULL);
598
599 B = isl_mat_sub_alloc6(ctx: bset->ctx, row: bset->eq, first_row: 0, n_row: n_eq, first_col: 0, n_col: 1 + nparam);
600 H = isl_mat_sub_alloc6(ctx: bset->ctx, row: bset->eq,
601 first_row: 0, n_row: n_eq, first_col: 1 + nparam, n_col: nvar + n_div);
602 inv = isl_mat_parameter_compression_ext(B, A: H);
603 inv = isl_mat_diagonal(mat1: inv, mat2: isl_mat_identity(ctx: bset->ctx, n_row: nvar));
604 map = isl_mat_right_inverse(mat: isl_mat_copy(mat: inv));
605
606 dom = isl_basic_set_universe(space: isl_space_copy(space: bset->dim));
607 ran = isl_basic_set_universe(space: isl_space_copy(space: bset->dim));
608
609 return isl_morph_alloc(dom, ran, map, inv);
610}
611
612/* Construct an isl_multi_aff that corresponds
613 * to the affine transformation matrix "mat" and
614 * that lives in an anonymous space.
615 */
616static __isl_give isl_multi_aff *isl_multi_aff_from_aff_mat_anonymous(
617 __isl_take isl_mat *mat)
618{
619 isl_size n_row, n_col;
620 isl_ctx *ctx;
621 isl_space *space;
622
623 ctx = isl_mat_get_ctx(mat);
624 n_row = isl_mat_rows(mat);
625 n_col = isl_mat_cols(mat);
626 if (n_row < 0 || n_col < 0)
627 space = NULL;
628 else
629 space = isl_space_alloc(ctx, nparam: 0, n_in: n_col - 1, n_out: n_row - 1);
630
631 return isl_multi_aff_from_aff_mat(space, mat);
632}
633
634/* Apply the morphism to the basic set.
635 * In particular, compute the preimage of "bset" under the inverse mapping
636 * in morph and intersect with the range of the morphism.
637 * Note that the mapping in morph applies to both parameters and set dimensions,
638 * so the parameters need to be treated as set dimensions during the call
639 * to isl_basic_set_preimage_multi_aff.
640 */
641__isl_give isl_basic_set *isl_morph_basic_set(__isl_take isl_morph *morph,
642 __isl_take isl_basic_set *bset)
643{
644 isl_size n_param;
645 isl_space *space;
646 isl_multi_aff *ma;
647
648 if (!morph || isl_basic_set_check_equal_space(bset1: bset, bset2: morph->dom) < 0)
649 goto error;
650 n_param = isl_basic_set_dim(bset: morph->dom, type: isl_dim_param);
651 if (n_param < 0)
652 goto error;
653
654 ma = isl_multi_aff_from_aff_mat_anonymous(mat: isl_mat_copy(mat: morph->inv));
655
656 bset = isl_basic_set_move_dims(bset, dst_type: isl_dim_set, dst_pos: 0,
657 src_type: isl_dim_param, src_pos: 0, n: n_param);
658 bset = isl_basic_set_preimage_multi_aff(bset, ma);
659 space = isl_basic_set_get_space(bset: morph->ran);
660 bset = isl_basic_set_reset_space(bset, space);
661 bset = isl_basic_set_intersect(bset1: bset, bset2: isl_basic_set_copy(bset: morph->ran));
662
663 isl_morph_free(morph);
664 return bset;
665error:
666 isl_morph_free(morph);
667 isl_basic_set_free(bset);
668 return NULL;
669}
670
671/* Apply the morphism to the set.
672 * In particular, compute the preimage of "set" under the inverse mapping
673 * in morph and intersect with the range of the morphism.
674 * Note that the mapping in morph applies to both parameters and set dimensions,
675 * so the parameters need to be treated as set dimensions during the call
676 * to isl_set_preimage_multi_aff.
677 */
678__isl_give isl_set *isl_morph_set(__isl_take isl_morph *morph,
679 __isl_take isl_set *set)
680{
681 isl_size n_param;
682 isl_space *space;
683 isl_multi_aff *ma;
684 isl_basic_set *ran;
685
686 if (!morph || isl_set_basic_set_check_equal_space(set, bset: morph->dom) < 0)
687 goto error;
688 n_param = isl_basic_set_dim(bset: morph->dom, type: isl_dim_param);
689 if (n_param < 0)
690 goto error;
691
692 ma = isl_multi_aff_from_aff_mat_anonymous(mat: isl_mat_copy(mat: morph->inv));
693
694 set = isl_set_move_dims(set, dst_type: isl_dim_set, dst_pos: 0, src_type: isl_dim_param, src_pos: 0, n: n_param);
695 set = isl_set_preimage_multi_aff(set, ma);
696 space = isl_basic_set_get_space(bset: morph->ran);
697 set = isl_set_reset_space(set, space);
698 ran = isl_basic_set_copy(bset: morph->ran);
699 set = isl_set_intersect(set1: set, set2: isl_set_from_basic_set(bset: ran));
700
701 isl_morph_free(morph);
702 return set;
703error:
704 isl_set_free(set);
705 isl_morph_free(morph);
706 return NULL;
707}
708
709/* Construct a morphism that first does morph2 and then morph1.
710 */
711__isl_give isl_morph *isl_morph_compose(__isl_take isl_morph *morph1,
712 __isl_take isl_morph *morph2)
713{
714 isl_mat *map, *inv;
715 isl_basic_set *dom, *ran;
716
717 if (!morph1 || !morph2)
718 goto error;
719
720 map = isl_mat_product(left: isl_mat_copy(mat: morph1->map), right: isl_mat_copy(mat: morph2->map));
721 inv = isl_mat_product(left: isl_mat_copy(mat: morph2->inv), right: isl_mat_copy(mat: morph1->inv));
722 dom = isl_morph_basic_set(morph: isl_morph_inverse(morph: isl_morph_copy(morph: morph2)),
723 bset: isl_basic_set_copy(bset: morph1->dom));
724 dom = isl_basic_set_intersect(bset1: dom, bset2: isl_basic_set_copy(bset: morph2->dom));
725 ran = isl_morph_basic_set(morph: isl_morph_copy(morph: morph1),
726 bset: isl_basic_set_copy(bset: morph2->ran));
727 ran = isl_basic_set_intersect(bset1: ran, bset2: isl_basic_set_copy(bset: morph1->ran));
728
729 isl_morph_free(morph: morph1);
730 isl_morph_free(morph: morph2);
731
732 return isl_morph_alloc(dom, ran, map, inv);
733error:
734 isl_morph_free(morph: morph1);
735 isl_morph_free(morph: morph2);
736 return NULL;
737}
738
739__isl_give isl_morph *isl_morph_inverse(__isl_take isl_morph *morph)
740{
741 isl_basic_set *bset;
742 isl_mat *mat;
743
744 morph = isl_morph_cow(morph);
745 if (!morph)
746 return NULL;
747
748 bset = morph->dom;
749 morph->dom = morph->ran;
750 morph->ran = bset;
751
752 mat = morph->map;
753 morph->map = morph->inv;
754 morph->inv = mat;
755
756 return morph;
757}
758
759/* We detect all the equalities first to avoid implicit equalities
760 * being discovered during the computations. In particular,
761 * the compression on the variables could expose additional stride
762 * constraints on the parameters. This would result in existentially
763 * quantified variables after applying the resulting morph, which
764 * in turn could break invariants of the calling functions.
765 */
766__isl_give isl_morph *isl_basic_set_full_compression(
767 __isl_keep isl_basic_set *bset)
768{
769 isl_morph *morph, *morph2;
770
771 bset = isl_basic_set_copy(bset);
772 bset = isl_basic_set_detect_equalities(bset);
773
774 morph = isl_basic_set_variable_compression(bset, type: isl_dim_param);
775 bset = isl_morph_basic_set(morph: isl_morph_copy(morph), bset);
776
777 morph2 = isl_basic_set_parameter_compression(bset);
778 bset = isl_morph_basic_set(morph: isl_morph_copy(morph: morph2), bset);
779
780 morph = isl_morph_compose(morph1: morph2, morph2: morph);
781
782 morph2 = isl_basic_set_variable_compression(bset, type: isl_dim_set);
783 isl_basic_set_free(bset);
784
785 morph = isl_morph_compose(morph1: morph2, morph2: morph);
786
787 return morph;
788}
789
790__isl_give isl_vec *isl_morph_vec(__isl_take isl_morph *morph,
791 __isl_take isl_vec *vec)
792{
793 if (!morph)
794 goto error;
795
796 vec = isl_mat_vec_product(mat: isl_mat_copy(mat: morph->map), vec);
797
798 isl_morph_free(morph);
799 return vec;
800error:
801 isl_morph_free(morph);
802 isl_vec_free(vec);
803 return NULL;
804}
805

source code of polly/lib/External/isl/isl_morph.c