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