generalize isl_multi_aff_identity
[isl.git] / isl_local_space.c
blobbce4399c3b0b77cc9dfb69b3359d635a437cfb5a
1 /*
2 * Copyright 2011 INRIA Saclay
3 * Copyright 2012 Ecole Normale Superieure
5 * Use of this software is governed by the MIT license
7 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
8 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
9 * 91893 Orsay, France
10 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
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/seq.h>
21 isl_ctx *isl_local_space_get_ctx(__isl_keep isl_local_space *ls)
23 return ls ? ls->dim->ctx : NULL;
26 __isl_give isl_local_space *isl_local_space_alloc_div(__isl_take isl_space *dim,
27 __isl_take isl_mat *div)
29 isl_ctx *ctx;
30 isl_local_space *ls = NULL;
32 if (!dim || !div)
33 goto error;
35 ctx = isl_space_get_ctx(dim);
36 ls = isl_calloc_type(ctx, struct isl_local_space);
37 if (!ls)
38 goto error;
40 ls->ref = 1;
41 ls->dim = dim;
42 ls->div = div;
44 return ls;
45 error:
46 isl_mat_free(div);
47 isl_space_free(dim);
48 isl_local_space_free(ls);
49 return NULL;
52 __isl_give isl_local_space *isl_local_space_alloc(__isl_take isl_space *dim,
53 unsigned n_div)
55 isl_ctx *ctx;
56 isl_mat *div;
57 unsigned total;
59 if (!dim)
60 return NULL;
62 total = isl_space_dim(dim, isl_dim_all);
64 ctx = isl_space_get_ctx(dim);
65 div = isl_mat_alloc(ctx, n_div, 1 + 1 + total + n_div);
66 return isl_local_space_alloc_div(dim, div);
69 __isl_give isl_local_space *isl_local_space_from_space(__isl_take isl_space *dim)
71 return isl_local_space_alloc(dim, 0);
74 __isl_give isl_local_space *isl_local_space_copy(__isl_keep isl_local_space *ls)
76 if (!ls)
77 return NULL;
79 ls->ref++;
80 return ls;
83 __isl_give isl_local_space *isl_local_space_dup(__isl_keep isl_local_space *ls)
85 if (!ls)
86 return NULL;
88 return isl_local_space_alloc_div(isl_space_copy(ls->dim),
89 isl_mat_copy(ls->div));
93 __isl_give isl_local_space *isl_local_space_cow(__isl_take isl_local_space *ls)
95 if (!ls)
96 return NULL;
98 if (ls->ref == 1)
99 return ls;
100 ls->ref--;
101 return isl_local_space_dup(ls);
104 void *isl_local_space_free(__isl_take isl_local_space *ls)
106 if (!ls)
107 return NULL;
109 if (--ls->ref > 0)
110 return NULL;
112 isl_space_free(ls->dim);
113 isl_mat_free(ls->div);
115 free(ls);
117 return NULL;
120 /* Is the local space that of a set?
122 int isl_local_space_is_set(__isl_keep isl_local_space *ls)
124 return ls ? isl_space_is_set(ls->dim) : -1;
127 /* Return true if the two local spaces are identical, with identical
128 * expressions for the integer divisions.
130 int isl_local_space_is_equal(__isl_keep isl_local_space *ls1,
131 __isl_keep isl_local_space *ls2)
133 int equal;
135 if (!ls1 || !ls2)
136 return -1;
138 equal = isl_space_is_equal(ls1->dim, ls2->dim);
139 if (equal < 0 || !equal)
140 return equal;
142 if (!isl_local_space_divs_known(ls1))
143 return 0;
144 if (!isl_local_space_divs_known(ls2))
145 return 0;
147 return isl_mat_is_equal(ls1->div, ls2->div);
150 int isl_local_space_dim(__isl_keep isl_local_space *ls,
151 enum isl_dim_type type)
153 if (!ls)
154 return 0;
155 if (type == isl_dim_div)
156 return ls->div->n_row;
157 if (type == isl_dim_all)
158 return isl_space_dim(ls->dim, isl_dim_all) + ls->div->n_row;
159 return isl_space_dim(ls->dim, type);
162 unsigned isl_local_space_offset(__isl_keep isl_local_space *ls,
163 enum isl_dim_type type)
165 isl_space *dim;
167 if (!ls)
168 return 0;
170 dim = ls->dim;
171 switch (type) {
172 case isl_dim_cst: return 0;
173 case isl_dim_param: return 1;
174 case isl_dim_in: return 1 + dim->nparam;
175 case isl_dim_out: return 1 + dim->nparam + dim->n_in;
176 case isl_dim_div: return 1 + dim->nparam + dim->n_in + dim->n_out;
177 default: return 0;
181 /* Does the given dimension have a name?
183 int isl_local_space_has_dim_name(__isl_keep isl_local_space *ls,
184 enum isl_dim_type type, unsigned pos)
186 return ls ? isl_space_has_dim_name(ls->dim, type, pos) : -1;
189 const char *isl_local_space_get_dim_name(__isl_keep isl_local_space *ls,
190 enum isl_dim_type type, unsigned pos)
192 return ls ? isl_space_get_dim_name(ls->dim, type, pos) : NULL;
195 int isl_local_space_has_dim_id(__isl_keep isl_local_space *ls,
196 enum isl_dim_type type, unsigned pos)
198 return ls ? isl_space_has_dim_id(ls->dim, type, pos) : -1;
201 __isl_give isl_id *isl_local_space_get_dim_id(__isl_keep isl_local_space *ls,
202 enum isl_dim_type type, unsigned pos)
204 return ls ? isl_space_get_dim_id(ls->dim, type, pos) : NULL;
207 __isl_give isl_aff *isl_local_space_get_div(__isl_keep isl_local_space *ls,
208 int pos)
210 isl_aff *aff;
212 if (!ls)
213 return NULL;
215 if (pos < 0 || pos >= ls->div->n_row)
216 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
217 "index out of bounds", return NULL);
219 if (isl_int_is_zero(ls->div->row[pos][0]))
220 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
221 "expression of div unknown", return NULL);
223 aff = isl_aff_alloc(isl_local_space_copy(ls));
224 if (!aff)
225 return NULL;
226 isl_seq_cpy(aff->v->el, ls->div->row[pos], aff->v->size);
227 return aff;
230 __isl_give isl_space *isl_local_space_get_space(__isl_keep isl_local_space *ls)
232 if (!ls)
233 return NULL;
235 return isl_space_copy(ls->dim);
238 __isl_give isl_local_space *isl_local_space_set_dim_name(
239 __isl_take isl_local_space *ls,
240 enum isl_dim_type type, unsigned pos, const char *s)
242 ls = isl_local_space_cow(ls);
243 if (!ls)
244 return NULL;
245 ls->dim = isl_space_set_dim_name(ls->dim, type, pos, s);
246 if (!ls->dim)
247 return isl_local_space_free(ls);
249 return ls;
252 __isl_give isl_local_space *isl_local_space_set_dim_id(
253 __isl_take isl_local_space *ls,
254 enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
256 ls = isl_local_space_cow(ls);
257 if (!ls)
258 return isl_id_free(id);
259 ls->dim = isl_space_set_dim_id(ls->dim, type, pos, id);
260 if (!ls->dim)
261 return isl_local_space_free(ls);
263 return ls;
266 __isl_give isl_local_space *isl_local_space_reset_space(
267 __isl_take isl_local_space *ls, __isl_take isl_space *dim)
269 ls = isl_local_space_cow(ls);
270 if (!ls || !dim)
271 goto error;
273 isl_space_free(ls->dim);
274 ls->dim = dim;
276 return ls;
277 error:
278 isl_local_space_free(ls);
279 isl_space_free(dim);
280 return NULL;
283 /* Reorder the columns of the given div definitions according to the
284 * given reordering.
285 * The order of the divs themselves is assumed not to change.
287 static __isl_give isl_mat *reorder_divs(__isl_take isl_mat *div,
288 __isl_take isl_reordering *r)
290 int i, j;
291 isl_mat *mat;
292 int extra;
294 if (!div || !r)
295 goto error;
297 extra = isl_space_dim(r->dim, isl_dim_all) + div->n_row - r->len;
298 mat = isl_mat_alloc(div->ctx, div->n_row, div->n_col + extra);
299 if (!mat)
300 goto error;
302 for (i = 0; i < div->n_row; ++i) {
303 isl_seq_cpy(mat->row[i], div->row[i], 2);
304 isl_seq_clr(mat->row[i] + 2, mat->n_col - 2);
305 for (j = 0; j < r->len; ++j)
306 isl_int_set(mat->row[i][2 + r->pos[j]],
307 div->row[i][2 + j]);
310 isl_reordering_free(r);
311 isl_mat_free(div);
312 return mat;
313 error:
314 isl_reordering_free(r);
315 isl_mat_free(div);
316 return NULL;
319 /* Reorder the dimensions of "ls" according to the given reordering.
320 * The reordering r is assumed to have been extended with the local
321 * variables, leaving them in the same order.
323 __isl_give isl_local_space *isl_local_space_realign(
324 __isl_take isl_local_space *ls, __isl_take isl_reordering *r)
326 ls = isl_local_space_cow(ls);
327 if (!ls || !r)
328 goto error;
330 ls->div = reorder_divs(ls->div, isl_reordering_copy(r));
331 if (!ls->div)
332 goto error;
334 ls = isl_local_space_reset_space(ls, isl_space_copy(r->dim));
336 isl_reordering_free(r);
337 return ls;
338 error:
339 isl_local_space_free(ls);
340 isl_reordering_free(r);
341 return NULL;
344 __isl_give isl_local_space *isl_local_space_add_div(
345 __isl_take isl_local_space *ls, __isl_take isl_vec *div)
347 ls = isl_local_space_cow(ls);
348 if (!ls || !div)
349 goto error;
351 if (ls->div->n_col != div->size)
352 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
353 "incompatible dimensions", goto error);
355 ls->div = isl_mat_add_zero_cols(ls->div, 1);
356 ls->div = isl_mat_add_rows(ls->div, 1);
357 if (!ls->div)
358 goto error;
360 isl_seq_cpy(ls->div->row[ls->div->n_row - 1], div->el, div->size);
361 isl_int_set_si(ls->div->row[ls->div->n_row - 1][div->size], 0);
363 isl_vec_free(div);
364 return ls;
365 error:
366 isl_local_space_free(ls);
367 isl_vec_free(div);
368 return NULL;
371 __isl_give isl_local_space *isl_local_space_replace_divs(
372 __isl_take isl_local_space *ls, __isl_take isl_mat *div)
374 ls = isl_local_space_cow(ls);
376 if (!ls || !div)
377 goto error;
379 isl_mat_free(ls->div);
380 ls->div = div;
381 return ls;
382 error:
383 isl_mat_free(div);
384 isl_local_space_free(ls);
385 return NULL;
388 /* Copy row "s" of "src" to row "d" of "dst", applying the expansion
389 * defined by "exp".
391 static void expand_row(__isl_keep isl_mat *dst, int d,
392 __isl_keep isl_mat *src, int s, int *exp)
394 int i;
395 unsigned c = src->n_col - src->n_row;
397 isl_seq_cpy(dst->row[d], src->row[s], c);
398 isl_seq_clr(dst->row[d] + c, dst->n_col - c);
400 for (i = 0; i < s; ++i)
401 isl_int_set(dst->row[d][c + exp[i]], src->row[s][c + i]);
404 /* Compare (known) divs.
405 * Return non-zero if at least one of the two divs is unknown.
406 * In particular, if both divs are unknown, we respect their
407 * current order. Otherwise, we sort the known div after the unknown
408 * div only if the known div depends on the unknown div.
410 static int cmp_row(isl_int *row_i, isl_int *row_j, int i, int j,
411 unsigned n_row, unsigned n_col)
413 int li, lj;
414 int unknown_i, unknown_j;
416 unknown_i = isl_int_is_zero(row_i[0]);
417 unknown_j = isl_int_is_zero(row_j[0]);
419 if (unknown_i && unknown_j)
420 return i - j;
422 if (unknown_i)
423 li = n_col - n_row + i;
424 else
425 li = isl_seq_last_non_zero(row_i, n_col);
426 if (unknown_j)
427 lj = n_col - n_row + j;
428 else
429 lj = isl_seq_last_non_zero(row_j, n_col);
431 if (li != lj)
432 return li - lj;
434 return isl_seq_cmp(row_i, row_j, n_col);
437 /* Call cmp_row for divs in a matrix.
439 int isl_mat_cmp_div(__isl_keep isl_mat *div, int i, int j)
441 return cmp_row(div->row[i], div->row[j], i, j, div->n_row, div->n_col);
444 /* Call cmp_row for divs in a basic map.
446 static int bmap_cmp_row(__isl_keep isl_basic_map *bmap, int i, int j,
447 unsigned total)
449 return cmp_row(bmap->div[i], bmap->div[j], i, j, bmap->n_div, total);
452 /* Sort the divs in "bmap".
454 * We first make sure divs are placed after divs on which they depend.
455 * Then we perform a simple insertion sort based on the same ordering
456 * that is used in isl_merge_divs.
458 __isl_give isl_basic_map *isl_basic_map_sort_divs(
459 __isl_take isl_basic_map *bmap)
461 int i, j;
462 unsigned total;
464 bmap = isl_basic_map_order_divs(bmap);
465 if (!bmap)
466 return NULL;
467 if (bmap->n_div <= 1)
468 return bmap;
470 total = 2 + isl_basic_map_total_dim(bmap);
471 for (i = 1; i < bmap->n_div; ++i) {
472 for (j = i - 1; j >= 0; --j) {
473 if (bmap_cmp_row(bmap, j, j + 1, total) <= 0)
474 break;
475 isl_basic_map_swap_div(bmap, j, j + 1);
479 return bmap;
482 /* Sort the divs in the basic maps of "map".
484 __isl_give isl_map *isl_map_sort_divs(__isl_take isl_map *map)
486 return isl_map_inline_foreach_basic_map(map, &isl_basic_map_sort_divs);
489 /* Combine the two lists of divs into a single list.
490 * For each row i in div1, exp1[i] is set to the position of the corresponding
491 * row in the result. Similarly for div2 and exp2.
492 * This function guarantees
493 * exp1[i] >= i
494 * exp1[i+1] > exp1[i]
495 * For optimal merging, the two input list should have been sorted.
497 __isl_give isl_mat *isl_merge_divs(__isl_keep isl_mat *div1,
498 __isl_keep isl_mat *div2, int *exp1, int *exp2)
500 int i, j, k;
501 isl_mat *div = NULL;
502 unsigned d;
504 if (!div1 || !div2)
505 return NULL;
507 d = div1->n_col - div1->n_row;
508 div = isl_mat_alloc(div1->ctx, 1 + div1->n_row + div2->n_row,
509 d + div1->n_row + div2->n_row);
510 if (!div)
511 return NULL;
513 for (i = 0, j = 0, k = 0; i < div1->n_row && j < div2->n_row; ++k) {
514 int cmp;
516 expand_row(div, k, div1, i, exp1);
517 expand_row(div, k + 1, div2, j, exp2);
519 cmp = isl_mat_cmp_div(div, k, k + 1);
520 if (cmp == 0) {
521 exp1[i++] = k;
522 exp2[j++] = k;
523 } else if (cmp < 0) {
524 exp1[i++] = k;
525 } else {
526 exp2[j++] = k;
527 isl_seq_cpy(div->row[k], div->row[k + 1], div->n_col);
530 for (; i < div1->n_row; ++i, ++k) {
531 expand_row(div, k, div1, i, exp1);
532 exp1[i] = k;
534 for (; j < div2->n_row; ++j, ++k) {
535 expand_row(div, k, div2, j, exp2);
536 exp2[j] = k;
539 div->n_row = k;
540 div->n_col = d + k;
542 return div;
545 /* Swap divs "a" and "b" in "ls".
547 __isl_give isl_local_space *isl_local_space_swap_div(
548 __isl_take isl_local_space *ls, int a, int b)
550 int offset;
552 ls = isl_local_space_cow(ls);
553 if (!ls)
554 return NULL;
555 if (a < 0 || a >= ls->div->n_row || b < 0 || b >= ls->div->n_row)
556 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
557 "index out of bounds", return isl_local_space_free(ls));
558 offset = ls->div->n_col - ls->div->n_row;
559 ls->div = isl_mat_swap_cols(ls->div, offset + a, offset + b);
560 ls->div = isl_mat_swap_rows(ls->div, a, b);
561 if (!ls->div)
562 return isl_local_space_free(ls);
563 return ls;
566 /* Construct a local space that contains all the divs in either
567 * "ls1" or "ls2".
569 __isl_give isl_local_space *isl_local_space_intersect(
570 __isl_take isl_local_space *ls1, __isl_take isl_local_space *ls2)
572 isl_ctx *ctx;
573 int *exp1 = NULL;
574 int *exp2 = NULL;
575 isl_mat *div;
577 if (!ls1 || !ls2)
578 goto error;
580 ctx = isl_local_space_get_ctx(ls1);
581 if (!isl_space_is_equal(ls1->dim, ls2->dim))
582 isl_die(ctx, isl_error_invalid,
583 "spaces should be identical", goto error);
585 if (ls2->div->n_row == 0) {
586 isl_local_space_free(ls2);
587 return ls1;
590 if (ls1->div->n_row == 0) {
591 isl_local_space_free(ls1);
592 return ls2;
595 exp1 = isl_alloc_array(ctx, int, ls1->div->n_row);
596 exp2 = isl_alloc_array(ctx, int, ls2->div->n_row);
597 if (!exp1 || !exp2)
598 goto error;
600 div = isl_merge_divs(ls1->div, ls2->div, exp1, exp2);
601 if (!div)
602 goto error;
604 free(exp1);
605 free(exp2);
606 isl_local_space_free(ls2);
607 isl_mat_free(ls1->div);
608 ls1->div = div;
610 return ls1;
611 error:
612 free(exp1);
613 free(exp2);
614 isl_local_space_free(ls1);
615 isl_local_space_free(ls2);
616 return NULL;
619 int isl_local_space_divs_known(__isl_keep isl_local_space *ls)
621 int i;
623 if (!ls)
624 return -1;
626 for (i = 0; i < ls->div->n_row; ++i)
627 if (isl_int_is_zero(ls->div->row[i][0]))
628 return 0;
630 return 1;
633 __isl_give isl_local_space *isl_local_space_domain(
634 __isl_take isl_local_space *ls)
636 ls = isl_local_space_drop_dims(ls, isl_dim_out,
637 0, isl_local_space_dim(ls, isl_dim_out));
638 ls = isl_local_space_cow(ls);
639 if (!ls)
640 return NULL;
641 ls->dim = isl_space_domain(ls->dim);
642 if (!ls->dim)
643 return isl_local_space_free(ls);
644 return ls;
647 __isl_give isl_local_space *isl_local_space_range(
648 __isl_take isl_local_space *ls)
650 ls = isl_local_space_drop_dims(ls, isl_dim_in,
651 0, isl_local_space_dim(ls, isl_dim_in));
652 ls = isl_local_space_cow(ls);
653 if (!ls)
654 return NULL;
656 ls->dim = isl_space_range(ls->dim);
657 if (!ls->dim)
658 return isl_local_space_free(ls);
659 return ls;
662 /* Construct a local space for a map that has the given local
663 * space as domain and that has a zero-dimensional range.
665 __isl_give isl_local_space *isl_local_space_from_domain(
666 __isl_take isl_local_space *ls)
668 ls = isl_local_space_cow(ls);
669 if (!ls)
670 return NULL;
671 ls->dim = isl_space_from_domain(ls->dim);
672 if (!ls->dim)
673 return isl_local_space_free(ls);
674 return ls;
677 __isl_give isl_local_space *isl_local_space_add_dims(
678 __isl_take isl_local_space *ls, enum isl_dim_type type, unsigned n)
680 int pos;
682 if (!ls)
683 return NULL;
684 pos = isl_local_space_dim(ls, type);
685 return isl_local_space_insert_dims(ls, type, pos, n);
688 /* Remove common factor of non-constant terms and denominator.
690 static void normalize_div(__isl_keep isl_local_space *ls, int div)
692 isl_ctx *ctx = ls->div->ctx;
693 unsigned total = ls->div->n_col - 2;
695 isl_seq_gcd(ls->div->row[div] + 2, total, &ctx->normalize_gcd);
696 isl_int_gcd(ctx->normalize_gcd,
697 ctx->normalize_gcd, ls->div->row[div][0]);
698 if (isl_int_is_one(ctx->normalize_gcd))
699 return;
701 isl_seq_scale_down(ls->div->row[div] + 2, ls->div->row[div] + 2,
702 ctx->normalize_gcd, total);
703 isl_int_divexact(ls->div->row[div][0], ls->div->row[div][0],
704 ctx->normalize_gcd);
705 isl_int_fdiv_q(ls->div->row[div][1], ls->div->row[div][1],
706 ctx->normalize_gcd);
709 /* Exploit the equalities in "eq" to simplify the expressions of
710 * the integer divisions in "ls".
711 * The integer divisions in "ls" are assumed to appear as regular
712 * dimensions in "eq".
714 __isl_give isl_local_space *isl_local_space_substitute_equalities(
715 __isl_take isl_local_space *ls, __isl_take isl_basic_set *eq)
717 int i, j, k;
718 unsigned total;
719 unsigned n_div;
721 ls = isl_local_space_cow(ls);
722 if (!ls || !eq)
723 goto error;
725 total = isl_space_dim(eq->dim, isl_dim_all);
726 if (isl_local_space_dim(ls, isl_dim_all) != total)
727 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
728 "dimensions don't match", goto error);
729 total++;
730 n_div = eq->n_div;
731 for (i = 0; i < eq->n_eq; ++i) {
732 j = isl_seq_last_non_zero(eq->eq[i], total + n_div);
733 if (j < 0 || j == 0 || j >= total)
734 continue;
736 for (k = 0; k < ls->div->n_row; ++k) {
737 if (isl_int_is_zero(ls->div->row[k][1 + j]))
738 continue;
739 isl_seq_elim(ls->div->row[k] + 1, eq->eq[i], j, total,
740 &ls->div->row[k][0]);
741 normalize_div(ls, k);
745 isl_basic_set_free(eq);
746 return ls;
747 error:
748 isl_basic_set_free(eq);
749 isl_local_space_free(ls);
750 return NULL;
753 /* Plug in the affine expressions "subs" of length "subs_len" (including
754 * the denominator and the constant term) into the variable at position "pos"
755 * of all the div expressions starting at "first".
757 * Let i be the dimension to replace and let "subs" be of the form
759 * f/d
761 * Any integer division starting at "first" with a non-zero coefficient for i,
763 * floor((a i + g)/m)
765 * is replaced by
767 * floor((a f + d g)/(m d))
769 __isl_give isl_local_space *isl_local_space_substitute_seq(
770 __isl_take isl_local_space *ls,
771 enum isl_dim_type type, unsigned pos, isl_int *subs, int subs_len,
772 int first)
774 int i;
775 isl_int v;
777 ls = isl_local_space_cow(ls);
778 if (!ls)
779 return NULL;
780 ls->div = isl_mat_cow(ls->div);
781 if (!ls->div)
782 return isl_local_space_free(ls);
784 pos += isl_local_space_offset(ls, type);
786 isl_int_init(v);
787 for (i = first; i < ls->div->n_row; ++i) {
788 if (isl_int_is_zero(ls->div->row[i][1 + pos]))
789 continue;
790 isl_seq_substitute(ls->div->row[i], pos, subs,
791 ls->div->n_col, subs_len, v);
792 normalize_div(ls, i);
794 isl_int_clear(v);
796 return ls;
799 /* Plug in "subs" for dimension "type", "pos" in the integer divisions
800 * of "ls".
802 * Let i be the dimension to replace and let "subs" be of the form
804 * f/d
806 * Any integer division with a non-zero coefficient for i,
808 * floor((a i + g)/m)
810 * is replaced by
812 * floor((a f + d g)/(m d))
814 __isl_give isl_local_space *isl_local_space_substitute(
815 __isl_take isl_local_space *ls,
816 enum isl_dim_type type, unsigned pos, __isl_keep isl_aff *subs)
818 ls = isl_local_space_cow(ls);
819 if (!ls || !subs)
820 return isl_local_space_free(ls);
822 if (!isl_space_is_equal(ls->dim, subs->ls->dim))
823 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
824 "spaces don't match", return isl_local_space_free(ls));
825 if (isl_local_space_dim(subs->ls, isl_dim_div) != 0)
826 isl_die(isl_local_space_get_ctx(ls), isl_error_unsupported,
827 "cannot handle divs yet",
828 return isl_local_space_free(ls));
830 return isl_local_space_substitute_seq(ls, type, pos, subs->v->el,
831 subs->v->size, 0);
834 int isl_local_space_is_named_or_nested(__isl_keep isl_local_space *ls,
835 enum isl_dim_type type)
837 if (!ls)
838 return -1;
839 return isl_space_is_named_or_nested(ls->dim, type);
842 __isl_give isl_local_space *isl_local_space_drop_dims(
843 __isl_take isl_local_space *ls,
844 enum isl_dim_type type, unsigned first, unsigned n)
846 isl_ctx *ctx;
848 if (!ls)
849 return NULL;
850 if (n == 0 && !isl_local_space_is_named_or_nested(ls, type))
851 return ls;
853 ctx = isl_local_space_get_ctx(ls);
854 if (first + n > isl_local_space_dim(ls, type))
855 isl_die(ctx, isl_error_invalid, "range out of bounds",
856 return isl_local_space_free(ls));
858 ls = isl_local_space_cow(ls);
859 if (!ls)
860 return NULL;
862 if (type == isl_dim_div) {
863 ls->div = isl_mat_drop_rows(ls->div, first, n);
864 } else {
865 ls->dim = isl_space_drop_dims(ls->dim, type, first, n);
866 if (!ls->dim)
867 return isl_local_space_free(ls);
870 first += 1 + isl_local_space_offset(ls, type);
871 ls->div = isl_mat_drop_cols(ls->div, first, n);
872 if (!ls->div)
873 return isl_local_space_free(ls);
875 return ls;
878 __isl_give isl_local_space *isl_local_space_insert_dims(
879 __isl_take isl_local_space *ls,
880 enum isl_dim_type type, unsigned first, unsigned n)
882 isl_ctx *ctx;
884 if (!ls)
885 return NULL;
886 if (n == 0 && !isl_local_space_is_named_or_nested(ls, type))
887 return ls;
889 ctx = isl_local_space_get_ctx(ls);
890 if (first > isl_local_space_dim(ls, type))
891 isl_die(ctx, isl_error_invalid, "position out of bounds",
892 return isl_local_space_free(ls));
894 ls = isl_local_space_cow(ls);
895 if (!ls)
896 return NULL;
898 if (type == isl_dim_div) {
899 ls->div = isl_mat_insert_zero_rows(ls->div, first, n);
900 } else {
901 ls->dim = isl_space_insert_dims(ls->dim, type, first, n);
902 if (!ls->dim)
903 return isl_local_space_free(ls);
906 first += 1 + isl_local_space_offset(ls, type);
907 ls->div = isl_mat_insert_zero_cols(ls->div, first, n);
908 if (!ls->div)
909 return isl_local_space_free(ls);
911 return ls;
914 /* Check if the constraints pointed to by "constraint" is a div
915 * constraint corresponding to div "div" in "ls".
917 * That is, if div = floor(f/m), then check if the constraint is
919 * f - m d >= 0
920 * or
921 * -(f-(m-1)) + m d >= 0
923 int isl_local_space_is_div_constraint(__isl_keep isl_local_space *ls,
924 isl_int *constraint, unsigned div)
926 unsigned pos;
928 if (!ls)
929 return -1;
931 if (isl_int_is_zero(ls->div->row[div][0]))
932 return 0;
934 pos = isl_local_space_offset(ls, isl_dim_div) + div;
936 if (isl_int_eq(constraint[pos], ls->div->row[div][0])) {
937 int neg;
938 isl_int_sub(ls->div->row[div][1],
939 ls->div->row[div][1], ls->div->row[div][0]);
940 isl_int_add_ui(ls->div->row[div][1], ls->div->row[div][1], 1);
941 neg = isl_seq_is_neg(constraint, ls->div->row[div]+1, pos);
942 isl_int_sub_ui(ls->div->row[div][1], ls->div->row[div][1], 1);
943 isl_int_add(ls->div->row[div][1],
944 ls->div->row[div][1], ls->div->row[div][0]);
945 if (!neg)
946 return 0;
947 if (isl_seq_first_non_zero(constraint+pos+1,
948 ls->div->n_row-div-1) != -1)
949 return 0;
950 } else if (isl_int_abs_eq(constraint[pos], ls->div->row[div][0])) {
951 if (!isl_seq_eq(constraint, ls->div->row[div]+1, pos))
952 return 0;
953 if (isl_seq_first_non_zero(constraint+pos+1,
954 ls->div->n_row-div-1) != -1)
955 return 0;
956 } else
957 return 0;
959 return 1;
963 * Set active[i] to 1 if the dimension at position i is involved
964 * in the linear expression l.
966 int *isl_local_space_get_active(__isl_keep isl_local_space *ls, isl_int *l)
968 int i, j;
969 isl_ctx *ctx;
970 int *active = NULL;
971 unsigned total;
972 unsigned offset;
974 ctx = isl_local_space_get_ctx(ls);
975 total = isl_local_space_dim(ls, isl_dim_all);
976 active = isl_calloc_array(ctx, int, total);
977 if (!active)
978 return NULL;
980 for (i = 0; i < total; ++i)
981 active[i] = !isl_int_is_zero(l[i]);
983 offset = isl_local_space_offset(ls, isl_dim_div) - 1;
984 for (i = ls->div->n_row - 1; i >= 0; --i) {
985 if (!active[offset + i])
986 continue;
987 for (j = 0; j < total; ++j)
988 active[j] |= !isl_int_is_zero(ls->div->row[i][2 + j]);
991 return active;
994 /* Given a local space "ls" of a set, create a local space
995 * for the lift of the set. In particular, the result
996 * is of the form [dim -> local[..]], with ls->div->n_row variables in the
997 * range of the wrapped map.
999 __isl_give isl_local_space *isl_local_space_lift(
1000 __isl_take isl_local_space *ls)
1002 ls = isl_local_space_cow(ls);
1003 if (!ls)
1004 return NULL;
1006 ls->dim = isl_space_lift(ls->dim, ls->div->n_row);
1007 ls->div = isl_mat_drop_rows(ls->div, 0, ls->div->n_row);
1008 if (!ls->dim || !ls->div)
1009 return isl_local_space_free(ls);
1011 return ls;
1014 /* Construct a basic map that maps a set living in local space "ls"
1015 * to the corresponding lifted local space.
1017 __isl_give isl_basic_map *isl_local_space_lifting(
1018 __isl_take isl_local_space *ls)
1020 isl_basic_map *lifting;
1021 isl_basic_set *bset;
1023 if (!ls)
1024 return NULL;
1025 if (!isl_local_space_is_set(ls))
1026 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
1027 "lifting only defined on set spaces",
1028 return isl_local_space_free(ls));
1030 bset = isl_basic_set_from_local_space(ls);
1031 lifting = isl_basic_set_unwrap(isl_basic_set_lift(bset));
1032 lifting = isl_basic_map_domain_map(lifting);
1033 lifting = isl_basic_map_reverse(lifting);
1035 return lifting;