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