isl_tab_pip.c: same_solution: return isl_bool
[isl.git] / isl_local_space.c
blobdaefc91703e310fd07b627a24ea09c638aa8c0f7
1 /*
2 * Copyright 2011 INRIA Saclay
3 * Copyright 2012-2014 Ecole Normale Superieure
5 * Use of this software is governed by the MIT license
7 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
8 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
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_vec_private.h>
20 #include <isl_seq.h>
21 #include <isl_local.h>
23 isl_ctx *isl_local_space_get_ctx(__isl_keep isl_local_space *ls)
25 return ls ? ls->dim->ctx : NULL;
28 /* Return a hash value that digests "ls".
30 uint32_t isl_local_space_get_hash(__isl_keep isl_local_space *ls)
32 uint32_t hash, space_hash, div_hash;
34 if (!ls)
35 return 0;
37 hash = isl_hash_init();
38 space_hash = isl_space_get_hash(ls->dim);
39 isl_hash_hash(hash, space_hash);
40 div_hash = isl_mat_get_hash(ls->div);
41 isl_hash_hash(hash, div_hash);
43 return hash;
46 __isl_give isl_local_space *isl_local_space_alloc_div(__isl_take isl_space *dim,
47 __isl_take isl_mat *div)
49 isl_ctx *ctx;
50 isl_local_space *ls = NULL;
52 if (!dim || !div)
53 goto error;
55 ctx = isl_space_get_ctx(dim);
56 ls = isl_calloc_type(ctx, struct isl_local_space);
57 if (!ls)
58 goto error;
60 ls->ref = 1;
61 ls->dim = dim;
62 ls->div = div;
64 return ls;
65 error:
66 isl_mat_free(div);
67 isl_space_free(dim);
68 isl_local_space_free(ls);
69 return NULL;
72 __isl_give isl_local_space *isl_local_space_alloc(__isl_take isl_space *dim,
73 unsigned n_div)
75 isl_ctx *ctx;
76 isl_mat *div;
77 unsigned total;
79 if (!dim)
80 return NULL;
82 total = isl_space_dim(dim, isl_dim_all);
84 ctx = isl_space_get_ctx(dim);
85 div = isl_mat_alloc(ctx, n_div, 1 + 1 + total + n_div);
86 return isl_local_space_alloc_div(dim, div);
89 __isl_give isl_local_space *isl_local_space_from_space(__isl_take isl_space *dim)
91 return isl_local_space_alloc(dim, 0);
94 __isl_give isl_local_space *isl_local_space_copy(__isl_keep isl_local_space *ls)
96 if (!ls)
97 return NULL;
99 ls->ref++;
100 return ls;
103 __isl_give isl_local_space *isl_local_space_dup(__isl_keep isl_local_space *ls)
105 if (!ls)
106 return NULL;
108 return isl_local_space_alloc_div(isl_space_copy(ls->dim),
109 isl_mat_copy(ls->div));
113 __isl_give isl_local_space *isl_local_space_cow(__isl_take isl_local_space *ls)
115 if (!ls)
116 return NULL;
118 if (ls->ref == 1)
119 return ls;
120 ls->ref--;
121 return isl_local_space_dup(ls);
124 __isl_null isl_local_space *isl_local_space_free(
125 __isl_take isl_local_space *ls)
127 if (!ls)
128 return NULL;
130 if (--ls->ref > 0)
131 return NULL;
133 isl_space_free(ls->dim);
134 isl_mat_free(ls->div);
136 free(ls);
138 return NULL;
141 /* Is the local space that of a parameter domain?
143 isl_bool isl_local_space_is_params(__isl_keep isl_local_space *ls)
145 if (!ls)
146 return isl_bool_error;
147 return isl_space_is_params(ls->dim);
150 /* Is the local space that of a set?
152 isl_bool isl_local_space_is_set(__isl_keep isl_local_space *ls)
154 return ls ? isl_space_is_set(ls->dim) : isl_bool_error;
157 /* Do "ls1" and "ls2" have the same space?
159 isl_bool isl_local_space_has_equal_space(__isl_keep isl_local_space *ls1,
160 __isl_keep isl_local_space *ls2)
162 if (!ls1 || !ls2)
163 return isl_bool_error;
165 return isl_space_is_equal(ls1->dim, ls2->dim);
168 /* Return true if the two local spaces are identical, with identical
169 * expressions for the integer divisions.
171 isl_bool isl_local_space_is_equal(__isl_keep isl_local_space *ls1,
172 __isl_keep isl_local_space *ls2)
174 isl_bool equal;
176 equal = isl_local_space_has_equal_space(ls1, ls2);
177 if (equal < 0 || !equal)
178 return equal;
180 if (!isl_local_space_divs_known(ls1))
181 return isl_bool_false;
182 if (!isl_local_space_divs_known(ls2))
183 return isl_bool_false;
185 return isl_mat_is_equal(ls1->div, ls2->div);
188 /* Compare two isl_local_spaces.
190 * Return -1 if "ls1" is "smaller" than "ls2", 1 if "ls1" is "greater"
191 * than "ls2" and 0 if they are equal.
193 int isl_local_space_cmp(__isl_keep isl_local_space *ls1,
194 __isl_keep isl_local_space *ls2)
196 int cmp;
198 if (ls1 == ls2)
199 return 0;
200 if (!ls1)
201 return -1;
202 if (!ls2)
203 return 1;
205 cmp = isl_space_cmp(ls1->dim, ls2->dim);
206 if (cmp != 0)
207 return cmp;
209 return isl_local_cmp(ls1->div, ls2->div);
212 int isl_local_space_dim(__isl_keep isl_local_space *ls,
213 enum isl_dim_type type)
215 if (!ls)
216 return 0;
217 if (type == isl_dim_div)
218 return ls->div->n_row;
219 if (type == isl_dim_all)
220 return isl_space_dim(ls->dim, isl_dim_all) + ls->div->n_row;
221 return isl_space_dim(ls->dim, type);
224 unsigned isl_local_space_offset(__isl_keep isl_local_space *ls,
225 enum isl_dim_type type)
227 isl_space *dim;
229 if (!ls)
230 return 0;
232 dim = ls->dim;
233 switch (type) {
234 case isl_dim_cst: return 0;
235 case isl_dim_param: return 1;
236 case isl_dim_in: return 1 + dim->nparam;
237 case isl_dim_out: return 1 + dim->nparam + dim->n_in;
238 case isl_dim_div: return 1 + dim->nparam + dim->n_in + dim->n_out;
239 default: return 0;
243 /* Return the position of the dimension of the given type and name
244 * in "ls".
245 * Return -1 if no such dimension can be found.
247 int isl_local_space_find_dim_by_name(__isl_keep isl_local_space *ls,
248 enum isl_dim_type type, const char *name)
250 if (!ls)
251 return -1;
252 if (type == isl_dim_div)
253 return -1;
254 return isl_space_find_dim_by_name(ls->dim, type, name);
257 /* Does the given dimension have a name?
259 isl_bool isl_local_space_has_dim_name(__isl_keep isl_local_space *ls,
260 enum isl_dim_type type, unsigned pos)
262 return ls ? isl_space_has_dim_name(ls->dim, type, pos) : isl_bool_error;
265 const char *isl_local_space_get_dim_name(__isl_keep isl_local_space *ls,
266 enum isl_dim_type type, unsigned pos)
268 return ls ? isl_space_get_dim_name(ls->dim, type, pos) : NULL;
271 isl_bool isl_local_space_has_dim_id(__isl_keep isl_local_space *ls,
272 enum isl_dim_type type, unsigned pos)
274 return ls ? isl_space_has_dim_id(ls->dim, type, pos) : isl_bool_error;
277 __isl_give isl_id *isl_local_space_get_dim_id(__isl_keep isl_local_space *ls,
278 enum isl_dim_type type, unsigned pos)
280 return ls ? isl_space_get_dim_id(ls->dim, type, pos) : NULL;
283 /* Return the argument of the integer division at position "pos" in "ls".
284 * All local variables in "ls" are known to have a (complete) explicit
285 * representation.
287 static __isl_give isl_aff *extract_div(__isl_keep isl_local_space *ls, int pos)
289 isl_aff *aff;
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;
298 /* Return the argument of the integer division at position "pos" in "ls".
299 * The integer division at that position is known to have a complete
300 * explicit representation, but some of the others do not.
301 * Remove them first because the domain of an isl_aff
302 * is not allowed to have unknown local variables.
304 static __isl_give isl_aff *drop_unknown_divs_and_extract_div(
305 __isl_keep isl_local_space *ls, int pos)
307 int i, n;
308 isl_bool unknown;
309 isl_aff *aff;
311 ls = isl_local_space_copy(ls);
312 n = isl_local_space_dim(ls, isl_dim_div);
313 for (i = n - 1; i >= 0; --i) {
314 unknown = isl_local_space_div_is_marked_unknown(ls, i);
315 if (unknown < 0)
316 ls = isl_local_space_free(ls);
317 else if (!unknown)
318 continue;
319 ls = isl_local_space_drop_dims(ls, isl_dim_div, i, 1);
320 if (pos > i)
321 --pos;
323 aff = extract_div(ls, pos);
324 isl_local_space_free(ls);
325 return aff;
328 /* Return the argument of the integer division at position "pos" in "ls".
329 * The integer division is assumed to have a complete explicit
330 * representation. If some of the other integer divisions
331 * do not have an explicit representation, then they need
332 * to be removed first because the domain of an isl_aff
333 * is not allowed to have unknown local variables.
335 __isl_give isl_aff *isl_local_space_get_div(__isl_keep isl_local_space *ls,
336 int pos)
338 isl_bool known;
340 if (!ls)
341 return NULL;
343 if (pos < 0 || pos >= ls->div->n_row)
344 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
345 "index out of bounds", return NULL);
347 known = isl_local_space_div_is_known(ls, pos);
348 if (known < 0)
349 return NULL;
350 if (!known)
351 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
352 "expression of div unknown", return NULL);
353 if (!isl_local_space_is_set(ls))
354 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
355 "cannot represent divs of map spaces", return NULL);
357 known = isl_local_space_divs_known(ls);
358 if (known < 0)
359 return NULL;
360 if (known)
361 return extract_div(ls, pos);
362 else
363 return drop_unknown_divs_and_extract_div(ls, pos);
366 __isl_give isl_space *isl_local_space_get_space(__isl_keep isl_local_space *ls)
368 if (!ls)
369 return NULL;
371 return isl_space_copy(ls->dim);
374 /* Replace the identifier of the tuple of type "type" by "id".
376 __isl_give isl_local_space *isl_local_space_set_tuple_id(
377 __isl_take isl_local_space *ls,
378 enum isl_dim_type type, __isl_take isl_id *id)
380 ls = isl_local_space_cow(ls);
381 if (!ls)
382 goto error;
383 ls->dim = isl_space_set_tuple_id(ls->dim, type, id);
384 if (!ls->dim)
385 return isl_local_space_free(ls);
386 return ls;
387 error:
388 isl_id_free(id);
389 return NULL;
392 __isl_give isl_local_space *isl_local_space_set_dim_name(
393 __isl_take isl_local_space *ls,
394 enum isl_dim_type type, unsigned pos, const char *s)
396 ls = isl_local_space_cow(ls);
397 if (!ls)
398 return NULL;
399 ls->dim = isl_space_set_dim_name(ls->dim, type, pos, s);
400 if (!ls->dim)
401 return isl_local_space_free(ls);
403 return ls;
406 __isl_give isl_local_space *isl_local_space_set_dim_id(
407 __isl_take isl_local_space *ls,
408 enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
410 ls = isl_local_space_cow(ls);
411 if (!ls)
412 goto error;
413 ls->dim = isl_space_set_dim_id(ls->dim, type, pos, id);
414 if (!ls->dim)
415 return isl_local_space_free(ls);
417 return ls;
418 error:
419 isl_id_free(id);
420 return NULL;
423 __isl_give isl_local_space *isl_local_space_reset_space(
424 __isl_take isl_local_space *ls, __isl_take isl_space *dim)
426 ls = isl_local_space_cow(ls);
427 if (!ls || !dim)
428 goto error;
430 isl_space_free(ls->dim);
431 ls->dim = dim;
433 return ls;
434 error:
435 isl_local_space_free(ls);
436 isl_space_free(dim);
437 return NULL;
440 /* Reorder the columns of the given div definitions according to the
441 * given reordering.
442 * The order of the divs themselves is assumed not to change.
444 static __isl_give isl_mat *reorder_divs(__isl_take isl_mat *div,
445 __isl_take isl_reordering *r)
447 int i, j;
448 isl_mat *mat;
449 int extra;
451 if (!div || !r)
452 goto error;
454 extra = isl_space_dim(r->dim, isl_dim_all) + div->n_row - r->len;
455 mat = isl_mat_alloc(div->ctx, div->n_row, div->n_col + extra);
456 if (!mat)
457 goto error;
459 for (i = 0; i < div->n_row; ++i) {
460 isl_seq_cpy(mat->row[i], div->row[i], 2);
461 isl_seq_clr(mat->row[i] + 2, mat->n_col - 2);
462 for (j = 0; j < r->len; ++j)
463 isl_int_set(mat->row[i][2 + r->pos[j]],
464 div->row[i][2 + j]);
467 isl_reordering_free(r);
468 isl_mat_free(div);
469 return mat;
470 error:
471 isl_reordering_free(r);
472 isl_mat_free(div);
473 return NULL;
476 /* Reorder the dimensions of "ls" according to the given reordering.
477 * The reordering r is assumed to have been extended with the local
478 * variables, leaving them in the same order.
480 __isl_give isl_local_space *isl_local_space_realign(
481 __isl_take isl_local_space *ls, __isl_take isl_reordering *r)
483 ls = isl_local_space_cow(ls);
484 if (!ls || !r)
485 goto error;
487 ls->div = reorder_divs(ls->div, isl_reordering_copy(r));
488 if (!ls->div)
489 goto error;
491 ls = isl_local_space_reset_space(ls, isl_space_copy(r->dim));
493 isl_reordering_free(r);
494 return ls;
495 error:
496 isl_local_space_free(ls);
497 isl_reordering_free(r);
498 return NULL;
501 __isl_give isl_local_space *isl_local_space_add_div(
502 __isl_take isl_local_space *ls, __isl_take isl_vec *div)
504 ls = isl_local_space_cow(ls);
505 if (!ls || !div)
506 goto error;
508 if (ls->div->n_col != div->size)
509 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
510 "incompatible dimensions", goto error);
512 ls->div = isl_mat_add_zero_cols(ls->div, 1);
513 ls->div = isl_mat_add_rows(ls->div, 1);
514 if (!ls->div)
515 goto error;
517 isl_seq_cpy(ls->div->row[ls->div->n_row - 1], div->el, div->size);
518 isl_int_set_si(ls->div->row[ls->div->n_row - 1][div->size], 0);
520 isl_vec_free(div);
521 return ls;
522 error:
523 isl_local_space_free(ls);
524 isl_vec_free(div);
525 return NULL;
528 __isl_give isl_local_space *isl_local_space_replace_divs(
529 __isl_take isl_local_space *ls, __isl_take isl_mat *div)
531 ls = isl_local_space_cow(ls);
533 if (!ls || !div)
534 goto error;
536 isl_mat_free(ls->div);
537 ls->div = div;
538 return ls;
539 error:
540 isl_mat_free(div);
541 isl_local_space_free(ls);
542 return NULL;
545 /* Copy row "s" of "src" to row "d" of "dst", applying the expansion
546 * defined by "exp".
548 static void expand_row(__isl_keep isl_mat *dst, int d,
549 __isl_keep isl_mat *src, int s, int *exp)
551 int i;
552 unsigned c = src->n_col - src->n_row;
554 isl_seq_cpy(dst->row[d], src->row[s], c);
555 isl_seq_clr(dst->row[d] + c, dst->n_col - c);
557 for (i = 0; i < s; ++i)
558 isl_int_set(dst->row[d][c + exp[i]], src->row[s][c + i]);
561 /* Compare (known) divs.
562 * Return non-zero if at least one of the two divs is unknown.
563 * In particular, if both divs are unknown, we respect their
564 * current order. Otherwise, we sort the known div after the unknown
565 * div only if the known div depends on the unknown div.
567 static int cmp_row(isl_int *row_i, isl_int *row_j, int i, int j,
568 unsigned n_row, unsigned n_col)
570 int li, lj;
571 int unknown_i, unknown_j;
573 unknown_i = isl_int_is_zero(row_i[0]);
574 unknown_j = isl_int_is_zero(row_j[0]);
576 if (unknown_i && unknown_j)
577 return i - j;
579 if (unknown_i)
580 li = n_col - n_row + i;
581 else
582 li = isl_seq_last_non_zero(row_i, n_col);
583 if (unknown_j)
584 lj = n_col - n_row + j;
585 else
586 lj = isl_seq_last_non_zero(row_j, n_col);
588 if (li != lj)
589 return li - lj;
591 return isl_seq_cmp(row_i, row_j, n_col);
594 /* Call cmp_row for divs in a matrix.
596 int isl_mat_cmp_div(__isl_keep isl_mat *div, int i, int j)
598 return cmp_row(div->row[i], div->row[j], i, j, div->n_row, div->n_col);
601 /* Call cmp_row for divs in a basic map.
603 static int bmap_cmp_row(__isl_keep isl_basic_map *bmap, int i, int j,
604 unsigned total)
606 return cmp_row(bmap->div[i], bmap->div[j], i, j, bmap->n_div, total);
609 /* Sort the divs in "bmap".
611 * We first make sure divs are placed after divs on which they depend.
612 * Then we perform a simple insertion sort based on the same ordering
613 * that is used in isl_merge_divs.
615 __isl_give isl_basic_map *isl_basic_map_sort_divs(
616 __isl_take isl_basic_map *bmap)
618 int i, j;
619 unsigned total;
621 bmap = isl_basic_map_order_divs(bmap);
622 if (!bmap)
623 return NULL;
624 if (bmap->n_div <= 1)
625 return bmap;
627 total = 2 + isl_basic_map_total_dim(bmap);
628 for (i = 1; i < bmap->n_div; ++i) {
629 for (j = i - 1; j >= 0; --j) {
630 if (bmap_cmp_row(bmap, j, j + 1, total) <= 0)
631 break;
632 isl_basic_map_swap_div(bmap, j, j + 1);
636 return bmap;
639 /* Sort the divs in the basic maps of "map".
641 __isl_give isl_map *isl_map_sort_divs(__isl_take isl_map *map)
643 return isl_map_inline_foreach_basic_map(map, &isl_basic_map_sort_divs);
646 /* Combine the two lists of divs into a single list.
647 * For each row i in div1, exp1[i] is set to the position of the corresponding
648 * row in the result. Similarly for div2 and exp2.
649 * This function guarantees
650 * exp1[i] >= i
651 * exp1[i+1] > exp1[i]
652 * For optimal merging, the two input list should have been sorted.
654 __isl_give isl_mat *isl_merge_divs(__isl_keep isl_mat *div1,
655 __isl_keep isl_mat *div2, int *exp1, int *exp2)
657 int i, j, k;
658 isl_mat *div = NULL;
659 unsigned d;
661 if (!div1 || !div2)
662 return NULL;
664 d = div1->n_col - div1->n_row;
665 div = isl_mat_alloc(div1->ctx, 1 + div1->n_row + div2->n_row,
666 d + div1->n_row + div2->n_row);
667 if (!div)
668 return NULL;
670 for (i = 0, j = 0, k = 0; i < div1->n_row && j < div2->n_row; ++k) {
671 int cmp;
673 expand_row(div, k, div1, i, exp1);
674 expand_row(div, k + 1, div2, j, exp2);
676 cmp = isl_mat_cmp_div(div, k, k + 1);
677 if (cmp == 0) {
678 exp1[i++] = k;
679 exp2[j++] = k;
680 } else if (cmp < 0) {
681 exp1[i++] = k;
682 } else {
683 exp2[j++] = k;
684 isl_seq_cpy(div->row[k], div->row[k + 1], div->n_col);
687 for (; i < div1->n_row; ++i, ++k) {
688 expand_row(div, k, div1, i, exp1);
689 exp1[i] = k;
691 for (; j < div2->n_row; ++j, ++k) {
692 expand_row(div, k, div2, j, exp2);
693 exp2[j] = k;
696 div->n_row = k;
697 div->n_col = d + k;
699 return div;
702 /* Swap divs "a" and "b" in "ls".
704 __isl_give isl_local_space *isl_local_space_swap_div(
705 __isl_take isl_local_space *ls, int a, int b)
707 int offset;
709 ls = isl_local_space_cow(ls);
710 if (!ls)
711 return NULL;
712 if (a < 0 || a >= ls->div->n_row || b < 0 || b >= ls->div->n_row)
713 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
714 "index out of bounds", return isl_local_space_free(ls));
715 offset = ls->div->n_col - ls->div->n_row;
716 ls->div = isl_mat_swap_cols(ls->div, offset + a, offset + b);
717 ls->div = isl_mat_swap_rows(ls->div, a, b);
718 if (!ls->div)
719 return isl_local_space_free(ls);
720 return ls;
723 /* Construct a local space that contains all the divs in either
724 * "ls1" or "ls2".
726 __isl_give isl_local_space *isl_local_space_intersect(
727 __isl_take isl_local_space *ls1, __isl_take isl_local_space *ls2)
729 isl_ctx *ctx;
730 int *exp1 = NULL;
731 int *exp2 = NULL;
732 isl_mat *div;
733 int equal;
735 if (!ls1 || !ls2)
736 goto error;
738 ctx = isl_local_space_get_ctx(ls1);
739 if (!isl_space_is_equal(ls1->dim, ls2->dim))
740 isl_die(ctx, isl_error_invalid,
741 "spaces should be identical", goto error);
743 if (ls2->div->n_row == 0) {
744 isl_local_space_free(ls2);
745 return ls1;
748 if (ls1->div->n_row == 0) {
749 isl_local_space_free(ls1);
750 return ls2;
753 exp1 = isl_alloc_array(ctx, int, ls1->div->n_row);
754 exp2 = isl_alloc_array(ctx, int, ls2->div->n_row);
755 if (!exp1 || !exp2)
756 goto error;
758 div = isl_merge_divs(ls1->div, ls2->div, exp1, exp2);
759 if (!div)
760 goto error;
762 equal = isl_mat_is_equal(ls1->div, div);
763 if (equal < 0)
764 goto error;
765 if (!equal)
766 ls1 = isl_local_space_cow(ls1);
767 if (!ls1)
768 goto error;
770 free(exp1);
771 free(exp2);
772 isl_local_space_free(ls2);
773 isl_mat_free(ls1->div);
774 ls1->div = div;
776 return ls1;
777 error:
778 free(exp1);
779 free(exp2);
780 isl_local_space_free(ls1);
781 isl_local_space_free(ls2);
782 return NULL;
785 /* Is the local variable "div" of "ls" marked as not having
786 * an explicit representation?
787 * Note that even if this variable is not marked in this way and therefore
788 * does have an explicit representation, this representation may still
789 * depend (indirectly) on other local variables that do not
790 * have an explicit representation.
792 isl_bool isl_local_space_div_is_marked_unknown(__isl_keep isl_local_space *ls,
793 int div)
795 if (!ls)
796 return isl_bool_error;
797 return isl_local_div_is_marked_unknown(ls->div, div);
800 /* Does "ls" have a complete explicit representation for div "div"?
802 isl_bool isl_local_space_div_is_known(__isl_keep isl_local_space *ls, int div)
804 if (!ls)
805 return isl_bool_error;
806 return isl_local_div_is_known(ls->div, div);
809 /* Does "ls" have an explicit representation for all local variables?
811 isl_bool isl_local_space_divs_known(__isl_keep isl_local_space *ls)
813 int i;
815 if (!ls)
816 return isl_bool_error;
818 for (i = 0; i < ls->div->n_row; ++i) {
819 isl_bool unknown = isl_local_space_div_is_marked_unknown(ls, i);
820 if (unknown < 0 || unknown)
821 return isl_bool_not(unknown);
824 return isl_bool_true;
827 __isl_give isl_local_space *isl_local_space_domain(
828 __isl_take isl_local_space *ls)
830 ls = isl_local_space_drop_dims(ls, isl_dim_out,
831 0, isl_local_space_dim(ls, isl_dim_out));
832 ls = isl_local_space_cow(ls);
833 if (!ls)
834 return NULL;
835 ls->dim = isl_space_domain(ls->dim);
836 if (!ls->dim)
837 return isl_local_space_free(ls);
838 return ls;
841 __isl_give isl_local_space *isl_local_space_range(
842 __isl_take isl_local_space *ls)
844 ls = isl_local_space_drop_dims(ls, isl_dim_in,
845 0, isl_local_space_dim(ls, isl_dim_in));
846 ls = isl_local_space_cow(ls);
847 if (!ls)
848 return NULL;
850 ls->dim = isl_space_range(ls->dim);
851 if (!ls->dim)
852 return isl_local_space_free(ls);
853 return ls;
856 /* Construct a local space for a map that has the given local
857 * space as domain and that has a zero-dimensional range.
859 __isl_give isl_local_space *isl_local_space_from_domain(
860 __isl_take isl_local_space *ls)
862 ls = isl_local_space_cow(ls);
863 if (!ls)
864 return NULL;
865 ls->dim = isl_space_from_domain(ls->dim);
866 if (!ls->dim)
867 return isl_local_space_free(ls);
868 return ls;
871 __isl_give isl_local_space *isl_local_space_add_dims(
872 __isl_take isl_local_space *ls, enum isl_dim_type type, unsigned n)
874 int pos;
876 if (!ls)
877 return NULL;
878 pos = isl_local_space_dim(ls, type);
879 return isl_local_space_insert_dims(ls, type, pos, n);
882 /* Remove common factor of non-constant terms and denominator.
884 static void normalize_div(__isl_keep isl_local_space *ls, int div)
886 isl_ctx *ctx = ls->div->ctx;
887 unsigned total = ls->div->n_col - 2;
889 isl_seq_gcd(ls->div->row[div] + 2, total, &ctx->normalize_gcd);
890 isl_int_gcd(ctx->normalize_gcd,
891 ctx->normalize_gcd, ls->div->row[div][0]);
892 if (isl_int_is_one(ctx->normalize_gcd))
893 return;
895 isl_seq_scale_down(ls->div->row[div] + 2, ls->div->row[div] + 2,
896 ctx->normalize_gcd, total);
897 isl_int_divexact(ls->div->row[div][0], ls->div->row[div][0],
898 ctx->normalize_gcd);
899 isl_int_fdiv_q(ls->div->row[div][1], ls->div->row[div][1],
900 ctx->normalize_gcd);
903 /* Exploit the equalities in "eq" to simplify the expressions of
904 * the integer divisions in "ls".
905 * The integer divisions in "ls" are assumed to appear as regular
906 * dimensions in "eq".
908 __isl_give isl_local_space *isl_local_space_substitute_equalities(
909 __isl_take isl_local_space *ls, __isl_take isl_basic_set *eq)
911 int i, j, k;
912 unsigned total;
913 unsigned n_div;
915 if (!ls || !eq)
916 goto error;
918 total = isl_space_dim(eq->dim, isl_dim_all);
919 if (isl_local_space_dim(ls, isl_dim_all) != total)
920 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
921 "spaces don't match", goto error);
922 total++;
923 n_div = eq->n_div;
924 for (i = 0; i < eq->n_eq; ++i) {
925 j = isl_seq_last_non_zero(eq->eq[i], total + n_div);
926 if (j < 0 || j == 0 || j >= total)
927 continue;
929 for (k = 0; k < ls->div->n_row; ++k) {
930 if (isl_int_is_zero(ls->div->row[k][1 + j]))
931 continue;
932 ls = isl_local_space_cow(ls);
933 if (!ls)
934 goto error;
935 ls->div = isl_mat_cow(ls->div);
936 if (!ls->div)
937 goto error;
938 isl_seq_elim(ls->div->row[k] + 1, eq->eq[i], j, total,
939 &ls->div->row[k][0]);
940 normalize_div(ls, k);
944 isl_basic_set_free(eq);
945 return ls;
946 error:
947 isl_basic_set_free(eq);
948 isl_local_space_free(ls);
949 return NULL;
952 /* Plug in the affine expressions "subs" of length "subs_len" (including
953 * the denominator and the constant term) into the variable at position "pos"
954 * of the "n" div expressions starting at "first".
956 * Let i be the dimension to replace and let "subs" be of the form
958 * f/d
960 * Any integer division starting at "first" with a non-zero coefficient for i,
962 * floor((a i + g)/m)
964 * is replaced by
966 * floor((a f + d g)/(m d))
968 __isl_give isl_local_space *isl_local_space_substitute_seq(
969 __isl_take isl_local_space *ls,
970 enum isl_dim_type type, unsigned pos, isl_int *subs, int subs_len,
971 int first, int n)
973 int i;
974 isl_int v;
976 if (n == 0)
977 return ls;
978 ls = isl_local_space_cow(ls);
979 if (!ls)
980 return NULL;
981 ls->div = isl_mat_cow(ls->div);
982 if (!ls->div)
983 return isl_local_space_free(ls);
985 if (first + n > ls->div->n_row)
986 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
987 "index out of bounds", return isl_local_space_free(ls));
989 pos += isl_local_space_offset(ls, type);
991 isl_int_init(v);
992 for (i = first; i < first + n; ++i) {
993 if (isl_int_is_zero(ls->div->row[i][1 + pos]))
994 continue;
995 isl_seq_substitute(ls->div->row[i], pos, subs,
996 ls->div->n_col, subs_len, v);
997 normalize_div(ls, i);
999 isl_int_clear(v);
1001 return ls;
1004 /* Plug in "subs" for dimension "type", "pos" in the integer divisions
1005 * of "ls".
1007 * Let i be the dimension to replace and let "subs" be of the form
1009 * f/d
1011 * Any integer division with a non-zero coefficient for i,
1013 * floor((a i + g)/m)
1015 * is replaced by
1017 * floor((a f + d g)/(m d))
1019 __isl_give isl_local_space *isl_local_space_substitute(
1020 __isl_take isl_local_space *ls,
1021 enum isl_dim_type type, unsigned pos, __isl_keep isl_aff *subs)
1023 ls = isl_local_space_cow(ls);
1024 if (!ls || !subs)
1025 return isl_local_space_free(ls);
1027 if (!isl_space_is_equal(ls->dim, subs->ls->dim))
1028 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
1029 "spaces don't match", return isl_local_space_free(ls));
1030 if (isl_local_space_dim(subs->ls, isl_dim_div) != 0)
1031 isl_die(isl_local_space_get_ctx(ls), isl_error_unsupported,
1032 "cannot handle divs yet",
1033 return isl_local_space_free(ls));
1035 return isl_local_space_substitute_seq(ls, type, pos, subs->v->el,
1036 subs->v->size, 0, ls->div->n_row);
1039 int isl_local_space_is_named_or_nested(__isl_keep isl_local_space *ls,
1040 enum isl_dim_type type)
1042 if (!ls)
1043 return -1;
1044 return isl_space_is_named_or_nested(ls->dim, type);
1047 __isl_give isl_local_space *isl_local_space_drop_dims(
1048 __isl_take isl_local_space *ls,
1049 enum isl_dim_type type, unsigned first, unsigned n)
1051 isl_ctx *ctx;
1053 if (!ls)
1054 return NULL;
1055 if (n == 0 && !isl_local_space_is_named_or_nested(ls, type))
1056 return ls;
1058 ctx = isl_local_space_get_ctx(ls);
1059 if (first + n > isl_local_space_dim(ls, type))
1060 isl_die(ctx, isl_error_invalid, "range out of bounds",
1061 return isl_local_space_free(ls));
1063 ls = isl_local_space_cow(ls);
1064 if (!ls)
1065 return NULL;
1067 if (type == isl_dim_div) {
1068 ls->div = isl_mat_drop_rows(ls->div, first, n);
1069 } else {
1070 ls->dim = isl_space_drop_dims(ls->dim, type, first, n);
1071 if (!ls->dim)
1072 return isl_local_space_free(ls);
1075 first += 1 + isl_local_space_offset(ls, type);
1076 ls->div = isl_mat_drop_cols(ls->div, first, n);
1077 if (!ls->div)
1078 return isl_local_space_free(ls);
1080 return ls;
1083 __isl_give isl_local_space *isl_local_space_insert_dims(
1084 __isl_take isl_local_space *ls,
1085 enum isl_dim_type type, unsigned first, unsigned n)
1087 isl_ctx *ctx;
1089 if (!ls)
1090 return NULL;
1091 if (n == 0 && !isl_local_space_is_named_or_nested(ls, type))
1092 return ls;
1094 ctx = isl_local_space_get_ctx(ls);
1095 if (first > isl_local_space_dim(ls, type))
1096 isl_die(ctx, isl_error_invalid, "position out of bounds",
1097 return isl_local_space_free(ls));
1099 ls = isl_local_space_cow(ls);
1100 if (!ls)
1101 return NULL;
1103 if (type == isl_dim_div) {
1104 ls->div = isl_mat_insert_zero_rows(ls->div, first, n);
1105 } else {
1106 ls->dim = isl_space_insert_dims(ls->dim, type, first, n);
1107 if (!ls->dim)
1108 return isl_local_space_free(ls);
1111 first += 1 + isl_local_space_offset(ls, type);
1112 ls->div = isl_mat_insert_zero_cols(ls->div, first, n);
1113 if (!ls->div)
1114 return isl_local_space_free(ls);
1116 return ls;
1119 /* Check if the constraints pointed to by "constraint" is a div
1120 * constraint corresponding to div "div" in "ls".
1122 * That is, if div = floor(f/m), then check if the constraint is
1124 * f - m d >= 0
1125 * or
1126 * -(f-(m-1)) + m d >= 0
1128 int isl_local_space_is_div_constraint(__isl_keep isl_local_space *ls,
1129 isl_int *constraint, unsigned div)
1131 unsigned pos;
1133 if (!ls)
1134 return -1;
1136 if (isl_int_is_zero(ls->div->row[div][0]))
1137 return 0;
1139 pos = isl_local_space_offset(ls, isl_dim_div) + div;
1141 if (isl_int_eq(constraint[pos], ls->div->row[div][0])) {
1142 int neg;
1143 isl_int_sub(ls->div->row[div][1],
1144 ls->div->row[div][1], ls->div->row[div][0]);
1145 isl_int_add_ui(ls->div->row[div][1], ls->div->row[div][1], 1);
1146 neg = isl_seq_is_neg(constraint, ls->div->row[div]+1, pos);
1147 isl_int_sub_ui(ls->div->row[div][1], ls->div->row[div][1], 1);
1148 isl_int_add(ls->div->row[div][1],
1149 ls->div->row[div][1], ls->div->row[div][0]);
1150 if (!neg)
1151 return 0;
1152 if (isl_seq_first_non_zero(constraint+pos+1,
1153 ls->div->n_row-div-1) != -1)
1154 return 0;
1155 } else if (isl_int_abs_eq(constraint[pos], ls->div->row[div][0])) {
1156 if (!isl_seq_eq(constraint, ls->div->row[div]+1, pos))
1157 return 0;
1158 if (isl_seq_first_non_zero(constraint+pos+1,
1159 ls->div->n_row-div-1) != -1)
1160 return 0;
1161 } else
1162 return 0;
1164 return 1;
1168 * Set active[i] to 1 if the dimension at position i is involved
1169 * in the linear expression l.
1171 int *isl_local_space_get_active(__isl_keep isl_local_space *ls, isl_int *l)
1173 int i, j;
1174 isl_ctx *ctx;
1175 int *active = NULL;
1176 unsigned total;
1177 unsigned offset;
1179 ctx = isl_local_space_get_ctx(ls);
1180 total = isl_local_space_dim(ls, isl_dim_all);
1181 active = isl_calloc_array(ctx, int, total);
1182 if (total && !active)
1183 return NULL;
1185 for (i = 0; i < total; ++i)
1186 active[i] = !isl_int_is_zero(l[i]);
1188 offset = isl_local_space_offset(ls, isl_dim_div) - 1;
1189 for (i = ls->div->n_row - 1; i >= 0; --i) {
1190 if (!active[offset + i])
1191 continue;
1192 for (j = 0; j < total; ++j)
1193 active[j] |= !isl_int_is_zero(ls->div->row[i][2 + j]);
1196 return active;
1199 /* Given a local space "ls" of a set, create a local space
1200 * for the lift of the set. In particular, the result
1201 * is of the form [dim -> local[..]], with ls->div->n_row variables in the
1202 * range of the wrapped map.
1204 __isl_give isl_local_space *isl_local_space_lift(
1205 __isl_take isl_local_space *ls)
1207 ls = isl_local_space_cow(ls);
1208 if (!ls)
1209 return NULL;
1211 ls->dim = isl_space_lift(ls->dim, ls->div->n_row);
1212 ls->div = isl_mat_drop_rows(ls->div, 0, ls->div->n_row);
1213 if (!ls->dim || !ls->div)
1214 return isl_local_space_free(ls);
1216 return ls;
1219 /* Construct a basic map that maps a set living in local space "ls"
1220 * to the corresponding lifted local space.
1222 __isl_give isl_basic_map *isl_local_space_lifting(
1223 __isl_take isl_local_space *ls)
1225 isl_basic_map *lifting;
1226 isl_basic_set *bset;
1228 if (!ls)
1229 return NULL;
1230 if (!isl_local_space_is_set(ls))
1231 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
1232 "lifting only defined on set spaces", goto error);
1234 bset = isl_basic_set_from_local_space(ls);
1235 lifting = isl_basic_set_unwrap(isl_basic_set_lift(bset));
1236 lifting = isl_basic_map_domain_map(lifting);
1237 lifting = isl_basic_map_reverse(lifting);
1239 return lifting;
1240 error:
1241 isl_local_space_free(ls);
1242 return NULL;
1245 /* Compute the preimage of "ls" under the function represented by "ma".
1246 * In other words, plug in "ma" in "ls". The result is a local space
1247 * that is part of the domain space of "ma".
1249 * If the divs in "ls" are represented as
1251 * floor((a_i(p) + b_i x + c_i(divs))/n_i)
1253 * and ma is represented by
1255 * x = D(p) + F(y) + G(divs')
1257 * then the resulting divs are
1259 * floor((a_i(p) + b_i D(p) + b_i F(y) + B_i G(divs') + c_i(divs))/n_i)
1261 * We first copy over the divs from "ma" and then
1262 * we add the modified divs from "ls".
1264 __isl_give isl_local_space *isl_local_space_preimage_multi_aff(
1265 __isl_take isl_local_space *ls, __isl_take isl_multi_aff *ma)
1267 int i;
1268 isl_space *space;
1269 isl_local_space *res = NULL;
1270 int n_div_ls, n_div_ma;
1271 isl_int f, c1, c2, g;
1273 ma = isl_multi_aff_align_divs(ma);
1274 if (!ls || !ma)
1275 goto error;
1276 if (!isl_space_is_range_internal(ls->dim, ma->space))
1277 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
1278 "spaces don't match", goto error);
1280 n_div_ls = isl_local_space_dim(ls, isl_dim_div);
1281 n_div_ma = ma->n ? isl_aff_dim(ma->p[0], isl_dim_div) : 0;
1283 space = isl_space_domain(isl_multi_aff_get_space(ma));
1284 res = isl_local_space_alloc(space, n_div_ma + n_div_ls);
1285 if (!res)
1286 goto error;
1288 if (n_div_ma) {
1289 isl_mat_free(res->div);
1290 res->div = isl_mat_copy(ma->p[0]->ls->div);
1291 res->div = isl_mat_add_zero_cols(res->div, n_div_ls);
1292 res->div = isl_mat_add_rows(res->div, n_div_ls);
1293 if (!res->div)
1294 goto error;
1297 isl_int_init(f);
1298 isl_int_init(c1);
1299 isl_int_init(c2);
1300 isl_int_init(g);
1302 for (i = 0; i < ls->div->n_row; ++i) {
1303 if (isl_int_is_zero(ls->div->row[i][0])) {
1304 isl_int_set_si(res->div->row[n_div_ma + i][0], 0);
1305 continue;
1307 isl_seq_preimage(res->div->row[n_div_ma + i], ls->div->row[i],
1308 ma, 0, 0, n_div_ma, n_div_ls, f, c1, c2, g, 1);
1309 normalize_div(res, n_div_ma + i);
1312 isl_int_clear(f);
1313 isl_int_clear(c1);
1314 isl_int_clear(c2);
1315 isl_int_clear(g);
1317 isl_local_space_free(ls);
1318 isl_multi_aff_free(ma);
1319 return res;
1320 error:
1321 isl_local_space_free(ls);
1322 isl_multi_aff_free(ma);
1323 isl_local_space_free(res);
1324 return NULL;
1327 /* Move the "n" dimensions of "src_type" starting at "src_pos" of "ls"
1328 * to dimensions of "dst_type" at "dst_pos".
1330 * Moving to/from local dimensions is not allowed.
1331 * We currently assume that the dimension type changes.
1333 __isl_give isl_local_space *isl_local_space_move_dims(
1334 __isl_take isl_local_space *ls,
1335 enum isl_dim_type dst_type, unsigned dst_pos,
1336 enum isl_dim_type src_type, unsigned src_pos, unsigned n)
1338 unsigned g_dst_pos;
1339 unsigned g_src_pos;
1341 if (!ls)
1342 return NULL;
1343 if (n == 0 &&
1344 !isl_local_space_is_named_or_nested(ls, src_type) &&
1345 !isl_local_space_is_named_or_nested(ls, dst_type))
1346 return ls;
1348 if (src_pos + n > isl_local_space_dim(ls, src_type))
1349 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
1350 "range out of bounds", return isl_local_space_free(ls));
1351 if (dst_pos > isl_local_space_dim(ls, dst_type))
1352 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
1353 "position out of bounds",
1354 return isl_local_space_free(ls));
1355 if (src_type == isl_dim_div)
1356 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
1357 "cannot move divs", return isl_local_space_free(ls));
1358 if (dst_type == isl_dim_div)
1359 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
1360 "cannot move to divs", return isl_local_space_free(ls));
1361 if (dst_type == src_type && dst_pos == src_pos)
1362 return ls;
1363 if (dst_type == src_type)
1364 isl_die(isl_local_space_get_ctx(ls), isl_error_unsupported,
1365 "moving dims within the same type not supported",
1366 return isl_local_space_free(ls));
1368 ls = isl_local_space_cow(ls);
1369 if (!ls)
1370 return NULL;
1372 g_src_pos = 1 + isl_local_space_offset(ls, src_type) + src_pos;
1373 g_dst_pos = 1 + isl_local_space_offset(ls, dst_type) + dst_pos;
1374 if (dst_type > src_type)
1375 g_dst_pos -= n;
1376 ls->div = isl_mat_move_cols(ls->div, g_dst_pos, g_src_pos, n);
1377 if (!ls->div)
1378 return isl_local_space_free(ls);
1379 ls->dim = isl_space_move_dims(ls->dim, dst_type, dst_pos,
1380 src_type, src_pos, n);
1381 if (!ls->dim)
1382 return isl_local_space_free(ls);
1384 return ls;
1387 /* Remove any internal structure of the domain of "ls".
1388 * If there is any such internal structure in the input,
1389 * then the name of the corresponding space is also removed.
1391 __isl_give isl_local_space *isl_local_space_flatten_domain(
1392 __isl_take isl_local_space *ls)
1394 if (!ls)
1395 return NULL;
1397 if (!ls->dim->nested[0])
1398 return ls;
1400 ls = isl_local_space_cow(ls);
1401 if (!ls)
1402 return NULL;
1404 ls->dim = isl_space_flatten_domain(ls->dim);
1405 if (!ls->dim)
1406 return isl_local_space_free(ls);
1408 return ls;
1411 /* Remove any internal structure of the range of "ls".
1412 * If there is any such internal structure in the input,
1413 * then the name of the corresponding space is also removed.
1415 __isl_give isl_local_space *isl_local_space_flatten_range(
1416 __isl_take isl_local_space *ls)
1418 if (!ls)
1419 return NULL;
1421 if (!ls->dim->nested[1])
1422 return ls;
1424 ls = isl_local_space_cow(ls);
1425 if (!ls)
1426 return NULL;
1428 ls->dim = isl_space_flatten_range(ls->dim);
1429 if (!ls->dim)
1430 return isl_local_space_free(ls);
1432 return ls;
1435 /* Given the local space "ls" of a map, return the local space of a set
1436 * that lives in a space that wraps the space of "ls" and that has
1437 * the same divs.
1439 __isl_give isl_local_space *isl_local_space_wrap(__isl_take isl_local_space *ls)
1441 ls = isl_local_space_cow(ls);
1442 if (!ls)
1443 return NULL;
1445 ls->dim = isl_space_wrap(ls->dim);
1446 if (!ls->dim)
1447 return isl_local_space_free(ls);
1449 return ls;