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