?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
document isl_dim_move
[isl.git] / isl_dim.c
blob514ab5cf2a4c6318922e64297b31f9cf51a76790
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_dim_private.h>
15 #include <isl_id_private.h>
16 #include <isl_reordering.h>
17
18 isl_ctx *isl_dim_get_ctx(__isl_keep isl_dim *dim)
19 {
20 return dim ? dim->ctx : NULL;
21 }
22
23 struct isl_dim *isl_dim_alloc(struct isl_ctx *ctx,
24 unsigned nparam, unsigned n_in, unsigned n_out)
25 {
26 struct isl_dim *dim;
27
28 dim = isl_alloc_type(ctx, struct isl_dim);
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 struct isl_dim *isl_dim_set_alloc(struct isl_ctx *ctx,
52 unsigned nparam, unsigned dim)
53 {
54 return isl_dim_alloc(ctx, nparam, 0, dim);
55 }
56
57 static unsigned global_pos(struct isl_dim *dim,
58 enum isl_dim_type type, unsigned pos)
59 {
60 struct isl_ctx *ctx = dim->ctx;
61
62 switch (type) {
63 case isl_dim_param:
64 isl_assert(ctx, pos < dim->nparam, return isl_dim_total(dim));
65 return pos;
66 case isl_dim_in:
67 isl_assert(ctx, pos < dim->n_in, return isl_dim_total(dim));
68 return pos + dim->nparam;
69 case isl_dim_out:
70 isl_assert(ctx, pos < dim->n_out, return isl_dim_total(dim));
71 return pos + dim->nparam + dim->n_in;
72 default:
73 isl_assert(ctx, 0, return isl_dim_total(dim));
74 }
75 return isl_dim_total(dim);
76 }
77
78 /* Extend length of ids array to the total number of dimensions.
79 */
80 static __isl_give isl_dim *extend_ids(__isl_take isl_dim *dim)
81 {
82 isl_id **ids;
83 int i;
84
85 if (isl_dim_total(dim) <= dim->n_id)
86 return dim;
87
88 if (!dim->ids) {
89 dim->ids = isl_calloc_array(dim->ctx,
90 isl_id *, isl_dim_total(dim));
91 if (!dim->ids)
92 goto error;
93 } else {
94 ids = isl_realloc_array(dim->ctx, dim->ids,
95 isl_id *, isl_dim_total(dim));
96 if (!ids)
97 goto error;
98 dim->ids = ids;
99 for (i = dim->n_id; i < isl_dim_total(dim); ++i)
100 dim->ids[i] = NULL;
101 }
102
103 dim->n_id = isl_dim_total(dim);
104
105 return dim;
106 error:
107 isl_dim_free(dim);
108 return NULL;
109 }
110
111 static __isl_give isl_dim *set_id(__isl_take isl_dim *dim,
112 enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
113 {
114 dim = isl_dim_cow(dim);
115
116 if (!dim)
117 goto error;
118
119 pos = global_pos(dim, type, pos);
120 if (pos == isl_dim_total(dim))
121 goto error;
122
123 if (pos >= dim->n_id) {
124 if (!id)
125 return dim;
126 dim = extend_ids(dim);
127 if (!dim)
128 goto error;
129 }
130
131 dim->ids[pos] = id;
132
133 return dim;
134 error:
135 isl_id_free(id);
136 isl_dim_free(dim);
137 return NULL;
138 }
139
140 static __isl_keep isl_id *get_id(__isl_keep isl_dim *dim,
141 enum isl_dim_type type, unsigned pos)
142 {
143 if (!dim)
144 return NULL;
145
146 pos = global_pos(dim, type, pos);
147 if (pos == isl_dim_total(dim))
148 return NULL;
149 if (pos >= dim->n_id)
150 return NULL;
151 return dim->ids[pos];
152 }
153
154 static unsigned offset(struct isl_dim *dim, enum isl_dim_type type)
155 {
156 switch (type) {
157 case isl_dim_param: return 0;
158 case isl_dim_in: return dim->nparam;
159 case isl_dim_out: return dim->nparam + dim->n_in;
160 default: return 0;
161 }
162 }
163
164 static unsigned n(struct isl_dim *dim, enum isl_dim_type type)
165 {
166 switch (type) {
167 case isl_dim_param: return dim->nparam;
168 case isl_dim_in: return dim->n_in;
169 case isl_dim_out: return dim->n_out;
170 case isl_dim_all: return dim->nparam + dim->n_in + dim->n_out;
171 default: return 0;
172 }
173 }
174
175 unsigned isl_dim_size(struct isl_dim *dim, enum isl_dim_type type)
176 {
177 if (!dim)
178 return 0;
179 return n(dim, type);
180 }
181
182 unsigned isl_dim_offset(__isl_keep isl_dim *dim, enum isl_dim_type type)
183 {
184 if (!dim)
185 return 0;
186 return offset(dim, type);
187 }
188
189 static __isl_give isl_dim *copy_ids(__isl_take isl_dim *dst,
190 enum isl_dim_type dst_type, unsigned offset, __isl_keep isl_dim *src,
191 enum isl_dim_type src_type)
192 {
193 int i;
194 isl_id *id;
195
196 if (!dst)
197 return NULL;
198
199 for (i = 0; i < n(src, src_type); ++i) {
200 id = get_id(src, src_type, i);
201 if (!id)
202 continue;
203 dst = set_id(dst, dst_type, offset + i, isl_id_copy(id));
204 if (!dst)
205 return NULL;
206 }
207 return dst;
208 }
209
210 struct isl_dim *isl_dim_dup(struct isl_dim *dim)
211 {
212 struct isl_dim *dup;
213 if (!dim)
214 return NULL;
215 dup = isl_dim_alloc(dim->ctx, dim->nparam, dim->n_in, dim->n_out);
216 if (dim->tuple_id[0] &&
217 !(dup->tuple_id[0] = isl_id_copy(dim->tuple_id[0])))
218 goto error;
219 if (dim->tuple_id[1] &&
220 !(dup->tuple_id[1] = isl_id_copy(dim->tuple_id[1])))
221 goto error;
222 if (dim->nested[0] && !(dup->nested[0] = isl_dim_copy(dim->nested[0])))
223 goto error;
224 if (dim->nested[1] && !(dup->nested[1] = isl_dim_copy(dim->nested[1])))
225 goto error;
226 if (!dim->ids)
227 return dup;
228 dup = copy_ids(dup, isl_dim_param, 0, dim, isl_dim_param);
229 dup = copy_ids(dup, isl_dim_in, 0, dim, isl_dim_in);
230 dup = copy_ids(dup, isl_dim_out, 0, dim, isl_dim_out);
231 return dup;
232 error:
233 isl_dim_free(dup);
234 return NULL;
235 }
236
237 struct isl_dim *isl_dim_cow(struct isl_dim *dim)
238 {
239 if (!dim)
240 return NULL;
241
242 if (dim->ref == 1)
243 return dim;
244 dim->ref--;
245 return isl_dim_dup(dim);
246 }
247
248 struct isl_dim *isl_dim_copy(struct isl_dim *dim)
249 {
250 if (!dim)
251 return NULL;
252
253 dim->ref++;
254 return dim;
255 }
256
257 void isl_dim_free(struct isl_dim *dim)
258 {
259 int i;
260
261 if (!dim)
262 return;
263
264 if (--dim->ref > 0)
265 return;
266
267 isl_id_free(dim->tuple_id[0]);
268 isl_id_free(dim->tuple_id[1]);
269
270 isl_dim_free(dim->nested[0]);
271 isl_dim_free(dim->nested[1]);
272
273 for (i = 0; i < dim->n_id; ++i)
274 isl_id_free(dim->ids[i]);
275 free(dim->ids);
276 isl_ctx_deref(dim->ctx);
277
278 free(dim);
279 }
280
281 static int name_ok(isl_ctx *ctx, const char *s)
282 {
283 char *p;
284 long dummy;
285
286 dummy = strtol(s, &p, 0);
287 if (p != s)
288 isl_die(ctx, isl_error_invalid, "name looks like a number",
289 return 0);
290
291 return 1;
292 }
293
294 int isl_dim_has_tuple_id(__isl_keep isl_dim *dim, enum isl_dim_type type)
295 {
296 if (!dim)
297 return -1;
298 if (type != isl_dim_in && type != isl_dim_out)
299 isl_die(dim->ctx, isl_error_invalid,
300 "only input, output and set tuples can have ids",
301 return -1);
302 return dim->tuple_id[type - isl_dim_in] != NULL;
303 }
304
305 __isl_give isl_id *isl_dim_get_tuple_id(__isl_keep isl_dim *dim,
306 enum isl_dim_type type)
307 {
308 if (!dim)
309 return NULL;
310 if (type != isl_dim_in && type != isl_dim_out)
311 isl_die(dim->ctx, isl_error_invalid,
312 "only input, output and set tuples can have ids",
313 return NULL);
314 if (!dim->tuple_id[type - isl_dim_in])
315 isl_die(dim->ctx, isl_error_invalid,
316 "tuple has no id", return NULL);
317 return isl_id_copy(dim->tuple_id[type - isl_dim_in]);
318 }
319
320 __isl_give isl_dim *isl_dim_set_tuple_id(__isl_take isl_dim *dim,
321 enum isl_dim_type type, __isl_take isl_id *id)
322 {
323 dim = isl_dim_cow(dim);
324 if (!dim || !id)
325 goto error;
326 if (type != isl_dim_in && type != isl_dim_out)
327 isl_die(dim->ctx, isl_error_invalid,
328 "only input, output and set tuples can have names",
329 goto error);
330
331 isl_id_free(dim->tuple_id[type - isl_dim_in]);
332 dim->tuple_id[type - isl_dim_in] = id;
333
334 return dim;
335 error:
336 isl_id_free(id);
337 isl_dim_free(dim);
338 return NULL;
339 }
340
341 __isl_give isl_dim *isl_dim_reset_tuple_id(__isl_take isl_dim *dim,
342 enum isl_dim_type type)
343 {
344 dim = isl_dim_cow(dim);
345 if (!dim)
346 return NULL;
347 if (type != isl_dim_in && type != isl_dim_out)
348 isl_die(dim->ctx, isl_error_invalid,
349 "only input, output and set tuples can have names",
350 goto error);
351
352 isl_id_free(dim->tuple_id[type - isl_dim_in]);
353 dim->tuple_id[type - isl_dim_in] = NULL;
354
355 return dim;
356 error:
357 isl_dim_free(dim);
358 return NULL;
359 }
360
361 __isl_give isl_dim *isl_dim_set_dim_id(__isl_take isl_dim *dim,
362 enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
363 {
364 dim = isl_dim_cow(dim);
365 if (!dim || !id)
366 goto error;
367 isl_id_free(get_id(dim, type, pos));
368 return set_id(dim, type, pos, id);
369 error:
370 isl_id_free(id);
371 isl_dim_free(dim);
372 return NULL;
373 }
374
375 int isl_dim_has_dim_id(__isl_keep isl_dim *dim,
376 enum isl_dim_type type, unsigned pos)
377 {
378 if (!dim)
379 return -1;
380 return get_id(dim, type, pos) != NULL;
381 }
382
383 __isl_give isl_id *isl_dim_get_dim_id(__isl_keep isl_dim *dim,
384 enum isl_dim_type type, unsigned pos)
385 {
386 if (!dim)
387 return NULL;
388 if (!get_id(dim, type, pos))
389 isl_die(dim->ctx, isl_error_invalid,
390 "dim has no id", return NULL);
391 return isl_id_copy(get_id(dim, type, pos));
392 }
393
394 __isl_give isl_dim *isl_dim_set_tuple_name(__isl_take isl_dim *dim,
395 enum isl_dim_type type, const char *s)
396 {
397 isl_id *id;
398
399 if (!dim)
400 return NULL;
401
402 if (!s)
403 return isl_dim_reset_tuple_id(dim, type);
404
405 if (!name_ok(dim->ctx, s))
406 goto error;
407
408 id = isl_id_alloc(dim->ctx, s, NULL);
409 return isl_dim_set_tuple_id(dim, type, id);
410 error:
411 isl_dim_free(dim);
412 return NULL;
413 }
414
415 const char *isl_dim_get_tuple_name(__isl_keep isl_dim *dim,
416 enum isl_dim_type type)
417 {
418 isl_id *id;
419 if (!dim)
420 return NULL;
421 if (type != isl_dim_in && type != isl_dim_out)
422 return NULL;
423 id = dim->tuple_id[type - isl_dim_in];
424 return id ? id->name : NULL;
425 }
426
427 struct isl_dim *isl_dim_set_name(struct isl_dim *dim,
428 enum isl_dim_type type, unsigned pos,
429 const char *s)
430 {
431 isl_id *id;
432
433 if (!dim)
434 return NULL;
435 if (!name_ok(dim->ctx, s))
436 goto error;
437 id = isl_id_alloc(dim->ctx, s, NULL);
438 return isl_dim_set_dim_id(dim, type, pos, id);
439 error:
440 isl_dim_free(dim);
441 return NULL;
442 }
443
444 const char *isl_dim_get_name(struct isl_dim *dim,
445 enum isl_dim_type type, unsigned pos)
446 {
447 isl_id *id = get_id(dim, type, pos);
448 return id ? id->name : NULL;
449 }
450
451 int isl_dim_find_dim_by_id(__isl_keep isl_dim *dim, enum isl_dim_type type,
452 __isl_keep isl_id *id)
453 {
454 int i;
455 int offset;
456 int n;
457
458 if (!dim || !id)
459 return -1;
460
461 offset = isl_dim_offset(dim, type);
462 n = isl_dim_size(dim, type);
463 for (i = 0; i < n && offset + i < dim->n_id; ++i)
464 if (dim->ids[offset + i] == id)
465 return i;
466
467 return -1;
468 }
469
470 static __isl_keep isl_id *tuple_id(__isl_keep isl_dim *dim,
471 enum isl_dim_type type)
472 {
473 if (!dim)
474 return NULL;
475 if (type == isl_dim_in)
476 return dim->tuple_id[0];
477 if (type == isl_dim_out)
478 return dim->tuple_id[1];
479 return NULL;
480 }
481
482 static __isl_keep isl_dim *nested(__isl_keep isl_dim *dim,
483 enum isl_dim_type type)
484 {
485 if (!dim)
486 return NULL;
487 if (type == isl_dim_in)
488 return dim->nested[0];
489 if (type == isl_dim_out)
490 return dim->nested[1];
491 return NULL;
492 }
493
494 int isl_dim_tuple_match(__isl_keep isl_dim *dim1, enum isl_dim_type dim1_type,
495 __isl_keep isl_dim *dim2, enum isl_dim_type dim2_type)
496 {
497 isl_id *id1, *id2;
498 isl_dim *nested1, *nested2;
499
500 if (!dim1 || !dim2)
501 return -1;
502
503 if (n(dim1, dim1_type) != n(dim2, dim2_type))
504 return 0;
505 id1 = tuple_id(dim1, dim1_type);
506 id2 = tuple_id(dim2, dim2_type);
507 if (!id1 ^ !id2)
508 return 0;
509 if (id1 && id1 != id2)
510 return 0;
511 nested1 = nested(dim1, dim1_type);
512 nested2 = nested(dim2, dim2_type);
513 if (!nested1 ^ !nested2)
514 return 0;
515 if (nested1 && !isl_dim_equal(nested1, nested2))
516 return 0;
517 return 1;
518 }
519
520 static int match(struct isl_dim *dim1, enum isl_dim_type dim1_type,
521 struct isl_dim *dim2, enum isl_dim_type dim2_type)
522 {
523 int i;
524
525 if (!isl_dim_tuple_match(dim1, dim1_type, dim2, dim2_type))
526 return 0;
527
528 if (!dim1->ids && !dim2->ids)
529 return 1;
530
531 for (i = 0; i < n(dim1, dim1_type); ++i) {
532 if (get_id(dim1, dim1_type, i) != get_id(dim2, dim2_type, i))
533 return 0;
534 }
535 return 1;
536 }
537
538 int isl_dim_match(struct isl_dim *dim1, enum isl_dim_type dim1_type,
539 struct isl_dim *dim2, enum isl_dim_type dim2_type)
540 {
541 return match(dim1, dim1_type, dim2, dim2_type);
542 }
543
544 static void get_ids(struct isl_dim *dim, enum isl_dim_type type,
545 unsigned first, unsigned n, __isl_keep isl_id **ids)
546 {
547 int i;
548
549 for (i = 0; i < n ; ++i)
550 ids[i] = get_id(dim, type, first + i);
551 }
552
553 struct isl_dim *isl_dim_extend(struct isl_dim *dim,
554 unsigned nparam, unsigned n_in, unsigned n_out)
555 {
556 isl_id **ids = NULL;
557
558 if (!dim)
559 return NULL;
560 if (dim->nparam == nparam && dim->n_in == n_in && dim->n_out == n_out)
561 return dim;
562
563 isl_assert(dim->ctx, dim->nparam <= nparam, goto error);
564 isl_assert(dim->ctx, dim->n_in <= n_in, goto error);
565 isl_assert(dim->ctx, dim->n_out <= n_out, goto error);
566
567 dim = isl_dim_cow(dim);
568
569 if (dim->ids) {
570 ids = isl_calloc_array(dim->ctx, isl_id *,
571 nparam + n_in + n_out);
572 if (!ids)
573 goto error;
574 get_ids(dim, isl_dim_param, 0, dim->nparam, ids);
575 get_ids(dim, isl_dim_in, 0, dim->n_in, ids + nparam);
576 get_ids(dim, isl_dim_out, 0, dim->n_out, ids + nparam + n_in);
577 free(dim->ids);
578 dim->ids = ids;
579 dim->n_id = nparam + n_in + n_out;
580 }
581 dim->nparam = nparam;
582 dim->n_in = n_in;
583 dim->n_out = n_out;
584
585 return dim;
586 error:
587 free(ids);
588 isl_dim_free(dim);
589 return NULL;
590 }
591
592 struct isl_dim *isl_dim_add(struct isl_dim *dim, enum isl_dim_type type,
593 unsigned n)
594 {
595 if (!dim)
596 return NULL;
597 dim = isl_dim_reset(dim, type);
598 switch (type) {
599 case isl_dim_param:
600 dim = isl_dim_extend(dim,
601 dim->nparam + n, dim->n_in, dim->n_out);
602 if (dim && dim->nested[0] &&
603 !(dim->nested[0] = isl_dim_add(dim->nested[0],
604 isl_dim_param, n)))
605 goto error;
606 if (dim && dim->nested[1] &&
607 !(dim->nested[1] = isl_dim_add(dim->nested[1],
608 isl_dim_param, n)))
609 goto error;
610 return dim;
611 case isl_dim_in:
612 return isl_dim_extend(dim,
613 dim->nparam, dim->n_in + n, dim->n_out);
614 case isl_dim_out:
615 return isl_dim_extend(dim,
616 dim->nparam, dim->n_in, dim->n_out + n);
617 default:
618 isl_die(dim->ctx, isl_error_invalid,
619 "cannot add dimensions of specified type", goto error);
620 }
621 error:
622 isl_dim_free(dim);
623 return NULL;
624 }
625
626 static int valid_dim_type(enum isl_dim_type type)
627 {
628 switch (type) {
629 case isl_dim_param:
630 case isl_dim_in:
631 case isl_dim_out:
632 return 1;
633 default:
634 return 0;
635 }
636 }
637
638 __isl_give isl_dim *isl_dim_insert(__isl_take isl_dim *dim,
639 enum isl_dim_type type, unsigned pos, unsigned n)
640 {
641 isl_id **ids = NULL;
642
643 if (!dim)
644 return NULL;
645 if (n == 0)
646 return isl_dim_reset(dim, type);
647
648 if (!valid_dim_type(type))
649 isl_die(dim->ctx, isl_error_invalid,
650 "cannot insert dimensions of specified type",
651 goto error);
652
653 isl_assert(dim->ctx, pos <= isl_dim_size(dim, type), goto error);
654
655 dim = isl_dim_cow(dim);
656 if (!dim)
657 return NULL;
658
659 if (dim->ids) {
660 enum isl_dim_type t;
661 int off;
662 int s[3];
663 int *size = s - isl_dim_param;
664 ids = isl_calloc_array(dim->ctx, isl_id *,
665 dim->nparam + dim->n_in + dim->n_out + n);
666 if (!ids)
667 goto error;
668 off = 0;
669 size[isl_dim_param] = dim->nparam;
670 size[isl_dim_in] = dim->n_in;
671 size[isl_dim_out] = dim->n_out;
672 for (t = isl_dim_param; t <= isl_dim_out; ++t) {
673 if (t != type) {
674 get_ids(dim, t, 0, size[t], ids + off);
675 off += size[t];
676 } else {
677 get_ids(dim, t, 0, pos, ids + off);
678 off += pos + n;
679 get_ids(dim, t, pos, size[t] - pos, ids + off);
680 off += size[t] - pos;
681 }
682 }
683 free(dim->ids);
684 dim->ids = ids;
685 dim->n_id = dim->nparam + dim->n_in + dim->n_out + n;
686 }
687 switch (type) {
688 case isl_dim_param: dim->nparam += n; break;
689 case isl_dim_in: dim->n_in += n; break;
690 case isl_dim_out: dim->n_out += n; break;
691 default: ;
692 }
693 dim = isl_dim_reset(dim, type);
694
695 return dim;
696 error:
697 isl_dim_free(dim);
698 return NULL;
699 }
700
701 __isl_give isl_dim *isl_dim_move(__isl_take isl_dim *dim,
702 enum isl_dim_type dst_type, unsigned dst_pos,
703 enum isl_dim_type src_type, unsigned src_pos, unsigned n)
704 {
705 int i;
706
707 if (!dim)
708 return NULL;
709 if (n == 0)
710 return dim;
711
712 isl_assert(dim->ctx, src_pos + n <= isl_dim_size(dim, src_type),
713 goto error);
714
715 if (dst_type == src_type && dst_pos == src_pos)
716 return dim;
717
718 isl_assert(dim->ctx, dst_type != src_type, goto error);
719
720 dim = isl_dim_reset(dim, src_type);
721 dim = isl_dim_reset(dim, dst_type);
722
723 dim = isl_dim_cow(dim);
724 if (!dim)
725 return NULL;
726
727 if (dim->ids) {
728 isl_id **ids;
729 enum isl_dim_type t;
730 int off;
731 int s[3];
732 int *size = s - isl_dim_param;
733 ids = isl_calloc_array(dim->ctx, isl_id *,
734 dim->nparam + dim->n_in + dim->n_out);
735 if (!ids)
736 goto error;
737 off = 0;
738 size[isl_dim_param] = dim->nparam;
739 size[isl_dim_in] = dim->n_in;
740 size[isl_dim_out] = dim->n_out;
741 for (t = isl_dim_param; t <= isl_dim_out; ++t) {
742 if (t == dst_type) {
743 get_ids(dim, t, 0, dst_pos, ids + off);
744 off += dst_pos;
745 get_ids(dim, src_type, src_pos, n, ids + off);
746 off += n;
747 get_ids(dim, t, dst_pos, size[t] - dst_pos,
748 ids + off);
749 off += size[t] - dst_pos;
750 } else if (t == src_type) {
751 get_ids(dim, t, 0, src_pos, ids + off);
752 off += src_pos;
753 get_ids(dim, t, src_pos + n,
754 size[t] - src_pos - n, ids + off);
755 off += size[t] - src_pos - n;
756 } else {
757 get_ids(dim, t, 0, size[t], ids + off);
758 off += size[t];
759 }
760 }
761 free(dim->ids);
762 dim->ids = ids;
763 dim->n_id = dim->nparam + dim->n_in + dim->n_out;
764 }
765
766 switch (dst_type) {
767 case isl_dim_param: dim->nparam += n; break;
768 case isl_dim_in: dim->n_in += n; break;
769 case isl_dim_out: dim->n_out += n; break;
770 default: ;
771 }
772
773 switch (src_type) {
774 case isl_dim_param: dim->nparam -= n; break;
775 case isl_dim_in: dim->n_in -= n; break;
776 case isl_dim_out: dim->n_out -= n; break;
777 default: ;
778 }
779
780 if (dst_type != isl_dim_param && src_type != isl_dim_param)
781 return dim;
782
783 for (i = 0; i < 2; ++i) {
784 if (!dim->nested[i])
785 continue;
786 dim->nested[i] = isl_dim_replace(dim->nested[i],
787 isl_dim_param, dim);
788 if (!dim->nested[i])
789 goto error;
790 }
791
792 return dim;
793 error:
794 isl_dim_free(dim);
795 return NULL;
796 }
797
798 struct isl_dim *isl_dim_join(struct isl_dim *left, struct isl_dim *right)
799 {
800 struct isl_dim *dim;
801
802 if (!left || !right)
803 goto error;
804
805 isl_assert(left->ctx, match(left, isl_dim_param, right, isl_dim_param),
806 goto error);
807 isl_assert(left->ctx,
808 isl_dim_tuple_match(left, isl_dim_out, right, isl_dim_in),
809 goto error);
810
811 dim = isl_dim_alloc(left->ctx, left->nparam, left->n_in, right->n_out);
812 if (!dim)
813 goto error;
814
815 dim = copy_ids(dim, isl_dim_param, 0, left, isl_dim_param);
816 dim = copy_ids(dim, isl_dim_in, 0, left, isl_dim_in);
817 dim = copy_ids(dim, isl_dim_out, 0, right, isl_dim_out);
818
819 if (dim && left->tuple_id[0] &&
820 !(dim->tuple_id[0] = isl_id_copy(left->tuple_id[0])))
821 goto error;
822 if (dim && right->tuple_id[1] &&
823 !(dim->tuple_id[1] = isl_id_copy(right->tuple_id[1])))
824 goto error;
825 if (dim && left->nested[0] &&
826 !(dim->nested[0] = isl_dim_copy(left->nested[0])))
827 goto error;
828 if (dim && right->nested[1] &&
829 !(dim->nested[1] = isl_dim_copy(right->nested[1])))
830 goto error;
831
832 isl_dim_free(left);
833 isl_dim_free(right);
834
835 return dim;
836 error:
837 isl_dim_free(left);
838 isl_dim_free(right);
839 return NULL;
840 }
841
842 struct isl_dim *isl_dim_product(struct isl_dim *left, struct isl_dim *right)
843 {
844 isl_dim *dom1, *dom2, *nest1, *nest2;
845
846 if (!left || !right)
847 goto error;
848
849 isl_assert(left->ctx, match(left, isl_dim_param, right, isl_dim_param),
850 goto error);
851
852 dom1 = isl_dim_domain(isl_dim_copy(left));
853 dom2 = isl_dim_domain(isl_dim_copy(right));
854 nest1 = isl_dim_wrap(isl_dim_join(isl_dim_reverse(dom1), dom2));
855
856 dom1 = isl_dim_range(left);
857 dom2 = isl_dim_range(right);
858 nest2 = isl_dim_wrap(isl_dim_join(isl_dim_reverse(dom1), dom2));
859
860 return isl_dim_join(isl_dim_reverse(nest1), nest2);
861 error:
862 isl_dim_free(left);
863 isl_dim_free(right);
864 return NULL;
865 }
866
867 __isl_give isl_dim *isl_dim_range_product(__isl_take isl_dim *left,
868 __isl_take isl_dim *right)
869 {
870 isl_dim *dom, *ran1, *ran2, *nest;
871
872 if (!left || !right)
873 goto error;
874
875 isl_assert(left->ctx, match(left, isl_dim_param, right, isl_dim_param),
876 goto error);
877 if (!isl_dim_tuple_match(left, isl_dim_in, right, isl_dim_in))
878 isl_die(left->ctx, isl_error_invalid,
879 "domains need to match", goto error);
880
881 dom = isl_dim_domain(isl_dim_copy(left));
882
883 ran1 = isl_dim_range(left);
884 ran2 = isl_dim_range(right);
885 nest = isl_dim_wrap(isl_dim_join(isl_dim_reverse(ran1), ran2));
886
887 return isl_dim_join(isl_dim_reverse(dom), nest);
888 error:
889 isl_dim_free(left);
890 isl_dim_free(right);
891 return NULL;
892 }
893
894 __isl_give isl_dim *isl_dim_map_from_set(__isl_take isl_dim *dim)
895 {
896 isl_id **ids = NULL;
897
898 if (!dim)
899 return NULL;
900 isl_assert(dim->ctx, dim->n_in == 0, goto error);
901 if (dim->n_out == 0 && !isl_dim_is_named_or_nested(dim, isl_dim_out))
902 return dim;
903 dim = isl_dim_cow(dim);
904 if (!dim)
905 return NULL;
906 if (dim->ids) {
907 ids = isl_calloc_array(dim->ctx, isl_id *,
908 dim->nparam + dim->n_out + dim->n_out);
909 if (!ids)
910 goto error;
911 get_ids(dim, isl_dim_param, 0, dim->nparam, ids);
912 get_ids(dim, isl_dim_out, 0, dim->n_out, ids + dim->nparam);
913 }
914 dim->n_in = dim->n_out;
915 if (ids) {
916 free(dim->ids);
917 dim->ids = ids;
918 dim->n_id = dim->nparam + dim->n_out + dim->n_out;
919 dim = copy_ids(dim, isl_dim_out, 0, dim, isl_dim_in);
920 }
921 isl_id_free(dim->tuple_id[0]);
922 dim->tuple_id[0] = isl_id_copy(dim->tuple_id[1]);
923 isl_dim_free(dim->nested[0]);
924 dim->nested[0] = isl_dim_copy(dim->nested[1]);
925 return dim;
926 error:
927 isl_dim_free(dim);
928 return NULL;
929 }
930
931 static __isl_give isl_dim *set_ids(struct isl_dim *dim, enum isl_dim_type type,
932 unsigned first, unsigned n, __isl_take isl_id **ids)
933 {
934 int i;
935
936 for (i = 0; i < n ; ++i)
937 dim = set_id(dim, type, first + i, ids[i]);
938
939 return dim;
940 }
941
942 struct isl_dim *isl_dim_reverse(struct isl_dim *dim)
943 {
944 unsigned t;
945 isl_dim *nested;
946 isl_id **ids = NULL;
947 isl_id *id;
948
949 if (!dim)
950 return NULL;
951 if (match(dim, isl_dim_in, dim, isl_dim_out))
952 return dim;
953
954 dim = isl_dim_cow(dim);
955 if (!dim)
956 return NULL;
957
958 id = dim->tuple_id[0];
959 dim->tuple_id[0] = dim->tuple_id[1];
960 dim->tuple_id[1] = id;
961
962 nested = dim->nested[0];
963 dim->nested[0] = dim->nested[1];
964 dim->nested[1] = nested;
965
966 if (dim->ids) {
967 ids = isl_alloc_array(dim->ctx, isl_id *,
968 dim->n_in + dim->n_out);
969 if (!ids)
970 goto error;
971 get_ids(dim, isl_dim_in, 0, dim->n_in, ids);
972 get_ids(dim, isl_dim_out, 0, dim->n_out, ids + dim->n_in);
973 }
974
975 t = dim->n_in;
976 dim->n_in = dim->n_out;
977 dim->n_out = t;
978
979 if (dim->ids) {
980 dim = set_ids(dim, isl_dim_out, 0, dim->n_out, ids);
981 dim = set_ids(dim, isl_dim_in, 0, dim->n_in, ids + dim->n_out);
982 free(ids);
983 }
984
985 return dim;
986 error:
987 free(ids);
988 isl_dim_free(dim);
989 return NULL;
990 }
991
992 struct isl_dim *isl_dim_drop(struct isl_dim *dim, enum isl_dim_type type,
993 unsigned first, unsigned num)
994 {
995 int i;
996
997 if (!dim)
998 return NULL;
999
1000 if (num == 0)
1001 return isl_dim_reset(dim, type);
1002
1003 if (!valid_dim_type(type))
1004 isl_die(dim->ctx, isl_error_invalid,
1005 "cannot drop dimensions of specified type", goto error);
1006
1007 isl_assert(dim->ctx, first + num <= n(dim, type), goto error);
1008 dim = isl_dim_cow(dim);
1009 if (!dim)
1010 goto error;
1011 if (dim->ids) {
1012 dim = extend_ids(dim);
1013 if (!dim)
1014 goto error;
1015 for (i = 0; i < num; ++i)
1016 isl_id_free(get_id(dim, type, first + i));
1017 for (i = first+num; i < n(dim, type); ++i)
1018 set_id(dim, type, i - num, get_id(dim, type, i));
1019 switch (type) {
1020 case isl_dim_param:
1021 get_ids(dim, isl_dim_in, 0, dim->n_in,
1022 dim->ids + offset(dim, isl_dim_in) - num);
1023 case isl_dim_in:
1024 get_ids(dim, isl_dim_out, 0, dim->n_out,
1025 dim->ids + offset(dim, isl_dim_out) - num);
1026 default:
1027 ;
1028 }
1029 dim->n_id -= num;
1030 }
1031 switch (type) {
1032 case isl_dim_param: dim->nparam -= num; break;
1033 case isl_dim_in: dim->n_in -= num; break;
1034 case isl_dim_out: dim->n_out -= num; break;
1035 default: ;
1036 }
1037 dim = isl_dim_reset(dim, type);
1038 if (type == isl_dim_param) {
1039 if (dim && dim->nested[0] &&
1040 !(dim->nested[0] = isl_dim_drop(dim->nested[0],
1041 isl_dim_param, first, num)))
1042 goto error;
1043 if (dim && dim->nested[1] &&
1044 !(dim->nested[1] = isl_dim_drop(dim->nested[1],
1045 isl_dim_param, first, num)))
1046 goto error;
1047 }
1048 return dim;
1049 error:
1050 isl_dim_free(dim);
1051 return NULL;
1052 }
1053
1054 struct isl_dim *isl_dim_drop_inputs(struct isl_dim *dim,
1055 unsigned first, unsigned n)
1056 {
1057 if (!dim)
1058 return NULL;
1059 return isl_dim_drop(dim, isl_dim_in, first, n);
1060 }
1061
1062 struct isl_dim *isl_dim_drop_outputs(struct isl_dim *dim,
1063 unsigned first, unsigned n)
1064 {
1065 if (!dim)
1066 return NULL;
1067 return isl_dim_drop(dim, isl_dim_out, first, n);
1068 }
1069
1070 struct isl_dim *isl_dim_domain(struct isl_dim *dim)
1071 {
1072 if (!dim)
1073 return NULL;
1074 dim = isl_dim_drop_outputs(dim, 0, dim->n_out);
1075 return isl_dim_reverse(dim);
1076 }
1077
1078 __isl_give isl_dim *isl_dim_from_domain(__isl_take isl_dim *dim)
1079 {
1080 return isl_dim_reverse(dim);
1081 }
1082
1083 struct isl_dim *isl_dim_range(struct isl_dim *dim)
1084 {
1085 if (!dim)
1086 return NULL;
1087 return isl_dim_drop_inputs(dim, 0, dim->n_in);
1088 }
1089
1090 __isl_give isl_dim *isl_dim_from_range(__isl_take isl_dim *dim)
1091 {
1092 return dim;
1093 }
1094
1095 __isl_give isl_dim *isl_dim_as_set_dim(__isl_take isl_dim *dim)
1096 {
1097 dim = isl_dim_cow(dim);
1098 if (!dim)
1099 return NULL;
1100
1101 dim->n_out += dim->n_in;
1102 dim->n_in = 0;
1103 dim = isl_dim_reset(dim, isl_dim_in);
1104 dim = isl_dim_reset(dim, isl_dim_out);
1105
1106 return dim;
1107 }
1108
1109 struct isl_dim *isl_dim_underlying(struct isl_dim *dim, unsigned n_div)
1110 {
1111 int i;
1112
1113 if (!dim)
1114 return NULL;
1115 if (n_div == 0 &&
1116 dim->nparam == 0 && dim->n_in == 0 && dim->n_id == 0)
1117 return isl_dim_reset(isl_dim_reset(dim, isl_dim_in), isl_dim_out);
1118 dim = isl_dim_cow(dim);
1119 if (!dim)
1120 return NULL;
1121 dim->n_out += dim->nparam + dim->n_in + n_div;
1122 dim->nparam = 0;
1123 dim->n_in = 0;
1124
1125 for (i = 0; i < dim->n_id; ++i)
1126 isl_id_free(get_id(dim, isl_dim_out, i));
1127 dim->n_id = 0;
1128 dim = isl_dim_reset(dim, isl_dim_in);
1129 dim = isl_dim_reset(dim, isl_dim_out);
1130
1131 return dim;
1132 }
1133
1134 unsigned isl_dim_total(struct isl_dim *dim)
1135 {
1136 return dim ? dim->nparam + dim->n_in + dim->n_out : 0;
1137 }
1138
1139 int isl_dim_equal(struct isl_dim *dim1, struct isl_dim *dim2)
1140 {
1141 if (!dim1 || !dim2)
1142 return -1;
1143 return match(dim1, isl_dim_param, dim2, isl_dim_param) &&
1144 isl_dim_tuple_match(dim1, isl_dim_in, dim2, isl_dim_in) &&
1145 isl_dim_tuple_match(dim1, isl_dim_out, dim2, isl_dim_out);
1146 }
1147
1148 int isl_dim_compatible(struct isl_dim *dim1, struct isl_dim *dim2)
1149 {
1150 return dim1->nparam == dim2->nparam &&
1151 dim1->n_in + dim1->n_out == dim2->n_in + dim2->n_out;
1152 }
1153
1154 static uint32_t isl_hash_dim(uint32_t hash, __isl_keep isl_dim *dim)
1155 {
1156 int i;
1157 isl_id *id;
1158
1159 if (!dim)
1160 return hash;
1161
1162 hash = isl_hash_builtin(hash, dim->nparam);
1163 hash = isl_hash_builtin(hash, dim->n_in);
1164 hash = isl_hash_builtin(hash, dim->n_out);
1165
1166 for (i = 0; i < dim->nparam; ++i) {
1167 id = get_id(dim, isl_dim_param, i);
1168 hash = isl_hash_id(hash, id);
1169 }
1170
1171 id = tuple_id(dim, isl_dim_in);
1172 hash = isl_hash_id(hash, id);
1173 id = tuple_id(dim, isl_dim_out);
1174 hash = isl_hash_id(hash, id);
1175
1176 hash = isl_hash_dim(hash, dim->nested[0]);
1177 hash = isl_hash_dim(hash, dim->nested[1]);
1178
1179 return hash;
1180 }
1181
1182 uint32_t isl_dim_get_hash(__isl_keep isl_dim *dim)
1183 {
1184 uint32_t hash;
1185
1186 if (!dim)
1187 return 0;
1188
1189 hash = isl_hash_init();
1190 hash = isl_hash_dim(hash, dim);
1191
1192 return hash;
1193 }
1194
1195 int isl_dim_is_wrapping(__isl_keep isl_dim *dim)
1196 {
1197 if (!dim)
1198 return -1;
1199
1200 if (dim->n_in != 0 || dim->tuple_id[0] || dim->nested[0])
1201 return 0;
1202
1203 return dim->nested[1] != NULL;
1204 }
1205
1206 __isl_give isl_dim *isl_dim_wrap(__isl_take isl_dim *dim)
1207 {
1208 isl_dim *wrap;
1209
1210 if (!dim)
1211 return NULL;
1212
1213 wrap = isl_dim_alloc(dim->ctx, dim->nparam, 0, dim->n_in + dim->n_out);
1214
1215 wrap = copy_ids(wrap, isl_dim_param, 0, dim, isl_dim_param);
1216 wrap = copy_ids(wrap, isl_dim_set, 0, dim, isl_dim_in);
1217 wrap = copy_ids(wrap, isl_dim_set, dim->n_in, dim, isl_dim_out);
1218
1219 if (!wrap)
1220 goto error;
1221
1222 wrap->nested[1] = dim;
1223
1224 return wrap;
1225 error:
1226 isl_dim_free(dim);
1227 return NULL;
1228 }
1229
1230 __isl_give isl_dim *isl_dim_unwrap(__isl_take isl_dim *dim)
1231 {
1232 isl_dim *unwrap;
1233
1234 if (!dim)
1235 return NULL;
1236
1237 if (!isl_dim_is_wrapping(dim))
1238 isl_die(dim->ctx, isl_error_invalid, "not a wrapping dim",
1239 goto error);
1240
1241 unwrap = isl_dim_copy(dim->nested[1]);
1242 isl_dim_free(dim);
1243
1244 return unwrap;
1245 error:
1246 isl_dim_free(dim);
1247 return NULL;
1248 }
1249
1250 int isl_dim_is_named_or_nested(__isl_keep isl_dim *dim, enum isl_dim_type type)
1251 {
1252 if (type != isl_dim_in && type != isl_dim_out)
1253 return 0;
1254 if (!dim)
1255 return -1;
1256 if (dim->tuple_id[type - isl_dim_in])
1257 return 1;
1258 if (dim->nested[type - isl_dim_in])
1259 return 1;
1260 return 0;
1261 }
1262
1263 int isl_dim_may_be_set(__isl_keep isl_dim *dim)
1264 {
1265 if (!dim)
1266 return -1;
1267 if (isl_dim_size(dim, isl_dim_in) != 0)
1268 return 0;
1269 if (isl_dim_is_named_or_nested(dim, isl_dim_in))
1270 return 0;
1271 return 1;
1272 }
1273
1274 __isl_give isl_dim *isl_dim_reset(__isl_take isl_dim *dim,
1275 enum isl_dim_type type)
1276 {
1277 if (!isl_dim_is_named_or_nested(dim, type))
1278 return dim;
1279
1280 dim = isl_dim_cow(dim);
1281 if (!dim)
1282 return NULL;
1283
1284 isl_id_free(dim->tuple_id[type - isl_dim_in]);
1285 dim->tuple_id[type - isl_dim_in] = NULL;
1286 isl_dim_free(dim->nested[type - isl_dim_in]);
1287 dim->nested[type - isl_dim_in] = NULL;
1288
1289 return dim;
1290 }
1291
1292 __isl_give isl_dim *isl_dim_flatten(__isl_take isl_dim *dim)
1293 {
1294 if (!dim)
1295 return NULL;
1296 if (!dim->nested[0] && !dim->nested[1])
1297 return dim;
1298
1299 if (dim->nested[0])
1300 dim = isl_dim_reset(dim, isl_dim_in);
1301 if (dim && dim->nested[1])
1302 dim = isl_dim_reset(dim, isl_dim_out);
1303
1304 return dim;
1305 }
1306
1307 __isl_give isl_dim *isl_dim_flatten_range(__isl_take isl_dim *dim)
1308 {
1309 if (!dim)
1310 return NULL;
1311 if (!dim->nested[1])
1312 return dim;
1313
1314 return isl_dim_reset(dim, isl_dim_out);
1315 }
1316
1317 /* Replace the dimensions of the given type of dst by those of src.
1318 */
1319 __isl_give isl_dim *isl_dim_replace(__isl_take isl_dim *dst,
1320 enum isl_dim_type type, __isl_keep isl_dim *src)
1321 {
1322 dst = isl_dim_cow(dst);
1323
1324 if (!dst || !src)
1325 goto error;
1326
1327 dst = isl_dim_drop(dst, type, 0, isl_dim_size(dst, type));
1328 dst = isl_dim_add(dst, type, isl_dim_size(src, type));
1329 dst = copy_ids(dst, type, 0, src, type);
1330
1331 if (dst && type == isl_dim_param) {
1332 int i;
1333 for (i = 0; i <= 1; ++i) {
1334 if (!dst->nested[i])
1335 continue;
1336 dst->nested[i] = isl_dim_replace(dst->nested[i],
1337 type, src);
1338 if (!dst->nested[i])
1339 goto error;
1340 }
1341 }
1342
1343 return dst;
1344 error:
1345 isl_dim_free(dst);
1346 return NULL;
1347 }
1348
1349 /* Given a dimension specification "dim" of a set, create a dimension
1350 * specification for the lift of the set. In particular, the result
1351 * is of the form [dim -> local[..]], with n_local variables in the
1352 * range of the wrapped map.
1353 */
1354 __isl_give isl_dim *isl_dim_lift(__isl_take isl_dim *dim, unsigned n_local)
1355 {
1356 isl_dim *local_dim;
1357
1358 if (!dim)
1359 return NULL;
1360
1361 local_dim = isl_dim_dup(dim);
1362 local_dim = isl_dim_drop(local_dim, isl_dim_set, 0, dim->n_out);
1363 local_dim = isl_dim_add(local_dim, isl_dim_set, n_local);
1364 local_dim = isl_dim_set_tuple_name(local_dim, isl_dim_set, "local");
1365 dim = isl_dim_join(isl_dim_from_domain(dim),
1366 isl_dim_from_range(local_dim));
1367 dim = isl_dim_wrap(dim);
1368 dim = isl_dim_set_tuple_name(dim, isl_dim_set, "lifted");
1369
1370 return dim;
1371 }
1372
1373 int isl_dim_can_zip(__isl_keep isl_dim *dim)
1374 {
1375 if (!dim)
1376 return -1;
1377
1378 return dim->nested[0] && dim->nested[1];
1379 }
1380
1381 __isl_give isl_dim *isl_dim_zip(__isl_take isl_dim *dim)
1382 {
1383 isl_dim *dom, *ran;
1384 isl_dim *dom_dom, *dom_ran, *ran_dom, *ran_ran;
1385
1386 if (!isl_dim_can_zip(dim))
1387 isl_die(dim->ctx, isl_error_invalid, "dim cannot be zipped",
1388 goto error);
1389
1390 if (!dim)
1391 return 0;
1392 dom = isl_dim_unwrap(isl_dim_domain(isl_dim_copy(dim)));
1393 ran = isl_dim_unwrap(isl_dim_range(dim));
1394 dom_dom = isl_dim_domain(isl_dim_copy(dom));
1395 dom_ran = isl_dim_range(dom);
1396 ran_dom = isl_dim_domain(isl_dim_copy(ran));
1397 ran_ran = isl_dim_range(ran);
1398 dom = isl_dim_join(isl_dim_from_domain(dom_dom),
1399 isl_dim_from_range(ran_dom));
1400 ran = isl_dim_join(isl_dim_from_domain(dom_ran),
1401 isl_dim_from_range(ran_ran));
1402 return isl_dim_join(isl_dim_from_domain(isl_dim_wrap(dom)),
1403 isl_dim_from_range(isl_dim_wrap(ran)));
1404 error:
1405 isl_dim_free(dim);
1406 return NULL;
1407 }
1408
1409 int isl_dim_has_named_params(__isl_keep isl_dim *dim)
1410 {
1411 int i;
1412 unsigned off;
1413
1414 if (!dim)
1415 return -1;
1416 if (dim->nparam == 0)
1417 return 1;
1418 off = isl_dim_offset(dim, isl_dim_param);
1419 if (off + dim->nparam > dim->n_id)
1420 return 0;
1421 for (i = 0; i < dim->nparam; ++i)
1422 if (!dim->ids[off + i])
1423 return 0;
1424 return 1;
1425 }
1426
1427 /* Align the initial parameters of dim1 to match the order in dim2.
1428 */
1429 __isl_give isl_dim *isl_dim_align_params(__isl_take isl_dim *dim1,
1430 __isl_take isl_dim *dim2)
1431 {
1432 isl_reordering *exp;
1433
1434 if (!isl_dim_has_named_params(dim1) || !isl_dim_has_named_params(dim2))
1435 isl_die(isl_dim_get_ctx(dim1), isl_error_invalid,
1436 "parameter alignment requires named parameters",
1437 goto error);
1438
1439 exp = isl_parameter_alignment_reordering(dim1, dim2);
1440 isl_dim_free(dim1);
1441 isl_dim_free(dim2);
1442 if (!exp)
1443 return NULL;
1444 dim1 = isl_dim_copy(exp->dim);
1445 isl_reordering_free(exp);
1446 return dim1;
1447 error:
1448 isl_dim_free(dim1);
1449 isl_dim_free(dim2);
1450 return NULL;
1451 }
Integer set library