?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
isl_map_simplify.c: div_is_redundant: use isl_basic_map_offset
[isl.git] / isl_space.c
blob26a3d2554c4aa6b0489ec64eff39cbbbae4e3d31
1 /*
2 * Copyright 2008-2009 Katholieke Universiteit Leuven
3 * Copyright 2010 INRIA Saclay
4 * Copyright 2013-2014 Ecole Normale Superieure
5 *
6 * Use of this software is governed by the MIT license
7 *
8 * Written by Sven Verdoolaege, K.U.Leuven, Departement
9 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
10 * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,
11 * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France
12 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
13 */
14
15 #include <stdlib.h>
16 #include <string.h>
17 #include <isl_space_private.h>
18 #include <isl_id_private.h>
19 #include <isl_reordering.h>
20
21 isl_ctx *isl_space_get_ctx(__isl_keep isl_space *space)
22 {
23 return space ? space->ctx : NULL;
24 }
25
26 __isl_give isl_space *isl_space_alloc(isl_ctx *ctx,
27 unsigned nparam, unsigned n_in, unsigned n_out)
28 {
29 isl_space *space;
30
31 space = isl_alloc_type(ctx, struct isl_space);
32 if (!space)
33 return NULL;
34
35 space->ctx = ctx;
36 isl_ctx_ref(ctx);
37 space->ref = 1;
38 space->nparam = nparam;
39 space->n_in = n_in;
40 space->n_out = n_out;
41
42 space->tuple_id[0] = NULL;
43 space->tuple_id[1] = NULL;
44
45 space->nested[0] = NULL;
46 space->nested[1] = NULL;
47
48 space->n_id = 0;
49 space->ids = NULL;
50
51 return space;
52 }
53
54 /* Mark the space as being that of a set, by setting the domain tuple
55 * to isl_id_none.
56 */
57 static __isl_give isl_space *mark_as_set(__isl_take isl_space *space)
58 {
59 space = isl_space_cow(space);
60 if (!space)
61 return NULL;
62 space = isl_space_set_tuple_id(space, isl_dim_in, &isl_id_none);
63 return space;
64 }
65
66 /* Is the space that of a set?
67 */
68 isl_bool isl_space_is_set(__isl_keep isl_space *space)
69 {
70 if (!space)
71 return isl_bool_error;
72 if (space->n_in != 0 || space->nested[0])
73 return isl_bool_false;
74 if (space->tuple_id[0] != &isl_id_none)
75 return isl_bool_false;
76 return isl_bool_true;
77 }
78
79 /* Check that "space" is a set space.
80 */
81 isl_stat isl_space_check_is_set(__isl_keep isl_space *space)
82 {
83 isl_bool is_set;
84
85 is_set = isl_space_is_set(space);
86 if (is_set < 0)
87 return isl_stat_error;
88 if (!is_set)
89 isl_die(isl_space_get_ctx(space), isl_error_invalid,
90 "space is not a set", return isl_stat_error);
91 return isl_stat_ok;
92 }
93
94 /* Is the given space that of a map?
95 */
96 isl_bool isl_space_is_map(__isl_keep isl_space *space)
97 {
98 if (!space)
99 return isl_bool_error;
100 return space->tuple_id[0] != &isl_id_none &&
101 space->tuple_id[1] != &isl_id_none;
102 }
103
104 __isl_give isl_space *isl_space_set_alloc(isl_ctx *ctx,
105 unsigned nparam, unsigned dim)
106 {
107 isl_space *space;
108 space = isl_space_alloc(ctx, nparam, 0, dim);
109 space = mark_as_set(space);
110 return space;
111 }
112
113 /* Mark the space as being that of a parameter domain, by setting
114 * both tuples to isl_id_none.
115 */
116 static __isl_give isl_space *mark_as_params(isl_space *space)
117 {
118 if (!space)
119 return NULL;
120 space = isl_space_set_tuple_id(space, isl_dim_in, &isl_id_none);
121 space = isl_space_set_tuple_id(space, isl_dim_out, &isl_id_none);
122 return space;
123 }
124
125 /* Is the space that of a parameter domain?
126 */
127 isl_bool isl_space_is_params(__isl_keep isl_space *space)
128 {
129 if (!space)
130 return isl_bool_error;
131 if (space->n_in != 0 || space->nested[0] ||
132 space->n_out != 0 || space->nested[1])
133 return isl_bool_false;
134 if (space->tuple_id[0] != &isl_id_none)
135 return isl_bool_false;
136 if (space->tuple_id[1] != &isl_id_none)
137 return isl_bool_false;
138 return isl_bool_true;
139 }
140
141 /* Create a space for a parameter domain.
142 */
143 __isl_give isl_space *isl_space_params_alloc(isl_ctx *ctx, unsigned nparam)
144 {
145 isl_space *space;
146 space = isl_space_alloc(ctx, nparam, 0, 0);
147 space = mark_as_params(space);
148 return space;
149 }
150
151 static int global_pos(__isl_keep isl_space *space,
152 enum isl_dim_type type, unsigned pos)
153 {
154 if (isl_space_check_range(space, type, pos, 1) < 0)
155 return -1;
156
157 switch (type) {
158 case isl_dim_param:
159 return pos;
160 case isl_dim_in:
161 return pos + space->nparam;
162 case isl_dim_out:
163 return pos + space->nparam + space->n_in;
164 default:
165 isl_assert(isl_space_get_ctx(space), 0, return -1);
166 }
167 return -1;
168 }
169
170 /* Extend length of ids array to the total number of dimensions.
171 */
172 static __isl_give isl_space *extend_ids(__isl_take isl_space *space)
173 {
174 isl_id **ids;
175 int i;
176
177 if (isl_space_dim(space, isl_dim_all) <= space->n_id)
178 return space;
179
180 if (!space->ids) {
181 space->ids = isl_calloc_array(space->ctx,
182 isl_id *, isl_space_dim(space, isl_dim_all));
183 if (!space->ids)
184 goto error;
185 } else {
186 ids = isl_realloc_array(space->ctx, space->ids,
187 isl_id *, isl_space_dim(space, isl_dim_all));
188 if (!ids)
189 goto error;
190 space->ids = ids;
191 for (i = space->n_id; i < isl_space_dim(space, isl_dim_all); ++i)
192 space->ids[i] = NULL;
193 }
194
195 space->n_id = isl_space_dim(space, isl_dim_all);
196
197 return space;
198 error:
199 isl_space_free(space);
200 return NULL;
201 }
202
203 static __isl_give isl_space *set_id(__isl_take isl_space *space,
204 enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
205 {
206 int gpos;
207
208 space = isl_space_cow(space);
209
210 gpos = global_pos(space, type, pos);
211 if (gpos < 0)
212 goto error;
213
214 if (gpos >= space->n_id) {
215 if (!id)
216 return space;
217 space = extend_ids(space);
218 if (!space)
219 goto error;
220 }
221
222 space->ids[gpos] = id;
223
224 return space;
225 error:
226 isl_id_free(id);
227 isl_space_free(space);
228 return NULL;
229 }
230
231 static __isl_keep isl_id *get_id(__isl_keep isl_space *space,
232 enum isl_dim_type type, unsigned pos)
233 {
234 int gpos;
235
236 gpos = global_pos(space, type, pos);
237 if (gpos < 0)
238 return NULL;
239 if (gpos >= space->n_id)
240 return NULL;
241 return space->ids[gpos];
242 }
243
244 static unsigned offset(__isl_keep isl_space *space, enum isl_dim_type type)
245 {
246 switch (type) {
247 case isl_dim_param: return 0;
248 case isl_dim_in: return space->nparam;
249 case isl_dim_out: return space->nparam + space->n_in;
250 default: return 0;
251 }
252 }
253
254 static unsigned n(__isl_keep isl_space *space, enum isl_dim_type type)
255 {
256 switch (type) {
257 case isl_dim_param: return space->nparam;
258 case isl_dim_in: return space->n_in;
259 case isl_dim_out: return space->n_out;
260 case isl_dim_all:
261 return space->nparam + space->n_in + space->n_out;
262 default: return 0;
263 }
264 }
265
266 unsigned isl_space_dim(__isl_keep isl_space *space, enum isl_dim_type type)
267 {
268 if (!space)
269 return 0;
270 return n(space, type);
271 }
272
273 unsigned isl_space_offset(__isl_keep isl_space *dim, enum isl_dim_type type)
274 {
275 if (!dim)
276 return 0;
277 return offset(dim, type);
278 }
279
280 static __isl_give isl_space *copy_ids(__isl_take isl_space *dst,
281 enum isl_dim_type dst_type, unsigned offset, __isl_keep isl_space *src,
282 enum isl_dim_type src_type)
283 {
284 int i;
285 isl_id *id;
286
287 if (!dst)
288 return NULL;
289
290 for (i = 0; i < n(src, src_type); ++i) {
291 id = get_id(src, src_type, i);
292 if (!id)
293 continue;
294 dst = set_id(dst, dst_type, offset + i, isl_id_copy(id));
295 if (!dst)
296 return NULL;
297 }
298 return dst;
299 }
300
301 __isl_take isl_space *isl_space_dup(__isl_keep isl_space *space)
302 {
303 isl_space *dup;
304 if (!space)
305 return NULL;
306 dup = isl_space_alloc(space->ctx,
307 space->nparam, space->n_in, space->n_out);
308 if (!dup)
309 return NULL;
310 if (space->tuple_id[0] &&
311 !(dup->tuple_id[0] = isl_id_copy(space->tuple_id[0])))
312 goto error;
313 if (space->tuple_id[1] &&
314 !(dup->tuple_id[1] = isl_id_copy(space->tuple_id[1])))
315 goto error;
316 if (space->nested[0] &&
317 !(dup->nested[0] = isl_space_copy(space->nested[0])))
318 goto error;
319 if (space->nested[1] &&
320 !(dup->nested[1] = isl_space_copy(space->nested[1])))
321 goto error;
322 if (!space->ids)
323 return dup;
324 dup = copy_ids(dup, isl_dim_param, 0, space, isl_dim_param);
325 dup = copy_ids(dup, isl_dim_in, 0, space, isl_dim_in);
326 dup = copy_ids(dup, isl_dim_out, 0, space, isl_dim_out);
327 return dup;
328 error:
329 isl_space_free(dup);
330 return NULL;
331 }
332
333 __isl_give isl_space *isl_space_cow(__isl_take isl_space *space)
334 {
335 if (!space)
336 return NULL;
337
338 if (space->ref == 1)
339 return space;
340 space->ref--;
341 return isl_space_dup(space);
342 }
343
344 __isl_give isl_space *isl_space_copy(__isl_keep isl_space *dim)
345 {
346 if (!dim)
347 return NULL;
348
349 dim->ref++;
350 return dim;
351 }
352
353 __isl_null isl_space *isl_space_free(__isl_take isl_space *space)
354 {
355 int i;
356
357 if (!space)
358 return NULL;
359
360 if (--space->ref > 0)
361 return NULL;
362
363 isl_id_free(space->tuple_id[0]);
364 isl_id_free(space->tuple_id[1]);
365
366 isl_space_free(space->nested[0]);
367 isl_space_free(space->nested[1]);
368
369 for (i = 0; i < space->n_id; ++i)
370 isl_id_free(space->ids[i]);
371 free(space->ids);
372 isl_ctx_deref(space->ctx);
373
374 free(space);
375
376 return NULL;
377 }
378
379 /* Check if "s" is a valid dimension or tuple name.
380 * We currently only forbid names that look like a number.
381 *
382 * s is assumed to be non-NULL.
383 */
384 static int name_ok(isl_ctx *ctx, const char *s)
385 {
386 char *p;
387 long dummy;
388
389 dummy = strtol(s, &p, 0);
390 if (p != s)
391 isl_die(ctx, isl_error_invalid, "name looks like a number",
392 return 0);
393
394 return 1;
395 }
396
397 /* Is it possible for the given dimension type to have a tuple id?
398 */
399 static int space_can_have_id(__isl_keep isl_space *space,
400 enum isl_dim_type type)
401 {
402 if (!space)
403 return 0;
404 if (isl_space_is_params(space))
405 isl_die(space->ctx, isl_error_invalid,
406 "parameter spaces don't have tuple ids", return 0);
407 if (isl_space_is_set(space) && type != isl_dim_set)
408 isl_die(space->ctx, isl_error_invalid,
409 "set spaces can only have a set id", return 0);
410 if (type != isl_dim_in && type != isl_dim_out)
411 isl_die(space->ctx, isl_error_invalid,
412 "only input, output and set tuples can have ids",
413 return 0);
414
415 return 1;
416 }
417
418 /* Does the tuple have an id?
419 */
420 isl_bool isl_space_has_tuple_id(__isl_keep isl_space *space,
421 enum isl_dim_type type)
422 {
423 if (!space_can_have_id(space, type))
424 return isl_bool_error;
425 return space->tuple_id[type - isl_dim_in] != NULL;
426 }
427
428 __isl_give isl_id *isl_space_get_tuple_id(__isl_keep isl_space *space,
429 enum isl_dim_type type)
430 {
431 int has_id;
432
433 if (!space)
434 return NULL;
435 has_id = isl_space_has_tuple_id(space, type);
436 if (has_id < 0)
437 return NULL;
438 if (!has_id)
439 isl_die(space->ctx, isl_error_invalid,
440 "tuple has no id", return NULL);
441 return isl_id_copy(space->tuple_id[type - isl_dim_in]);
442 }
443
444 __isl_give isl_space *isl_space_set_tuple_id(__isl_take isl_space *space,
445 enum isl_dim_type type, __isl_take isl_id *id)
446 {
447 space = isl_space_cow(space);
448 if (!space || !id)
449 goto error;
450 if (type != isl_dim_in && type != isl_dim_out)
451 isl_die(space->ctx, isl_error_invalid,
452 "only input, output and set tuples can have names",
453 goto error);
454
455 isl_id_free(space->tuple_id[type - isl_dim_in]);
456 space->tuple_id[type - isl_dim_in] = id;
457
458 return space;
459 error:
460 isl_id_free(id);
461 isl_space_free(space);
462 return NULL;
463 }
464
465 __isl_give isl_space *isl_space_reset_tuple_id(__isl_take isl_space *space,
466 enum isl_dim_type type)
467 {
468 space = isl_space_cow(space);
469 if (!space)
470 return NULL;
471 if (type != isl_dim_in && type != isl_dim_out)
472 isl_die(space->ctx, isl_error_invalid,
473 "only input, output and set tuples can have names",
474 goto error);
475
476 isl_id_free(space->tuple_id[type - isl_dim_in]);
477 space->tuple_id[type - isl_dim_in] = NULL;
478
479 return space;
480 error:
481 isl_space_free(space);
482 return NULL;
483 }
484
485 /* Set the id of the given dimension of "space" to "id".
486 * If the dimension already has an id, then it is replaced.
487 * If the dimension is a parameter, then we need to change it
488 * in the nested spaces (if any) as well.
489 */
490 __isl_give isl_space *isl_space_set_dim_id(__isl_take isl_space *space,
491 enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
492 {
493 space = isl_space_cow(space);
494 if (!space || !id)
495 goto error;
496
497 if (type == isl_dim_param) {
498 int i;
499
500 for (i = 0; i < 2; ++i) {
501 if (!space->nested[i])
502 continue;
503 space->nested[i] =
504 isl_space_set_dim_id(space->nested[i],
505 type, pos, isl_id_copy(id));
506 if (!space->nested[i])
507 goto error;
508 }
509 }
510
511 isl_id_free(get_id(space, type, pos));
512 return set_id(space, type, pos, id);
513 error:
514 isl_id_free(id);
515 isl_space_free(space);
516 return NULL;
517 }
518
519 /* Reset the id of the given dimension of "space".
520 * If the dimension already has an id, then it is removed.
521 * If the dimension is a parameter, then we need to reset it
522 * in the nested spaces (if any) as well.
523 */
524 __isl_give isl_space *isl_space_reset_dim_id(__isl_take isl_space *space,
525 enum isl_dim_type type, unsigned pos)
526 {
527 space = isl_space_cow(space);
528 if (!space)
529 goto error;
530
531 if (type == isl_dim_param) {
532 int i;
533
534 for (i = 0; i < 2; ++i) {
535 if (!space->nested[i])
536 continue;
537 space->nested[i] =
538 isl_space_reset_dim_id(space->nested[i],
539 type, pos);
540 if (!space->nested[i])
541 goto error;
542 }
543 }
544
545 isl_id_free(get_id(space, type, pos));
546 return set_id(space, type, pos, NULL);
547 error:
548 isl_space_free(space);
549 return NULL;
550 }
551
552 isl_bool isl_space_has_dim_id(__isl_keep isl_space *space,
553 enum isl_dim_type type, unsigned pos)
554 {
555 if (!space)
556 return isl_bool_error;
557 return get_id(space, type, pos) != NULL;
558 }
559
560 __isl_give isl_id *isl_space_get_dim_id(__isl_keep isl_space *space,
561 enum isl_dim_type type, unsigned pos)
562 {
563 if (!space)
564 return NULL;
565 if (!get_id(space, type, pos))
566 isl_die(space->ctx, isl_error_invalid,
567 "dim has no id", return NULL);
568 return isl_id_copy(get_id(space, type, pos));
569 }
570
571 __isl_give isl_space *isl_space_set_tuple_name(__isl_take isl_space *space,
572 enum isl_dim_type type, const char *s)
573 {
574 isl_id *id;
575
576 if (!space)
577 return NULL;
578
579 if (!s)
580 return isl_space_reset_tuple_id(space, type);
581
582 if (!name_ok(space->ctx, s))
583 goto error;
584
585 id = isl_id_alloc(space->ctx, s, NULL);
586 return isl_space_set_tuple_id(space, type, id);
587 error:
588 isl_space_free(space);
589 return NULL;
590 }
591
592 /* Does the tuple have a name?
593 */
594 isl_bool isl_space_has_tuple_name(__isl_keep isl_space *space,
595 enum isl_dim_type type)
596 {
597 isl_id *id;
598
599 if (!space_can_have_id(space, type))
600 return isl_bool_error;
601 id = space->tuple_id[type - isl_dim_in];
602 return id && id->name;
603 }
604
605 __isl_keep const char *isl_space_get_tuple_name(__isl_keep isl_space *space,
606 enum isl_dim_type type)
607 {
608 isl_id *id;
609 if (!space)
610 return NULL;
611 if (type != isl_dim_in && type != isl_dim_out)
612 return NULL;
613 id = space->tuple_id[type - isl_dim_in];
614 return id ? id->name : NULL;
615 }
616
617 __isl_give isl_space *isl_space_set_dim_name(__isl_take isl_space *space,
618 enum isl_dim_type type, unsigned pos,
619 const char *s)
620 {
621 isl_id *id;
622
623 if (!space)
624 return NULL;
625 if (!s)
626 return isl_space_reset_dim_id(space, type, pos);
627 if (!name_ok(space->ctx, s))
628 goto error;
629 id = isl_id_alloc(space->ctx, s, NULL);
630 return isl_space_set_dim_id(space, type, pos, id);
631 error:
632 isl_space_free(space);
633 return NULL;
634 }
635
636 /* Does the given dimension have a name?
637 */
638 isl_bool isl_space_has_dim_name(__isl_keep isl_space *space,
639 enum isl_dim_type type, unsigned pos)
640 {
641 isl_id *id;
642
643 if (!space)
644 return isl_bool_error;
645 id = get_id(space, type, pos);
646 return id && id->name;
647 }
648
649 __isl_keep const char *isl_space_get_dim_name(__isl_keep isl_space *space,
650 enum isl_dim_type type, unsigned pos)
651 {
652 isl_id *id = get_id(space, type, pos);
653 return id ? id->name : NULL;
654 }
655
656 int isl_space_find_dim_by_id(__isl_keep isl_space *space,
657 enum isl_dim_type type, __isl_keep isl_id *id)
658 {
659 int i;
660 int offset;
661 int n;
662
663 if (!space || !id)
664 return -1;
665
666 offset = isl_space_offset(space, type);
667 n = isl_space_dim(space, type);
668 for (i = 0; i < n && offset + i < space->n_id; ++i)
669 if (space->ids[offset + i] == id)
670 return i;
671
672 return -1;
673 }
674
675 int isl_space_find_dim_by_name(__isl_keep isl_space *space,
676 enum isl_dim_type type, const char *name)
677 {
678 int i;
679 int offset;
680 int n;
681
682 if (!space || !name)
683 return -1;
684
685 offset = isl_space_offset(space, type);
686 n = isl_space_dim(space, type);
687 for (i = 0; i < n && offset + i < space->n_id; ++i) {
688 isl_id *id = get_id(space, type, i);
689 if (id && id->name && !strcmp(id->name, name))
690 return i;
691 }
692
693 return -1;
694 }
695
696 /* Reset the user pointer on all identifiers of parameters and tuples
697 * of "space".
698 */
699 __isl_give isl_space *isl_space_reset_user(__isl_take isl_space *space)
700 {
701 int i;
702 isl_ctx *ctx;
703 isl_id *id;
704 const char *name;
705
706 if (!space)
707 return NULL;
708
709 ctx = isl_space_get_ctx(space);
710
711 for (i = 0; i < space->nparam && i < space->n_id; ++i) {
712 if (!isl_id_get_user(space->ids[i]))
713 continue;
714 space = isl_space_cow(space);
715 if (!space)
716 return NULL;
717 name = isl_id_get_name(space->ids[i]);
718 id = isl_id_alloc(ctx, name, NULL);
719 isl_id_free(space->ids[i]);
720 space->ids[i] = id;
721 if (!id)
722 return isl_space_free(space);
723 }
724
725 for (i = 0; i < 2; ++i) {
726 if (!space->tuple_id[i])
727 continue;
728 if (!isl_id_get_user(space->tuple_id[i]))
729 continue;
730 space = isl_space_cow(space);
731 if (!space)
732 return NULL;
733 name = isl_id_get_name(space->tuple_id[i]);
734 id = isl_id_alloc(ctx, name, NULL);
735 isl_id_free(space->tuple_id[i]);
736 space->tuple_id[i] = id;
737 if (!id)
738 return isl_space_free(space);
739 }
740
741 for (i = 0; i < 2; ++i) {
742 if (!space->nested[i])
743 continue;
744 space = isl_space_cow(space);
745 if (!space)
746 return NULL;
747 space->nested[i] = isl_space_reset_user(space->nested[i]);
748 if (!space->nested[i])
749 return isl_space_free(space);
750 }
751
752 return space;
753 }
754
755 static __isl_keep isl_id *tuple_id(__isl_keep isl_space *dim,
756 enum isl_dim_type type)
757 {
758 if (!dim)
759 return NULL;
760 if (type == isl_dim_in)
761 return dim->tuple_id[0];
762 if (type == isl_dim_out)
763 return dim->tuple_id[1];
764 return NULL;
765 }
766
767 static __isl_keep isl_space *nested(__isl_keep isl_space *dim,
768 enum isl_dim_type type)
769 {
770 if (!dim)
771 return NULL;
772 if (type == isl_dim_in)
773 return dim->nested[0];
774 if (type == isl_dim_out)
775 return dim->nested[1];
776 return NULL;
777 }
778
779 /* Are the two spaces the same, apart from positions and names of parameters?
780 */
781 isl_bool isl_space_has_equal_tuples(__isl_keep isl_space *space1,
782 __isl_keep isl_space *space2)
783 {
784 if (!space1 || !space2)
785 return isl_bool_error;
786 if (space1 == space2)
787 return isl_bool_true;
788 return isl_space_tuple_is_equal(space1, isl_dim_in,
789 space2, isl_dim_in) &&
790 isl_space_tuple_is_equal(space1, isl_dim_out,
791 space2, isl_dim_out);
792 }
793
794 /* Check if the tuple of type "type1" of "space1" is the same as
795 * the tuple of type "type2" of "space2".
796 *
797 * That is, check if the tuples have the same identifier, the same dimension
798 * and the same internal structure.
799 * The identifiers of the dimensions inside the tuples do not affect the result.
800 *
801 * Note that this function only checks the tuples themselves.
802 * If nested tuples are involved, then we need to be careful not
803 * to have result affected by possibly differing parameters
804 * in those nested tuples.
805 */
806 isl_bool isl_space_tuple_is_equal(__isl_keep isl_space *space1,
807 enum isl_dim_type type1, __isl_keep isl_space *space2,
808 enum isl_dim_type type2)
809 {
810 isl_id *id1, *id2;
811 isl_space *nested1, *nested2;
812
813 if (!space1 || !space2)
814 return isl_bool_error;
815
816 if (space1 == space2 && type1 == type2)
817 return isl_bool_true;
818
819 if (n(space1, type1) != n(space2, type2))
820 return isl_bool_false;
821 id1 = tuple_id(space1, type1);
822 id2 = tuple_id(space2, type2);
823 if (!id1 ^ !id2)
824 return isl_bool_false;
825 if (id1 && id1 != id2)
826 return isl_bool_false;
827 nested1 = nested(space1, type1);
828 nested2 = nested(space2, type2);
829 if (!nested1 ^ !nested2)
830 return isl_bool_false;
831 if (nested1 && !isl_space_has_equal_tuples(nested1, nested2))
832 return isl_bool_false;
833 return isl_bool_true;
834 }
835
836 static isl_bool match(__isl_keep isl_space *space1, enum isl_dim_type type1,
837 __isl_keep isl_space *space2, enum isl_dim_type type2)
838 {
839 int i;
840
841 if (space1 == space2 && type1 == type2)
842 return isl_bool_true;
843
844 if (!isl_space_tuple_is_equal(space1, type1, space2, type2))
845 return isl_bool_false;
846
847 if (!space1->ids && !space2->ids)
848 return isl_bool_true;
849
850 for (i = 0; i < n(space1, type1); ++i) {
851 if (get_id(space1, type1, i) != get_id(space2, type2, i))
852 return isl_bool_false;
853 }
854 return isl_bool_true;
855 }
856
857 /* Do "space1" and "space2" have the same parameters?
858 */
859 isl_bool isl_space_has_equal_params(__isl_keep isl_space *space1,
860 __isl_keep isl_space *space2)
861 {
862 if (!space1 || !space2)
863 return isl_bool_error;
864
865 return match(space1, isl_dim_param, space2, isl_dim_param);
866 }
867
868 /* Do "space1" and "space2" have the same identifiers for all
869 * the tuple variables?
870 */
871 isl_bool isl_space_has_equal_ids(__isl_keep isl_space *space1,
872 __isl_keep isl_space *space2)
873 {
874 isl_bool equal;
875
876 if (!space1 || !space2)
877 return isl_bool_error;
878
879 equal = match(space1, isl_dim_in, space2, isl_dim_in);
880 if (equal < 0 || !equal)
881 return equal;
882 return match(space1, isl_dim_out, space2, isl_dim_out);
883 }
884
885 isl_bool isl_space_match(__isl_keep isl_space *space1, enum isl_dim_type type1,
886 __isl_keep isl_space *space2, enum isl_dim_type type2)
887 {
888 if (!space1 || !space2)
889 return isl_bool_error;
890
891 return match(space1, type1, space2, type2);
892 }
893
894 static void get_ids(__isl_keep isl_space *dim, enum isl_dim_type type,
895 unsigned first, unsigned n, __isl_keep isl_id **ids)
896 {
897 int i;
898
899 for (i = 0; i < n ; ++i)
900 ids[i] = get_id(dim, type, first + i);
901 }
902
903 static __isl_give isl_space *space_extend(__isl_take isl_space *space,
904 unsigned nparam, unsigned n_in, unsigned n_out)
905 {
906 isl_id **ids = NULL;
907
908 if (!space)
909 return NULL;
910 if (space->nparam == nparam &&
911 space->n_in == n_in && space->n_out == n_out)
912 return space;
913
914 isl_assert(space->ctx, space->nparam <= nparam, goto error);
915 isl_assert(space->ctx, space->n_in <= n_in, goto error);
916 isl_assert(space->ctx, space->n_out <= n_out, goto error);
917
918 space = isl_space_cow(space);
919 if (!space)
920 goto error;
921
922 if (space->ids) {
923 unsigned n;
924 n = nparam + n_in + n_out;
925 if (n < nparam || n < n_in || n < n_out)
926 isl_die(isl_space_get_ctx(space), isl_error_invalid,
927 "overflow in total number of dimensions",
928 goto error);
929 ids = isl_calloc_array(space->ctx, isl_id *, n);
930 if (!ids)
931 goto error;
932 get_ids(space, isl_dim_param, 0, space->nparam, ids);
933 get_ids(space, isl_dim_in, 0, space->n_in, ids + nparam);
934 get_ids(space, isl_dim_out, 0, space->n_out,
935 ids + nparam + n_in);
936 free(space->ids);
937 space->ids = ids;
938 space->n_id = nparam + n_in + n_out;
939 }
940 space->nparam = nparam;
941 space->n_in = n_in;
942 space->n_out = n_out;
943
944 return space;
945 error:
946 free(ids);
947 isl_space_free(space);
948 return NULL;
949 }
950
951 __isl_give isl_space *isl_space_extend(__isl_take isl_space *space,
952 unsigned nparam, unsigned n_in, unsigned n_out)
953 {
954 return space_extend(space, nparam, n_in, n_out);
955 }
956
957 __isl_give isl_space *isl_space_add_dims(__isl_take isl_space *space,
958 enum isl_dim_type type, unsigned n)
959 {
960 space = isl_space_reset(space, type);
961 if (!space)
962 return NULL;
963 switch (type) {
964 case isl_dim_param:
965 space = space_extend(space,
966 space->nparam + n, space->n_in, space->n_out);
967 if (space && space->nested[0] &&
968 !(space->nested[0] = isl_space_add_dims(space->nested[0],
969 isl_dim_param, n)))
970 goto error;
971 if (space && space->nested[1] &&
972 !(space->nested[1] = isl_space_add_dims(space->nested[1],
973 isl_dim_param, n)))
974 goto error;
975 return space;
976 case isl_dim_in:
977 return space_extend(space,
978 space->nparam, space->n_in + n, space->n_out);
979 case isl_dim_out:
980 return space_extend(space,
981 space->nparam, space->n_in, space->n_out + n);
982 default:
983 isl_die(space->ctx, isl_error_invalid,
984 "cannot add dimensions of specified type", goto error);
985 }
986 error:
987 isl_space_free(space);
988 return NULL;
989 }
990
991 /* Add a parameter with identifier "id" to "space", provided
992 * it does not already appear in "space".
993 */
994 __isl_give isl_space *isl_space_add_param_id(__isl_take isl_space *space,
995 __isl_take isl_id *id)
996 {
997 int pos;
998
999 if (!space || !id)
1000 goto error;
1001
1002 if (isl_space_find_dim_by_id(space, isl_dim_param, id) >= 0) {
1003 isl_id_free(id);
1004 return space;
1005 }
1006
1007 pos = isl_space_dim(space, isl_dim_param);
1008 space = isl_space_add_dims(space, isl_dim_param, 1);
1009 space = isl_space_set_dim_id(space, isl_dim_param, pos, id);
1010
1011 return space;
1012 error:
1013 isl_space_free(space);
1014 isl_id_free(id);
1015 return NULL;
1016 }
1017
1018 static int valid_dim_type(enum isl_dim_type type)
1019 {
1020 switch (type) {
1021 case isl_dim_param:
1022 case isl_dim_in:
1023 case isl_dim_out:
1024 return 1;
1025 default:
1026 return 0;
1027 }
1028 }
1029
1030 #undef TYPE
1031 #define TYPE isl_space
1032 #include "check_type_range_templ.c"
1033
1034 /* Insert "n" dimensions of type "type" at position "pos".
1035 * If we are inserting parameters, then they are also inserted in
1036 * any nested spaces.
1037 */
1038 __isl_give isl_space *isl_space_insert_dims(__isl_take isl_space *space,
1039 enum isl_dim_type type, unsigned pos, unsigned n)
1040 {
1041 isl_ctx *ctx;
1042 isl_id **ids = NULL;
1043
1044 if (!space)
1045 return NULL;
1046 if (n == 0)
1047 return isl_space_reset(space, type);
1048
1049 ctx = isl_space_get_ctx(space);
1050 if (!valid_dim_type(type))
1051 isl_die(ctx, isl_error_invalid,
1052 "cannot insert dimensions of specified type",
1053 goto error);
1054
1055 if (isl_space_check_range(space, type, pos, 0) < 0)
1056 return isl_space_free(space);
1057
1058 space = isl_space_cow(space);
1059 if (!space)
1060 return NULL;
1061
1062 if (space->ids) {
1063 enum isl_dim_type t, o = isl_dim_param;
1064 int off;
1065 int s[3];
1066 ids = isl_calloc_array(ctx, isl_id *,
1067 space->nparam + space->n_in + space->n_out + n);
1068 if (!ids)
1069 goto error;
1070 off = 0;
1071 s[isl_dim_param - o] = space->nparam;
1072 s[isl_dim_in - o] = space->n_in;
1073 s[isl_dim_out - o] = space->n_out;
1074 for (t = isl_dim_param; t <= isl_dim_out; ++t) {
1075 if (t != type) {
1076 get_ids(space, t, 0, s[t - o], ids + off);
1077 off += s[t - o];
1078 } else {
1079 get_ids(space, t, 0, pos, ids + off);
1080 off += pos + n;
1081 get_ids(space, t, pos, s[t - o] - pos,
1082 ids + off);
1083 off += s[t - o] - pos;
1084 }
1085 }
1086 free(space->ids);
1087 space->ids = ids;
1088 space->n_id = space->nparam + space->n_in + space->n_out + n;
1089 }
1090 switch (type) {
1091 case isl_dim_param: space->nparam += n; break;
1092 case isl_dim_in: space->n_in += n; break;
1093 case isl_dim_out: space->n_out += n; break;
1094 default: ;
1095 }
1096 space = isl_space_reset(space, type);
1097
1098 if (type == isl_dim_param) {
1099 if (space && space->nested[0] &&
1100 !(space->nested[0] = isl_space_insert_dims(space->nested[0],
1101 isl_dim_param, pos, n)))
1102 goto error;
1103 if (space && space->nested[1] &&
1104 !(space->nested[1] = isl_space_insert_dims(space->nested[1],
1105 isl_dim_param, pos, n)))
1106 goto error;
1107 }
1108
1109 return space;
1110 error:
1111 isl_space_free(space);
1112 return NULL;
1113 }
1114
1115 __isl_give isl_space *isl_space_move_dims(__isl_take isl_space *space,
1116 enum isl_dim_type dst_type, unsigned dst_pos,
1117 enum isl_dim_type src_type, unsigned src_pos, unsigned n)
1118 {
1119 int i;
1120
1121 space = isl_space_reset(space, src_type);
1122 space = isl_space_reset(space, dst_type);
1123 if (!space)
1124 return NULL;
1125 if (n == 0)
1126 return space;
1127
1128 if (isl_space_check_range(space, src_type, src_pos, n) < 0)
1129 return isl_space_free(space);
1130
1131 if (dst_type == src_type && dst_pos == src_pos)
1132 return space;
1133
1134 isl_assert(space->ctx, dst_type != src_type, goto error);
1135
1136 space = isl_space_cow(space);
1137 if (!space)
1138 return NULL;
1139
1140 if (space->ids) {
1141 isl_id **ids;
1142 enum isl_dim_type t, o = isl_dim_param;
1143 int off;
1144 int s[3];
1145 ids = isl_calloc_array(space->ctx, isl_id *,
1146 space->nparam + space->n_in + space->n_out);
1147 if (!ids)
1148 goto error;
1149 off = 0;
1150 s[isl_dim_param - o] = space->nparam;
1151 s[isl_dim_in - o] = space->n_in;
1152 s[isl_dim_out - o] = space->n_out;
1153 for (t = isl_dim_param; t <= isl_dim_out; ++t) {
1154 if (t == dst_type) {
1155 get_ids(space, t, 0, dst_pos, ids + off);
1156 off += dst_pos;
1157 get_ids(space, src_type, src_pos, n, ids + off);
1158 off += n;
1159 get_ids(space, t, dst_pos, s[t - o] - dst_pos,
1160 ids + off);
1161 off += s[t - o] - dst_pos;
1162 } else if (t == src_type) {
1163 get_ids(space, t, 0, src_pos, ids + off);
1164 off += src_pos;
1165 get_ids(space, t, src_pos + n,
1166 s[t - o] - src_pos - n, ids + off);
1167 off += s[t - o] - src_pos - n;
1168 } else {
1169 get_ids(space, t, 0, s[t - o], ids + off);
1170 off += s[t - o];
1171 }
1172 }
1173 free(space->ids);
1174 space->ids = ids;
1175 space->n_id = space->nparam + space->n_in + space->n_out;
1176 }
1177
1178 switch (dst_type) {
1179 case isl_dim_param: space->nparam += n; break;
1180 case isl_dim_in: space->n_in += n; break;
1181 case isl_dim_out: space->n_out += n; break;
1182 default: ;
1183 }
1184
1185 switch (src_type) {
1186 case isl_dim_param: space->nparam -= n; break;
1187 case isl_dim_in: space->n_in -= n; break;
1188 case isl_dim_out: space->n_out -= n; break;
1189 default: ;
1190 }
1191
1192 if (dst_type != isl_dim_param && src_type != isl_dim_param)
1193 return space;
1194
1195 for (i = 0; i < 2; ++i) {
1196 if (!space->nested[i])
1197 continue;
1198 space->nested[i] = isl_space_replace_params(space->nested[i],
1199 space);
1200 if (!space->nested[i])
1201 goto error;
1202 }
1203
1204 return space;
1205 error:
1206 isl_space_free(space);
1207 return NULL;
1208 }
1209
1210 /* Check that "space1" and "space2" have the same parameters,
1211 * reporting an error if they do not.
1212 */
1213 isl_stat isl_space_check_equal_params(__isl_keep isl_space *space1,
1214 __isl_keep isl_space *space2)
1215 {
1216 isl_bool equal;
1217
1218 equal = isl_space_has_equal_params(space1, space2);
1219 if (equal < 0)
1220 return isl_stat_error;
1221 if (!equal)
1222 isl_die(isl_space_get_ctx(space1), isl_error_invalid,
1223 "parameters need to match", return isl_stat_error);
1224 return isl_stat_ok;
1225 }
1226
1227 __isl_give isl_space *isl_space_join(__isl_take isl_space *left,
1228 __isl_take isl_space *right)
1229 {
1230 isl_space *space;
1231
1232 if (isl_space_check_equal_params(left, right) < 0)
1233 goto error;
1234
1235 isl_assert(left->ctx,
1236 isl_space_tuple_is_equal(left, isl_dim_out, right, isl_dim_in),
1237 goto error);
1238
1239 space = isl_space_alloc(left->ctx,
1240 left->nparam, left->n_in, right->n_out);
1241 if (!space)
1242 goto error;
1243
1244 space = copy_ids(space, isl_dim_param, 0, left, isl_dim_param);
1245 space = copy_ids(space, isl_dim_in, 0, left, isl_dim_in);
1246 space = copy_ids(space, isl_dim_out, 0, right, isl_dim_out);
1247
1248 if (space && left->tuple_id[0] &&
1249 !(space->tuple_id[0] = isl_id_copy(left->tuple_id[0])))
1250 goto error;
1251 if (space && right->tuple_id[1] &&
1252 !(space->tuple_id[1] = isl_id_copy(right->tuple_id[1])))
1253 goto error;
1254 if (space && left->nested[0] &&
1255 !(space->nested[0] = isl_space_copy(left->nested[0])))
1256 goto error;
1257 if (space && right->nested[1] &&
1258 !(space->nested[1] = isl_space_copy(right->nested[1])))
1259 goto error;
1260
1261 isl_space_free(left);
1262 isl_space_free(right);
1263
1264 return space;
1265 error:
1266 isl_space_free(left);
1267 isl_space_free(right);
1268 return NULL;
1269 }
1270
1271 /* Given two map spaces { A -> C } and { B -> D }, construct the space
1272 * { [A -> B] -> [C -> D] }.
1273 * Given two set spaces { A } and { B }, construct the space { [A -> B] }.
1274 */
1275 __isl_give isl_space *isl_space_product(__isl_take isl_space *left,
1276 __isl_take isl_space *right)
1277 {
1278 isl_space *dom1, *dom2, *nest1, *nest2;
1279 int is_set;
1280
1281 if (!left || !right)
1282 goto error;
1283
1284 is_set = isl_space_is_set(left);
1285 if (is_set != isl_space_is_set(right))
1286 isl_die(isl_space_get_ctx(left), isl_error_invalid,
1287 "expecting either two set spaces or two map spaces",
1288 goto error);
1289 if (is_set)
1290 return isl_space_range_product(left, right);
1291
1292 if (isl_space_check_equal_params(left, right) < 0)
1293 goto error;
1294
1295 dom1 = isl_space_domain(isl_space_copy(left));
1296 dom2 = isl_space_domain(isl_space_copy(right));
1297 nest1 = isl_space_wrap(isl_space_join(isl_space_reverse(dom1), dom2));
1298
1299 dom1 = isl_space_range(left);
1300 dom2 = isl_space_range(right);
1301 nest2 = isl_space_wrap(isl_space_join(isl_space_reverse(dom1), dom2));
1302
1303 return isl_space_join(isl_space_reverse(nest1), nest2);
1304 error:
1305 isl_space_free(left);
1306 isl_space_free(right);
1307 return NULL;
1308 }
1309
1310 /* Given two spaces { A -> C } and { B -> C }, construct the space
1311 * { [A -> B] -> C }
1312 */
1313 __isl_give isl_space *isl_space_domain_product(__isl_take isl_space *left,
1314 __isl_take isl_space *right)
1315 {
1316 isl_space *ran, *dom1, *dom2, *nest;
1317
1318 if (isl_space_check_equal_params(left, right) < 0)
1319 goto error;
1320
1321 if (!isl_space_tuple_is_equal(left, isl_dim_out, right, isl_dim_out))
1322 isl_die(left->ctx, isl_error_invalid,
1323 "ranges need to match", goto error);
1324
1325 ran = isl_space_range(isl_space_copy(left));
1326
1327 dom1 = isl_space_domain(left);
1328 dom2 = isl_space_domain(right);
1329 nest = isl_space_wrap(isl_space_join(isl_space_reverse(dom1), dom2));
1330
1331 return isl_space_join(isl_space_reverse(nest), ran);
1332 error:
1333 isl_space_free(left);
1334 isl_space_free(right);
1335 return NULL;
1336 }
1337
1338 __isl_give isl_space *isl_space_range_product(__isl_take isl_space *left,
1339 __isl_take isl_space *right)
1340 {
1341 isl_space *dom, *ran1, *ran2, *nest;
1342
1343 if (isl_space_check_equal_params(left, right) < 0)
1344 goto error;
1345
1346 if (!isl_space_tuple_is_equal(left, isl_dim_in, right, isl_dim_in))
1347 isl_die(left->ctx, isl_error_invalid,
1348 "domains need to match", goto error);
1349
1350 dom = isl_space_domain(isl_space_copy(left));
1351
1352 ran1 = isl_space_range(left);
1353 ran2 = isl_space_range(right);
1354 nest = isl_space_wrap(isl_space_join(isl_space_reverse(ran1), ran2));
1355
1356 return isl_space_join(isl_space_reverse(dom), nest);
1357 error:
1358 isl_space_free(left);
1359 isl_space_free(right);
1360 return NULL;
1361 }
1362
1363 /* Given a space of the form [A -> B] -> C, return the space A -> C.
1364 */
1365 __isl_give isl_space *isl_space_domain_factor_domain(
1366 __isl_take isl_space *space)
1367 {
1368 isl_space *nested;
1369 isl_space *domain;
1370
1371 if (!space)
1372 return NULL;
1373 if (!isl_space_domain_is_wrapping(space))
1374 isl_die(isl_space_get_ctx(space), isl_error_invalid,
1375 "domain not a product", return isl_space_free(space));
1376
1377 nested = space->nested[0];
1378 domain = isl_space_copy(space);
1379 domain = isl_space_drop_dims(domain, isl_dim_in,
1380 nested->n_in, nested->n_out);
1381 if (!domain)
1382 return isl_space_free(space);
1383 if (nested->tuple_id[0]) {
1384 domain->tuple_id[0] = isl_id_copy(nested->tuple_id[0]);
1385 if (!domain->tuple_id[0])
1386 goto error;
1387 }
1388 if (nested->nested[0]) {
1389 domain->nested[0] = isl_space_copy(nested->nested[0]);
1390 if (!domain->nested[0])
1391 goto error;
1392 }
1393
1394 isl_space_free(space);
1395 return domain;
1396 error:
1397 isl_space_free(space);
1398 isl_space_free(domain);
1399 return NULL;
1400 }
1401
1402 /* Given a space of the form [A -> B] -> C, return the space B -> C.
1403 */
1404 __isl_give isl_space *isl_space_domain_factor_range(
1405 __isl_take isl_space *space)
1406 {
1407 isl_space *nested;
1408 isl_space *range;
1409
1410 if (!space)
1411 return NULL;
1412 if (!isl_space_domain_is_wrapping(space))
1413 isl_die(isl_space_get_ctx(space), isl_error_invalid,
1414 "domain not a product", return isl_space_free(space));
1415
1416 nested = space->nested[0];
1417 range = isl_space_copy(space);
1418 range = isl_space_drop_dims(range, isl_dim_in, 0, nested->n_in);
1419 if (!range)
1420 return isl_space_free(space);
1421 if (nested->tuple_id[1]) {
1422 range->tuple_id[0] = isl_id_copy(nested->tuple_id[1]);
1423 if (!range->tuple_id[0])
1424 goto error;
1425 }
1426 if (nested->nested[1]) {
1427 range->nested[0] = isl_space_copy(nested->nested[1]);
1428 if (!range->nested[0])
1429 goto error;
1430 }
1431
1432 isl_space_free(space);
1433 return range;
1434 error:
1435 isl_space_free(space);
1436 isl_space_free(range);
1437 return NULL;
1438 }
1439
1440 /* Internal function that selects the domain of the map that is
1441 * embedded in either a set space or the range of a map space.
1442 * In particular, given a space of the form [A -> B], return the space A.
1443 * Given a space of the form A -> [B -> C], return the space A -> B.
1444 */
1445 static __isl_give isl_space *range_factor_domain(__isl_take isl_space *space)
1446 {
1447 isl_space *nested;
1448 isl_space *domain;
1449
1450 if (!space)
1451 return NULL;
1452
1453 nested = space->nested[1];
1454 domain = isl_space_copy(space);
1455 domain = isl_space_drop_dims(domain, isl_dim_out,
1456 nested->n_in, nested->n_out);
1457 if (!domain)
1458 return isl_space_free(space);
1459 if (nested->tuple_id[0]) {
1460 domain->tuple_id[1] = isl_id_copy(nested->tuple_id[0]);
1461 if (!domain->tuple_id[1])
1462 goto error;
1463 }
1464 if (nested->nested[0]) {
1465 domain->nested[1] = isl_space_copy(nested->nested[0]);
1466 if (!domain->nested[1])
1467 goto error;
1468 }
1469
1470 isl_space_free(space);
1471 return domain;
1472 error:
1473 isl_space_free(space);
1474 isl_space_free(domain);
1475 return NULL;
1476 }
1477
1478 /* Given a space of the form A -> [B -> C], return the space A -> B.
1479 */
1480 __isl_give isl_space *isl_space_range_factor_domain(
1481 __isl_take isl_space *space)
1482 {
1483 if (!space)
1484 return NULL;
1485 if (!isl_space_range_is_wrapping(space))
1486 isl_die(isl_space_get_ctx(space), isl_error_invalid,
1487 "range not a product", return isl_space_free(space));
1488
1489 return range_factor_domain(space);
1490 }
1491
1492 /* Given a space of the form [A -> B], return the space A.
1493 */
1494 static __isl_give isl_space *set_factor_domain(__isl_take isl_space *space)
1495 {
1496 if (!space)
1497 return NULL;
1498 if (!isl_space_is_wrapping(space))
1499 isl_die(isl_space_get_ctx(space), isl_error_invalid,
1500 "not a product", return isl_space_free(space));
1501
1502 return range_factor_domain(space);
1503 }
1504
1505 /* Given a space of the form [A -> B] -> [C -> D], return the space A -> C.
1506 * Given a space of the form [A -> B], return the space A.
1507 */
1508 __isl_give isl_space *isl_space_factor_domain(__isl_take isl_space *space)
1509 {
1510 if (!space)
1511 return NULL;
1512 if (isl_space_is_set(space))
1513 return set_factor_domain(space);
1514 space = isl_space_domain_factor_domain(space);
1515 space = isl_space_range_factor_domain(space);
1516 return space;
1517 }
1518
1519 /* Internal function that selects the range of the map that is
1520 * embedded in either a set space or the range of a map space.
1521 * In particular, given a space of the form [A -> B], return the space B.
1522 * Given a space of the form A -> [B -> C], return the space A -> C.
1523 */
1524 static __isl_give isl_space *range_factor_range(__isl_take isl_space *space)
1525 {
1526 isl_space *nested;
1527 isl_space *range;
1528
1529 if (!space)
1530 return NULL;
1531
1532 nested = space->nested[1];
1533 range = isl_space_copy(space);
1534 range = isl_space_drop_dims(range, isl_dim_out, 0, nested->n_in);
1535 if (!range)
1536 return isl_space_free(space);
1537 if (nested->tuple_id[1]) {
1538 range->tuple_id[1] = isl_id_copy(nested->tuple_id[1]);
1539 if (!range->tuple_id[1])
1540 goto error;
1541 }
1542 if (nested->nested[1]) {
1543 range->nested[1] = isl_space_copy(nested->nested[1]);
1544 if (!range->nested[1])
1545 goto error;
1546 }
1547
1548 isl_space_free(space);
1549 return range;
1550 error:
1551 isl_space_free(space);
1552 isl_space_free(range);
1553 return NULL;
1554 }
1555
1556 /* Given a space of the form A -> [B -> C], return the space A -> C.
1557 */
1558 __isl_give isl_space *isl_space_range_factor_range(
1559 __isl_take isl_space *space)
1560 {
1561 if (!space)
1562 return NULL;
1563 if (!isl_space_range_is_wrapping(space))
1564 isl_die(isl_space_get_ctx(space), isl_error_invalid,
1565 "range not a product", return isl_space_free(space));
1566
1567 return range_factor_range(space);
1568 }
1569
1570 /* Given a space of the form [A -> B], return the space B.
1571 */
1572 static __isl_give isl_space *set_factor_range(__isl_take isl_space *space)
1573 {
1574 if (!space)
1575 return NULL;
1576 if (!isl_space_is_wrapping(space))
1577 isl_die(isl_space_get_ctx(space), isl_error_invalid,
1578 "not a product", return isl_space_free(space));
1579
1580 return range_factor_range(space);
1581 }
1582
1583 /* Given a space of the form [A -> B] -> [C -> D], return the space B -> D.
1584 * Given a space of the form [A -> B], return the space B.
1585 */
1586 __isl_give isl_space *isl_space_factor_range(__isl_take isl_space *space)
1587 {
1588 if (!space)
1589 return NULL;
1590 if (isl_space_is_set(space))
1591 return set_factor_range(space);
1592 space = isl_space_domain_factor_range(space);
1593 space = isl_space_range_factor_range(space);
1594 return space;
1595 }
1596
1597 __isl_give isl_space *isl_space_map_from_set(__isl_take isl_space *space)
1598 {
1599 isl_ctx *ctx;
1600 isl_id **ids = NULL;
1601 int n_id;
1602
1603 if (!space)
1604 return NULL;
1605 ctx = isl_space_get_ctx(space);
1606 if (!isl_space_is_set(space))
1607 isl_die(ctx, isl_error_invalid, "not a set space", goto error);
1608 space = isl_space_cow(space);
1609 if (!space)
1610 return NULL;
1611 n_id = space->nparam + space->n_out + space->n_out;
1612 if (n_id > 0 && space->ids) {
1613 ids = isl_calloc_array(space->ctx, isl_id *, n_id);
1614 if (!ids)
1615 goto error;
1616 get_ids(space, isl_dim_param, 0, space->nparam, ids);
1617 get_ids(space, isl_dim_out, 0, space->n_out,
1618 ids + space->nparam);
1619 }
1620 space->n_in = space->n_out;
1621 if (ids) {
1622 free(space->ids);
1623 space->ids = ids;
1624 space->n_id = n_id;
1625 space = copy_ids(space, isl_dim_out, 0, space, isl_dim_in);
1626 }
1627 isl_id_free(space->tuple_id[0]);
1628 space->tuple_id[0] = isl_id_copy(space->tuple_id[1]);
1629 isl_space_free(space->nested[0]);
1630 space->nested[0] = isl_space_copy(space->nested[1]);
1631 return space;
1632 error:
1633 isl_space_free(space);
1634 return NULL;
1635 }
1636
1637 __isl_give isl_space *isl_space_map_from_domain_and_range(
1638 __isl_take isl_space *domain, __isl_take isl_space *range)
1639 {
1640 if (!domain || !range)
1641 goto error;
1642 if (!isl_space_is_set(domain))
1643 isl_die(isl_space_get_ctx(domain), isl_error_invalid,
1644 "domain is not a set space", goto error);
1645 if (!isl_space_is_set(range))
1646 isl_die(isl_space_get_ctx(range), isl_error_invalid,
1647 "range is not a set space", goto error);
1648 return isl_space_join(isl_space_reverse(domain), range);
1649 error:
1650 isl_space_free(domain);
1651 isl_space_free(range);
1652 return NULL;
1653 }
1654
1655 static __isl_give isl_space *set_ids(__isl_take isl_space *dim,
1656 enum isl_dim_type type,
1657 unsigned first, unsigned n, __isl_take isl_id **ids)
1658 {
1659 int i;
1660
1661 for (i = 0; i < n ; ++i)
1662 dim = set_id(dim, type, first + i, ids[i]);
1663
1664 return dim;
1665 }
1666
1667 __isl_give isl_space *isl_space_reverse(__isl_take isl_space *space)
1668 {
1669 unsigned t;
1670 isl_space *nested;
1671 isl_id **ids = NULL;
1672 isl_id *id;
1673
1674 if (!space)
1675 return NULL;
1676 if (match(space, isl_dim_in, space, isl_dim_out))
1677 return space;
1678
1679 space = isl_space_cow(space);
1680 if (!space)
1681 return NULL;
1682
1683 id = space->tuple_id[0];
1684 space->tuple_id[0] = space->tuple_id[1];
1685 space->tuple_id[1] = id;
1686
1687 nested = space->nested[0];
1688 space->nested[0] = space->nested[1];
1689 space->nested[1] = nested;
1690
1691 if (space->ids) {
1692 int n_id = space->n_in + space->n_out;
1693 ids = isl_alloc_array(space->ctx, isl_id *, n_id);
1694 if (n_id && !ids)
1695 goto error;
1696 get_ids(space, isl_dim_in, 0, space->n_in, ids);
1697 get_ids(space, isl_dim_out, 0, space->n_out, ids + space->n_in);
1698 }
1699
1700 t = space->n_in;
1701 space->n_in = space->n_out;
1702 space->n_out = t;
1703
1704 if (space->ids) {
1705 space = set_ids(space, isl_dim_out, 0, space->n_out, ids);
1706 space = set_ids(space, isl_dim_in, 0, space->n_in,
1707 ids + space->n_out);
1708 free(ids);
1709 }
1710
1711 return space;
1712 error:
1713 free(ids);
1714 isl_space_free(space);
1715 return NULL;
1716 }
1717
1718 __isl_give isl_space *isl_space_drop_dims(__isl_take isl_space *space,
1719 enum isl_dim_type type, unsigned first, unsigned num)
1720 {
1721 int i;
1722
1723 if (!space)
1724 return NULL;
1725
1726 if (num == 0)
1727 return isl_space_reset(space, type);
1728
1729 if (!valid_dim_type(type))
1730 isl_die(space->ctx, isl_error_invalid,
1731 "cannot drop dimensions of specified type", goto error);
1732
1733 if (isl_space_check_range(space, type, first, num) < 0)
1734 return isl_space_free(space);
1735 space = isl_space_cow(space);
1736 if (!space)
1737 goto error;
1738 if (space->ids) {
1739 space = extend_ids(space);
1740 if (!space)
1741 goto error;
1742 for (i = 0; i < num; ++i)
1743 isl_id_free(get_id(space, type, first + i));
1744 for (i = first+num; i < n(space, type); ++i)
1745 set_id(space, type, i - num, get_id(space, type, i));
1746 switch (type) {
1747 case isl_dim_param:
1748 get_ids(space, isl_dim_in, 0, space->n_in,
1749 space->ids + offset(space, isl_dim_in) - num);
1750 case isl_dim_in:
1751 get_ids(space, isl_dim_out, 0, space->n_out,
1752 space->ids + offset(space, isl_dim_out) - num);
1753 default:
1754 ;
1755 }
1756 space->n_id -= num;
1757 }
1758 switch (type) {
1759 case isl_dim_param: space->nparam -= num; break;
1760 case isl_dim_in: space->n_in -= num; break;
1761 case isl_dim_out: space->n_out -= num; break;
1762 default: ;
1763 }
1764 space = isl_space_reset(space, type);
1765 if (type == isl_dim_param) {
1766 if (space && space->nested[0] &&
1767 !(space->nested[0] = isl_space_drop_dims(space->nested[0],
1768 isl_dim_param, first, num)))
1769 goto error;
1770 if (space && space->nested[1] &&
1771 !(space->nested[1] = isl_space_drop_dims(space->nested[1],
1772 isl_dim_param, first, num)))
1773 goto error;
1774 }
1775 return space;
1776 error:
1777 isl_space_free(space);
1778 return NULL;
1779 }
1780
1781 __isl_give isl_space *isl_space_drop_inputs(__isl_take isl_space *dim,
1782 unsigned first, unsigned n)
1783 {
1784 if (!dim)
1785 return NULL;
1786 return isl_space_drop_dims(dim, isl_dim_in, first, n);
1787 }
1788
1789 __isl_give isl_space *isl_space_drop_outputs(__isl_take isl_space *dim,
1790 unsigned first, unsigned n)
1791 {
1792 if (!dim)
1793 return NULL;
1794 return isl_space_drop_dims(dim, isl_dim_out, first, n);
1795 }
1796
1797 /* Remove all parameters from "space".
1798 */
1799 __isl_give isl_space *isl_space_drop_all_params(__isl_take isl_space *space)
1800 {
1801 unsigned nparam;
1802
1803 nparam = isl_space_dim(space, isl_dim_param);
1804 return isl_space_drop_dims(space, isl_dim_param, 0, nparam);
1805 }
1806
1807 __isl_give isl_space *isl_space_domain(__isl_take isl_space *space)
1808 {
1809 if (!space)
1810 return NULL;
1811 space = isl_space_drop_dims(space, isl_dim_out, 0, space->n_out);
1812 space = isl_space_reverse(space);
1813 space = mark_as_set(space);
1814 return space;
1815 }
1816
1817 __isl_give isl_space *isl_space_from_domain(__isl_take isl_space *space)
1818 {
1819 if (!space)
1820 return NULL;
1821 if (!isl_space_is_set(space))
1822 isl_die(isl_space_get_ctx(space), isl_error_invalid,
1823 "not a set space", goto error);
1824 space = isl_space_reverse(space);
1825 space = isl_space_reset(space, isl_dim_out);
1826 return space;
1827 error:
1828 isl_space_free(space);
1829 return NULL;
1830 }
1831
1832 __isl_give isl_space *isl_space_range(__isl_take isl_space *space)
1833 {
1834 if (!space)
1835 return NULL;
1836 space = isl_space_drop_dims(space, isl_dim_in, 0, space->n_in);
1837 space = mark_as_set(space);
1838 return space;
1839 }
1840
1841 __isl_give isl_space *isl_space_from_range(__isl_take isl_space *space)
1842 {
1843 if (!space)
1844 return NULL;
1845 if (!isl_space_is_set(space))
1846 isl_die(isl_space_get_ctx(space), isl_error_invalid,
1847 "not a set space", goto error);
1848 return isl_space_reset(space, isl_dim_in);
1849 error:
1850 isl_space_free(space);
1851 return NULL;
1852 }
1853
1854 /* Given a map space A -> B, return the map space [A -> B] -> A.
1855 */
1856 __isl_give isl_space *isl_space_domain_map(__isl_take isl_space *space)
1857 {
1858 isl_space *domain;
1859
1860 domain = isl_space_from_range(isl_space_domain(isl_space_copy(space)));
1861 space = isl_space_from_domain(isl_space_wrap(space));
1862 space = isl_space_join(space, domain);
1863
1864 return space;
1865 }
1866
1867 /* Given a map space A -> B, return the map space [A -> B] -> B.
1868 */
1869 __isl_give isl_space *isl_space_range_map(__isl_take isl_space *space)
1870 {
1871 isl_space *range;
1872
1873 range = isl_space_from_range(isl_space_range(isl_space_copy(space)));
1874 space = isl_space_from_domain(isl_space_wrap(space));
1875 space = isl_space_join(space, range);
1876
1877 return space;
1878 }
1879
1880 __isl_give isl_space *isl_space_params(__isl_take isl_space *space)
1881 {
1882 if (isl_space_is_params(space))
1883 return space;
1884 space = isl_space_drop_dims(space,
1885 isl_dim_in, 0, isl_space_dim(space, isl_dim_in));
1886 space = isl_space_drop_dims(space,
1887 isl_dim_out, 0, isl_space_dim(space, isl_dim_out));
1888 space = mark_as_params(space);
1889 return space;
1890 }
1891
1892 __isl_give isl_space *isl_space_set_from_params(__isl_take isl_space *space)
1893 {
1894 if (!space)
1895 return NULL;
1896 if (!isl_space_is_params(space))
1897 isl_die(isl_space_get_ctx(space), isl_error_invalid,
1898 "not a parameter space", goto error);
1899 return isl_space_reset(space, isl_dim_set);
1900 error:
1901 isl_space_free(space);
1902 return NULL;
1903 }
1904
1905 __isl_give isl_space *isl_space_underlying(__isl_take isl_space *space,
1906 unsigned n_div)
1907 {
1908 int i;
1909 isl_bool is_set;
1910
1911 is_set = isl_space_is_set(space);
1912 if (is_set < 0)
1913 return isl_space_free(space);
1914 if (n_div == 0 && is_set &&
1915 space->nparam == 0 && space->n_in == 0 && space->n_id == 0)
1916 return isl_space_reset(space, isl_dim_out);
1917 space = isl_space_cow(space);
1918 if (!space)
1919 return NULL;
1920 space->n_out += space->nparam + space->n_in + n_div;
1921 space->nparam = 0;
1922 space->n_in = 0;
1923
1924 for (i = 0; i < space->n_id; ++i)
1925 isl_id_free(get_id(space, isl_dim_out, i));
1926 space->n_id = 0;
1927 space = isl_space_reset(space, isl_dim_in);
1928 space = isl_space_reset(space, isl_dim_out);
1929 space = mark_as_set(space);
1930
1931 return space;
1932 }
1933
1934 /* Are the two spaces the same, including positions and names of parameters?
1935 */
1936 isl_bool isl_space_is_equal(__isl_keep isl_space *space1,
1937 __isl_keep isl_space *space2)
1938 {
1939 isl_bool equal;
1940
1941 if (!space1 || !space2)
1942 return isl_bool_error;
1943 if (space1 == space2)
1944 return isl_bool_true;
1945 equal = isl_space_has_equal_params(space1, space2);
1946 if (equal < 0 || !equal)
1947 return equal;
1948 return isl_space_has_equal_tuples(space1, space2);
1949 }
1950
1951 /* Do the tuples of "space1" correspond to those of the domain of "space2"?
1952 * That is, is "space1" eqaul to the domain of "space2", ignoring parameters.
1953 *
1954 * "space2" is allowed to be a set space, in which case "space1"
1955 * should be a parameter space.
1956 */
1957 isl_bool isl_space_has_domain_tuples(__isl_keep isl_space *space1,
1958 __isl_keep isl_space *space2)
1959 {
1960 isl_bool is_set;
1961
1962 is_set = isl_space_is_set(space1);
1963 if (is_set < 0 || !is_set)
1964 return is_set;
1965 return isl_space_tuple_is_equal(space1, isl_dim_set,
1966 space2, isl_dim_in);
1967 }
1968
1969 /* Is space1 equal to the domain of space2?
1970 *
1971 * In the internal version we also allow space2 to be the space of a set,
1972 * provided space1 is a parameter space.
1973 */
1974 isl_bool isl_space_is_domain_internal(__isl_keep isl_space *space1,
1975 __isl_keep isl_space *space2)
1976 {
1977 isl_bool equal_params;
1978
1979 if (!space1 || !space2)
1980 return isl_bool_error;
1981 equal_params = isl_space_has_equal_params(space1, space2);
1982 if (equal_params < 0 || !equal_params)
1983 return equal_params;
1984 return isl_space_has_domain_tuples(space1, space2);
1985 }
1986
1987 /* Is space1 equal to the domain of space2?
1988 */
1989 isl_bool isl_space_is_domain(__isl_keep isl_space *space1,
1990 __isl_keep isl_space *space2)
1991 {
1992 if (!space2)
1993 return isl_bool_error;
1994 if (!isl_space_is_map(space2))
1995 return isl_bool_false;
1996 return isl_space_is_domain_internal(space1, space2);
1997 }
1998
1999 /* Is space1 equal to the range of space2?
2000 *
2001 * In the internal version, space2 is allowed to be the space of a set,
2002 * in which case it should be equal to space1.
2003 */
2004 isl_bool isl_space_is_range_internal(__isl_keep isl_space *space1,
2005 __isl_keep isl_space *space2)
2006 {
2007 isl_bool equal_params;
2008
2009 if (!space1 || !space2)
2010 return isl_bool_error;
2011 if (!isl_space_is_set(space1))
2012 return isl_bool_false;
2013 equal_params = isl_space_has_equal_params(space1, space2);
2014 if (equal_params < 0 || !equal_params)
2015 return equal_params;
2016 return isl_space_tuple_is_equal(space1, isl_dim_set,
2017 space2, isl_dim_out);
2018 }
2019
2020 /* Is space1 equal to the range of space2?
2021 */
2022 isl_bool isl_space_is_range(__isl_keep isl_space *space1,
2023 __isl_keep isl_space *space2)
2024 {
2025 if (!space2)
2026 return isl_bool_error;
2027 if (!isl_space_is_map(space2))
2028 return isl_bool_false;
2029 return isl_space_is_range_internal(space1, space2);
2030 }
2031
2032 /* Update "hash" by hashing in the parameters of "space".
2033 */
2034 static uint32_t isl_hash_params(uint32_t hash, __isl_keep isl_space *space)
2035 {
2036 int i;
2037 isl_id *id;
2038
2039 if (!space)
2040 return hash;
2041
2042 isl_hash_byte(hash, space->nparam % 256);
2043
2044 for (i = 0; i < space->nparam; ++i) {
2045 id = get_id(space, isl_dim_param, i);
2046 hash = isl_hash_id(hash, id);
2047 }
2048
2049 return hash;
2050 }
2051
2052 /* Update "hash" by hashing in the tuples of "space".
2053 * Changes in this function should be reflected in isl_hash_tuples_domain.
2054 */
2055 static uint32_t isl_hash_tuples(uint32_t hash, __isl_keep isl_space *space)
2056 {
2057 isl_id *id;
2058
2059 if (!space)
2060 return hash;
2061
2062 isl_hash_byte(hash, space->n_in % 256);
2063 isl_hash_byte(hash, space->n_out % 256);
2064
2065 id = tuple_id(space, isl_dim_in);
2066 hash = isl_hash_id(hash, id);
2067 id = tuple_id(space, isl_dim_out);
2068 hash = isl_hash_id(hash, id);
2069
2070 hash = isl_hash_tuples(hash, space->nested[0]);
2071 hash = isl_hash_tuples(hash, space->nested[1]);
2072
2073 return hash;
2074 }
2075
2076 /* Update "hash" by hashing in the domain tuple of "space".
2077 * The result of this function is equal to the result of applying
2078 * isl_hash_tuples to the domain of "space".
2079 */
2080 static uint32_t isl_hash_tuples_domain(uint32_t hash,
2081 __isl_keep isl_space *space)
2082 {
2083 isl_id *id;
2084
2085 if (!space)
2086 return hash;
2087
2088 isl_hash_byte(hash, 0);
2089 isl_hash_byte(hash, space->n_in % 256);
2090
2091 hash = isl_hash_id(hash, &isl_id_none);
2092 id = tuple_id(space, isl_dim_in);
2093 hash = isl_hash_id(hash, id);
2094
2095 hash = isl_hash_tuples(hash, space->nested[0]);
2096
2097 return hash;
2098 }
2099
2100 /* Return a hash value that digests the tuples of "space",
2101 * i.e., that ignores the parameters.
2102 */
2103 uint32_t isl_space_get_tuple_hash(__isl_keep isl_space *space)
2104 {
2105 uint32_t hash;
2106
2107 if (!space)
2108 return 0;
2109
2110 hash = isl_hash_init();
2111 hash = isl_hash_tuples(hash, space);
2112
2113 return hash;
2114 }
2115
2116 uint32_t isl_space_get_hash(__isl_keep isl_space *space)
2117 {
2118 uint32_t hash;
2119
2120 if (!space)
2121 return 0;
2122
2123 hash = isl_hash_init();
2124 hash = isl_hash_params(hash, space);
2125 hash = isl_hash_tuples(hash, space);
2126
2127 return hash;
2128 }
2129
2130 /* Return the hash value of the domain of "space".
2131 * That is, isl_space_get_domain_hash(space) is equal to
2132 * isl_space_get_hash(isl_space_domain(space)).
2133 */
2134 uint32_t isl_space_get_domain_hash(__isl_keep isl_space *space)
2135 {
2136 uint32_t hash;
2137
2138 if (!space)
2139 return 0;
2140
2141 hash = isl_hash_init();
2142 hash = isl_hash_params(hash, space);
2143 hash = isl_hash_tuples_domain(hash, space);
2144
2145 return hash;
2146 }
2147
2148 /* Is "space" the space of a set wrapping a map space?
2149 */
2150 isl_bool isl_space_is_wrapping(__isl_keep isl_space *space)
2151 {
2152 if (!space)
2153 return isl_bool_error;
2154
2155 if (!isl_space_is_set(space))
2156 return isl_bool_false;
2157
2158 return space->nested[1] != NULL;
2159 }
2160
2161 /* Is "space" the space of a map where the domain is a wrapped map space?
2162 */
2163 isl_bool isl_space_domain_is_wrapping(__isl_keep isl_space *space)
2164 {
2165 if (!space)
2166 return isl_bool_error;
2167
2168 if (isl_space_is_set(space))
2169 return isl_bool_false;
2170
2171 return space->nested[0] != NULL;
2172 }
2173
2174 /* Is "space" the space of a map where the range is a wrapped map space?
2175 */
2176 isl_bool isl_space_range_is_wrapping(__isl_keep isl_space *space)
2177 {
2178 if (!space)
2179 return isl_bool_error;
2180
2181 if (isl_space_is_set(space))
2182 return isl_bool_false;
2183
2184 return space->nested[1] != NULL;
2185 }
2186
2187 /* Is "space" a product of two spaces?
2188 * That is, is it a wrapping set space or a map space
2189 * with wrapping domain and range?
2190 */
2191 isl_bool isl_space_is_product(__isl_keep isl_space *space)
2192 {
2193 isl_bool is_set;
2194 isl_bool is_product;
2195
2196 is_set = isl_space_is_set(space);
2197 if (is_set < 0)
2198 return isl_bool_error;
2199 if (is_set)
2200 return isl_space_is_wrapping(space);
2201 is_product = isl_space_domain_is_wrapping(space);
2202 if (is_product < 0 || !is_product)
2203 return is_product;
2204 return isl_space_range_is_wrapping(space);
2205 }
2206
2207 __isl_give isl_space *isl_space_wrap(__isl_take isl_space *space)
2208 {
2209 isl_space *wrap;
2210
2211 if (!space)
2212 return NULL;
2213
2214 wrap = isl_space_set_alloc(space->ctx,
2215 space->nparam, space->n_in + space->n_out);
2216
2217 wrap = copy_ids(wrap, isl_dim_param, 0, space, isl_dim_param);
2218 wrap = copy_ids(wrap, isl_dim_set, 0, space, isl_dim_in);
2219 wrap = copy_ids(wrap, isl_dim_set, space->n_in, space, isl_dim_out);
2220
2221 if (!wrap)
2222 goto error;
2223
2224 wrap->nested[1] = space;
2225
2226 return wrap;
2227 error:
2228 isl_space_free(space);
2229 return NULL;
2230 }
2231
2232 __isl_give isl_space *isl_space_unwrap(__isl_take isl_space *space)
2233 {
2234 isl_space *unwrap;
2235
2236 if (!space)
2237 return NULL;
2238
2239 if (!isl_space_is_wrapping(space))
2240 isl_die(space->ctx, isl_error_invalid, "not a wrapping space",
2241 goto error);
2242
2243 unwrap = isl_space_copy(space->nested[1]);
2244 isl_space_free(space);
2245
2246 return unwrap;
2247 error:
2248 isl_space_free(space);
2249 return NULL;
2250 }
2251
2252 isl_bool isl_space_is_named_or_nested(__isl_keep isl_space *space,
2253 enum isl_dim_type type)
2254 {
2255 if (type != isl_dim_in && type != isl_dim_out)
2256 return isl_bool_false;
2257 if (!space)
2258 return isl_bool_error;
2259 if (space->tuple_id[type - isl_dim_in])
2260 return isl_bool_true;
2261 if (space->nested[type - isl_dim_in])
2262 return isl_bool_true;
2263 return isl_bool_false;
2264 }
2265
2266 isl_bool isl_space_may_be_set(__isl_keep isl_space *space)
2267 {
2268 isl_bool nested;
2269
2270 if (!space)
2271 return isl_bool_error;
2272 if (isl_space_is_set(space))
2273 return isl_bool_true;
2274 if (isl_space_dim(space, isl_dim_in) != 0)
2275 return isl_bool_false;
2276 nested = isl_space_is_named_or_nested(space, isl_dim_in);
2277 if (nested < 0 || nested)
2278 return isl_bool_not(nested);
2279 return isl_bool_true;
2280 }
2281
2282 __isl_give isl_space *isl_space_reset(__isl_take isl_space *space,
2283 enum isl_dim_type type)
2284 {
2285 if (!isl_space_is_named_or_nested(space, type))
2286 return space;
2287
2288 space = isl_space_cow(space);
2289 if (!space)
2290 return NULL;
2291
2292 isl_id_free(space->tuple_id[type - isl_dim_in]);
2293 space->tuple_id[type - isl_dim_in] = NULL;
2294 isl_space_free(space->nested[type - isl_dim_in]);
2295 space->nested[type - isl_dim_in] = NULL;
2296
2297 return space;
2298 }
2299
2300 __isl_give isl_space *isl_space_flatten(__isl_take isl_space *space)
2301 {
2302 if (!space)
2303 return NULL;
2304 if (!space->nested[0] && !space->nested[1])
2305 return space;
2306
2307 if (space->nested[0])
2308 space = isl_space_reset(space, isl_dim_in);
2309 if (space && space->nested[1])
2310 space = isl_space_reset(space, isl_dim_out);
2311
2312 return space;
2313 }
2314
2315 __isl_give isl_space *isl_space_flatten_domain(__isl_take isl_space *space)
2316 {
2317 if (!space)
2318 return NULL;
2319 if (!space->nested[0])
2320 return space;
2321
2322 return isl_space_reset(space, isl_dim_in);
2323 }
2324
2325 __isl_give isl_space *isl_space_flatten_range(__isl_take isl_space *space)
2326 {
2327 if (!space)
2328 return NULL;
2329 if (!space->nested[1])
2330 return space;
2331
2332 return isl_space_reset(space, isl_dim_out);
2333 }
2334
2335 /* Replace the parameters of dst by those of src.
2336 */
2337 __isl_give isl_space *isl_space_replace_params(__isl_take isl_space *dst,
2338 __isl_keep isl_space *src)
2339 {
2340 isl_bool equal_params;
2341 enum isl_dim_type type = isl_dim_param;
2342
2343 equal_params = isl_space_has_equal_params(dst, src);
2344 if (equal_params < 0)
2345 return isl_space_free(dst);
2346 if (equal_params)
2347 return dst;
2348
2349 dst = isl_space_cow(dst);
2350
2351 if (!dst || !src)
2352 goto error;
2353
2354 dst = isl_space_drop_dims(dst, type, 0, isl_space_dim(dst, type));
2355 dst = isl_space_add_dims(dst, type, isl_space_dim(src, type));
2356 dst = copy_ids(dst, type, 0, src, type);
2357
2358 if (dst) {
2359 int i;
2360 for (i = 0; i <= 1; ++i) {
2361 if (!dst->nested[i])
2362 continue;
2363 dst->nested[i] = isl_space_replace_params(
2364 dst->nested[i], src);
2365 if (!dst->nested[i])
2366 goto error;
2367 }
2368 }
2369
2370 return dst;
2371 error:
2372 isl_space_free(dst);
2373 return NULL;
2374 }
2375
2376 /* Given a dimension specification "dim" of a set, create a dimension
2377 * specification for the lift of the set. In particular, the result
2378 * is of the form [dim -> local[..]], with n_local variables in the
2379 * range of the wrapped map.
2380 */
2381 __isl_give isl_space *isl_space_lift(__isl_take isl_space *space,
2382 unsigned n_local)
2383 {
2384 isl_space *local_space;
2385
2386 if (!space)
2387 return NULL;
2388
2389 local_space = isl_space_dup(space);
2390 local_space = isl_space_drop_dims(local_space, isl_dim_set, 0,
2391 space->n_out);
2392 local_space = isl_space_add_dims(local_space, isl_dim_set, n_local);
2393 local_space = isl_space_set_tuple_name(local_space,
2394 isl_dim_set, "local");
2395 space = isl_space_join(isl_space_from_domain(space),
2396 isl_space_from_range(local_space));
2397 space = isl_space_wrap(space);
2398 space = isl_space_set_tuple_name(space, isl_dim_set, "lifted");
2399
2400 return space;
2401 }
2402
2403 isl_bool isl_space_can_zip(__isl_keep isl_space *space)
2404 {
2405 isl_bool is_set;
2406
2407 is_set = isl_space_is_set(space);
2408 if (is_set < 0)
2409 return isl_bool_error;
2410 if (is_set)
2411 return isl_bool_false;
2412 return isl_space_is_product(space);
2413 }
2414
2415 __isl_give isl_space *isl_space_zip(__isl_take isl_space *space)
2416 {
2417 isl_space *dom, *ran;
2418 isl_space *dom_dom, *dom_ran, *ran_dom, *ran_ran;
2419
2420 if (!isl_space_can_zip(space))
2421 isl_die(space->ctx, isl_error_invalid, "dim cannot be zipped",
2422 goto error);
2423
2424 if (!space)
2425 return NULL;
2426 dom = isl_space_unwrap(isl_space_domain(isl_space_copy(space)));
2427 ran = isl_space_unwrap(isl_space_range(space));
2428 dom_dom = isl_space_domain(isl_space_copy(dom));
2429 dom_ran = isl_space_range(dom);
2430 ran_dom = isl_space_domain(isl_space_copy(ran));
2431 ran_ran = isl_space_range(ran);
2432 dom = isl_space_join(isl_space_from_domain(dom_dom),
2433 isl_space_from_range(ran_dom));
2434 ran = isl_space_join(isl_space_from_domain(dom_ran),
2435 isl_space_from_range(ran_ran));
2436 return isl_space_join(isl_space_from_domain(isl_space_wrap(dom)),
2437 isl_space_from_range(isl_space_wrap(ran)));
2438 error:
2439 isl_space_free(space);
2440 return NULL;
2441 }
2442
2443 /* Can we apply isl_space_curry to "space"?
2444 * That is, does is it have a map space with a nested relation in its domain?
2445 */
2446 isl_bool isl_space_can_curry(__isl_keep isl_space *space)
2447 {
2448 return isl_space_domain_is_wrapping(space);
2449 }
2450
2451 /* Given a space (A -> B) -> C, return the corresponding space
2452 * A -> (B -> C).
2453 */
2454 __isl_give isl_space *isl_space_curry(__isl_take isl_space *space)
2455 {
2456 isl_space *dom, *ran;
2457 isl_space *dom_dom, *dom_ran;
2458
2459 if (!space)
2460 return NULL;
2461
2462 if (!isl_space_can_curry(space))
2463 isl_die(space->ctx, isl_error_invalid,
2464 "space cannot be curried", goto error);
2465
2466 dom = isl_space_unwrap(isl_space_domain(isl_space_copy(space)));
2467 ran = isl_space_range(space);
2468 dom_dom = isl_space_domain(isl_space_copy(dom));
2469 dom_ran = isl_space_range(dom);
2470 ran = isl_space_join(isl_space_from_domain(dom_ran),
2471 isl_space_from_range(ran));
2472 return isl_space_join(isl_space_from_domain(dom_dom),
2473 isl_space_from_range(isl_space_wrap(ran)));
2474 error:
2475 isl_space_free(space);
2476 return NULL;
2477 }
2478
2479 /* Can isl_space_range_curry be applied to "space"?
2480 * That is, does it have a nested relation in its range,
2481 * the domain of which is itself a nested relation?
2482 */
2483 isl_bool isl_space_can_range_curry(__isl_keep isl_space *space)
2484 {
2485 isl_bool can;
2486
2487 if (!space)
2488 return isl_bool_error;
2489 can = isl_space_range_is_wrapping(space);
2490 if (can < 0 || !can)
2491 return can;
2492 return isl_space_can_curry(space->nested[1]);
2493 }
2494
2495 /* Given a space A -> ((B -> C) -> D), return the corresponding space
2496 * A -> (B -> (C -> D)).
2497 */
2498 __isl_give isl_space *isl_space_range_curry(__isl_take isl_space *space)
2499 {
2500 if (!space)
2501 return NULL;
2502
2503 if (!isl_space_can_range_curry(space))
2504 isl_die(isl_space_get_ctx(space), isl_error_invalid,
2505 "space range cannot be curried",
2506 return isl_space_free(space));
2507
2508 space = isl_space_cow(space);
2509 if (!space)
2510 return NULL;
2511 space->nested[1] = isl_space_curry(space->nested[1]);
2512 if (!space->nested[1])
2513 return isl_space_free(space);
2514
2515 return space;
2516 }
2517
2518 /* Can we apply isl_space_uncurry to "space"?
2519 * That is, does it have a map space with a nested relation in its range?
2520 */
2521 isl_bool isl_space_can_uncurry(__isl_keep isl_space *space)
2522 {
2523 return isl_space_range_is_wrapping(space);
2524 }
2525
2526 /* Given a space A -> (B -> C), return the corresponding space
2527 * (A -> B) -> C.
2528 */
2529 __isl_give isl_space *isl_space_uncurry(__isl_take isl_space *space)
2530 {
2531 isl_space *dom, *ran;
2532 isl_space *ran_dom, *ran_ran;
2533
2534 if (!space)
2535 return NULL;
2536
2537 if (!isl_space_can_uncurry(space))
2538 isl_die(space->ctx, isl_error_invalid,
2539 "space cannot be uncurried",
2540 return isl_space_free(space));
2541
2542 dom = isl_space_domain(isl_space_copy(space));
2543 ran = isl_space_unwrap(isl_space_range(space));
2544 ran_dom = isl_space_domain(isl_space_copy(ran));
2545 ran_ran = isl_space_range(ran);
2546 dom = isl_space_join(isl_space_from_domain(dom),
2547 isl_space_from_range(ran_dom));
2548 return isl_space_join(isl_space_from_domain(isl_space_wrap(dom)),
2549 isl_space_from_range(ran_ran));
2550 }
2551
2552 isl_bool isl_space_has_named_params(__isl_keep isl_space *space)
2553 {
2554 int i;
2555 unsigned off;
2556
2557 if (!space)
2558 return isl_bool_error;
2559 if (space->nparam == 0)
2560 return isl_bool_true;
2561 off = isl_space_offset(space, isl_dim_param);
2562 if (off + space->nparam > space->n_id)
2563 return isl_bool_false;
2564 for (i = 0; i < space->nparam; ++i)
2565 if (!space->ids[off + i])
2566 return isl_bool_false;
2567 return isl_bool_true;
2568 }
2569
2570 /* Check that "space" has only named parameters, reporting an error
2571 * if it does not.
2572 */
2573 isl_stat isl_space_check_named_params(__isl_keep isl_space *space)
2574 {
2575 isl_bool named;
2576
2577 named = isl_space_has_named_params(space);
2578 if (named < 0)
2579 return isl_stat_error;
2580 if (!named)
2581 isl_die(isl_space_get_ctx(space), isl_error_invalid,
2582 "unexpected unnamed parameters", return isl_stat_error);
2583
2584 return isl_stat_ok;
2585 }
2586
2587 /* Align the initial parameters of space1 to match the order in space2.
2588 */
2589 __isl_give isl_space *isl_space_align_params(__isl_take isl_space *space1,
2590 __isl_take isl_space *space2)
2591 {
2592 isl_reordering *exp;
2593
2594 if (isl_space_check_named_params(space1) < 0 ||
2595 isl_space_check_named_params(space2) < 0)
2596 goto error;
2597
2598 exp = isl_parameter_alignment_reordering(space1, space2);
2599 exp = isl_reordering_extend_space(exp, space1);
2600 isl_space_free(space2);
2601 space1 = isl_reordering_get_space(exp);
2602 isl_reordering_free(exp);
2603 return space1;
2604 error:
2605 isl_space_free(space1);
2606 isl_space_free(space2);
2607 return NULL;
2608 }
2609
2610 /* Given the space of set (domain), construct a space for a map
2611 * with as domain the given space and as range the range of "model".
2612 */
2613 __isl_give isl_space *isl_space_extend_domain_with_range(
2614 __isl_take isl_space *space, __isl_take isl_space *model)
2615 {
2616 if (!model)
2617 goto error;
2618
2619 space = isl_space_from_domain(space);
2620 space = isl_space_add_dims(space, isl_dim_out,
2621 isl_space_dim(model, isl_dim_out));
2622 if (isl_space_has_tuple_id(model, isl_dim_out))
2623 space = isl_space_set_tuple_id(space, isl_dim_out,
2624 isl_space_get_tuple_id(model, isl_dim_out));
2625 if (!space)
2626 goto error;
2627 if (model->nested[1]) {
2628 isl_space *nested = isl_space_copy(model->nested[1]);
2629 int n_nested, n_space;
2630 nested = isl_space_align_params(nested, isl_space_copy(space));
2631 n_nested = isl_space_dim(nested, isl_dim_param);
2632 n_space = isl_space_dim(space, isl_dim_param);
2633 if (n_nested > n_space)
2634 nested = isl_space_drop_dims(nested, isl_dim_param,
2635 n_space, n_nested - n_space);
2636 if (!nested)
2637 goto error;
2638 space->nested[1] = nested;
2639 }
2640 isl_space_free(model);
2641 return space;
2642 error:
2643 isl_space_free(model);
2644 isl_space_free(space);
2645 return NULL;
2646 }
2647
2648 /* Compare the "type" dimensions of two isl_spaces.
2649 *
2650 * The order is fairly arbitrary.
2651 */
2652 static int isl_space_cmp_type(__isl_keep isl_space *space1,
2653 __isl_keep isl_space *space2, enum isl_dim_type type)
2654 {
2655 int cmp;
2656 isl_space *nested1, *nested2;
2657
2658 if (isl_space_dim(space1, type) != isl_space_dim(space2, type))
2659 return isl_space_dim(space1, type) -
2660 isl_space_dim(space2, type);
2661
2662 cmp = isl_id_cmp(tuple_id(space1, type), tuple_id(space2, type));
2663 if (cmp != 0)
2664 return cmp;
2665
2666 nested1 = nested(space1, type);
2667 nested2 = nested(space2, type);
2668 if (!nested1 != !nested2)
2669 return !nested1 - !nested2;
2670
2671 if (nested1)
2672 return isl_space_cmp(nested1, nested2);
2673
2674 return 0;
2675 }
2676
2677 /* Compare two isl_spaces.
2678 *
2679 * The order is fairly arbitrary.
2680 */
2681 int isl_space_cmp(__isl_keep isl_space *space1, __isl_keep isl_space *space2)
2682 {
2683 int i;
2684 int cmp;
2685
2686 if (space1 == space2)
2687 return 0;
2688 if (!space1)
2689 return -1;
2690 if (!space2)
2691 return 1;
2692
2693 cmp = isl_space_cmp_type(space1, space2, isl_dim_param);
2694 if (cmp != 0)
2695 return cmp;
2696 cmp = isl_space_cmp_type(space1, space2, isl_dim_in);
2697 if (cmp != 0)
2698 return cmp;
2699 cmp = isl_space_cmp_type(space1, space2, isl_dim_out);
2700 if (cmp != 0)
2701 return cmp;
2702
2703 if (!space1->ids && !space2->ids)
2704 return 0;
2705
2706 for (i = 0; i < n(space1, isl_dim_param); ++i) {
2707 cmp = isl_id_cmp(get_id(space1, isl_dim_param, i),
2708 get_id(space2, isl_dim_param, i));
2709 if (cmp != 0)
2710 return cmp;
2711 }
2712
2713 return 0;
2714 }
Integer set library