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