2 * Copyright 2008-2009 Katholieke Universiteit Leuven
4 * Use of this software is governed by the GNU LGPLv2.1 license
6 * Written by Sven Verdoolaege, K.U.Leuven, Departement
7 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
14 struct isl_dim *isl_dim_alloc(struct isl_ctx *ctx,
15 unsigned nparam, unsigned n_in, unsigned n_out)
19 dim = isl_alloc_type(ctx, struct isl_dim);
30 dim->tuple_name[0] = NULL;
31 dim->tuple_name[1] = NULL;
39 struct isl_dim *isl_dim_set_alloc(struct isl_ctx *ctx,
40 unsigned nparam, unsigned dim)
42 return isl_dim_alloc(ctx, nparam, 0, dim);
45 static unsigned global_pos(struct isl_dim *dim,
46 enum isl_dim_type type, unsigned pos)
48 struct isl_ctx *ctx = dim->ctx;
52 isl_assert(ctx, pos < dim->nparam, return isl_dim_total(dim));
55 isl_assert(ctx, pos < dim->n_in, return isl_dim_total(dim));
56 return pos + dim->nparam;
58 isl_assert(ctx, pos < dim->n_out, return isl_dim_total(dim));
59 return pos + dim->nparam + dim->n_in;
61 isl_assert(ctx, 0, return isl_dim_total(dim));
63 return isl_dim_total(dim);
66 /* Extend length of names array to the total number of dimensions.
68 static __isl_give isl_dim *extend_names(__isl_take isl_dim *dim)
70 struct isl_name **names;
73 if (isl_dim_total(dim) <= dim->n_name)
77 dim->names = isl_calloc_array(dim->ctx,
78 struct isl_name *, isl_dim_total(dim));
82 names = isl_realloc_array(dim->ctx, dim->names,
83 struct isl_name *, isl_dim_total(dim));
87 for (i = dim->n_name; i < isl_dim_total(dim); ++i)
91 dim->n_name = isl_dim_total(dim);
99 static struct isl_dim *set_name(struct isl_dim *dim,
100 enum isl_dim_type type, unsigned pos,
101 struct isl_name *name)
103 struct isl_ctx *ctx = dim->ctx;
104 dim = isl_dim_cow(dim);
109 pos = global_pos(dim, type, pos);
110 isl_assert(ctx, pos != isl_dim_total(dim), goto error);
112 if (pos >= dim->n_name) {
115 dim = extend_names(dim);
120 dim->names[pos] = name;
124 isl_name_free(ctx, name);
129 static struct isl_name *get_name(struct isl_dim *dim,
130 enum isl_dim_type type, unsigned pos)
135 pos = global_pos(dim, type, pos);
136 if (pos == isl_dim_total(dim))
138 if (pos >= dim->n_name)
140 return dim->names[pos];
143 static unsigned offset(struct isl_dim *dim, enum isl_dim_type type)
146 case isl_dim_param: return 0;
147 case isl_dim_in: return dim->nparam;
148 case isl_dim_out: return dim->nparam + dim->n_in;
153 static unsigned n(struct isl_dim *dim, enum isl_dim_type type)
156 case isl_dim_param: return dim->nparam;
157 case isl_dim_in: return dim->n_in;
158 case isl_dim_out: return dim->n_out;
163 unsigned isl_dim_size(struct isl_dim *dim, enum isl_dim_type type)
170 unsigned isl_dim_offset(__isl_keep isl_dim *dim, enum isl_dim_type type)
174 return offset(dim, type);
177 static struct isl_dim *copy_names(struct isl_dim *dst,
178 enum isl_dim_type dst_type, unsigned offset, struct isl_dim *src,
179 enum isl_dim_type src_type)
182 struct isl_name *name;
187 for (i = 0; i < n(src, src_type); ++i) {
188 name = get_name(src, src_type, i);
191 dst = set_name(dst, dst_type, offset + i,
192 isl_name_copy(dst->ctx, name));
199 struct isl_dim *isl_dim_dup(struct isl_dim *dim)
204 dup = isl_dim_alloc(dim->ctx, dim->nparam, dim->n_in, dim->n_out);
205 if (dim->tuple_name[0] &&
206 !(dup->tuple_name[0] = isl_name_copy(dim->ctx, dim->tuple_name[0])))
208 if (dim->tuple_name[1] &&
209 !(dup->tuple_name[1] = isl_name_copy(dim->ctx, dim->tuple_name[1])))
213 dup = copy_names(dup, isl_dim_param, 0, dim, isl_dim_param);
214 dup = copy_names(dup, isl_dim_in, 0, dim, isl_dim_in);
215 dup = copy_names(dup, isl_dim_out, 0, dim, isl_dim_out);
222 struct isl_dim *isl_dim_cow(struct isl_dim *dim)
230 return isl_dim_dup(dim);
233 struct isl_dim *isl_dim_copy(struct isl_dim *dim)
242 void isl_dim_free(struct isl_dim *dim)
252 isl_name_free(dim->ctx, dim->tuple_name[0]);
253 isl_name_free(dim->ctx, dim->tuple_name[1]);
255 for (i = 0; i < dim->n_name; ++i)
256 isl_name_free(dim->ctx, dim->names[i]);
258 isl_ctx_deref(dim->ctx);
263 static int name_ok(isl_ctx *ctx, const char *s)
268 dummy = strtol(s, &p, 0);
270 isl_die(ctx, isl_error_invalid, "name looks like a number",
276 __isl_give isl_dim *isl_dim_set_tuple_name(__isl_take isl_dim *dim,
277 enum isl_dim_type type, const char *s)
279 struct isl_name *name;
281 dim = isl_dim_cow(dim);
284 if (type != isl_dim_in && type != isl_dim_out)
285 isl_die(dim->ctx, isl_error_invalid,
286 "only input, output and set tuples can have names",
288 if (!name_ok(dim->ctx, s))
290 name = isl_name_get(dim->ctx, s);
294 isl_name_free(dim->ctx, dim->tuple_name[type - isl_dim_in]);
295 dim->tuple_name[type - isl_dim_in] = name;
303 const char *isl_dim_get_tuple_name(__isl_keep isl_dim *dim,
304 enum isl_dim_type type)
306 struct isl_name *name;
309 if (type != isl_dim_in && type != isl_dim_out)
311 name = dim->tuple_name[type - isl_dim_in];
312 return name ? name->name : NULL;
315 struct isl_dim *isl_dim_set_name(struct isl_dim *dim,
316 enum isl_dim_type type, unsigned pos,
319 struct isl_name *name;
323 if (!name_ok(dim->ctx, s))
325 name = isl_name_get(dim->ctx, s);
328 return set_name(dim, type, pos, name);
334 const char *isl_dim_get_name(struct isl_dim *dim,
335 enum isl_dim_type type, unsigned pos)
337 struct isl_name *name = get_name(dim, type, pos);
338 return name ? name->name : NULL;
341 static struct isl_name *tuple_name(__isl_keep isl_dim *dim,
342 enum isl_dim_type type)
346 if (type == isl_dim_in)
347 return dim->tuple_name[0];
348 if (type == isl_dim_out)
349 return dim->tuple_name[1];
353 int isl_dim_tuple_match(__isl_keep isl_dim *dim1, enum isl_dim_type dim1_type,
354 __isl_keep isl_dim *dim2, enum isl_dim_type dim2_type)
356 struct isl_name *name1, *name2;
358 if (n(dim1, dim1_type) != n(dim2, dim2_type))
360 name1 = tuple_name(dim1, dim1_type);
361 name2 = tuple_name(dim2, dim2_type);
364 if (name1 && name1->name != name2->name)
369 static int match(struct isl_dim *dim1, enum isl_dim_type dim1_type,
370 struct isl_dim *dim2, enum isl_dim_type dim2_type)
374 if (!isl_dim_tuple_match(dim1, dim1_type, dim2, dim2_type))
377 if (!dim1->names && !dim2->names)
380 for (i = 0; i < n(dim1, dim1_type); ++i) {
381 if (get_name(dim1, dim1_type, i) !=
382 get_name(dim2, dim2_type, i))
388 int isl_dim_match(struct isl_dim *dim1, enum isl_dim_type dim1_type,
389 struct isl_dim *dim2, enum isl_dim_type dim2_type)
391 return match(dim1, dim1_type, dim2, dim2_type);
394 static void get_names(struct isl_dim *dim, enum isl_dim_type type,
395 unsigned first, unsigned n, struct isl_name **names)
399 for (i = 0; i < n ; ++i)
400 names[i] = get_name(dim, type, first+i);
403 struct isl_dim *isl_dim_extend(struct isl_dim *dim,
404 unsigned nparam, unsigned n_in, unsigned n_out)
406 struct isl_name **names = NULL;
410 if (dim->nparam == nparam && dim->n_in == n_in && dim->n_out == n_out)
413 isl_assert(dim->ctx, dim->nparam <= nparam, goto error);
414 isl_assert(dim->ctx, dim->n_in <= n_in, goto error);
415 isl_assert(dim->ctx, dim->n_out <= n_out, goto error);
417 dim = isl_dim_cow(dim);
420 names = isl_calloc_array(dim->ctx, struct isl_name *,
421 nparam + n_in + n_out);
424 get_names(dim, isl_dim_param, 0, dim->nparam, names);
425 get_names(dim, isl_dim_in, 0, dim->n_in, names + nparam);
426 get_names(dim, isl_dim_out, 0, dim->n_out,
427 names + nparam + n_in);
430 dim->n_name = nparam + n_in + n_out;
432 dim->nparam = nparam;
443 struct isl_dim *isl_dim_add(struct isl_dim *dim, enum isl_dim_type type,
448 if ((type == isl_dim_in || type == isl_dim_out) &&
449 dim->tuple_name[type - isl_dim_in]) {
450 dim = isl_dim_cow(dim);
453 isl_name_free(dim->ctx, dim->tuple_name[type - isl_dim_in]);
454 dim->tuple_name[type - isl_dim_in] = NULL;
458 return isl_dim_extend(dim,
459 dim->nparam + n, dim->n_in, dim->n_out);
461 return isl_dim_extend(dim,
462 dim->nparam, dim->n_in + n, dim->n_out);
464 return isl_dim_extend(dim,
465 dim->nparam, dim->n_in, dim->n_out + n);
470 __isl_give isl_dim *isl_dim_insert(__isl_take isl_dim *dim,
471 enum isl_dim_type type, unsigned pos, unsigned n)
473 struct isl_name **names = NULL;
477 if (n == 0 && !isl_dim_get_tuple_name(dim, type))
480 isl_assert(dim->ctx, pos <= isl_dim_size(dim, type), goto error);
482 dim = isl_dim_cow(dim);
490 names = isl_calloc_array(dim->ctx, struct isl_name *,
491 dim->nparam + dim->n_in + dim->n_out + n);
495 size[isl_dim_param] = dim->nparam;
496 size[isl_dim_in] = dim->n_in;
497 size[isl_dim_out] = dim->n_out;
498 for (t = isl_dim_param; t <= isl_dim_out; ++t) {
500 get_names(dim, t, 0, size[t], names + off);
503 get_names(dim, t, 0, pos, names + off);
505 get_names(dim, t, pos, size[t]-pos, names+off);
506 off += size[t] - pos;
511 dim->n_name = dim->nparam + dim->n_in + dim->n_out + n;
514 case isl_dim_param: dim->nparam += n; break;
515 case isl_dim_in: dim->n_in += n; break;
516 case isl_dim_out: dim->n_out += n; break;
518 if (type == isl_dim_in || type == isl_dim_out) {
519 isl_name_free(dim->ctx, dim->tuple_name[type - isl_dim_in]);
520 dim->tuple_name[type - isl_dim_in] = NULL;
529 __isl_give isl_dim *isl_dim_move(__isl_take isl_dim *dim,
530 enum isl_dim_type dst_type, unsigned dst_pos,
531 enum isl_dim_type src_type, unsigned src_pos, unsigned n)
538 isl_assert(dim->ctx, src_pos + n <= isl_dim_size(dim, src_type),
541 if (dst_type == src_type && dst_pos == src_pos)
544 isl_assert(dim->ctx, dst_type != src_type, goto error);
546 dim = isl_dim_cow(dim);
551 struct isl_name **names;
555 names = isl_calloc_array(dim->ctx, struct isl_name *,
556 dim->nparam + dim->n_in + dim->n_out);
560 size[isl_dim_param] = dim->nparam;
561 size[isl_dim_in] = dim->n_in;
562 size[isl_dim_out] = dim->n_out;
563 for (t = isl_dim_param; t <= isl_dim_out; ++t) {
565 get_names(dim, t, 0, dst_pos, names + off);
567 get_names(dim, src_type, src_pos, n, names+off);
569 get_names(dim, t, dst_pos, size[t] - dst_pos,
571 off += size[t] - dst_pos;
572 } else if (t == src_type) {
573 get_names(dim, t, 0, src_pos, names + off);
575 get_names(dim, t, src_pos + n,
576 size[t] - src_pos - n, names + off);
577 off += size[t] - src_pos - n;
579 get_names(dim, t, 0, size[t], names + off);
585 dim->n_name = dim->nparam + dim->n_in + dim->n_out;
589 case isl_dim_param: dim->nparam += n; break;
590 case isl_dim_in: dim->n_in += n; break;
591 case isl_dim_out: dim->n_out += n; break;
595 case isl_dim_param: dim->nparam -= n; break;
596 case isl_dim_in: dim->n_in -= n; break;
597 case isl_dim_out: dim->n_out -= n; break;
606 struct isl_dim *isl_dim_join(struct isl_dim *left, struct isl_dim *right)
613 isl_assert(left->ctx, match(left, isl_dim_param, right, isl_dim_param),
615 isl_assert(left->ctx,
616 isl_dim_tuple_match(left, isl_dim_out, right, isl_dim_in),
619 dim = isl_dim_alloc(left->ctx, left->nparam, left->n_in, right->n_out);
623 dim = copy_names(dim, isl_dim_param, 0, left, isl_dim_param);
624 dim = copy_names(dim, isl_dim_in, 0, left, isl_dim_in);
625 dim = copy_names(dim, isl_dim_out, 0, right, isl_dim_out);
627 if (dim && left->tuple_name[0] &&
628 !(dim->tuple_name[0] = isl_name_copy(dim->ctx, left->tuple_name[0])))
630 if (dim && right->tuple_name[1] &&
631 !(dim->tuple_name[1] = isl_name_copy(dim->ctx, right->tuple_name[1])))
644 struct isl_dim *isl_dim_product(struct isl_dim *left, struct isl_dim *right)
651 isl_assert(left->ctx, match(left, isl_dim_param, right, isl_dim_param),
654 dim = isl_dim_alloc(left->ctx, left->nparam,
655 left->n_in + right->n_in, left->n_out + right->n_out);
659 dim = copy_names(dim, isl_dim_param, 0, left, isl_dim_param);
660 dim = copy_names(dim, isl_dim_in, 0, left, isl_dim_in);
661 dim = copy_names(dim, isl_dim_in, left->n_in, right, isl_dim_in);
662 dim = copy_names(dim, isl_dim_out, 0, left, isl_dim_out);
663 dim = copy_names(dim, isl_dim_out, left->n_out, right, isl_dim_out);
675 struct isl_dim *isl_dim_map(struct isl_dim *dim)
677 struct isl_name **names = NULL;
681 isl_assert(dim->ctx, dim->n_in == 0, goto error);
682 if (dim->n_out == 0 && !dim->tuple_name[1])
684 dim = isl_dim_cow(dim);
688 names = isl_calloc_array(dim->ctx, struct isl_name *,
689 dim->nparam + dim->n_out + dim->n_out);
692 get_names(dim, isl_dim_param, 0, dim->nparam, names);
693 get_names(dim, isl_dim_out, 0, dim->n_out, names + dim->nparam);
695 dim->n_in = dim->n_out;
699 dim->n_name = dim->nparam + dim->n_out + dim->n_out;
700 dim = copy_names(dim, isl_dim_out, 0, dim, isl_dim_in);
702 isl_name_free(dim->ctx, dim->tuple_name[0]);
703 dim->tuple_name[0] = isl_name_copy(dim->ctx, dim->tuple_name[1]);
710 static struct isl_dim *set_names(struct isl_dim *dim, enum isl_dim_type type,
711 unsigned first, unsigned n, struct isl_name **names)
715 for (i = 0; i < n ; ++i)
716 dim = set_name(dim, type, first+i, names[i]);
721 struct isl_dim *isl_dim_reverse(struct isl_dim *dim)
724 struct isl_name **names = NULL;
725 struct isl_name *name;
729 if (match(dim, isl_dim_in, dim, isl_dim_out))
732 dim = isl_dim_cow(dim);
736 name = dim->tuple_name[0];
737 dim->tuple_name[0] = dim->tuple_name[1];
738 dim->tuple_name[1] = name;
741 names = isl_alloc_array(dim->ctx, struct isl_name *,
742 dim->n_in + dim->n_out);
745 get_names(dim, isl_dim_in, 0, dim->n_in, names);
746 get_names(dim, isl_dim_out, 0, dim->n_out, names + dim->n_in);
750 dim->n_in = dim->n_out;
754 dim = set_names(dim, isl_dim_out, 0, dim->n_out, names);
755 dim = set_names(dim, isl_dim_in, 0, dim->n_in, names + dim->n_out);
766 struct isl_dim *isl_dim_drop(struct isl_dim *dim, enum isl_dim_type type,
767 unsigned first, unsigned num)
777 isl_assert(dim->ctx, first + num <= n(dim, type), goto error);
778 dim = isl_dim_cow(dim);
782 dim = extend_names(dim);
785 for (i = 0; i < num; ++i)
786 isl_name_free(dim->ctx, get_name(dim, type, first+i));
787 for (i = first+num; i < n(dim, type); ++i)
788 set_name(dim, type, i - num, get_name(dim, type, i));
791 get_names(dim, isl_dim_in, 0, dim->n_in,
792 dim->names + offset(dim, isl_dim_in) - num);
794 get_names(dim, isl_dim_out, 0, dim->n_out,
795 dim->names + offset(dim, isl_dim_out) - num);
802 case isl_dim_param: dim->nparam -= num; break;
803 case isl_dim_in: dim->n_in -= num; break;
804 case isl_dim_out: dim->n_out -= num; break;
806 if (type == isl_dim_in || type == isl_dim_out) {
807 isl_name_free(dim->ctx, dim->tuple_name[type - isl_dim_in]);
808 dim->tuple_name[type - isl_dim_in] = NULL;
816 struct isl_dim *isl_dim_drop_inputs(struct isl_dim *dim,
817 unsigned first, unsigned n)
821 return isl_dim_drop(dim, isl_dim_in, first, n);
824 struct isl_dim *isl_dim_drop_outputs(struct isl_dim *dim,
825 unsigned first, unsigned n)
829 return isl_dim_drop(dim, isl_dim_out, first, n);
832 struct isl_dim *isl_dim_domain(struct isl_dim *dim)
836 dim = isl_dim_drop_outputs(dim, 0, dim->n_out);
837 return isl_dim_reverse(dim);
840 struct isl_dim *isl_dim_range(struct isl_dim *dim)
844 return isl_dim_drop_inputs(dim, 0, dim->n_in);
847 __isl_give isl_dim *isl_dim_as_set_dim(__isl_take isl_dim *dim)
849 dim = isl_dim_cow(dim);
853 dim->n_out += dim->n_in;
855 isl_name_free(dim->ctx, dim->tuple_name[0]);
856 isl_name_free(dim->ctx, dim->tuple_name[1]);
857 dim->tuple_name[0] = NULL;
858 dim->tuple_name[1] = NULL;
863 struct isl_dim *isl_dim_underlying(struct isl_dim *dim, unsigned n_div)
870 dim->nparam == 0 && dim->n_in == 0 && dim->n_name == 0 &&
873 dim = isl_dim_cow(dim);
876 dim->n_out += dim->nparam + dim->n_in + n_div;
880 for (i = 0; i < dim->n_name; ++i)
881 isl_name_free(dim->ctx, get_name(dim, isl_dim_out, i));
883 isl_name_free(dim->ctx, dim->tuple_name[0]);
884 isl_name_free(dim->ctx, dim->tuple_name[1]);
885 dim->tuple_name[0] = NULL;
886 dim->tuple_name[1] = NULL;
891 unsigned isl_dim_total(struct isl_dim *dim)
893 return dim->nparam + dim->n_in + dim->n_out;
896 int isl_dim_equal(struct isl_dim *dim1, struct isl_dim *dim2)
898 return match(dim1, isl_dim_param, dim2, isl_dim_param) &&
899 isl_dim_tuple_match(dim1, isl_dim_in, dim2, isl_dim_in) &&
900 isl_dim_tuple_match(dim1, isl_dim_out, dim2, isl_dim_out);
903 int isl_dim_compatible(struct isl_dim *dim1, struct isl_dim *dim2)
905 return dim1->nparam == dim2->nparam &&
906 dim1->n_in + dim1->n_out == dim2->n_in + dim2->n_out;