?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
isl_basic_set_expand_divs: avoid invalid access on error
[isl.git] / isl_space.c
blobb0aca350a75c65144e51671a04c78cac5be9e0aa
1 /*
2 * Copyright 2008-2009 Katholieke Universiteit Leuven
3 * Copyright 2010 INRIA Saclay
4 *
5 * Use of this software is governed by the MIT license
6 *
7 * Written by Sven Verdoolaege, K.U.Leuven, Departement
8 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
9 * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,
10 * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France
11 */
12
13 #include <stdlib.h>
14 #include <isl_space_private.h>
15 #include <isl_id_private.h>
16 #include <isl_reordering.h>
17
18 isl_ctx *isl_space_get_ctx(__isl_keep isl_space *dim)
19 {
20 return dim ? dim->ctx : NULL;
21 }
22
23 __isl_give isl_space *isl_space_alloc(isl_ctx *ctx,
24 unsigned nparam, unsigned n_in, unsigned n_out)
25 {
26 isl_space *dim;
27
28 dim = isl_alloc_type(ctx, struct isl_space);
29 if (!dim)
30 return NULL;
31
32 dim->ctx = ctx;
33 isl_ctx_ref(ctx);
34 dim->ref = 1;
35 dim->nparam = nparam;
36 dim->n_in = n_in;
37 dim->n_out = n_out;
38
39 dim->tuple_id[0] = NULL;
40 dim->tuple_id[1] = NULL;
41
42 dim->nested[0] = NULL;
43 dim->nested[1] = NULL;
44
45 dim->n_id = 0;
46 dim->ids = NULL;
47
48 return dim;
49 }
50
51 /* Mark the space as being that of a set, by setting the domain tuple
52 * to isl_id_none.
53 */
54 static __isl_give isl_space *mark_as_set(__isl_take isl_space *space)
55 {
56 space = isl_space_cow(space);
57 if (!space)
58 return NULL;
59 space = isl_space_set_tuple_id(space, isl_dim_in, &isl_id_none);
60 return space;
61 }
62
63 /* Is the space that of a set?
64 */
65 int isl_space_is_set(__isl_keep isl_space *space)
66 {
67 if (!space)
68 return -1;
69 if (space->n_in != 0 || space->nested[0])
70 return 0;
71 if (space->tuple_id[0] != &isl_id_none)
72 return 0;
73 return 1;
74 }
75
76 /* Is the given space that of a map?
77 */
78 int isl_space_is_map(__isl_keep isl_space *space)
79 {
80 if (!space)
81 return -1;
82 return space->tuple_id[0] != &isl_id_none &&
83 space->tuple_id[1] != &isl_id_none;
84 }
85
86 __isl_give isl_space *isl_space_set_alloc(isl_ctx *ctx,
87 unsigned nparam, unsigned dim)
88 {
89 isl_space *space;
90 space = isl_space_alloc(ctx, nparam, 0, dim);
91 space = mark_as_set(space);
92 return space;
93 }
94
95 /* Mark the space as being that of a parameter domain, by setting
96 * both tuples to isl_id_none.
97 */
98 static __isl_give isl_space *mark_as_params(isl_space *space)
99 {
100 if (!space)
101 return NULL;
102 space = isl_space_set_tuple_id(space, isl_dim_in, &isl_id_none);
103 space = isl_space_set_tuple_id(space, isl_dim_out, &isl_id_none);
104 return space;
105 }
106
107 /* Is the space that of a parameter domain?
108 */
109 int isl_space_is_params(__isl_keep isl_space *space)
110 {
111 if (!space)
112 return -1;
113 if (space->n_in != 0 || space->nested[0] ||
114 space->n_out != 0 || space->nested[1])
115 return 0;
116 if (space->tuple_id[0] != &isl_id_none)
117 return 0;
118 if (space->tuple_id[1] != &isl_id_none)
119 return 0;
120 return 1;
121 }
122
123 /* Create a space for a parameter domain.
124 */
125 __isl_give isl_space *isl_space_params_alloc(isl_ctx *ctx, unsigned nparam)
126 {
127 isl_space *space;
128 space = isl_space_alloc(ctx, nparam, 0, 0);
129 space = mark_as_params(space);
130 return space;
131 }
132
133 static unsigned global_pos(__isl_keep isl_space *dim,
134 enum isl_dim_type type, unsigned pos)
135 {
136 struct isl_ctx *ctx = dim->ctx;
137
138 switch (type) {
139 case isl_dim_param:
140 isl_assert(ctx, pos < dim->nparam,
141 return isl_space_dim(dim, isl_dim_all));
142 return pos;
143 case isl_dim_in:
144 isl_assert(ctx, pos < dim->n_in,
145 return isl_space_dim(dim, isl_dim_all));
146 return pos + dim->nparam;
147 case isl_dim_out:
148 isl_assert(ctx, pos < dim->n_out,
149 return isl_space_dim(dim, isl_dim_all));
150 return pos + dim->nparam + dim->n_in;
151 default:
152 isl_assert(ctx, 0, return isl_space_dim(dim, isl_dim_all));
153 }
154 return isl_space_dim(dim, isl_dim_all);
155 }
156
157 /* Extend length of ids array to the total number of dimensions.
158 */
159 static __isl_give isl_space *extend_ids(__isl_take isl_space *dim)
160 {
161 isl_id **ids;
162 int i;
163
164 if (isl_space_dim(dim, isl_dim_all) <= dim->n_id)
165 return dim;
166
167 if (!dim->ids) {
168 dim->ids = isl_calloc_array(dim->ctx,
169 isl_id *, isl_space_dim(dim, isl_dim_all));
170 if (!dim->ids)
171 goto error;
172 } else {
173 ids = isl_realloc_array(dim->ctx, dim->ids,
174 isl_id *, isl_space_dim(dim, isl_dim_all));
175 if (!ids)
176 goto error;
177 dim->ids = ids;
178 for (i = dim->n_id; i < isl_space_dim(dim, isl_dim_all); ++i)
179 dim->ids[i] = NULL;
180 }
181
182 dim->n_id = isl_space_dim(dim, isl_dim_all);
183
184 return dim;
185 error:
186 isl_space_free(dim);
187 return NULL;
188 }
189
190 static __isl_give isl_space *set_id(__isl_take isl_space *dim,
191 enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
192 {
193 dim = isl_space_cow(dim);
194
195 if (!dim)
196 goto error;
197
198 pos = global_pos(dim, type, pos);
199 if (pos == isl_space_dim(dim, isl_dim_all))
200 goto error;
201
202 if (pos >= dim->n_id) {
203 if (!id)
204 return dim;
205 dim = extend_ids(dim);
206 if (!dim)
207 goto error;
208 }
209
210 dim->ids[pos] = id;
211
212 return dim;
213 error:
214 isl_id_free(id);
215 isl_space_free(dim);
216 return NULL;
217 }
218
219 static __isl_keep isl_id *get_id(__isl_keep isl_space *dim,
220 enum isl_dim_type type, unsigned pos)
221 {
222 if (!dim)
223 return NULL;
224
225 pos = global_pos(dim, type, pos);
226 if (pos == isl_space_dim(dim, isl_dim_all))
227 return NULL;
228 if (pos >= dim->n_id)
229 return NULL;
230 return dim->ids[pos];
231 }
232
233 static unsigned offset(__isl_keep isl_space *dim, enum isl_dim_type type)
234 {
235 switch (type) {
236 case isl_dim_param: return 0;
237 case isl_dim_in: return dim->nparam;
238 case isl_dim_out: return dim->nparam + dim->n_in;
239 default: return 0;
240 }
241 }
242
243 static unsigned n(__isl_keep isl_space *dim, enum isl_dim_type type)
244 {
245 switch (type) {
246 case isl_dim_param: return dim->nparam;
247 case isl_dim_in: return dim->n_in;
248 case isl_dim_out: return dim->n_out;
249 case isl_dim_all: return dim->nparam + dim->n_in + dim->n_out;
250 default: return 0;
251 }
252 }
253
254 unsigned isl_space_dim(__isl_keep isl_space *dim, enum isl_dim_type type)
255 {
256 if (!dim)
257 return 0;
258 return n(dim, type);
259 }
260
261 unsigned isl_space_offset(__isl_keep isl_space *dim, enum isl_dim_type type)
262 {
263 if (!dim)
264 return 0;
265 return offset(dim, type);
266 }
267
268 static __isl_give isl_space *copy_ids(__isl_take isl_space *dst,
269 enum isl_dim_type dst_type, unsigned offset, __isl_keep isl_space *src,
270 enum isl_dim_type src_type)
271 {
272 int i;
273 isl_id *id;
274
275 if (!dst)
276 return NULL;
277
278 for (i = 0; i < n(src, src_type); ++i) {
279 id = get_id(src, src_type, i);
280 if (!id)
281 continue;
282 dst = set_id(dst, dst_type, offset + i, isl_id_copy(id));
283 if (!dst)
284 return NULL;
285 }
286 return dst;
287 }
288
289 __isl_take isl_space *isl_space_dup(__isl_keep isl_space *dim)
290 {
291 isl_space *dup;
292 if (!dim)
293 return NULL;
294 dup = isl_space_alloc(dim->ctx, dim->nparam, dim->n_in, dim->n_out);
295 if (!dup)
296 return NULL;
297 if (dim->tuple_id[0] &&
298 !(dup->tuple_id[0] = isl_id_copy(dim->tuple_id[0])))
299 goto error;
300 if (dim->tuple_id[1] &&
301 !(dup->tuple_id[1] = isl_id_copy(dim->tuple_id[1])))
302 goto error;
303 if (dim->nested[0] && !(dup->nested[0] = isl_space_copy(dim->nested[0])))
304 goto error;
305 if (dim->nested[1] && !(dup->nested[1] = isl_space_copy(dim->nested[1])))
306 goto error;
307 if (!dim->ids)
308 return dup;
309 dup = copy_ids(dup, isl_dim_param, 0, dim, isl_dim_param);
310 dup = copy_ids(dup, isl_dim_in, 0, dim, isl_dim_in);
311 dup = copy_ids(dup, isl_dim_out, 0, dim, isl_dim_out);
312 return dup;
313 error:
314 isl_space_free(dup);
315 return NULL;
316 }
317
318 __isl_give isl_space *isl_space_cow(__isl_take isl_space *dim)
319 {
320 if (!dim)
321 return NULL;
322
323 if (dim->ref == 1)
324 return dim;
325 dim->ref--;
326 return isl_space_dup(dim);
327 }
328
329 __isl_give isl_space *isl_space_copy(__isl_keep isl_space *dim)
330 {
331 if (!dim)
332 return NULL;
333
334 dim->ref++;
335 return dim;
336 }
337
338 void *isl_space_free(__isl_take isl_space *dim)
339 {
340 int i;
341
342 if (!dim)
343 return NULL;
344
345 if (--dim->ref > 0)
346 return NULL;
347
348 isl_id_free(dim->tuple_id[0]);
349 isl_id_free(dim->tuple_id[1]);
350
351 isl_space_free(dim->nested[0]);
352 isl_space_free(dim->nested[1]);
353
354 for (i = 0; i < dim->n_id; ++i)
355 isl_id_free(dim->ids[i]);
356 free(dim->ids);
357 isl_ctx_deref(dim->ctx);
358
359 free(dim);
360
361 return NULL;
362 }
363
364 /* Check if "s" is a valid dimension or tuple name.
365 * We currently only forbid names that look like a number.
366 *
367 * s is assumed to be non-NULL.
368 */
369 static int name_ok(isl_ctx *ctx, const char *s)
370 {
371 char *p;
372 long dummy;
373
374 dummy = strtol(s, &p, 0);
375 if (p != s)
376 isl_die(ctx, isl_error_invalid, "name looks like a number",
377 return 0);
378
379 return 1;
380 }
381
382 /* Is it possible for the given dimension type to have a tuple id?
383 */
384 static int space_can_have_id(__isl_keep isl_space *space,
385 enum isl_dim_type type)
386 {
387 if (!space)
388 return 0;
389 if (isl_space_is_params(space))
390 isl_die(space->ctx, isl_error_invalid,
391 "parameter spaces don't have tuple ids", return 0);
392 if (isl_space_is_set(space) && type != isl_dim_set)
393 isl_die(space->ctx, isl_error_invalid,
394 "set spaces can only have a set id", return 0);
395 if (type != isl_dim_in && type != isl_dim_out)
396 isl_die(space->ctx, isl_error_invalid,
397 "only input, output and set tuples can have ids",
398 return 0);
399
400 return 1;
401 }
402
403 /* Does the tuple have an id?
404 */
405 int isl_space_has_tuple_id(__isl_keep isl_space *dim, enum isl_dim_type type)
406 {
407 if (!space_can_have_id(dim, type))
408 return -1;
409 return dim->tuple_id[type - isl_dim_in] != NULL;
410 }
411
412 __isl_give isl_id *isl_space_get_tuple_id(__isl_keep isl_space *dim,
413 enum isl_dim_type type)
414 {
415 int has_id;
416
417 if (!dim)
418 return NULL;
419 has_id = isl_space_has_tuple_id(dim, type);
420 if (has_id < 0)
421 return NULL;
422 if (!has_id)
423 isl_die(dim->ctx, isl_error_invalid,
424 "tuple has no id", return NULL);
425 return isl_id_copy(dim->tuple_id[type - isl_dim_in]);
426 }
427
428 __isl_give isl_space *isl_space_set_tuple_id(__isl_take isl_space *dim,
429 enum isl_dim_type type, __isl_take isl_id *id)
430 {
431 dim = isl_space_cow(dim);
432 if (!dim || !id)
433 goto error;
434 if (type != isl_dim_in && type != isl_dim_out)
435 isl_die(dim->ctx, isl_error_invalid,
436 "only input, output and set tuples can have names",
437 goto error);
438
439 isl_id_free(dim->tuple_id[type - isl_dim_in]);
440 dim->tuple_id[type - isl_dim_in] = id;
441
442 return dim;
443 error:
444 isl_id_free(id);
445 isl_space_free(dim);
446 return NULL;
447 }
448
449 __isl_give isl_space *isl_space_reset_tuple_id(__isl_take isl_space *dim,
450 enum isl_dim_type type)
451 {
452 dim = isl_space_cow(dim);
453 if (!dim)
454 return NULL;
455 if (type != isl_dim_in && type != isl_dim_out)
456 isl_die(dim->ctx, isl_error_invalid,
457 "only input, output and set tuples can have names",
458 goto error);
459
460 isl_id_free(dim->tuple_id[type - isl_dim_in]);
461 dim->tuple_id[type - isl_dim_in] = NULL;
462
463 return dim;
464 error:
465 isl_space_free(dim);
466 return NULL;
467 }
468
469 /* Set the id of the given dimension of "space" to "id".
470 * If the dimension already has an id, then it is replaced.
471 * If the dimension is a parameter, then we need to change it
472 * in the nested spaces (if any) as well.
473 */
474 __isl_give isl_space *isl_space_set_dim_id(__isl_take isl_space *space,
475 enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
476 {
477 space = isl_space_cow(space);
478 if (!space || !id)
479 goto error;
480
481 if (type == isl_dim_param) {
482 int i;
483
484 for (i = 0; i < 2; ++i) {
485 if (!space->nested[i])
486 continue;
487 space->nested[i] =
488 isl_space_set_dim_id(space->nested[i],
489 type, pos, isl_id_copy(id));
490 if (!space->nested[i])
491 goto error;
492 }
493 }
494
495 isl_id_free(get_id(space, type, pos));
496 return set_id(space, type, pos, id);
497 error:
498 isl_id_free(id);
499 isl_space_free(space);
500 return NULL;
501 }
502
503 /* Reset the id of the given dimension of "space".
504 * If the dimension already has an id, then it is removed.
505 * If the dimension is a parameter, then we need to reset it
506 * in the nested spaces (if any) as well.
507 */
508 __isl_give isl_space *isl_space_reset_dim_id(__isl_take isl_space *space,
509 enum isl_dim_type type, unsigned pos)
510 {
511 space = isl_space_cow(space);
512 if (!space)
513 goto error;
514
515 if (type == isl_dim_param) {
516 int i;
517
518 for (i = 0; i < 2; ++i) {
519 if (!space->nested[i])
520 continue;
521 space->nested[i] =
522 isl_space_reset_dim_id(space->nested[i],
523 type, pos);
524 if (!space->nested[i])
525 goto error;
526 }
527 }
528
529 isl_id_free(get_id(space, type, pos));
530 return set_id(space, type, pos, NULL);
531 error:
532 isl_space_free(space);
533 return NULL;
534 }
535
536 int isl_space_has_dim_id(__isl_keep isl_space *dim,
537 enum isl_dim_type type, unsigned pos)
538 {
539 if (!dim)
540 return -1;
541 return get_id(dim, type, pos) != NULL;
542 }
543
544 __isl_give isl_id *isl_space_get_dim_id(__isl_keep isl_space *dim,
545 enum isl_dim_type type, unsigned pos)
546 {
547 if (!dim)
548 return NULL;
549 if (!get_id(dim, type, pos))
550 isl_die(dim->ctx, isl_error_invalid,
551 "dim has no id", return NULL);
552 return isl_id_copy(get_id(dim, type, pos));
553 }
554
555 __isl_give isl_space *isl_space_set_tuple_name(__isl_take isl_space *dim,
556 enum isl_dim_type type, const char *s)
557 {
558 isl_id *id;
559
560 if (!dim)
561 return NULL;
562
563 if (!s)
564 return isl_space_reset_tuple_id(dim, type);
565
566 if (!name_ok(dim->ctx, s))
567 goto error;
568
569 id = isl_id_alloc(dim->ctx, s, NULL);
570 return isl_space_set_tuple_id(dim, type, id);
571 error:
572 isl_space_free(dim);
573 return NULL;
574 }
575
576 /* Does the tuple have a name?
577 */
578 int isl_space_has_tuple_name(__isl_keep isl_space *space,
579 enum isl_dim_type type)
580 {
581 isl_id *id;
582
583 if (!space_can_have_id(space, type))
584 return -1;
585 id = space->tuple_id[type - isl_dim_in];
586 return id && id->name;
587 }
588
589 const char *isl_space_get_tuple_name(__isl_keep isl_space *dim,
590 enum isl_dim_type type)
591 {
592 isl_id *id;
593 if (!dim)
594 return NULL;
595 if (type != isl_dim_in && type != isl_dim_out)
596 return NULL;
597 id = dim->tuple_id[type - isl_dim_in];
598 return id ? id->name : NULL;
599 }
600
601 __isl_give isl_space *isl_space_set_dim_name(__isl_take isl_space *dim,
602 enum isl_dim_type type, unsigned pos,
603 const char *s)
604 {
605 isl_id *id;
606
607 if (!dim)
608 return NULL;
609 if (!s)
610 return isl_space_reset_dim_id(dim, type, pos);
611 if (!name_ok(dim->ctx, s))
612 goto error;
613 id = isl_id_alloc(dim->ctx, s, NULL);
614 return isl_space_set_dim_id(dim, type, pos, id);
615 error:
616 isl_space_free(dim);
617 return NULL;
618 }
619
620 /* Does the given dimension have a name?
621 */
622 int isl_space_has_dim_name(__isl_keep isl_space *space,
623 enum isl_dim_type type, unsigned pos)
624 {
625 isl_id *id;
626
627 if (!space)
628 return -1;
629 id = get_id(space, type, pos);
630 return id && id->name;
631 }
632
633 __isl_keep const char *isl_space_get_dim_name(__isl_keep isl_space *dim,
634 enum isl_dim_type type, unsigned pos)
635 {
636 isl_id *id = get_id(dim, type, pos);
637 return id ? id->name : NULL;
638 }
639
640 int isl_space_find_dim_by_id(__isl_keep isl_space *dim, enum isl_dim_type type,
641 __isl_keep isl_id *id)
642 {
643 int i;
644 int offset;
645 int n;
646
647 if (!dim || !id)
648 return -1;
649
650 offset = isl_space_offset(dim, type);
651 n = isl_space_dim(dim, type);
652 for (i = 0; i < n && offset + i < dim->n_id; ++i)
653 if (dim->ids[offset + i] == id)
654 return i;
655
656 return -1;
657 }
658
659 int isl_space_find_dim_by_name(__isl_keep isl_space *space,
660 enum isl_dim_type type, const char *name)
661 {
662 int i;
663 int offset;
664 int n;
665
666 if (!space || !name)
667 return -1;
668
669 offset = isl_space_offset(space, type);
670 n = isl_space_dim(space, type);
671 for (i = 0; i < n && offset + i < space->n_id; ++i)
672 if (space->ids[offset + i]->name &&
673 !strcmp(space->ids[offset + i]->name, name))
674 return i;
675
676 return -1;
677 }
678
679 static __isl_keep isl_id *tuple_id(__isl_keep isl_space *dim,
680 enum isl_dim_type type)
681 {
682 if (!dim)
683 return NULL;
684 if (type == isl_dim_in)
685 return dim->tuple_id[0];
686 if (type == isl_dim_out)
687 return dim->tuple_id[1];
688 return NULL;
689 }
690
691 static __isl_keep isl_space *nested(__isl_keep isl_space *dim,
692 enum isl_dim_type type)
693 {
694 if (!dim)
695 return NULL;
696 if (type == isl_dim_in)
697 return dim->nested[0];
698 if (type == isl_dim_out)
699 return dim->nested[1];
700 return NULL;
701 }
702
703 int isl_space_tuple_match(__isl_keep isl_space *dim1, enum isl_dim_type dim1_type,
704 __isl_keep isl_space *dim2, enum isl_dim_type dim2_type)
705 {
706 isl_id *id1, *id2;
707 isl_space *nested1, *nested2;
708
709 if (!dim1 || !dim2)
710 return -1;
711
712 if (dim1 == dim2 && dim1_type == dim2_type)
713 return 1;
714
715 if (n(dim1, dim1_type) != n(dim2, dim2_type))
716 return 0;
717 id1 = tuple_id(dim1, dim1_type);
718 id2 = tuple_id(dim2, dim2_type);
719 if (!id1 ^ !id2)
720 return 0;
721 if (id1 && id1 != id2)
722 return 0;
723 nested1 = nested(dim1, dim1_type);
724 nested2 = nested(dim2, dim2_type);
725 if (!nested1 ^ !nested2)
726 return 0;
727 if (nested1 && !isl_space_is_equal(nested1, nested2))
728 return 0;
729 return 1;
730 }
731
732 static int match(__isl_keep isl_space *dim1, enum isl_dim_type dim1_type,
733 __isl_keep isl_space *dim2, enum isl_dim_type dim2_type)
734 {
735 int i;
736
737 if (dim1 == dim2 && dim1_type == dim2_type)
738 return 1;
739
740 if (!isl_space_tuple_match(dim1, dim1_type, dim2, dim2_type))
741 return 0;
742
743 if (!dim1->ids && !dim2->ids)
744 return 1;
745
746 for (i = 0; i < n(dim1, dim1_type); ++i) {
747 if (get_id(dim1, dim1_type, i) != get_id(dim2, dim2_type, i))
748 return 0;
749 }
750 return 1;
751 }
752
753 int isl_space_match(__isl_keep isl_space *dim1, enum isl_dim_type dim1_type,
754 __isl_keep isl_space *dim2, enum isl_dim_type dim2_type)
755 {
756 if (!dim1 || !dim2)
757 return -1;
758
759 return match(dim1, dim1_type, dim2, dim2_type);
760 }
761
762 static void get_ids(__isl_keep isl_space *dim, enum isl_dim_type type,
763 unsigned first, unsigned n, __isl_keep isl_id **ids)
764 {
765 int i;
766
767 for (i = 0; i < n ; ++i)
768 ids[i] = get_id(dim, type, first + i);
769 }
770
771 __isl_give isl_space *isl_space_extend(__isl_take isl_space *dim,
772 unsigned nparam, unsigned n_in, unsigned n_out)
773 {
774 isl_id **ids = NULL;
775
776 if (!dim)
777 return NULL;
778 if (dim->nparam == nparam && dim->n_in == n_in && dim->n_out == n_out)
779 return dim;
780
781 isl_assert(dim->ctx, dim->nparam <= nparam, goto error);
782 isl_assert(dim->ctx, dim->n_in <= n_in, goto error);
783 isl_assert(dim->ctx, dim->n_out <= n_out, goto error);
784
785 dim = isl_space_cow(dim);
786 if (!dim)
787 goto error;
788
789 if (dim->ids) {
790 ids = isl_calloc_array(dim->ctx, isl_id *,
791 nparam + n_in + n_out);
792 if (!ids)
793 goto error;
794 get_ids(dim, isl_dim_param, 0, dim->nparam, ids);
795 get_ids(dim, isl_dim_in, 0, dim->n_in, ids + nparam);
796 get_ids(dim, isl_dim_out, 0, dim->n_out, ids + nparam + n_in);
797 free(dim->ids);
798 dim->ids = ids;
799 dim->n_id = nparam + n_in + n_out;
800 }
801 dim->nparam = nparam;
802 dim->n_in = n_in;
803 dim->n_out = n_out;
804
805 return dim;
806 error:
807 free(ids);
808 isl_space_free(dim);
809 return NULL;
810 }
811
812 __isl_give isl_space *isl_space_add_dims(__isl_take isl_space *dim,
813 enum isl_dim_type type, unsigned n)
814 {
815 if (!dim)
816 return NULL;
817 dim = isl_space_reset(dim, type);
818 switch (type) {
819 case isl_dim_param:
820 dim = isl_space_extend(dim,
821 dim->nparam + n, dim->n_in, dim->n_out);
822 if (dim && dim->nested[0] &&
823 !(dim->nested[0] = isl_space_add_dims(dim->nested[0],
824 isl_dim_param, n)))
825 goto error;
826 if (dim && dim->nested[1] &&
827 !(dim->nested[1] = isl_space_add_dims(dim->nested[1],
828 isl_dim_param, n)))
829 goto error;
830 return dim;
831 case isl_dim_in:
832 return isl_space_extend(dim,
833 dim->nparam, dim->n_in + n, dim->n_out);
834 case isl_dim_out:
835 return isl_space_extend(dim,
836 dim->nparam, dim->n_in, dim->n_out + n);
837 default:
838 isl_die(dim->ctx, isl_error_invalid,
839 "cannot add dimensions of specified type", goto error);
840 }
841 error:
842 isl_space_free(dim);
843 return NULL;
844 }
845
846 static int valid_dim_type(enum isl_dim_type type)
847 {
848 switch (type) {
849 case isl_dim_param:
850 case isl_dim_in:
851 case isl_dim_out:
852 return 1;
853 default:
854 return 0;
855 }
856 }
857
858 /* Insert "n" dimensions of type "type" at position "pos".
859 * If we are inserting parameters, then they are also inserted in
860 * any nested spaces.
861 */
862 __isl_give isl_space *isl_space_insert_dims(__isl_take isl_space *dim,
863 enum isl_dim_type type, unsigned pos, unsigned n)
864 {
865 isl_id **ids = NULL;
866
867 if (!dim)
868 return NULL;
869 if (n == 0)
870 return isl_space_reset(dim, type);
871
872 if (!valid_dim_type(type))
873 isl_die(dim->ctx, isl_error_invalid,
874 "cannot insert dimensions of specified type",
875 goto error);
876
877 isl_assert(dim->ctx, pos <= isl_space_dim(dim, type), goto error);
878
879 dim = isl_space_cow(dim);
880 if (!dim)
881 return NULL;
882
883 if (dim->ids) {
884 enum isl_dim_type t, o = isl_dim_param;
885 int off;
886 int s[3];
887 ids = isl_calloc_array(dim->ctx, isl_id *,
888 dim->nparam + dim->n_in + dim->n_out + n);
889 if (!ids)
890 goto error;
891 off = 0;
892 s[isl_dim_param - o] = dim->nparam;
893 s[isl_dim_in - o] = dim->n_in;
894 s[isl_dim_out - o] = dim->n_out;
895 for (t = isl_dim_param; t <= isl_dim_out; ++t) {
896 if (t != type) {
897 get_ids(dim, t, 0, s[t - o], ids + off);
898 off += s[t - o];
899 } else {
900 get_ids(dim, t, 0, pos, ids + off);
901 off += pos + n;
902 get_ids(dim, t, pos, s[t - o] - pos, ids + off);
903 off += s[t - o] - pos;
904 }
905 }
906 free(dim->ids);
907 dim->ids = ids;
908 dim->n_id = dim->nparam + dim->n_in + dim->n_out + n;
909 }
910 switch (type) {
911 case isl_dim_param: dim->nparam += n; break;
912 case isl_dim_in: dim->n_in += n; break;
913 case isl_dim_out: dim->n_out += n; break;
914 default: ;
915 }
916 dim = isl_space_reset(dim, type);
917
918 if (type == isl_dim_param) {
919 if (dim && dim->nested[0] &&
920 !(dim->nested[0] = isl_space_insert_dims(dim->nested[0],
921 isl_dim_param, pos, n)))
922 goto error;
923 if (dim && dim->nested[1] &&
924 !(dim->nested[1] = isl_space_insert_dims(dim->nested[1],
925 isl_dim_param, pos, n)))
926 goto error;
927 }
928
929 return dim;
930 error:
931 isl_space_free(dim);
932 return NULL;
933 }
934
935 __isl_give isl_space *isl_space_move_dims(__isl_take isl_space *dim,
936 enum isl_dim_type dst_type, unsigned dst_pos,
937 enum isl_dim_type src_type, unsigned src_pos, unsigned n)
938 {
939 int i;
940
941 if (!dim)
942 return NULL;
943 if (n == 0)
944 return dim;
945
946 isl_assert(dim->ctx, src_pos + n <= isl_space_dim(dim, src_type),
947 goto error);
948
949 if (dst_type == src_type && dst_pos == src_pos)
950 return dim;
951
952 isl_assert(dim->ctx, dst_type != src_type, goto error);
953
954 dim = isl_space_reset(dim, src_type);
955 dim = isl_space_reset(dim, dst_type);
956
957 dim = isl_space_cow(dim);
958 if (!dim)
959 return NULL;
960
961 if (dim->ids) {
962 isl_id **ids;
963 enum isl_dim_type t, o = isl_dim_param;
964 int off;
965 int s[3];
966 ids = isl_calloc_array(dim->ctx, isl_id *,
967 dim->nparam + dim->n_in + dim->n_out);
968 if (!ids)
969 goto error;
970 off = 0;
971 s[isl_dim_param - o] = dim->nparam;
972 s[isl_dim_in - o] = dim->n_in;
973 s[isl_dim_out - o] = dim->n_out;
974 for (t = isl_dim_param; t <= isl_dim_out; ++t) {
975 if (t == dst_type) {
976 get_ids(dim, t, 0, dst_pos, ids + off);
977 off += dst_pos;
978 get_ids(dim, src_type, src_pos, n, ids + off);
979 off += n;
980 get_ids(dim, t, dst_pos, s[t - o] - dst_pos,
981 ids + off);
982 off += s[t - o] - dst_pos;
983 } else if (t == src_type) {
984 get_ids(dim, t, 0, src_pos, ids + off);
985 off += src_pos;
986 get_ids(dim, t, src_pos + n,
987 s[t - o] - src_pos - n, ids + off);
988 off += s[t - o] - src_pos - n;
989 } else {
990 get_ids(dim, t, 0, s[t - o], ids + off);
991 off += s[t - o];
992 }
993 }
994 free(dim->ids);
995 dim->ids = ids;
996 dim->n_id = dim->nparam + dim->n_in + dim->n_out;
997 }
998
999 switch (dst_type) {
1000 case isl_dim_param: dim->nparam += n; break;
1001 case isl_dim_in: dim->n_in += n; break;
1002 case isl_dim_out: dim->n_out += n; break;
1003 default: ;
1004 }
1005
1006 switch (src_type) {
1007 case isl_dim_param: dim->nparam -= n; break;
1008 case isl_dim_in: dim->n_in -= n; break;
1009 case isl_dim_out: dim->n_out -= n; break;
1010 default: ;
1011 }
1012
1013 if (dst_type != isl_dim_param && src_type != isl_dim_param)
1014 return dim;
1015
1016 for (i = 0; i < 2; ++i) {
1017 if (!dim->nested[i])
1018 continue;
1019 dim->nested[i] = isl_space_replace(dim->nested[i],
1020 isl_dim_param, dim);
1021 if (!dim->nested[i])
1022 goto error;
1023 }
1024
1025 return dim;
1026 error:
1027 isl_space_free(dim);
1028 return NULL;
1029 }
1030
1031 __isl_give isl_space *isl_space_join(__isl_take isl_space *left,
1032 __isl_take isl_space *right)
1033 {
1034 isl_space *dim;
1035
1036 if (!left || !right)
1037 goto error;
1038
1039 isl_assert(left->ctx, match(left, isl_dim_param, right, isl_dim_param),
1040 goto error);
1041 isl_assert(left->ctx,
1042 isl_space_tuple_match(left, isl_dim_out, right, isl_dim_in),
1043 goto error);
1044
1045 dim = isl_space_alloc(left->ctx, left->nparam, left->n_in, right->n_out);
1046 if (!dim)
1047 goto error;
1048
1049 dim = copy_ids(dim, isl_dim_param, 0, left, isl_dim_param);
1050 dim = copy_ids(dim, isl_dim_in, 0, left, isl_dim_in);
1051 dim = copy_ids(dim, isl_dim_out, 0, right, isl_dim_out);
1052
1053 if (dim && left->tuple_id[0] &&
1054 !(dim->tuple_id[0] = isl_id_copy(left->tuple_id[0])))
1055 goto error;
1056 if (dim && right->tuple_id[1] &&
1057 !(dim->tuple_id[1] = isl_id_copy(right->tuple_id[1])))
1058 goto error;
1059 if (dim && left->nested[0] &&
1060 !(dim->nested[0] = isl_space_copy(left->nested[0])))
1061 goto error;
1062 if (dim && right->nested[1] &&
1063 !(dim->nested[1] = isl_space_copy(right->nested[1])))
1064 goto error;
1065
1066 isl_space_free(left);
1067 isl_space_free(right);
1068
1069 return dim;
1070 error:
1071 isl_space_free(left);
1072 isl_space_free(right);
1073 return NULL;
1074 }
1075
1076 __isl_give isl_space *isl_space_product(__isl_take isl_space *left,
1077 __isl_take isl_space *right)
1078 {
1079 isl_space *dom1, *dom2, *nest1, *nest2;
1080
1081 if (!left || !right)
1082 goto error;
1083
1084 isl_assert(left->ctx, match(left, isl_dim_param, right, isl_dim_param),
1085 goto error);
1086
1087 dom1 = isl_space_domain(isl_space_copy(left));
1088 dom2 = isl_space_domain(isl_space_copy(right));
1089 nest1 = isl_space_wrap(isl_space_join(isl_space_reverse(dom1), dom2));
1090
1091 dom1 = isl_space_range(left);
1092 dom2 = isl_space_range(right);
1093 nest2 = isl_space_wrap(isl_space_join(isl_space_reverse(dom1), dom2));
1094
1095 return isl_space_join(isl_space_reverse(nest1), nest2);
1096 error:
1097 isl_space_free(left);
1098 isl_space_free(right);
1099 return NULL;
1100 }
1101
1102 /* Given two spaces { A -> C } and { B -> C }, construct the space
1103 * { [A -> B] -> C }
1104 */
1105 __isl_give isl_space *isl_space_domain_product(__isl_take isl_space *left,
1106 __isl_take isl_space *right)
1107 {
1108 isl_space *ran, *dom1, *dom2, *nest;
1109
1110 if (!left || !right)
1111 goto error;
1112
1113 if (!match(left, isl_dim_param, right, isl_dim_param))
1114 isl_die(left->ctx, isl_error_invalid,
1115 "parameters need to match", goto error);
1116 if (!isl_space_tuple_match(left, isl_dim_out, right, isl_dim_out))
1117 isl_die(left->ctx, isl_error_invalid,
1118 "ranges need to match", goto error);
1119
1120 ran = isl_space_range(isl_space_copy(left));
1121
1122 dom1 = isl_space_domain(left);
1123 dom2 = isl_space_domain(right);
1124 nest = isl_space_wrap(isl_space_join(isl_space_reverse(dom1), dom2));
1125
1126 return isl_space_join(isl_space_reverse(nest), ran);
1127 error:
1128 isl_space_free(left);
1129 isl_space_free(right);
1130 return NULL;
1131 }
1132
1133 __isl_give isl_space *isl_space_range_product(__isl_take isl_space *left,
1134 __isl_take isl_space *right)
1135 {
1136 isl_space *dom, *ran1, *ran2, *nest;
1137
1138 if (!left || !right)
1139 goto error;
1140
1141 isl_assert(left->ctx, match(left, isl_dim_param, right, isl_dim_param),
1142 goto error);
1143 if (!isl_space_tuple_match(left, isl_dim_in, right, isl_dim_in))
1144 isl_die(left->ctx, isl_error_invalid,
1145 "domains need to match", goto error);
1146
1147 dom = isl_space_domain(isl_space_copy(left));
1148
1149 ran1 = isl_space_range(left);
1150 ran2 = isl_space_range(right);
1151 nest = isl_space_wrap(isl_space_join(isl_space_reverse(ran1), ran2));
1152
1153 return isl_space_join(isl_space_reverse(dom), nest);
1154 error:
1155 isl_space_free(left);
1156 isl_space_free(right);
1157 return NULL;
1158 }
1159
1160 __isl_give isl_space *isl_space_map_from_set(__isl_take isl_space *dim)
1161 {
1162 isl_ctx *ctx;
1163 isl_id **ids = NULL;
1164
1165 if (!dim)
1166 return NULL;
1167 ctx = isl_space_get_ctx(dim);
1168 if (!isl_space_is_set(dim))
1169 isl_die(ctx, isl_error_invalid, "not a set space", goto error);
1170 dim = isl_space_cow(dim);
1171 if (!dim)
1172 return NULL;
1173 if (dim->ids) {
1174 ids = isl_calloc_array(dim->ctx, isl_id *,
1175 dim->nparam + dim->n_out + dim->n_out);
1176 if (!ids)
1177 goto error;
1178 get_ids(dim, isl_dim_param, 0, dim->nparam, ids);
1179 get_ids(dim, isl_dim_out, 0, dim->n_out, ids + dim->nparam);
1180 }
1181 dim->n_in = dim->n_out;
1182 if (ids) {
1183 free(dim->ids);
1184 dim->ids = ids;
1185 dim->n_id = dim->nparam + dim->n_out + dim->n_out;
1186 dim = copy_ids(dim, isl_dim_out, 0, dim, isl_dim_in);
1187 }
1188 isl_id_free(dim->tuple_id[0]);
1189 dim->tuple_id[0] = isl_id_copy(dim->tuple_id[1]);
1190 isl_space_free(dim->nested[0]);
1191 dim->nested[0] = isl_space_copy(dim->nested[1]);
1192 return dim;
1193 error:
1194 isl_space_free(dim);
1195 return NULL;
1196 }
1197
1198 __isl_give isl_space *isl_space_map_from_domain_and_range(
1199 __isl_take isl_space *domain, __isl_take isl_space *range)
1200 {
1201 if (!domain || !range)
1202 goto error;
1203 if (!isl_space_is_set(domain))
1204 isl_die(isl_space_get_ctx(domain), isl_error_invalid,
1205 "domain is not a set space", goto error);
1206 if (!isl_space_is_set(range))
1207 isl_die(isl_space_get_ctx(range), isl_error_invalid,
1208 "range is not a set space", goto error);
1209 return isl_space_join(isl_space_reverse(domain), range);
1210 error:
1211 isl_space_free(domain);
1212 isl_space_free(range);
1213 return NULL;
1214 }
1215
1216 static __isl_give isl_space *set_ids(__isl_take isl_space *dim,
1217 enum isl_dim_type type,
1218 unsigned first, unsigned n, __isl_take isl_id **ids)
1219 {
1220 int i;
1221
1222 for (i = 0; i < n ; ++i)
1223 dim = set_id(dim, type, first + i, ids[i]);
1224
1225 return dim;
1226 }
1227
1228 __isl_give isl_space *isl_space_reverse(__isl_take isl_space *dim)
1229 {
1230 unsigned t;
1231 isl_space *nested;
1232 isl_id **ids = NULL;
1233 isl_id *id;
1234
1235 if (!dim)
1236 return NULL;
1237 if (match(dim, isl_dim_in, dim, isl_dim_out))
1238 return dim;
1239
1240 dim = isl_space_cow(dim);
1241 if (!dim)
1242 return NULL;
1243
1244 id = dim->tuple_id[0];
1245 dim->tuple_id[0] = dim->tuple_id[1];
1246 dim->tuple_id[1] = id;
1247
1248 nested = dim->nested[0];
1249 dim->nested[0] = dim->nested[1];
1250 dim->nested[1] = nested;
1251
1252 if (dim->ids) {
1253 ids = isl_alloc_array(dim->ctx, isl_id *,
1254 dim->n_in + dim->n_out);
1255 if (!ids)
1256 goto error;
1257 get_ids(dim, isl_dim_in, 0, dim->n_in, ids);
1258 get_ids(dim, isl_dim_out, 0, dim->n_out, ids + dim->n_in);
1259 }
1260
1261 t = dim->n_in;
1262 dim->n_in = dim->n_out;
1263 dim->n_out = t;
1264
1265 if (dim->ids) {
1266 dim = set_ids(dim, isl_dim_out, 0, dim->n_out, ids);
1267 dim = set_ids(dim, isl_dim_in, 0, dim->n_in, ids + dim->n_out);
1268 free(ids);
1269 }
1270
1271 return dim;
1272 error:
1273 free(ids);
1274 isl_space_free(dim);
1275 return NULL;
1276 }
1277
1278 __isl_give isl_space *isl_space_drop_dims(__isl_take isl_space *dim,
1279 enum isl_dim_type type, unsigned first, unsigned num)
1280 {
1281 int i;
1282
1283 if (!dim)
1284 return NULL;
1285
1286 if (num == 0)
1287 return isl_space_reset(dim, type);
1288
1289 if (!valid_dim_type(type))
1290 isl_die(dim->ctx, isl_error_invalid,
1291 "cannot drop dimensions of specified type", goto error);
1292
1293 isl_assert(dim->ctx, first + num <= n(dim, type), goto error);
1294 dim = isl_space_cow(dim);
1295 if (!dim)
1296 goto error;
1297 if (dim->ids) {
1298 dim = extend_ids(dim);
1299 if (!dim)
1300 goto error;
1301 for (i = 0; i < num; ++i)
1302 isl_id_free(get_id(dim, type, first + i));
1303 for (i = first+num; i < n(dim, type); ++i)
1304 set_id(dim, type, i - num, get_id(dim, type, i));
1305 switch (type) {
1306 case isl_dim_param:
1307 get_ids(dim, isl_dim_in, 0, dim->n_in,
1308 dim->ids + offset(dim, isl_dim_in) - num);
1309 case isl_dim_in:
1310 get_ids(dim, isl_dim_out, 0, dim->n_out,
1311 dim->ids + offset(dim, isl_dim_out) - num);
1312 default:
1313 ;
1314 }
1315 dim->n_id -= num;
1316 }
1317 switch (type) {
1318 case isl_dim_param: dim->nparam -= num; break;
1319 case isl_dim_in: dim->n_in -= num; break;
1320 case isl_dim_out: dim->n_out -= num; break;
1321 default: ;
1322 }
1323 dim = isl_space_reset(dim, type);
1324 if (type == isl_dim_param) {
1325 if (dim && dim->nested[0] &&
1326 !(dim->nested[0] = isl_space_drop_dims(dim->nested[0],
1327 isl_dim_param, first, num)))
1328 goto error;
1329 if (dim && dim->nested[1] &&
1330 !(dim->nested[1] = isl_space_drop_dims(dim->nested[1],
1331 isl_dim_param, first, num)))
1332 goto error;
1333 }
1334 return dim;
1335 error:
1336 isl_space_free(dim);
1337 return NULL;
1338 }
1339
1340 __isl_give isl_space *isl_space_drop_inputs(__isl_take isl_space *dim,
1341 unsigned first, unsigned n)
1342 {
1343 if (!dim)
1344 return NULL;
1345 return isl_space_drop_dims(dim, isl_dim_in, first, n);
1346 }
1347
1348 __isl_give isl_space *isl_space_drop_outputs(__isl_take isl_space *dim,
1349 unsigned first, unsigned n)
1350 {
1351 if (!dim)
1352 return NULL;
1353 return isl_space_drop_dims(dim, isl_dim_out, first, n);
1354 }
1355
1356 __isl_give isl_space *isl_space_domain(__isl_take isl_space *dim)
1357 {
1358 if (!dim)
1359 return NULL;
1360 dim = isl_space_drop_outputs(dim, 0, dim->n_out);
1361 dim = isl_space_reverse(dim);
1362 dim = mark_as_set(dim);
1363 return dim;
1364 }
1365
1366 __isl_give isl_space *isl_space_from_domain(__isl_take isl_space *dim)
1367 {
1368 if (!dim)
1369 return NULL;
1370 if (!isl_space_is_set(dim))
1371 isl_die(isl_space_get_ctx(dim), isl_error_invalid,
1372 "not a set space", goto error);
1373 dim = isl_space_reverse(dim);
1374 dim = isl_space_reset(dim, isl_dim_out);
1375 return dim;
1376 error:
1377 isl_space_free(dim);
1378 return NULL;
1379 }
1380
1381 __isl_give isl_space *isl_space_range(__isl_take isl_space *dim)
1382 {
1383 if (!dim)
1384 return NULL;
1385 dim = isl_space_drop_inputs(dim, 0, dim->n_in);
1386 dim = mark_as_set(dim);
1387 return dim;
1388 }
1389
1390 __isl_give isl_space *isl_space_from_range(__isl_take isl_space *dim)
1391 {
1392 if (!dim)
1393 return NULL;
1394 if (!isl_space_is_set(dim))
1395 isl_die(isl_space_get_ctx(dim), isl_error_invalid,
1396 "not a set space", goto error);
1397 return isl_space_reset(dim, isl_dim_in);
1398 error:
1399 isl_space_free(dim);
1400 return NULL;
1401 }
1402
1403 __isl_give isl_space *isl_space_params(__isl_take isl_space *space)
1404 {
1405 if (isl_space_is_params(space))
1406 return space;
1407 space = isl_space_drop_dims(space,
1408 isl_dim_in, 0, isl_space_dim(space, isl_dim_in));
1409 space = isl_space_drop_dims(space,
1410 isl_dim_out, 0, isl_space_dim(space, isl_dim_out));
1411 space = mark_as_params(space);
1412 return space;
1413 }
1414
1415 __isl_give isl_space *isl_space_set_from_params(__isl_take isl_space *space)
1416 {
1417 if (!space)
1418 return NULL;
1419 if (!isl_space_is_params(space))
1420 isl_die(isl_space_get_ctx(space), isl_error_invalid,
1421 "not a parameter space", goto error);
1422 return isl_space_reset(space, isl_dim_set);
1423 error:
1424 isl_space_free(space);
1425 return NULL;
1426 }
1427
1428 __isl_give isl_space *isl_space_as_set_space(__isl_take isl_space *dim)
1429 {
1430 dim = isl_space_cow(dim);
1431 if (!dim)
1432 return NULL;
1433
1434 dim->n_out += dim->n_in;
1435 dim->n_in = 0;
1436 dim = isl_space_reset(dim, isl_dim_in);
1437 dim = isl_space_reset(dim, isl_dim_out);
1438
1439 return dim;
1440 }
1441
1442 __isl_give isl_space *isl_space_underlying(__isl_take isl_space *dim,
1443 unsigned n_div)
1444 {
1445 int i;
1446
1447 if (!dim)
1448 return NULL;
1449 if (n_div == 0 &&
1450 dim->nparam == 0 && dim->n_in == 0 && dim->n_id == 0)
1451 return isl_space_reset(isl_space_reset(dim, isl_dim_in), isl_dim_out);
1452 dim = isl_space_cow(dim);
1453 if (!dim)
1454 return NULL;
1455 dim->n_out += dim->nparam + dim->n_in + n_div;
1456 dim->nparam = 0;
1457 dim->n_in = 0;
1458
1459 for (i = 0; i < dim->n_id; ++i)
1460 isl_id_free(get_id(dim, isl_dim_out, i));
1461 dim->n_id = 0;
1462 dim = isl_space_reset(dim, isl_dim_in);
1463 dim = isl_space_reset(dim, isl_dim_out);
1464
1465 return dim;
1466 }
1467
1468 /* Are the two spaces the same, including positions and names of parameters?
1469 */
1470 int isl_space_is_equal(__isl_keep isl_space *dim1, __isl_keep isl_space *dim2)
1471 {
1472 if (!dim1 || !dim2)
1473 return -1;
1474 if (dim1 == dim2)
1475 return 1;
1476 return match(dim1, isl_dim_param, dim2, isl_dim_param) &&
1477 isl_space_tuple_match(dim1, isl_dim_in, dim2, isl_dim_in) &&
1478 isl_space_tuple_match(dim1, isl_dim_out, dim2, isl_dim_out);
1479 }
1480
1481 /* Is space1 equal to the domain of space2?
1482 *
1483 * In the internal version we also allow space2 to be the space of a set,
1484 * provided space1 is a parameter space.
1485 */
1486 int isl_space_is_domain_internal(__isl_keep isl_space *space1,
1487 __isl_keep isl_space *space2)
1488 {
1489 if (!space1 || !space2)
1490 return -1;
1491 if (!isl_space_is_set(space1))
1492 return 0;
1493 return match(space1, isl_dim_param, space2, isl_dim_param) &&
1494 isl_space_tuple_match(space1, isl_dim_set, space2, isl_dim_in);
1495 }
1496
1497 /* Is space1 equal to the domain of space2?
1498 */
1499 int isl_space_is_domain(__isl_keep isl_space *space1,
1500 __isl_keep isl_space *space2)
1501 {
1502 if (!space2)
1503 return -1;
1504 if (!isl_space_is_map(space2))
1505 return 0;
1506 return isl_space_is_domain_internal(space1, space2);
1507 }
1508
1509 /* Is space1 equal to the range of space2?
1510 *
1511 * In the internal version, space2 is allowed to be the space of a set,
1512 * in which case it should be equal to space1.
1513 */
1514 int isl_space_is_range_internal(__isl_keep isl_space *space1,
1515 __isl_keep isl_space *space2)
1516 {
1517 if (!space1 || !space2)
1518 return -1;
1519 if (!isl_space_is_set(space1))
1520 return 0;
1521 return match(space1, isl_dim_param, space2, isl_dim_param) &&
1522 isl_space_tuple_match(space1, isl_dim_set, space2, isl_dim_out);
1523 }
1524
1525 /* Is space1 equal to the range of space2?
1526 */
1527 int isl_space_is_range(__isl_keep isl_space *space1,
1528 __isl_keep isl_space *space2)
1529 {
1530 if (!space2)
1531 return -1;
1532 if (!isl_space_is_map(space2))
1533 return 0;
1534 return isl_space_is_range_internal(space1, space2);
1535 }
1536
1537 int isl_space_compatible(__isl_keep isl_space *dim1,
1538 __isl_keep isl_space *dim2)
1539 {
1540 return dim1->nparam == dim2->nparam &&
1541 dim1->n_in + dim1->n_out == dim2->n_in + dim2->n_out;
1542 }
1543
1544 static uint32_t isl_hash_dim(uint32_t hash, __isl_keep isl_space *dim)
1545 {
1546 int i;
1547 isl_id *id;
1548
1549 if (!dim)
1550 return hash;
1551
1552 hash = isl_hash_builtin(hash, dim->nparam);
1553 hash = isl_hash_builtin(hash, dim->n_in);
1554 hash = isl_hash_builtin(hash, dim->n_out);
1555
1556 for (i = 0; i < dim->nparam; ++i) {
1557 id = get_id(dim, isl_dim_param, i);
1558 hash = isl_hash_id(hash, id);
1559 }
1560
1561 id = tuple_id(dim, isl_dim_in);
1562 hash = isl_hash_id(hash, id);
1563 id = tuple_id(dim, isl_dim_out);
1564 hash = isl_hash_id(hash, id);
1565
1566 hash = isl_hash_dim(hash, dim->nested[0]);
1567 hash = isl_hash_dim(hash, dim->nested[1]);
1568
1569 return hash;
1570 }
1571
1572 uint32_t isl_space_get_hash(__isl_keep isl_space *dim)
1573 {
1574 uint32_t hash;
1575
1576 if (!dim)
1577 return 0;
1578
1579 hash = isl_hash_init();
1580 hash = isl_hash_dim(hash, dim);
1581
1582 return hash;
1583 }
1584
1585 int isl_space_is_wrapping(__isl_keep isl_space *dim)
1586 {
1587 if (!dim)
1588 return -1;
1589
1590 if (!isl_space_is_set(dim))
1591 return 0;
1592
1593 return dim->nested[1] != NULL;
1594 }
1595
1596 __isl_give isl_space *isl_space_wrap(__isl_take isl_space *dim)
1597 {
1598 isl_space *wrap;
1599
1600 if (!dim)
1601 return NULL;
1602
1603 wrap = isl_space_set_alloc(dim->ctx,
1604 dim->nparam, dim->n_in + dim->n_out);
1605
1606 wrap = copy_ids(wrap, isl_dim_param, 0, dim, isl_dim_param);
1607 wrap = copy_ids(wrap, isl_dim_set, 0, dim, isl_dim_in);
1608 wrap = copy_ids(wrap, isl_dim_set, dim->n_in, dim, isl_dim_out);
1609
1610 if (!wrap)
1611 goto error;
1612
1613 wrap->nested[1] = dim;
1614
1615 return wrap;
1616 error:
1617 isl_space_free(dim);
1618 return NULL;
1619 }
1620
1621 __isl_give isl_space *isl_space_unwrap(__isl_take isl_space *dim)
1622 {
1623 isl_space *unwrap;
1624
1625 if (!dim)
1626 return NULL;
1627
1628 if (!isl_space_is_wrapping(dim))
1629 isl_die(dim->ctx, isl_error_invalid, "not a wrapping space",
1630 goto error);
1631
1632 unwrap = isl_space_copy(dim->nested[1]);
1633 isl_space_free(dim);
1634
1635 return unwrap;
1636 error:
1637 isl_space_free(dim);
1638 return NULL;
1639 }
1640
1641 int isl_space_is_named_or_nested(__isl_keep isl_space *dim, enum isl_dim_type type)
1642 {
1643 if (type != isl_dim_in && type != isl_dim_out)
1644 return 0;
1645 if (!dim)
1646 return -1;
1647 if (dim->tuple_id[type - isl_dim_in])
1648 return 1;
1649 if (dim->nested[type - isl_dim_in])
1650 return 1;
1651 return 0;
1652 }
1653
1654 int isl_space_may_be_set(__isl_keep isl_space *dim)
1655 {
1656 if (!dim)
1657 return -1;
1658 if (isl_space_is_set(dim))
1659 return 1;
1660 if (isl_space_dim(dim, isl_dim_in) != 0)
1661 return 0;
1662 if (isl_space_is_named_or_nested(dim, isl_dim_in))
1663 return 0;
1664 return 1;
1665 }
1666
1667 __isl_give isl_space *isl_space_reset(__isl_take isl_space *dim,
1668 enum isl_dim_type type)
1669 {
1670 if (!isl_space_is_named_or_nested(dim, type))
1671 return dim;
1672
1673 dim = isl_space_cow(dim);
1674 if (!dim)
1675 return NULL;
1676
1677 isl_id_free(dim->tuple_id[type - isl_dim_in]);
1678 dim->tuple_id[type - isl_dim_in] = NULL;
1679 isl_space_free(dim->nested[type - isl_dim_in]);
1680 dim->nested[type - isl_dim_in] = NULL;
1681
1682 return dim;
1683 }
1684
1685 __isl_give isl_space *isl_space_flatten(__isl_take isl_space *dim)
1686 {
1687 if (!dim)
1688 return NULL;
1689 if (!dim->nested[0] && !dim->nested[1])
1690 return dim;
1691
1692 if (dim->nested[0])
1693 dim = isl_space_reset(dim, isl_dim_in);
1694 if (dim && dim->nested[1])
1695 dim = isl_space_reset(dim, isl_dim_out);
1696
1697 return dim;
1698 }
1699
1700 __isl_give isl_space *isl_space_flatten_domain(__isl_take isl_space *dim)
1701 {
1702 if (!dim)
1703 return NULL;
1704 if (!dim->nested[0])
1705 return dim;
1706
1707 return isl_space_reset(dim, isl_dim_in);
1708 }
1709
1710 __isl_give isl_space *isl_space_flatten_range(__isl_take isl_space *dim)
1711 {
1712 if (!dim)
1713 return NULL;
1714 if (!dim->nested[1])
1715 return dim;
1716
1717 return isl_space_reset(dim, isl_dim_out);
1718 }
1719
1720 /* Replace the dimensions of the given type of dst by those of src.
1721 */
1722 __isl_give isl_space *isl_space_replace(__isl_take isl_space *dst,
1723 enum isl_dim_type type, __isl_keep isl_space *src)
1724 {
1725 dst = isl_space_cow(dst);
1726
1727 if (!dst || !src)
1728 goto error;
1729
1730 dst = isl_space_drop_dims(dst, type, 0, isl_space_dim(dst, type));
1731 dst = isl_space_add_dims(dst, type, isl_space_dim(src, type));
1732 dst = copy_ids(dst, type, 0, src, type);
1733
1734 if (dst && type == isl_dim_param) {
1735 int i;
1736 for (i = 0; i <= 1; ++i) {
1737 if (!dst->nested[i])
1738 continue;
1739 dst->nested[i] = isl_space_replace(dst->nested[i],
1740 type, src);
1741 if (!dst->nested[i])
1742 goto error;
1743 }
1744 }
1745
1746 return dst;
1747 error:
1748 isl_space_free(dst);
1749 return NULL;
1750 }
1751
1752 /* Given a dimension specification "dim" of a set, create a dimension
1753 * specification for the lift of the set. In particular, the result
1754 * is of the form [dim -> local[..]], with n_local variables in the
1755 * range of the wrapped map.
1756 */
1757 __isl_give isl_space *isl_space_lift(__isl_take isl_space *dim, unsigned n_local)
1758 {
1759 isl_space *local_dim;
1760
1761 if (!dim)
1762 return NULL;
1763
1764 local_dim = isl_space_dup(dim);
1765 local_dim = isl_space_drop_dims(local_dim, isl_dim_set, 0, dim->n_out);
1766 local_dim = isl_space_add_dims(local_dim, isl_dim_set, n_local);
1767 local_dim = isl_space_set_tuple_name(local_dim, isl_dim_set, "local");
1768 dim = isl_space_join(isl_space_from_domain(dim),
1769 isl_space_from_range(local_dim));
1770 dim = isl_space_wrap(dim);
1771 dim = isl_space_set_tuple_name(dim, isl_dim_set, "lifted");
1772
1773 return dim;
1774 }
1775
1776 int isl_space_can_zip(__isl_keep isl_space *dim)
1777 {
1778 if (!dim)
1779 return -1;
1780
1781 return dim->nested[0] && dim->nested[1];
1782 }
1783
1784 __isl_give isl_space *isl_space_zip(__isl_take isl_space *dim)
1785 {
1786 isl_space *dom, *ran;
1787 isl_space *dom_dom, *dom_ran, *ran_dom, *ran_ran;
1788
1789 if (!isl_space_can_zip(dim))
1790 isl_die(dim->ctx, isl_error_invalid, "dim cannot be zipped",
1791 goto error);
1792
1793 if (!dim)
1794 return NULL;
1795 dom = isl_space_unwrap(isl_space_domain(isl_space_copy(dim)));
1796 ran = isl_space_unwrap(isl_space_range(dim));
1797 dom_dom = isl_space_domain(isl_space_copy(dom));
1798 dom_ran = isl_space_range(dom);
1799 ran_dom = isl_space_domain(isl_space_copy(ran));
1800 ran_ran = isl_space_range(ran);
1801 dom = isl_space_join(isl_space_from_domain(dom_dom),
1802 isl_space_from_range(ran_dom));
1803 ran = isl_space_join(isl_space_from_domain(dom_ran),
1804 isl_space_from_range(ran_ran));
1805 return isl_space_join(isl_space_from_domain(isl_space_wrap(dom)),
1806 isl_space_from_range(isl_space_wrap(ran)));
1807 error:
1808 isl_space_free(dim);
1809 return NULL;
1810 }
1811
1812 /* Can we apply isl_space_curry to "space"?
1813 * That is, does it have a nested relation in its domain?
1814 */
1815 int isl_space_can_curry(__isl_keep isl_space *space)
1816 {
1817 if (!space)
1818 return -1;
1819
1820 return !!space->nested[0];
1821 }
1822
1823 /* Given a space (A -> B) -> C, return the corresponding space
1824 * A -> (B -> C).
1825 */
1826 __isl_give isl_space *isl_space_curry(__isl_take isl_space *space)
1827 {
1828 isl_space *dom, *ran;
1829 isl_space *dom_dom, *dom_ran;
1830
1831 if (!space)
1832 return NULL;
1833
1834 if (!isl_space_can_curry(space))
1835 isl_die(space->ctx, isl_error_invalid,
1836 "space cannot be curried", goto error);
1837
1838 dom = isl_space_unwrap(isl_space_domain(isl_space_copy(space)));
1839 ran = isl_space_range(space);
1840 dom_dom = isl_space_domain(isl_space_copy(dom));
1841 dom_ran = isl_space_range(dom);
1842 ran = isl_space_join(isl_space_from_domain(dom_ran),
1843 isl_space_from_range(ran));
1844 return isl_space_join(isl_space_from_domain(dom_dom),
1845 isl_space_from_range(isl_space_wrap(ran)));
1846 error:
1847 isl_space_free(space);
1848 return NULL;
1849 }
1850
1851 /* Can we apply isl_space_uncurry to "space"?
1852 * That is, does it have a nested relation in its range?
1853 */
1854 int isl_space_can_uncurry(__isl_keep isl_space *space)
1855 {
1856 if (!space)
1857 return -1;
1858
1859 return !!space->nested[1];
1860 }
1861
1862 /* Given a space A -> (B -> C), return the corresponding space
1863 * (A -> B) -> C.
1864 */
1865 __isl_give isl_space *isl_space_uncurry(__isl_take isl_space *space)
1866 {
1867 isl_space *dom, *ran;
1868 isl_space *ran_dom, *ran_ran;
1869
1870 if (!space)
1871 return NULL;
1872
1873 if (!isl_space_can_uncurry(space))
1874 isl_die(space->ctx, isl_error_invalid,
1875 "space cannot be uncurried",
1876 return isl_space_free(space));
1877
1878 dom = isl_space_domain(isl_space_copy(space));
1879 ran = isl_space_unwrap(isl_space_range(space));
1880 ran_dom = isl_space_domain(isl_space_copy(ran));
1881 ran_ran = isl_space_range(ran);
1882 dom = isl_space_join(isl_space_from_domain(dom),
1883 isl_space_from_range(ran_dom));
1884 return isl_space_join(isl_space_from_domain(isl_space_wrap(dom)),
1885 isl_space_from_range(ran_ran));
1886 }
1887
1888 int isl_space_has_named_params(__isl_keep isl_space *dim)
1889 {
1890 int i;
1891 unsigned off;
1892
1893 if (!dim)
1894 return -1;
1895 if (dim->nparam == 0)
1896 return 1;
1897 off = isl_space_offset(dim, isl_dim_param);
1898 if (off + dim->nparam > dim->n_id)
1899 return 0;
1900 for (i = 0; i < dim->nparam; ++i)
1901 if (!dim->ids[off + i])
1902 return 0;
1903 return 1;
1904 }
1905
1906 /* Align the initial parameters of dim1 to match the order in dim2.
1907 */
1908 __isl_give isl_space *isl_space_align_params(__isl_take isl_space *dim1,
1909 __isl_take isl_space *dim2)
1910 {
1911 isl_reordering *exp;
1912
1913 if (!isl_space_has_named_params(dim1) || !isl_space_has_named_params(dim2))
1914 isl_die(isl_space_get_ctx(dim1), isl_error_invalid,
1915 "parameter alignment requires named parameters",
1916 goto error);
1917
1918 dim2 = isl_space_params(dim2);
1919 exp = isl_parameter_alignment_reordering(dim1, dim2);
1920 exp = isl_reordering_extend_space(exp, dim1);
1921 isl_space_free(dim2);
1922 if (!exp)
1923 return NULL;
1924 dim1 = isl_space_copy(exp->dim);
1925 isl_reordering_free(exp);
1926 return dim1;
1927 error:
1928 isl_space_free(dim1);
1929 isl_space_free(dim2);
1930 return NULL;
1931 }
1932
1933 /* Given the space of set (domain), construct a space for a map
1934 * with as domain the given space and as range the range of "model".
1935 */
1936 __isl_give isl_space *isl_space_extend_domain_with_range(
1937 __isl_take isl_space *space, __isl_take isl_space *model)
1938 {
1939 if (!model)
1940 goto error;
1941
1942 space = isl_space_from_domain(space);
1943 space = isl_space_add_dims(space, isl_dim_out,
1944 isl_space_dim(model, isl_dim_out));
1945 if (isl_space_has_tuple_id(model, isl_dim_out))
1946 space = isl_space_set_tuple_id(space, isl_dim_out,
1947 isl_space_get_tuple_id(model, isl_dim_out));
1948 if (!space)
1949 goto error;
1950 if (model->nested[1]) {
1951 isl_space *nested = isl_space_copy(model->nested[1]);
1952 int n_nested, n_space;
1953 nested = isl_space_align_params(nested, isl_space_copy(space));
1954 n_nested = isl_space_dim(nested, isl_dim_param);
1955 n_space = isl_space_dim(space, isl_dim_param);
1956 if (n_nested > n_space)
1957 nested = isl_space_drop_dims(nested, isl_dim_param,
1958 n_space, n_nested - n_space);
1959 if (!nested)
1960 goto error;
1961 space->nested[1] = nested;
1962 }
1963 isl_space_free(model);
1964 return space;
1965 error:
1966 isl_space_free(model);
1967 isl_space_free(space);
1968 return NULL;
1969 }
Integer set library