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
11 #include <isl_dim_private.h>
14 isl_ctx *isl_dim_get_ctx(__isl_keep isl_dim *dim)
16 return dim ? dim->ctx : NULL;
19 struct isl_dim *isl_dim_alloc(struct isl_ctx *ctx,
20 unsigned nparam, unsigned n_in, unsigned n_out)
24 dim = isl_alloc_type(ctx, struct isl_dim);
35 dim->tuple_name[0] = NULL;
36 dim->tuple_name[1] = NULL;
44 struct isl_dim *isl_dim_set_alloc(struct isl_ctx *ctx,
45 unsigned nparam, unsigned dim)
47 return isl_dim_alloc(ctx, nparam, 0, dim);
50 static unsigned global_pos(struct isl_dim *dim,
51 enum isl_dim_type type, unsigned pos)
53 struct isl_ctx *ctx = dim->ctx;
57 isl_assert(ctx, pos < dim->nparam, return isl_dim_total(dim));
60 isl_assert(ctx, pos < dim->n_in, return isl_dim_total(dim));
61 return pos + dim->nparam;
63 isl_assert(ctx, pos < dim->n_out, return isl_dim_total(dim));
64 return pos + dim->nparam + dim->n_in;
66 isl_assert(ctx, 0, return isl_dim_total(dim));
68 return isl_dim_total(dim);
71 /* Extend length of names array to the total number of dimensions.
73 static __isl_give isl_dim *extend_names(__isl_take isl_dim *dim)
75 struct isl_name **names;
78 if (isl_dim_total(dim) <= dim->n_name)
82 dim->names = isl_calloc_array(dim->ctx,
83 struct isl_name *, isl_dim_total(dim));
87 names = isl_realloc_array(dim->ctx, dim->names,
88 struct isl_name *, isl_dim_total(dim));
92 for (i = dim->n_name; i < isl_dim_total(dim); ++i)
96 dim->n_name = isl_dim_total(dim);
104 static struct isl_dim *set_name(struct isl_dim *dim,
105 enum isl_dim_type type, unsigned pos,
106 struct isl_name *name)
108 struct isl_ctx *ctx = dim->ctx;
109 dim = isl_dim_cow(dim);
114 pos = global_pos(dim, type, pos);
115 isl_assert(ctx, pos != isl_dim_total(dim), goto error);
117 if (pos >= dim->n_name) {
120 dim = extend_names(dim);
125 dim->names[pos] = name;
129 isl_name_free(ctx, name);
134 static struct isl_name *get_name(struct isl_dim *dim,
135 enum isl_dim_type type, unsigned pos)
140 pos = global_pos(dim, type, pos);
141 if (pos == isl_dim_total(dim))
143 if (pos >= dim->n_name)
145 return dim->names[pos];
148 static unsigned offset(struct isl_dim *dim, enum isl_dim_type type)
151 case isl_dim_param: return 0;
152 case isl_dim_in: return dim->nparam;
153 case isl_dim_out: return dim->nparam + dim->n_in;
158 static unsigned n(struct isl_dim *dim, enum isl_dim_type type)
161 case isl_dim_param: return dim->nparam;
162 case isl_dim_in: return dim->n_in;
163 case isl_dim_out: return dim->n_out;
168 unsigned isl_dim_size(struct isl_dim *dim, enum isl_dim_type type)
175 unsigned isl_dim_offset(__isl_keep isl_dim *dim, enum isl_dim_type type)
179 return offset(dim, type);
182 static struct isl_dim *copy_names(struct isl_dim *dst,
183 enum isl_dim_type dst_type, unsigned offset, struct isl_dim *src,
184 enum isl_dim_type src_type)
187 struct isl_name *name;
192 for (i = 0; i < n(src, src_type); ++i) {
193 name = get_name(src, src_type, i);
196 dst = set_name(dst, dst_type, offset + i,
197 isl_name_copy(dst->ctx, name));
204 struct isl_dim *isl_dim_dup(struct isl_dim *dim)
209 dup = isl_dim_alloc(dim->ctx, dim->nparam, dim->n_in, dim->n_out);
210 if (dim->tuple_name[0] &&
211 !(dup->tuple_name[0] = isl_name_copy(dim->ctx, dim->tuple_name[0])))
213 if (dim->tuple_name[1] &&
214 !(dup->tuple_name[1] = isl_name_copy(dim->ctx, dim->tuple_name[1])))
218 dup = copy_names(dup, isl_dim_param, 0, dim, isl_dim_param);
219 dup = copy_names(dup, isl_dim_in, 0, dim, isl_dim_in);
220 dup = copy_names(dup, isl_dim_out, 0, dim, isl_dim_out);
227 struct isl_dim *isl_dim_cow(struct isl_dim *dim)
235 return isl_dim_dup(dim);
238 struct isl_dim *isl_dim_copy(struct isl_dim *dim)
247 void isl_dim_free(struct isl_dim *dim)
257 isl_name_free(dim->ctx, dim->tuple_name[0]);
258 isl_name_free(dim->ctx, dim->tuple_name[1]);
260 for (i = 0; i < dim->n_name; ++i)
261 isl_name_free(dim->ctx, dim->names[i]);
263 isl_ctx_deref(dim->ctx);
268 static int name_ok(isl_ctx *ctx, const char *s)
273 dummy = strtol(s, &p, 0);
275 isl_die(ctx, isl_error_invalid, "name looks like a number",
281 __isl_give isl_dim *isl_dim_set_tuple_name(__isl_take isl_dim *dim,
282 enum isl_dim_type type, const char *s)
284 struct isl_name *name;
286 dim = isl_dim_cow(dim);
289 if (type != isl_dim_in && type != isl_dim_out)
290 isl_die(dim->ctx, isl_error_invalid,
291 "only input, output and set tuples can have names",
296 if (!name_ok(dim->ctx, s))
298 name = isl_name_get(dim->ctx, s);
303 isl_name_free(dim->ctx, dim->tuple_name[type - isl_dim_in]);
304 dim->tuple_name[type - isl_dim_in] = name;
312 const char *isl_dim_get_tuple_name(__isl_keep isl_dim *dim,
313 enum isl_dim_type type)
315 struct isl_name *name;
318 if (type != isl_dim_in && type != isl_dim_out)
320 name = dim->tuple_name[type - isl_dim_in];
321 return name ? name->name : NULL;
324 struct isl_dim *isl_dim_set_name(struct isl_dim *dim,
325 enum isl_dim_type type, unsigned pos,
328 struct isl_name *name;
332 if (!name_ok(dim->ctx, s))
334 name = isl_name_get(dim->ctx, s);
337 return set_name(dim, type, pos, name);
343 const char *isl_dim_get_name(struct isl_dim *dim,
344 enum isl_dim_type type, unsigned pos)
346 struct isl_name *name = get_name(dim, type, pos);
347 return name ? name->name : NULL;
350 static struct isl_name *tuple_name(__isl_keep isl_dim *dim,
351 enum isl_dim_type type)
355 if (type == isl_dim_in)
356 return dim->tuple_name[0];
357 if (type == isl_dim_out)
358 return dim->tuple_name[1];
362 int isl_dim_tuple_match(__isl_keep isl_dim *dim1, enum isl_dim_type dim1_type,
363 __isl_keep isl_dim *dim2, enum isl_dim_type dim2_type)
365 struct isl_name *name1, *name2;
367 if (n(dim1, dim1_type) != n(dim2, dim2_type))
369 name1 = tuple_name(dim1, dim1_type);
370 name2 = tuple_name(dim2, dim2_type);
373 if (name1 && name1->name != name2->name)
378 static int match(struct isl_dim *dim1, enum isl_dim_type dim1_type,
379 struct isl_dim *dim2, enum isl_dim_type dim2_type)
383 if (!isl_dim_tuple_match(dim1, dim1_type, dim2, dim2_type))
386 if (!dim1->names && !dim2->names)
389 for (i = 0; i < n(dim1, dim1_type); ++i) {
390 if (get_name(dim1, dim1_type, i) !=
391 get_name(dim2, dim2_type, i))
397 int isl_dim_match(struct isl_dim *dim1, enum isl_dim_type dim1_type,
398 struct isl_dim *dim2, enum isl_dim_type dim2_type)
400 return match(dim1, dim1_type, dim2, dim2_type);
403 static void get_names(struct isl_dim *dim, enum isl_dim_type type,
404 unsigned first, unsigned n, struct isl_name **names)
408 for (i = 0; i < n ; ++i)
409 names[i] = get_name(dim, type, first+i);
412 struct isl_dim *isl_dim_extend(struct isl_dim *dim,
413 unsigned nparam, unsigned n_in, unsigned n_out)
415 struct isl_name **names = NULL;
419 if (dim->nparam == nparam && dim->n_in == n_in && dim->n_out == n_out)
422 isl_assert(dim->ctx, dim->nparam <= nparam, goto error);
423 isl_assert(dim->ctx, dim->n_in <= n_in, goto error);
424 isl_assert(dim->ctx, dim->n_out <= n_out, goto error);
426 dim = isl_dim_cow(dim);
429 names = isl_calloc_array(dim->ctx, struct isl_name *,
430 nparam + n_in + n_out);
433 get_names(dim, isl_dim_param, 0, dim->nparam, names);
434 get_names(dim, isl_dim_in, 0, dim->n_in, names + nparam);
435 get_names(dim, isl_dim_out, 0, dim->n_out,
436 names + nparam + n_in);
439 dim->n_name = nparam + n_in + n_out;
441 dim->nparam = nparam;
452 struct isl_dim *isl_dim_add(struct isl_dim *dim, enum isl_dim_type type,
457 if ((type == isl_dim_in || type == isl_dim_out) &&
458 dim->tuple_name[type - isl_dim_in]) {
459 dim = isl_dim_cow(dim);
462 isl_name_free(dim->ctx, dim->tuple_name[type - isl_dim_in]);
463 dim->tuple_name[type - isl_dim_in] = NULL;
467 return isl_dim_extend(dim,
468 dim->nparam + n, dim->n_in, dim->n_out);
470 return isl_dim_extend(dim,
471 dim->nparam, dim->n_in + n, dim->n_out);
473 return isl_dim_extend(dim,
474 dim->nparam, dim->n_in, dim->n_out + n);
479 __isl_give isl_dim *isl_dim_insert(__isl_take isl_dim *dim,
480 enum isl_dim_type type, unsigned pos, unsigned n)
482 struct isl_name **names = NULL;
486 if (n == 0 && !isl_dim_get_tuple_name(dim, type))
489 isl_assert(dim->ctx, pos <= isl_dim_size(dim, type), goto error);
491 dim = isl_dim_cow(dim);
499 names = isl_calloc_array(dim->ctx, struct isl_name *,
500 dim->nparam + dim->n_in + dim->n_out + n);
504 size[isl_dim_param] = dim->nparam;
505 size[isl_dim_in] = dim->n_in;
506 size[isl_dim_out] = dim->n_out;
507 for (t = isl_dim_param; t <= isl_dim_out; ++t) {
509 get_names(dim, t, 0, size[t], names + off);
512 get_names(dim, t, 0, pos, names + off);
514 get_names(dim, t, pos, size[t]-pos, names+off);
515 off += size[t] - pos;
520 dim->n_name = dim->nparam + dim->n_in + dim->n_out + n;
523 case isl_dim_param: dim->nparam += n; break;
524 case isl_dim_in: dim->n_in += n; break;
525 case isl_dim_out: dim->n_out += n; break;
527 if (type == isl_dim_in || type == isl_dim_out) {
528 isl_name_free(dim->ctx, dim->tuple_name[type - isl_dim_in]);
529 dim->tuple_name[type - isl_dim_in] = NULL;
538 __isl_give isl_dim *isl_dim_move(__isl_take isl_dim *dim,
539 enum isl_dim_type dst_type, unsigned dst_pos,
540 enum isl_dim_type src_type, unsigned src_pos, unsigned n)
547 isl_assert(dim->ctx, src_pos + n <= isl_dim_size(dim, src_type),
550 if (dst_type == src_type && dst_pos == src_pos)
553 isl_assert(dim->ctx, dst_type != src_type, goto error);
555 dim = isl_dim_cow(dim);
560 struct isl_name **names;
564 names = isl_calloc_array(dim->ctx, struct isl_name *,
565 dim->nparam + dim->n_in + dim->n_out);
569 size[isl_dim_param] = dim->nparam;
570 size[isl_dim_in] = dim->n_in;
571 size[isl_dim_out] = dim->n_out;
572 for (t = isl_dim_param; t <= isl_dim_out; ++t) {
574 get_names(dim, t, 0, dst_pos, names + off);
576 get_names(dim, src_type, src_pos, n, names+off);
578 get_names(dim, t, dst_pos, size[t] - dst_pos,
580 off += size[t] - dst_pos;
581 } else if (t == src_type) {
582 get_names(dim, t, 0, src_pos, names + off);
584 get_names(dim, t, src_pos + n,
585 size[t] - src_pos - n, names + off);
586 off += size[t] - src_pos - n;
588 get_names(dim, t, 0, size[t], names + off);
594 dim->n_name = dim->nparam + dim->n_in + dim->n_out;
598 case isl_dim_param: dim->nparam += n; break;
599 case isl_dim_in: dim->n_in += n; break;
600 case isl_dim_out: dim->n_out += n; break;
604 case isl_dim_param: dim->nparam -= n; break;
605 case isl_dim_in: dim->n_in -= n; break;
606 case isl_dim_out: dim->n_out -= n; break;
615 struct isl_dim *isl_dim_join(struct isl_dim *left, struct isl_dim *right)
622 isl_assert(left->ctx, match(left, isl_dim_param, right, isl_dim_param),
624 isl_assert(left->ctx,
625 isl_dim_tuple_match(left, isl_dim_out, right, isl_dim_in),
628 dim = isl_dim_alloc(left->ctx, left->nparam, left->n_in, right->n_out);
632 dim = copy_names(dim, isl_dim_param, 0, left, isl_dim_param);
633 dim = copy_names(dim, isl_dim_in, 0, left, isl_dim_in);
634 dim = copy_names(dim, isl_dim_out, 0, right, isl_dim_out);
636 if (dim && left->tuple_name[0] &&
637 !(dim->tuple_name[0] = isl_name_copy(dim->ctx, left->tuple_name[0])))
639 if (dim && right->tuple_name[1] &&
640 !(dim->tuple_name[1] = isl_name_copy(dim->ctx, right->tuple_name[1])))
653 struct isl_dim *isl_dim_product(struct isl_dim *left, struct isl_dim *right)
660 isl_assert(left->ctx, match(left, isl_dim_param, right, isl_dim_param),
663 dim = isl_dim_alloc(left->ctx, left->nparam,
664 left->n_in + right->n_in, left->n_out + right->n_out);
668 dim = copy_names(dim, isl_dim_param, 0, left, isl_dim_param);
669 dim = copy_names(dim, isl_dim_in, 0, left, isl_dim_in);
670 dim = copy_names(dim, isl_dim_in, left->n_in, right, isl_dim_in);
671 dim = copy_names(dim, isl_dim_out, 0, left, isl_dim_out);
672 dim = copy_names(dim, isl_dim_out, left->n_out, right, isl_dim_out);
684 struct isl_dim *isl_dim_map(struct isl_dim *dim)
686 struct isl_name **names = NULL;
690 isl_assert(dim->ctx, dim->n_in == 0, goto error);
691 if (dim->n_out == 0 && !dim->tuple_name[1])
693 dim = isl_dim_cow(dim);
697 names = isl_calloc_array(dim->ctx, struct isl_name *,
698 dim->nparam + dim->n_out + dim->n_out);
701 get_names(dim, isl_dim_param, 0, dim->nparam, names);
702 get_names(dim, isl_dim_out, 0, dim->n_out, names + dim->nparam);
704 dim->n_in = dim->n_out;
708 dim->n_name = dim->nparam + dim->n_out + dim->n_out;
709 dim = copy_names(dim, isl_dim_out, 0, dim, isl_dim_in);
711 isl_name_free(dim->ctx, dim->tuple_name[0]);
712 dim->tuple_name[0] = isl_name_copy(dim->ctx, dim->tuple_name[1]);
719 static struct isl_dim *set_names(struct isl_dim *dim, enum isl_dim_type type,
720 unsigned first, unsigned n, struct isl_name **names)
724 for (i = 0; i < n ; ++i)
725 dim = set_name(dim, type, first+i, names[i]);
730 struct isl_dim *isl_dim_reverse(struct isl_dim *dim)
733 struct isl_name **names = NULL;
734 struct isl_name *name;
738 if (match(dim, isl_dim_in, dim, isl_dim_out))
741 dim = isl_dim_cow(dim);
745 name = dim->tuple_name[0];
746 dim->tuple_name[0] = dim->tuple_name[1];
747 dim->tuple_name[1] = name;
750 names = isl_alloc_array(dim->ctx, struct isl_name *,
751 dim->n_in + dim->n_out);
754 get_names(dim, isl_dim_in, 0, dim->n_in, names);
755 get_names(dim, isl_dim_out, 0, dim->n_out, names + dim->n_in);
759 dim->n_in = dim->n_out;
763 dim = set_names(dim, isl_dim_out, 0, dim->n_out, names);
764 dim = set_names(dim, isl_dim_in, 0, dim->n_in, names + dim->n_out);
775 struct isl_dim *isl_dim_drop(struct isl_dim *dim, enum isl_dim_type type,
776 unsigned first, unsigned num)
783 if (n == 0 && !isl_dim_get_tuple_name(dim, type))
786 isl_assert(dim->ctx, first + num <= n(dim, type), goto error);
787 dim = isl_dim_cow(dim);
791 dim = extend_names(dim);
794 for (i = 0; i < num; ++i)
795 isl_name_free(dim->ctx, get_name(dim, type, first+i));
796 for (i = first+num; i < n(dim, type); ++i)
797 set_name(dim, type, i - num, get_name(dim, type, i));
800 get_names(dim, isl_dim_in, 0, dim->n_in,
801 dim->names + offset(dim, isl_dim_in) - num);
803 get_names(dim, isl_dim_out, 0, dim->n_out,
804 dim->names + offset(dim, isl_dim_out) - num);
811 case isl_dim_param: dim->nparam -= num; break;
812 case isl_dim_in: dim->n_in -= num; break;
813 case isl_dim_out: dim->n_out -= num; break;
815 if (type == isl_dim_in || type == isl_dim_out) {
816 isl_name_free(dim->ctx, dim->tuple_name[type - isl_dim_in]);
817 dim->tuple_name[type - isl_dim_in] = NULL;
825 struct isl_dim *isl_dim_drop_inputs(struct isl_dim *dim,
826 unsigned first, unsigned n)
830 return isl_dim_drop(dim, isl_dim_in, first, n);
833 struct isl_dim *isl_dim_drop_outputs(struct isl_dim *dim,
834 unsigned first, unsigned n)
838 return isl_dim_drop(dim, isl_dim_out, first, n);
841 struct isl_dim *isl_dim_domain(struct isl_dim *dim)
845 dim = isl_dim_drop_outputs(dim, 0, dim->n_out);
846 return isl_dim_reverse(dim);
849 struct isl_dim *isl_dim_range(struct isl_dim *dim)
853 return isl_dim_drop_inputs(dim, 0, dim->n_in);
856 __isl_give isl_dim *isl_dim_as_set_dim(__isl_take isl_dim *dim)
858 dim = isl_dim_cow(dim);
862 dim->n_out += dim->n_in;
864 isl_name_free(dim->ctx, dim->tuple_name[0]);
865 isl_name_free(dim->ctx, dim->tuple_name[1]);
866 dim->tuple_name[0] = NULL;
867 dim->tuple_name[1] = NULL;
872 struct isl_dim *isl_dim_underlying(struct isl_dim *dim, unsigned n_div)
879 dim->nparam == 0 && dim->n_in == 0 && dim->n_name == 0 &&
882 dim = isl_dim_cow(dim);
885 dim->n_out += dim->nparam + dim->n_in + n_div;
889 for (i = 0; i < dim->n_name; ++i)
890 isl_name_free(dim->ctx, get_name(dim, isl_dim_out, i));
892 isl_name_free(dim->ctx, dim->tuple_name[0]);
893 isl_name_free(dim->ctx, dim->tuple_name[1]);
894 dim->tuple_name[0] = NULL;
895 dim->tuple_name[1] = NULL;
900 unsigned isl_dim_total(struct isl_dim *dim)
902 return dim->nparam + dim->n_in + dim->n_out;
905 int isl_dim_equal(struct isl_dim *dim1, struct isl_dim *dim2)
907 return match(dim1, isl_dim_param, dim2, isl_dim_param) &&
908 isl_dim_tuple_match(dim1, isl_dim_in, dim2, isl_dim_in) &&
909 isl_dim_tuple_match(dim1, isl_dim_out, dim2, isl_dim_out);
912 int isl_dim_compatible(struct isl_dim *dim1, struct isl_dim *dim2)
914 return dim1->nparam == dim2->nparam &&
915 dim1->n_in + dim1->n_out == dim2->n_in + dim2->n_out;
918 uint32_t isl_dim_get_hash(__isl_keep isl_dim *dim)
922 struct isl_name *name;
926 hash = isl_hash_init();
928 hash = isl_hash_builtin(hash, dim->nparam);
929 hash = isl_hash_builtin(hash, dim->n_in);
930 hash = isl_hash_builtin(hash, dim->n_out);
932 for (i = 0; i < dim->nparam; ++i) {
933 name = get_name(dim, isl_dim_param, i);
934 hash = isl_hash_builtin(hash, name);
937 name = tuple_name(dim, isl_dim_in);
938 hash = isl_hash_builtin(hash, name);
939 name = tuple_name(dim, isl_dim_out);
940 hash = isl_hash_builtin(hash, name);