?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
doc: drop long outdated note on transitive closures
[isl.git] / isl_dim.c
bloba9ae54ebb64b1dabb91f327e385baf9a3923ae28
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_name.h"
16
17 isl_ctx *isl_dim_get_ctx(__isl_keep isl_dim *dim)
18 {
19 return dim ? dim->ctx : NULL;
20 }
21
22 struct isl_dim *isl_dim_alloc(struct isl_ctx *ctx,
23 unsigned nparam, unsigned n_in, unsigned n_out)
24 {
25 struct isl_dim *dim;
26
27 dim = isl_alloc_type(ctx, struct isl_dim);
28 if (!dim)
29 return NULL;
30
31 dim->ctx = ctx;
32 isl_ctx_ref(ctx);
33 dim->ref = 1;
34 dim->nparam = nparam;
35 dim->n_in = n_in;
36 dim->n_out = n_out;
37
38 dim->tuple_name[0] = NULL;
39 dim->tuple_name[1] = NULL;
40
41 dim->nested[0] = NULL;
42 dim->nested[1] = NULL;
43
44 dim->n_name = 0;
45 dim->names = NULL;
46
47 return dim;
48 }
49
50 struct isl_dim *isl_dim_set_alloc(struct isl_ctx *ctx,
51 unsigned nparam, unsigned dim)
52 {
53 return isl_dim_alloc(ctx, nparam, 0, dim);
54 }
55
56 static unsigned global_pos(struct isl_dim *dim,
57 enum isl_dim_type type, unsigned pos)
58 {
59 struct isl_ctx *ctx = dim->ctx;
60
61 switch (type) {
62 case isl_dim_param:
63 isl_assert(ctx, pos < dim->nparam, return isl_dim_total(dim));
64 return pos;
65 case isl_dim_in:
66 isl_assert(ctx, pos < dim->n_in, return isl_dim_total(dim));
67 return pos + dim->nparam;
68 case isl_dim_out:
69 isl_assert(ctx, pos < dim->n_out, return isl_dim_total(dim));
70 return pos + dim->nparam + dim->n_in;
71 default:
72 isl_assert(ctx, 0, return isl_dim_total(dim));
73 }
74 return isl_dim_total(dim);
75 }
76
77 /* Extend length of names array to the total number of dimensions.
78 */
79 static __isl_give isl_dim *extend_names(__isl_take isl_dim *dim)
80 {
81 struct isl_name **names;
82 int i;
83
84 if (isl_dim_total(dim) <= dim->n_name)
85 return dim;
86
87 if (!dim->names) {
88 dim->names = isl_calloc_array(dim->ctx,
89 struct isl_name *, isl_dim_total(dim));
90 if (!dim->names)
91 goto error;
92 } else {
93 names = isl_realloc_array(dim->ctx, dim->names,
94 struct isl_name *, isl_dim_total(dim));
95 if (!names)
96 goto error;
97 dim->names = names;
98 for (i = dim->n_name; i < isl_dim_total(dim); ++i)
99 dim->names[i] = NULL;
100 }
101
102 dim->n_name = isl_dim_total(dim);
103
104 return dim;
105 error:
106 isl_dim_free(dim);
107 return NULL;
108 }
109
110 static struct isl_dim *set_name(struct isl_dim *dim,
111 enum isl_dim_type type, unsigned pos,
112 struct isl_name *name)
113 {
114 struct isl_ctx *ctx = dim->ctx;
115 dim = isl_dim_cow(dim);
116
117 if (!dim)
118 goto error;
119
120 pos = global_pos(dim, type, pos);
121 if (pos == isl_dim_total(dim))
122 goto error;
123
124 if (pos >= dim->n_name) {
125 if (!name)
126 return dim;
127 dim = extend_names(dim);
128 if (!dim)
129 goto error;
130 }
131
132 dim->names[pos] = name;
133
134 return dim;
135 error:
136 isl_name_free(ctx, name);
137 isl_dim_free(dim);
138 return NULL;
139 }
140
141 static struct isl_name *get_name(struct isl_dim *dim,
142 enum isl_dim_type type, unsigned pos)
143 {
144 if (!dim)
145 return NULL;
146
147 pos = global_pos(dim, type, pos);
148 if (pos == isl_dim_total(dim))
149 return NULL;
150 if (pos >= dim->n_name)
151 return NULL;
152 return dim->names[pos];
153 }
154
155 static unsigned offset(struct isl_dim *dim, enum isl_dim_type type)
156 {
157 switch (type) {
158 case isl_dim_param: return 0;
159 case isl_dim_in: return dim->nparam;
160 case isl_dim_out: return dim->nparam + dim->n_in;
161 default: return 0;
162 }
163 }
164
165 static unsigned n(struct isl_dim *dim, enum isl_dim_type type)
166 {
167 switch (type) {
168 case isl_dim_param: return dim->nparam;
169 case isl_dim_in: return dim->n_in;
170 case isl_dim_out: return 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 struct isl_dim *copy_names(struct isl_dim *dst,
190 enum isl_dim_type dst_type, unsigned offset, struct isl_dim *src,
191 enum isl_dim_type src_type)
192 {
193 int i;
194 struct isl_name *name;
195
196 if (!dst)
197 return NULL;
198
199 for (i = 0; i < n(src, src_type); ++i) {
200 name = get_name(src, src_type, i);
201 if (!name)
202 continue;
203 dst = set_name(dst, dst_type, offset + i,
204 isl_name_copy(dst->ctx, name));
205 if (!dst)
206 return NULL;
207 }
208 return dst;
209 }
210
211 struct isl_dim *isl_dim_dup(struct isl_dim *dim)
212 {
213 struct isl_dim *dup;
214 if (!dim)
215 return NULL;
216 dup = isl_dim_alloc(dim->ctx, dim->nparam, dim->n_in, dim->n_out);
217 if (dim->tuple_name[0] &&
218 !(dup->tuple_name[0] = isl_name_copy(dim->ctx, dim->tuple_name[0])))
219 goto error;
220 if (dim->tuple_name[1] &&
221 !(dup->tuple_name[1] = isl_name_copy(dim->ctx, dim->tuple_name[1])))
222 goto error;
223 if (dim->nested[0] && !(dup->nested[0] = isl_dim_copy(dim->nested[0])))
224 goto error;
225 if (dim->nested[1] && !(dup->nested[1] = isl_dim_copy(dim->nested[1])))
226 goto error;
227 if (!dim->names)
228 return dup;
229 dup = copy_names(dup, isl_dim_param, 0, dim, isl_dim_param);
230 dup = copy_names(dup, isl_dim_in, 0, dim, isl_dim_in);
231 dup = copy_names(dup, isl_dim_out, 0, dim, isl_dim_out);
232 return dup;
233 error:
234 isl_dim_free(dup);
235 return NULL;
236 }
237
238 struct isl_dim *isl_dim_cow(struct isl_dim *dim)
239 {
240 if (!dim)
241 return NULL;
242
243 if (dim->ref == 1)
244 return dim;
245 dim->ref--;
246 return isl_dim_dup(dim);
247 }
248
249 struct isl_dim *isl_dim_copy(struct isl_dim *dim)
250 {
251 if (!dim)
252 return NULL;
253
254 dim->ref++;
255 return dim;
256 }
257
258 void isl_dim_free(struct isl_dim *dim)
259 {
260 int i;
261
262 if (!dim)
263 return;
264
265 if (--dim->ref > 0)
266 return;
267
268 isl_name_free(dim->ctx, dim->tuple_name[0]);
269 isl_name_free(dim->ctx, dim->tuple_name[1]);
270
271 isl_dim_free(dim->nested[0]);
272 isl_dim_free(dim->nested[1]);
273
274 for (i = 0; i < dim->n_name; ++i)
275 isl_name_free(dim->ctx, dim->names[i]);
276 free(dim->names);
277 isl_ctx_deref(dim->ctx);
278
279 free(dim);
280 }
281
282 static int name_ok(isl_ctx *ctx, const char *s)
283 {
284 char *p;
285 long dummy;
286
287 dummy = strtol(s, &p, 0);
288 if (p != s)
289 isl_die(ctx, isl_error_invalid, "name looks like a number",
290 return 0);
291
292 return 1;
293 }
294
295 __isl_give isl_dim *isl_dim_set_tuple_name(__isl_take isl_dim *dim,
296 enum isl_dim_type type, const char *s)
297 {
298 struct isl_name *name;
299
300 dim = isl_dim_cow(dim);
301 if (!dim)
302 return NULL;
303 if (type != isl_dim_in && type != isl_dim_out)
304 isl_die(dim->ctx, isl_error_invalid,
305 "only input, output and set tuples can have names",
306 goto error);
307 if (!s) {
308 name = NULL;
309 } else {
310 if (!name_ok(dim->ctx, s))
311 goto error;
312 name = isl_name_get(dim->ctx, s);
313 if (!name)
314 goto error;
315 }
316
317 isl_name_free(dim->ctx, dim->tuple_name[type - isl_dim_in]);
318 dim->tuple_name[type - isl_dim_in] = name;
319
320 return dim;
321 error:
322 isl_dim_free(dim);
323 return NULL;
324 }
325
326 const char *isl_dim_get_tuple_name(__isl_keep isl_dim *dim,
327 enum isl_dim_type type)
328 {
329 struct isl_name *name;
330 if (!dim)
331 return NULL;
332 if (type != isl_dim_in && type != isl_dim_out)
333 return NULL;
334 name = dim->tuple_name[type - isl_dim_in];
335 return name ? name->name : NULL;
336 }
337
338 struct isl_dim *isl_dim_set_name(struct isl_dim *dim,
339 enum isl_dim_type type, unsigned pos,
340 const char *s)
341 {
342 struct isl_name *name;
343
344 if (!dim)
345 return NULL;
346 if (!name_ok(dim->ctx, s))
347 goto error;
348 isl_name_free(dim->ctx, get_name(dim, type, pos));
349 name = isl_name_get(dim->ctx, s);
350 if (!name)
351 goto error;
352 return set_name(dim, type, pos, name);
353 error:
354 isl_dim_free(dim);
355 return NULL;
356 }
357
358 const char *isl_dim_get_name(struct isl_dim *dim,
359 enum isl_dim_type type, unsigned pos)
360 {
361 struct isl_name *name = get_name(dim, type, pos);
362 return name ? name->name : NULL;
363 }
364
365 static struct isl_name *tuple_name(__isl_keep isl_dim *dim,
366 enum isl_dim_type type)
367 {
368 if (!dim)
369 return NULL;
370 if (type == isl_dim_in)
371 return dim->tuple_name[0];
372 if (type == isl_dim_out)
373 return dim->tuple_name[1];
374 return NULL;
375 }
376
377 static __isl_keep isl_dim *nested(__isl_keep isl_dim *dim,
378 enum isl_dim_type type)
379 {
380 if (!dim)
381 return NULL;
382 if (type == isl_dim_in)
383 return dim->nested[0];
384 if (type == isl_dim_out)
385 return dim->nested[1];
386 return NULL;
387 }
388
389 int isl_dim_tuple_match(__isl_keep isl_dim *dim1, enum isl_dim_type dim1_type,
390 __isl_keep isl_dim *dim2, enum isl_dim_type dim2_type)
391 {
392 struct isl_name *name1, *name2;
393 isl_dim *nested1, *nested2;
394
395 if (n(dim1, dim1_type) != n(dim2, dim2_type))
396 return 0;
397 name1 = tuple_name(dim1, dim1_type);
398 name2 = tuple_name(dim2, dim2_type);
399 if (!name1 ^ !name2)
400 return 0;
401 if (name1 && name1->name != name2->name)
402 return 0;
403 nested1 = nested(dim1, dim1_type);
404 nested2 = nested(dim2, dim2_type);
405 if (!nested1 ^ !nested2)
406 return 0;
407 if (nested1 && !isl_dim_equal(nested1, nested2))
408 return 0;
409 return 1;
410 }
411
412 static int match(struct isl_dim *dim1, enum isl_dim_type dim1_type,
413 struct isl_dim *dim2, enum isl_dim_type dim2_type)
414 {
415 int i;
416
417 if (!isl_dim_tuple_match(dim1, dim1_type, dim2, dim2_type))
418 return 0;
419
420 if (!dim1->names && !dim2->names)
421 return 1;
422
423 for (i = 0; i < n(dim1, dim1_type); ++i) {
424 if (get_name(dim1, dim1_type, i) !=
425 get_name(dim2, dim2_type, i))
426 return 0;
427 }
428 return 1;
429 }
430
431 int isl_dim_match(struct isl_dim *dim1, enum isl_dim_type dim1_type,
432 struct isl_dim *dim2, enum isl_dim_type dim2_type)
433 {
434 return match(dim1, dim1_type, dim2, dim2_type);
435 }
436
437 static void get_names(struct isl_dim *dim, enum isl_dim_type type,
438 unsigned first, unsigned n, struct isl_name **names)
439 {
440 int i;
441
442 for (i = 0; i < n ; ++i)
443 names[i] = get_name(dim, type, first+i);
444 }
445
446 struct isl_dim *isl_dim_extend(struct isl_dim *dim,
447 unsigned nparam, unsigned n_in, unsigned n_out)
448 {
449 struct isl_name **names = NULL;
450
451 if (!dim)
452 return NULL;
453 if (dim->nparam == nparam && dim->n_in == n_in && dim->n_out == n_out)
454 return dim;
455
456 isl_assert(dim->ctx, dim->nparam <= nparam, goto error);
457 isl_assert(dim->ctx, dim->n_in <= n_in, goto error);
458 isl_assert(dim->ctx, dim->n_out <= n_out, goto error);
459
460 dim = isl_dim_cow(dim);
461
462 if (dim->names) {
463 names = isl_calloc_array(dim->ctx, struct isl_name *,
464 nparam + n_in + n_out);
465 if (!names)
466 goto error;
467 get_names(dim, isl_dim_param, 0, dim->nparam, names);
468 get_names(dim, isl_dim_in, 0, dim->n_in, names + nparam);
469 get_names(dim, isl_dim_out, 0, dim->n_out,
470 names + nparam + n_in);
471 free(dim->names);
472 dim->names = names;
473 dim->n_name = nparam + n_in + n_out;
474 }
475 dim->nparam = nparam;
476 dim->n_in = n_in;
477 dim->n_out = n_out;
478
479 return dim;
480 error:
481 free(names);
482 isl_dim_free(dim);
483 return NULL;
484 }
485
486 struct isl_dim *isl_dim_add(struct isl_dim *dim, enum isl_dim_type type,
487 unsigned n)
488 {
489 if (!dim)
490 return NULL;
491 dim = isl_dim_reset(dim, type);
492 switch (type) {
493 case isl_dim_param:
494 dim = isl_dim_extend(dim,
495 dim->nparam + n, dim->n_in, dim->n_out);
496 if (dim && dim->nested[0] &&
497 !(dim->nested[0] = isl_dim_add(dim->nested[0],
498 isl_dim_param, n)))
499 goto error;
500 if (dim && dim->nested[1] &&
501 !(dim->nested[1] = isl_dim_add(dim->nested[1],
502 isl_dim_param, n)))
503 goto error;
504 return dim;
505 case isl_dim_in:
506 return isl_dim_extend(dim,
507 dim->nparam, dim->n_in + n, dim->n_out);
508 case isl_dim_out:
509 return isl_dim_extend(dim,
510 dim->nparam, dim->n_in, dim->n_out + n);
511 }
512 return dim;
513 error:
514 isl_dim_free(dim);
515 return NULL;
516 }
517
518 __isl_give isl_dim *isl_dim_insert(__isl_take isl_dim *dim,
519 enum isl_dim_type type, unsigned pos, unsigned n)
520 {
521 struct isl_name **names = NULL;
522
523 if (!dim)
524 return NULL;
525 if (n == 0)
526 return isl_dim_reset(dim, type);
527
528 isl_assert(dim->ctx, pos <= isl_dim_size(dim, type), goto error);
529
530 dim = isl_dim_cow(dim);
531 if (!dim)
532 return NULL;
533
534 if (dim->names) {
535 enum isl_dim_type t;
536 int off;
537 int s[3];
538 int *size = s - isl_dim_param;
539 names = isl_calloc_array(dim->ctx, struct isl_name *,
540 dim->nparam + dim->n_in + dim->n_out + n);
541 if (!names)
542 goto error;
543 off = 0;
544 size[isl_dim_param] = dim->nparam;
545 size[isl_dim_in] = dim->n_in;
546 size[isl_dim_out] = dim->n_out;
547 for (t = isl_dim_param; t <= isl_dim_out; ++t) {
548 if (t != type) {
549 get_names(dim, t, 0, size[t], names + off);
550 off += size[t];
551 } else {
552 get_names(dim, t, 0, pos, names + off);
553 off += pos + n;
554 get_names(dim, t, pos, size[t]-pos, names+off);
555 off += size[t] - pos;
556 }
557 }
558 free(dim->names);
559 dim->names = names;
560 dim->n_name = dim->nparam + dim->n_in + dim->n_out + n;
561 }
562 switch (type) {
563 case isl_dim_param: dim->nparam += n; break;
564 case isl_dim_in: dim->n_in += n; break;
565 case isl_dim_out: dim->n_out += n; break;
566 }
567 dim = isl_dim_reset(dim, type);
568
569 return dim;
570 error:
571 isl_dim_free(dim);
572 return NULL;
573 }
574
575 __isl_give isl_dim *isl_dim_move(__isl_take isl_dim *dim,
576 enum isl_dim_type dst_type, unsigned dst_pos,
577 enum isl_dim_type src_type, unsigned src_pos, unsigned n)
578 {
579 int i;
580
581 if (!dim)
582 return NULL;
583 if (n == 0)
584 return dim;
585
586 isl_assert(dim->ctx, src_pos + n <= isl_dim_size(dim, src_type),
587 goto error);
588
589 if (dst_type == src_type && dst_pos == src_pos)
590 return dim;
591
592 isl_assert(dim->ctx, dst_type != src_type, goto error);
593
594 dim = isl_dim_reset(dim, src_type);
595 dim = isl_dim_reset(dim, dst_type);
596
597 dim = isl_dim_cow(dim);
598 if (!dim)
599 return NULL;
600
601 if (dim->names) {
602 struct isl_name **names;
603 enum isl_dim_type t;
604 int off;
605 int s[3];
606 int *size = s - isl_dim_param;
607 names = isl_calloc_array(dim->ctx, struct isl_name *,
608 dim->nparam + dim->n_in + dim->n_out);
609 if (!names)
610 goto error;
611 off = 0;
612 size[isl_dim_param] = dim->nparam;
613 size[isl_dim_in] = dim->n_in;
614 size[isl_dim_out] = dim->n_out;
615 for (t = isl_dim_param; t <= isl_dim_out; ++t) {
616 if (t == dst_type) {
617 get_names(dim, t, 0, dst_pos, names + off);
618 off += dst_pos;
619 get_names(dim, src_type, src_pos, n, names+off);
620 off += n;
621 get_names(dim, t, dst_pos, size[t] - dst_pos,
622 names + off);
623 off += size[t] - dst_pos;
624 } else if (t == src_type) {
625 get_names(dim, t, 0, src_pos, names + off);
626 off += src_pos;
627 get_names(dim, t, src_pos + n,
628 size[t] - src_pos - n, names + off);
629 off += size[t] - src_pos - n;
630 } else {
631 get_names(dim, t, 0, size[t], names + off);
632 off += size[t];
633 }
634 }
635 free(dim->names);
636 dim->names = names;
637 dim->n_name = dim->nparam + dim->n_in + dim->n_out;
638 }
639
640 switch (dst_type) {
641 case isl_dim_param: dim->nparam += n; break;
642 case isl_dim_in: dim->n_in += n; break;
643 case isl_dim_out: dim->n_out += n; break;
644 }
645
646 switch (src_type) {
647 case isl_dim_param: dim->nparam -= n; break;
648 case isl_dim_in: dim->n_in -= n; break;
649 case isl_dim_out: dim->n_out -= n; break;
650 }
651
652 if (dst_type != isl_dim_param && src_type != isl_dim_param)
653 return dim;
654
655 for (i = 0; i < 2; ++i) {
656 if (!dim->nested[i])
657 continue;
658 dim->nested[i] = isl_dim_replace(dim->nested[i],
659 isl_dim_param, dim);
660 if (!dim->nested[i])
661 goto error;
662 }
663
664 return dim;
665 error:
666 isl_dim_free(dim);
667 return NULL;
668 }
669
670 struct isl_dim *isl_dim_join(struct isl_dim *left, struct isl_dim *right)
671 {
672 struct isl_dim *dim;
673
674 if (!left || !right)
675 goto error;
676
677 isl_assert(left->ctx, match(left, isl_dim_param, right, isl_dim_param),
678 goto error);
679 isl_assert(left->ctx,
680 isl_dim_tuple_match(left, isl_dim_out, right, isl_dim_in),
681 goto error);
682
683 dim = isl_dim_alloc(left->ctx, left->nparam, left->n_in, right->n_out);
684 if (!dim)
685 goto error;
686
687 dim = copy_names(dim, isl_dim_param, 0, left, isl_dim_param);
688 dim = copy_names(dim, isl_dim_in, 0, left, isl_dim_in);
689 dim = copy_names(dim, isl_dim_out, 0, right, isl_dim_out);
690
691 if (dim && left->tuple_name[0] &&
692 !(dim->tuple_name[0] = isl_name_copy(dim->ctx, left->tuple_name[0])))
693 goto error;
694 if (dim && right->tuple_name[1] &&
695 !(dim->tuple_name[1] = isl_name_copy(dim->ctx, right->tuple_name[1])))
696 goto error;
697 if (dim && left->nested[0] &&
698 !(dim->nested[0] = isl_dim_copy(left->nested[0])))
699 goto error;
700 if (dim && right->nested[1] &&
701 !(dim->nested[1] = isl_dim_copy(right->nested[1])))
702 goto error;
703
704 isl_dim_free(left);
705 isl_dim_free(right);
706
707 return dim;
708 error:
709 isl_dim_free(left);
710 isl_dim_free(right);
711 return NULL;
712 }
713
714 struct isl_dim *isl_dim_product(struct isl_dim *left, struct isl_dim *right)
715 {
716 isl_dim *dom1, *dom2, *nest1, *nest2;
717
718 if (!left || !right)
719 goto error;
720
721 isl_assert(left->ctx, match(left, isl_dim_param, right, isl_dim_param),
722 goto error);
723
724 dom1 = isl_dim_domain(isl_dim_copy(left));
725 dom2 = isl_dim_domain(isl_dim_copy(right));
726 nest1 = isl_dim_wrap(isl_dim_join(isl_dim_reverse(dom1), dom2));
727
728 dom1 = isl_dim_range(left);
729 dom2 = isl_dim_range(right);
730 nest2 = isl_dim_wrap(isl_dim_join(isl_dim_reverse(dom1), dom2));
731
732 return isl_dim_join(isl_dim_reverse(nest1), nest2);
733 error:
734 isl_dim_free(left);
735 isl_dim_free(right);
736 return NULL;
737 }
738
739 __isl_give isl_dim *isl_dim_range_product(__isl_take isl_dim *left,
740 __isl_take isl_dim *right)
741 {
742 isl_dim *dom, *ran1, *ran2, *nest;
743
744 if (!left || !right)
745 goto error;
746
747 isl_assert(left->ctx, match(left, isl_dim_param, right, isl_dim_param),
748 goto error);
749 if (!isl_dim_match(left, isl_dim_in, right, isl_dim_in))
750 isl_die(left->ctx, isl_error_invalid,
751 "domains need to match", goto error);
752
753 dom = isl_dim_domain(isl_dim_copy(left));
754
755 ran1 = isl_dim_range(left);
756 ran2 = isl_dim_range(right);
757 nest = isl_dim_wrap(isl_dim_join(isl_dim_reverse(ran1), ran2));
758
759 return isl_dim_join(isl_dim_reverse(dom), nest);
760 error:
761 isl_dim_free(left);
762 isl_dim_free(right);
763 return NULL;
764 }
765
766 __isl_give isl_dim *isl_dim_map_from_set(__isl_take isl_dim *dim)
767 {
768 struct isl_name **names = NULL;
769
770 if (!dim)
771 return NULL;
772 isl_assert(dim->ctx, dim->n_in == 0, goto error);
773 if (dim->n_out == 0 && !isl_dim_is_named_or_nested(dim, isl_dim_out))
774 return dim;
775 dim = isl_dim_cow(dim);
776 if (!dim)
777 return NULL;
778 if (dim->names) {
779 names = isl_calloc_array(dim->ctx, struct isl_name *,
780 dim->nparam + dim->n_out + dim->n_out);
781 if (!names)
782 goto error;
783 get_names(dim, isl_dim_param, 0, dim->nparam, names);
784 get_names(dim, isl_dim_out, 0, dim->n_out, names + dim->nparam);
785 }
786 dim->n_in = dim->n_out;
787 if (names) {
788 free(dim->names);
789 dim->names = names;
790 dim->n_name = dim->nparam + dim->n_out + dim->n_out;
791 dim = copy_names(dim, isl_dim_out, 0, dim, isl_dim_in);
792 }
793 isl_name_free(dim->ctx, dim->tuple_name[0]);
794 dim->tuple_name[0] = isl_name_copy(dim->ctx, dim->tuple_name[1]);
795 isl_dim_free(dim->nested[0]);
796 dim->nested[0] = isl_dim_copy(dim->nested[1]);
797 return dim;
798 error:
799 isl_dim_free(dim);
800 return NULL;
801 }
802
803 static struct isl_dim *set_names(struct isl_dim *dim, enum isl_dim_type type,
804 unsigned first, unsigned n, struct isl_name **names)
805 {
806 int i;
807
808 for (i = 0; i < n ; ++i)
809 dim = set_name(dim, type, first+i, names[i]);
810
811 return dim;
812 }
813
814 struct isl_dim *isl_dim_reverse(struct isl_dim *dim)
815 {
816 unsigned t;
817 isl_dim *nested;
818 struct isl_name **names = NULL;
819 struct isl_name *name;
820
821 if (!dim)
822 return NULL;
823 if (match(dim, isl_dim_in, dim, isl_dim_out))
824 return dim;
825
826 dim = isl_dim_cow(dim);
827 if (!dim)
828 return NULL;
829
830 name = dim->tuple_name[0];
831 dim->tuple_name[0] = dim->tuple_name[1];
832 dim->tuple_name[1] = name;
833
834 nested = dim->nested[0];
835 dim->nested[0] = dim->nested[1];
836 dim->nested[1] = nested;
837
838 if (dim->names) {
839 names = isl_alloc_array(dim->ctx, struct isl_name *,
840 dim->n_in + dim->n_out);
841 if (!names)
842 goto error;
843 get_names(dim, isl_dim_in, 0, dim->n_in, names);
844 get_names(dim, isl_dim_out, 0, dim->n_out, names + dim->n_in);
845 }
846
847 t = dim->n_in;
848 dim->n_in = dim->n_out;
849 dim->n_out = t;
850
851 if (dim->names) {
852 dim = set_names(dim, isl_dim_out, 0, dim->n_out, names);
853 dim = set_names(dim, isl_dim_in, 0, dim->n_in, names + dim->n_out);
854 free(names);
855 }
856
857 return dim;
858 error:
859 free(names);
860 isl_dim_free(dim);
861 return NULL;
862 }
863
864 struct isl_dim *isl_dim_drop(struct isl_dim *dim, enum isl_dim_type type,
865 unsigned first, unsigned num)
866 {
867 int i;
868
869 if (!dim)
870 return NULL;
871
872 if (n == 0)
873 return isl_dim_reset(dim, type);
874
875 isl_assert(dim->ctx, first + num <= n(dim, type), goto error);
876 dim = isl_dim_cow(dim);
877 if (!dim)
878 goto error;
879 if (dim->names) {
880 dim = extend_names(dim);
881 if (!dim)
882 goto error;
883 for (i = 0; i < num; ++i)
884 isl_name_free(dim->ctx, get_name(dim, type, first+i));
885 for (i = first+num; i < n(dim, type); ++i)
886 set_name(dim, type, i - num, get_name(dim, type, i));
887 switch (type) {
888 case isl_dim_param:
889 get_names(dim, isl_dim_in, 0, dim->n_in,
890 dim->names + offset(dim, isl_dim_in) - num);
891 case isl_dim_in:
892 get_names(dim, isl_dim_out, 0, dim->n_out,
893 dim->names + offset(dim, isl_dim_out) - num);
894 case isl_dim_out:
895 ;
896 }
897 dim->n_name -= num;
898 }
899 switch (type) {
900 case isl_dim_param: dim->nparam -= num; break;
901 case isl_dim_in: dim->n_in -= num; break;
902 case isl_dim_out: dim->n_out -= num; break;
903 }
904 dim = isl_dim_reset(dim, type);
905 if (type == isl_dim_param) {
906 if (dim && dim->nested[0] &&
907 !(dim->nested[0] = isl_dim_drop(dim->nested[0],
908 isl_dim_param, first, num)))
909 goto error;
910 if (dim && dim->nested[1] &&
911 !(dim->nested[1] = isl_dim_drop(dim->nested[1],
912 isl_dim_param, first, num)))
913 goto error;
914 }
915 return dim;
916 error:
917 isl_dim_free(dim);
918 return NULL;
919 }
920
921 struct isl_dim *isl_dim_drop_inputs(struct isl_dim *dim,
922 unsigned first, unsigned n)
923 {
924 if (!dim)
925 return NULL;
926 return isl_dim_drop(dim, isl_dim_in, first, n);
927 }
928
929 struct isl_dim *isl_dim_drop_outputs(struct isl_dim *dim,
930 unsigned first, unsigned n)
931 {
932 if (!dim)
933 return NULL;
934 return isl_dim_drop(dim, isl_dim_out, first, n);
935 }
936
937 struct isl_dim *isl_dim_domain(struct isl_dim *dim)
938 {
939 if (!dim)
940 return NULL;
941 dim = isl_dim_drop_outputs(dim, 0, dim->n_out);
942 return isl_dim_reverse(dim);
943 }
944
945 __isl_give isl_dim *isl_dim_from_domain(__isl_take isl_dim *dim)
946 {
947 return isl_dim_reverse(dim);
948 }
949
950 struct isl_dim *isl_dim_range(struct isl_dim *dim)
951 {
952 if (!dim)
953 return NULL;
954 return isl_dim_drop_inputs(dim, 0, dim->n_in);
955 }
956
957 __isl_give isl_dim *isl_dim_from_range(__isl_take isl_dim *dim)
958 {
959 return dim;
960 }
961
962 __isl_give isl_dim *isl_dim_as_set_dim(__isl_take isl_dim *dim)
963 {
964 dim = isl_dim_cow(dim);
965 if (!dim)
966 return NULL;
967
968 dim->n_out += dim->n_in;
969 dim->n_in = 0;
970 dim = isl_dim_reset(dim, isl_dim_in);
971 dim = isl_dim_reset(dim, isl_dim_out);
972
973 return dim;
974 }
975
976 struct isl_dim *isl_dim_underlying(struct isl_dim *dim, unsigned n_div)
977 {
978 int i;
979
980 if (!dim)
981 return NULL;
982 if (n_div == 0 &&
983 dim->nparam == 0 && dim->n_in == 0 && dim->n_name == 0)
984 return isl_dim_reset(isl_dim_reset(dim, isl_dim_in), isl_dim_out);
985 dim = isl_dim_cow(dim);
986 if (!dim)
987 return NULL;
988 dim->n_out += dim->nparam + dim->n_in + n_div;
989 dim->nparam = 0;
990 dim->n_in = 0;
991
992 for (i = 0; i < dim->n_name; ++i)
993 isl_name_free(dim->ctx, get_name(dim, isl_dim_out, i));
994 dim->n_name = 0;
995 dim = isl_dim_reset(dim, isl_dim_in);
996 dim = isl_dim_reset(dim, isl_dim_out);
997
998 return dim;
999 }
1000
1001 unsigned isl_dim_total(struct isl_dim *dim)
1002 {
1003 return dim ? dim->nparam + dim->n_in + dim->n_out : 0;
1004 }
1005
1006 int isl_dim_equal(struct isl_dim *dim1, struct isl_dim *dim2)
1007 {
1008 return match(dim1, isl_dim_param, dim2, isl_dim_param) &&
1009 isl_dim_tuple_match(dim1, isl_dim_in, dim2, isl_dim_in) &&
1010 isl_dim_tuple_match(dim1, isl_dim_out, dim2, isl_dim_out);
1011 }
1012
1013 int isl_dim_compatible(struct isl_dim *dim1, struct isl_dim *dim2)
1014 {
1015 return dim1->nparam == dim2->nparam &&
1016 dim1->n_in + dim1->n_out == dim2->n_in + dim2->n_out;
1017 }
1018
1019 static uint32_t isl_hash_dim(uint32_t hash, __isl_keep isl_dim *dim)
1020 {
1021 int i;
1022 struct isl_name *name;
1023
1024 if (!dim)
1025 return hash;
1026
1027 hash = isl_hash_builtin(hash, dim->nparam);
1028 hash = isl_hash_builtin(hash, dim->n_in);
1029 hash = isl_hash_builtin(hash, dim->n_out);
1030
1031 for (i = 0; i < dim->nparam; ++i) {
1032 name = get_name(dim, isl_dim_param, i);
1033 hash = isl_hash_name(hash, name);
1034 }
1035
1036 name = tuple_name(dim, isl_dim_in);
1037 hash = isl_hash_name(hash, name);
1038 name = tuple_name(dim, isl_dim_out);
1039 hash = isl_hash_name(hash, name);
1040
1041 hash = isl_hash_dim(hash, dim->nested[0]);
1042 hash = isl_hash_dim(hash, dim->nested[1]);
1043
1044 return hash;
1045 }
1046
1047 uint32_t isl_dim_get_hash(__isl_keep isl_dim *dim)
1048 {
1049 uint32_t hash;
1050
1051 if (!dim)
1052 return 0;
1053
1054 hash = isl_hash_init();
1055 hash = isl_hash_dim(hash, dim);
1056
1057 return hash;
1058 }
1059
1060 int isl_dim_is_wrapping(__isl_keep isl_dim *dim)
1061 {
1062 if (!dim)
1063 return -1;
1064
1065 if (dim->n_in != 0 || dim->tuple_name[0] || dim->nested[0])
1066 return 0;
1067
1068 return dim->nested[1] != NULL;
1069 }
1070
1071 __isl_give isl_dim *isl_dim_wrap(__isl_take isl_dim *dim)
1072 {
1073 isl_dim *wrap;
1074
1075 if (!dim)
1076 return NULL;
1077
1078 wrap = isl_dim_alloc(dim->ctx, dim->nparam, 0, dim->n_in + dim->n_out);
1079
1080 wrap = copy_names(wrap, isl_dim_param, 0, dim, isl_dim_param);
1081 wrap = copy_names(wrap, isl_dim_set, 0, dim, isl_dim_in);
1082 wrap = copy_names(wrap, isl_dim_set, dim->n_in, dim, isl_dim_out);
1083
1084 if (!wrap)
1085 goto error;
1086
1087 wrap->nested[1] = dim;
1088
1089 return wrap;
1090 error:
1091 isl_dim_free(dim);
1092 return NULL;
1093 }
1094
1095 __isl_give isl_dim *isl_dim_unwrap(__isl_take isl_dim *dim)
1096 {
1097 isl_dim *unwrap;
1098
1099 if (!dim)
1100 return NULL;
1101
1102 if (!isl_dim_is_wrapping(dim))
1103 isl_die(dim->ctx, isl_error_invalid, "not a wrapping dim",
1104 goto error);
1105
1106 unwrap = isl_dim_copy(dim->nested[1]);
1107 isl_dim_free(dim);
1108
1109 return unwrap;
1110 error:
1111 isl_dim_free(dim);
1112 return NULL;
1113 }
1114
1115 int isl_dim_is_named_or_nested(__isl_keep isl_dim *dim, enum isl_dim_type type)
1116 {
1117 if (type != isl_dim_in && type != isl_dim_out)
1118 return 0;
1119 if (!dim)
1120 return -1;
1121 if (dim->tuple_name[type - isl_dim_in])
1122 return 1;
1123 if (dim->nested[type - isl_dim_in])
1124 return 1;
1125 return 0;
1126 }
1127
1128 __isl_give isl_dim *isl_dim_reset(__isl_take isl_dim *dim,
1129 enum isl_dim_type type)
1130 {
1131 if (!isl_dim_is_named_or_nested(dim, type))
1132 return dim;
1133
1134 dim = isl_dim_cow(dim);
1135 if (!dim)
1136 return NULL;
1137
1138 isl_name_free(dim->ctx, dim->tuple_name[type - isl_dim_in]);
1139 dim->tuple_name[type - isl_dim_in] = NULL;
1140 isl_dim_free(dim->nested[type - isl_dim_in]);
1141 dim->nested[type - isl_dim_in] = NULL;
1142
1143 return dim;
1144 }
1145
1146 __isl_give isl_dim *isl_dim_flatten(__isl_take isl_dim *dim)
1147 {
1148 if (!dim)
1149 return NULL;
1150 if (!dim->nested[0] && !dim->nested[1])
1151 return dim;
1152
1153 if (dim->nested[0])
1154 dim = isl_dim_reset(dim, isl_dim_in);
1155 if (dim && dim->nested[1])
1156 dim = isl_dim_reset(dim, isl_dim_out);
1157
1158 return dim;
1159 }
1160
1161 /* Replace the dimensions of the given type of dst by those of src.
1162 */
1163 __isl_give isl_dim *isl_dim_replace(__isl_take isl_dim *dst,
1164 enum isl_dim_type type, __isl_keep isl_dim *src)
1165 {
1166 dst = isl_dim_cow(dst);
1167
1168 if (!dst || !src)
1169 goto error;
1170
1171 dst = isl_dim_drop(dst, type, 0, isl_dim_size(dst, type));
1172 dst = isl_dim_add(dst, type, isl_dim_size(src, type));
1173 dst = copy_names(dst, type, 0, src, type);
1174
1175 if (dst && type == isl_dim_param) {
1176 int i;
1177 for (i = 0; i <= 1; ++i) {
1178 if (!dst->nested[i])
1179 continue;
1180 dst->nested[i] = isl_dim_replace(dst->nested[i],
1181 type, src);
1182 if (!dst->nested[i])
1183 goto error;
1184 }
1185 }
1186
1187 return dst;
1188 error:
1189 isl_dim_free(dst);
1190 return NULL;
1191 }
1192
1193 /* Given a dimension specification "dim" of a set, create a dimension
1194 * specification for the lift of the set. In particular, the result
1195 * is of the form [dim -> local[..]], with n_local variables in the
1196 * range of the wrapped map.
1197 */
1198 __isl_give isl_dim *isl_dim_lift(__isl_take isl_dim *dim, unsigned n_local)
1199 {
1200 isl_dim *local_dim;
1201
1202 if (!dim)
1203 return NULL;
1204
1205 local_dim = isl_dim_dup(dim);
1206 local_dim = isl_dim_drop(local_dim, isl_dim_set, 0, dim->n_out);
1207 local_dim = isl_dim_add(local_dim, isl_dim_set, n_local);
1208 local_dim = isl_dim_set_tuple_name(local_dim, isl_dim_set, "local");
1209 dim = isl_dim_join(isl_dim_from_domain(dim),
1210 isl_dim_from_range(local_dim));
1211 dim = isl_dim_wrap(dim);
1212 dim = isl_dim_set_tuple_name(dim, isl_dim_set, "lifted");
1213
1214 return dim;
1215 }
Integer set library