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