?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
add isl_local_space_is_params
[isl.git] / isl_local_space.c
blobd02cd20557998dcd2374fecb2ca468e1b0fec592
1 /*
2 * Copyright 2011 INRIA Saclay
3 * Copyright 2012-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_ctx_private.h>
14 #include <isl_map_private.h>
15 #include <isl_local_space_private.h>
16 #include <isl_space_private.h>
17 #include <isl_mat_private.h>
18 #include <isl_aff_private.h>
19 #include <isl_vec_private.h>
20 #include <isl_seq.h>
21
22 isl_ctx *isl_local_space_get_ctx(__isl_keep isl_local_space *ls)
23 {
24 return ls ? ls->dim->ctx : NULL;
25 }
26
27 __isl_give isl_local_space *isl_local_space_alloc_div(__isl_take isl_space *dim,
28 __isl_take isl_mat *div)
29 {
30 isl_ctx *ctx;
31 isl_local_space *ls = NULL;
32
33 if (!dim || !div)
34 goto error;
35
36 ctx = isl_space_get_ctx(dim);
37 ls = isl_calloc_type(ctx, struct isl_local_space);
38 if (!ls)
39 goto error;
40
41 ls->ref = 1;
42 ls->dim = dim;
43 ls->div = div;
44
45 return ls;
46 error:
47 isl_mat_free(div);
48 isl_space_free(dim);
49 isl_local_space_free(ls);
50 return NULL;
51 }
52
53 __isl_give isl_local_space *isl_local_space_alloc(__isl_take isl_space *dim,
54 unsigned n_div)
55 {
56 isl_ctx *ctx;
57 isl_mat *div;
58 unsigned total;
59
60 if (!dim)
61 return NULL;
62
63 total = isl_space_dim(dim, isl_dim_all);
64
65 ctx = isl_space_get_ctx(dim);
66 div = isl_mat_alloc(ctx, n_div, 1 + 1 + total + n_div);
67 return isl_local_space_alloc_div(dim, div);
68 }
69
70 __isl_give isl_local_space *isl_local_space_from_space(__isl_take isl_space *dim)
71 {
72 return isl_local_space_alloc(dim, 0);
73 }
74
75 __isl_give isl_local_space *isl_local_space_copy(__isl_keep isl_local_space *ls)
76 {
77 if (!ls)
78 return NULL;
79
80 ls->ref++;
81 return ls;
82 }
83
84 __isl_give isl_local_space *isl_local_space_dup(__isl_keep isl_local_space *ls)
85 {
86 if (!ls)
87 return NULL;
88
89 return isl_local_space_alloc_div(isl_space_copy(ls->dim),
90 isl_mat_copy(ls->div));
91
92 }
93
94 __isl_give isl_local_space *isl_local_space_cow(__isl_take isl_local_space *ls)
95 {
96 if (!ls)
97 return NULL;
98
99 if (ls->ref == 1)
100 return ls;
101 ls->ref--;
102 return isl_local_space_dup(ls);
103 }
104
105 __isl_null isl_local_space *isl_local_space_free(
106 __isl_take isl_local_space *ls)
107 {
108 if (!ls)
109 return NULL;
110
111 if (--ls->ref > 0)
112 return NULL;
113
114 isl_space_free(ls->dim);
115 isl_mat_free(ls->div);
116
117 free(ls);
118
119 return NULL;
120 }
121
122 /* Is the local space that of a parameter domain?
123 */
124 int isl_local_space_is_params(__isl_keep isl_local_space *ls)
125 {
126 if (!ls)
127 return -1;
128 return isl_space_is_params(ls->dim);
129 }
130
131 /* Is the local space that of a set?
132 */
133 int isl_local_space_is_set(__isl_keep isl_local_space *ls)
134 {
135 return ls ? isl_space_is_set(ls->dim) : -1;
136 }
137
138 /* Return true if the two local spaces are identical, with identical
139 * expressions for the integer divisions.
140 */
141 int isl_local_space_is_equal(__isl_keep isl_local_space *ls1,
142 __isl_keep isl_local_space *ls2)
143 {
144 int equal;
145
146 if (!ls1 || !ls2)
147 return -1;
148
149 equal = isl_space_is_equal(ls1->dim, ls2->dim);
150 if (equal < 0 || !equal)
151 return equal;
152
153 if (!isl_local_space_divs_known(ls1))
154 return 0;
155 if (!isl_local_space_divs_known(ls2))
156 return 0;
157
158 return isl_mat_is_equal(ls1->div, ls2->div);
159 }
160
161 /* Compare two isl_local_spaces.
162 *
163 * Return -1 if "ls1" is "smaller" than "ls2", 1 if "ls1" is "greater"
164 * than "ls2" and 0 if they are equal.
165 *
166 * The order is fairly arbitrary. We do "prefer" divs that only involve
167 * earlier dimensions in the sense that we consider local spaces where
168 * the first differing div involves earlier dimensions to be smaller.
169 */
170 int isl_local_space_cmp(__isl_keep isl_local_space *ls1,
171 __isl_keep isl_local_space *ls2)
172 {
173 int i;
174 int cmp;
175 int known1, known2;
176 int last1, last2;
177 int n_col;
178
179 if (ls1 == ls2)
180 return 0;
181 if (!ls1)
182 return -1;
183 if (!ls2)
184 return 1;
185
186 cmp = isl_space_cmp(ls1->dim, ls2->dim);
187 if (cmp != 0)
188 return cmp;
189
190 if (ls1->div->n_row != ls2->div->n_row)
191 return ls1->div->n_row - ls2->div->n_row;
192
193 n_col = isl_mat_cols(ls1->div);
194 for (i = 0; i < ls1->div->n_row; ++i) {
195 known1 = isl_local_space_div_is_known(ls1, i);
196 known2 = isl_local_space_div_is_known(ls2, i);
197 if (!known1 && !known2)
198 continue;
199 if (!known1)
200 return 1;
201 if (!known2)
202 return -1;
203 last1 = isl_seq_last_non_zero(ls1->div->row[i] + 1, n_col - 1);
204 last2 = isl_seq_last_non_zero(ls2->div->row[i] + 1, n_col - 1);
205 if (last1 != last2)
206 return last1 - last2;
207 cmp = isl_seq_cmp(ls1->div->row[i], ls2->div->row[i], n_col);
208 if (cmp != 0)
209 return cmp;
210 }
211
212 return 0;
213 }
214
215 int isl_local_space_dim(__isl_keep isl_local_space *ls,
216 enum isl_dim_type type)
217 {
218 if (!ls)
219 return 0;
220 if (type == isl_dim_div)
221 return ls->div->n_row;
222 if (type == isl_dim_all)
223 return isl_space_dim(ls->dim, isl_dim_all) + ls->div->n_row;
224 return isl_space_dim(ls->dim, type);
225 }
226
227 unsigned isl_local_space_offset(__isl_keep isl_local_space *ls,
228 enum isl_dim_type type)
229 {
230 isl_space *dim;
231
232 if (!ls)
233 return 0;
234
235 dim = ls->dim;
236 switch (type) {
237 case isl_dim_cst: return 0;
238 case isl_dim_param: return 1;
239 case isl_dim_in: return 1 + dim->nparam;
240 case isl_dim_out: return 1 + dim->nparam + dim->n_in;
241 case isl_dim_div: return 1 + dim->nparam + dim->n_in + dim->n_out;
242 default: return 0;
243 }
244 }
245
246 /* Does the given dimension have a name?
247 */
248 int isl_local_space_has_dim_name(__isl_keep isl_local_space *ls,
249 enum isl_dim_type type, unsigned pos)
250 {
251 return ls ? isl_space_has_dim_name(ls->dim, type, pos) : -1;
252 }
253
254 const char *isl_local_space_get_dim_name(__isl_keep isl_local_space *ls,
255 enum isl_dim_type type, unsigned pos)
256 {
257 return ls ? isl_space_get_dim_name(ls->dim, type, pos) : NULL;
258 }
259
260 int isl_local_space_has_dim_id(__isl_keep isl_local_space *ls,
261 enum isl_dim_type type, unsigned pos)
262 {
263 return ls ? isl_space_has_dim_id(ls->dim, type, pos) : -1;
264 }
265
266 __isl_give isl_id *isl_local_space_get_dim_id(__isl_keep isl_local_space *ls,
267 enum isl_dim_type type, unsigned pos)
268 {
269 return ls ? isl_space_get_dim_id(ls->dim, type, pos) : NULL;
270 }
271
272 __isl_give isl_aff *isl_local_space_get_div(__isl_keep isl_local_space *ls,
273 int pos)
274 {
275 isl_aff *aff;
276
277 if (!ls)
278 return NULL;
279
280 if (pos < 0 || pos >= ls->div->n_row)
281 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
282 "index out of bounds", return NULL);
283
284 if (isl_int_is_zero(ls->div->row[pos][0]))
285 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
286 "expression of div unknown", return NULL);
287 if (!isl_local_space_is_set(ls))
288 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
289 "cannot represent divs of map spaces", return NULL);
290
291 aff = isl_aff_alloc(isl_local_space_copy(ls));
292 if (!aff)
293 return NULL;
294 isl_seq_cpy(aff->v->el, ls->div->row[pos], aff->v->size);
295 return aff;
296 }
297
298 __isl_give isl_space *isl_local_space_get_space(__isl_keep isl_local_space *ls)
299 {
300 if (!ls)
301 return NULL;
302
303 return isl_space_copy(ls->dim);
304 }
305
306 /* Replace the identifier of the tuple of type "type" by "id".
307 */
308 __isl_give isl_local_space *isl_local_space_set_tuple_id(
309 __isl_take isl_local_space *ls,
310 enum isl_dim_type type, __isl_take isl_id *id)
311 {
312 ls = isl_local_space_cow(ls);
313 if (!ls)
314 goto error;
315 ls->dim = isl_space_set_tuple_id(ls->dim, type, id);
316 if (!ls->dim)
317 return isl_local_space_free(ls);
318 return ls;
319 error:
320 isl_id_free(id);
321 return NULL;
322 }
323
324 __isl_give isl_local_space *isl_local_space_set_dim_name(
325 __isl_take isl_local_space *ls,
326 enum isl_dim_type type, unsigned pos, const char *s)
327 {
328 ls = isl_local_space_cow(ls);
329 if (!ls)
330 return NULL;
331 ls->dim = isl_space_set_dim_name(ls->dim, type, pos, s);
332 if (!ls->dim)
333 return isl_local_space_free(ls);
334
335 return ls;
336 }
337
338 __isl_give isl_local_space *isl_local_space_set_dim_id(
339 __isl_take isl_local_space *ls,
340 enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
341 {
342 ls = isl_local_space_cow(ls);
343 if (!ls)
344 goto error;
345 ls->dim = isl_space_set_dim_id(ls->dim, type, pos, id);
346 if (!ls->dim)
347 return isl_local_space_free(ls);
348
349 return ls;
350 error:
351 isl_id_free(id);
352 return NULL;
353 }
354
355 __isl_give isl_local_space *isl_local_space_reset_space(
356 __isl_take isl_local_space *ls, __isl_take isl_space *dim)
357 {
358 ls = isl_local_space_cow(ls);
359 if (!ls || !dim)
360 goto error;
361
362 isl_space_free(ls->dim);
363 ls->dim = dim;
364
365 return ls;
366 error:
367 isl_local_space_free(ls);
368 isl_space_free(dim);
369 return NULL;
370 }
371
372 /* Reorder the columns of the given div definitions according to the
373 * given reordering.
374 * The order of the divs themselves is assumed not to change.
375 */
376 static __isl_give isl_mat *reorder_divs(__isl_take isl_mat *div,
377 __isl_take isl_reordering *r)
378 {
379 int i, j;
380 isl_mat *mat;
381 int extra;
382
383 if (!div || !r)
384 goto error;
385
386 extra = isl_space_dim(r->dim, isl_dim_all) + div->n_row - r->len;
387 mat = isl_mat_alloc(div->ctx, div->n_row, div->n_col + extra);
388 if (!mat)
389 goto error;
390
391 for (i = 0; i < div->n_row; ++i) {
392 isl_seq_cpy(mat->row[i], div->row[i], 2);
393 isl_seq_clr(mat->row[i] + 2, mat->n_col - 2);
394 for (j = 0; j < r->len; ++j)
395 isl_int_set(mat->row[i][2 + r->pos[j]],
396 div->row[i][2 + j]);
397 }
398
399 isl_reordering_free(r);
400 isl_mat_free(div);
401 return mat;
402 error:
403 isl_reordering_free(r);
404 isl_mat_free(div);
405 return NULL;
406 }
407
408 /* Reorder the dimensions of "ls" according to the given reordering.
409 * The reordering r is assumed to have been extended with the local
410 * variables, leaving them in the same order.
411 */
412 __isl_give isl_local_space *isl_local_space_realign(
413 __isl_take isl_local_space *ls, __isl_take isl_reordering *r)
414 {
415 ls = isl_local_space_cow(ls);
416 if (!ls || !r)
417 goto error;
418
419 ls->div = reorder_divs(ls->div, isl_reordering_copy(r));
420 if (!ls->div)
421 goto error;
422
423 ls = isl_local_space_reset_space(ls, isl_space_copy(r->dim));
424
425 isl_reordering_free(r);
426 return ls;
427 error:
428 isl_local_space_free(ls);
429 isl_reordering_free(r);
430 return NULL;
431 }
432
433 __isl_give isl_local_space *isl_local_space_add_div(
434 __isl_take isl_local_space *ls, __isl_take isl_vec *div)
435 {
436 ls = isl_local_space_cow(ls);
437 if (!ls || !div)
438 goto error;
439
440 if (ls->div->n_col != div->size)
441 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
442 "incompatible dimensions", goto error);
443
444 ls->div = isl_mat_add_zero_cols(ls->div, 1);
445 ls->div = isl_mat_add_rows(ls->div, 1);
446 if (!ls->div)
447 goto error;
448
449 isl_seq_cpy(ls->div->row[ls->div->n_row - 1], div->el, div->size);
450 isl_int_set_si(ls->div->row[ls->div->n_row - 1][div->size], 0);
451
452 isl_vec_free(div);
453 return ls;
454 error:
455 isl_local_space_free(ls);
456 isl_vec_free(div);
457 return NULL;
458 }
459
460 __isl_give isl_local_space *isl_local_space_replace_divs(
461 __isl_take isl_local_space *ls, __isl_take isl_mat *div)
462 {
463 ls = isl_local_space_cow(ls);
464
465 if (!ls || !div)
466 goto error;
467
468 isl_mat_free(ls->div);
469 ls->div = div;
470 return ls;
471 error:
472 isl_mat_free(div);
473 isl_local_space_free(ls);
474 return NULL;
475 }
476
477 /* Copy row "s" of "src" to row "d" of "dst", applying the expansion
478 * defined by "exp".
479 */
480 static void expand_row(__isl_keep isl_mat *dst, int d,
481 __isl_keep isl_mat *src, int s, int *exp)
482 {
483 int i;
484 unsigned c = src->n_col - src->n_row;
485
486 isl_seq_cpy(dst->row[d], src->row[s], c);
487 isl_seq_clr(dst->row[d] + c, dst->n_col - c);
488
489 for (i = 0; i < s; ++i)
490 isl_int_set(dst->row[d][c + exp[i]], src->row[s][c + i]);
491 }
492
493 /* Compare (known) divs.
494 * Return non-zero if at least one of the two divs is unknown.
495 * In particular, if both divs are unknown, we respect their
496 * current order. Otherwise, we sort the known div after the unknown
497 * div only if the known div depends on the unknown div.
498 */
499 static int cmp_row(isl_int *row_i, isl_int *row_j, int i, int j,
500 unsigned n_row, unsigned n_col)
501 {
502 int li, lj;
503 int unknown_i, unknown_j;
504
505 unknown_i = isl_int_is_zero(row_i[0]);
506 unknown_j = isl_int_is_zero(row_j[0]);
507
508 if (unknown_i && unknown_j)
509 return i - j;
510
511 if (unknown_i)
512 li = n_col - n_row + i;
513 else
514 li = isl_seq_last_non_zero(row_i, n_col);
515 if (unknown_j)
516 lj = n_col - n_row + j;
517 else
518 lj = isl_seq_last_non_zero(row_j, n_col);
519
520 if (li != lj)
521 return li - lj;
522
523 return isl_seq_cmp(row_i, row_j, n_col);
524 }
525
526 /* Call cmp_row for divs in a matrix.
527 */
528 int isl_mat_cmp_div(__isl_keep isl_mat *div, int i, int j)
529 {
530 return cmp_row(div->row[i], div->row[j], i, j, div->n_row, div->n_col);
531 }
532
533 /* Call cmp_row for divs in a basic map.
534 */
535 static int bmap_cmp_row(__isl_keep isl_basic_map *bmap, int i, int j,
536 unsigned total)
537 {
538 return cmp_row(bmap->div[i], bmap->div[j], i, j, bmap->n_div, total);
539 }
540
541 /* Sort the divs in "bmap".
542 *
543 * We first make sure divs are placed after divs on which they depend.
544 * Then we perform a simple insertion sort based on the same ordering
545 * that is used in isl_merge_divs.
546 */
547 __isl_give isl_basic_map *isl_basic_map_sort_divs(
548 __isl_take isl_basic_map *bmap)
549 {
550 int i, j;
551 unsigned total;
552
553 bmap = isl_basic_map_order_divs(bmap);
554 if (!bmap)
555 return NULL;
556 if (bmap->n_div <= 1)
557 return bmap;
558
559 total = 2 + isl_basic_map_total_dim(bmap);
560 for (i = 1; i < bmap->n_div; ++i) {
561 for (j = i - 1; j >= 0; --j) {
562 if (bmap_cmp_row(bmap, j, j + 1, total) <= 0)
563 break;
564 isl_basic_map_swap_div(bmap, j, j + 1);
565 }
566 }
567
568 return bmap;
569 }
570
571 /* Sort the divs in the basic maps of "map".
572 */
573 __isl_give isl_map *isl_map_sort_divs(__isl_take isl_map *map)
574 {
575 return isl_map_inline_foreach_basic_map(map, &isl_basic_map_sort_divs);
576 }
577
578 /* Combine the two lists of divs into a single list.
579 * For each row i in div1, exp1[i] is set to the position of the corresponding
580 * row in the result. Similarly for div2 and exp2.
581 * This function guarantees
582 * exp1[i] >= i
583 * exp1[i+1] > exp1[i]
584 * For optimal merging, the two input list should have been sorted.
585 */
586 __isl_give isl_mat *isl_merge_divs(__isl_keep isl_mat *div1,
587 __isl_keep isl_mat *div2, int *exp1, int *exp2)
588 {
589 int i, j, k;
590 isl_mat *div = NULL;
591 unsigned d;
592
593 if (!div1 || !div2)
594 return NULL;
595
596 d = div1->n_col - div1->n_row;
597 div = isl_mat_alloc(div1->ctx, 1 + div1->n_row + div2->n_row,
598 d + div1->n_row + div2->n_row);
599 if (!div)
600 return NULL;
601
602 for (i = 0, j = 0, k = 0; i < div1->n_row && j < div2->n_row; ++k) {
603 int cmp;
604
605 expand_row(div, k, div1, i, exp1);
606 expand_row(div, k + 1, div2, j, exp2);
607
608 cmp = isl_mat_cmp_div(div, k, k + 1);
609 if (cmp == 0) {
610 exp1[i++] = k;
611 exp2[j++] = k;
612 } else if (cmp < 0) {
613 exp1[i++] = k;
614 } else {
615 exp2[j++] = k;
616 isl_seq_cpy(div->row[k], div->row[k + 1], div->n_col);
617 }
618 }
619 for (; i < div1->n_row; ++i, ++k) {
620 expand_row(div, k, div1, i, exp1);
621 exp1[i] = k;
622 }
623 for (; j < div2->n_row; ++j, ++k) {
624 expand_row(div, k, div2, j, exp2);
625 exp2[j] = k;
626 }
627
628 div->n_row = k;
629 div->n_col = d + k;
630
631 return div;
632 }
633
634 /* Swap divs "a" and "b" in "ls".
635 */
636 __isl_give isl_local_space *isl_local_space_swap_div(
637 __isl_take isl_local_space *ls, int a, int b)
638 {
639 int offset;
640
641 ls = isl_local_space_cow(ls);
642 if (!ls)
643 return NULL;
644 if (a < 0 || a >= ls->div->n_row || b < 0 || b >= ls->div->n_row)
645 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
646 "index out of bounds", return isl_local_space_free(ls));
647 offset = ls->div->n_col - ls->div->n_row;
648 ls->div = isl_mat_swap_cols(ls->div, offset + a, offset + b);
649 ls->div = isl_mat_swap_rows(ls->div, a, b);
650 if (!ls->div)
651 return isl_local_space_free(ls);
652 return ls;
653 }
654
655 /* Construct a local space that contains all the divs in either
656 * "ls1" or "ls2".
657 */
658 __isl_give isl_local_space *isl_local_space_intersect(
659 __isl_take isl_local_space *ls1, __isl_take isl_local_space *ls2)
660 {
661 isl_ctx *ctx;
662 int *exp1 = NULL;
663 int *exp2 = NULL;
664 isl_mat *div;
665 int equal;
666
667 if (!ls1 || !ls2)
668 goto error;
669
670 ctx = isl_local_space_get_ctx(ls1);
671 if (!isl_space_is_equal(ls1->dim, ls2->dim))
672 isl_die(ctx, isl_error_invalid,
673 "spaces should be identical", goto error);
674
675 if (ls2->div->n_row == 0) {
676 isl_local_space_free(ls2);
677 return ls1;
678 }
679
680 if (ls1->div->n_row == 0) {
681 isl_local_space_free(ls1);
682 return ls2;
683 }
684
685 exp1 = isl_alloc_array(ctx, int, ls1->div->n_row);
686 exp2 = isl_alloc_array(ctx, int, ls2->div->n_row);
687 if (!exp1 || !exp2)
688 goto error;
689
690 div = isl_merge_divs(ls1->div, ls2->div, exp1, exp2);
691 if (!div)
692 goto error;
693
694 equal = isl_mat_is_equal(ls1->div, div);
695 if (equal < 0)
696 goto error;
697 if (!equal)
698 ls1 = isl_local_space_cow(ls1);
699 if (!ls1)
700 goto error;
701
702 free(exp1);
703 free(exp2);
704 isl_local_space_free(ls2);
705 isl_mat_free(ls1->div);
706 ls1->div = div;
707
708 return ls1;
709 error:
710 free(exp1);
711 free(exp2);
712 isl_local_space_free(ls1);
713 isl_local_space_free(ls2);
714 return NULL;
715 }
716
717 /* Does "ls" have an explicit representation for div "div"?
718 */
719 int isl_local_space_div_is_known(__isl_keep isl_local_space *ls, int div)
720 {
721 if (!ls)
722 return -1;
723 if (div < 0 || div >= ls->div->n_row)
724 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
725 "position out of bounds", return -1);
726 return !isl_int_is_zero(ls->div->row[div][0]);
727 }
728
729 int isl_local_space_divs_known(__isl_keep isl_local_space *ls)
730 {
731 int i;
732
733 if (!ls)
734 return -1;
735
736 for (i = 0; i < ls->div->n_row; ++i)
737 if (isl_int_is_zero(ls->div->row[i][0]))
738 return 0;
739
740 return 1;
741 }
742
743 __isl_give isl_local_space *isl_local_space_domain(
744 __isl_take isl_local_space *ls)
745 {
746 ls = isl_local_space_drop_dims(ls, isl_dim_out,
747 0, isl_local_space_dim(ls, isl_dim_out));
748 ls = isl_local_space_cow(ls);
749 if (!ls)
750 return NULL;
751 ls->dim = isl_space_domain(ls->dim);
752 if (!ls->dim)
753 return isl_local_space_free(ls);
754 return ls;
755 }
756
757 __isl_give isl_local_space *isl_local_space_range(
758 __isl_take isl_local_space *ls)
759 {
760 ls = isl_local_space_drop_dims(ls, isl_dim_in,
761 0, isl_local_space_dim(ls, isl_dim_in));
762 ls = isl_local_space_cow(ls);
763 if (!ls)
764 return NULL;
765
766 ls->dim = isl_space_range(ls->dim);
767 if (!ls->dim)
768 return isl_local_space_free(ls);
769 return ls;
770 }
771
772 /* Construct a local space for a map that has the given local
773 * space as domain and that has a zero-dimensional range.
774 */
775 __isl_give isl_local_space *isl_local_space_from_domain(
776 __isl_take isl_local_space *ls)
777 {
778 ls = isl_local_space_cow(ls);
779 if (!ls)
780 return NULL;
781 ls->dim = isl_space_from_domain(ls->dim);
782 if (!ls->dim)
783 return isl_local_space_free(ls);
784 return ls;
785 }
786
787 __isl_give isl_local_space *isl_local_space_add_dims(
788 __isl_take isl_local_space *ls, enum isl_dim_type type, unsigned n)
789 {
790 int pos;
791
792 if (!ls)
793 return NULL;
794 pos = isl_local_space_dim(ls, type);
795 return isl_local_space_insert_dims(ls, type, pos, n);
796 }
797
798 /* Remove common factor of non-constant terms and denominator.
799 */
800 static void normalize_div(__isl_keep isl_local_space *ls, int div)
801 {
802 isl_ctx *ctx = ls->div->ctx;
803 unsigned total = ls->div->n_col - 2;
804
805 isl_seq_gcd(ls->div->row[div] + 2, total, &ctx->normalize_gcd);
806 isl_int_gcd(ctx->normalize_gcd,
807 ctx->normalize_gcd, ls->div->row[div][0]);
808 if (isl_int_is_one(ctx->normalize_gcd))
809 return;
810
811 isl_seq_scale_down(ls->div->row[div] + 2, ls->div->row[div] + 2,
812 ctx->normalize_gcd, total);
813 isl_int_divexact(ls->div->row[div][0], ls->div->row[div][0],
814 ctx->normalize_gcd);
815 isl_int_fdiv_q(ls->div->row[div][1], ls->div->row[div][1],
816 ctx->normalize_gcd);
817 }
818
819 /* Exploit the equalities in "eq" to simplify the expressions of
820 * the integer divisions in "ls".
821 * The integer divisions in "ls" are assumed to appear as regular
822 * dimensions in "eq".
823 */
824 __isl_give isl_local_space *isl_local_space_substitute_equalities(
825 __isl_take isl_local_space *ls, __isl_take isl_basic_set *eq)
826 {
827 int i, j, k;
828 unsigned total;
829 unsigned n_div;
830
831 if (!ls || !eq)
832 goto error;
833
834 total = isl_space_dim(eq->dim, isl_dim_all);
835 if (isl_local_space_dim(ls, isl_dim_all) != total)
836 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
837 "spaces don't match", goto error);
838 total++;
839 n_div = eq->n_div;
840 for (i = 0; i < eq->n_eq; ++i) {
841 j = isl_seq_last_non_zero(eq->eq[i], total + n_div);
842 if (j < 0 || j == 0 || j >= total)
843 continue;
844
845 for (k = 0; k < ls->div->n_row; ++k) {
846 if (isl_int_is_zero(ls->div->row[k][1 + j]))
847 continue;
848 ls = isl_local_space_cow(ls);
849 if (!ls)
850 goto error;
851 ls->div = isl_mat_cow(ls->div);
852 if (!ls->div)
853 goto error;
854 isl_seq_elim(ls->div->row[k] + 1, eq->eq[i], j, total,
855 &ls->div->row[k][0]);
856 normalize_div(ls, k);
857 }
858 }
859
860 isl_basic_set_free(eq);
861 return ls;
862 error:
863 isl_basic_set_free(eq);
864 isl_local_space_free(ls);
865 return NULL;
866 }
867
868 /* Plug in the affine expressions "subs" of length "subs_len" (including
869 * the denominator and the constant term) into the variable at position "pos"
870 * of the "n" div expressions starting at "first".
871 *
872 * Let i be the dimension to replace and let "subs" be of the form
873 *
874 * f/d
875 *
876 * Any integer division starting at "first" with a non-zero coefficient for i,
877 *
878 * floor((a i + g)/m)
879 *
880 * is replaced by
881 *
882 * floor((a f + d g)/(m d))
883 */
884 __isl_give isl_local_space *isl_local_space_substitute_seq(
885 __isl_take isl_local_space *ls,
886 enum isl_dim_type type, unsigned pos, isl_int *subs, int subs_len,
887 int first, int n)
888 {
889 int i;
890 isl_int v;
891
892 if (n == 0)
893 return ls;
894 ls = isl_local_space_cow(ls);
895 if (!ls)
896 return NULL;
897 ls->div = isl_mat_cow(ls->div);
898 if (!ls->div)
899 return isl_local_space_free(ls);
900
901 if (first + n > ls->div->n_row)
902 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
903 "index out of bounds", return isl_local_space_free(ls));
904
905 pos += isl_local_space_offset(ls, type);
906
907 isl_int_init(v);
908 for (i = first; i < ls->div->n_row; ++i) {
909 if (isl_int_is_zero(ls->div->row[i][1 + pos]))
910 continue;
911 isl_seq_substitute(ls->div->row[i], pos, subs,
912 ls->div->n_col, subs_len, v);
913 normalize_div(ls, i);
914 }
915 isl_int_clear(v);
916
917 return ls;
918 }
919
920 /* Plug in "subs" for dimension "type", "pos" in the integer divisions
921 * of "ls".
922 *
923 * Let i be the dimension to replace and let "subs" be of the form
924 *
925 * f/d
926 *
927 * Any integer division with a non-zero coefficient for i,
928 *
929 * floor((a i + g)/m)
930 *
931 * is replaced by
932 *
933 * floor((a f + d g)/(m d))
934 */
935 __isl_give isl_local_space *isl_local_space_substitute(
936 __isl_take isl_local_space *ls,
937 enum isl_dim_type type, unsigned pos, __isl_keep isl_aff *subs)
938 {
939 ls = isl_local_space_cow(ls);
940 if (!ls || !subs)
941 return isl_local_space_free(ls);
942
943 if (!isl_space_is_equal(ls->dim, subs->ls->dim))
944 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
945 "spaces don't match", return isl_local_space_free(ls));
946 if (isl_local_space_dim(subs->ls, isl_dim_div) != 0)
947 isl_die(isl_local_space_get_ctx(ls), isl_error_unsupported,
948 "cannot handle divs yet",
949 return isl_local_space_free(ls));
950
951 return isl_local_space_substitute_seq(ls, type, pos, subs->v->el,
952 subs->v->size, 0, ls->div->n_row);
953 }
954
955 int isl_local_space_is_named_or_nested(__isl_keep isl_local_space *ls,
956 enum isl_dim_type type)
957 {
958 if (!ls)
959 return -1;
960 return isl_space_is_named_or_nested(ls->dim, type);
961 }
962
963 __isl_give isl_local_space *isl_local_space_drop_dims(
964 __isl_take isl_local_space *ls,
965 enum isl_dim_type type, unsigned first, unsigned n)
966 {
967 isl_ctx *ctx;
968
969 if (!ls)
970 return NULL;
971 if (n == 0 && !isl_local_space_is_named_or_nested(ls, type))
972 return ls;
973
974 ctx = isl_local_space_get_ctx(ls);
975 if (first + n > isl_local_space_dim(ls, type))
976 isl_die(ctx, isl_error_invalid, "range out of bounds",
977 return isl_local_space_free(ls));
978
979 ls = isl_local_space_cow(ls);
980 if (!ls)
981 return NULL;
982
983 if (type == isl_dim_div) {
984 ls->div = isl_mat_drop_rows(ls->div, first, n);
985 } else {
986 ls->dim = isl_space_drop_dims(ls->dim, type, first, n);
987 if (!ls->dim)
988 return isl_local_space_free(ls);
989 }
990
991 first += 1 + isl_local_space_offset(ls, type);
992 ls->div = isl_mat_drop_cols(ls->div, first, n);
993 if (!ls->div)
994 return isl_local_space_free(ls);
995
996 return ls;
997 }
998
999 __isl_give isl_local_space *isl_local_space_insert_dims(
1000 __isl_take isl_local_space *ls,
1001 enum isl_dim_type type, unsigned first, unsigned n)
1002 {
1003 isl_ctx *ctx;
1004
1005 if (!ls)
1006 return NULL;
1007 if (n == 0 && !isl_local_space_is_named_or_nested(ls, type))
1008 return ls;
1009
1010 ctx = isl_local_space_get_ctx(ls);
1011 if (first > isl_local_space_dim(ls, type))
1012 isl_die(ctx, isl_error_invalid, "position out of bounds",
1013 return isl_local_space_free(ls));
1014
1015 ls = isl_local_space_cow(ls);
1016 if (!ls)
1017 return NULL;
1018
1019 if (type == isl_dim_div) {
1020 ls->div = isl_mat_insert_zero_rows(ls->div, first, n);
1021 } else {
1022 ls->dim = isl_space_insert_dims(ls->dim, type, first, n);
1023 if (!ls->dim)
1024 return isl_local_space_free(ls);
1025 }
1026
1027 first += 1 + isl_local_space_offset(ls, type);
1028 ls->div = isl_mat_insert_zero_cols(ls->div, first, n);
1029 if (!ls->div)
1030 return isl_local_space_free(ls);
1031
1032 return ls;
1033 }
1034
1035 /* Check if the constraints pointed to by "constraint" is a div
1036 * constraint corresponding to div "div" in "ls".
1037 *
1038 * That is, if div = floor(f/m), then check if the constraint is
1039 *
1040 * f - m d >= 0
1041 * or
1042 * -(f-(m-1)) + m d >= 0
1043 */
1044 int isl_local_space_is_div_constraint(__isl_keep isl_local_space *ls,
1045 isl_int *constraint, unsigned div)
1046 {
1047 unsigned pos;
1048
1049 if (!ls)
1050 return -1;
1051
1052 if (isl_int_is_zero(ls->div->row[div][0]))
1053 return 0;
1054
1055 pos = isl_local_space_offset(ls, isl_dim_div) + div;
1056
1057 if (isl_int_eq(constraint[pos], ls->div->row[div][0])) {
1058 int neg;
1059 isl_int_sub(ls->div->row[div][1],
1060 ls->div->row[div][1], ls->div->row[div][0]);
1061 isl_int_add_ui(ls->div->row[div][1], ls->div->row[div][1], 1);
1062 neg = isl_seq_is_neg(constraint, ls->div->row[div]+1, pos);
1063 isl_int_sub_ui(ls->div->row[div][1], ls->div->row[div][1], 1);
1064 isl_int_add(ls->div->row[div][1],
1065 ls->div->row[div][1], ls->div->row[div][0]);
1066 if (!neg)
1067 return 0;
1068 if (isl_seq_first_non_zero(constraint+pos+1,
1069 ls->div->n_row-div-1) != -1)
1070 return 0;
1071 } else if (isl_int_abs_eq(constraint[pos], ls->div->row[div][0])) {
1072 if (!isl_seq_eq(constraint, ls->div->row[div]+1, pos))
1073 return 0;
1074 if (isl_seq_first_non_zero(constraint+pos+1,
1075 ls->div->n_row-div-1) != -1)
1076 return 0;
1077 } else
1078 return 0;
1079
1080 return 1;
1081 }
1082
1083 /*
1084 * Set active[i] to 1 if the dimension at position i is involved
1085 * in the linear expression l.
1086 */
1087 int *isl_local_space_get_active(__isl_keep isl_local_space *ls, isl_int *l)
1088 {
1089 int i, j;
1090 isl_ctx *ctx;
1091 int *active = NULL;
1092 unsigned total;
1093 unsigned offset;
1094
1095 ctx = isl_local_space_get_ctx(ls);
1096 total = isl_local_space_dim(ls, isl_dim_all);
1097 active = isl_calloc_array(ctx, int, total);
1098 if (total && !active)
1099 return NULL;
1100
1101 for (i = 0; i < total; ++i)
1102 active[i] = !isl_int_is_zero(l[i]);
1103
1104 offset = isl_local_space_offset(ls, isl_dim_div) - 1;
1105 for (i = ls->div->n_row - 1; i >= 0; --i) {
1106 if (!active[offset + i])
1107 continue;
1108 for (j = 0; j < total; ++j)
1109 active[j] |= !isl_int_is_zero(ls->div->row[i][2 + j]);
1110 }
1111
1112 return active;
1113 }
1114
1115 /* Given a local space "ls" of a set, create a local space
1116 * for the lift of the set. In particular, the result
1117 * is of the form [dim -> local[..]], with ls->div->n_row variables in the
1118 * range of the wrapped map.
1119 */
1120 __isl_give isl_local_space *isl_local_space_lift(
1121 __isl_take isl_local_space *ls)
1122 {
1123 ls = isl_local_space_cow(ls);
1124 if (!ls)
1125 return NULL;
1126
1127 ls->dim = isl_space_lift(ls->dim, ls->div->n_row);
1128 ls->div = isl_mat_drop_rows(ls->div, 0, ls->div->n_row);
1129 if (!ls->dim || !ls->div)
1130 return isl_local_space_free(ls);
1131
1132 return ls;
1133 }
1134
1135 /* Construct a basic map that maps a set living in local space "ls"
1136 * to the corresponding lifted local space.
1137 */
1138 __isl_give isl_basic_map *isl_local_space_lifting(
1139 __isl_take isl_local_space *ls)
1140 {
1141 isl_basic_map *lifting;
1142 isl_basic_set *bset;
1143
1144 if (!ls)
1145 return NULL;
1146 if (!isl_local_space_is_set(ls))
1147 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
1148 "lifting only defined on set spaces", goto error);
1149
1150 bset = isl_basic_set_from_local_space(ls);
1151 lifting = isl_basic_set_unwrap(isl_basic_set_lift(bset));
1152 lifting = isl_basic_map_domain_map(lifting);
1153 lifting = isl_basic_map_reverse(lifting);
1154
1155 return lifting;
1156 error:
1157 isl_local_space_free(ls);
1158 return NULL;
1159 }
1160
1161 /* Compute the preimage of "ls" under the function represented by "ma".
1162 * In other words, plug in "ma" in "ls". The result is a local space
1163 * that is part of the domain space of "ma".
1164 *
1165 * If the divs in "ls" are represented as
1166 *
1167 * floor((a_i(p) + b_i x + c_i(divs))/n_i)
1168 *
1169 * and ma is represented by
1170 *
1171 * x = D(p) + F(y) + G(divs')
1172 *
1173 * then the resulting divs are
1174 *
1175 * floor((a_i(p) + b_i D(p) + b_i F(y) + B_i G(divs') + c_i(divs))/n_i)
1176 *
1177 * We first copy over the divs from "ma" and then
1178 * we add the modified divs from "ls".
1179 */
1180 __isl_give isl_local_space *isl_local_space_preimage_multi_aff(
1181 __isl_take isl_local_space *ls, __isl_take isl_multi_aff *ma)
1182 {
1183 int i;
1184 isl_space *space;
1185 isl_local_space *res = NULL;
1186 int n_div_ls, n_div_ma;
1187 isl_int f, c1, c2, g;
1188
1189 ma = isl_multi_aff_align_divs(ma);
1190 if (!ls || !ma)
1191 goto error;
1192 if (!isl_space_is_range_internal(ls->dim, ma->space))
1193 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
1194 "spaces don't match", goto error);
1195
1196 n_div_ls = isl_local_space_dim(ls, isl_dim_div);
1197 n_div_ma = ma->n ? isl_aff_dim(ma->p[0], isl_dim_div) : 0;
1198
1199 space = isl_space_domain(isl_multi_aff_get_space(ma));
1200 res = isl_local_space_alloc(space, n_div_ma + n_div_ls);
1201 if (!res)
1202 goto error;
1203
1204 if (n_div_ma) {
1205 isl_mat_free(res->div);
1206 res->div = isl_mat_copy(ma->p[0]->ls->div);
1207 res->div = isl_mat_add_zero_cols(res->div, n_div_ls);
1208 res->div = isl_mat_add_rows(res->div, n_div_ls);
1209 if (!res->div)
1210 goto error;
1211 }
1212
1213 isl_int_init(f);
1214 isl_int_init(c1);
1215 isl_int_init(c2);
1216 isl_int_init(g);
1217
1218 for (i = 0; i < ls->div->n_row; ++i) {
1219 if (isl_int_is_zero(ls->div->row[i][0])) {
1220 isl_int_set_si(res->div->row[n_div_ma + i][0], 0);
1221 continue;
1222 }
1223 isl_seq_preimage(res->div->row[n_div_ma + i], ls->div->row[i],
1224 ma, 0, 0, n_div_ma, n_div_ls, f, c1, c2, g, 1);
1225 normalize_div(res, n_div_ma + i);
1226 }
1227
1228 isl_int_clear(f);
1229 isl_int_clear(c1);
1230 isl_int_clear(c2);
1231 isl_int_clear(g);
1232
1233 isl_local_space_free(ls);
1234 isl_multi_aff_free(ma);
1235 return res;
1236 error:
1237 isl_local_space_free(ls);
1238 isl_multi_aff_free(ma);
1239 isl_local_space_free(res);
1240 return NULL;
1241 }
1242
1243 /* Move the "n" dimensions of "src_type" starting at "src_pos" of "ls"
1244 * to dimensions of "dst_type" at "dst_pos".
1245 *
1246 * Moving to/from local dimensions is not allowed.
1247 * We currently assume that the dimension type changes.
1248 */
1249 __isl_give isl_local_space *isl_local_space_move_dims(
1250 __isl_take isl_local_space *ls,
1251 enum isl_dim_type dst_type, unsigned dst_pos,
1252 enum isl_dim_type src_type, unsigned src_pos, unsigned n)
1253 {
1254 unsigned g_dst_pos;
1255 unsigned g_src_pos;
1256
1257 if (!ls)
1258 return NULL;
1259 if (n == 0 &&
1260 !isl_local_space_is_named_or_nested(ls, src_type) &&
1261 !isl_local_space_is_named_or_nested(ls, dst_type))
1262 return ls;
1263
1264 if (src_pos + n > isl_local_space_dim(ls, src_type))
1265 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
1266 "range out of bounds", return isl_local_space_free(ls));
1267 if (dst_pos > isl_local_space_dim(ls, dst_type))
1268 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
1269 "position out of bounds",
1270 return isl_local_space_free(ls));
1271 if (src_type == isl_dim_div)
1272 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
1273 "cannot move divs", return isl_local_space_free(ls));
1274 if (dst_type == isl_dim_div)
1275 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
1276 "cannot move to divs", return isl_local_space_free(ls));
1277 if (dst_type == src_type && dst_pos == src_pos)
1278 return ls;
1279 if (dst_type == src_type)
1280 isl_die(isl_local_space_get_ctx(ls), isl_error_unsupported,
1281 "moving dims within the same type not supported",
1282 return isl_local_space_free(ls));
1283
1284 ls = isl_local_space_cow(ls);
1285 if (!ls)
1286 return NULL;
1287
1288 g_src_pos = 1 + isl_local_space_offset(ls, src_type) + src_pos;
1289 g_dst_pos = 1 + isl_local_space_offset(ls, dst_type) + dst_pos;
1290 if (dst_type > src_type)
1291 g_dst_pos -= n;
1292 ls->div = isl_mat_move_cols(ls->div, g_dst_pos, g_src_pos, n);
1293 if (!ls->div)
1294 return isl_local_space_free(ls);
1295 ls->dim = isl_space_move_dims(ls->dim, dst_type, dst_pos,
1296 src_type, src_pos, n);
1297 if (!ls->dim)
1298 return isl_local_space_free(ls);
1299
1300 return ls;
1301 }
1302
1303 /* Remove any internal structure of the domain of "ls".
1304 * If there is any such internal structure in the input,
1305 * then the name of the corresponding space is also removed.
1306 */
1307 __isl_give isl_local_space *isl_local_space_flatten_domain(
1308 __isl_take isl_local_space *ls)
1309 {
1310 if (!ls)
1311 return NULL;
1312
1313 if (!ls->dim->nested[0])
1314 return ls;
1315
1316 ls = isl_local_space_cow(ls);
1317 if (!ls)
1318 return NULL;
1319
1320 ls->dim = isl_space_flatten_domain(ls->dim);
1321 if (!ls->dim)
1322 return isl_local_space_free(ls);
1323
1324 return ls;
1325 }
1326
1327 /* Remove any internal structure of the range of "ls".
1328 * If there is any such internal structure in the input,
1329 * then the name of the corresponding space is also removed.
1330 */
1331 __isl_give isl_local_space *isl_local_space_flatten_range(
1332 __isl_take isl_local_space *ls)
1333 {
1334 if (!ls)
1335 return NULL;
1336
1337 if (!ls->dim->nested[1])
1338 return ls;
1339
1340 ls = isl_local_space_cow(ls);
1341 if (!ls)
1342 return NULL;
1343
1344 ls->dim = isl_space_flatten_range(ls->dim);
1345 if (!ls->dim)
1346 return isl_local_space_free(ls);
1347
1348 return ls;
1349 }
Integer set library